多域混合尺寸電路設計之巨集電路擺置

Multi-Domain Macro Placement for Large-Scale Mixed-Size Designs

劉彥君(Yen-Chun Liu)

指導教授 ： 郭斯彥

共同指導教授 ： 張耀文(Yao-Wen Chang)

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2018年)

https://doi.org/10.6342/NTU201800736

摘要

多域混合尺寸電路 (multi-domain mixed-size designs) 常含有數千 個巨集電路以及數千萬個標準元件，因此巨集電路擺置的問題相當具 有挑戰性。傳統演算法中為了處理單域電路，因此最大化電路中間標 準元件擺置空間，將巨集電路堆疊在混合尺寸電路周圍，若是在多域 電路中使用相同方法將會使得巨集電路和標準元件間和不同域之間的 連線拉長。
在本篇論文中，為了進一步考慮多域電路中整體域間的互動，我們 提出了一個混合表示法多域堆積樹 (MDP-tree)，結合切片樹 (slicing tree) 以及多重堆積樹 (MP-tree) 。基於二元樹的特性，多域堆積樹能 夠快速並有效地擺放巨集電路，最佳化多域間的連線關係，並為每個 域保留適當的面積擺置標準元件。
實驗結果顯示，我們所提出的方法相較於先前的研究，可以有效的 降低半週長線長 (half-perimeter wirelength) 以及整體繞線長度 (global routing wirelength) 並且得到更好的電路擺置結果。

關鍵字

實體設計 ； 電路擺置 ； 巨集電路擺置

並列摘要

The benefits of using modern system-on-chip (SoC), such as low power, low cost, fast operation, and greater design, have attracted higher attention from circuit designers. In recent years, a modern SoC may consist of several domains, tens of millions standard cells, and thousands of pre-designed macros, which is called a multi-domain design. With the increasing use of pre-designed macros in a multi-domain design, macro placement plays a more important role in the design flow.
In this thesis, we present a new hybrid representation of slicing trees and multi-packing trees, called multi-domain-packing trees (MDP-trees), for macro placement to handle large-scale multi-domain mixed-size designs. To the best of our knowledge, there is still no published work specifically tackling the multi-domain macro placement. Based on binary trees, the MDP-tree is very efficient and effective for handling macro placement with multiple domains. Previous works on macro placement can handle only single-domain designs, which do not consider the global interactions among domains. In contrast, our MDP-trees optimize the interconnections among domains and the macro positions simultaneously. The area of each domain is well reserved and the macro displacement is minimized from initial macro positions of a prototype.
Experimental results show that our approach can significantly reduce the average half-perimeter wirelength (HPWL) and the average global routing wirelength.

並列關鍵字

Physical Design ； Placement ； Macro Placement

參考文獻

[1] S. N. Adya, S. Chaturvedi, J. A. Roy, D. A. Papa, and I. L. Markov, “Unification of partitioning, placement and floorplanning,” in Proc. of ICCAD, pp. 550–557, 2004.

[2] T. F. Chan, J. Cong, J. Shinnerl, K. Sze, and M. Xie, “mPL6: Enhanced multilevel mixed-size placement,” in Proc. of ISPD, pp. 212–214, 2006.

[3] T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, “NTUplace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints,” IEEE Tran. on CAD, vol. 27, no. 7, pp. 1228–1240, July 2008.

[4] T.-C. Chen, P.-H. Yuh, Y.-W. Chang, F.-J. Huang, and D. Liu, “MP-trees: A packing-based macro placement algorithm for mixed size designs,” in Proc. of DAC, pp. 447–452, 2007.

[5] T.-C. Chen, P.-H. Yuh, Y.-W. Chang, F.-J. Huang, and T.-Y. Liu, “MP-trees: A packing-based macro placement algorithm for modern mixed-size designs,” IEEE Tran. on CAD, vol. 27, no. 9, pp. 1621–1634, September 2008.