<csapp> pipeline lab （《深入理解计算机系统》lab7）

好久没更新了。。最近也是比较懒。。一直没有更新。。

好了现在开始慢慢更一下。

lab7 说明及要求pdf ：地址点我 可以直接在界面里下载

lab7 po主解答代码包括文件包：地址点我

好了进入正题

-------------------------------------------------------------------------------------------------------------------------------------

这个pipeline lab分3part。

partA主要是个warm up，将三个c语言代码片段改写为汇编语言，主要考察正确性。这部分很简单。。

partB实现了一个sequencial processor，也就是顺序的处理器，不存在流水线行为。这部分较为简单。

partC是先实现一个pipeline processor 然后在修改一个多重复制的汇编代码使其更加适合你所写的pipeline processor，最终要求是使你的processor能以一个较低的CPE处理ncopy这个多重复制代码程序，具体要求详见pdf，理论上是cpe越低说明你的pipeline processor的性能越高，和你所修改的ncopy 的汇编代码更加契合(在不使用作弊手段的情况下)。

接下来就具体看一下这三个部分。

--------------------------------------------------------------------------------------------------------------------------------------

PART A:

三段C代码都是很简单的， 都可以在PDF中找到。

只要了解汇编代码一些具体的简单用法就可以将这部分很简单的完成。

下面以其中一段代码的为例进行说明：

1 /* linked list element */
2 typedef struct ELE {
3 int val;
4 struct ELE *next;
5 } *list_ptr;
6
7 /* sum_list - Sum the elements of a linked list */
8 int sum_list(list_ptr ls)
9 {
10 int val = 0;
11 while (ls) {
12 val += ls->val;
13 ls = ls->next;
14 }
15 return val;
16 }
           

简单分析一下，这段代码首先定义了一个数字链表，然后是做了一个将计算一个实例数字链表中的所有数字之和并返回这个和值运算的函数。

然后看一下具体说明，得到了链表的具体内容是

ele1:

.long 0x00a

.long ele2

ele2:

.long 0x0b0

.long ele3

ele3:

.long 0xc00

.long 0

就是共有三个数字，我们的汇编程序也就同这样就可以。

那么我们开始进行转换。

init:           irmovl 0x100,%esp       传入初始栈、帧位置
                irmovl 0x100,%ebp
                irmovl ele1,%eax	传入链表的第一个元素地址
                pushl %eax<span style="white-space:pre">		</span>压栈
                call sum_list<span style="white-space:pre">		</span>调用函数
                halt
sum_list:       pushl %ebp
                rrmovl %esp,%ebp
                mrmovl 8(%ebp),%ebx<span style="white-space:pre">	</span>ebx寄存器中放置链表下一个元素的地址
                irmovl 0,%eax<span style="white-space:pre">		</span>eax寄存器中存放和值
                andl %ebx,%ebx<span style="white-space:pre">		</span>如果链表下个为0那么说明该链表已经到头，退出循环
                je done
loop:           mrmovl (%ebx),%ecx<span style="white-space:pre">	</span>取出当前链表位置的元素值
                addl %ecx,%eax<span style="white-space:pre">		</span>加到和值eax寄存器中
                mrmovl 4(%ebx),%ebx
                andl %ebx,%ebx
                jne loop
done:            rrmovl %ebp,%esp
                popl %ebp
                ret<span style="white-space:pre">			</span>还原栈状态并返回
           

其他两个函数也类似这个，很简单，具体可以看文件包中的代码，在此处就不赘述。

-------------------------------------------------------------------------------------------------------------------------------------

PART B：

这部分主要使用简单的HCL语言完成一个sequencial processor 。HCL语言即是硬件控制语言，这个lab虽然依赖HCL语言完成但是并不要求很深的应用，不了解的可以通过查看seq-full.hcl中提供的部分进行简略的了解或者查询相关资料。这部分代码已经提供了基本所有功能的实现，需要我们添加iaddl, ileave两个功能即可。

二者的流程图如下，依照其在每个阶段的功能相应添加到提供的代码中即可，很简单。

