凌晨九点的世界
CSAPP深入理解计算机系统 Lab4(architecture Lab) 详解
凌晨九点 Lv2
  2023-10-25 22:51:47   2024-04-12 23:35:52  

本文以记录个人学习CSAPP的过程，使用blog的方式记录能更专注的思考，不至于走马观花式的做实验。同时我关注的不仅是实验本身还有实验中使用工具的学习。

实验说明

在官方网站上其实有两个版本的architecture Lab，这里我们使用的是CSAPP 3e的实验。

本实验通过自己动手写汇编代码，自己设计CPU的执行过程，优化执行过程从而对计算机中CPU执行过程和流水线等知识有更深刻的理解，我认为是目前几个实验中最灵活的一个。

具体实验环境的搭建在实验手册中都有讲解，同时还有一个关于Y86模拟器的使用说明，都在下载的项目目录下有。

特别说明：本实验要求使用Y86的汇编语言，需要参考CSAPP第4章的相关内容学习后再动手编写。

实验具体流程

Part A

根据实验说明，我们需要实现在example.c中三个函数的Y86-64版本的汇编代码，在编写汇编代码前，需要简要梳理一下Y86-64的语法规则，这里建议详细阅读原书的4.1章节，我只对关键部分进行说明：

  1. 通用寄存器有15个(没有%15)
  2. 指令集设计如下图

![指令集](/Users/lcjd/Library/Application Support/typora-user-images/image-20231109164413862.png)

在原书的4.1.5节对一个完整的汇编代码有详细的介绍，这里就不过多说明。在本实验中有一部分代码包括栈的设置、测试数据初始化的部分是共用的代码，我将其写在这里。

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
  .pos 0
  irmovq stack, %rsp
  call main
  halt

  .align 8
ele1:
  .quad 0x00a
  .quad ele2
ele2:
  .quad 0x0b0
  .quad ele3
ele3:
  .quad 0xc00
  .quad 0 
main:
  irmovq ele1, %rdi
  # call the function
  call func
  ret
  
# the positon insert function

  .pos 0x200
stack:

sum.ys

这里需要写一个链表元素值求和的汇编代码，并给出测试数据。具体编写思路只需要按照c代码对应翻译即可

函数部分代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
sum_list:
  irmovq $8, %r8
  irmovq $0, %rax
  andq %rdi, %rdi
  jmp test
loop:
  mrmovq (%rdi), %r10
  addq %r10, %rax
  addq %r8, %rdi
  mrmovq (%rdi), %rdi
  andq %rdi, %rdi
test:
  jne loop
  ret

代码中需要说明的是由于y86_64中没有立即数的加法运算，需要我们将需要运算的数存放在寄存器中再进行寄存器的加法运算。

将这部分代码加入公共代码的部分后结果保存在sum.ys中。调用make sum.yo通过汇编器将代码编译为可执行程序sum.yo，然后调用./yis sum.yo

结果如下

1
2
3
4
5
6
7
8
9
10
11
$ ./yis sum.yo
Stopped in 30 steps at PC = 0x13.  Status 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%rax:   0x0000000000000000      0x0000000000000cba
%rsp:   0x0000000000000000      0x0000000000000200
%r8:    0x0000000000000000      0x0000000000000008
%r10:   0x0000000000000000      0x0000000000000c00

Changes to memory:
0x01f0: 0x0000000000000000      0x000000000000005b
0x01f8: 0x0000000000000000      0x0000000000000013

通过rax的验证我们知道，程序正确执行。

rsum.ys

递归无法像迭代一样完全翻译程序，因为递归程序在汇编代码中需要维护递归栈，但是我们不需要将所有当前变量都保存在栈中，根据需求我们只需要把当前结点的值保存在栈中,因此只需要为每次递归分配8B的空间即可，并和递归调用的返回值相加即可。

函数部分代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
sum_list:
  irmovq $8, %r8
  irmovq $0, %rax
  andq %rdi, %rdi
  jmp test
loop:
  mrmovq (%rdi), %r10
  addq %r10, %rax
  addq %r8, %rdi
  mrmovq (%rdi), %rdi
  andq %rdi, %rdi
test:
  jne loop
  ret

执行同样的测试结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
$ ./yis rsum.yo
Stopped in 48 steps at PC = 0x13.  Status 'HLT', CC Z=0 S=0 O=0
Changes to registers:
%rax:   0x0000000000000000      0x0000000000000cba
%rsp:   0x0000000000000000      0x0000000000000200
%r8:    0x0000000000000000      0x0000000000000008
%r10:   0x0000000000000000      0x0000000000000c00
%r11:   0x0000000000000000      0x000000000000000a

Changes to memory:
0x01c0: 0x0000000000000000      0x000000000000009c
0x01c8: 0x0000000000000000      0x0000000000000c00
0x01d0: 0x0000000000000000      0x000000000000009c
0x01d8: 0x0000000000000000      0x00000000000000b0
0x01e0: 0x0000000000000000      0x000000000000009c
0x01e8: 0x0000000000000000      0x000000000000000a
0x01f0: 0x0000000000000000      0x000000000000005b
0x01f8: 0x0000000000000000      0x0000000000000013

