Learning Objectives
- 從波形量出訊號穿過閘的時間
- 找出關鍵路徑，說明它怎麼決定時脈的上限
- 重新排列閘的連接，在功能不變下縮短最長路徑
- 解釋 glitch 怎麼產生、什麼時候有害，並用冗餘項消除靜態危障
- 比較漣波進位與前瞻進位的速度與閘數
電路不是瞬間算完的
到目前為止看真值表，好像輸入一變，輸出就立刻是答案。真實的閘是電晶體，輸出要把線上的電荷充上去或放掉，需要時間。輸入改變到輸出跟著改變的時間，叫傳遞延遲（propagation delay）。
一個閘的延遲很短，但訊號要穿過很多閘。真值表只說最後的答案，不說要等多久，所以兩個真值表完全相同的電路，速度可能差很多。這一課要回答三個問題：要等多久才算算完？等待期間輸出是什麼？怎麼讓它等少一點？
模擬器的延遲是簡化模型。 這裡每個閘的延遲都是整數個「單位」，預設 1。它不是奈秒，也沒有考慮線長、負載與電壓，所以適合比較「哪條路比較長」，不適合換算成真實晶片的速度。
最長的那條路決定一切
一個電路裡有很多條從輸入到輸出的路徑。所有路徑都走完，輸出才算穩定。最慢的那條叫關鍵路徑（critical path）。
這直接決定時脈能跑多快。下一課會學到正反器：電腦每一拍把結果存起來，下一拍再從存好的值開始算。如果時脈週期比關鍵路徑短，存的時候輸出還沒算完，存到的就是錯的值。所以：
時脈週期 > 關鍵路徑的延遲
（真實設計還要再加上正反器本身需要的時間與一點餘裕，第 7 課會提到。）
一個閘多、路徑短的設計可能比閘少、路徑長的設計跑得更快。4 輸入 AND 只用 3 個 AND，有兩種接法。串成一長條的時候，第一個輸入要穿過 3 個閘；接成樹狀的時候，每個輸入都只穿過 2 個閘。閘的數量相同，功能相同，只有最長路徑不同。
下面的工具上半是三個 NOT 串起來，下半是串成一長條的 4 輸入 AND。看波形：輸入一變，每往後一個閘，變化就晚一格。
不必跑模擬也能算關鍵路徑
設計工具不會把所有輸入組合都跑一遍，而是分析線路：每個閘的輸出，要等它最慢的輸入到了之後再過 1 個單位。這種方法叫靜態時序分析（static timing analysis）。下面這段就是它的核心想法：
等待期間，輸出可能是錯的
延遲不只是「晚一點」。兩條長度不同的路徑匯合時，輸出會短暫出現不該有的值，這種現象叫競爭（race），出現的短暫脈衝叫 glitch。
最小的例子是 A·A′。按照布林代數，它永遠是 0。可是 NOT 要花時間：A 從 0 變 1 的瞬間，A 已經是 1，A′ 還沒變，也還是 1。AND 看到兩個 1，輸出就短暫變成 1，等 A′ 變成 0 才掉回去。
它有害嗎？ 要看誰在讀：
- 如果下游是「等穩定之後才看一眼」，脈衝過了就沒事。正反器只在時脈上升那一瞬間看輸入，只要週期夠長，glitch 根本碰不到它。所以同步電路多半不怕 glitch，這正是後面的課都用時脈的原因之一。
- 如果這條線直接當成時脈或重設訊號，脈衝本身就是事件，不能當作沒發生。
更隱蔽的例子是第 4 課的 2 選 1 多工器：Y = S′·D0 + S·D1。令 D0＝D1＝1，不管 S 是多少，Y 都應該是 1。可是 S 由 1 變 0 時，S·D1 馬上變 0，而 S′·D0 還要多等 NOT 的 1 個單位才變 1。中間有一段時間兩項都是 0，Y 掉下去又回來。這種「應該維持不變卻抖了一下」的現象叫靜態危障（static hazard）。反過來 S 由 0 變 1 就沒事：S·D1 先變 1，S′·D0 後變 0，中間兩項同時是 1，輸出不動。
解法是加一個冗餘項：Y = S′·D0 + S·D1 + D0·D1。多出來的項在卡諾圖上就是把兩個相鄰的圈「橋接」起來的那個圈，邏輯上完全不需要，真值表一點都沒變。但是 D0＝D1＝1 時它一直是 1，不管 S 怎麼換，都把輸出撐住。這正好和第 3 課相反：化簡時會把這一項拿掉，現在為了時間上的行為又加回來。最少閘不一定是最好的設計。
下面的工具把這幾件事放在一起。GA 就是 S·S′，它同時接到兩個 D 正反器（第 7 課會細講，這裡只要知道它在 CLK 上升時把 D 存起來）：F1 拿 GA 當時脈，F2 用乾淨的時脈讀 GA。
加法器的關鍵路徑：進位鏈
上一課的漣波進位加法器，最慢的路徑就是進位。全 1 加 1 時，每一位都要等前一位的進位：1111 + 0001，第 0 位的進位傳到第 1 位，再傳到第 2 位，一路到最高位。每一位多經過 AND 和 OR 兩個閘，路徑長度和位元數成正比。64 位元就要等上百個閘。
怎麼不要等？ 觀察每一位，進位只有兩種來源：
- 產生（generate）
g = A·B：這一位自己就會進位 - 傳遞（propagate）
p = A ⊕ B：這一位會把進來的進位傳下去
於是第 2 位的進位不必等第 1 位，可以直接展開：
c2 = g1 + p1·g0 + p1·p0·cin
輸入一到就能算，不用一位一位等，這就是前瞻進位（carry lookahead）。IBM 的 Gerald Rosenberger 在 1957 年就為二進位的前瞻進位加法器申請了專利。
代價是展開式越來越長：位元越多，AND 與 OR 的輸入越多。實務上切成小組，例如每 4 位元一組，組內前瞻，組與組之間再串起來。下面這個工具用程式產生這兩種電路，真的跑閘級模擬。
為什麼時脈要照最壞情況
剛才的工具表格裡也有「隨機 30 組」的統計。隨機輸入的進位鏈通常很短，平均穩定時間遠小於最壞情況。看起來很可惜：大部分時候只要等一小段，時脈卻要照最壞的算。
但是時脈週期是固定的，它不知道這次算的是哪一組數字。只要有一組輸入會來不及，週期就必須留夠，否則就是偶爾算錯，而且很難除錯。
分組前瞻還有一個限制：組與組之間仍然是漣波，所以曲線仍然是一條直線，只是斜率比較小。真實處理器用多層的前瞻，或平行前綴（parallel-prefix）加法器（例如 Brent-Kung、Kogge-Stone），讓延遲隨位元數的對數成長，代價是更多的閘與更複雜的佈線。
確認一下
一個電路有兩條路徑：A 經過 2 個閘、B 經過 7 個閘，每個閘 1 單位。時脈週期最少要多少？
把 8 輸入的 AND 從一長條串法改成樹狀，閘的數量與最長路徑會怎樣？
Y = A·A′ 在這個模擬器裡，A 由 1 變 0 時會有 glitch 嗎？
下面哪一條線最不能有 glitch？
Y = S′·D0 + S·D1 加上冗餘項 D0·D1 之後，真值表怎麼變？
前瞻進位比漣波進位快，為什麼不把所有位元展開成一大組？
重點整理
- 閘有傳遞延遲，延遲沿著路徑累加。真值表看不出快慢。
- 最長的路徑是關鍵路徑，時脈週期必須比它長。同樣的閘，換個接法就可能縮短它。
- 路徑長度不同的訊號匯合會產生 glitch。下游如果只在時脈來時讀一次就沒事；接到時脈或重設腳就可能出事。
- 靜態危障可以加冗餘項消除，代價是多用閘。
- 漣波進位的關鍵路徑和位元數成正比；前瞻進位用 generate 與 propagate 提前算出進位，速度變快，閘變多。
這一課一直提到「把結果存起來」，可是目前為止的電路都記不住東西。下一課就來做會記憶的電路：栓鎖與正反器。