對具最小擾動HiBinLegalizer之最佳化分析以及網格數的精化

Abstract

隨著積體電路製程的演進，最小線寬(feature size)的微小化，單一晶片上有數以百萬的標準元件(standard cell)以及智慧產權(Intellectual Property,簡稱 IP)模組或巨集模組塊(macro block)，使得超大型積體電路擺置(placement)的問題愈趨於複雜。然而一個合法的擺置必須所有元件之間沒有交疊並且所有的標準元件須對齊至列上；因此在積體電路設計中，擺置的合法化(legalization)為一個重要的環節。 此篇論文主要對已發表的合法化方法HiBinLegalizer，證明其所提出的位置解法器可得的最佳移動量，此外我們也提出數個定理改進搜尋列的尋找中位數的時間複雜度。由於HiBinLegalizer是一個階層式的方法，亦為將晶片分割成許多大小相同的單元格，並且透過每一個單元格的密度資訊，決定是否合併其他單元格一同納入合法化。對擺置合法化而言，分割晶片，除了可以增進執行速度，還可限制每一個標準元件的最大移動量以及減少列的搜索次數。然而初始的總單元格數量及單元格的長寬比會影響後續合併及最終結果的效能(移動量和執行時間)，因此本篇提出如何利用巨集模組塊的長寬比和最大合併區域內的標準單元個數，決定單元格長寬比以及決定總格數的範圍，最後合併兩者資訊找出好的分割網格尺寸，以取捨執行時間和最小移動量。

With semiconductor fabrication technology developing, millions of standard cells and macros (pre-designed blocks or intellectual property (IP)) are integrated into a single chip. Legalization procedure is part of placement design in physical design automation. For a legal placement, all elements (cells and macros) are non-overlapping and all cells must be aligns to row. In this paper, we based on a method, HiBinLegalizer, which was published in ASPDAC-2010, proposed the grid bin size refinement and proved the solver for the objective function is optimal solution. The grid bin size refinement use the aspect ratio of macros to obtain the aspect ratio of grid and use the number of cells in maximum merged-bin to determine the bin size for HiBinLegalizer. Moreover, we proposed some lemmas to improve the procedure of trial row in HiBinLegalizer, so that, the order of time complexity is O(1) as compared with the original O(n) . The experimental results demonstrate the effectiveness of our method.