CS:APP Architecture Lab
实验需求
该实验分为三个部分,每个部分都有自己的特色。在A部分中,您将编写一些简单的 Y86−64 程序并熟悉 Y86−64 工具。在B部分中,您将使用一条新指令扩展 SEQ 模拟器。这两部分将为C部分做准备,C部分是实验的核心,您将优化 Y86−64 基准程序和处理器设计。
Part A
本部分在目录sim/misc中进行。
需求
用 Y86−64 指令编写能实现下述C语言函数功能的汇编程序。
注:在所有的 Y86−64 函数中,应该遵循 x86−64 的约定来传递函数参数、使用寄存器和使用堆栈。
链表元素求和
/* linked list element */
typedef struct ELE {
long val;
struct ELE *next;
} *list_ptr;
//循环版本
/* 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;
}
//递归版本
/* 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;
}
}
所使用的数据如下
# Sample linked list
.align 8
ele1:
.quad 0x00a
.quad ele2
ele2:
.quad 0x0b0
.quad ele3
ele3:
.quad 0xc00
.quad 0
数组元素拷贝
/* 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;
}
所使用的数据如下
.align 8
# Source block
src:
.quad 0x00a
.quad 0x0b0
.quad 0xc00
# Destination block
dest:
.quad 0x111
.quad 0x222
.quad 0x333
Solution
sum_list
参考 CS:APP3e P252 即可编写出以下汇编程序。
# 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 sum_list
ret
# long sum_list(list_ptr ls)
# ls in %rdi
sum_list:
irmovq $8,%r8 # constant 8
xorq %rax,%rax # val = 0
andq %rdi,%rdi # set CC
jmp test # goto test
loop:
mrmovq (%rdi),%r9 # val += ls -> val
addq %r9,%rax
addq %r8,%rdi # ls = ls -> next
mrmovq (%rdi),%rdi
andq %rdi,%rdi # set CC
test:
jne loop # stop when ls == 0
ret # return
# Stack starts here and grows to lower addresses.
.pos 0x200
stack:
rsum_list
按照对应c函数进行模拟即可,具体可看注释。
# 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
# long rsum_list(list_ptr ls)
# ls in %rdi
rsum_list:
irmovq $8,%r8 # constant 8
andq %rdi,%rdi # ls != 0 ?
jne test
xorq %rax,%rax # return 0
ret
test:
mrmovq (%rdi),%r9 # val = ls -> val
pushq %r9 # save val
addq %r8,%rdi # ls = ls->next
mrmovq (%rdi),%rdi
call rsum_list # get rest
popq %r9 # get val
addq %r9,%rax # val + rest
ret
# Stack starts here and grows to lower addresses.
.pos 0x200
stack:
copy_block
和sum_list结构类似,注意数据与前文中的链表是不同的。
# Execution begins at address 0
.pos 0
irmovq stack, %rsp # Set up stack pointer
call main # Execute main program
halt # Terminate program
.align 8
# Source block
src:
.quad 0x00a
.quad 0x0b0
.quad 0xc00
# Destination block
dest:
.quad 0x111
.quad 0x222
.quad 0x333
main:
irmovq src,%rdi
irmovq dest,%rsi
irmovq $3,%rdx
call copy_block
ret
# long copy_block(long *src, long *dest, long len)
# src in %rdi, dest in %rsi, len in %rdx
copy_block:
irmovq $8,%r8 # constant 8
irmovq $1,%r9 # constant 1
xorq %rax,%rax # result = 0
andq %rdx,%rdx # set CC
jmp test # goto test
loop:
mrmovq (%rdi),%r10 # val = *src++
addq %r8,%rdi
rmmovq %r10,(%rsi) # *dest++ = val
addq %r8,%rsi
xorq %r10,%rax # result ^= val
subq %r9,%rdx # len--
andq %rdx,%rdx # set CC
test:
jne loop # stop when len == 0
ret # return
# Stack starts here and grows to lower addresses.
.pos 0x200
stack:
Part B
本部分在目录sim/seq中进行。
需求
扩展 SEQ 处理器以支持 iaddq 指令,如 CS:APP3e 家庭作业问题4.51和4.52中所述。
要添加该指令,您需要修改文件 seq−full.hcl 。它实现了 CS:APP3e 教科书中描述的 SEQ 处理器。
Solution
首先由家庭作业问题4.51我们可以确认 iaddq 指令所执行的计算如下
阶段 | iaddq V, rB |
---|---|
取指 | icode:ifun <— M1[PC] |
rA:rB <— M1[PC+1] | |
valC <— M8[PC+2] | |
valP <— PC+10 | |
译码 | valB <— R[rB] |
执行 | valE <— valB+valC |
Set CC | |
访存 | |
回写 | R[rB] <— valE |
更新PC | PC <— valP |
然后只需用上述给出的指令描述表结合 CS:APP3e 中 4.3.4 SQE 阶段的实现,对文件 seq−full.hcl 中的控制信号定义进行修改即可。
具体修改如下 (只需修改四个阶段)
################ Fetch Stage ################################### 取指阶段
# Determine instruction code
word icode = [
imem_error: INOP;
1: imem_icode; # Default: get from instruction memory
];
# Determine instruction function
word ifun = [
imem_error: FNONE;
1: imem_ifun; # Default: get from instruction memory
];
# 将IIADDQ归为合法指令
bool instr_valid = icode in
{ INOP, IHALT, IRRMOVQ, IIRMOVQ, IRMMOVQ, IMRMOVQ,
IOPQ, IJXX, ICALL, IRET, IPUSHQ, IPOPQ, IIADDQ };
# Does fetched instruction require a regid byte?
# IIADDQ指令包括一个寄存器指示符
bool need_regids =
icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ,
IIRMOVQ, IRMMOVQ, IMRMOVQ, IIADDQ };
# Does fetched instruction require a constant word?
# IIADDQ指令包括一个常数字
bool need_valC =
icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX, ICALL, IIADDQ };
################ Decode Stage ################################### 译码、回写阶段
## What register should be used as the A source?
word srcA = [
icode in { IRRMOVQ, IRMMOVQ, IOPQ, IPUSHQ } : rA;
icode in { IPOPQ, IRET } : RRSP;
1 : RNONE; # Don't need register
];
## What register should be used as the B source?
# IIADDQ中的valB由rB产生,故寄存器ID srB应为rB
word srcB = [
icode in { IOPQ, IRMMOVQ, IMRMOVQ, IIADDQ } : rB;
icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
1 : RNONE; # Don't need register
];
## What register should be used as the E destination?
# IIADDQ需要将执行结果回写到R[rB]中,故寄存器ID 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
];
## What register should be used as the M destination?
word dstM = [
icode in { IMRMOVQ, IPOPQ } : rA;
1 : RNONE; # Don't write any register
];
################ Execute Stage ################################### 执行阶段
## Select input A to ALU
# IIADDQ在执行阶段的操作数alua == valC
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
];
## Select input B to ALU
# IIADDQ在执行阶段的操作数alub == valB
word aluB = [
icode in { IRMMOVQ, IMRMOVQ, IOPQ, ICALL,
IPUSHQ, IRET, IPOPQ, IIADDQ } : valB;
icode in { IRRMOVQ, IIRMOVQ } : 0;
# Other instructions don't need ALU
];
## Set the ALU function
word alufun = [
icode == IOPQ : ifun;
1 : ALUADD;
];
## Should the condition codes be updated?
# IIADDQ指令执行结果会更新条件码寄存器
bool set_cc = icode in { IOPQ, IIADDQ };
可能遇到的问题
在使用 make 来构建一个新的 SEQ 模拟器make VERSION=full
时可能会出现以下报错
# Building the seq-full.hcl version of SEQ
../misc/hcl2c -n seq-full.hcl <seq-full.hcl >seq-full.c
gcc -Wall -O2 -isystem /usr/include/tcl8.5 -I../misc -DHAS_GUI -o ssim \
seq-full.c ssim.c ../misc/isa.c -L/usr/lib -ltk8.5 -ltcl8.5 -lm
/tmp/ccgYK3Jx.o:(.data.rel+0x0):对‘matherr’未定义的引用
collect2: error: ld returned 1 exit status
Makefile:42: recipe for target 'ssim' failed
make: *** [ssim] Error 1
解决方案
将 seq 目录下 ssim.c 文件中的
884 extern int matherr();
885 int *tclDummyMathPtr = (int *) matherr;
注释掉即可
Part C
本部分在目录 sim/pipe 中进行。
需求
修改 ncopy.ys 和 pipe−full.hcl,目的是使 ncopy.ys 在 pipe−full.hcl 构建出的 PIPE 处理器上尽可能快地运行。(在能够实现 ncopy.ys 功能的前提下)
ncopy.ys实现的效果是将一个数组中的内容拷贝至另一数组中,并统计源数组中大于0的元素个数。
其对应c语言代码如下
/*
* ncopy - copy src to dst, returning number of positive ints
* contained in src array.
*/
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;
}
Solution
优化核心思想:
- 减少执行的指令数。
- 降低指令间的数据依赖,减少数据冒险。
- 减少控制冒险。
硬件部分初步优化 (pipe−full.hcl)
根据优化核心思想第一点,首先想到的优化是扩展 PIPE 处理器使其支持 iaddq 指令,使得寄存器在做与立即数的加减操作时所需的指令数从2变为1。
结合PartB所做工作,很容易就能对pipe−full.hcl做出以下修改 (同样是四个阶段)
################ Fetch Stage ################################### 取指阶段
## What address should instruction be fetched at
word f_pc = [
# Mispredicted branch. Fetch at incremented PC
M_icode == IJXX && !M_Cnd : M_valA;
# Completion of RET instruction
W_icode == IRET : W_valM;
# Default: Use predicted value of PC
1 : F_predPC;
];
## Determine icode of fetched instruction
word f_icode = [
imem_error : INOP;
1: imem_icode;
];
# Determine ifun
word f_ifun = [
imem_error : FNONE;
1: imem_ifun;
];
# Is instruction valid?
# 将IIADDQ归为合法指令
bool instr_valid = f_icode in
{ INOP, IHALT, IRRMOVQ, IIRMOVQ, IRMMOVQ, IMRMOVQ,
IOPQ, IJXX, ICALL, IRET, IPUSHQ, IPOPQ, IIADDQ };
# Determine status code for fetched instruction
word f_stat = [
imem_error: SADR;
!instr_valid : SINS;
f_icode == IHALT : SHLT;
1 : SAOK;
];
# Does fetched instruction require a regid byte?
# IIADDQ指令包括一个寄存器指示符
bool need_regids =
f_icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ,
IIRMOVQ, IRMMOVQ, IMRMOVQ, IIADDQ };
# Does fetched instruction require a constant word?
# IIADDQ指令包括一个常数字
bool need_valC =
f_icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX, ICALL, IIADDQ };
# Predict next value of PC
word f_predPC = [
f_icode in { IJXX, ICALL } : f_valC;
1 : f_valP;
];
################ Decode Stage ###################################### 译码、回写阶段
## What register should be used as the A source?
word d_srcA = [
D_icode in { IRRMOVQ, IRMMOVQ, IOPQ, IPUSHQ } : D_rA;
D_icode in { IPOPQ, IRET } : RRSP;
1 : RNONE; # Don't need register
];
## What register should be used as the B source?
# IIADDQ中的valB由rB产生,故寄存器ID d_srcB应为D_rB
word d_srcB = [
D_icode in { IOPQ, IRMMOVQ, IMRMOVQ, IIADDQ } : D_rB;
D_icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
1 : RNONE; # Don't need register
];
## What register should be used as the E destination?
# IIADDQ需要将执行结果回写到R[rB]中,故寄存器ID d_dstE的值为D_rB
word d_dstE = [
D_icode in { IRRMOVQ, IIRMOVQ, IOPQ, IIADDQ} : D_rB;
D_icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
1 : RNONE; # Don't write any register
];
## What register should be used as the M destination?
word d_dstM = [
D_icode in { IMRMOVQ, IPOPQ } : D_rA;
1 : RNONE; # Don't write any register
];
## What should be the A value?
## Forward into decode stage for valA
word d_valA = [
D_icode in { ICALL, IJXX } : D_valP; # Use incremented PC
d_srcA == e_dstE : e_valE; # Forward valE from execute
d_srcA == M_dstM : m_valM; # Forward valM from memory
d_srcA == M_dstE : M_valE; # Forward valE from memory
d_srcA == W_dstM : W_valM; # Forward valM from write back
d_srcA == W_dstE : W_valE; # Forward valE from write back
1 : d_rvalA; # Use value read from register file
];
word d_valB = [
d_srcB == e_dstE : e_valE; # Forward valE from execute
d_srcB == M_dstM : m_valM; # Forward valM from memory
d_srcB == M_dstE : M_valE; # Forward valE from memory
d_srcB == W_dstM : W_valM; # Forward valM from write back
d_srcB == W_dstE : W_valE; # Forward valE from write back
1 : d_rvalB; # Use value read from register file
];
################ Execute Stage ##################################### 执行阶段
## Select input A to ALU
# IIADDQ在执行阶段的操作数aluA == E_valC
word aluA = [
E_icode in { IRRMOVQ, IOPQ } : E_valA;
E_icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IIADDQ } : E_valC;
E_icode in { ICALL, IPUSHQ } : -8;
E_icode in { IRET, IPOPQ } : 8;
# Other instructions don't need ALU
];
## Select input B to ALU
# IIADDQ在执行阶段的操作数aluB == E_valB
word aluB = [
E_icode in { IRMMOVQ, IMRMOVQ, IOPQ, ICALL,
IPUSHQ, IRET, IPOPQ, IIADDQ } : E_valB;
E_icode in { IRRMOVQ, IIRMOVQ } : 0;
# Other instructions don't need ALU
];
## Set the ALU function
word alufun = [
E_icode == IOPQ : E_ifun;
1 : ALUADD;
];
## Should the condition codes be updated?
# IIADDQ指令执行结果会更新条件码寄存器
bool set_cc = E_icode in {IOPQ,IIADDQ} &&
# State changes only during normal operation
!m_stat in { SADR, SINS, SHLT } && !W_stat in { SADR, SINS, SHLT };
## Generate valA in execute stage
word e_valA = E_valA; # Pass valA through stage
## Set dstE to RNONE in event of not-taken conditional move
word e_dstE = [
E_icode == IRRMOVQ && !e_Cnd : RNONE;
1 : E_dstE;
];
软件部分优化 (ncopy.ys)
使用的优化技巧为循环展开+多路并行。
循环展开是一种程序变换,通过增加每次迭代计算元素的数量,减少循环迭代次数。
循环展开能从三个方面优化程序性能:
- 它减少了不直接有助于程序结果的操作数的数量,例如循环索引的计算。
- 循环迭代次数减少使得分支预测错误减少。
- 每次迭代计算元素的数量增加,为并行运算提供了机会。
由于使用了循环展开,使得我们在一次循环中,会拷贝多个数组元素,并对多个源数组元素进行判断。
根据优化核心思想第二点,我们可以用不同的寄存器来完成这些数组元素需要进行的操作。
由于使用的是不同的寄存器,这大大降低了指令之间的数据依赖,这样的操作就被称为多路并行。
由于PIPE处理器使用的是五级流水线,这就意味着如果一条指令的操作数被它的前面三条指令中任意一条改变的话,就会出现数据冒险,要想完全避免数据冒险,我们就要每隔三条指令才对某操作数修改。
故我们选用4×4展开,第一个四表示一次循环处理四个元素,第二个四表示我们使用的是四路并行。
我们可以基于4×4展开构思出一定的代码顺序,来达成完全避免数据冒险。
得到的c语言代码如下
word_t ncopy(word_t *src, word_t *dst, word_t len)
{
word_t count = 0;
if(len <= 0)return 0;
word_t rax, r8, r9, r10, r11, r12, r13, r14;
rax = r12 = r13 = r14 = 0;
int i;
for(i = 1;i <= len-3; i += 4){
r8 = *(src);
r9 = *(src + 1);
r10 = *(src + 2);
r11 = *(src + 3);
*(dst) = r8;
*(dst + 1) = r9;
*(dst + 2) = r10;
*(dst + 3) = r11;
if(r8 > 0)
rax++;
if(r9 > 0)
r12++;
if(r10 > 0)
r13++;
if(r11 > 0)
r14++;
src += 4;
dst += 4;
}
len = len - i + 1;
while(len){
r8 = *(src);
*(dst) = r8;
if(r8 > 0)
rax++;
len--;
}
return (rax + r12 + r13 + r14);
}
对应的Y86−64汇编代码如下
#/* $begin ncopy-ys */
##################################################################
# ncopy.ys - Copy a src block of len words to dst.
# Return the number of positive words (>0) contained in src.
#
# zcw-2021214100
#
##################################################################
# Do not modify this portion
# Function prologue.
# %rdi = src, %rsi = dst, %rdx = len
ncopy:
##################################################################
# You can modify this portion
# Loop header
xorq %rax,%rax # count = 0;
andq %rdx,%rdx # len <= 0?
jle Done # if so, goto Done:
xorq %r12,%r12
xorq %r13,%r13
xorq %r14,%r14
irmovq $1,%rcx # save i in %rcx
rrmovq %rdx,%rbp
iaddq $-3,%rbp # save len-3 in %rbp
jmp test1
loop1:
mrmovq (%rdi),%r8
mrmovq $8(%rdi),%r9
mrmovq $16(%rdi),%r10
mrmovq $24(%rdi),%r11
rmmovq %r8,(%rsi)
rmmovq %r9,$8(%rsi)
rmmovq %r10,$16(%rsi)
rmmovq %r11,$24(%rsi)
andq %r8,%r8
jle tag1
iaddq $1,%rax
tag1:
andq %r9,%r9
jle tag2
iaddq $1,%r12
tag2:
andq %r10,%r10
jle tag3
iaddq $1,%r13
tag3:
andq %r11,%r11
jle tag4
iaddq $1,%r14
tag4:
iaddq $32,%rdi
iaddq $32,%rsi
iaddq $4,%rcx # i += 4
test1:
rrmovq %rcx,%rbx # i - (len-3) <= 0?
subq %rbp,%rbx
andq %rbx,%rbx
jle loop1
subq %rcx,%rdx # len = len - i + 1
iaddq $1,%rdx
andq %rdx,%rdx
jmp test2
loop2:
mrmovq (%rdi),%r8
rmmovq %r8,(%rsi)
andq %r8,%r8
jle tag5
iaddq $1,%rax
tag5:
iaddq $8,%rdi
iaddq $8,%rsi
iaddq $-1,%rdx
andq %rdx,%rdx
test2:
jg loop2 # stop when len == 0
addq %r12,%rax # rax + r12 + r13 + r14
addq %r13,%r14
addq %r14,%rax
##################################################################
# Do not modify the following section of code
# Function epilogue.
Done:
ret
##################################################################
# Keep the following label at the end of your function
End:
#/* $end ncopy-ys */
初步测试
规则
我们将以每元素的周期数(CPE)为来表示功能的性能,如果你的平均CPE是c,那么你这部分实验的分数将是S:
S={0,c>10.50 20∗(10.5−c)7.50<=c<=10.50 60c<7.50
结果与反思
由实验指导书archlab.pdf可知,以最初的 pipe−full.hcl 与 ncopy.ys进行测试,得到的平均CPE为15.18
此时我们的平均CPE已经优化到10.47,小成功(
由于本人水平有限,对 ncopy.ys 已经想不出更好的优化方式了。
遂思考PIPE能否进一步优化,发现减少控制冒险这一优化思想还没用上。
硬件部分最终优化 (pipe−full.hcl)
我们可尝试对 PIPE 处理器的预测策略进行修改,进而达到减少控制冒险的目的。
PIPE 的默认预测策略是 “总是选择分支”,我们可以尝试将其改为 “从不选择分支”
对pipe−full.hcl做如下修改
# Predict next value of PC
word f_predPC = [
# "总是选择分支" 策略
# f_icode in { IJXX, ICALL } : f_valC;
# "从不选择分支" 策略
f_icode == ICALL : f_valC;
1 : f_valP;
];
最终测试
将 PIPE 处理器的预测策略修改为”从不选择分支”后得到以下测试结果:
分数拉满!
本人猜测出现该情况是由于测试用例中数组元素大多大于0,契合了汇编代码中不选择分支的情况,故修改预测策略后,预测的结果与实际结果较为吻合,大大减少了控制冒险,进而出现了速度飙升的情况。
可能遇到的问题
在使用 make 来构建一个新的 PIPE 模拟器make VERSION=full
时可能会出现以下报错
# Building the pipe-full.hcl version of PIPE
../misc/hcl2c -n pipe-full.hcl < pipe-full.hcl > pipe-full.c
gcc -Wall -O2 -isystem /usr/include/tcl8.5 -I../misc -DHAS_GUI -o psim psim.c pipe-full.c \
../misc/isa.c -L/usr/lib -ltk8.5 -ltcl8.5 -lm
/tmp/ccU1DUfL.o:(.data.rel+0x0):对‘matherr’未定义的引用
collect2: error: ld returned 1 exit status
Makefile:42: recipe for target 'psim' failed
make: *** [psim] Error 1
解决方案
将 pipe 目录下 psim.c 文件中的
806 extern int matherr();
807 int *tclDummyMathPtr = (int *) matherr;
注释掉即可
帅呆了
帅