針對當代電路設計之擺置最佳化

Abstract

擺置是實體設計中最重要的步驟之一，並且已經被研究了數十年。雖然擺置是傳統的設計自動化問題，當代電路設計的挑戰（包括可繞度、高效能、低功耗）已經大幅改變了擺置問題。因此，在擺置的過程中，通常需要考慮各種不同的目標以及限制。例如可繞度：隨著元件尺寸持續縮小，各式各樣的設計規範需要在細部繞線階段考慮。幸運的是，其中一些規範能於擺置階段簡潔地寫成限制式，滿足此種限制能大幅度得提高細部繞線的可繞度。除了考慮可繞度而產生的限制外，考慮各元件特性而衍生之區域限制也對現今電路擺置技術產生新的議題。為提升效能，擺置技術為現今奈米積體電路設計之時脈週期瓶頸，如何有效率地達成時序收斂也為擺置技術的最關鍵挑戰。另一方面，為因應現今於高性能處理器中極速高升的運算複雜度，如何有效萃取資料路徑並於電路擺置階段考慮資料路徑為當代實體設計師需要面對的課題。為了有效取捨電路之高效能與低功耗，閂鎖器叢集及擺置也高性能處理器之關鍵技術，特別針對千兆赫茲電路，降低閂鎖器於擺置階段對於時序之影響將直接決定晶片之效能，並且，閂鎖器叢集的個數也直接決定時鐘門控的能力，進而影響晶片之功耗。因此，在當代高效能之電路設計中，考慮可繞度、區域限制、時序收斂、資料路徑、以及閂鎖器叢集及擺置之方法將愈來愈為重要。 這份論文中，我們針對上述當代高效能電路設計中所面臨之關鍵課題提出了數個全新的擺置演算法。這份論文首先介紹一考慮可繞度與區域限制之解析擺置器，不同於先前的研究大多利用剩餘空間的分配或是擴大元件尺寸來減少繞線擁擠區域，我們提出一加權線長模型來減少擺置階段之繞線擁擠區域面積並同時降低總繞線長度。接著，我們提出一以時序為導向之擺置演算法，相較於過去傳統的時序最佳化擺置方法主要考量訊號延宕之問題，我們提出一系列處理訊號速決之演算法框架，並進一步探討如何於此框架下不加遽訊號延宕情形。針對資料路徑最佳化，我們首先拓展傳統位元切割對於資料路徑萃取之定義，並依此定義提出了於二分圖上之邊覆蓋演算法來萃取更多有利於擺置之資料路徑，我們亦提出一考量資料路徑之解析擺置器以驗證萃取之資料路徑有效性。最後，針對閂鎖器擺置最佳化，我們採用一混和整數線性規劃有效解決閂鎖器叢集及擺置問題以期降低其於擺置階段對於時序之影響以及減少閂鎖器叢集的個數並達成低功耗。

Placement is a classical problem in physical design that has been studied for several decades. In recent years, however, modern design considerations (including performance, routability, and power) have reshaped the placement problem comprehensively. In this dissertation, we focus on addressing these considerations in respect to resolving the following critical challenges during placement: (1) datapath, (2) technology and fence-region constraints, (3) timing closure, and (4) latch clustering. To improve circuit performance, datapath-aware placement for physical regularity has shown great promise in recent work. However, the lack of widespread industrial adoption indicates this research topic is still unsolved, mainly because existing datapath extraction techniques cannot provide general physical alignment constraints to the following datapath-aware placement. Therefore, it is critical to develop a unified framework for datapath extraction and placement to improve circuit performance. To improve routability, as technology nodes continuously shrink to $10nm$ and below, various complex design rules should be satisfied in detailed routing (after placement). Fortunately, some of these rules can be formulated as technology constraints in placement. Therefore, considering technology constraints in placement could optimize routability in detailed routing. In addition to technology constraints for routability, fence regions also impose constraints in placement for better performance. For example, chip designers may specify a fence region for placing certain cells to improve circuit performance. Violating these fence-region constraints could result in inferior performance. On the other hand, minimizing the interconnection delay during placement is another way to improve circuit performance, mainly because the delay caused by thinner and more resistive wires has become a major bottleneck for timing closure in the physical design flow. Finally, to achieve better power and performance trade-off, latch clustering and placement play important roles in physical design, as the number of latch clusters determines the effectiveness for clock gating (i.e., dynamic power saving) and the placement determines the timing disruption for the clustering process. Therefore, it is important to develop placement optimization techniques for the aforementioned critical challenges in modern circuit designs. In this dissertation, we develop a new physical synthesis framework, especially focusing on the placement stage, to resolve the critical challenges of modern circuit designs. (1) We first start with a state-of-the-art analytical placement engine. With this placement engine, we propose a bit slicing datapath extraction algorithm, which provides alignment guidance to the engine to achieve better routed wirelength, and thus better performance. In this extraction algorithm, we first extend the definition of a traditional bit slicing problem. According to the extended definition, we propose a balanced bipartite edge-cover algorithm to effectively extract placement-friendly datapath bit slices for better performance. (2) To improve routability and further optimize performance, we simultaneously integrate a novel weighted wirelength model and the fence-region consideration into the placement engine. (3) To further achieve timing closure, we present a series of timing-driven placement algorithms after the analytical placement engine, where the presented algorithms mainly target on moving sequential logics (e.g., flip-flops and latches) to eliminate timing violations. (4) Lastly, for latch clustering and placement, we present two mixed integer linear programming models to simultaneously minimize the number of clusters and the disturbance of latch locations, and thus achieve better power and performance trade-off. Experimental results show the effectiveness and efficiency of our proposed algorithms.