[發明專利]基于時鐘偏差規劃算法的數字電路工作頻率優化方法

無效

• 申請號: 201210110065.2
• 申請日: 2012-04-16
• 公開（公告）號: CN102682158A
• 公開（公告）日: 2012-09-19
• 發明（設計）人: 黃凱
• 申請（專利權）人: 東南大學
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06F17/30
• 代理公司: 南京天翼專利代理有限責任公司 32112
• 代理人: 朱戈勝

1.一種基于時鐘偏差規劃算法的數字電路工作頻率優化方法，其特征是包括步驟：1)創建路徑優化潛力查找函數；2)可預估路徑優化潛力的時鐘偏差規劃算法；3)關鍵路徑重排布；這三個步驟構成的整體優化方案，作為點工具集成到通用電子設計自動化EDA流程中；

所述步驟1)中，路徑優化潛力查找函數：記錄了特定工藝下路徑長度和路徑優化潛力之間的保守關系，本路徑優化潛力查找函數是由統計獲得；

所述步驟2)中，可預估路徑優化潛力的時鐘偏差規劃算法，是通過預支路徑優化潛力的時鐘偏差規算法優化設計的工作頻率；可預估路徑優化潛力的時鐘偏差規劃算法包括回路分解算法和時鐘偏差規劃算法；

2.1)所述回路分解算法：通過關鍵路徑查找函數查找關鍵路徑的優化潛力，并通過預支潛力將關鍵路徑轉變為非關鍵路徑，將關鍵路徑圖中的回路分解，得到的關鍵路徑圖表現為樹狀圖；

2.2)所述時鐘偏差規劃算法：讀入所述樹狀圖，通過時鐘偏差規劃算法的策略將關鍵路徑轉變為非關鍵路徑，得到關鍵路徑重排布；

所述步驟3)的關鍵路徑重排布，是讀入步驟2.2)輸出的待優化關鍵路徑，采用結構化布局方案對物理設計進行重構，加強被預支優化潛力路徑的物理約束，從而充分釋放這部分路徑的優化潛力。

2.根據權利要求1所述的基于時鐘偏差規劃算法的數字電路工作頻率優化方法，其特征是

所述步驟1)中，路徑優化潛力查找函數的創建是針對不同的工藝節點只用進行一次；對于相應的工藝節點，統計出寄存器物理位置和其間路徑優化潛力的關系，路徑優化潛力查找函數，建立了路徑物理信息和優化潛力之間的保守關系，算法可以通過路徑的物理信息得到其優化潛力的保守值；

所述步驟1)中，在電路的布局階段之后，選取某一違規的時序路徑，首先計算出它的曼哈頓距離，將它進行歸組后的重布局，再檢測這條路徑的延時；對比曼哈頓距離，記錄曼哈頓距離和歸組優化力度之間的關系；

為了統計的保守性，對于曼哈頓距離接近的多組路徑，選擇裕量改善最小的一組進行采樣統計，得到路徑優化潛力查找函數曲線，為了保守統計，函數曲線出現在采樣點下方。

3.根據權利要求2所述的基于時鐘偏差規劃算法的數字電路工作頻率優化方法，其特征是所述步驟2)中，可預估路徑優化潛力的時鐘偏差規劃算法步驟包括：

a)輸入記錄關鍵路徑信息的矩陣即關鍵矩陣和寄存器物理的位置信息；

b)對關鍵矩陣進行矩陣簡化、離散化；

c)以當前優化目標為閥值，將步驟b)得到的離散化的關鍵矩陣轉變為鄰接矩陣；

d)在步驟c)的基礎上進行回路分解：

通過潛力查找函數查得關鍵回路中路徑的優化潛力；通過回路分解算法將關鍵回路分解；回路分解之后電路中的關鍵路徑呈樹狀結構，不存在關鍵回路；對于樹狀結構的關鍵路徑，在時鐘偏差規劃算法中借用前后級的裕量將其轉變成非關鍵路徑，輸出寄存器時鐘延時和待優化關鍵路徑。

4.根據權利要求1所述的基于時鐘偏差規劃算法的數字電路工作頻率優化方法，其特征是所述步驟3)中，關鍵路徑重排布的操作對象是從時鐘偏差規劃算法生成的待優化關鍵路徑；首先從這些路徑提取出寄存器對，把寄存器按照出現次數排列，出現次數最多的寄存器定義為基準寄存器；在重排布時，基準寄存器位置不變；待重排寄存器是指和基準寄存器存在路徑關系的寄存器集合。

5.根據權利要求4所述的基于時鐘偏差規劃算法的數字電路工作頻率優化方法，其特征是對寄存器重排布遵守以下法則：

根據關鍵程度的不同決定待重排寄存器與基準寄存器之間的距離，具體是，將待重排寄存器按照與基準寄存器關鍵程度的不同分為若干等級；把基準寄存器四周的等曼哈頓距離環即等距環也分為若干層，設層與層之間的曼哈頓距離，等距環的形狀為菱形；每一層等距環對應關鍵程度相近的一部分待重排寄存器；越關鍵的路徑，對應的等距環和基準寄存器之間的曼哈頓距離也越?。蝗绻粋€待重排寄存器之前已經被規劃到某個等距環中，那么對應新的基準寄存器重排列時，不能超出原來等距環的范圍；若不能超出原來等距環的范圍，則取兩個等距環的中心連線中點。