[發明專利]一種用于求解給定邊框約束的VLSI版圖設計方法

在審

• 申請號: 201710207178.7
• 申請日: 2017-03-31
• 公開（公告）號: CN106777849A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 陳建利;劉巖;朱自然;朱文興
• 申請（專利權）人: 福州大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 福州元創專利商標代理有限公司35100
• 代理人: 蔡學俊

1.一種用于求解給定邊框約束的VLSI版圖設計方法，其特征在于，按照如下步驟實現：

步驟S1：將版圖規劃表示為B*-tree；

步驟S2：初始化所述步驟S1獲取的B*-tree為完全二叉樹，記為初始解I；

步驟S3：設置算法迭代次數iterative＝0，設置最大的迭代數目；

步驟S4：判斷所述初始解I是否為可行解；

步驟S5：通過一系列B*-tree擾動產生鄰居解；

步驟S6：對所述步驟S5中的鄰居解采用可行解策略，使得鄰居解滿足邊框約束；

步驟S7：采用混合模擬退火算法在解空間中搜索最優解；

步驟S8：令iterative＝iterative+1；

步驟S9：重復所述步驟S5至所述步驟S8，直到迭代次數iterative大于預設的迭代數目。

2.根據權利要求1所述的一種用于求解給定邊框約束的VLSI版圖設計方法，其特征在于，在所述步驟S1中將版圖規劃表示為B*-tree，其中，樹形結構中的每個節點都代表一個模塊，而且每個節點至多有兩個子節點。

3.根據權利要求1所述的一種用于求解給定邊框約束的VLSI版圖設計方法，其特征在于，在所述步驟S2中，所述初始化所述步驟S1獲取的B*-tree為完全二叉樹包括：除了樹結構中的最后兩行的節點，每個父節點有兩個子節點。

4.根據權利要求1所述的一種用于求解給定邊框約束的VLSI版圖設計方法，其特征在于，在所述步驟S5中，對于解空間中每個解都由B*-tree表示，且所述一系列B*-tree的擾動方式包括：模塊旋轉、移動模塊到另一個區域以及交換兩個模塊。

5.根據權利要求1所述的一種用于求解給定邊框約束的VLSI版圖設計方法，其特征在于，在所述步驟S6中，通過可行解策略算法使所述所述步驟S5中獲取的鄰居解為可行解，且所述可行解策略算法采用如下步驟實現：

步驟S61：令j＝＝0；

步驟S62：while(初始解S是不可行的orj≤給定的數值)；

步驟S63：令j++；

步驟S64：通過一系列B*-tree的擾動產生新的解S₁；。

其中，j表示可行解策略在實行過程中的迭代次數。

6.根據權利要求1所述的一種用于求解給定邊框約束的VLSI版圖設計方法，其特征在于，在所述步驟S7中，還包括如下步驟：

步驟S71：通過B*-tree擾動產生新的解I'，并將對應的B*-tree記為J；

步驟S72：基于新的罰函數計算新解I'的費用值，并計算新的解和上一步解的費用差；

步驟S73：判斷是否接受J；

步驟S74：通過一新的溫度改變公式搜索最優解。