邏輯設計與 HCL (Logic Design & HCL)

Overview Table

數位系統三要素與 HCL 定位 (p.408)

現代電路以電壓表示位元:邏輯 1 約 1.0 V(高電壓),邏輯 0 約 0.0 V(低電壓)。實作數位系統需要三種元件:

• Combinational logic(組合邏輯):對位元計算函數
• Memory elements(記憶元件):儲存位元
• Clock signals(時脈訊號):規範記憶元件「何時」載入新值

4.2.1 邏輯閘 (Logic Gates) (p.409)

邏輯閘是數位電路的基本計算元件,輸出等於輸入位元值的某個 Boolean 函數(Figure 4.9)。

   AND                 OR                  NOT
a ──┐                a ──┐
    ├D──── out           ├)>─── out      a ──▷o── out
b ──┘                b ──┘
out = a && b         out = a || b        out = !a

• HCL 採用 C 的邏輯運算子 &&、||、!,而不是位元運算子 &、|、~——因為邏輯閘操作的是單一位元,不是整個字組
• AND/OR 閘常見 n-way 版本(n > 2),HCL 仍以二元運算子串接:三輸入 AND 寫作 a && b && c
• 邏輯閘永遠處於作用狀態(always active):任一輸入改變,經過一小段延遲後輸出隨之改變

4.2.2 組合電路與 HCL Boolean 運算式 (p.410-411)

把多個邏輯閘接成網路即得組合電路 (combinational circuit)。建構網路有三條限制:

1. 每個邏輯閘輸入必須恰好接到下列之一:primary input(系統輸入)、某記憶元件的輸出、或某邏輯閘的輸出
2. 兩個以上邏輯閘的輸出不可相接——否則可能把導線驅動到不同電壓,造成無效電壓或電路故障
3. 網路必須無環 (acyclic)——迴圈會使電路計算的函數產生歧義

Bit equal(位元相等測試)(Figure 4.10):兩輸入同為 1(上方 AND)或同為 0(下方 AND)時輸出 1:

a ──┬───────────┤AND├──┐
    │     ┌─────┤   │  │
b ──┼─────┤            ├──[OR]── eq
    │     └─!───┤   │  │
    └────!──────┤AND├──┘

eq = (a && b) || (!a && !b)

bool eq = (a && b) || (!a && !b);

HCL 的 = 只是幫運算式取名字——不像 C 那樣「執行計算並把結果存入某記憶體位置」。

Bit MUX(單一位元多工器)(Figure 4.11):multiplexor 依控制訊號值,從一組資料訊號中選出一個。此處 s=1 輸出 a;s=0 輸出 b。上方 AND 閘在 s=0 時放行 b(其另一輸入為 !s),下方 AND 閘在 s=1 時放行 a:

s ──┬──!───┤AND├──┐
b ──┼──────┤   │  │
    │             ├──[OR]── out
    │   ┌──┤AND├──┘
a ──┴───┴──┘

out = (s && a) || (!s && b)

bool out = (s && a) || (!s && b);

組合電路 vs. C 邏輯運算式的三大差異(p.411):

4.2.3 字組級組合電路與 HCL 整數運算式 (p.412-416)

實務電路多操作資料字組 (data words)——代表整數或某種控制樣式的一組位元訊號。處理器設計中字組寬度介於 4 到 64 位元(整數、位址、指令碼、暫存器識別碼)。

• HCL 中字組級訊號一律宣告為 int,不指定位寬(為求簡化;完整 HDL 中每個字組都可宣告特定位元數)
• 繪圖慣例(p.413):中等粗細實線 = 承載字組各位元的一組導線;虛線 = 單一位元訊號

字組相等測試(Figure 4.12):以 64 個 bit-equal 電路逐位比較,輸出再以 AND 閘合併——若且唯若 A 的每一位元等於 B 的對應位元時輸出 1:

b63,a63 ─[Bit equal]─ eq63 ─┐
b62,a62 ─[Bit equal]─ eq62 ─┤             B ══╗
   ...        ...           ├─[AND]── Eq      ║[ = ]---→ Eq(單位元,虛線)
b1, a1  ─[Bit equal]─ eq1  ─┤             A ══╝
b0, a0  ─[Bit equal]─ eq0  ─┘
(a) 位元級實作                 (b) 字組級抽象

bool Eq = (A == B);

語法沿用 C 慣例:= 為賦值(命名),== 為相等運算子;引數 A、B 型別為 int。

字組級 MUX(Figure 4.13):由 64 個結構類似 bit MUX 的子電路組成;實作上 !s 只產生一次、在每個位元位置重複使用,以減少反相器 (inverter) 數量。

Case expression(HCL 的多工器描述)(p.414)

多工功能在 HCL 以 case expression 描述,一般形式:

[
    select_1 : expr_1;
    select_2 : expr_2;
       ...
    select_k : expr_k;
]

• 每個 case 由 Boolean 選擇運算式 select_i(何時選此 case)與整數結果運算式 expr_i(結果值)組成
• 不要求各選擇條件互斥(與 C 的 switch 不同):邏輯上依序求值,選第一個結果為 1 的 case
• 最後一個 case 的選擇運算式寫 1,即 HCL 的 default case 寫法——幾乎所有 case expression 都如此結尾
• 選擇運算式可為任意 Boolean 運算式、case 數量不限

字組級 MUX 的 HCL:

word Out = [
    s: A;
    1: B;
];

4-way MUX(Figure 4.14):以 s1 s0 兩控制位元(視為 2 位元二進位數)從 A、B、C、D 選一:

s1 ─┐
s0 ─┤
D ──┤
C ──┤ MUX4 ──→ Out4
B ──┤
A ──┘

word Out4 = [
    !s1 && !s0 : A; # 00
    !s1        : B; # 01
    !s0        : C; # 10
    1          : D; # 11
];

• # 之後到行尾為註解
• 因為「只選第一個符合者」,選擇運算式可化簡:第二條寫 !s1 即可(不必寫完整的 !s1 && s0,因為 s1=0 的另一種可能已被第一條攔截);同理第三條寫 !s0、第四條寫 1

MIN3(三字組取最小值)(p.415):

word Min3 = [
    A <= B && A <= C : A;
    B <= A && B <= C : B;
    1                : C;
];

利用循序求值特性,第二條可化簡為 B <= C : B;(全式只需 3 次比較)——第一條沒中就代表 A 不是最小值(Practice Problem 4.11)。

ALU(arithmetic/logic unit)(Figure 4.15,p.416):重要的組合電路,三個輸入——兩個資料輸入 A、B 與一個控制輸入;控制值決定執行哪種算術/邏輯運算:

      0             1             2             3
Y ──┤A     │   Y ──┤A     │   Y ──┤A     │   Y ──┤A     │
    │ ALU  ├X+Y    │ ALU  ├X-Y    │ ALU  ├X&Y    │ ALU  ├X^Y
X ──┤B     │   X ──┤B     │   X ──┤B     │   X ──┤B     │

• 四種運算恰好對應 Y86-64 的四個整數運算指令(addq/subq/andq/xorq),控制值 = 其 function code(ifun)(見 04-Processor-Architecture/01-Y86-64-ISA)
• 減法運算元順序:A 輸入被 B 輸入減(A 接 Y、B 接 X,輸出 X − Y)——刻意配合 subq rA, rB(rB ← rB − rA)的引數順序

4.2.4 集合成員測試 (Set Membership) (p.416-417)

處理器設計常需把一個訊號與多個可能匹配值比較(典型:判斷 icode 是否屬於某類指令碼)。例:由 2 位元訊號 code 產生 4-way MUX 的控制位元 s1、s0:

code ──►[Control]──► s1
                 └─► s0  ──► 控制 MUX4 選 A/B/C/D

用相等測試表達:

bool s1 = code == 2 || code == 3;
bool s0 = code == 1 || code == 3;

以集合成員測試改寫更精簡(s1 = 1 當 code ∈ {2,3};s0 = 1 當 code ∈ {1,3}):

bool s1 = code in { 2, 3 };
bool s0 = code in { 1, 3 };

一般形式:iexpr in { iexpr_1, iexpr_2, ..., iexpr_k }——被測值與候選匹配值皆為整數運算式。

4.2.5 記憶與時脈 (Memory and Clocking) (p.417-420)

組合電路不儲存任何資訊,只是對輸入訊號產生對應的函數輸出。要建立循序電路 (sequential circuit)——有狀態、並對狀態進行運算的系統——必須引入儲存位元的裝置。所有儲存裝置由單一 clock(週期訊號)控制新值的載入時機。兩類記憶裝置:

Clocked register 的運作(Figure 4.16)

        State = x                  rising          State = y
Input=y ──►[ x ]──► Output=x      ─clock─►  ──►[ y ]──► Output=y
(clock 低電位期間:輸出鎖定為 x)            (上升緣:輸入 y 載入成新狀態)

• clock 為低電位時,即使前級組合邏輯已在輸入端算出新值 y,輸出仍固定為目前狀態 x
• clock 上升緣 (rising edge):輸入訊號被載入為暫存器的新狀態 y,成為新輸出,直到下一個上升緣
• 關鍵:暫存器是電路中不同組合邏輯區塊之間的屏障 (barrier)——值每個 clock cycle 只在上升緣從暫存器輸入傳到輸出一次

Register file(暫存器檔案)(p.418-419)

         valA ◄──┐
srcA ───────► A  │
                 │  Register    W ◄─── dstW(寫入位址)
         valB ◄──┤    file        ◄─── valW(寫入資料)
srcB ───────► B  │
                 └────┬────
                    clock
  讀取埠 A、B(位址 srcA/srcB,輸出 valA/valB);寫入埠 W

• 多埠 (multiported) RAM:2 個讀取埠 + 1 個寫入埠,可同時讀兩個程式暫存器並更新第三個
• 位址即 register ID(Figure 4.4 的編碼);例如 srcA = 3 會讀出 %rbx,值出現在 valA
• 讀取像組合邏輯:設定 srcA/srcB 後經一段延遲,對應值出現在輸出——雖然 register file 有內部儲存、並非組合電路
• 寫入由 clock 控制:每次 clock 上升,valW 的值被寫入 dstW 指定的程式暫存器;dstW 為特殊 ID 0xF 時不寫入任何暫存器

Data memory(資料記憶體)(p.419-420)

             ┌──────────┐──► data out
 error ◄─────┤          │
 read  ─────►│   Data   │
 write ─────►│  memory  │◄── clock
             └──────────┘
         address ▲   ▲ data in

• 單一 address 輸入、data in(寫入資料)、data out(讀出資料)
• 讀取:給定 address、write 設為 0,延遲後該位址儲存的值出現在 data out——行為如組合邏輯
• 寫入:設定 address、data in、write=1,clock 作動時更新該位置(前提是位址有效)
• error 訊號:位址超出範圍時為 1、否則為 0;由組合邏輯產生——邊界檢查純粹是位址輸入的函數,不涉及狀態儲存
• 處理器另有一個唯讀的 instruction memory 讀取指令;大多數實際系統把兩者合併為單一記憶體、開兩個埠(一讀指令、一讀寫資料)(p.420)

Exam/Test Patterns

Related Notes

• 04-Processor-Architecture/01-Y86-64-ISA
• 04-Processor-Architecture/03-Sequential-SEQ-Implementation
• 04-Processor-Architecture/04-Pipelining-Principles
• 04-Processor-Architecture/05-Pipelined-PIPE-Implementation-and-Hazards
• 02-Information-Representation/01-Information-Storage-and-Bits
• 06-Memory-Hierarchy/02-Locality-and-Memory-Hierarchy