用於擺置繞線流程的可繞度和效能最佳化技術

Abstract

近年來，隨著奈米技術的進步，晶片中的元件越來越多，同時繞線的難度也越來越高。晶片的可繞性(Routability)成為眾人所觀注的議題。在該議題上，全域繞線(Global Routing)扮演著重要的角色。在電路實體設計(Physical Design)的流程中，全域繞線上承元件擺放(Placement)，下啟細部繞線(Detailed Routing)。一個快速的全域繞線器能提供擁擠度(Congestion)的資訊給擺放器，讓擺放器擺出較容易繞線的布局。此外，若全域繞線器能有效的解決繞線擁擠度的問題，細部繞線的負擔和所需時間可以大幅降低。當全域繞線器和擺放器合作時，全域繞線器如何快速且準確的回報擁擠度資訊給擺放器是一個重要的議題。另一方面，當全域繞線器扮演細部繞線器的指導者角色時，全域繞線結果的品質就顯的格外重要。若細部繞線器能根據一個高品質的全域繞線結果進行細部繞線，將會提升細部繞線結果的品質，並大縮短細部繞線的時間。這篇論文提出了兩個全域繞線器: Grace是個快速的全域繞線器，適合擔任擁擠度預估器; NCTU-GR 2.0能產生高品質的繞線結果來指導細部繞線，其繞線結果較不擁擠且有較短的線長。此外，為了將Grace應用於業界，我們增加了許多功能於Grace中來滿足業界的需求。在擺放和繞線的中間階段，我們結合了擺放器和全域繞線器，提出了一個可繞性優化器(Routability Optimizer)。若給予一個布局結果，該優化器可以重新擺放其中的元件，讓該布局更容易被繞線，進而得到更好的繞線結果。最終，在進行細部繞線前，我們還提出了一個三維繞線改善器，將全域繞線的結果在做進一步的改善，此舉可以更進一步的降低細部繞線器的時間和負擔。

Routability has become one of most critical issues to successfully achieve design closure. To address this issue, global routing plays an important role in the placement and routing flow. During the placement stage, a fast global router can serve as a routing congestion estimator to guide that placers improve the routability of placement solutions; however, traditional global routers are too slow to offer quick but accurate congestion estimation. In the routing stage, the duty of a global router is to identify a global routing result to guide downstream detailed routers. The runtime of the detailed router can significantly reduce if the global routing result has well optimized congestion and wirelength. In this dissertation, two global routing engines are proposed, Grace and NCTU-GR 2.0. Grace is a fast global router to serve as a fast routing congestion estimator, adopts the proposed unilateral monotonic routing and hybrid unilateral monotonic routing to replace time-consuming maze routing in its routing flow, and invokes a congestion-aware bounding box expansion scheme to avoid over-expanding the searching regions to achieve high speedup. Moreover, in order to use Grace in the industrial flow, Grace have been enhanced to tackle the layer directive and scenic constraints for considering the timing issue. Another proposed global router NCTU-GR 2.0 can generate high-quality global routing results to guide the downstream detailed router. The proposed bounded-length maze routing avoids producing redundant detours to save routing resource; rectilinear Steiner minimum tree aware routing scheme can guide NCTU-GR 2.0 to build a routing tree for each multi-pin net with shorter wirelength; a dynamically adjusted history cost function highlights for NCTU-GR 2.0 which grid edges are critical routing resource that can be more carefully allocated to the nets that really desire. Based on the proposed innovations to carefully utilize routing resource, NCTU-GR 2.0 obtains shorter total wirelength and lower congestion than the other state-of-the-art academic global routers. In addition, between the placement and routing stages, this dissertation presents an incremental place-and-route tool called Ropt to optimize the routability of a given placement solution. Rather than minimizing HPWL, Ropt directly improves routability by minimizing the routing cost of nets, as the routing cost is defined in terms of global congestion, local congestion and wirelength. In addition to using NCTU-GR 2.0 to evaluate the routability of the placement solutions, this work also uses Wroute to obtain detailed routing results of the optimized placement solutions for the evaluation of real routability. Finally, the proposed post-3D-global-router called Post3DGR further refines the wirelength, congestion, and via count of a given 3D global routing result. Post3DGR consists of the 3D post routing stage and negotiation-based layer assignment stage. The 3D post routing stage adopts an inherited history cost function to guide the routing, which can greedily reduce total wirelength and vias. The negotiation-based layer assignment stage re-assigns the routing layer for each wire to reduce via count. The negotiation-based layer assignment can be extended to consider via overflow and antenna effect. Considering these issues before detailed routing can ease the effort and runtime of subsequent detailed routing.