計算機系統——處理器體系結構

一、Y86-64指令集體系架構
  指令集體系架構定義了狀態單元、指令集、編碼、規範及異常事件處理。

1.1 Y86-64指令集
  Y86-64是Intel x86-64得一個簡單版本。
  Y86-64處理器的狀態包括：
  -程式暫存器，除了%r15的64位元暫存器；
  -條件碼，由算術或邏輯指令產生的標識，包括ZF、SF與OF；
  -程式計數器【Program Counter，PC】記錄下一條指令的地址；
  -程式狀態【Program Status，Stat】指示程式的正常操作或錯誤狀態；
  -記憶體，按位元組編址的儲存陣列，按小端順序儲存。
  在Y86-64處理器的狀態之上，規定了一系列的指令集，包括
  -處理器停止指令halt，無運算元；
  -空指令nop，無運算元；
  -暫存器傳送指令rrmovq，運算元為暫存器；
  -立即數暫存器傳送指令irmovq，運算元為立即數與暫存器；
  -暫存器記憶體傳送指令rmmovq，運算元為暫存器與地址；
  -記憶體暫存器傳送指令mrmovq，運算元為寄地址與暫存器；
  -運算指令OPq，運算元為暫存器；
  -跳轉指令jC，運算元為地址；
  -條件傳送指令cmovC，運算元為暫存器；
  -呼叫指令call，運算元為地址；
  -返回指令ret，無運算元；
  -壓棧指令pushq，運算元為暫存器；
  -彈棧指令popq，運算元為暫存器。

1.2 Y86-64指令編碼
  指令需要1到10個位元組不等，其第一個位元組表徵著主要功能，其高4位元為指令碼，低4位元為功能碼，例如addq編碼為60，subq編碼為61，其均是程式碼號為0x0110的運算指令；jmp編碼為70，jle編碼為71，其均是程式碼號為0x0111的跳轉指令。
  在指令的運算元中包含暫存器，每一個程式暫存器都有一個與之相對應的0x0到0xE之間的識別符號，形如

  在運算指令中，加運算的編碼為60，減運算的編碼為61，和運算的編碼為62，互斥或運算的編碼為63。加法指令的通用格式為

addq rA, rB

當rA，rB取%rax與%rsi時，其暫存器編碼分別為0與6，那麼指令編碼表示為60 06。

  在傳送指令中，暫存器傳送指令的指令碼為2，立即數暫存器傳送指令的指令碼為3，暫存器記憶體傳送指令的指令碼為4，記憶體暫存器傳送指令的指令碼為5；運算元中的立即數或記憶體地址均佔8個位元組，例如

irmovq $0xabcd, %rax

其編碼為30 f2 cd ab 00 00 00 00 00 00，其中，立即數暫存器傳送指令的運算元高4位元為0xF，即不使用暫存器。

  在跳轉指令中，跳轉的運算元為8位元組的目的地址，其對目的地址進行絕對編碼，相對於x86-64的相對編碼。

  在條件指令中，無條件的功能碼為0，小於等於為1，小於為2，等於為3，不等於為4，大於等於為5，大於為6；其與傳送指令型別結合，形成條件傳送指令；或與跳轉指令結合，形成條件跳轉指令。

  在棧指令中，Y86-64的程式棧與x86-64相似，由%rsp指向棧頂，棧操作包括壓棧與彈棧，編碼分別為A0與B0，假設對%rax進行棧操作，那麼壓棧與彈棧程式碼為

pushq %rax
popq %rax

其編碼為a0 0f與b0 0f。

  在呼叫指令中，呼叫指令編碼為80，呼叫的地址運算元使用絕對編碼，返回指令的編碼為90。

  此外，還有空指令編碼為10與停止指令00。

  在狀態條件中，包括正常操作，編碼為1；遇到停止指令，編碼為2；遇到錯誤地址，編碼為3；遇到無效指令，編碼為4，用於stat的賦值。當stat = 1時，程式繼續執行，否則程式停止。

