[發明專利]一種基于PSO算法的有用偏差時序優化方法

有效

• 申請號: 202011165958.8
• 申請日: 2020-10-27
• 公開（公告）號: CN112001140B
• 公開（公告）日: 2021-03-30
• 發明（設計）人: 黃凱;李鵬;李立浧;習偉;曾祥君;尹項根;宋怡瞳;鄭丹丹
• 申請（專利權）人: 浙江大學
• 主分類號: G06F30/3315
• 分類號: G06F30/3315;G06F30/27;G06N3/00
• 代理公司: 杭州浙科專利事務所(普通合伙) 33213
• 代理人: 孫孟輝

本發明公開了一種基于PSO算法的有用偏差時序優化方法，包括：S1，選取路徑公共點并加入緩沖器；S2，將路徑公共點作為粒子，緩沖器數量作為粒子位置，將建立時間和保持時間的最差違例之和作為全局最優解，采用PSO算法得到最優緩沖器數量，包括：S21，隨機生成初始粒子位置；S22，將初始粒子位置輸入skew函數，得到個體最優解和全局最優解；S23，進入循環，將粒子位置輸入skew函數，更新個體最優解，并得到本輪全局最優解；S24，如果本輪全局最優解大于全局最優解，則將本輪全局最優解作為全局最優解，否則不變；S25，更新速度；S26，更新粒子位置，如繼續循環進入步驟S23，如結束循環輸出粒子位置。

技術領域

本發明涉及芯片物理設計靜態時序技術領域，尤其是涉及了一種基于PSO算法的有用偏差時序優化方法。

背景技術

隨著集成電路的設計需求更高，電路規模增大，組合邏輯等級增長，要使電路達到時序收斂也更加困難。集成電路的時序收斂由兩部分構成，一是保持時間收斂，二是建立時間收斂。對于電路來說，保持時間（hold）與電路功能直接相關，如果保持時間不收斂將導致功能出現問題。而建立時間（setup）則與電路的頻率有關，如果建立時間不收斂，就會導致電路的工作頻率達不到設計要求。因此在工程項目中，為了保證芯片的功能運行正常，應先排除保持時間違例，然后再盡量修掉建立時間違例。

集成電路的時鐘通常為樹狀，即通過保證到達各個節點的時鐘樹長度相同來簡化時序修復的工作難度。但對于到達同一點的建立時間和保持時間來說，相互之間有沖突。也就是說，如果某一點的保持時間有一定的裕量（slack），而建立時間有違例時，則可以通過改變到達這一點時鐘樹長度來將保持時間的裕量“借到”建立時間來，減小保持時間的裕量，也減小建立時間的違例。這種方法稱為有用偏差（useful skew）優化法。但是這種情況也可能導致在優化建立時間時產生新的保持時間違例。因此需綜合兩方面因素進行時序的優化。

發明內容

為解決現有技術的不足，實現有用偏差優化建立時間時，使保持時間的違例更小的目的，本發明采用如下的技術方案：

一種基于PSO算法的有用偏差時序優化方法，包括如下步驟：

S1，選取路徑公共點并加入緩沖器；

S2，將路徑公共點作為粒子，緩沖器數量作為粒子位置，將建立時間和保持時間的最差違例之和作為全局最優解，采用PSO（Particle Swarm Optimization，粒子群優化）算法得到最優緩沖器數量，包括如下步驟：

S21，隨機生成初始粒子位置；

S22，將初始粒子位置輸入skew函數，得到個體最優解和全局最優解；

S23，進入循環，將粒子位置輸入skew函數，更新個體最優解，并得到本輪全局最優解；

S24，如果本輪全局最優解大于全局最優解，則將本輪全局最優解作為全局最優解，否則全局優化解不變；

S25，根據粒子位置、全局最優解和慣性權重更新速度：

其中，vel是速度，w是慣性權重，r1、r2是介于0和1之間的隨機數，c1、c2是學習因子，pos是粒子位置，pbest是個體最優解，gbest是全局最優解；

S26，根據更新的速度更新粒子位置：

判斷循環是否符合結束條件，如果不符合則進入步驟S23，如果符合則輸出粒子位置，即得到優化后的緩沖器數量。