基於分割法產生適用於可繞度 導向之解析擺置器的初始佈局

Partition-Based Initial Placement for Routability-Driven Analytical Placer

李培瑜(Pei-Yu Lee)

指導教授 ： 劉建男

國立中央大學/資訊電機學院/電機工程學系/碩士(2014年)

摘要

隨著科技不斷進步，積體電路的設計複雜度愈來愈高，實體設計面臨的問題愈來愈多。擺置階段是電子設計自動化軟體中極重要的一環，需要能經由考量多目標來決定標準元件的實際位置，而擺置階段最重要的就是全域擺置，因為全域擺置的結果深深地影響整個擺置階段的效果。
現今許多的擺置器將重點放在可繞度的預估上，因為在擺置的下一階段即是繞線。而用以前線長最佳化的考量會造成繞線階段的困難，小則浪費時間，大則根本無法成功完成繞線，因此在擺置階段預先考量此擺置是否能比較容易地被繞線完成是一門很重要的課題。目前的解析式擺置器（analytical placer）會先以線長為考量產生初始擺置，經過對於線長以及密度的優化後再作對可繞度做優化。為了得到易於繞線的擺置，一個能以可繞度為考量並且能夠增加解析式擺置器對於可繞度優化的初始擺置亟需被提出並應用於解析式擺置器上。
本篇論文提出了一個改善傳統分割法的擴展式分割法，藉由上到下擴展式分割法配合擴展順序決定產生一個對於可繞度優化的初始擺置。實驗數據顯示以擴展式分割法所產生的可繞度導向初始擺置能夠有效地提升解析式擺置器的可繞度。

關鍵字

超大型積體電路 ； 分割法擺置 ； 可繞度導向擺置 ； 初始擺置

並列摘要

As technology advances, the complexity of integrated circuits has increased rapidly. Placement, an important stage in physical design, requires more effective algorithms to handle multiple objectives, such as timing, power, routability, and wirelength.
Recently, placers focus on improving routability due to a wirelength-driven placer may cause high routing congestion or produce an unroutable placement. Therefore, how to optimize routability during placement stage is an important issue. State-of-the-art analytical placers guide their placement by a wirelength-driven initial placement, followed by optimizing the objective function which consists of wirelength, density and routability. At last, an optimization that only concerns routability is applied. To get a more routable placement, a routability-driven initial placement that benefits analytical placer’s routability is urgently needed.
In this thesis, we propose a new partition method which improves traditional partition method to produce a better initial placement for analytical placers by using a top-down recursive expansion partition. Experimental results show that using the proposed algorithm will effectively improve the routability of analytical placer.

並列關鍵字

VLSI ； Partition-based Placement ； Routability-driven Placement ； Initial Placement

參考文獻

[1] Jarrod A. Roy, David A. Papa, Saurabh N. Adya, Haward, H. Chan, Aaron N. Ng, James F. Lu, and Igor L. Markov, “Capo： Robust and scalable open-source min-cut floorplacer,” in Proceedings of International Symposium on Physical Design, pp. 224–226, 2005.

[2] Taraneh Taghavi, Xiaojian Yang, Bo-Kyung Choi, Maogang Wang and Majid Sarrafzadeh, “Dragon2005： Large Scale Mixed-Sized Placement Tool,” in Proceedings of International Symposium on Physical Design, pp. 42-47, 2005.

[3] Meng-Kai Hsu, Yi-Fang Chen, Chau-Chin Huang, Tung-Chieh Chen, and Yao-Wen Chang, “Routability-Driven Placement for Hierarchical Mixed-Size Circuit Designs,” in Proceedings of Design Automation Conference, pp. 1-6, 2013.

[5] Myung-Chul Kim, Jin Hu, Dong-Jin Lee, and Igor L. Markov, “A SimPLR Method for Routability-driven Placement,” in Proceedings of International Conference on Computer-Aided Design, pp. 67-73, 2011.

[6] Yu-Min Lee, Tsung-You Wu, and Po-Yi Chiang, “A Hierarchical Bin-Based Legalizer for Standard-Cell Designs with Minimal Disturbance,” in Proceedings of Asia and South Pacific Design Automation Conference, pp. 568-573, 2010.