- 學位論文
具備最小干擾於標準元件下的電路快速合法化方法
FastLegalize: Legalization for Standard Cell Based Design with Minimal Disturbance
摘要
隨著製程進入奈米時代，現今的積體電路中有著數以百萬計的可移動標準元件(standard cell)與固定單元(fixed macros)。在做電路合法化時為了維持原有的全域擺置結果，在晶片上標準元件的移動量必須要最小化。因此在這一篇論文中我們提出了一個有效將電路中標準元件移動量達到最小化的方法。 為了能夠有效限制標準元件的移動量，首先將晶片切割成每一個大小都相同的格子，然後從密度最大的格子開始做合法化。由於密度太大的格子裡的空間不足給標準元件做合法化，因此必須嘗試合併周圍的格子直到它的密度小於臨界值，在這裏我們提出兩種結構以有效的去合法化電路。 合併後的格子開始透過我們有效的方法去做合法化，所提出的方法可同時維持在全域擺置結果的特性與最小化移動距離。為了能夠改進效能，在合法化的過程中每個標準元件都會隨時做擺置上的更新。直到所有的格子都做完合法化後即結束。 與最新的研究結果“Abacus”比較後，我們所提出的方法可減少平均48%的移動量，最大的移動量可減少140%，此外，執行上的速度有將近1.11倍的提升。實驗結果證明我們的方法可以獲得一個好的合法化電路。
並列摘要
An efficient legalization approach is necessary for the integrated circuit design which consists of millions of movable standard cells and fixed macros. To maintain the global placement result, the disturbance of cells must be minimized. In this work, a fast legalization placer, FastLegalize, is developed to legalize standard cells with minimal movement. First, a chip is divided into several bins with equal size to limit the movable scope of cells. Then, starting with the most crowed unlegalized bin, a merging procedure for bins is used to integrate bins into a cross-shaped bin-merged structure or a square-shaped bin-merged structure until the cell density in that bin-merged structure is less than a defined threshold. After that, an efficient legalization method which simultaneously preserves the ordering in each row and minimizes the sum of absolute movement distances is developed to legalize cells in that bin-merged structure. To improve the legalization quality, the proposed legalization method refreshes the positions of legalized cells during legalization. Finally, the above legalizing procedure is repeated until all cells are non-overlapped. Compared with the state-of-the-art method, Abacus, FastLegalize can reduce the total movement of cells to be 48% in average, and save the largest movement of cells to be 140% in average. Moreover, FastLegalize can obtain average 1.11X runtime speed up.