設計收斂之擺放轉置演算法

Abstract

為了達到設計收斂,晶片設計需符合時序,功率以及可繞性等條件。但 隨著製程進步,符合這些條件趨於困難。而由於晶片設計趨於複雜,晶片設 計流程中的擺放演算法已無法有效的同時處理多項最佳化目標。因此,在 晶片擺放後嵌入晶片最佳化的演算法去處理特定目標成為一個實際作法, 並且可有效地將原本複雜問題拆成多個小問題一一解決。這些嵌入在擺放 過程後的最佳化演算法可稱為擺放轉置,即根據一個擺放過後的晶片,移 動邏輯閘去達到指定目標最佳化。傳統晶片設計流程是在晶片中預留空間 以備不時之需,如後續時序網路,但預留空間這做法不能有效的地解決問 題而且在擺放階段中也無法計算該預留多少空間。因此,在晶片擺放後, 執行後擺放階段演算法針對特定目標做最佳化成為一個較為實際的作法。

在晶片擺放後執行的演算法可以統稱為擺放轉置演算法,即根據一個 給定的擺放後的晶片,調整邏輯閘的位置藉以達到特定目標的最佳化如可 繞性、時序、溫度、功率分佈等等。晶片原貌性可藉由總繞線溢流量,最大繞線溢流量,時序,關鍵時序路徑總量等參數藉以衡量,但衡量這些參 數極為耗時,將會使得擺放轉置演算法難以實現。因此,在本論文中,提 出的擺放轉置演算法都是以邏輯閘的總移動量去衡量演算法對於晶片原貌 性的改變。控制邏輯閘的移動量是可以有效被控制且可以盡可能維持原始 晶片的效能。

在這篇論文,我們提出三個擺放轉置的演算法,每一個演算法有各自 不同演算法移動邏輯閘並專注於最佳化某一目標,但都盡量能降低對原始 邏輯閘擺放的衝擊。透過將邏輯閘移動量最小化,可盡量維持原始擺放位 置的原貌。第一種演算法討論暫存器的合併與重置,透過暫存器的合併並 重新計算合併後的暫存器位置以達到低功率的效果。第二個演算法討論透 過流量演算法移動邏輯閘藉以降低晶片最高溫度,在高功率的區域利用流 量演算法重計算邏輯閘的位置藉以達到平均區域性功率的目的。第三個演 算法, 我們提出一個漸進式擺放引擎建立在高斯平滑的基礎上去修正邏輯 閘之間的相對位置,經實驗觀察,修正邏輯閘的相對位置不會增加整體半 週長,但對於可繞性有很大助益。

To achieve design closure, design constraints including timing, power or routability are becoming more challenging as design complexity increases. Due to increase in design complexity, placement along is insufficient to simultaneously optimize multiple objectives. Thus, a general approach is to reserve additional white space to make room for gate sizing, buffer insertion and reduce routing overflow. However, reserving white space is a only a general approach and difficult to address specific objective. In addition, reserving white space increases die area can only be use conservatively. Thus, deploying optimizations at post-placement stage is a practical approach to optimize specific objective while maintaining the integrity of the original placement. Post-placement optimization techniques can be referred as placement migration, which is the movement of cells based on an existing placement solution to address a specific objective such as timing, routability or heat distribution. The key criterion of placement migration is to preserve the integrity of the original placement while optimizing the target objective. The integrity of the original placement can be measured through routing overflow, timing of critical paths, number of violation paths, etc. However, measuring these criteria is time consuming. A more efficient method to maintain the integrity of the original placement is to minimize displacement of cells. Total displacement and maximum displacement of cells can be controlled during placement migration. In this dissertation, we present three different approaches to achieve placement migration, each approach is targeted on specific objective with different method to move cells but all share common criterion, which minimize perturbation of cells. Integrity of original placement is kept by minimizing total displacement of cells. The first approach discusses flip-flop merging and re-allocation for multi-bit flip-flops. The second approach discusses on heat distribution for maximum temperature reduction based on network flow approach. The third approach presents an incremental placement engine based on Gaussian smoothing which is designed to improve relative order of cells at post-placement stage.