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

一、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 s = 0 s=0時輸出 b b b，而在 s = 1 s = 1 s=1時輸出 a a a，

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

其在 A A A與 B B B的每一位都相等時，輸出才為1，在HCL中，所有字級的信號宣告均為int，并不指定字的大小，其HCL運算式為

bool eq = (A == B)

??字級的多路復用電路根據輸入位 s s s產生字級 o u t out out，在HCL的運算式為

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

考慮位級輸入位 s s s與字級輸入 A A A與 B B B，在 s = 1 s = 1 s=1時輸出 A A 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 C C為時鐘周期， I I I為完成的指令數， B = C ? I B = C - I B=C?I為插入的氣泡個數，那么有 C P I = 1 + B / I CPI = 1 + B / I CPI=1+B/I平均處罰分別來自于資料加載冒險、控制冒險與回傳等待，