1.3 Y86-64程式
  給定C函數程式碼如下

long sum(long *start, long count){
    long sum = 0;
    while (count){
        sum += *start;
        start++;
        count--;
    }
    return sum;
}

其x86-64的組合程式碼為

sum:
	movl	$0, %eax
	jmp	.L2
.L3:
	addq	(%rdi), %rax
	addq	$8, %rdi
	subq	$1, %rsi
.L2:
	testq	%rsi, %rsi
	jne	.L3
	rep ret

其Y86-64的組合程式碼為

sum:
	irmovq $8, %r8
	irmovq $1, %r9
	xorq %rax, %rax
	andq %rsi, %rsi
	jmp test
loop:
	mrmovq (%rdi), %r10
	addq %r10, %rax
	addq %r8, %rdi
	subq %r9, %rsi
test:
	jne loop
	ret

可以看出，x86-64與Y86-64遵循通用的模式，但是依然有一定的不同：
  -Y86-64的算術指令不允許使用立即數，必須將立即數載入到暫存器；
  -Y86-64不允許直接對記憶體的值進行操作，需要先載入到暫存器；
  -Y86-64必須隱式的設定條件碼。

---

二、邏輯設計與硬體控制

2.1 位級組合電路與HCL布林表示式
  將很多的邏輯閘組合成一個網，構建的計算塊稱為組合電路。硬體描述語言【Hardware Description Language，HDL】用於描述電路的結構，形成了組合電路的表示式。
  考慮同或網路，形如

其HCL表示式為

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

其實現了位級相等的判斷。
  一種簡單而有用的組合電路是多路複用器【multiplexor，MUX】，其可以根據輸入控制訊號的值，從一組不同的資料訊號中選出一個，典型的形如

其HCL表示式為

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

其在$s=0$時輸出$b$，而在$s=1$時輸出$a$。

2.2 字級組合電路與HCL整數表示式
  通過將邏輯閘組合成更大的網，可以構造出能計算更復雜函數的組合電路。執行字級計算的組合電路根據輸入字的各個位，用邏輯閘計算輸出字的各個位。例如判斷64位元字$A$與$B$是否相等，形如

其在$A$與$B$的每一位都相等時，輸出才為1。在HCL中，所有字級的訊號宣告均為int，並不指定字的大小。其HCL表示式為

bool eq = (A == B)

  字級的多路複用電路根據輸入位$s$產生字級$out$，在HCL的表示式為

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

考慮位級輸入位$s$與字級輸入$A$與$B$，在$s=1$時輸出$A$，其組合電路為

其HCL可以描述為

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

其中，第二個表示式為1，表明前面沒有情況被選中的情況下的預設情況。
  處理器的算術邏輯單元【arithmetic and logic unit，ALU】是一種重要的組合電路，其抽象組合電路為

其HCL可以描述為

word Out = [
	(s == 0): X + Y;
	(s == 1): X - Y;
	(s == 2): X & Y;
	(s == 3): X ^ Y;
]

2.3 儲存器與時鐘
  為了引入按位元儲存資訊的裝置，需要使用時序電路，由時鐘週期訊號控制了載入時間。
  時鐘暫存器，儲存時鐘訊號控制暫存器載入值；隨機存取儲存器，簡稱記憶體，用地址選擇讀寫字，包括虛擬記憶體系統與程式暫存器檔案。
  暫存器檔案有兩個讀埠、一個寫埠，允許同時進行多個讀和寫操作。讀埠包括地址輸入scrA和scrB，在讀入地址輸入後從資料輸出valA和valB輸出資料。寫埠包括地址輸出dstW與資料輸入valW，暫存器檔案需要的地址為暫存器標識。當輸入地址無效時，暫存器檔案的error標識會置為1。

---

三、Y86-64的順序實現
  Y86-64的順序【Sequential，SEQ】處理器在時鐘週期上處理完整指令的所有步驟。

