臺灣博碩士論文加值系統

本論文提出一應用於超大型積體電路之時序導向階層式電路分割演算法(timing-driven hierarchical partition algorithm, HPA)。本HPA演算法在維持電路的邏輯架構下，將電路分割為數個分割區塊。而本演算法的成本函數是由經過模組的切線數(net-cut)、路徑的權重(path-weight)和模組的面積(area)所組成。HPA演算法使用exhaustive search的方式，針對每一個不同的K值，尋找一個具有最小成本的分割結果。我們亦加入一模組面積的限制，此限制不僅降低候選模組(candidate module)的數目，加快程式的執行，並有助於本演算法獲得一平衡的分割結果。我們應用此程式於數個工業上的電路，實驗結果顯示，與已展開的電路(flattened circuit)比較之下，應用本程式所獲得的分割區塊具有較快critical path delay。這些分割區塊亦可在短時間內實作完成。

A timing-driven hierarchical partitioning algorithm (HPA) for VLSI circuits is proposed. The HPA partitions a circuit to several partition blocks while maintaining the hierarchy of the circuit. It uses a cost function which combines net-cut, path-weight, and area of each module. It prevents the critical paths crossing through partition block boundaries. An exhaustive search approach is utilized to find the minimal cost for different number of partitions. An area constraint of module is added to the HPA. It helps the HPA to obtain area balanced partition results in shorter CPU time. The program has been tested on several industrial circuits. Comparing to the flattened circuits, it has the result of a shorter circuit path delay with balanced size of partition blocks. These blocks may also be implemented in a shorter time. Experimental results are presented.

中文摘要…………………………………………………………………………I
英文摘要 ( Abstract )……………………………………………………………II
誌謝………………………………………………………………………………III
內容……………………………………………………………………………..IV
中文目錄…………………………………………………………………..……V
英文目錄 ( Table of Contents ).………………………….…………………….VI
中文論文簡介…………………..……………………………………………….VII
英文論文……………………………………………………………………..1-29
英文摘要( Abstract )………………………………..........……..………………...II
1.Introduction……………….…………………………………………………...1
2.The Partitioning Problem……………….………...……………………….…..3
2.1 Input Specification..………….….…………………………………….…..3
2.2 Problem Formulation……………………………………………….………6
2.3 Constraints…………………………………………………………….……7
2.4 The Objective……………………………………………………………..10
2.5 Output Specification..……………………………………………………12
3.The Objective Functions……………………………………………………..13
3.1 Net-cut Model…………………………………………………………….13
3.2 Path-weight Model………………………………………..…………..…13
3.3 Area Model…………………………………….…………………….…..14
4.The Hierarchical Partitioning Algorithm (HPA)…………………………....16
4.1 Program Flow……………………………………………………………..16
4.2 The Hierarchical Partitioning Algorithm (HPA)…………………….…..18
4.3 An Example…………………………………………………….….……..20
5.Experiments…………………………………………………………..……….24
5.1 Experimental Setup……………………………………………..………..24
5.2 Experimental Flow…………………………………………………....…24
5.3 Experimental Results………………………………………………….…26
6.Conclusions………………………………………………………….……….28
Reference…….…………………………………….......................................….29

作者簡介…………………………………………………………………….…VIII

[1] Cong, J., Sung Kyu Lim, “Performance Driven Multiway Partitioning,” Asia and South Pacific Design Automation Conference, pp. 441-446, 2000.[2] Minami, J., Koide, T., Wakabayashi, S., “A circuit partitioning algorithm under path delay constraints,” IEEE Asia-Pacific Conference on Circuits and Systems, pp. 113-116, 1998. [3] Ababei, C.; Kia Bazargan, “Statistical timing driven partitioning for VLSI circuits,” Proceedings of Design Automation and Test in Europe Conference and Exhibition, pp. 1109 -1109, 2002[4] Chau-Shen Chen; Ting Ting Hwang; Liu, C.L., “Architecture driven circuit partitioning,” IEEE Transactions on Very Large Scale Integration Systems, Vol. 9 Issue:2, pp. 383-389, April 2001.[5] Wen-Jong Fang; Wu, A.C.-H., “A hierarchical functional structuring and partitioning approach for multiple-FPGA implementations,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.16 Issue:10,pp.1188-1195, Oct. 1997.[6] Wen-Jong Fang; Wu, A.C.-H., “Multi-way FPGA Partitioning By Fully Exploiting Design Hierarchy,“ Proceedings of Design Automation Conference, pp. 518 -521, 1997.