# CS:APP Architecture Lab
## 環境準備
### 安裝
一樣到官網安裝壓縮檔: [Lab Assignments](http://csapp.cs.cmu.edu/3e/labs.html)
> [Lab PDF 檔](http://csapp.cs.cmu.edu/3e/archlab.pdf)
### 環境調整
先將檔案解壓縮
```
$ tar xvf archlab-handout.tar
$ cd archlab-handout
$ tar xvf sim.tar
```
安裝作業需要套件
```
$ sudo apt install tcl tcl-dev tk tk-dev
$ sudo apt-get install bison flex
```
接下來稍微麻煩一些，因為編譯器版本更新，因此我們需要做以下的改動
1. 修改 `sim/Makefile`
```diff
all:
(cd misc; make all)
- (cd pipe; make all GUIMODE=$(GUIMODE) TKLIBS="$(TKLIBS)" TKINC="$(TKINC)")
+ (cd pipe; make all)
- (cd seq; make all GUIMODE=$(GUIMODE) TKLIBS="$(TKLIBS)" TKINC="$(TKINC)")
+ (cd seq; make all)
(cd y86-code; make all)
```
2. 修改 `misc/Makefile`
```diff
-CFLAGS=-Wall -O1 -g
+CFLAGS=-Wall -O1 -g -fcommon
-LCFLAGS=-O1
+LCFLAGS=-O1 -fcommon
```
3. 修改 `pipe/Makefile` 和 `seq/Makefile`
```diff
-CFLAGS=-Wall -O2
+CFLAGS=-Wall -O1 -g -fcommon
```
4. 將上面四個 `Makefile` 的 `GUIMODE`, `TKLIBS`, `TKINC` 註解掉
```
#GUIMODE=-DHAS_GUI
#TKLIBS=-L/usr/lib -ltk -ltcl
#TKINC=-isystem /usr/include/tcl8.5
```
修改完成後編譯就可以成功了。
```
$ make clean
$ make
../misc/yas prog1.ys
../misc/yas prog2.ys
../misc/yas prog3.ys
../misc/yas prog4.ys
../misc/yas prog5.ys
../misc/yas prog6.ys
../misc/yas prog7.ys
../misc/yas prog8.ys
../misc/yas prog9.ys
../misc/yas prog10.ys
../misc/yas ret-hazard.ys
make[1]: Leaving directory '/home/appmedia/CSAPP/Architecture-Lab/archlab-handout/sim/y86-code'
```
## Part A
第 A 部份希望你用 Y86-64 組合語言寫三個函式，三個都是鍊結串列的操作。下圖是串列的結構體。移動到 `sim/misc` 目錄下。
```cpp
/* linked list element */
typedef struct ELE {
long val;
struct ELE *next;
} *list_ptr;
--------------------------
# Sample linked list
.align 8
ele1:
.quad 0x00a
.quad ele2
ele2:
.quad 0x0b0
.quad ele3
ele3:
.quad 0xc00
.quad 0
```
可以參考 CS:APP 中的圖 4-8 ，提供了簡單的框架。
### `sum_list`
實現走訪整個鍊結串列，累加每個節點的值。
```cpp
/* sum_list - Sum the elements of a linked list */
long sum_list(list_ptr ls)
{
long val = 0;
while (ls) {
val += ls->val;
ls = ls->next;
}
return val;
}
```
創建 `sum_list.ys` 檔。
* `ls -> next`: 因為結構體對齊是 8 ，因此指向下一個節點是加 8
* while 迴圈使用 jump-to-middle，可參考CS:APP 第三章 3.6.7 節
```cpp
# Execution begins at address 0
.pos 0
irmovq stack,%rsp # Set up stack pointer
call main # Execute main program
halt # Terminate program
# Sample linked list
.align 8
ele1:
.quad 0x00a
.quad ele2
ele2:
.quad 0x0b0
.quad ele3
ele3:
.quad 0xc00
.quad 0
main:
irmovq ele1,%rdi // linked list initial address
call sumlist
ret
sumlist:
irmovq %0, %rax // set val = 0
jmp test
loop:
mrmovq (%rdi), %rsi
addq %rsi, %rax
mrmovq 8(%rdi), %rdi // ls = ls -> next
test:
andq %rdi, %rdi // if (!ls) return
jne loop
ret
# Stack starts here and grows to lower addresses
.pos 0x200
stack: // 下面要留一行空白
```
輸入下面命令，`rax` 為 `0xcba` 代表成功。
```
$ ./yas sum_list.ys
$ ./yis sum_list.yo
Stopped in 26 steps at PC = 0x13. Status 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%rax: 0x0000000000000000 0x0000000000000cba
%rsp: 0x0000000000000000 0x0000000000000200
%rsi: 0x0000000000000000 0x0000000000000c00
Changes to memory:
0x01f0: 0x0000000000000000 0x000000000000005b
0x01f8: 0x0000000000000000 0x0000000000000013
```
### `rsum_list`
一樣是求和函式，只是這題是用遞迴的方式。
```cpp
/* rsum_list - Recursive version of sum_list */
long rsum_list(list_ptr ls)
{
if (!ls)
return 0;
else {
long val = ls->val;
long rest = rsum_list(ls->next);
return val + rest;
}
}
```
創建 `rsum_list.ys` 檔。
* 進入遞迴之前要先將暫存的 `rsi` push 進堆疊，等到回來之後才 pop 出來。
```cpp
# Execution begins at address 0
.pos 0
irmovq stack, %rsp # Set up stack pointer
call main # Execute main program
halt # Terminate program
# Sample linked list
.align 8
ele1:
.quad 0x00a
.quad ele2
ele2:
.quad 0x0b0
.quad ele3
ele3:
.quad 0xc00
.quad 0
main:
irmovq ele1,%rdi
call rsum_list
ret
rsum_list:
andq %rdi, %rdi // if (!ls)
je return
mrmovq (%rdi), %rsi // val = ls->val
mrmovq 8(%rdi), %rdi // rdi = ls->next
pushq %rsi --------|
call rsum_list |
popq %rsi --------|
addq %rsi, %rax // val + rest
ret
return:
irmovq $0, %rax
ret
# Stack starts here and grows to lower addresses
.pos 0x200
stack:
```
輸入下面命令，`rax` 為 `0xcba` 代表成功。
```cpp
$ ./yas rsum_list.ys
$ ./yis rsum_list.yo
Stopped in 37 steps at PC = 0x13. Status 'HLT', CC Z=0 S=0 O=0
Changes to registers:
%rax: 0x0000000000000000 0x0000000000000cba
%rsp: 0x0000000000000000 0x0000000000000200
%rsi: 0x0000000000000000 0x000000000000000a
Changes to memory:
0x01c0: 0x0000000000000000 0x0000000000000086
0x01c8: 0x0000000000000000 0x0000000000000c00
0x01d0: 0x0000000000000000 0x0000000000000086
0x01d8: 0x0000000000000000 0x00000000000000b0
0x01e0: 0x0000000000000000 0x0000000000000086
0x01e8: 0x0000000000000000 0x000000000000000a
0x01f0: 0x0000000000000000 0x000000000000005b
0x01f8: 0x0000000000000000 0x0000000000000013
```
### `copy_block`
將 `src` 陣列裡的元素抓出來給 `dest` 陣列，並將每個元素做 XOR 操作後回傳。
```cpp
/* copy_block - Copy src to dest and return xor checksum of src */
long copy_block(long *src, long *dest, long len)
{
long result = 0;
while (len > 0) {
long val = *src++;
*dest++ = val;
result ^= val;
len--;
}
return result;
}
```
創建 `rsum_list.ys` 檔。
* 輸入參數的順序分別是: `rdi`, `rsi`, `rdx`
* 設置常數給暫存器 `r8`, `r9`，用來做加法操作
* 第一次的迴圈的判斷條件為 `andq` 操作，而之後則是在 `subq` 之後便會設置條件碼(CC) ZF 位，表示檢查操作後是否為 0
```cpp
# Execution begins at address 0
.pos 0
irmovq stack, %rsp # Set up stack pointer
call main # Execute main program
halt # Terminate program
# Sample
.align 8
# Source block
src:
.quad 0x00a
.quad 0x0b0
.quad 0xc00
# Destination block
dest:
.quad 0x111
.quad 0x222
.quad 0x333
main:
irmovq src, %rdi // first arg
irmovq dest, %rsi // second arg
irmovq $3, %rdx // third arg
call copy_block
ret
copy_block:
irmovq $0, %rax
irmovq $1, %r8
irmovq $8, %r9
andq %rdx, %rdx
jmp test
loop:
mrmovq (%rdi), %rbx // val = *src
addq %r9, %rdi // *src++
rmmovq %rbx, (%rsi) // *dest = val
addq %r9, %rsi // *dest++
xorq %rbx, %rax // result ^= val
subq %r8, %rdx // len--
test:
jne loop
ret
# Stack starts here and grows to lower addresses
.pos 0x200
stack:
```
輸入下面命令，`rax` 為 `0xcba` 代表成功。
```cpp
$ ./yas copy_block.ys
$ ./yis copy_block.yo
Stopped in 36 steps at PC = 0x13. Status 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%rax: 0x0000000000000000 0x0000000000000cba
%rbx: 0x0000000000000000 0x0000000000000c00
%rsp: 0x0000000000000000 0x0000000000000200
%rsi: 0x0000000000000000 0x0000000000000048
%rdi: 0x0000000000000000 0x0000000000000030
%r8: 0x0000000000000000 0x0000000000000001
%r9: 0x0000000000000000 0x0000000000000008
Changes to memory:
0x0030: 0x0000000000000111 0x000000000000000a
0x0038: 0x0000000000000222 0x00000000000000b0
0x0040: 0x0000000000000333 0x0000000000000c00
0x01f0: 0x0000000000000000 0x000000000000006f
0x01f8: 0x0000000000000000 0x0000000000000013
```
## 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 code
* `rA`, `rB`: 取出兩個暫存器的地址
* `valC`: 8 bytes 常數
* `valP`: 下一個指令地址
#### Decode Stage
* `valA`, `valB`: 為兩個來源值，可能從暫存器文件或是 Forwarding Unit 來的
#### Execute Stage
* `valE`: 根據 `ifun` 控制運算的輸出
* `CC`: 設置條件碼
* 若是條件跳轉，會根據條件碼判斷是否跳躍
#### Memory Stage
* `valM`: 從資料記憶體取出的值
* 若是存儲指令，將 `valA` 寫進資料記憶體
#### WriteBack Stage
* 將最多兩個結果寫回目的暫存器
#### Update PC
* 更新 PC 為下一個指令的地址
### `iaddq` 動作
回到 Figure 4.18 來看，可以發現 `iaddq` 指令和 `OPq` 指令類似，差別在前者是使用立即數運算，因此我們可以將 `iaddq` 動作寫下來。注意到不用取出 `valA` ，取而代之的是換成常數值 `valC` 。
```cpp
Fetch:
icode:ifun <- M_1[PC]
rA:rB <- M_1[PC+1]
valC <- M_8[PC+2]
valP <- PC+10
Decode:
valB <- R[rB]
Execute:
valE <- valB + valC
Set CC
Memory:
None
Write Back:
R[rB] <- valE
Update PC:
PC <- valP
```
### 修改 HCL 行為
先到 `sim/seq` 路徑下，打開 `seq-full.hcl` 。可以看到它已經幫我們加好要實作的指令 `iaddq` ，後面都用 `IIADDQ` ，表示 Instruction ADDQ。
```cpp
# Instruction code for iaddq instruction
wordsig IIADDQ 'I_IADDQ' # Part B added by Appmedia06
```
下面我會寫出要修改的地方，可以對照上面架構圖參考。
#### Fetch Stage
* `instr_valid`: 確認指令是否合法
```cpp
bool instr_valid = icode in
{ INOP, IHALT, IRRMOVQ, IIRMOVQ, IRMMOVQ, IMRMOVQ,
IOPQ, IJXX, ICALL, IRET, IPUSHQ, IPOPQ, IIADDQ };
```
* `need_regids`: 表示指令是否有包括暫存器。(need register IDs)
```cpp
bool need_regids =
icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ,
IIRMOVQ, IRMMOVQ, IMRMOVQ, IIADDQ };
```
* `need_valC`: 是否使用到常數值 `valC`。
```cpp
bool need_valC =
icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX, ICALL, IIADDQ };
```
#### Decode Stage
* `srcB`: 是否需要從 `rB` 取出值，在 `iaddq` 中，`rB` 作為來源以及目的暫存器。
```cpp
word srcB = [
icode in { IOPQ, IRMMOVQ, IMRMOVQ, IIADDQ } : rB;
icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
1 : RNONE; # Don't need register
];
```
* `dstE`: 設置目的暫存器存回位置，要放入 `rB` 。
```
word dstE = [
icode in { IRRMOVQ } && Cnd : rB;
icode in { IIRMOVQ, IOPQ, IIADDQ} : rB;
icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
1 : RNONE; # Don't write any register
];
```
#### Execute Stage
對照上面架構圖可以看出
* `aluA`: 需要對應到 `valC`
```cpp
word aluA = [
icode in { IRRMOVQ, IOPQ } : valA;
icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IIADDQ } : valC;
icode in { ICALL, IPUSHQ } : -8;
icode in { IRET, IPOPQ } : 8;
# Other instructions don't need ALU
];
```
* `aluB`: 需要對應到 `valB`
```cpp
word aluB = [
icode in { IRMMOVQ, IMRMOVQ, IOPQ, ICALL,
IPUSHQ, IRET, IPOPQ, IIADDQ } : valB;
icode in { IRRMOVQ, IIRMOVQ } : 0;
# Other instructions don't need ALU
];
```
#### 其他階段皆不影響
### 測試
在 `sim/seq` 目錄下執行
* 建立自己版本的 `seq-full.hcl`
```
make VERSION=full
```
* 在簡單的 Y86-64 程式上測試解答
```
./ssim -t ../y86-code/asumi.yo
```
* 使用基準程式來測試解答
```
cd ../y86-code; make testssim
Makefile:42: warning: ignoring prerequisites on suffix rule definition
Makefile:45: warning: ignoring prerequisites on suffix rule definition
Makefile:48: warning: ignoring prerequisites on suffix rule definition
Makefile:51: warning: ignoring prerequisites on suffix rule definition
../seq/ssim -t asum.yo > asum.seq
...
prog8.seq:ISA Check Succeeds
pushquestion.seq:ISA Check Succeeds
pushtest.seq:ISA Check Succeeds
ret-hazard.seq:ISA Check Succeeds
rm asum.seq asumr.seq cjr.seq j-cc.seq poptest.seq pushquestion.seq pushtest.seq prog1.seq prog2.seq prog3.seq prog4.seq prog5.seq prog6.seq prog7.seq prog8.seq ret-hazard.seq
```
* 測試除了 `iaddq` 以外的所有指令
```
cd ../ptest; make SIM=../seq/ssim
./optest.pl -s ../seq/ssim
Simulating with ../seq/ssim
All 49 ISA Checks Succeed
./jtest.pl -s ../seq/ssim
Simulating with ../seq/ssim
All 64 ISA Checks Succeed
./ctest.pl -s ../seq/ssim
Simulating with ../seq/ssim
All 22 ISA Checks Succeed
./htest.pl -s ../seq/ssim
```
* 測試我們實作的 `iaddq` 指令
```
cd ../ptest; make SIM=../seq/ssim TFLAGS=-i
../ptest; make SIM=../seq/ssim TFLAGS=-i
./optest.pl -s ../seq/ssim -i
Simulating with ../seq/ssim
All 58 ISA Checks Succeed
./jtest.pl -s ../seq/ssim -i
Simulating with ../seq/ssim
All 96 ISA Checks Succeed
./ctest.pl -s ../seq/ssim -i
Simulating with ../seq/ssim
All 22 ISA Checks Succeed
./htest.pl -s ../seq/ssim -i
Simulating with ../seq/ssim
All 756 ISA Checks Succeed
```
都出現 `Succeed` 就代表成功了。
## Part C
這部份是要對 `pipe-full.hcl` 和 `ncopy.ys` 進行優化。 PIPE 是一個流水線的 Y86-64 處理器。而 `ncopy` 函式是要將 `len` 大小的數組 `src` 複製到 `dsc` 。而評斷標準則是根據計算 CPE 來計分。
:::info
在 `sim/pipe` 路徑下執行
:::
* `ncopy` 函式
```cpp
word_t ncopy(word_t *src, word_t *dst, word_t len)
{
word_t count = 0;
word_t val;
while (len > 0) {
val = *src++;
*dst++ = val;
if (val > 0)
count++;
len--;
}
return count;
}
```
* 預設的組合語言
```cpp
# Loop header
xorq %rax,%rax # count = 0;
andq %rdx,%rdx # len <= 0?
jle Done # if so, goto Done:
Loop:
mrmovq (%rdi), %r10 # read val from src...
rmmovq %r10, (%rsi) # ...and store it to dst
andq %r10, %r10 # val <= 0?
jle Npos # if so, goto Npos:
irmovq $1, %r10
addq %r10, %rax # count++
Npos:
irmovq $1, %r10
subq %r10, %rdx # len--
irmovq $8, %r10
addq %r10, %rdi # src++
addq %r10, %rsi # dst++
andq %rdx,%rdx # len > 0?
jg Loop # if so, goto Loop:
```
### 未優化
我們先來測試什麼都沒做的分數:
```cpp
make VERSION=full
./psim -t sdriver.yo
./psim -t ldriver.yo
./correctness.pl
./benchmark.pl
Average CPE 15.18
Score 0.0/60.0
```
### 加入 `iaddq` 指令
在 Part B 我們在 `seq` 架構加入 `iaddq` 指令，現在一樣在 `pipe` 加入。修改 `pipe-full.hcl` ，詳細可參考 [Part B](https://hackmd.io/aMOfuLoOQcas3ExP43349w?view#%E4%BF%AE%E6%94%B9-HCL-%E8%A1%8C%E7%82%BA) 。
觀察原始組合語言，可以發現在加法上浪費了一些時間，一開始將 `r10` 設成 1 ，要對陣列往後一個元素時，又將 `r10` 設置成 8 。我們改用 `iaddq` 替代。
```diff
ncopy:
# Loop header
xorq %rax,%rax # count = 0;
andq %rdx,%rdx # len <= 0?
jle Done # if so, goto Done:
Loop:
mrmovq (%rdi), %r10 # read val from src...
rmmovq %r10, (%rsi) # ...and store it to dst
andq %r10, %r10 # val <= 0?
jle Npos # if so, goto Npos:
+ iaddq $1, %rax # count++
Npos:
+ iaddq $8, %rdi # src++
+ iaddq $8, %rsi # dst++
+ iaddq $-1, %rdx # len-- 順便設置條件碼
jg Loop # if so, goto Loop:
```
這部份優化有兩個要點:
1. 換掉可以用 `iaddq` 替換的指令，讓同一個暫存器不要一直修改執行
2. 在最後判斷 `len > 0` ，對應到 `andq %rdx,%rdx` 所產生的條件碼，可以將 `len--` 對應的指令放到最後面，這樣就可以直接設置條件碼而省掉上面 `andq` 指令。
針對第二點，我們可以將 `iaddq` 指令設置條件碼，因此不同於 Part B ，需要多修改以下。
```cpp
## Should the condition codes be updated?
bool set_cc = (E_icode == IOPQ || E_icode == IIADDQ) &&
# State changes only during normal operation
!m_stat in { SADR, SINS, SHLT } && !W_stat in { SADR, SINS, SHLT };
```
先檢查新增的指令是否有問題：
```cpp
make VERSION=full
./psim -t ../y86-code/asumi.yo
(cd ../ptest;make SIM=../pipe/psim TFLAGS=-i)
(cd ../ptest;make SIM=../pipe/psim)
```
有寫 ISA Succeed 就沒問題。接著來看 CPE。可以看到已經從 18.15 進步到 11.7 ，但仍大於 10 ，所以還沒有分數。
```cpp
./psim -t sdriver.yo
./psim -t ldriver.yo
./correctness.pl
./benchmark.pl
Average CPE 11.70
Score 0.0/60.0
```
### 循環展開 8x1
使用循環展開來優化程式，對應課本 5.8 節。我們使用 8 路展開，使用一個變數 `limit` 來暫存 `len` ，循環展開的判斷條件用 `limit` ，剩餘的就用 `len`。
流程就是進入 8 個循環，接著檢查是否超過 8 個元素，若超過則看有沒有剩餘的，用一個循環處理剩餘的部份。
但在循環展開的部份，有兩種寫法。第一種是記憶體操作是在每個循環裡。第二種則是先做完 8 個記憶體操作，每個循環再做條件判斷。
* 版本一
```cpp
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
```
* 版本二
```cpp
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
```
* 版本一效能
```
Average CPE 9.23
Score 25.5/60.0
```
* 版本二效能
```cpp
Average CPE 8.44
Score 41.1/60.0
```
可以看到版本二的效能好很多，我認為是因為以下問題:
1. 減少 Data Dependency: 版本一在讀記憶體後緊接著又寫記憶體，使兩個指令發生 Load-use data dependency ，而版本二則因為是一次讀完並一次寫完，而且使用不同暫存器，因此解決了這個問題。
```cpp
mrmovq (%rdi), %r10 # read val from src...
rmmovq %r10, (%rsi) # ...and store it to dst
```
2. Space Locality: 版本二一次讀取和寫入一個連續的記憶體區段，會比分段讀寫效率來的更高。
### 剩餘部份循環展開
將剩餘部份循環展開 7x1: `R0` 到 `R7`，因為剩下一定是小於 8 的。此外在增加一些優化，例如只用 `len` 判斷、減少初始值設定。
```cpp
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
```
* 分數
```
Average CPE 8.15
Score 47.1/60.0
```
### 新增 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](https://dreamanddead.github.io/CSAPP-3e-Solutions/chapter4/4.57/)
```
Average CPE 8.15
Score 47.1/60.0
```
### 分支預測優化
我們嘗試優化分支，因為原本的分支預測都是猜要跳，但原本的程式是寫 `jle Done` ，多數的情況下是不會跳到 Done 的，因此修改成以下狀態：
```cpp
R0:
iaddq $3, %rdx
jg R00
jmp Done
R00:
mrmovq (%rdi),%r8
rmmovq %r8, (%rsi)
andq %r8, %r8
jle R1
iaddq $1,%rax
```
分數很明顯衝上來了。
```
Average CPE 7.70
Score 56.0/60.0
```
### 其他修正
最後我嘗試將循環展開改成不同的數字，例如 6x1 、 4x1 等等，但分數反而降下去了。後來參考他人文章，透過修改分支的預測，將猜會跳改成猜不會跳，就成功拿到滿分了。
```cpp
# Predict next value of PC
word f_predPC = [
f_icode in { ICALL } : f_valC;
1 : f_valP;
];
```
```cpp
Average CPE 5.42
Score 60.0/60.0
```
Sign in with Wallet
Connect another wallet