多重排高標準元件之有效率的擺置合法化演算法

Abstract

在先進技術的電路設計中，標準元件庫（Standard Cell Library）需要擁有不同高度的元件；例如：鰭式場效電晶體（FinFET）技術中，鰭的數量將會決定元件的高度。高度較高的元件擁有較高的驅動強度（Drive Strength），然而會消耗更多面積及功率；反之，高度較低的元件雖然驅動強度較低，卻能節省一些面積及功率。因此，結合這兩種不同高度的元件將能達到嶄新的效果。同時處理高度不一的元件對佈局設計而言是一個複雜的挑戰，原因出自於元件的維度增加以及這些元件帶來更大的解空間（Solution Space）。 目前解決關於這一類問題的論文並不多，而本篇論文能解決的正好是針對不同高度的標準元件佈局，使每個元件彼此之間沒有重疊，並且不讓每個元件與其初始位置相距太遠。我們首先研究一個適用於單排高元件的合法化擺置（Leglization）方法──Abacus，想將其延伸成多重排高（Multiple-Row-Height）的合法化擺置方法。然而若只是簡單的延伸將會遇到許多問題，例如空間不夠或是產生過多未使用空間。因此，我們大幅修正Abacus合法化擺置的演算法，並透過其架構來設計多重排高的合法化擺置方法，不但可以有效率的移除每個元件之間的重疊狀況，還可以降低未使用空間，使佈局設計的空間利用更加寬裕。我們在目標函式中引進未使用空間作為成本考量，並推導出在特定限制下能得到最佳解的狀況。 實驗結果顯示：我們的成果比目前同類型最新的論文所增加的線長少50%，並能在合理的執行時間內完成。

For circuit designs in advanced technologies, standard-cell libraries consist of cells with different heights; for example, the number of fins determines the height of cells in the FinFET technology. Cells of larger heights give higher drive strengths, but consume larger areas and power. Such mixed cell heights incur new, complicated challenges for layout designs, due mainly to the heterogeneity in cell dimensions and thus their larger solution spaces. There is not much published work on layout designs with mixed-height standard cells. This paper addresses the legalization problem of mixed-height standard cells, which intends to place cells without any overlap and with minimized displacement. We first study the properties of Abacus, generally considered the best legalization method for traditional single-row-height standard cells but criticized not suitable for handling the new challenge, analyze the capability and insufficiencies of Abacus for tackling the new problem, and remedy Abacus’s insufficiencies and extend its advantages to develop an effective and efficient algorithm for the addressed problem. For example, dead spaces become a critical issue in mixed-cell-height legalization, which cannot be handled well with an Abacus variant alone. We thus derive a dead-space-aware objective function and an optimization scheme to handle this issue. Experimental results show that our algorithm can achieve the best wirelength among all published methods in reasonable running time, e.g., about 50% smaller wirelength increase than a state-of-the-art work.