CS:APP Lab 4 解题报告

2018-05-13 CSAPP

CSAPP 的第四章《处理器体系结构》大多讲述的是 CPU 的实现,比较偏硬件。大约也是这个原因,很多高校在选用此教材讲述计算机系统导论课程时会直接跳过这一章。与之配套的 Lab 4,Architecture Lab 则更是无人问津。我趁着考完期中的空闲时间,花了近一天时间啃了下第四章,并顺便做了个下这个 Architecture Lab。

Architecture Lab 的主要目标是修改一个 Y86-64 汇编程序写就的函数 ncopy 以及我们使用的流水线 CPU 的 HCL 代码,使之在我们的 Y86-64 处理器上的效率尽量高(CPE(Clocks Per Element) 尽量小)。在这个任务之前,有两个小的任务来帮助我们熟悉相关的操作。

实验前的准备

我们需要一个能用的 Linux 操作系统(笔者使用的是 elementaryOS )。首先我们需要下载最新的实验材料:

1
$ wget http://csapp.cs.cmu.edu/im/labs/archlab.tar

之后对其解压:

1
2
3
$ tar xvf archlab-handout.tar
$ cd archlab-handout
$ tar xvf sim.tar

因为本套件依赖 Tcl/tk,我们需要安装这两个软件:

1
sudo apt install tcl tcl-dev tk tk-dev

因为 Makefile 里写的 tcl 的版本已经比较老了,我们需要修改一下 Makefile:

1
2
$ sed -i "s/tcl8.5/tcl8.6/g" Makefile
$ sed -i "s/CFLAGS=/CFLAGS=-DUSE_INTERP_RESULT /g" Makefile

之后即可正常编译套件了。执行编译:

1
2
$ cd sim
$ make clean; make

Part A - 编写 Y86-64 汇编程序

在这里我们需要做的是将 sim/misc 下的 example.c 内含的三个函数改写成汇编版本的。直接以书上的图 4-7 为样本照猫画虎即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# sum_list.ys by name1e5s
# Execution begins at address 0

.pos 0
irmovq stack,%rsp
call main
halt

# 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

sum_list:
irmovq $0,%rax
jmp test
loop: mrmovq 0(%rdi),%rsi
addq %rsi,%rax
mrmovq 8(%rdi),%rsi
rrmovq %rsi,%rdi
test: andq %rdi,%rdi
jne loop
ret

.pos 0x100
stack:

写完第一个之后我们就可以使用如下指令进行测试辣:

1
2
3
4
5
6
7
8
9
10
$ ./yas sum.ys
$ ./yis sum.yo
Stopped in 29 steps at PC = 0x13. Status 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%rax: 0x0000000000000000 0x0000000000000cba
%rsp: 0x0000000000000000 0x0000000000000100

Changes to memory:
0x00f0: 0x0000000000000000 0x000000000000005b
0x00f8: 0x0000000000000000 0x0000000000000013

输出结果在 %rax 内,直接进行比对即可。
与之类似的,我们可以写出剩下两个函数的 Y86-64 版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# rsum.ys by name1e5s
# Execution begins at address 0

.pos 0
irmovq stack, %rsp
call main
halt

# Sample linked list
.align 8
ele1:
.quad 0x00a
.quad e1e2
e1e2:
.quad 0x0b0
.quad e1e3
e1e3:
.quad 0xc00
.quad 0

main: irmovq ele1, %rdi
call rsum_list
ret


rsum_list:
pushq %r12
irmovq $0, %rax
andq %rdi,%rdi
je re
mrmovq 0(%rdi), %r12
mrmovq 8(%rdi), %rdi
call rsum_list
addq %r12, %rax
re: popq %r12
ret

.pos 0x100
stack:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# cblock.ys by name1e5s
# Execution begins at address 0

.pos 0
irmovq stack, %rsp
call main
halt

.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

copy_block:
pushq %r12
pushq %r13
pushq %r14
irmovq $1, %r13
irmovq $8, %r14
irmovq $0, %rax
jmp Tloop
loop:
mrmovq 0(%rdi), %r12
addq %r14, %rdi
rmmovq %r12, (%rsi)
addq %r14, %rsi
xorq %r12, %rax
subq %r13, %rdx
Tloop:
andq %rdx, %rdx
jg loop
popq %r14
popq %r13
popq %r12
ret

.pos 0x100
stack:

Part B - 添加 iaddq 指令

直接按照 iaddq 的属性在 sim/seq/seq-full.hcl 中特定的位置添加 “IIADDQ” 即可,在此按下不表。

在添加完后,需要对其进行测试,执行如下指令:

1
2
$ make VERSION=full
$ (cd ../ptest; make SIM=../seq/ssim TFLAGS=-i)

如果没有问题,会返回如下结果:

1
All 756 ISA Checks Succeed.

Part C - 优化函数

这里我们要做的就是修改 sim/pipe/pipe-full.hcl 以及 ‘sim/pipe/ncopy.ys’ 的内容。使我们的程序运行效率尽量高。在为 pipe-full.hcl 实现完 iaddq 之后。我们就可以分别使用如下指令测试我们的代码:

1
2
$ ./correctness.pl #结果是否正确
$ ./benchmark.pl #得出效率,分数越高结果越好

笔者的答案如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#/* $begin ncopy-ys */
##################################################################
# ncopy.ys - Copy a src block of len words to dst.
# Return the number of positive words (>0) contained in src.
#
# Include your name and ID here.
#
# Describe how and why you modified the baseline code.
#
##################################################################
# 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
iaddq $-4,%rdx # length -= 4
jl REM

Loop:
mrmovq (%rdi), %r10 # read val from src...
mrmovq 8(%rdi),%r11
rmmovq %r10, (%rsi) # ...and store it to dst
andq %r10, %r10 # val <= 0?
jle Npos # if so, goto Npos:
iaddq $1,%rax
Npos:
rmmovq %r11,8(%rsi)
andq %r11,%r11
jle Npos2
iaddq $1,%rax
Npos2:
mrmovq 16(%rdi),%r10
mrmovq 24(%rdi),%r11
rmmovq %r10, 16(%rsi)
andq %r10,%r10
jle Npos3
iaddq $1,%rax
Npos3:
rmmovq %r11,24(%rsi)
andq %r11,%r11
jle nLoop
iaddq $1,%rax
nLoop:
iaddq $32,%rdi
iaddq $32,%rsi
iaddq $-4,%rdx
jge Loop

REM:
iaddq $3,%rdx
jl Done
mrmovq (%rdi), %r10
mrmovq 8(%rdi),%r11
rmmovq %r10, (%rsi)
andq %r10,%r10
jle RENPO
iaddq $1,%rax
RENPO:
iaddq $-1,%rdx
jl Done
rmmovq %r11,8(%rsi)
andq %r11,%r11
jle RENPO1
iaddq $1,%rax
RENPO1:
iaddq $-1,%rdx
jl Done
mrmovq 16(%rdi), %r10
rmmovq %r10, 16(%rsi)
andq %r10,%r10
jle Done
iaddq $1,%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 */

笔者仅仅使用了两个最基础的优化策略:循环展开和提前为下一个步骤读取内存。这样就可以更好的利用 CPU 的流水线特性。笔者最终的得分是 48.6 分,中规中矩吧(但在网上有关新版 Architecture lab 的博文中也是最高的了(逃 )。如果能为小的样例特殊优化下的话,结果应该能更好。

如果要继续优化的话,尝试修改下 CPU 的流水线策略也许是一个不错的选择。

CSAPP

评论