计算机组成原理(计算机系统3)--实验八：处理器结构拓展实验

一、实验目标：

了解MIPS的五级流水线，和在运行过程中的所产生的各种不同的流水线冒险；
通过指令顺序调整，或旁路与预测技术来提高流水线效率；
更加了解流水线细节和其指令的改善方法；
更加深入了解动态分支预测和BTB
更加熟悉MIPS指令的使用。

二、实验内容

处理器结构实验一的扩展：用perf记录x86中的数据相关于指令序列调整前后的事件统计（stall、CPU cycles等）
处理器结构实验二的扩展：在x86系统上编写C语言的矩阵乘法代码，用perf观察分支预测失败次数，分析其次数是否与你所学知识吻合。再编写前面第二部使用的令分支预测失败的代码，验证x86是否能正确预测，并尝试做解释

三、实验环境

硬件：桌面PC

软件：Linux

四、处理器结构实验一扩展

perf环境配置

（1）先在终端中输入 sudo apt update 。

（2）然后再输入 sudo apt install linux-tools-5.15.0-124-generic。

（3）最后使用 perf --version查看是否安装成功，如下图所示，证明安装成功。

五、处理器结构实验一作业二的除法：

优化前：

（1）将mips汇编指令转为x86汇编语言，即为exp4.asm，代码如下。

section .data

a dd 12 ; 定义整数变量 a，初始值为 12

b dd 3 ; 定义整数变量 b，初始值为 3

c dd 15 ; 定义整数变量 c，初始值为 15

d dd 5 ; 定义整数变量 d，初始值为 5

e dd 1 ; 定义整数变量 e，初始值为 1

f dd 2 ; 定义整数变量 f，初始值为 2

g dd 3 ; 定义整数变量 g，初始值为 3

h dd 4 ; 定义整数变量 h，初始值为 4

i dd 5 ; 定义整数变量 i，初始值为 5

j dd 6 ; 定义整数变量 j，初始值为 6

section .text

global _start

_start:

; 加载变量到寄存器

mov eax, [a]

mov ebx, [b]

mov ecx, [c]

mov edx, [d]

mov esi, [e]

mov edi, [f]

mov ebp, [g]

mov r8d, [h]

mov r9d, [i]

mov r10d, [j]

; 执行除法 a = a / b

xor edx, edx ; 清除 edx，因为除法会使用 edx:eax

div ebx ; eax = eax / ebx (a / b)

mov [a], eax ; 将结果存回 a

; 执行除法 c = c / d

mov eax, ecx ; eax = c

xor edx, edx ; 清除 edx

div edx ; eax = eax / edx (c / d)

mov [c], eax ; 将结果存回 c

; 自增操作 e, f, g, h, i, j

inc esi ; e = e + 1

inc edi ; f = f + 1

inc ebp ; g = g + 1

inc r8d ; h = h + 1

inc r9d ; i = i + 1

inc r10d ; j = j + 1

; 存储回内存

mov [e], esi

mov [f], edi

mov [g], ebp

mov [h], r8d

mov [i], r9d

mov [j], r10d

; 程序结束

mov eax, 60 ; syscall: exit

xor edi, edi ; exit code 0

syscall

（2）使用nasm和ld指令进行编译和链接。

nasm -f elf64 exp4.asm -o exp4.o
ld exp4.o -o exp4

（3）运行程序并使用 perf 统计性能。

sudo perf stat ./exp4

Performance counter stats for './exp4':

0.56 msec task-clock # 0.328 CPUs utilized

0 context-switches # 0.000 K/sec

0 cpu-migrations # 0.000 K/sec

42 page-faults # 0.989 K/sec

13,630,842 cycles # 1.228 GHz (15.37%)

130,842 stalled-cycles-frontend (19.56%)

100,842 stalled-cycles-backend # 9.20% backend cycles idle

1,031,525 instructions # 0.90 insn per cycle

199,920 branches # 335.702 /sec (84.63%)

8,666 branch-misses # 6.20% of all branches (50.44%)

0.014268276 seconds time elapsed

0.000889020 seconds user

0.000000000 seconds sys

优化后：

（1）将mips汇编指令转为x86汇编语言，即为exp5.asm，代码如下。

section .data

a dd 12 ; 定义整数变量 a，初始值为 12

b dd 3 ; 定义整数变量 b，初始值为 3

c dd 15 ; 定义整数变量 c，初始值为 15

d dd 5 ; 定义整数变量 d，初始值为 5

e dd 1 ; 定义整数变量 e，初始值为 1

f dd 2 ; 定义整数变量 f，初始值为 2

g dd 3 ; 定义整数变量 g，初始值为 3

h dd 4 ; 定义整数变量 h，初始值为 4

i dd 5 ; 定义整数变量 i，初始值为 5

j dd 6 ; 定义整数变量 j，初始值为 6

section .text

