數字電路的統計計時分析系統和方法
2023-06-17 18:38:16 4
專利名稱：數字電路的統計計時分析系統和方法
技術領域：
本發明涉及數字集成電路的設計自動化。具體地說，涉及在存在延遲變化的情況下，數字電路的靜態計時分析。更具體地說，本發明涉及在考慮並保存各個電路組件的延遲之間的相關性的時候，以概率或統計方式傳播數字電路的到達時間和所需到達時間。
相關申請C.Visweswariah，「System and Method for Probabilistic CriticalityPrediction of Digital Circuits」，文件編號YOR92003-0402US1，美國專利申請號(待指定)，申請日09/18/03。
C.Visweswariah，「System and Method for Incremental StatisticalTiming Analysis of Digital Circuits」，文件編號YOR92003-0401，美國專利申請號(待指定)，申請日09/18/03。
這些同時待審的申請中陳述的說明作為參考整體包含於本申請中。
背景技術：
對於後續每代集成電路技術來說，可變性成比例地增大。這種可變性的來源包括製造變化，設備疲勞，環境變化和鎖相環(PLL)變化。就製造變化來說，線路前端(FEOL，the front-end-of-the-line)(其內定義有源電晶體的層)表現出電晶體電學特性方面的變化。在製造過程中，諸如柵極長度，半導體結的深度或氧化物的厚度之類物理量不能被極佳地控制，從而表現出變化，這會導致電晶體性能方面的變化。隨著現代技術中，物理尺寸變得越來越小，可變性成比例地增大。另外，由金屬互連層構成的線路後端(BEOL)(the back-end-of-the-line)也表現出可變性。例如，每個金屬層的厚度、寬度和層間介電厚度是可變性的來源。這些又導致導線改變它們的延遲，事實上這些可變性的來源能夠改變驅動它們的柵極的延遲和由它們驅動的柵極的延遲。
第二種主要變化起因於諸如熱電子和負偏壓溫度不穩定性(NBIT)之類設備疲勞結果。在現場長期使用之後，由於這些物理現象的緣故，電晶體特性發生變化，導致電路組件的延遲發生變化。
第三種主要變化起因於諸如溫度和供電電壓之類環境影響。
第四種主要變化是PLL變化，它可包括PLL抖動和佔空度可變性。
要指出的是除了上述之外，還存在其它變化來源，例如模型-硬體誤相關性，矽絕緣體(SOI)歷史影響和耦合噪聲。在數字集成電路的統計計時分析中，還可考慮這些其它類型的變化。
可按照多種不同的方式對集成電路中柵極和導線表現出的延遲的變化分類。所述變化可源於製造過程中批次的不同，晶片的不同，晶片的不同，或者在單一晶片內部。光刻過程中的透鏡象差效應會導致原版域兩端電晶體有效長度的變化。在晶片兩端能夠存在溫度和供電電壓變化。也可依據其中形成可變性的時標對變化分類。例如，疲勞效應在數年內導致可變性，而晶片兩端的溫度和供電電壓梯度可在數秒或數毫秒內形成，耦接噪聲可在納秒級或皮秒級內產生。無論按照何種方式對其分類，顯然這些變化源使集成電路分析和設計更困難，在計時分析中，必須準確考慮這些變化源。
處理這種可變性的傳統計時(timing)方法是在不同的「情況」或「角落」(corner)進行多次靜態計時分析，從而確定在這些變化的影響下，電路的性能的散布。角落可包括「最佳情況」，「標稱」和「最壞情況」。不幸的是，由於獨立的並且重要的變化源眾多，並且需要太多的計時運行(run)，因此傳統的方法不成功。一種解決方式是針對相對於某些變化源的最壞情況或保護帶，但是這會導致悲觀的性能預測。另一種解決計時運行的激增的方式是跳過位於某些角落的分析，但是這存在風險，因為在跳過的角落，電路的性能可能是不合格的，這可由在檢測器上或在現場失效的晶片證明。由於這些影響，傳統的計時方法迅速變得難以負擔，同時既冒險又悲觀。
傳統計時方法所面臨的問題的一種解決方法是統計或概率計時分析。在這種分析中，諸如延遲、到達時間和遲滯(slack)之類計時量不被看作單一數字，而是被看作概率分布。從而，藉助單一計時運行預測在變化的影響下，電路性能的完整概率分布。可能避免不必要的風險，過多的計時運行和悲觀主義的問題。現有技術中這種統計計時方法的四個例子包括Liou等的[J-J.Liou，K-T.Cheng，S.Kundu和A.Krstic，「Faststatistical timing analysis by probabilistic event propagation」，Proc.Design Automation Conference，2001年6月，Las Vegas，NY，661-666頁]，Scheffer[L.Scheffer，「Explicit computation of performanceas a function of process variation」，Proc.ACM/IEEE workshop on timingissues in the specification and synthesis of digital systems，2002年12月，Monterey，CA，1-8頁]，Gattiker等[A.Gattiker，S.Nassif，R.Dinakar和C.Long，「Timing yield estimation from static timing analysis」，Proc.IEEE International Symposium on Quality Electronic Design(ISQED)，2001，437-442頁]，和Jess等[J.A.G.Jess，K.Kalafala，S.R.Naidu，R.H.J.M.Otten和C.Viserswariah，「Statistical timing forparametric yield prediction of digital integrated circuits」，Proc.DesingAutomation Conference，2003年6月，Anaheim，CA，932-937頁]。上面引用的參考文獻作為參考整體包含於此。
實踐中現有方法不適宜的原因有幾個。現有方法的主要缺陷是它們不能正確說明相關性。集成電路上柵極和導線的延遲表現出強相關性。考慮一個簡單例子來證明相關性的重要性。具有50000個鎖存器的晶片具有50000次設置計時測試和50000次保持計時測試。假定這些測試中的每次測試被成功滿足的概率為99.99％。如果100000個概率完美相關，則晶片正確工作的總概率為99.99％。即，如果一個測試通過，則所有測試都通過。但是，如果概率是獨立的，則產生工作晶片的概率為0.9999的100000次冪，結果是微不足道的0.005％！延遲相關性的來源有很多，下面說明一些例子。兩個路徑可共用相同柵極中的一些；這種情況下，兩個路徑的延遲相關。如果由於某些製造變化的緣故，特定的晶片具有更強的P型電晶體，則該晶片上的每個單個P型電晶體將更強。如果第三層金屬稍厚，則在整個晶片內，第三層金屬可能較厚。發射路徑(使數據信號到達鎖存器的路徑)和俘獲路徑(使對應的時鐘信號到達同一鎖存器的路徑)表現出一定的共同性，於是具有相關延遲。共同性可包括共用沿路徑的一些柵極，共用金屬層，共用供電電壓島，共用相同的柵極等。由於柵極在晶片表面的物理位置的緣故，它們的延遲也可以是相關的。例如，彼此鄰近的兩個柵極不可能看到顯著的相對通道長度變化，於是，它們的延遲可能會密切相關。
必須準確考慮所有這些變化源，否則結果將沒有意義。在Liou等的文獻中，每個單個柵極的延遲被認為與其它任意柵極完全無關，致使分析在實踐中無用。在Gattiker等的文獻中，考慮了柵極延遲相關性。列舉了關鍵路徑，但是當組合這些路徑的影響時，每個路徑的延遲被認為與任意其它路徑無關，從而忽略了數個重要的相關性來源。
在現有方法中，考慮相關性的一種方法是Jess等人的方法。該方法是基於路徑的方法。每個路徑的延遲或遲滯被收集並被表示成變化源的一階模型。隨後通過按照相關概率方式組合這些路徑遲滯，計算整個電路或晶片的遲滯。不幸的是，任意電路中存在指數數目的路徑。列舉並分析電路中的所有路徑不現實。Jess等建議考慮前N個關鍵路徑，但是顯然不能保證在過程空間或變化空間中的某一點或角落，第(N+1)個路徑(或者除前N個路徑之外的任意路徑)不關鍵。所有基於路徑的方法都具有路徑數目過大，必須使用某一試探法來限制提交供詳細分析的路徑的數目的基本限制。
要指出的是雖然在集成電路的延遲可變性方面，存在許多重要的相關性來源，但是也存在一些完全隨機的變化源。例如，在現代技術中，電晶體中氧化物厚度只為幾個原子厚，出於各種原因，電晶體可能具有多於一層或少於一層的原子，導致一個電晶體與另一個電晶體之間相當隨意的變化。雖然Liou等的現有方法能夠處理這種隨機變化，但是其它現有方法，例如Gattiker等和Jess等的方法不能處理這種隨機變化。
此外，所有上述現有方法存在其它問題。來自靜態計時程序的重要輸出是能夠使設計員，或者自動化合成或優化程序能夠改進電路的診斷結果。現有方法缺乏這樣的診斷結果。例如，如果某一電路路徑對特定的變化源過於敏感，則對於變化，電路並不穩健。如果這種診斷結果存在，則設計員或合成程序能夠採取各種描述降低所述過分敏感性。從而對於統計計時程序的輸出來說，重要的是由變化源用參數表示。代替報告電路某一節點的到達時間具有過遲的概率分布，有益的是向各個變化源報告新近到達時間的敏感性，以便能夠實現恰當的補救。現有方法以概率分布的形式產生統計計時結果。不幸的是，這無助於設計員或自動化優化程序改進電路的性能或穩健性。
由於這些及其它原因，工業實踐中未使用文獻中提出的統計計時方法。
發明內容
本發明的一個方面是數字電路的統計或概率靜態計時的一種改進系統和方法。
本發明的另一方面是一種統計計時方法，所述方法具有計時圖尺寸方面的線性複雜性，和變化源的數目方面的線性複雜性。
本發明的另一方面是一種統計計時方法，所述方法考慮了單個柵極和導線的延遲之間的相關性，以及電路路徑的延遲之間的相關性。
本發明的另一方面是一種統計計時方法，所述方法允許包含確定部分，相關隨機部分和獨立隨機部分的延遲模型。
本發明的另一方面是一種把數字電路的計時圖的每個節點的到達時間、要求到達時間、變化(slew)和遲滯(slack)表示成概率分布的計時結果。
本發明的另一方面是一種按照由變化源參數化的形式，表示數字電路的計時圖的每個節點的到達時間、要求到達時間、變化和遲滯的計時圖。
本發明是一種考慮統計延遲變化，用於數字電路的統計或概率靜態計時分析的系統和方法。每個柵極或導線的延遲被假定為由標稱部分，由每個變化源參數化的相關隨機部分和獨立隨機部分構成。在考慮相關性的同時，以參數化隨機變量的形式傳播到達時間和要求的到達時間。包括早(early)模式和晚(late)模式計時；處理組合和順序電路；適應靜態CMOS以及動態邏輯電路系列。就計時圖的大小和變化源的數目來說，計時分析複雜性是線性的。結果是計時報告，其中以參數化的概率分布的形式，報告諸如到達時間和遲滯之類所有計時量。
參考附圖，根據本發明優選實施例的下述非限制性詳細說明，將更好地理解本發明的前述及其它目的、特徵和優點，其中圖1是本發明的一個實施例的方框圖，描述了數字電路的統計或概率靜態計時。
圖2執行數字電路的統計或概率靜態計時的優選方法的流程圖。
圖3表示了計時圖的兩個稜邊和三個節點，舉例說明統計計時分析中涉及的基本正向傳播操作。
圖4表示了計時圖的兩個稜邊和三個節點，舉例說明統計計時分析中涉及的基本反向傳播操作。
圖5是輸出報告的一個優選實施例的方框圖。
具體實施例方式
圖1中表示了本發明的統計或概率靜態計時流程。第一輸入是代表要分析的電路的結構的連接表(netlist)，表示在方框100中。第二輸入是一組計時斷言(assertion)，方框110。這些計時斷言通常包括主輸入端的到達時間，主輸出端的要求到達時間，時鐘的相位信息，和主輸出端驅動的外部負載的細節。斷言可採取確定數字或獨立概率分布或相關概率分布的形式。第三輸入是一組參數化延遲模型，方框120。這些參數化延遲模型允許計時器確定不僅作為傳統的延遲模型變量(例如輸入變化(slew)或上升/下降時間，和輸出負載)的函數而且作為變化源的函數的柵極或導線的延遲。例如，可採用類似於下述的一階線性模型
這裡延遲由確定(常數)部分a0，相關(或全局)部分 和獨立(或局部)部分an+1ΔR組成。變化源的數目為n，並且ai，i＝1，...，n是延遲對變化源xi，i＝1，...，n的敏感性，an+1是對變化的獨立隨機來源R的敏感性。符號Δxi表示xi與其平均或標稱值的偏差，ΔR表示R與其平均或標稱值的偏差。要明白的是可根據需要在預表徵步驟中保存延遲模型，或者在運行中(on the fly)計算延遲模型。保存延遲模型的格式可包括分析延遲等式或表格模型。下一輸入是變化的來源的統計信息，方框130。該輸入一般具有變化來源的列表，以及每個變化來源的平均值和標準偏差。這裡規定變化源之間的任意相關性。
現有技術中，電路連接表100，斷言110，參數化延遲模型120，變化源的統計信息130，以及它們的功能等同物為人們熟知。
新的概率或統計靜態計時程序(方框140)接受所有這些輸入，並產生新的統計計時報告(方框150)。該報告一般包括電路每個節點的到達時間、要求到達時間、遲滯和變化。這些計時量不是單個數字，而是概率分布。計時報告中的信息可採取多種形式，包括下述一種或多種每個計時量的平均值和方差，每個計時量的分布的參數化表示，每個計時量的分布的圖形表示，和這些各個計時量之間的相關性報告。在計時報告中可加入諸如檢查過分敏感性之類的各種自動審計。關心過分敏感性，因為為了改進電路的穩健性，必須降低所述過分敏感性。顯然被計時的電路可以非常大，由數百萬個柵極和導線組成。上面提及的所有信息可能極其龐大，從而通常提供選項以便有選擇地輸出所需的信息，或者甚至應要求計算或圖形顯示所有該信息。
圖2的流程圖中表示了方框140的新穎的統計計時器的細節。第一步是讀取包含要被計時的電路的布局細節的連接表。由於該連接表通常呈分層結構的形式，因此使該連接表變平(即減少分層結構中層次的數目)。在方框210中，讀取斷言(每個斷言可以是確定的或者概率的)，並讀取參數化延遲模型。變化源的信息，例如平均值和標準偏差，以及變化源之間的任意相關性被保存在存儲器中。
方框220中所示的下一主要步驟是計時圖的構成，這是在所有靜態計時程序中都類似的一個步驟。在靜態計時圖中，每個節點代表電路的一個節點或信號，每個弧線或稜邊代表當通過諸如柵極或導線之類電路組件傳送一個邏輯轉變(從低到高或從高到低)時，導致的電路中的延遲。於是在該圖中捕獲電路的所有可能有效邏輯轉變。到達時間通常保存在靜態計時圖的節點上，單個柵極和導線的延遲保存在靜態計時圖的稜邊上。晚模式中的到達時間是在其正確的邏輯值下，保證對應信號穩定的最早時間(已通過電路的任意可能路徑)，早模式中的到達時間是對應信號能夠從其前一周期的穩定邏輯值改變的最早時間(即，輸出不能早於早模式到達時間發生變化)。圖中的順序部件和動態電路由稱為測試段的一種特殊稜邊(edge)表示，所述測試段是計時圖的(必須在計時圖的兩個節點之間進行計時測試以便確保電路的正確計時操作)的指示。本領域技術人員熟知關於柵極層次連接表和電晶體層次連接表的這種靜態計時圖的建立。
下一步驟是本發明的通過計時圖的，到達時間的相關統計正向傳播(方框230)。隨後在方框240，進行本發明的要求到達時間的相關統計反向傳播。最後，在方框250，產生本發明的計時報告。下面說明在早模式和晚模式分析方框230和240中涉及的計算細節。
靜態計時分析中的四種基本運算是「加」、「減」、「最大」和「最小」。為了實現成功的統計計算分析，必須用概率等同物替代這四種基本運算。關鍵是概率等同物必須正確考慮和傳播相關性。考慮圖3中所示的簡單情形，圖3中，出自節點a(310)和b(320)的計時圖的兩條有向稜邊(340和350)在公共計時節點c(330)相遇。稜邊dac代表從節點a到節點c的延遲，稜邊dbc代表從節點b到節點c的延遲。我們假定在a和b的早到達時間和晚到達時間為如下形式
ATalate=a0late+i=1nailatexi+an+1lateRalate,]]>ATblate=b0late+i=1nbilatexi+bn+1lateRblate,]]>ATaearly=a0early+i=1naiearlyxi+an+1earlyRaearly,]]>ATbearly=b0early+i=1nbiearlyxi+bn+1earlyRbearly,]]>並且延遲為如下形式daclate=g0late+i=1ngilatexi+gn+1lateRglate,]]>dbclate=h0late+i=1nhilatexi+hn+1lateRhlate,]]>dacearly=g0early+i=1ngiearlyxi+gn+1earlyRgearly,]]>dbclate=h0early+i=1nhiearlyxi+hn+1earlyRhearly.]]>在節點c，要求確定ATclate=max[ATalate+daclate,ATblate+dbclate]]]>和ATcearly=min[ATaearly+dacearly,ATbearly+dbcearly],]]>它們分別是保證節點c在當前時鐘周期中穩定的最早時間和節點c可從其前一周期移動邏輯值改變的最早時間。雖然下面舉例說明晚模式計算，可按照類似方式進行早模式計算。從而，ATclate=max[{a0late+i=1nailatexi+an+1lateRalate+g0late+i=1ngilatexi+gn+1lateRglate},]]>{b0late+i=1nbilatexi+bn+1lateRblate+h0late+i=1nhilatexi+hn+1lateRhlate}],]]>=max[{(a0late+g0late)+i=1n(ailate+gilate)xi+an+1lateRalate+gn+1lateRglate},]]>{(b0late+h0late)+i=1n(bilate+hilate)xi+bn+1lateRblate+hn+1lateRhlate}].]]>如果變化源(全局變量x和局部變量R)是高斯或正態分布，則我們試圖找出其最大值的上述兩個量值也是高斯分布。從而，我們可寫作ATclate=max[{p1=N(1,1)},{p2=N(2,2)}],]]>這裡p1和p2是具有假定為如上所述的平均值和方差的高斯隨機變量。這兩個隨機變量是不獨立的，即這兩個隨機變量相關。但是，變化源x可能相關或獨立。下面說明這些情況中的每種情況。
假定變化源彼此獨立，並且具有零均值和單位方差，則我們可把協方差矩陣寫為cov(p1,p2)=i=1n{ailate+gilate}2+{an+1late}2+{gn+1late}2i=1n(ailate+gilate)(bilate+hilate)i=1n(ailate+gilate)(bilate+hilate)i=1n{bilate+hilate}2+{bn+1late}2+{hn+1late}2,]]>但是如果變化源不是獨立的，則協方差矩陣是(a1+g1)(a2+g2)(an+gn)an+1gn+100(b1+h1)(b2+h2)(bn+hn)00bn+1hn+1[V](a1+g1)(b1+h1)(a2+g2)(b2+h2)(an+gn)(bn+hn)an+10gn+100bn+10hn+1,]]>這裡V是用戶提供的變化源的協方差，為了簡潔起見，在後一等式中省略了上標late。(注意在上面的獨立情況下，V是對角矩陣)。在任一情況下，比較cov(p1,p2)=12121222,]]>能夠推導σ1、σ2和相關係數ρ。在變化源獨立的情況下，這可通過收集平方和及我們試圖確定其最大值的兩個高斯分布的對應係數的乘積來實現。要指出的是到達時間和延遲的隨機分量提供2×2協方差矩陣的對角項，從而增大正在確定其最大值的兩個數量的方差，但是不提供非對角項，從而減小相關性係數。
下一步是計算max[p1，p2]，這可利用如同在[J.A.G.Jess和C.Viserswariah於2002年6月27日向美國專利局申請的「System andMethod For Statistical Modeling And Statistical Timing Analysis OfIntegrated Circuits」，美國專利申請號0/184329]，及Jess等[J.A.G.Jess，K.Kalafala，S.R.Naidu，R.H.J.M.Otten和C.Viserswariah，「Statisticaltiming for parametric yield prediction of digital integrated circuits」，Proc.Desing Automation Conference，2003年6月，Anaheim，CA，932-937頁]中教導的現有方法實現。上述文獻以參考的方式全部包含在此。簡要地說，執行的優選方法是在恰當的數值範圍內(例如，從max(μ1-3σ1，μ2-3σ2)到max(μ1+3σ1，μ2+3σ2))掃描變量η。在η的每個值下，p1＝η的概率被乘以p2＜η的條件概率，獲得p1優於(dominate)p2的概率。同樣地，在η的相同值下，p2＝η的概率被乘以p1＜η的條件概率，獲得p2優於p1的概率。這種實踐導致ATclate的概率分布。對η的所有值收集p1優於p2和p2優於p1的單個概率；在上面引用的參考文獻中，這些概率被稱為「聯編概率」(binding probability)，而在本文獻中它們被稱為「到達緊密度概率」(ATP)，因為這些概率是分別依據圖3的上稜邊和下稜邊確定位於節點c的到達時間的概率。我們把這些到達緊密度概率分別表示為T和(1-T)。要指出的是Jess等的方法中使用類似的技術，但是沒有考慮延遲的完全隨機分量，另外基於路徑應用該方法，而這裡在計時圖的每個節點應用該方法。
在計時圖中進一步前移之前的最後步驟是按照允許在計時圖中向下遊傳播最後到達時間的方式，重新表述在節點c的最後到達時間。重新表述的方式如下所示。由於依據圖3時間的T％的上稜邊確定節點c的到達時間，從上稜邊得到節點c的到達時間對全局變化源的依賴性，但是具有權重因子T。同樣地，從下稜邊得到節點c的到達時間對全局變化源的依賴性，但是具有權重因子(1-T)。數學上表示成ATclate=c0late+i=1ncilatexi+cn+1lateRclate]]>cilate=T(ailate+gilate)+(1-T)(bilate+hilate),i=1,2,n.]]>剩下的是確定c0late和cn+1late，根據ATclate的概率分布易於確定它們。分布的平均值被賦予c0late，隨機部分cn+1late被賦予一個值，以致分布的方差和重新表述的到達時間的方差相符。
現在已按照「標準形式」表述了節點c的到達時間，節點c的到達時間可向下遊傳播。要明白代替最大值，早模式計算只需要計算兩個分布的最小值。按照稍微不同的方式計算條件概率，例程的其餘部分相同。例如，在η的掃描過程中，p1＝η的概率被乘以p2＞η的條件概率，獲得p1小於p2的概率。本領域的技術人員顯然可擴展上述方法，以適應延遲等式的各種功能形式和各種概率分布。所需要的是計算緊密度概率T和(1-T)，並按照「標準形式」重新表述位於節點c的到達時間，以便向下遊傳播。
當兩個以上的稜邊會聚於某一計時節點時，每次兩個稜邊地進行最大化和最小化。到達緊密度概率被保存為計算展開(unfold)，隨後在後處理步驟中分配最終的緊密度概率。例如，假定存在會聚於某一計時點的3條稜邊。假定前兩條稜邊的緊密度概率分別被確定為60％和40％。現在，這兩種分布的最大值再與由第三稜邊代表的路徑延遲進行max運算。假定對於第一對稜邊來說，該計算得到的緊密度概率為80％，第三稜邊的緊密度概率為20％。則這三條稜邊的最終到達緊密度概率分別為48％(0.6×0.8)，32％(0.4×0.8)和20％。
要明白按照類似方式，通過計時圖，正向傳播早模式到達時間，唯一的差別在於考慮早模式延遲，並且代替「max」運算使用「min」運算。
這樣，通過分級(levelized)計時圖，正向傳播早到達時間和晚到達時間，直到計算了所有端點的到達時間為止。端點是主輸出端或者是測試段。在主輸出端，在晚模式下，從斷言的要求到達時間中減去概率到達時間，在早模式下，從概率到達時間中減去斷言的要求到達時間，從而分別確定主輸出端的晚遲滯和早遲滯。零遲滯意味著準確表示計時要求。正遲滯意味著存在高於滿足要求的某些計時餘量。負遲滯意味著電路不能正確完成任務。
類似地，在測試段相互比較到達時間，以確定遲滯。例如，在鎖存器，最後的數據到達時間通常被加入鎖存器的設置(或保護)時間中，隨後與早期時鐘到達時間比較，以確保數據被正確鎖存。對於不同類型的鎖存器和不同類型的動態電路來說，這些比較採取不同的形式，但是它們都是相同原理的直接擴展。
在完成正向傳播之後，下一步是要求到達時間的相關統計反向傳播(圖2的方框240)。始於每個端點，如同傳統的靜態計時分析中那樣，按照分級(levelized)方式，反向傳播要求的到達時間。但是，在本發明的方法中，這些要求的到達時間本質上是統計的。類似於圖2的方框230進行圖2的方框240中涉及的操作，但是存在一些重要差別。第一個差別是在反向穿越(traversal)中，延遲從要求的到達時間中被減去，而不是被加入到達時間。第二個差別是在反向穿越中，晚模式分析需要「min」運算，而早模式分析需要「max」運算。第三個差別是計時圖的某一稜邊的要求的到達緊密度概率被定義為依據該稜邊確定該稜邊的源節點的要求到達時間的概率。按照和方框220的正向傳播期間的到達緊密度概率完全相同的方式確定這些緊密度概率，並按照完全相同的方式應用這些緊密度概率，以便在進一步傳播之前，按照標準方式表述要求的到達時間。從而，類似於正向傳播進行反向傳播，只是存在這些不多的重要差別。
圖4圖解說明了反向傳播。反向傳播的基本目的是確定計時圖的每個節點的要求到達時間。假定我們試圖計算圖4的節點a(框410)的要求到達時間，節點a具有分別到達節點b(框420)和c(框43))的兩條扇出稜邊(框440和450)。從而，在晚模式下，節點a的要求到達時間可被寫為RATalate=min[{RATblate-dablate},{RATclate-daclate}]]]>早模式下，節點a的要求到達時間可被寫為RATaearly=max[{RATbearly-dabearly},{RATcearly-dacearly}].]]>減去稜邊的延遲，並獲得max或min的實際過程和正向傳播中執行的操作類似。同樣地，按照和正向傳播中相應計算完全類似的方式，確定要求的到達緊密度概率。
一旦完成正向和反向傳播，則在計時圖的任意地方，晚到達時間和早到達時間，要求的到達時間和遲滯現在都是可得到的，這些可按照許多不同的形式報告給用戶(圖2的方框250)。這些形式可包括圖形圖表，文本表格，應請求查詢，失敗計時測試的審計，在所有計時點或所有端點的過分敏感性的審計，等等。
圖5的方框510中圖解說明了計時報告。藉助編程接口，或者藉助硬碟文件可把計時報告傳送給用戶。計時報告通常由某些電路信息(方框520)和對應的統計計時信息(方框530)組成。電路信息可包括柵極、組件和導線的列表；或者路徑的列表；或者節點的列表；或者順序部件的列表；或者端點(主輸出端和計時測試)的列表；或者時鐘相位的列表。可按照各種方式分類和過濾這些項目，使得對於報告的閱讀者來說，報告直觀並且多產。就節點來說，對應的統計計時信息可包括一個或多個節點的統計到達時間，統計要求到達時間，統計變化(slew)或統計遲滯。對於計時測試或主輸出端來說，對應的計時信息可包括計時測試被滿足，或者主輸出端滿足其要求的到達時間的概率。對於路徑來說，對應的計時信息可包括統計路徑遲滯和統計到達時間，要求到達時間，其端點的變化和遲滯。此外，可按照不同形式表示報告中的每個統計計時量，包括平均值和標準偏差；平均值，獨立隨機部分和相關部分；計時量的分布的圖形顯示；或者對單個全局變化源的敏感性。此外，已知任意兩個統計計時量，則報告可包括這兩個計時量的相關係數，這兩個計時量的協方差矩陣，以及一個計時量大於或小於另一計時量的概率。上述說明中的每個計時量顯然可以是早模式或晚模式計時量之一；上升或下降計時量之一；以及特定於具體時鐘的具體相位的計時量。此外，一旦完成統計計時分析，則可按照各種有益方式報告這些結果。
上面在計時圖的簡單片斷的環境下解釋了本發明的具體說明。本領域的普通技術人員能夠擴展這些原理，以適應單獨的升降到達時間及延遲；順序(sequential)電路；具有透明(transparent)鎖存器的電路；處理變化(上升/下降時間)傳播和效果的擴展；完全隨機的概率延遲模型；相關的概率延遲模型；隨機的變化源；相關的變化源；具有關於鎖存器設置和保持測試的概率保護時間的電路；具有關於動態電路計時測試的概率保護時間的電路；具有多個時鐘相位的電路；時鐘循環周期和計時斷言是隨機的情況；電晶體層連接表，以及藉助電路模擬器，在傳播過程中計算參數化延遲模型的情形。
根據本公開內容，對本領域的技術人員來說，概率或統計靜態計時進程(圖1的方框140)接收的輸入顯然可以是計算機系統已知的任意輸入，包括(但不限於)鍵盤或滑鼠輸入，磁碟，磁帶，CD-ROM，網絡連接，光纖連接，射頻連結，紅外連結等。此外，包括參數化計時報告的輸出(圖1的方框150)可採取任意已知計算機輸出的形式。這些輸出包括(但不限於)印表機的列印輸出，圖形用戶界面(GUI)或CRT上的圖像，存儲介質(例如存儲器、CD-ROM、磁碟、軟磁碟)上的內容，文件，通過網絡(光纖、電話、電纜、射頻、紅外等)傳送的信息。
權利要求
1.一種確定電路中的計時的系統，包括a.接收表示要計時的電路的布局的電路連接表的連接表輸入端；b.接收代表邊界計時條件的一組一個或多個斷言的斷言輸入端；c.接收包含一個或多個變化源的可變性信息的一個或多個延遲變化源的列表的延遲可變性輸入端；d.接收參數化延遲模型的模型輸入端，參數化延遲模型包含關於電路的一個或多個組件的延遲的一個或多個模型，每個模型是一個或多個延遲變化源的函數；和e.確定並輸出電路的一個或多個節點的統計到達時間的處理單元，該統計到達時間呈一個或多個變化源的概率分布的加權和的形式。
2.按照權利要求1所述的系統，其中通過一次訪問電路的每個節點，所述處理單元確定統計到達時間。
3.按照權利要求1所述的系統，其中系統還確定並輸出電路的一個或多個節點的統計要求到達時間，該統計要求到達時間呈一個或多個變化源的概率分布的加權和的形式。
4.按照權利要求1所述的系統，其中處理單元還確定並輸出電路的一個或多個節點的統計遲滯，該統計遲滯呈一個或多個變化源的概率分布的加權和的形式。
5.按照權利要求1所述的系統，其中處理單元還確定並輸出電路的一個或多個節點的統計變化，該統計變化呈一個或多個變化源的概率分布的加權和的形式。
6.按照權利要求1所述的系統，其中處理單元進行晚模式統計計時分析，並輸出晚模式到達時間。
7.按照權利要求1所述的系統，其中處理單元進行早模式統計計時分析，並輸出一個或多個早模式到達時間。
8.按照權利要求1所述的系統，其中向電路的每個組件提供一個或多個獨立的升降統計延遲，所述處理單元確定並輸出電路的一個或多個節點的一個或多個獨立的升降統計到達時間。
9.按照權利要求8所述的系統，其中處理單元確定並輸出電路的一個或多個節點的一個或多個獨立的升降統計要求到達時間、一個或多個獨立的升降統計遲滯、和一個或多個獨立的升降統計變化。
10.按照權利要求1所述的系統，其中電路是下述一種或多種組合電路、順序電路、靜態邏輯電路和動態邏輯電路。
11.按照權利要求1所述的系統，其中電路是包含下述一個或多個的順序電路邊沿觸發的鎖存器、主從鎖存器、電平靈敏鎖存器和透明鎖存器。
12.按照權利要求1所述的系統，其中電路包含多個時鐘相位。
13.按照權利要求1所述的系統，其中電路的每個組件的參數延遲模型包括下述一個或多個確定部分、相關部分和獨立的隨機部分。
14.按照權利要求13所述的系統，其中變化源是相關的。
15.按照權利要求13所述的系統，其中變化源是獨立的。
16.按照權利要求1所述的系統，其中參數化延遲模型被預存在系統的一個或多個存儲器中的表中。
17.按照權利要求1所述的系統，其中參數化延遲模型在系統的一個或多個存儲器中被預存為延遲等式的係數。
18.按照權利要求1所述的系統，其中通過運行中電路模擬確定參數延遲模型。
19.按照權利要求1所述的系統，其中每個斷言是確定斷言和統計斷言之一。
20.按照權利要求1所述的系統，其中時鐘-邊沿信息是確定的時鐘-邊沿信息和統計的時鐘-邊沿信息之一。
21.按照權利要求1所述的系統，其中電路是順序電路，每個計時測試的保護時間是確定的保護時間和統計的保護時間之一。
22.一種分析電路的計時的方法，包括下述步驟a.輸入連接表、一個或多個斷言、一個或多個參數化延遲模型和一個或多個變化源；b.建立代表電路的計時圖，所述計時圖具有一個或多個節點和一條或多個稜邊；c.對於到達時間的正向傳播，對計時圖分級；d.在計時圖的每一級，傳播位於每個節點的一個或多個統計到達時間，每個統計到達時間是一個或多個變化源的概率分布的加權和。
23.按照權利要求22所述的方法，其中通過一次訪問電路的每個節點，確定統計到達時間。
24.按照權利要求22所述的方法，其中確定並輸出電路的一個或多個節點的統計變化，該統計變化呈一個或多個變化源的概率分布的加權和的形式。
25.按照權利要求22所述的方法，其中進行晚模式統計計時分析。
26.按照權利要求22所述的方法，其中進行早模式統計計時分析。
27.按照權利要求22所述的方法，其中向電路的每個組件提供獨立的升降統計延遲，並關於電路的一個或多個節點，確定獨立的升降統計到達時間。
28.按照權利要求27所述的方法，其中在電路的一個或多個節點，確定獨立的升降統計要求到達時間、獨立的升降統計遲滯和獨立的升降統計變化中的一個或多個。
29.按照權利要求22所述的方法，其中電路是下述一種或多種組合電路、順序電路、靜態邏輯電路和動態邏輯電路。
30.按照權利要求22所述的方法，其中電路是包含下述一個或多個的順序電路邊沿觸發的鎖存器、主從鎖存器、電平靈敏鎖存器和透明鎖存器。
31.按照權利要求30所述的方法，其中每個計時測試的保護時間是確定的保護時間和統計的保護時間之一。
32.按照權利要求22所述的方法，其中電路包含多個時鐘相位。
33.按照權利要求22所述的方法，其中電路的每個組件的參數延遲模型包括下述一個或多個確定部分、相關部分和獨立的隨機部分。
34.按照權利要求33所述的方法，其中變化源是相關的。
35.按照權利要求33所述的方法，其中變化源是獨立的。
36.按照權利要求22所述的方法，其中參數化延遲模型被預存在表中。
37.按照權利要求22所述的方法，其中參數化延遲模型被預存為延遲等式的係數。
38.按照權利要求22所述的方法，其中通過運行中電路模擬確定參數延遲模型。
39.按照權利要求22所述的方法，其中每個斷言是確定斷言和統計斷言之一。
40.按照權利要求22所述的方法，其中時鐘-邊沿信息是確定的時鐘-邊沿信息和統計的時鐘-邊沿信息之一。
41.按照權利要求22所述的方法，還包括下述步驟a.對於要求到達時間的反向傳播，對計時圖分級；和b.在計時圖的每一級，傳播位於每個節點的一個或多個統計要求到達時間，所述每個統計要求到達時間是一個或多個變化源的概率分布的加權和。
42.按照權利要求41所述的方法，其中通過一次訪問電路的每個節點，確定統計要求到達時間。
43.按照權利要求41所述的方法，其中確定並輸出電路的一個或多個節點的統計遲滯，該統計遲滯呈一個或多個變化源的概率分布的加權和的形式。
44.一種分析電路的計時的系統，包括a.讀取連接表、斷言、參數化延遲模型和變化源列表的裝置；b.建立代表電路的計時圖的裝置，所述計時圖具有一個或多個節點和一條或多個稜邊；c.對於到達時間的正向傳播的裝置，對計時圖分級；d.在計時圖的每一級，傳播位於每個節點的一個或多個統計到達時間的裝置，所述每個統計到達時間是一個或多個變化源的概率分布的加權和。
45.按照權利要求44所述的系統，還包括a.對於要求到達時間的反向傳播對計時圖分級的裝置；和b.在計時圖的每一級，傳播位於每個節點的一個或多個統計要求到達時間的裝置，所述每個統計要求到達時間是一個或多個變化源的概率分布的加權和。
46.一種保存分析電路的計時的方法的計算機存儲器，所述方法包括下述步驟a.輸入連接表、一個或多個斷言、一個或多個參數化延遲模型和一個或多個變化源；b.建立代表電路的計時圖，所述計時圖具有一個或多個節點和一條或多個稜邊；c.對於到達時間的正向傳播對計時圖分級；d.在計時圖的每一級，傳播位於每個節點的一個或多個統計到達時間，所述每個統計到達時間是一個或多個變化源的概率分布的加權和。
47.按照權利要求46所述的計算機存儲器，其中所述方法還包括下述步驟a.對於要求到達時間的反向傳播，對計時圖分級；和b.在計時圖的每一級，傳播位於每個節點的一個或多個統計要求到達時間，所述每個統計要求到達時間是一個或多個變化源的概率分布的加權和。
48.一種由分析電路的計時的處理單元產生的計算機輸出產品，所述處理單元包括下述步驟a.輸入連接表、一個或多個斷言、一個或多個參數化延遲模型和一個或多個變化源；b.建立代表電路的計時圖，所述計時圖具有一個或多個節點和一條或多個稜邊；c.對於到達時間的正向傳播，對計時圖分級；d.在計時圖的每一級，傳播位於每個節點的一個或多個統計到達時間，所述每個統計到達時間是一個或多個變化源的概率分布的加權和。
49.按照權利要求48所述的計算機輸出產品，其中所述方法還包括下述步驟a.對於要求到達時間的反向傳播，對計時圖分級；和b.在計時圖的每一級，傳播位於每個節點的一個或多個統計要求到達時間，所述每個統計要求到達時間是一個或多個變化源的概率分布的加權和。
全文摘要
本發明是一種考慮統計延遲變化，用於數字電路的統計或概率靜態計時分析的系統和方法。每個柵極或導線的延遲被假定為由標稱部分，由每個變化源參數化的相關隨機部分和獨立隨機部分構成。在考慮相關性的同時，以參數化隨機變量的形式傳播到達時間和要求的到達時間。包括早模式和晚模式計時；處理組合和順序電路；適應靜態CMOS以及動態邏輯電路系列。就計時圖的大小和變化源的數目來說，計時分析複雜性是線性的。結果是計時報告，其中以參數化的概率分布的形式，報告諸如到達時間和遲滯之類所有計時量。
文檔編號G06F17/50GK1627302SQ200410078630
公開日2005年6月15日 申請日期2004年9月14日 優先權日2003年9月19日
發明者尚德莫裡·維斯威斯瓦雷 申請人:國際商業機器公司