CS:APP Architecture Lab
環境準備
安裝
一樣到官網安裝壓縮檔: Lab Assignments
Lab PDF 檔
環境調整
先將檔案解壓縮
安裝作業需要套件
接下來稍微麻煩一些，因為編譯器版本更新，因此我們需要做以下的改動
- 修改
sim/Makefile
- 修改
misc/Makefile
- 修改
pipe/Makefile 和 seq/Makefile
- 將上面四個
Makefile 的 GUIMODE, TKLIBS, TKINC 註解掉
修改完成後編譯就可以成功了。
Part A
第 A 部份希望你用 Y86-64 組合語言寫三個函式，三個都是鍊結串列的操作。下圖是串列的結構體。移動到 sim/misc 目錄下。
可以參考 CS:APP 中的圖 4-8 ，提供了簡單的框架。
sum_list
實現走訪整個鍊結串列，累加每個節點的值。
創建 sum_list.ys 檔。
ls -> next: 因為結構體對齊是 8 ，因此指向下一個節點是加 8- while 迴圈使用 jump-to-middle，可參考CS:APP 第三章 3.6.7 節
輸入下面命令，rax 為 0xcba 代表成功。
rsum_list
一樣是求和函式，只是這題是用遞迴的方式。
創建 rsum_list.ys 檔。
- 進入遞迴之前要先將暫存的
rsi push 進堆疊，等到回來之後才 pop 出來。
輸入下面命令，rax 為 0xcba 代表成功。
copy_block
將 src 陣列裡的元素抓出來給 dest 陣列，並將每個元素做 XOR 操作後回傳。
創建 rsum_list.ys 檔。
- 輸入參數的順序分別是:
rdi, rsi, rdx
- 設置常數給暫存器
r8, r9，用來做加法操作
- 第一次的迴圈的判斷條件為
andq 操作，而之後則是在 subq 之後便會設置條件碼(CC) ZF 位，表示檢查操作後是否為 0
輸入下面命令，rax 為 0xcba 代表成功。
Part B
這部份希望實作 iaddq 指令，將立即數和暫存器相加。整合了 CSAPP 裡的 4.51 和 4.52 題
4.51 Practice Problem 4.3 introduced the iaddq instruction to add immediate data to a register. Describe the computations performed to implement this instruction. Use the computations for irmovq and OPq (Figure 4.18) as a guide.
4.52 The file seq-full.hcl contains the HCL description for SEQ, along with the declaration of a constant IIADDQ having hexadecimal value C, the instruction code for iaddq. Modify the HCL descriptions of the control logic blocks to implement the iaddq instruction, as described in Practice Problem 4.3 and Problem 4.51. See the lab material for directions on how to generate a simulator for your solution and how to test it.
我們要根據 iaddq 指令在流水線每個階段的行為，修改 HCL 描述，下圖是 Figure 4.18
PIPE 架構
Fetch Stage
icode, ifun: 取出指令的類型以及function coderA, rB: 取出兩個暫存器的地址valC: 8 bytes 常數valP: 下一個指令地址
Decode Stage
valA, valB: 為兩個來源值，可能從暫存器文件或是 Forwarding Unit 來的
Execute Stage
valE: 根據 ifun 控制運算的輸出CC: 設置條件碼- 若是條件跳轉，會根據條件碼判斷是否跳躍
Memory Stage
valM: 從資料記憶體取出的值- 若是存儲指令，將
valA 寫進資料記憶體
WriteBack Stage
Update PC
iaddq 動作
回到 Figure 4.18 來看，可以發現 iaddq 指令和 OPq 指令類似，差別在前者是使用立即數運算，因此我們可以將 iaddq 動作寫下來。注意到不用取出 valA ，取而代之的是換成常數值 valC 。
修改 HCL 行為
先到 sim/seq 路徑下，打開 seq-full.hcl 。可以看到它已經幫我們加好要實作的指令 iaddq ，後面都用 IIADDQ ，表示 Instruction ADDQ。
下面我會寫出要修改的地方，可以對照上面架構圖參考。
Fetch Stage
need_regids: 表示指令是否有包括暫存器。(need register IDs)
need_valC: 是否使用到常數值 valC。
Decode Stage
srcB: 是否需要從 rB 取出值，在 iaddq 中，rB 作為來源以及目的暫存器。
dstE: 設置目的暫存器存回位置，要放入 rB 。
Execute Stage
對照上面架構圖可以看出
其他階段皆不影響
測試
在 sim/seq 目錄下執行
都出現 Succeed 就代表成功了。
Part C
這部份是要對 pipe-full.hcl 和 ncopy.ys 進行優化。 PIPE 是一個流水線的 Y86-64 處理器。而 ncopy 函式是要將 len 大小的數組 src 複製到 dsc 。而評斷標準則是根據計算 CPE 來計分。
未優化
我們先來測試什麼都沒做的分數:
加入 iaddq 指令
在 Part B 我們在 seq 架構加入 iaddq 指令，現在一樣在 pipe 加入。修改 pipe-full.hcl ，詳細可參考 Part B 。
觀察原始組合語言，可以發現在加法上浪費了一些時間，一開始將 r10 設成 1 ，要對陣列往後一個元素時，又將 r10 設置成 8 。我們改用 iaddq 替代。
這部份優化有兩個要點:
- 換掉可以用
iaddq 替換的指令，讓同一個暫存器不要一直修改執行
- 在最後判斷
len > 0 ，對應到 andq %rdx,%rdx 所產生的條件碼，可以將 len-- 對應的指令放到最後面，這樣就可以直接設置條件碼而省掉上面 andq 指令。
針對第二點，我們可以將 iaddq 指令設置條件碼，因此不同於 Part B ，需要多修改以下。
先檢查新增的指令是否有問題：
有寫 ISA Succeed 就沒問題。接著來看 CPE。可以看到已經從 18.15 進步到 11.7 ，但仍大於 10 ，所以還沒有分數。
循環展開 8x1
使用循環展開來優化程式，對應課本 5.8 節。我們使用 8 路展開，使用一個變數 limit 來暫存 len ，循環展開的判斷條件用 limit ，剩餘的就用 len。
流程就是進入 8 個循環，接著檢查是否超過 8 個元素，若超過則看有沒有剩餘的，用一個循環處理剩餘的部份。
但在循環展開的部份，有兩種寫法。第一種是記憶體操作是在每個循環裡。第二種則是先做完 8 個記憶體操作，每個循環再做條件判斷。
ncopy:
# Loop header
xorq %rax,%rax # count = 0;
rrmovq %rdx, %rcx # limit = len
iaddq $-7, %rcx # limit -= 7
jle Remain # if so, goto Remain:
Loop0:
mrmovq (%rdi), %r10 # read val from src...
rmmovq %r10, (%rsi) # ...and store it to dst
andq %r10, %r10 # val <= 0?
jle Loop1 # if so, goto Npos:
iaddq $1, %rax # count++
Loop1:
mrmovq 8(%rdi), %r10 # read val from src...
rmmovq %r10, 8(%rsi) # ...and store it to dst
andq %r10, %r10 # val <= 0?
jle Loop2 # if so, goto Npos:
iaddq $1, %rax # count++
Loop2:
mrmovq 16(%rdi), %r10 # read val from src...
rmmovq %r10, 16(%rsi) # ...and store it to dst
andq %r10, %r10 # val <= 0?
jle Loop3 # if so, goto Npos:
iaddq $1, %rax # count++
Loop3:
mrmovq 24(%rdi), %r10 # read val from src...
rmmovq %r10, 24(%rsi) # ...and store it to dst
andq %r10, %r10 # val <= 0?
jle Loop4 # if so, goto Npos:
iaddq $1, %rax # count++
Loop4:
mrmovq 32(%rdi), %r10 # read val from src...
rmmovq %r10, 32(%rsi) # ...and store it to dst
andq %r10, %r10 # val <= 0?
jle Loop5 # if so, goto Npos:
iaddq $1, %rax # count++
Loop5:
mrmovq 40(%rdi), %r10 # read val from src...
rmmovq %r10, 40(%rsi) # ...and store it to dst
andq %r10, %r10 # val <= 0?
jle Loop6 # if so, goto Npos:
iaddq $1, %rax # count++
Loop6:
mrmovq 48(%rdi), %r10 # read val from src...
rmmovq %r10, 48(%rsi) # ...and store it to dst
andq %r10, %r10 # val <= 0?
jle Loop7 # if so, goto Npos:
iaddq $1, %rax # count++
Loop7:
mrmovq 56(%rdi), %r10 # read val from src...
rmmovq %r10, 56(%rsi) # ...and store it to dst
andq %r10, %r10 # val <= 0?
jle test # if so, goto Npos:
iaddq $1, %rax # count++
test:
iaddq $64, %rdi # src += 8
iaddq $64, %rsi # dst += 8
iaddq $-8, %rdx # len -= 8
iaddq $-8, %rcx # limit -= 8
jg Loop0 # if so, goto Loop:
RemainTest:
andq %rdx, %rdx
jle Done
Remain:
mrmovq (%rdi), %r11 # read val from src...
rmmovq %r11, (%rsi) # ...and store it to dst
andq %r11, %r11 # val <= 0?
jle test2 # if so, goto Npos:
iaddq $1, %rax # count++
test2:
iaddq $8, %rdi
iaddq $8, %rsi
iaddq $-1, %rdx
jg Remain
ncopy:
# Loop header
xorq %rax,%rax # count = 0;
rrmovq %rdx, %rcx # limit = len
iaddq $-7, %rcx # limit -= 7
jle Remain # if so, goto Remain:
Load:
mrmovq (%rdi), %r8 # read val from src...
mrmovq 8(%rdi), %r9 # read val from src...
mrmovq 16(%rdi), %r10 # read val from src...
mrmovq 24(%rdi), %r11 # read val from src...
mrmovq 32(%rdi), %r12 # read val from src...
mrmovq 40(%rdi), %r13 # read val from src...
mrmovq 48(%rdi), %r14 # read val from src...
mrmovq 56(%rdi), %rbp # read val from src...
Store:
rmmovq %r8, (%rsi) # ...and store it to dst
rmmovq %r9, 8(%rsi) # ...and store it to dst
rmmovq %r10, 16(%rsi) # ...and store it to dst
rmmovq %r11, 24(%rsi) # ...and store it to dst
rmmovq %r12, 32(%rsi) # ...and store it to dst
rmmovq %r13, 40(%rsi) # ...and store it to dst
rmmovq %r14, 48(%rsi) # ...and store it to dst
rmmovq %rbp, 56(%rsi) # ...and store it to dst
Loop0:
andq %r8, %r8 # val <= 0?
jle Loop1 # if so, goto Npos:
iaddq $1, %rax # count++
Loop1:
andq %r9, %r9 # val <= 0?
jle Loop2 # if so, goto Npos:
iaddq $1, %rax # count++
Loop2:
andq %r10, %r10 # val <= 0?
jle Loop3 # if so, goto Npos:
iaddq $1, %rax # count++
Loop3:
andq %r11, %r11 # val <= 0?
jle Loop4 # if so, goto Npos:
iaddq $1, %rax # count++
Loop4:
andq %r12, %r12 # val <= 0?
jle Loop5 # if so, goto Npos:
iaddq $1, %rax # count++
Loop5:
andq %r13, %r13 # val <= 0?
jle Loop6 # if so, goto Npos:
iaddq $1, %rax # count++
Loop6:
andq %r14, %r14 # val <= 0?
jle Loop7 # if so, goto Npos:
iaddq $1, %rax # count++
Loop7:
andq %rbp, %rbp # val <= 0?
jle test # if so, goto Npos:
iaddq $1, %rax # count++
test:
iaddq $64, %rdi # src += 8
iaddq $64, %rsi # dst += 8
iaddq $-8, %rdx # len -= 8
iaddq $-8, %rcx # limit -= 8
jg Load # if so, goto Loop:
RemainTest:
andq %rdx, %rdx
jle Done
Remain:
mrmovq (%rdi), %r11 # read val from src...
rmmovq %r11, (%rsi) # ...and store it to dst
andq %r11, %r11 # val <= 0?
jle test2 # if so, goto Npos:
iaddq $1, %rax # count++
test2:
iaddq $8, %rdi
iaddq $8, %rsi
iaddq $-1, %rdx
jg Remain
可以看到版本二的效能好很多，我認為是因為以下問題:
- 減少 Data Dependency: 版本一在讀記憶體後緊接著又寫記憶體，使兩個指令發生 Load-use data dependency ，而版本二則因為是一次讀完並一次寫完，而且使用不同暫存器，因此解決了這個問題。
- Space Locality: 版本二一次讀取和寫入一個連續的記憶體區段，會比分段讀寫效率來的更高。
剩餘部份循環展開
將剩餘部份循環展開 7x1: R0 到 R7，因為剩下一定是小於 8 的。此外在增加一些優化，例如只用 len 判斷、減少初始值設定。
ncopy:
# Loop header
xorq %rax,%rax # count = 0;
iaddq $-7, %rdx # limit -= 7
jle R0 # if so, goto R0:
Load:
mrmovq (%rdi), %r8 # read val from src...
mrmovq 8(%rdi), %r9 # read val from src...
mrmovq 16(%rdi), %r10 # read val from src...
mrmovq 24(%rdi), %r11 # read val from src...
mrmovq 32(%rdi), %r12 # read val from src...
mrmovq 40(%rdi), %r13 # read val from src...
mrmovq 48(%rdi), %r14 # read val from src...
mrmovq 56(%rdi), %rbp # read val from src...
Store:
rmmovq %r8, (%rsi) # ...and store it to dst
rmmovq %r9, 8(%rsi) # ...and store it to dst
rmmovq %r10, 16(%rsi) # ...and store it to dst
rmmovq %r11, 24(%rsi) # ...and store it to dst
rmmovq %r12, 32(%rsi) # ...and store it to dst
rmmovq %r13, 40(%rsi) # ...and store it to dst
rmmovq %r14, 48(%rsi) # ...and store it to dst
rmmovq %rbp, 56(%rsi) # ...and store it to dst
Loop0:
andq %r8, %r8 # val <= 0?
jle Loop1 # if so, goto Npos:
iaddq $1, %rax # count++
Loop1:
andq %r9, %r9 # val <= 0?
jle Loop2 # if so, goto Npos:
iaddq $1, %rax # count++
Loop2:
andq %r10, %r10 # val <= 0?
jle Loop3 # if so, goto Npos:
iaddq $1, %rax # count++
Loop3:
andq %r11, %r11 # val <= 0?
jle Loop4 # if so, goto Npos:
iaddq $1, %rax # count++
Loop4:
andq %r12, %r12 # val <= 0?
jle Loop5 # if so, goto Npos:
iaddq $1, %rax # count++
Loop5:
andq %r13, %r13 # val <= 0?
jle Loop6 # if so, goto Npos:
iaddq $1, %rax # count++
Loop6:
andq %r14, %r14 # val <= 0?
jle Loop7 # if so, goto Npos:
iaddq $1, %rax # count++
Loop7:
andq %rbp, %rbp # val <= 0?
jle test # if so, goto Npos:
iaddq $1, %rax # count++
test:
iaddq $64, %rdi # src += 8
iaddq $64, %rsi # dst += 8
iaddq $-8, %rdx # len -= 8
jg Load # if so, goto Loop:
R0:
iaddq $7, %rdx
jle Done
mrmovq (%rdi),%r8
rmmovq %r8, (%rsi)
andq %r8, %r8
jle R1
iaddq $1,%rax
R1:
iaddq $-1, %rdx
jle Done
mrmovq 8(%rdi),%r8
rmmovq %r8, 8(%rsi)
andq %r8, %r8
jle R2
iaddq $1,%rax
R2:
iaddq $-1, %rdx
jle Done
mrmovq 16(%rdi),%r8
rmmovq %r8, 16(%rsi)
andq %r8, %r8
jle R3
iaddq $1,%rax
R3:
iaddq $-1, %rdx
jle Done
mrmovq 24(%rdi),%r8
rmmovq %r8, 24(%rsi)
andq %r8, %r8
jle R4
iaddq $1,%rax
R4:
iaddq $-1, %rdx
jle Done
mrmovq 32(%rdi),%r8
rmmovq %r8, 32(%rsi)
andq %r8, %r8
jle R5
iaddq $1,%rax
R5:
iaddq $-1, %rdx
jle Done
mrmovq 40(%rdi),%r8
rmmovq %r8, 40(%rsi)
andq %r8, %r8
jle R6
iaddq $1,%rax
R6:
iaddq $-1, %rdx
jle Done
mrmovq 48(%rdi),%r8
rmmovq %r8, 48(%rsi)
andq %r8, %r8
jle Done
iaddq $1,%rax
新增 Load forwarding
我們知道 Load-use data hazard 的行程就是當我使用 load 指令將記憶體資料讀取到暫存器，緊接著下一個指令就會使用到該暫存器時，forwarding 技術就沒辦法支援，一定要暫停一個時脈。然而，如果後面緊接著的指令為 Store 指令的話，就可以透過 forwarding 將記憶體資料從 MEM 階段移到 EXE 階段，因為 Store 指令是不需要計算，因此不用經過 ALU 。我們將其稱為 load forwarding 。
本節根據 4.57 題，下圖是 load forwarding 示意圖。m_valM 傳到 Fwd A。
CSAPP-3e-Solutions > Processor Architecture > 4.57
分支預測優化
我們嘗試優化分支，因為原本的分支預測都是猜要跳，但原本的程式是寫 jle Done ，多數的情況下是不會跳到 Done 的，因此修改成以下狀態：
分數很明顯衝上來了。
其他修正
最後我嘗試將循環展開改成不同的數字，例如 6x1 、 4x1 等等，但分數反而降下去了。後來參考他人文章，透過修改分支的預測，將猜會跳改成猜不會跳，就成功拿到滿分了。
HackMD