[發明專利]一種VLSI布局規劃中集中約束的實現方法

無效

• 申請號: 200710047704.4
• 申請日: 2007-11-01
• 公開（公告）號: CN101339571A
• 公開（公告）日: 2009-01-07
• 發明（設計）人: 王琳凱;陳珊珊;周電;周曉方
• 申請（專利權）人: 復旦大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 上海正旦專利代理有限公司
• 代理人: 陸飛;盛志范

1.一種VLSI布局規劃中集中約束的實現方法，其特征在于具體步驟如下：

(1)根據集中約束的要求構造允許的初始布局：首先將各個約束涉及的模塊連接為子樹，不涉及約束的模塊單獨劃分為子樹，然后將各個子樹連接構成整體B*-tree；

(2)采用模擬退火算法對全局因素進行優化：

模擬退火中基本操作為旋轉、交換、刪除和插入，操作方法為：

①旋轉操作：交換某個模塊的長寬；

②當交換，刪除，插入基本操作全部是在針對同一個子樹的內部節點操作時，即交換兩節點或刪除節點和插入節點都在同一子樹進行時，該類操作只針對節點進行；

③當操作涉及兩節點不在同一子樹內時，則需要根據下面的判斷完成相關操作：<1>針對交換操作：當其中一個節點為葉節點且另外一個節點對應子樹的根節點之父節點與葉節點在同一子樹中，交換其中對應葉節點和另一個節點對應整體子樹；否則交換兩節點對應子樹的位置；<2>針對刪除插入操作：刪除對應子樹，同時連接其他子樹保持樹的完整性，在插入子樹中選擇位置放置插入；

優化過程中各模塊長寬比不進行調整，全部當作硬模塊處理，其中模擬退火的溫度、迭代次數控制參數根據對求解時間和求解質量的要求進行調整；當搜索不再收斂或已經達到終止溫度時停止進一步搜索，取搜索中最優布局結果作為本步輸出；

(3)根據(2)步得到初始布局歸納出線性規劃的約束條件；

其中優化目標是在不改變原來相對位置條件下總面積最小，目標函數為：

Minimize…f＝λ₁·h_c+λ₂·w_c，

其中λ₁，λ₂分別是模擬退火布局結果長寬比例，h_c，w_c為布局的長度和寬度；

線性規劃的變量是所有模塊的位置x_i，y_i和長寬h_i，w_i及總體布局的長寬h_c，w_c；

所述歸納出的線性規劃約束條件有四種：<1>模塊自身長寬比的范圍λ_min＜h_i/w_i＜λ_max；<2>模塊之間的位置約束：x_i+w_i＜＝x_j和y_i+h_i＜＝y_j；<3>布局范圍約束：x_i+w_i＜＝w_c和y_i+h_i＜＝h_c；<4>參數范圍約束：x_i，y_i?w_i，h_i，w_c，h_c＞＝0；

(4)得到線性規劃的目標函數和約束條件后使用數學工具Matlab庫函數對線性規劃求取最優解，得到滿足所有約束條件下面積最優時所有參數的數值：各個模塊位置x_i，y_i，長寬h_i，w_i及總體長寬h_c，w_c。