應用於電源網路分析和快速傅立葉轉換之低誤差設計方法論

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.