科研動(dòng)態(tài)
SD-SSTA:?考慮偏斜分布的統(tǒng)計(jì)靜態(tài)時(shí)序分析算法
中文題目：SD-SSTA: 考慮偏斜分布的統(tǒng)計(jì)靜態(tài)時(shí)序分析算法
論文題目：SD-SSTA: Statistical Static Time Analysis Algorithm Considering Skewed Distribution
錄用期刊/會(huì)議：2024 International Symposium of Electronics Design Automation (ISEDA) (EI索引國(guó)際會(huì)議)
原文鏈接：https://www.ssslab.cn/assets/papers/2024-deng-SDSSTA.pdf
DOI：10.1109/ISEDA62518.2024.10618081
錄用/見(jiàn)刊時(shí)間：2024-3-26
作者列表：
1） 鄧福星 中國(guó)石油大學(xué)（北京） 人工智能學(xué)院 碩 23
2） 馮一航 中國(guó)石油大學(xué)（北京） 人工智能學(xué)院 碩 23
3） 牛 丹 東南大學(xué) 自動(dòng)化學(xué)院
4） 吳 梟 北京華大九天科技股份有限公司
5） 金 洲 中國(guó)石油大學(xué)（北京）人工智能學(xué)院
背景與動(dòng)機(jī):
靜態(tài)時(shí)序分析 (Static Timing Analysis，STA) 是近年來(lái)在數(shù)字電路設(shè)計(jì)中應(yīng)用最廣泛和最成功的分析引擎之一。然而，確定性靜態(tài)時(shí)序分析 (Deterministic Static Timing Analysis, DSTA)沒(méi)有考慮工藝參數(shù)的波動(dòng)對(duì)電路性能的影響，這引起了人們對(duì)確定性靜態(tài)時(shí)序分析能否有效模擬統(tǒng)計(jì)變化的關(guān)注。因此，統(tǒng)計(jì)靜態(tài)時(shí)序分析 (Statistical Static Timing Analysis，SSTA)已被提出并被廣泛研究。傳統(tǒng)的SSTA算法，如基于高斯分布的概率傳播算法和蒙特卡羅算法，無(wú)法達(dá)到高精度和良好的性能。本文提出了一種考慮偏態(tài)分布的SSTA算法——SD-SSTA，該算法成功地實(shí)現(xiàn)了到達(dá)時(shí)間和時(shí)序?qū)捲Ａ康木_計(jì)算，并且具有時(shí)間和空間上的優(yōu)異性能。
設(shè)計(jì)與實(shí)現(xiàn):
（1）算法框架
圖1 SD-SSTA算法的實(shí)現(xiàn)過(guò)程
我們提出的SD-SSTA算法分為以下三個(gè)階段。(1) 讀取電路設(shè)計(jì)文件，建立時(shí)序圖的數(shù)據(jù)結(jié)構(gòu)。(2) 進(jìn)行前向傳播，從時(shí)序圖的根節(jié)點(diǎn)開(kāi)始逐步計(jì)算所有節(jié)點(diǎn)的到達(dá)時(shí)間。(3) 計(jì)算指定時(shí)序路徑終點(diǎn)處的時(shí)序?qū)捲Ａ?。SD-SSTA算法流程如圖1所示。
（2）構(gòu)建時(shí)序圖
我們收集電路的統(tǒng)計(jì)數(shù)據(jù)，組織電路設(shè)計(jì)文件，其中包括描述電路結(jié)構(gòu)和時(shí)序信息的各個(gè)重要部分。圖2 (a)是一個(gè)簡(jiǎn)單的電路示例，SD-SSTA算法通過(guò)讀取電路設(shè)計(jì)文件構(gòu)建如圖2 (b)所示的時(shí)序圖。
圖2(a) 示例電路圖，(b)對(duì)應(yīng)的時(shí)序圖
（3）SD-SSTA的操作
本文通過(guò)在高斯分布中加入偏度系數(shù)來(lái)描述非高斯分布。因此SD-SSTA算法的到達(dá)時(shí)間計(jì)算包括兩個(gè)部分。
圖3 非高斯分布的Max和Add操作的實(shí)現(xiàn)
a. μ和σ: Max運(yùn)算后通常形成非高斯分布。所以我們用高斯混合模型（Gaussian Mixture Model，GMM）建立模型最大值的概率密度函數(shù)（Probability Density Function，PDF）。首先利用蒙特卡羅模擬方法對(duì)非高斯分布進(jìn)行建模，然后利用GMM進(jìn)行擬合。換句話(huà)說(shuō)，它可以分解成基本函數(shù)單元（Radial Basis Function，RBF)。進(jìn)一步，我們從模型的屬性中提取每個(gè)擬合RBF的μ和σ。因此，我們將非高斯分布作為公式(1)的線(xiàn)性組合來(lái)處理，如圖3所示。最后，通過(guò)公式(2)提取到達(dá)時(shí)間μ和σ:
b.偏度系數(shù): 兩個(gè)相關(guān)高斯隨機(jī)變量(X1和X2)的最大值的PDF形式為：
其中fi(x)分別是i = 1,2的高斯分布。
三階矩是偏度的度量。因此，通過(guò)計(jì)算三階矩，我們可以描述MAX運(yùn)算后非高斯分布的偏度。計(jì)算公式如下：
（4）計(jì)算時(shí)序?qū)捲Ａ?/span>
SD-SSTA算法計(jì)算指定時(shí)序路徑終點(diǎn)處的時(shí)序?qū)捲Ａ?。?duì)于圖2(a)中的上升沿觸發(fā)的觸發(fā)器，在DFF/D處下降信號(hào)的時(shí)序?qū)捲Ａ繎?yīng)用以下公式進(jìn)行計(jì)算。
（5）性能優(yōu)化
圖4 名稱(chēng)映射方法
在STA中，邏輯門(mén)的名稱(chēng)通常以字符串的形式存儲(chǔ)在電路文件中。對(duì)于大規(guī)模的電路，字符串的搜索和比較將消耗大量的內(nèi)存和時(shí)間。我們提出了一種名稱(chēng)映射方法，將電路文件中一個(gè)邏輯門(mén)的所有名稱(chēng)映射為整數(shù)，并且在程序運(yùn)行過(guò)程中只使用整數(shù)進(jìn)行計(jì)算。這種方式，特別是在大規(guī)模電路中，節(jié)省了大量的內(nèi)存，也在一定程度上減少了運(yùn)行時(shí)間。圖4顯示了Hash函數(shù)的映射過(guò)程。
實(shí)驗(yàn)結(jié)果及分析:
表1 關(guān)于測(cè)試用例的信息。（前兩行反映了案例的數(shù)據(jù)大小：第一行的值可以反映時(shí)序圖中的節(jié)點(diǎn)和邊的數(shù)量；第二行的值表示端點(diǎn)的數(shù)量；第三行的值表示標(biāo)準(zhǔn)差的均值）。
表2 每個(gè)樣例的最終準(zhǔn)確度得分
根據(jù)評(píng)分公式計(jì)算出相應(yīng)的時(shí)序?qū)捲Ａ繙?zhǔn)確度得分。表2比較了三種不同測(cè)試用例下SSTA和SD-SSTA算法計(jì)算的時(shí)間寬裕量準(zhǔn)確性。從表1中可以看出，電路3的方差小，即工藝參數(shù)的變化范圍很小，因此傳統(tǒng)算法可以實(shí)現(xiàn)精確的計(jì)算。而電路2的方差大，傳統(tǒng)方法無(wú)法解決，SD-SSTA算法的優(yōu)越性從而體現(xiàn)出來(lái)。
圖5 使用名稱(chēng)映射方法前后的時(shí)間和內(nèi)存比較
從圖5可以看出，名稱(chēng)映射方法減少了算法的時(shí)間和內(nèi)存，對(duì)大規(guī)模電路的效果尤為明顯。
結(jié)論:
本文提出了一種基于非高斯分布的SSTA方法SD-SSTA。不同于傳統(tǒng)的SSTA算法，我們利用GMM模型對(duì)非高斯分布進(jìn)行建模，并在高斯分布的基礎(chǔ)上引入偏度系數(shù)。非高斯分布用μ，σ和偏度系數(shù)表示，即非高斯分布被參數(shù)化。利用這些參數(shù)，準(zhǔn)確地計(jì)算了到達(dá)時(shí)間的前向傳播。在時(shí)間寬裕量的計(jì)算中，考慮了偏斜的影響，并在公式中引入了SAF。與傳統(tǒng)的SSTA結(jié)果相比，SD-SSTA算法顯著提高了時(shí)間寬裕量計(jì)算的準(zhǔn)確度。此外，通過(guò)名稱(chēng)映射有效地減少了內(nèi)存和時(shí)間，提高了算法的性能。
通訊作者簡(jiǎn)介:
金洲，副教授，中國(guó)石油大學(xué)（北京）計(jì)算機(jī)系副教授，入選北京市科協(xié)青年人才托舉工程、校青年拔尖人才。主要從事集成電路設(shè)計(jì)自動(dòng)化（EDA）方面的研究工作。主持并參與國(guó)家自然科學(xué)基金青年項(xiàng)目、培育項(xiàng)目、重點(diǎn)項(xiàng)目，科技部重點(diǎn)研發(fā)微納電子專(zhuān)項(xiàng)、高性能計(jì)算專(zhuān)項(xiàng)青年科學(xué)家項(xiàng)目，國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題、企業(yè)橫向課題等。在DAC、TCAD、TODAES、SC、PPoPP、IPDPS、TCAS-II、ASP-DAC等重要國(guó)際會(huì)議和期刊上發(fā)表60余篇高水平學(xué)術(shù)論文。獲EDA2青年科技獎(jiǎng)、SC23最佳論文獎(jiǎng)、ISEDA23榮譽(yù)論文獎(jiǎng)、IEEJ九州支部長(zhǎng)獎(jiǎng)等。
聯(lián)系方式：[email protected]