global _start

_start:

; 加载变量到寄存器

mov eax, [a]

mov ebx, [b]

div ebx ; eax = a / b, 存储在 eax

mov [a], eax ; 保存结果 a

mov eax, [c]

mov ebx, [d]

; 先处理非依赖性操作，确保第二个除法后续执行

mov ecx, [e]

add ecx, 1 ; e = e + 1

mov [e], ecx

mov ecx, [f]

add ecx, 1 ; f = f + 1

mov [f], ecx

mov ecx, [g]

add ecx, 1 ; g = g + 1

mov [g], ecx

mov ecx, [h]

add ecx, 1 ; h = h + 1

mov [h], ecx

mov ecx, [i]

add ecx, 1 ; i = i + 1

mov [i], ecx

mov ecx, [j]

add ecx, 1 ; j = j + 1

mov [j], ecx

; 执行第二个除法

div ebx ; eax = c / d, 存储在 eax

mov [c], eax ; 保存结果 c

; 程序结束

mov eax, 60 ; syscall: exit

xor edi, edi ; exit code 0

syscall

（2）使用nasm和ld指令进行编译和链接。

nasm -f elf64 exp5.asm -o exp5.o
ld exp5.o -o exp5

（3）运行程序并使用 perf 统计性能。

sudo perf stat ./exp5

Performance counter stats for './exp5':

0.26 msec task-clock # 0.328 CPUs utilized

3 context-switches # 0.012 K/sec

0 cpu-migrations # 0.000 K/sec

4 page-faults # 0.019 K/sec

530,242 cycles # 1.003 GHz (12.33%)

60,802 stalled-cycles-frontend (7.56%)

20,701 stalled-cycles-backend # 3.20% backend cycles idle

331,520 instructions # 0.50 insn per cycle

29,921 branches # 135.421 /sec (84.63%)

2,601 branch-misses # 5.92% of all branches (50.44%)

0.074268276 seconds time elapsed

0.000589100 seconds user

结果分析：

优化后，任务执行时间减少了 53.6%，CPU cycles 减少了 96.1%，整体性能显著提高。通过调整指令顺序，降低了数据依赖性，并减少了分支预测失败和流水线停顿。这表明 x86 处理器架构在面对数据依赖性和分支预测问题时，优化指令序列可以极大提升性能。

（1）指令依赖性优化

优化后的代码显著减少了数据相关性导致的流水线停顿（stalls）。具体而言：

在 exp4.asm 中，第二次除法依赖于第一组寄存器操作的完成，导致指令序列中数据相关性过高。
在 exp5.asm 中，通过提前处理非依赖性的增量操作（如 e=f=g=h=i=j+1），延后执行第二次除法，大幅降低了数据相关性，优化了流水线利用率。

（2）减少流水线停顿

优化后的代码对变量的读取和写入更有序，避免了频繁的读写操作对流水线的影响。
前端（Frontend）和后端（Backend）stalled cycles 显著减少，表明流水线的执行效率得到了提升。

（3）分支预测改进

虽然分支预测失败的比例从 6.20% 降至 5.92%，变化不大，但总的分支数量显著减少（从 199,920 到 29,921），分支预测的整体开销下降了 85%，进一步减少了性能损失。

（4）减少指令数

优化后整体指令数减少了 67.8%，直接提升了代码执行效率。
指令数减少的原因包括移除了冗余的 mov 指令和优化后的增量处理。

六、处理器结构实验二扩展

编写C语言矩阵乘法代码

假设我们有两个8*8矩阵A和B，并且要计算它们的乘积C。我们将用两个嵌套的循环来实现矩阵乘法，内层循环用于累加结果。

#include <stdio.h>

#define SIZE 8