验证rax的结果说明程序正确执行。

copy.ys

这里只需要将三个参数传入即可，执行过程逻辑并不困难。具体代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
main:
  irmovq src, %rdi
  irmovq dest, %rsi
  irmovq $3, %rdx
  call copy_block
  ret

copy_block:
  xorq %rax, %rax
  irmovq $8, %r8
  irmovq $1, %r11
L2:
  andq %rdx, %rdx
  je L3
  mrmovq (%rdi), %r9
  rmmovq %r9, (%rsi)
  subq %r11, %rdx
  xorq %r9, %rax
  addq %r8, %rdi
  addq %r8, %rsi
  jmp L2
L3:
  halt
  ret

测试如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
$ ./yis copy.yo
Stopped in 39 steps at PC = 0xb6.  Status 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%rax:   0x0000000000000000      0x0000000000000cba
%rsp:   0x0000000000000000      0x00000000000001f0
%rsi:   0x0000000000000000      0x0000000000000048
%rdi:   0x0000000000000000      0x0000000000000030
%r8:    0x0000000000000000      0x0000000000000008
%r9:    0x0000000000000000      0x0000000000000c00
%r11:   0x0000000000000000      0x0000000000000001

Changes to memory:
0x0030: 0x0000000000000111      0x000000000000000a
0x0038: 0x0000000000000222      0x00000000000000b0
0x0040: 0x0000000000000333      0x0000000000000c00
0x01f0: 0x0000000000000000      0x000000000000006f
0x01f8: 0x0000000000000000      0x0000000000000013

看到内存中的变化过程和返回值rax的校验码验证实验结果正确。

PartB

这部分的实验是要为SEQ处理器添加一条指令iaddq，这里需要修改hcl文件中的控制逻辑，使其满足需求的功能。这个部分比较容易，因为框架都已经写好，我们只需要将iaddq添加到相应的部分即可。

首先我们需要思考一下iaddq需要实现的动作，根据下图我们看到该指令的构成，对我们解析指令非常重要。

![iddq](/Users/lcjd/Library/Application Support/typora-user-images/image-20231109191110782.png)

我们可以以OPq和irmovq的指令作为案例可以设计出iaddq在各个步骤的执行如下(其中M_x,x表示取xByte)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 <- ValC + ValB
	Set CC
Memory：

Write back:
	R[rB] <- valE
PC update:
	PC <- valP

根据以上可以修改seq-full.hcl

1、在Symbolic representation of Y86-64 Instruction Codes的部分添加如下代码，用于表示这个指令的符号表示。

1
wordsig IIADDQ	'I_IADDQ'

2、然后以此添加IIADDQ到 instr_valid ， need_regids ， need_valC， srcA:rA ， srcB:rB， dstE:rB(second)， aluA:valC，aluB:valB， setcc

添加完后执行如下: ./ssim -t ../y86-code/asumi.yo (记得先在../y86-code目录下make一下)，简单测试后，执行cd ../y86-code; make testssim。结果如下：

![image-20231109195158473](/Users/lcjd/Library/Application Support/typora-user-images/image-20231109195158473.png)

Part3

在这个部分我们需要优化ncopy函数在流水线中的执行效率，我们可以通过修改添加新的指令在系统中，也可以通过修改指令的执行顺序等方式，提供了很大的自由度，这需要我们充分了解计算机系统的指令级优化策略。这个部分也是这次实验的重点。

在没有任何优化时执行./benchmark.pl后的平均时间为15.18，接下来我们就要开始优化这个流水线

1. 添加iaddr

首先可以把Part2中的iaddr，这样可以减少指令数，提升执行效率，修改pipe-full.hcl的过程大同小异，这里就不赘述了，以下是对ncopy.ys的修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
	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 $-1, %rdx		# len--
	iaddq $8, %rdi		# src++
	iaddq $8, %rsi		# dst++
	andq %rdx,%rdx		# len > 0?
	jg Loop			# if so, goto Loop:

经过修改并验证正确性后测试结果为Average CPE 12.70

2. 根据分支修改代码

已知如下：

1
2
3
4
5
# Predict next value of PC
word f_predPC = [
	f_icode in { IJXX, ICALL } : f_valC;
	1 : f_valP;
];

我们知道预测的方向是条件分支，而我们的代码中

  •  C
  1. 实验说明
  2. 实验具体流程
    1. Part A
      1. sum.ys
      2. rsum.ys
      3. copy.ys
    2. PartB
    3. Part3
      1. 1. 添加iaddr
      2. 2. 根据分支修改代码
  1. 实验说明
  2. 实验具体流程
    1. Part A
      1. sum.ys
      2. rsum.ys
      3. copy.ys
    2. PartB
    3. Part3
      1. 1. 添加iaddr
      2. 2. 根据分支修改代码