整合空間預留技術與考量繞線擁擠度之緩衝器規劃

隨著製程的進步，使得晶片面積大幅的縮小，連線的延遲效應日益顯著，所以在平面規劃階段處理繞線延遲和可繞度成為重要的課題。而緩衝器置入在處理繞線延遲問題已被證明為極有效的方法，所以本論文提出一個在平面規劃階段時，提供足夠的閒置空間給緩衝器以滿足繞線最長延遲時間的需求並有效地提高可繞度。以往的研究中，大多先依繞線長度、晶片面積…等目標決定一平面規劃，再依閒置空間的分布狀況，在適當位置置入緩衝器，在發現閒置空間不足或位置不恰當時再增加閒置空間或改變閒置空間的位置。本計劃則提出一全新的觀念，先適當的預留閒置空間，以得到一符合效能要求的平面規劃，再縮小閒置空間，以得到面積、繞線長度和置入緩衝器的個數的最佳化。本論文中，使用三個階段處理緩衝器置入的問題。在第一階段中，利用全面預留空間，對所有相鄰模組之間提供至少一個緩衝器位置寬度的空間。除了可以提供足夠的空間供緩衝器置入，並且由於增加繞線路徑的選擇而有較高的彈性處理繞線擁擠度的問題。第二階段，則利用shortest path graph表示連線依緩衝器位置而取得的可選擇繞線路徑。在此階段將針對即使提供閒置空間也無法處理的繞線，以變動相關模組的方位解決此類問題。另外，我們也將利用各個路徑通過閒置空間的機率，估計是否已提供足夠空間供緩衝器置入。此階段最後依所有連線其shortest path graph對繞線區域的連線擁擠度估計值，以漸進刪除路徑的方式決定最後連線的繞線路徑及置入緩衝器區域。第三階段，我們使用bipartite graph模型表示緩衝器與置入位置的關係，以有效地選擇緩衝器的位置。並在緩衝器選擇位置的範圍內，將位在同一區域的緩衝器置入於同一水平或是同一垂直的位置上，使得能夠快速的完成面積最小化的動作。在第一個階段以全面預留提供選擇路徑彈性為目標，第二階段則以降低繞線擁擠度為目標決定繞線路徑，並估計是否已提供足夠的閒置空間。第三個階段則完成面積最小化。以此三階段處理模組間閒置空間的預留及緩衝器置入，並針對不同階段的目的解決問題，同時將原本問題的複雜度降低。我們的方法有以下優點： (1)可利用現有的預留空間提供更大的彈性選擇繞線路徑，提高可繞度。 (2)除了空間預留，還利用變更模組方位的方法提高緩衝器的置入成功率。 (3)可以保證提供足夠的空間供緩衝器置入。 (4)可以在緩衝器置入前，提早知曉閒置空間是否足夠。

關鍵字

繞線擁擠度；可繞度；平面規畫；時間延遲；閒置空間；緩衝器置入

並列摘要

For deep submicron VLSI design technology, the performance and routablilty of interconnect design has become critical. To ensure the timing closure of design, buffer insertion is an effective technique. In this project, we want to reserve enough dead space for buffer insertion to improve delay and routablilty of all critical nets. We plan three steps to handle space reservation and buffer insertion. At the first step, unlike to the previous works that insert dead space only when there’s no enough space for buffer, we will reserve dead space everywhere between each two adjacent modules. This method will not only provide enough space for buffer insertion, but also reduce wire congestion by using more paths. At the second step, we construct shortest path graph with consideration of wire congestion for selecting routing paths and buffer sites. And we change the orientations of some modules for solving the problems that some routs can’t find space to insert buffers. We also use shortest path graph of each net to forecast if there is enough space for buffer insertion at this step. At the third step, we will decide the position of each buffer and remove all dead space that isn’t occupied by any buffer for area minimization. We use bipartite graph to express the relationships between the buffers and their allowed positions for choosing the buffer’s positions efficiently. And when some buffers belong to the same area choosing their positions, we will assign these buffers to the same vertical or horizontal channels for merging dead space in a short time. At first step, we provide space for buffer insertion. At the second step, the purposes are decrease wire congestion, buffer congestion and increase the successful ate of buffer insertion. Efficiently minimize area is the purpose of the last step. We use these three steps to handle reservation and minimization of dead space between all modules. With these three steps, we can solve different problems at each step and lower the complexity of the problems. The advantages of our approach are: (1)We have more flexibility to improve routability by space reservation. (2)Besides space reservation, we change the orientations of modules to increase the successful rates of buffer insertion. (3)Our method guarantees that we can provide enough space for buffer insertion. (4)We can forecast if there is enough space for buffer insertion.

並列關鍵字

buffer insertion ； routablility ； delay ； dead space ； wire congestion ； floorplan

參考文獻

[1] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows, Prentice Hall, 1993.

[2] C.J. Alpert, J. Hu, S.S. Sapatnekar and P.G. Villarrubia, “A practical methodology for early buffer and wire resource allocation,” in Proc. ACM/IEEE Design Automation Conference, 2001

[5] Song Chen, Xianlong Hong, Sheqin Dong, Yuchun Ma, Yici Cai, Chung-Kuan Cheng, Jun Gu, “A buffer planning algorithm with congestion optimization,” ASP-DAC, 2004.

[6] Yi-Hui Cheng and Yao-Wen Chang, “Integrating buffer planning with floorplanning for simultaneous multi-objective optimization,” ASP-DAC, 2004.

[7] C.C.N. Chu and D.F. Wong, “Closed form solution to simultaneous buffer insertion/sizing and wire sizing,” in Proc. ACM International Symposium on Physical Design, pp. 192-197, 1997.

國際替代計量

整合空間預留技術與考量繞線擁擠度之緩衝器規劃

未授權

主題瀏覽