平行的繞線擁擠評估器

A Parallel Routing Congestion Estimator

彭振宇(Zhen-Yu Peng)

指導教授 ： 王廷基

國立清華大學/電機資訊學院/資訊工程學系/碩士(2013年)

摘要

隨著design的縮小，可繞性變成了很大的挑戰，最近，許多placement tools採用繞線擁擠評估器（RCEs）來引導他們的演算法，且designer可以採用RCEs來判決他們的design在早期階段是否可繞，因此，業界需要一個快速且準確的RCE來減少設計成本與加速time-to-market時間，通常來說，RCEs可被分為兩種，一種是probability-based另一種是global-router-based（GR-based），因為GR-based RCE在擁擠評估上比probability-based RCEs來的準確，整合GR-based RCEs到placers變成了一種趨勢，儘管如此，GR-based RCEs比probability-based RCEs慢，當GR-based RCEs不斷地被placers重復使用，這變成了一個關鍵的影響。

　　為了加速GR-based RCEs，這篇論文提出了一個resource-based parallel strategy（RPS）把全域繞線問題分解成許多獨立的子問題，且這些子問題可以被同時使用threads來解決，RPS的概念為首先將繞線圖複製成多個繞線圖，接下來從原本的繞線圖分派繞線資源以及nets給每一個複製出來的繞線圖，之後，在這些複製圖的繞線問題就可被同時的解決。最後，在複製圖中的繞線結果將會被合併為一個最終的繞線結果，跟傳統的region-based parallel strategy比較，RPS可以較佳的處理那些bounding box有重疊的net和net跨越許多區域的情況，但是，怎麼分派繞線資源和nets給每一個複製圖是一個具挑戰的問題，如果nets和繞線資源沒有被正確的分派，繞線結果的品質將會退化且threads之間將會不平衡。這篇論文呈現資源的分配，net的分派，和routing effort balancing來使每一個threads的routing effort平坦，實驗結果顯示出現有的GR-based RCE搭配提出的RPS可以在使用四個threads的情況下達到三點四倍的加速。

關鍵字

平行 ； 繞線擁擠評估器 ； 繞線擁擠評估器

並列摘要

Routability has become very challenging with designs scaling down. Recently, many placement tools adopt routing congestion estimators (RCEs) to guide their algorithms, and designers can adopt RCEs to judge whether their designs are routable in the early design stage. Thus, industry desires a fast and accurate RCE to reduce the design cost and speed up time-to-market. Typically, RCEs can be categorized into two types, the probability-based and the global-routing-based (GR-based) methods. Because GR-based RCEs are more accurate than probability-based RCEs in congestion estimation, integrating GR-based RCEs into placers has become a trend. However, GR-based RCEs are much slower than probability-based RCEs, that becomes a critical issue when GR-based RCEs are iteratively launched by placers.

To accelerate GR-based RCEs, this thesis presents a resource-based parallel strategy (RPS) to partition a global routing problem into several independent sub-problems, and these sub-problems can be concurrently solved by multiple threads. The concept of RPS is to first duplicate the routing graph to several copies, and dispatches the routing resource and nets from the original routing graph to each duplicated graph. After that, the routing problem in each duplicated graph can be solved concurrently. Finally, the routing results in duplicated graphs are merged together to form a final routing result in the original graph. Compared to the traditional region-based parallel strategy, RPS can better handle the situations when many nets have bounding boxes overlapping with each other and a net crosses multiple regions. However, how to dispatch routing resource and nets to each duplicated graph is a challenging problem. If the nets and routing resource are not dispatched properly, the quality of routing results degrades and the computation effort of each thread may be unbalanced. This thesis presents resource allocation, net dispatching, and routing effort balancing methods to even the routing effort of each thread. Experimental results reveal that an existing GR-based RCE with the proposed RPS can averagely achieve 3.4X speedup with four threads.

並列關鍵字

Parallel ； Routing Congestion Estimator ； RCE

參考文獻

[5] J. L. S. Thakur, S. Krishnamoorthy, and H. S. Sheng, “Estimating routing congestion using probabilistic analysis,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 21(1), pp. 32-48, 2002.

[7] W.-H. Liu, Y.-L Li, and C.-K. Koh, “A fast maze-free routing congestion estimator with hybrid unilateral monotonic routing,” in Proceedings of International Conference on Computer-Aided Design, pp. 713-719, 2012.

[9] H. Shojaei, A. Davoodi, and J. T. Linderoth, “Congestion analysis for global routing via integer programming,” in Proceedings of International Conference on Computer-Aided Design, pp. 256-262, 2011.

[14] W.-H. Liu, W.-C. Kao, Y.-L. Li, and K.-Y. Chao, “NCTU-GR 2.0: Multithreaded collision-aware global routing with bounded-length maze routing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32(5), pp. 709-722, 2013.

[17] ISPD 2011 Routability-driven Placement Contest and Benchmark Suite. Available: http://www.ispd.cc/contests/11/ispd2011_contest.html