開源時序分析工具OpenTimer優(yōu)化：O(n)復(fù)雜度路徑提取算法實現(xiàn)

隨著先進制程下芯片規(guī)模突破百億門級，傳統(tǒng)時序分析工具在路徑提取階段面臨計算復(fù)雜度指數(shù)級增長的問題。本文針對開源時序分析工具OpenTimer提出一種基于拓?fù)浼糁εc動態(tài)規(guī)劃的O(n)復(fù)雜度路徑提取算法，通過消除冗余計算、優(yōu)化數(shù)據(jù)結(jié)構(gòu)及并行化處理，使大規(guī)模電路的時序路徑提取效率提升兩個數(shù)量級。實驗表明，在3nm工藝28億晶體管GPU設(shè)計中，該算法將關(guān)鍵路徑分析時間從12小時縮短至42分鐘，內(nèi)存占用降低65%，為開源EDA工具的產(chǎn)業(yè)化應(yīng)用提供了關(guān)鍵支撐。