深 圳 大 学 实 验 报 告
课 程 名 称:
计算机系统(3)
实验项目名称:
处理器结构实验二
学
专
院:
计算机与软件学院
业:
计算机科学与技术
指 导 教 师:
报告人:
学号:
班级:
实 验 时 间:
2017 年 12 月 4 日
实验报告提交时间: 2017 年 12 月 18 日
教务处制
一、实验目的
了解控制冒险分支预测的概念
了解多种分支预测的方法,动态分支预测更要深入了解
理解什么是 BTB(Branch Target Buffer),并且学会用 BTB 来优化所给程序
利用 BTB 的特点,设计并了解在哪种状态下 BTB 无效
了解循环展开,并于 BTB 功能进行对比
对 WinMIPS64 的各个窗口和操作更加熟悉
二、实验内容
按照下面的实验步骤及说明,完成相关操作记录实验过程的截图:
首先,给出一段矩阵乘法的代码,通过开启 BTB 功能对其进行优化,并且观察流
水线的细节,解释 BTB 在其中所起的作用;
其次,自行设计一段使得即使开启了 BTB 也无效的代码。
第三,使用循环展开的方法,观察流水因分支停顿的次数减少的现象,并对比采用
BTB 结构时流水因分支而停顿的次数。
(选做:在 x86 系统上编写 C 语言的矩阵乘法代码,用 perf 观察分支预测失败次
数,分析其次数是否与你所学知识吻合。再编写前面第二部使用的令分支预测失败的代
码,验证 x86 是否能正确预测,并尝试做解释)
三、实验环境
硬件:桌面 PC
软件:Windows
四、实验步骤及说明
背景知识
在遇到跳转语句的时候,我们往往需要等到 MEM 阶段才能确定这条指令是否跳转(通
过硬件的优化,可以极大的缩短分支的延迟,将分支执行提前到 ID 阶段,这样就能够将分
支预测错误代价减小到只有一条指令),这种为了确保预取正确指令而导致的延迟叫控制冒
险(分支冒险)。
为了降低控制冒险所带来的性能损失,一般采用分支预测技术。分支预测技术包含编译
时进行的静态分支预测,和执行时进行的动态分支预测。这里,我们着重介绍动态分支预测
中的 BTB(Branch Target Buffer)技术。
BTB 即为分支目标缓冲器,它将分支指令(对应的指令地址)放到一个缓冲区中保存
起来,当下次再遇到相同的指令(跳转判定)时,它将执行和上次一样的跳转(分支或不分
支)预测。
一种可行的 BTB 结构示意图如下:
深圳大学学生实验报告用纸
在采用了 BTB 之后,在流水线各个阶段所进行的相关操作如下:
注意,为了填写 BTB,需要额外一个周期。
(一) 矩阵乘法及优化
在这一阶段,我们首先给出矩阵乘法的例子,接着将流水线设置为不带 BTB 功能
(configure->enable branch target buffer)直接运行,观察结果进行记录;然后,再开启 BTB
深圳大学学生实验报告用纸
功能再次运行,观察实验结果。将两次的实验结果进行对比,观察 BTB 是否起作用,如果
有效果则进一步观察流水线执行细节并且解释 BTB 起作用原因。
矩阵乘法的代码如下:
.data
str: .asciiz "the data of matrix 3:\n"
mx1:
mx2:
mx3:
.space 512
.space 512
.space 512
.text
initial:
daddi r22,r0,mx1 #这个initial模块是给三个矩阵赋初值
daddi r23,r0,mx2
daddi r21,r0,mx3
input:
daddi r9,r0,64
daddi r8,r0,0
loop1:
dsll r11,r8,3
dadd r10,r11,r22
dadd r11,r11,r23
daddi r12,r0,2
daddi r13,r0,3
sd r12,0(r10)
sd r13,0(r11)
daddi r8,r8,1
slt r10,r8,r9
bne r10,r0,loop1
daddi r16,r0,8
daddi r17,r0,0
daddi r18,r0,0
#这个循环是执行for(int i = 0, i < 8; i++)的内容
daddi r19,r0,0
#这个循环是执行for(int j = 0, j < 8; j++)的内容
daddi r20,r0,0
#r20存储在计算result[i][j]过程中每个乘法结果的叠加值
mul:
loop2:
loop3:
loop4:
dsll r8,r17,6
#这个循环的执行计算每个result[i][j]
dsll r9,r19,3
dadd r8,r8,r9
dadd r8,r8,r22
ld r10,0(r8)
#取mx1[i][k]的值
dsll r8,r19,6
dsll r9,r18,3
dadd r8,r8,r9
dadd r8,r8,r23
ld r11,0(r8)
#取mx2[k][j]的值
dmul r13,r10,r11 #mx1[i][k]与mx2[k][j]相乘
深圳大学学生实验报告用纸
dadd r20,r20,r13 #中间结果累加
daddi r19,r19,1
slt r8,r19,r16
bne r8,r0,loop4
dsll r8,r17,6
dsll r9,r18,3
dadd r8,r8,r9
dadd r8,r8,r21
#计算result[i][j]的位置
sd r20,0(r8)
#将结果存入result[i][j]中
daddi r18,r18,1
slt r8,r18,r16
bne r8,r0,loop3
daddi r17,r17,1
slt r8,r17,r16
bne r8,r0,loop2
halt
不设置 BTB 功能,运行该程序,观察 Statistics 窗口的结果截屏并记录下来。
接着,设置 BTB 功能(在菜单栏处选择 Configure 项,然后在下拉菜单中为 Enable Branch
Target Buffer 选项划上钩)。并在此运行程序,观察 Statistics 窗口的结果并截屏记录下来。
在 这 里 , 我 们 仅 仅 观 察 比 较 Stalls 中 的 最 后 两 项------Branch Taken Stalls 和 Branch
Misprediction Stalls。
接下来,对比其结果。我们就结合流水线执行细节分析造成这种情况发生的原因。
(二)设计使 BTB 无效的代码
在这个部分,我们要设计一段代码,这段代码包含了一个循环。根据 BTB 的特性,我们
设计的这个代码将使得 BTB 的开启起不到相应的优化作用,反而会是的性能大大降低。
提示:一定要利用 BTB 的特性,即它的跳转判定是根据之前跳转成功与否来决定的。
给出所用代码以及设计思路,给出运行结果的截屏证明代码实现了目标。
(三)循环展开与 BTB 的效果比对
深圳大学学生实验报告用纸
首先,我们需要对循环展开这个概念有一定的了解。
什么是循环展开呢?所谓循环展开就是通过在每次迭代中执行更多的数据操作来减小
循环开销的影响。其基本思想是设法把操作对象线性化,并且在一次迭代中访问线性数据中
的一个小组而非单独的某个。这样得到的程序将执行更少的迭代次数,于是循环开销就被有
效地降低了。
接下来,我们就按照这种思想对上述的矩阵乘法程序进行循环展开。要求将上述的代码
通过循环展开将最里面的一个执行迭代 8 次的循环整个展开了,也就是说,我们将矩阵相乘的三个循
环通过代码的增加,减少到了两个循环。
比较,通过对比循环展开(未启用BTB)、使用BTB(未进行循环展开)以及未使用BTB
且未作循环展开的运行结果。比较他们的Branch Tanken Stalls和Branch Misprediction Stalls的
数量,并尝试给出评判。
五、实验结果
一、矩阵乘法及优化
不设置 BTB 功能:
设置 BTB 功能:
原因:
1、 当不设置 BTB 功能时,当遇到分支跳转情况时默认分支不跳转。
loop1 发生了 63 次预测错误,延迟了 63 个时钟周期,直到第 64 次才预测正
确;
loop2 第一层循环发生了 7 次预测错误,延迟了 7 个时钟周期,直到第 8 次(退
出)才预测正确;
loop3 第二层循环每一轮发生了 7 次预测错误,直到第 8 次才预测正确,总共
深圳大学学生实验报告用纸
需要 8 次轮回,共延迟了(7x8)个时钟周期;
loop4 第三层循环每一轮发生了 7 次预测错误,直到第 8 次才预测正确,第一、
第二层循环各需要 8 次,所以共延迟了(7x8x8)个时钟周期。
所以,
Branch Taken Stalls: 574=63(loop1)+7(loop2) +7x8(loop3) +7x8x8(loop4)
2、 当设置 BTB 功能时,
loop1 当发生第一次跳转时(默认不跳转,BTB 中不存在匹配项),预测错误
并将 PC 值和分支目标地址写入 BTB 中,延迟了 2 个时钟周期(Branch Tanken
Stalls+1)。接下来发生了 63 次预测成功跳转的情况,直到第 64 次需要打破循
环造成分支预测错误(清除已取指令,并从另一个分支(即失败处)取指令,
从 BTB 中删除相应项),延迟了 2 个时钟周期(Branch Misprediction Stalls+2);
loop2 当发生第一次跳转时,预测错误并将 PC 值和分支目标地址写入 BTB 中,
延迟了 2 个时钟周期(Branch Tanken Stalls+2)。接下来发生了 7 次预测成功跳
转的情况,直到第 8 次需要打破循环造成分支预测错误,延迟了 2 个时钟周
期(Branch Misprediction Stalls+2);
loop3 当发生第一次跳转时,预测错误并将 PC 值和分支目标地址写入 BTB 中,
延迟了 2 个时钟周期(Branch Tanken Stalls+2)。接下来发生了 7 次预测成功跳
转的情况,直到第 8 次需要打破第二层循环造成分支预测错误,延迟了 2 个
时钟周期(Branch Misprediction Stalls+2)。而二层循环需要进行 8 次,每一次进入第
二层循环都要建立 BTB,退出也要删除 BTB,所以 Branch Tanken Stalls+2x8,Branch
Misprediction Stalls+2x8;
loop4 当发生第一次跳转时,预测错误并将 PC 值和分支目标地址写入 BTB 中,
延迟了 2 个时钟周期(Branch Tanken Stalls+2)。接下来发生了 7 次预测成功跳
转的情况,直到第 8 次需要打破第三层循环造成分支预测错误,延迟了 2 个
时钟周期(Branch Misprediction Stalls+2)。而第一、第二层循环各需要 8 次,所
以 Branch Tanken Stalls+2x8x8,Branch Misprediction Stalls+2x8x8;
所以,
Branch Taken Stalls:148=2(loop1) +2(loop2) +2x8(loop3) +2x8x8(loop4);
Branch Misprediction Stalls:148=2(loop1)+2(loop2)+2x8(loop3)+2x8x8(loop4)
二、设计使 BTB 无效的代码
代码:
.text
daddi r1,r0,0
daddi r2,r0,5
#r1:sum=0
#r2:i=5
loop1:
daddi r2,r2,-1
beqz r2,exit
#i--
#if i=0,exit
深圳大学学生实验报告用纸
daddi r3,r0,2
#r3:j=2
loop2:
daddi r3,r3,-1
beqz r3,loop1
daddi r1,r1,1
#j--
#if j=0,loop1
#sum+=1
j loop2
exit:
halt
设计思路:
伪代码:
sum = 0
for i 5 to 0
for j 2 to 0
sum += 1
i=4,j=0 时,beqz r3,loop1 在 BTB 中没有匹配项,所以将判断结果-跳转,记录
在 BTB 中。这时延迟了 2 个时钟周期。
i=3,j=1 时,beqz r3,loop1 在 BTB 中有匹配项,所以将执行判断结果-跳转;但
是执行到 EX 阶段才发现是不应该跳转的,需要清除已取指令,并从另一个分支
(即失败处)取指令,从 BTB 中删除相应项。这时延迟了 2 个时钟周期。
i=3,j=0 时,beqz r3,loop1 在 BTB 中没有匹配项,所以将判断结果-跳转,记录
在 BTB 中。这时延迟了 2 个时钟周期。
i=2,j=1 时,beqz r3,loop1 在 BTB 中有匹配项,所以将执行判断结果-跳转;但
是执行到 EX 阶段才发现是不应该跳转的,需要清除已取指令,并从另一个分支
(即失败处)取指令,从 BTB 中删除相应项。这时延迟了 2 个时钟周期。。。。
运行结果:
不设置 BTB 功能:
设置 BTB 功能:
深圳大学学生实验报告用纸