應用於超大型積體電路之時序導向階層式分割方法

A Timing-Driven Hierarchical Partitioning Algorithm for VLSI Circuits

黃文貞(Wen-Chen Huang)

指導教授 ： 陳美麗

中原大學/工學院/資訊工程研究所/碩士(2002年)

https://doi.org/10.6840/cycu200200394

摘要

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

關鍵字

階層式分割 ； 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.

並列關鍵字

hierarchical partition ； path delay driven partition

參考文獻

[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

[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.

[1] Cong, J., Sung Kyu Lim, “Performance Driven Multiway Partitioning,” Asia and South Pacific Design Automation Conference, pp. 441-446, 2000.