Low Error Design Methodology for Power Grid Analysis and FFT
Date Issued
2012
Date
2012
Author(s)
Wei, Chun-jen
Abstract
Heuristic and approximation algorithms are commonly used to solve real-world problems. Certain degree of error is allowed to lower the computation complexity and practical runtime. This implicitly becomes a design paradigm constantly used, which seems to be a worthy trade-off made between the accuracy and the runtime. However, experimental results show that we can decrease the runtime by increasing the accuracy of an algorithm. In this work, two cases are studied.
The first case is the analysis of power grid adopting an accurate partition scheme. The runtime is reduced with lower maximum memory usages. Higher accuracy and portability also make it adequate to work with other advanced parallel solvers as a multi-level parallel analyzing system for larger power grids. Beyond the above accurate non-arithmetic method, the second case describes the performance gain in using an accurate arithmetic model to aid the design and verification of fixed-point fast Fourier transforms. In this case, we first derive a model capable of computing the signal-to-quantization-noise ratio as accurate as that of simulating with ten thousand sets of input combinations. Then we arithmetically compute the necessary number of fractional bits of each variable in a fixed-point fast Fourier transform given a signal-to-quantization-noise ratio constraint. An algorithm facilitated by a novel idea is presented. All the resultant FFT designs accurately meet the constraint.
Conventionally a solution is generated by inaccurate computations when error is allowed. Technologies such as search are used later for refinement. A loose constraint eases the computation but refinement afterward encumbers the performance. By contrast, our method and model are developed to achieve the highest accuracy and produce better results in a shorter runtime. The experimental results will show tightening the tolerance during algorithm development achieves better performance.
Subjects
power grid
power distribution network
nodal analysis
matrix
system equations
LU decomposition
algebraic multigrid
partition
parallel processing
rounding error
mean
variance
mean square error
truncation
fast Fourier transform
DFT
FFT
optimization
bit width
word length
algorithm
variable weight
SQNR
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-101-D92921022-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):f84bdedaa0b3454c8a99d5cdb5890b7a