3.1 SEQ處理階段
  SEQ處理一條指令可以分為如下階段：
  -取指：從記憶體中讀取指令位元組；
  -譯碼：從程式暫存器中讀入操作；
  -執行：算術邏輯單元執行計算；
  -訪存：從記憶體中讀出或寫入資料；
  -寫回：更新程式暫存器；
  -更新：將PC設定為下一指令的地址。
處理器無限迴圈上述的執行上述各個階段，並在發生異常時停止。

  算術指令OPq rA, rB的編碼為6Fn rArB。其中，Fn表示功能碼，rA表示暫存器A的識別符號，rB表示暫存器B的識別符號，那麼該指令的階段可以描述為：

icode:ifun = M[PC]
rA:rB = M[PC + 1]
valP = PC + 2
valA = R[rA]
valB = R[rB]
valE = valB OP valA
set CC
R[rB] = valE
PC = valP

  暫存器記憶體移動指令rmmovq rA, Dst(rB)的編碼為40 rArB Dst0 Dst1 Dst2 Dst3 Dst4 Dst5 Dst6 Dst7。其中，Dst表示目標地址，長度為8Byte，那麼該指令的階段可以描述為：

icode:ifun = M[PC]
rA:rB = M[PC + 1]
valC = M[PC + 2]
valP = PC + 10
valA = R[rA]
valB = R[rB]
valE = valB + valC
M[valE] = valA
PC = valP

  彈棧指令popq rA的編碼為b0 rAf。該指令的階段可以描述為：

icode:ifun = M[PC]
rA:rB = M[PC + 1]
valP = PC + 2
valA = R[%rsp]
valB = R[%rsp]
valE = valB + 8
valM = M[valA];
R[%rsp] = valE
R[rA] = valM
PC = valP

  條件傳送指令cmovC rA, rB的編碼為2fn rArB。該指令的階段可以描述為：

icode:ifun = M[PC]
rA:rB = M[PC + 1]
valP = PC + 2
valA = R[rA]
valB = 0x0
valE = valA + valB
if !Cond(CC, ifun)
	rB = 0xF
R[rB] = valE
PC = valP

條件傳送指令在不滿足條件時取埠值為0xF來取消資料寫入暫存器。

  條件跳轉指令jC Dst的編碼為7fn Dst0 Dst1 Dst2 Dst3 Dst4 Dst5 Dst6 Dst7。該指令的階段可以描述為：

icode:ifun = M[PC]
valC = M[PC + 1]
valP = PC + 9
Cnd = Cond(CC, ifun)
PC = Cnd? valC : valP

其計算下一地址與目的地址，並根據條件碼與分支條件做出選擇。

  呼叫指令call Dse的編碼為80 Dst0 Dst1 Dst2 Dst3 Dst4 Dst5 Dst6 Dst7。該指令的階段可以描述為：

icode:ifun = M[PC]
valC = M[PC + 1]
valP = PC + 9
valB = R[%rsp]
valE = valB + -0x8
M[valE] = valP
R[%rsp] = valE
PC = valC

  返回指令ret的編碼為90。該指令的階段可以描述為：

icode:ifun = M[PC]
valA = R[%rsp]
valB = R[%rsp]
valE = valB + 8
valM = M[valA]
R[%rsp] = valE
PC = valM

3.2 SEQ取指控制邏輯
  取指階段的硬體結構如下

其中，指令的最高位位元組Split產生了指令功能碼icode與ifun，instr_valid用於檢測指令的合法性，need_valC與need_regids則根據指令檢查暫存器指示位元組與常數；Align根據need_valC與need_regids選擇不同位輸出到rA、rB或valC；valP用於產生新的PC值。
  取指控制邏輯的HCL描述為

int icode = [
	imem_error: INOP;
	1: imem_icode;
];

int ifun = [
	imem_error: FNONE;
	1: imem_ifun;
];

