https://scholars.lib.ntu.edu.tw/handle/123456789/147745
標題: | Simultaneous Routing, Buffering, and Power Planning in Floorplan Design | 作者: | Fang, Jyh-Perng | 關鍵字: | 電源規劃;平面規劃;繞線;緩衝器置入;Power Planning;Routing;Buffering;Floorplan | 公開日期: | 2004 | 摘要: | 線評估及電源遞送這兩個問題在大多數情況下彼此獨立,但在某些情況下卻彼此相關,因此,我們針對不同的情況提出不同的對策。 對於電源遞送的評估,我們提出SE演算法來迅速評估電源輸入線的壓降。和現有的技術相比,SE演算法的優點是其資料結構單純,因此評估速度非常快。 就接線的問題而言,我們針對常見的繞線及緩衝器置入進行處理,所提出的包括MR演算法及MBR演算法,前者負責曼哈頓式繞線及緩衝器置入的評估,後者負責迂迴式繞線及緩衝器置入的評估。這兩者都採用現有的IFR技術來計算緩衝器的置入位置。 基於提昇速度及精確度的考量,MR及MBR演算法更分別被升級成FMR及DR演算法,計算緩衝器置入位置的方法也由IFR技術改成速度更快的BSA技術。 而且我們還進一步將習用的緩衝器位置計算方法BSA改進成EBSA。和BSA相較,EBSA對於獨佔性匯流排的緩衝器擁擠程度的評估較正確。 對於低成本的設計或接線層受限的設計而言,電源線和訊號線常不得不置於同一層。因此,若能將接線評估及電源遞送評估整合在一起,將能使評估結果更精確。我們將評估接線、評估電源遞送的諸演算法整合成一個完整的程序。在這個程序中,電源規劃的評估結果可以視需要饋入繞線演算法中。為了讓壓降及瞬間電流雜訊的評估結果可以饋入接線評估的演算法中,並新增瞬間電流雜訊的評估能力,我們將SE演算法更新成OSE演算法。為了評估電源線的繞線擁擠程度,我們也提出PMR演算法。另外,還提出FPSMR演算法,它別經由PMR演算法及FMR演算法評估電源線及訊號線的繞線擁擠程度,並加以整合。我們還將整合的程序嵌入疊代式平面規劃演算法中,使得繞線擁擠、緩衝器擁擠、壓降、及瞬間電流雜訊等影響實體設計訊號完整性的因素可以在平面規劃的階段先期評估,從而得出具有較佳面積/總線長且滿足繞線擁擠、緩衝器擁擠、壓降、及瞬間電流雜訊等限制條件的平面圖。 本論文所提出的諸演算法及計算程序均基於輕便靈敏的閘格結構,由於這種結構的計算速度夠快,因此相關評估的演算法可以順利整合至平面規劃器,而且不會使平面規劃器的整體速度明顯變慢。將繞線擁擠、緩衝器擁擠、壓降、及瞬間電流雜訊的評估整合至平面規劃器中可以先期過濾可能會在設計流程後段失敗的設計,從而早期達到設計收歛(design closure)的目標。 With the advances of VLSI technology, deep-sub-micron (DSM) fabrication process becomes more and more popular. In a DSM design, the congestion dominated by interconnections has become an important design issue. Some other previously overlooked effects, such as IR-drop and ground-bounce are also becoming the first-order design parameters to consider. Both the interconnection and power delivery effects are difficult to predict precisely during early design stage. Therefore, the VLSI physical design flow for DSM fabrication technology is typically performed in an iterative and incremental style. This research attempts to decrease the design iterations in such an iterative design flow by excluding the factors that are inclined to cause design failure. We propose two main problem-solving mechanisms at the foorplanning stage: interconnection evaluation and power delivery evaluation. The former takes congestion into account, the latter focuses on IR-drop and ground bounce. These two problems are independent for most design cases, but are related for some design cases. Therefore, different strategies have to be proposed for different conditions. For the problem of power delivery evaluation, a Successive Elimination (SE) power planning algorithm is proposed to evaluate IR-drop’s of power inputs. In comparison to the existing approaches, SE algorithm features simple data structure and thus a significantly efficient evaluation speed. For the problem of interconnection evaluation, we proposed a Manhattan Routing (MR) algorithm and a Maze-based between-buffer Routing (MBR) algorithm, which apply the existing Independent Feasible Region (IFR) technique to decide buffer locations and are responsible for the simultaneous routing and buffering, respectively in a Manhattan-type and a detour-type of interconnections. The MR and MBR algorithms are then respectively revised as a Fast Manhattan Routing (FMR) algorithm and a Detour Routing (DR) algorithm. The FMR and DR algorithms adopt the technique of Buffer Sit Approach (BSA) instead of IFR to decide buffer locations. In comparison to the MR and MBR algorithms, the FMR and DR algorithms feature a more efficient congestion evaluation. Moreover, as we have observed that BSA may insert buffers to congested regions on a dominant bus, an extended version of BSA, enhanced buffer site approach (EBSA), is proposed, which can evenly insert buffers to a dominant bus. For a low cost design or a design with limited layers, where power lines and signal nets are inevitably put on the same layer(s), the integration of interconnection evaluation and IR-drop/ground-bounce evaluation facilitates a more precise prediction Thus, a procedure is proposed to integrate power delivery planning, routing, and buffering in an iterative floorplanner such that IR-drop, ground-bounce and different kinds of congestions in a design can be simultaneously evaluated. To support more precise evaluation and to facilitate the interactions between power delivery planning and congestion evaluation, the SE algorithm is further enhanced as an Ordered Successive Elimination (OSE) algorithm to handle ground bounce additionally and to generate information of power lines. Also, a Fast Power line and Signal net Manhattan Routing (FPSMR) algorithm is included in our procedure to perform congestion evaluation of power lines and signal nets. The FPSMR algorithm is analogous to the FMR algorithm. The only difference is that, before operating as the FMR algorithm doing to evaluate congestion, the FPSMR algorithm has to invoke a Power line Manhattan Routing (PMR) algorithm to route power lines generated by the OSE algorithm. Sharing an agile grid data structure, the algorithms and procedures presented in this Dissertation feature consuming less memory as well as providing a quick and effective evaluation. An effective evaluation facilitates filtering out designs with worse routability or inferior performance. Besides, as these evaluations are performed at an earlier design stage, the design iteration is thus effectively decreased. Since the evaluation speed of these algorithms and procedures is very fast, the operation speed of an iterative floorplanner integrating the proposed procedures can be much improved. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/53073 | 其他識別: | en-US |
顯示於: | 電機工程學系 |
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
ntu-93-D88921026-1.pdf | 23.31 kB | Adobe PDF | 檢視/開啟 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。