- 學位論文
mSIGMA: 考慮訊號完整度及製造度之多階晶片繞線系統
mSIGMA: A Multilevel Full-Chip Routing System Considering SIGnal-integrity and MAnufacturability
摘要
由於超大型積體電路技術的快速發展，晶片設計已經到達奈米製程的時代。但在奈米晶片實體設計中，繞線(routing)所造成的問題佔整體晶片設計效能的比例卻逐漸增加且面臨到許多問題，尤其是(1)設計複雜度、(2)訊號完整度(signal-integrity)及(3)製造度(manufacturability)等三大問題急需去處理。因此，本篇論文提出了一創新的多階層繞線器(mSIGMA)來解決訊號完整度及可製造度等問題。 早期的繞線問題是使用直接兩階段繞線方式(flat routing)，也就是全域繞線(global routing)及區域繞線(detailed routing)來處理繞線問題，但此解法受限在其對於處理大量資料時的延伸性，為了解決這問題，學者們提出了階層繞線(hierarchical routing)來解決較大量的繞線問題，其使用了分而治之(divide and conquer)的方式來降低問題複雜度，但階層繞線仍受限於其無法保留各切割區塊間的全域資訊，得到更精確的結果，為了解決此問題，學者提出了多階層繞線器來解決以上架構所產生的問題。 多階層架構包含兩個主要步驟：粗糙化(coarsening)及反粗糙化(uncoarsening)。與之前多階層繞線器架構不同的地方是，我們在粗糙化及反粗糙化之間，提出了一軌道指派(track assignment)階段來加快繞線速度及實作最佳化。除了此創新的多階層架構，我們也對串音問題(crosstalk)、效能問題(performance)、天線效應問題(antenna effect)甚至最近提出的X架構(X-architecture)做了深入的研究。實驗結果證明，我們的創新架構比其他方法具有較好的彈性來處理以上的問題。跟之前發表在電子設計自動化重要會議發表的多階層繞線器相比，我們的方法在串音、效能、天線效應及總線長上，都有明顯的改善。在X架構的研究上，跟我們實作在曼哈頓架構(Manhattan architecture)的多階層繞線器相比，在總線長及效能上也都得到了不錯的成果。
並列摘要
As technology advances into nanometer territory, the paradigm shift of the routing problem is indispensable to cope with three major challenges: design complexity, signal-integrity problem, and manufacturability problem. As Moore's Law continues unencumbered into the nanometer era, chips are reaching 100 M gates in size, process geometries have shrunk to 90 nm and below, and engineers have to face compounded design complexity with every new design. These nanometer-scale designs require a new generation of physics-aware and manufacturing- aware routing. At 90 nm and below, there are so many signal-integrity issues that design teams cannot manually correct them all. Nanometer routers must prevent and correct these effects on-the-fly in order to reach timing closure. From a manufacturability standpoint, nanometer routers must explicitly support the ever increasing design complexity, and be capable of adapting to the requirements of timing, signal integrity, process antenna effect, and new interconnect architecture such as X-architecture. In this Dissertation, we propose a novel multilevel full-chip router, namely mSIGMA for SIGnal-integrity and MAnufacturability optimization. To handle the ever increasing design complexity of gigascale integration, the mSIGMA use a multilevel framework that has attracted much attention in the literature recently. The traditional multilevel framework employs a two-stage technique: coarsening followed by uncoarsening. The coarsening stage iteratively groups a set of circuit components (e.g., circuit nodes, cells, modules, routing tiles, etc.) based on a predefined cost metric until the number of components being considered is smaller than a threshold. Then, the uncoarsening stage iteratively ungroups a set of previously clustered circuit components and refines the solution by using optimization techniques. Different with the previous multilevel routing framework, we introduce an intermediate track assignment phase between coarsening and uncoarsening stages, to improve run-time and achieve optimization. To handle the signal-integrity problem, especially the crosstalk problem, we propose a fast layer/track assignment heuristic for crosstalk optimization. We first build the horizontal constraint graph (HCG) for all segments in the panel. For the crosstalk-driven layer assignment problem, we resort to a simple yet efficient heuristic by constructing a maximum spanning tree from the given HCG. Since a tree can be k colored in linear time if we have k layers, we shall first partition the vertices incident on edges with larger costs (coupling lengths) and allocates the corresponding segments to different layers. Then, our track assignment algorithm starts by finding the maximal sets of conflicting segments, and assigns these conflicting segments by the bipartite assignment graph till they are assigned in the panel. To handle the manufacturability problem, such as process antenna effect and the X-architecture, we also propose a desirable track assignment in our multilevel routing framework for manufacturability optimization. To solve the antenna effect, we propose a built-in jumper insertion approach for antenna effect avoidance. To take the advantage of the X-architecture, we also adopt our new multilevel routing framework for the X-based architecture, and the experimental results show the promise of wirelength and delay reduction.