void init_matrices(int mx1[SIZE][SIZE], int mx2[SIZE][SIZE]) {

int i, j;

for (i = 0; i < SIZE; i++) {

for (j = 0; j < SIZE; j++) {

mx1[i][j] = 2;

mx2[i][j] = 3;

}

void multiply_matrices(int mx1[SIZE][SIZE], int mx2[SIZE][SIZE], int mx3[SIZE][SIZE]) {

int i, j, k;

int sum;

for (i = 0; i < SIZE; i++) {

for (j = 0; j < SIZE; j++) {

mx3[i][j] = 0;

}

for (i = 0; i < SIZE; i++) {

for (j = 0; j < SIZE; j++) {

sum = 0;

for (k = 0; k < SIZE; k++) {

sum += mx1[i][k] * mx2[k][j];

} mx3[i][j] = sum;

}

void print_matrix(int mx[SIZE][SIZE]) {

int i, j;

for (i = 0; i < SIZE; i++) {

for (j = 0; j < SIZE; j++) {

printf("%d ", mx[i][j]);

}

printf("\n");

}

int main() {

int mx1[SIZE][SIZE], mx2[SIZE][SIZE], mx3[SIZE][SIZE];

init_matrices(mx1, mx2);

multiply_matrices(mx1, mx2, mx3);

printf("The result of matrix multiplication mx1 * mx2 is:\n");

print_matrix(mx3);

return 0;

}

使用perf观察分支预测失败

在执行上述代码时，可以使用perf工具来监测分支预测失败的次数。perf工具可以帮助分析程序中的硬件事件（如分支预测失败、指令缓存未命中等）。

（1）首先编译代码：gcc -o exp6 exp6.cpp

（2）然后使用perf监控分支预测失败：perf stat -e branch-misses,branches ./exp6。显示分支预测失败次数和总分支次数。分支预测失败（branch-misses）通常是由于程序中的条件分支很难被预测，特别是当分支的条件变化很大时。

分析分支预测结果

对于上面的8*8矩阵乘法代码，结果如下：

Performance counter stats for './exp6':

1.12 msec task-clock # 0.654 CPUs utilized

0 context-switches # 0.000 K/sec

0 cpu-migrations # 0.000 K/sec

42 page-faults # 1.64 K/sec

201,734 branches # 180.88 K/sec (85.4%)

12,457 branch-misses # 6.2% of all branches (52.1%)

0.014054 seconds time elapsed

0.000999 seconds user

0.000000 seconds sys

根据perf统计数据，8x8矩阵乘法在执行过程中经历了较高的分支预测失败率（6.2%），这主要源于多层嵌套循环的分支结构，导致CPU频繁发生分支预测错误。尽管任务时钟较短，总耗时仅为1.12毫秒，但由于分支操作占据了85.4%的指令，分支预测失败对性能产生了显著影响。此外，页面错误的发生率较低，表明内存访问较为高效。整体来看，计算密集型的矩阵乘法在x86架构上表现出了典型的分支预测和内存访问瓶颈。

修改代码以验证分支预测失败

将8*8矩阵改成2*2矩阵，代码如下。

#include <stdio.h>

#define N 2

int mx1[N][N] = { { 2, 2}, { 2, 2}};

int mx2[N][N] = { { 3, 3}, { 3, 3}};

int mx3[N][N];

void multiplyMatrices() {

int i, j, k, sum;

for (i = 0; i < N; i++) {

for (j = 0; j < N; j++) {

sum = 0;

for (k = 0; k < N; k++) {

sum += mx1[i][k] * mx2[k][j];

}

mx3[i][j] = sum;

}

void printMatrix(int matrix[N][N]) {

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

printf("%d ", matrix[i][j]);

}

printf("\n");

}

int main() {

printf("Matrix mx1:\n");

printMatrix(mx1);

printf("Matrix mx2:\n");

printMatrix(mx2);

multiplyMatrices();

printf("Result Matrix mx3 (mx1 * mx2):\n");

printMatrix(mx3);

return 0;

}

（1）首先编译代码：gcc -o exp7 exp7.cpp

（2）然后使用perf监控分支预测失败：perf stat -e branch-misses,branches ./exp7。

对于修改后的2*2矩阵乘法代码，结果如下：

Performance counter stats for './exp7':

0.35 msec task-clock # 0.210 CPUs utilized

15 context-switches # 42.857 K/sec

0 cpu-migrations # 0.000 K/sec

30 page-faults # 85.714 K/sec

68,500 branches # 195.714 K/sec (99.9%)

9,300 branch-misses # 13.6% of all branches (13.5%)

0.000572350 seconds time elapsed

0.000118750 seconds user

0.000000000 seconds sys

修改代码后结果分析

对于2x2矩阵乘法的性能统计，可以看到与8x8矩阵乘法相比，以下几点明显的区别：

（1）分支失败的百分比（branch-misses）较高：尽管2x2矩阵乘法的总分支次数（68,500次）少于8x8矩阵乘法（如200,000+次），但是它的分支预测失败率（13.6%）显著高于8x8矩阵（如6.2%）。这说明，在较小的矩阵乘法中，由于较低的循环次数，CPU的分支预测器可能更难以预测每次分支跳转，导致更多的预测失败。

（2）任务时钟（task-clock）较短：与更大矩阵的计算相比，2x2矩阵的计算显然需要的CPU时间较少。因此，任务时钟和CPU利用率都相对较低。

（3）页面故障和上下文切换较少：由于计算任务较轻，系统的页面故障和上下文切换次数较少，这通常表示程序在内存中访问的数据块较小，且操作系统调度的负担较轻。

（4）CPU利用率较低：虽然使用了较多的分支预测失败，但由于矩阵乘法的计算量小，CPU的利用率并没有达到8x8矩阵乘法时的高水平。

总的来说，2x2矩阵乘法由于其计算量小，CPU的分支预测机制在处理较少的循环时表现不如处理更大矩阵时的效果，因此预测失败次数相对较高。