集合體基礎的代數多重網格方法在晶片上功率網路分析上的應用

Abstract

隨著次深次微米技術演進到0.18微米以下，晶片上功率傳輸網路的分析，已經變成在今日的高效能晶片設計下的ㄧ個非常重要而且具挑戰性的ㄧ個問題。功率傳輸網路上較低的電源電壓，將會減少電路的雜訊容忍度。除此之外，較高的電路操作頻率，將使得由Ldi/dt電壓壓降而來的電路雜訊為之增加。這些效應將會增加功率傳輸網路的設計複雜度以及對於有效率的功率傳輸網路分析方法的需求。 在本篇論文當中，對於功率傳輸網路分析，我們提出了ㄧ個以集合體基礎的代數多重網格分析方法。首先，我們將原始的功率傳輸網路模擬成許多RLKC元件以及片段線性的電流源。然後，利用修飾節點分析方法，我們可以把原始問題轉換成一個Ax=b的線性代數問題。在此，A是一個 的矩陣，x和b是 的向量。在對於這個線性代數問題，應用了我們的集合體演算法之後，我們可以把原始的系統矩陣分成許多小的子矩陣，並實行一個代數的切割去簡化問題。 實驗結果顯示出，我們的集合體基礎的代數多重網格方法，在時間和記憶體方面，比較傳統的代數多重網格方法以及現存的改善Krylov子系統方法，都得到了更好的結果。

As the ultra deep sub-micron technology scales down to 0.18 µm, power distribution network analysis becomes one of the most critical and challenging problems in today’s high performance chip design. Lower supply voltage on power distribution network decreases the circuit noise margin and higher circuit operation frequency increases the circuit noise from Ldi/dt voltage drop. Those effects increase the design complexity of power distribution network and also increase the demand of efficient power distribution network analysis methods. In this thesis, we present an aggregation-based algebraic multigrid method for power distribution network analysis. First, we model the original power distribution network with RLKC segments and piecewise linear current sources. Then we use modified nodal analysis to transform the problem into an Ax=b linear algebraic problem where A is a n*n matrix, x and b are n*1 vectors. By performing an aggregation algorithm, the original system matrix is divided into many small sub-matrices and an algebraic partition is performed to simplify our problem. Experimental results show our aggregation-based algebraic multigrid method runs faster and spend less memory usage than both traditional algebraic multigrid method and the existing IEKS (Improve Krylov Subspace) method.