bool need_regids = icode in {
	IRRMOVQ, IOPQ, IPUSHQ, IPOPQ, IIRMOVQ, IRMMOVQ, IMRMOVQ
};

bool instr_valid = icode in {
	INOP, IHALT, IRRMOVQ, IIRMOVQ. IRMMOVQ, IMRMOVQ, IOPQ, IJXX, ICALL, IRENT, IPUSHQ, IPOPQ
};

3.3 SEQ譯碼寫回控制邏輯
  譯碼與寫回階段均建立在暫存器之上，硬體結構如下

暫存器檔案包括讀埠A與B，及寫埠E與M，通過地址srcA、srcB、dstM、dstE控制；訊號值Cnd由執行階段計算出，標明瞭是否滿足條件轉移。
  譯碼邏輯控制的HCL描述為

int srcA = [
	icode in {IRRMOVQ, IRMMOVQ, IOPQ, IPUSHQ}: rA;
	icode in {IPOPQ, IRET}: RRSP;
	1: RNONE;
];

  寫回邏輯控制的HCL描述為

int dstE = [
	icode in {IRRMOVQ} && Cnd: rB;
	icode in {IRRMOVQ, IOPQ} :rB;
	icode in {IPUSH, IPOPQ, ICALL, IRET}: RRSP;
	1: RNONE;
];

3.4 SEQ執行控制邏輯
  執行階段的硬體結構如下

其中，ALU單元用於運算並生成條件碼；CC是包含三個條件碼的暫存器；cond用於計算條件跳轉或轉移的標識。
  執行邏輯控制的HCL描述為

int aluA = [
	icode in {IRRMOVQ, IOPQ}: valA;
	icode in {IIRMOVQ, IRMMOVQ, IMRMOVQ}: valC;
	icode in {ICALL, IPUSHQ}: -8;
	icode in {IRET, IPOPQ}: 8;
];

int alufun = [
	icode == IOPQ : ifun;
	1 : ALUADD;
]; 

3.5 SEQ訪存控制邏輯
  訪存階段的硬體結構如下

其中，狀態碼stat描述了當前指令的執行情況。
  訪存邏輯控制的HCL描述為

int mem_addr = [
	icode in {IRMMOVQ, IPUSHQ, ICALL, IMRMOVQ}: valE;
	icode in {IPOPQ, IRET}: valA;
];

bool mem_read = icode in {
	IMRMOVQ, IMRMOVQ, IPOPQ, IRET
}

3.6 SEQ更新控制邏輯
  更新階段的硬體結構如下

其根據指令選擇新的PC地址。
  更新邏輯控制的HCL描述為

int new_pc = [
	icode == ICALL : valC;
	icode == IJXX && Cnd : valC;
	icode == IRET : valM;
	1 : valP;
];

---

四、Y86-64的流水線實現
4.1 流水線系統
  在SEQ結構中，指令的執行按照階段順序發生，一次只能處理一個操作，這導致硬體單元在一個時鐘週期內的僅一部分被使用，且時鐘也必須足夠慢。為此，使用流水線結構提高系統的吞吐量與輕微的延遲。
  在流水線系統中，在順序系統中插入暫存器，可以使得在同一時間，不同指令的不同階段進行運算，可以顯著的提高吞吐量，但是也存在如下侷限：
  -當個階段具有不一致的延遲時，流水線的吞吐量受到花費時間最長的階段限制；
  -當嘗試加深流水線時，將結果載入暫存器的時間會顯著影響效能；
  -程式中普遍具有操作依賴前一個操作的結果，稱為資料相關，如果結果沒有及時反饋，流水線將改變系統的行為，形成資料錯誤的資料冒險或跳轉錯誤的控制冒險。