## iiaddl:
## F:    icode:ifun<-M1[PC]
##       rA:rB<-M1[PC+1]
##       valC<-M4[PC+2]
##       valP<-PC+6
## D:    valB<-R[rB]
## E:    valE<-valB+valC
## M:
## W:    R[rB]<-valE
## U:    PC<-valP
##############################
##ileave:
## F:    icode:ifun<-M1[PC]
##       valP<-PC+1
## D:    valA<-R[%ebp]
##       valB<-R[%ebp]
## E:    valE<-valB+4
## M:    valM<-M[valA]
## W:    R[%esp]<-valE
##       R[%ebp]<-valM
## U:    PC<-valP
           

具体完成实现详见解答seq-full.hcl。

-------------------------------------------------------------------------------------------------------------------------------------

PART C:

这部分相当于前两部分的一个综合，难度大有提高。

在这部分中我们要做的是两个任务，第一是完善pipe-full.hcl文件，也就是使用HCL语言实现一个pipeline processor。第二是要优化ncopy.ys文件，也就是使用一些优化手段对给出的最简单的ncopy函数的汇编语言实现进行优化，使在执行ncopy函数时能尽可能少的减少CPE，也就是使运行这个程序的circle数尽可能少。

我个人的实现方式，也是我的建议就是先进行对ncopy.ys文件的优化，然后再根据优化后的实现来完善pipeline processor，并且在完善的过程中可以根据临时的需要修改ys文件。

对于pipeline processor的具体说明以及示意图可以在我的代码文件包里查看simguide.pdf文件。

那么我们就先来看ncopy的优化。

给出的ncopy函数的汇编实现是很简单的实现，就是将C语言函数改写了一下的形式，而这样的汇编写法在循环、判断跳转(jmp)、函数返回(ret)时都会有较多bubble出现，越多bubble就代表越高的cpe，那么我们的任务就是在完成解决所有的hazard的同时尽可能的修改这三种情况，减少stall & bubble的情况。修改这三种情况可以从修改ncopy的汇编代码入手也可以通过修改pipe-full.hcl文件，一般来说二者要结合起来修改。

我们对应的处理这三种情况，应对循环造成的circle浪费我们采取“循环展开”的方法，也就是例如对于原来每次循环执行一个复制操作，需要循环执行64次，我们就在汇编语言中采取手动写出每次循环情况的方法，比如写出16次循环情况，那么就只需要循环4次即可。注意，这里对ncopy,ys的大小存在限制，这也就说明我们不能无限展开，在这里我选择了展开16次循环，这一步可以减少近4的CPE。这一步主要修改ncopy.ys文件即可。

应对判断跳转由于具体实现较为复杂，这里在我写完其他优化发现已经足够满分了之后就没有再写，我这里说一下思路，就是在判断跳转时，processor会发生预测的情况，而如果预测失败就会造成较大的浪费。而判断语句在encode阶段可得到是否跳转的结果，那么我们就可以选择修改一下汇编代码。原来的判断跳转是判断语句后直接跟跳转语句，那么我们根据分析进行修改，将判断语句提前，使得判断语句和跳转语句之间隔了两个其他语句（这两个语句不能造成其他的预测跳转，数值计算情况！），那么这两个语句之间就隔了2个circle，也就使得跳转语句能直接拿到正确的判断结果，这样就可以使每次跳转都是正确的，减少了预测失败的损失。

应对函数返回的情况，第一我们可以完善并使用在PARTB中用到的ileave语句减少栈操作的消耗，第二在"pushl ****  -> ret "这样的语句形式中，在ebp寄存器中存储的地址值就是ret操作返回的值，那么我们就可以相应的修改自己的pipeline processor 来减少ret时的bubble(From 3 to 1)。

另外还需要注意完成对hazard情况的处理，例如ret hazard， l/u hazard等。

这里我把具体的思路都说明清楚了，代码中也有很详细的注释，这里就不一一详述代码了，具体代码还请在上面下载我的代码包对照查看。

---------------------------------------------------------------------------------------------------------------------------------------------

大家有什么具体的问题可以私信我，在我能力范围内必将一一解答。

前一段时间比较忙，没有及时回复大家，还请见谅。

stone

1/26/2015