中文題目：SD-SSTA: 考慮偏斜分布的統計靜態時序分析算法

論文題目：SD-SSTA: Statistical Static Time Analysis Algorithm Considering Skewed Distribution

錄用期刊/會議：2024 International Symposium of Electronics Design Automation (ISEDA) (EI索引國際會議)

原文鏈接：https://www.ssslab.cn/assets/papers/2024-deng-SDSSTA.pdf 

DOI：10.1109/ISEDA62518.2024.10618081

錄用/見刊時間：2024-3-26

作者列表：

1） 鄧福星 中國石油大學（北京） 人工智能學院 碩 23

2） 馮一航 中國石油大學（北京） 人工智能學院 碩 23

3） 牛   丹 東南大學 自動化學院

4） 吳   梟 北京華大九天科技股份有限公司

5） 金   洲 中國石油大學（北京）人工智能學院

 

背景與動機:

靜態時序分析 (Static Timing Analysis，STA) 是近年來在數字電路設計中應用最廣泛和最成功的分析引擎之一。然而，確定性靜態時序分析 (Deterministic Static Timing Analysis, DSTA)沒有考慮工藝參數的波動對電路性能的影響，這引起了人們對確定性靜態時序分析能否有效模擬統計變化的關注。因此，統計靜態時序分析 (Statistical Static Timing Analysis，SSTA)已被提出并被廣泛研究。傳統的SSTA算法，如基于高斯分布的概率傳播算法和蒙特卡羅算法，無法達到高精度和良好的性能。本文提出了一種考慮偏態分布的SSTA算法——SD-SSTA，該算法成功地實現了到達時間和時序寬裕量的精確計算，并且具有時間和空間上的優異性能。

設計與實現:

（1）算法框架

圖1 SD-SSTA算法的實現過程

我們提出的SD-SSTA算法分為以下三個階段。(1) 讀取電路設計文件，建立時序圖的數據結構。(2) 進行前向傳播，從時序圖的根節點開始逐步計算所有節點的到達時間。(3) 計算指定時序路徑終點處的時序寬裕量。SD-SSTA算法流程如圖1所示。

（2）構建時序圖

我們收集電路的統計數據，組織電路設計文件，其中包括描述電路結構和時序信息的各個重要部分。圖2 (a)是一個簡單的電路示例，SD-SSTA算法通過讀取電路設計文件構建如圖2 (b)所示的時序圖。

圖2(a) 示例電路圖，(b)對應的時序圖

（3）SD-SSTA的操作

本文通過在高斯分布中加入偏度系數來描述非高斯分布。因此SD-SSTA算法的到達時間計算包括兩個部分。

圖3 非高斯分布的Max和Add操作的實現

 a. μ和σ: Max運算后通常形成非高斯分布。所以我們用高斯混合模型（Gaussian Mixture Model，GMM）建立模型最大值的概率密度函數（Probability Density Function，PDF）。首先利用蒙特卡羅模擬方法對非高斯分布進行建模，然后利用GMM進行擬合。換句話說，它可以分解成基本函數單元（Radial Basis Function，RBF)。進一步，我們從模型的屬性中提取每個擬合RBF的μ和σ。因此，我們將非高斯分布作為公式(1)的線性組合來處理，如圖3所示。最后，通過公式(2)提取到達時間μ和σ:

b.偏度系數: 兩個相關高斯隨機變量(X1和X2)的最大值的PDF形式為：

其中fi(x)分別是i = 1,2的高斯分布。

三階矩是偏度的度量。因此，通過計算三階矩，我們可以描述MAX運算后非高斯分布的偏度。計算公式如下：

（4）計算時序寬裕量

SD-SSTA算法計算指定時序路徑終點處的時序寬裕量。對于圖2(a)中的上升沿觸發的觸發器，在DFF/D處下降信號的時序寬裕量應用以下公式進行計算。

（5）性能優化

 圖4 名稱映射方法

在STA中，邏輯門的名稱通常以字符串的形式存儲在電路文件中。對于大規模的電路，字符串的搜索和比較將消耗大量的內存和時間。我們提出了一種名稱映射方法，將電路文件中一個邏輯門的所有名稱映射為整數，并且在程序運行過程中只使用整數進行計算。這種方式，特別是在大規模電路中，節省了大量的內存，也在一定程度上減少了運行時間。圖4顯示了Hash函數的映射過程。

實驗結果及分析:

表1 關于測試用例的信息。（前兩行反映了案例的數據大?。旱谝恍械闹悼梢苑从硶r序圖中的節點和邊的數量；第二行的值表示端點的數量；第三行的值表示標準差的均值）。

表2 每個樣例的最終準確度得分 

根據評分公式計算出相應的時序寬裕量準確度得分。表2比較了三種不同測試用例下SSTA和SD-SSTA算法計算的時間寬裕量準確性。從表1中可以看出，電路3的方差小，即工藝參數的變化范圍很小，因此傳統算法可以實現精確的計算。而電路2的方差大，傳統方法無法解決，SD-SSTA算法的優越性從而體現出來。

 

圖5 使用名稱映射方法前后的時間和內存比較

從圖5可以看出，名稱映射方法減少了算法的時間和內存，對大規模電路的效果尤為明顯。

結論:

本文提出了一種基于非高斯分布的SSTA方法SD-SSTA。不同于傳統的SSTA算法，我們利用GMM模型對非高斯分布進行建模，并在高斯分布的基礎上引入偏度系數。非高斯分布用μ，σ和偏度系數表示，即非高斯分布被參數化。利用這些參數，準確地計算了到達時間的前向傳播。在時間寬裕量的計算中，考慮了偏斜的影響，并在公式中引入了SAF。與傳統的SSTA結果相比，SD-SSTA算法顯著提高了時間寬裕量計算的準確度。此外，通過名稱映射有效地減少了內存和時間，提高了算法的性能。

通訊作者簡介:

金洲，副教授，中國石油大學（北京）計算機系副教授，入選北京市科協青年人才托舉工程、校青年拔尖人才。主要從事集成電路設計自動化（EDA）方面的研究工作。主持并參與國家自然科學基金青年項目、培育項目、重點項目，科技部重點研發微納電子專項、高性能計算專項青年科學家項目，國家重點實驗室開放課題、企業橫向課題等。在DAC、TCAD、TODAES、SC、PPoPP、IPDPS、TCAS-II、ASP-DAC等重要國際會議和期刊上發表60余篇高水平學術論文。獲EDA2青年科技獎、SC23最佳論文獎、ISEDA23榮譽論文獎、IEEJ九州支部長獎等。

 聯系方式：jinzhou@cup.edu.cn