4.2 流水線結構的實現
  在SEQ結構中，將PC更新階段移動到時鐘週期開始，在某一指令的更新階段完成併到達取指階段，得到下一條指令地址的同時進入下一條指令的更新階段，使得處理器成為流水線系統，稱為SEQ+ 結構。在SEQ+結構中，PC將不再儲存在暫存器中，而由其他資訊直接決定。那麼SEQ+各階段為：
  -取指：選擇PC，讀取指令，並計算新的PC值，標記為F；
  -譯碼：從程式暫存器中讀入操作，標記為D；
  -執行：算術邏輯單元執行計算，標記為E；
  -訪存：從記憶體中讀出或寫入資料，標記為M；
  -寫回：更新程式暫存器，標記W。

  如果在各個階段的硬體之間新增流水線暫存器，儲存指令執行的中間值，使得訊號重新排列，稱為PIPE- 結構。由於資料相關，在各個階段之間需要形成反饋路徑，包括：
  -PC值預測的備選值需要前一指令決定；
  -分支資訊跳轉由前一指令決定；
  -暫存器的讀取需要暫存器及時更新，由前一指令決定；
  -返回點由記憶體中讀取需要記憶體的即使更新，由前一指令決定。
在當前指令完成取值後，沒有足夠的時間決定下一指令的地址，會進行預測。預測的策略包括：
  -非轉移指令，預測為valP，永久可靠；
  -呼叫指令與無條件轉移指令，預測為valC，永久可靠；
  -條件轉移指令，預測為valC，正確率大約為60%；
  -返回指令，不預測，暫停等待ret指令到達寫回階段。
當條件轉移預測錯誤時需要進行還原，需要存取失敗的PC。

4.3 流水線結構的高階實現
  在PIPE-結構中，依然存在著資料冒險和控制冒險的問題。如果使用動態插入氣泡暫停流水線，會降低流水線的速度。
  一種解決資料冒險的方法是資料轉發，其將指令生成的值直接傳遞到譯碼階段。考慮如下程式碼

0x00: irmovq $10, %rdx
0x0a: irmovq $3, %rax
0x14: nop
0x15: nop
0x16: addq %rdx, %eax
0x18: halt

那麼流水線執行階段形如

其中，第6週期執行的程式碼為

W:
	W_dstE = %rax
	W_valE = 3
D:
	src_A = %rdx
	src_B = %rax

0x00的寫回對%rax寫的同時，0x16的譯碼階段對%rax讀，為此，在%rax儲存到W暫存器的同時轉發提供給譯碼階段，形成旁路路徑。在有多重轉發發生時，使用各個指令的各個階段中，階段最早從流水線階段獲取的匹配值。當使用資料轉發依然可能出現冒險時，將指令暫停在取指和譯碼階段，並在硬體的執行階段持續注入氣泡，稱為載入/使用冒險。使用資料轉發的流水線HCL描述為

int d_valA = [
	D_icode in {ICALL, IJXX}: D_valP;
	d_srcA == e_dstE : e_valE;
	d_srcA == M_dstM : m_valM;
	d_srcA == M_dstE : M_valE;
	d_srcA == M_dstM : W_valM;
	d_srcA == W_dstE : W_valE;
	1 : d_valA
]

  在控制冒險中，僅取出預測分支的兩條指令，使得其只進行到譯碼階段，並在預測錯誤時用氣泡代替原指令的剩餘階段，此時不會對任何可見狀態產生影響。考慮如下程式碼

0x00: xorq %rax, %rax
0x02: jne 0x16
0x0b: irmovq $1, %rax
0x15: halt
0x16: irmovq $2, %rdx
0x20: irmovq $3, %rbx

假設其預測錯誤，那麼流水線執行階段形如

其在第4週期內，0x02的執行階段得到了預測錯誤的情況，並將0x16與0x20指令的第5週期及後續階段置為氣泡。即在預測錯誤的週期中，保持取值、訪存與寫回階段的硬體執行不變，而在譯碼與執行階段的硬體注入氣泡。
  在返回指令中，返回指令後一指令將被暫停在取指階段，並不斷地注入氣泡，直到返回指令完成訪存階段，得到了返回地址，再釋放暫停，後一指令完成取指階段。
  在流水線的資料冒險、控制冒險、返回指令三種特殊情況中，分別描述了暫停與氣泡的使用情況，其HCL描述為

bool F_stall = E_icode in {IMRMOVQ, IPOPQ} && E_dstM in {d_srcA, d_srcB} ||
				IRET in {D_icode, E_icode, M_icode};

boll D_stall = E_icode in {IMRMOVQ, IPOPQ} && E_dstM in {d_srcA, d_srcB};

bool D_bubble = (E_icode == IJXX && !e_Cnd) || IRET in {D_icode, E_icode, M_icode};

bool E_bubble = (E_icode == IJXX && !e_Cnd) || E_icode in { IMRMOVQ, IPOPQ } &&
				E_dstM in { d_srcA, d_srcB };

  此外，還可能發生兩種組合特殊情況：控制冒險分支出現返回指令與資料冒險出現返回指令。
  在控制冒險與返回指令同時發生時，控制冒險會在指令進入執行階段發現預測錯誤，並在訪存階段向錯誤預測的執行階段與譯碼階段使用氣泡替換原指令；返回指令在位於譯碼階段時，其會將其下一指令的取指暫存器暫停，並在執行階段向無指令的譯碼階段插入氣泡。組合來看控制冒險在發現預測錯誤的下一週期內，分別有：訪存階段硬體執行條件跳轉指令，執行階段硬體執行返回指令，譯碼階段為氣泡，取指階段將返回指令下一指令暫停取指暫存器。在控制冒險的機制下，執行階段與譯碼階段會被注入氣泡，由此使錯誤預測的返回指令取消；同時正確分支的指令進入取指階段，而被暫停的錯誤指令未被執行，也被取消掉。故這種特殊情況的處理是正確的。
  在資料冒險與返回指令同時發生時，位於譯碼階段的返回指令將要使用位於執行階段的運算的目的暫存器，產生資料冒險。當譯碼階段對執行階段產生資料冒險時，會將指令暫停在譯碼階段，並在執行階段插入氣泡，直到前一運算指令將運算結果儲存，釋放暫存器，再釋放暫停。組合來看，運算完成執行階段，進入下一週期內有：訪存階段硬體為返回指令機制下暫停的訪存暫存器，譯碼階段硬體或為返回機制的氣泡，或為載入/使用冒險機制的返回指令使用暫停的取指暫存器，運算階段為載入/使用冒險機制的氣泡。實際上，期望返回指令暫停在譯碼階段，這種情況下流水線機制需要特殊處理。
  在完成所有的處理後，形成PIPE結構處理器，形如

---

五、處理器的效能

5.1 例外處理
  處理器中很多事情都會導致異常控制流，在Y86-64中，包括：
  -halt指令；
  -非法指令碼與功能碼組合的指令；
  -非法地址的存取。
在處理器流水線中，當指令導致以嘗試，流水線控制邏輯必須禁止條件碼暫存器與資料記憶體的更新。流水線暫存器中增加了狀態列位，以保證維護異常。
  取指、訪存與寫回階段的stat的HCL描述分別為

int f_stat = [
	imem_error : SADR;
	!instr_valid : SINS;
	f_icode == IHALT : SHLT;
	1 : SAOK;
];

int m_stat = [
	dmem_error : SADR;
	1 : M_stat
];

int Stat = [
	W_stat == SBUB : SAOK;
	1 : W_stat;
]

5.2 效能評估
  通過計算指令所需要的平均時鐘週期數的估計來量化處理器的效能，稱為平均執行週期數【Cycle Per Instruction，CPI】。PIPE在每週期都取一條新指令，但又存在停頓或取消分支的情況，故其CPI略大於1。考慮$C$為時鐘週期，$I$為完成的指令數，$B=C-I$為插入的氣泡個數，那麼有$$CPI=1+B/I$$平均處罰分別來自於資料載入冒險、控制冒險與返回等待。