基于MIPS的流水线技术数据冒险转发策略研究

摘要：流水线技术是计算机加快处理指令的经典策略之一，迄今为止，几乎所有的计算机都采用了流水线技术来加速其中央处理器（CPU）的处理速度。然而，做到处理器的加速绝非轻而易举，流水线技术虽然巧妙地大幅提高了处理器的速度，但是这其中也包含着许多影响计算大局的关键问题，数据冒险就是其中一类。该文探究了数据冒险中数据被提前使用所带来的问题，并分析了专门针对此问题所用到的数据转发策略。

关键词：流水线技术；MIPS；数据冒险；转发策略

中图分类号： TP311 文献标识码： A 文章编号：1009-3044（2013）13-2946-05

流水线技术可以说是计算机制造艺术中的降龙十八掌，威力巨大而不失优雅的思想，就目前的计算机发展条件来说，其是提高处理器处理速度的关键。

简单来说，流水线技术是一种可以将多条指令的执行过程相互重叠的实现技巧。

让我们来从现实生活中举个例子，例如一位一级大厨在厨房做菜，一般来说，假设他可以将做菜分为以下四个步骤：

1） 在摆满了原材料的台子前挑选做菜的材料；

2） 在水池中清洗挑选出来的材料；

3） 一级厨师使用他眼花缭乱的技术进行炒菜；

4） 厨师炒完菜后将菜不紧不慢地送达客户的桌上。

对于一位厨师以及少量的客人来说，上述步骤似乎没有设么问题，我们的一级厨师只要专心地炒他的菜即可，仅有的几个客人也只需耐心地小等一会便可吃上美味佳肴。

然而，当客人变得多起来，情况就比较糟糕了，比如有1000个客人，厨师一个接一个地为客人炒菜就显得耗时太多了，总有看上去多的可怕的客人在抱怨等待时间太长，于是，这位可怜的厨师只好一边听着客人不耐烦的抱怨一边手忙脚乱的炒菜。

同样，不只是厨师会碰到这种棘手的事，每秒处理几亿计算的计算机也是任务艰巨，倘若只有少得可怜的CPU的计算机只是呆板的一个接一个地处理繁杂的计算任务，那计算机的响应时间就会被大幅拖长，其交互性就会大打折扣，客户很可能会因此对计算机失去信心。

不过幸运的是，流水线技术的出现很好地提高了CPU的处理速度。但是好事多磨，流水线技术在发展的过程中本身也包含着众多问题。

下面，就让我们结合MIPS汇编语言来分析一下流水线技术中的一种数据冒险问题，并分析一下专门应对此问题的数据转发策略。

1 流水线技术简介及数据冒险问题探究

1.1 流水线技术简介

正如概述中所述的，流水线技术是一种可以将多条指令的执行过程相互重叠的实现技巧。

可以就我们前面所举的一级厨师的例子来说明这个技巧的原理。

在概述中，厨师的做菜过程有四个步骤，简化来说即挑选材料、清洗材料、炒菜和上菜。若只有一个专门的厨师，则该厨师只能按部就班地一步一步来。

假设突然之间，厨师所在的餐馆富裕了，于是餐馆给厨师请了三个助手，一个是专门选原材料的材料师，一个是专门洗菜的，最后一个则是一个帅气的服务员，专门负责上菜，于是，厨师就可以一直待在灶台前专心地挥动锅铲进行炒菜这一单独事件。

按如上所述的情况，餐馆将会大有改观。假设以上的四个人很勤奋，一刻不停地坚守岗位，挑菜的一刻不停地在选材料，洗菜的一刻不停地清洗前面传到手中的菜，我们的一级大厨则不停地炒送过来的菜，最后服务员矜矜业业地不断为客人送上从厨房传来的菜。

现在的情况比起只有一个人不停地重复全部事情要好不少，假设以上四个步骤所花的时间是相同的，每个步骤花费一个单位时间，则在一个人的情况下，要每过四个单位时间才能搞定一个菜，但是在四个人各司其职的情况下，除了前三个单位时间没有菜被炒好外，以后每过一个单位时间便会有菜被炒好。这在要执行很多任务时会将速度加快不少，按上述描述，我们假设现在有八个单位时间，则一个人做完全部事情则只能抄完两个菜，倘若有四个人，则会炒好五个菜，在炒菜任务更多的情况下，这种加速就更可观了。

对于计算机处理指令来说，也可以用相同的技巧。

值得注意的是，MIPS汇编指令总是按照以上五个步骤的执行时间来运行，虽然有些MIPS汇编指令只会进行其中的四个或三个步骤，但是为了流水线技术的方便，这些指令也会运行五个单位执行时间，在多余的单位执行时间里，这些指令便什么都不做。

根据前文所述，计算机会将指令分为五个步骤执行，于是，使用流水线技术，这两条指令将会如下被执行：

1） 计算机从储存器中读取第一条指令；

2） 计算机在将第一条指令进行译码的同时从储存器中读取第二条指令；

3） 计算机执行将100加至$0储存的数据上，同时对第二条指令进行译码；

4） 计算机根据第一条指令而得出的储存地址读取数据，同时将600加至$0储存的数据上；

5） 计算机将执行第一条指令得到的数据存入寄存器$1中，同时读取由第二条指令指使的储存器地址；

6） 计算机将执行第二条指令而得的数据存入寄存器$2中，两条指令执行完毕。

二者亲密无间的配合可以用下图形象地说明：

在这里实际上只有一条执行线，图中画了两条是便于说明流水线技术。在第一个单位执行时间里，计算机会读取第一条指令；然后在第二个单位执行时间里，计算机会读取第一条指令中所指示的寄存器的值，同时由于第一条指令已经被读取指令完毕，所以读取指令的部分变得空闲，计算机便同时在第二个单位执行时间里读取第二条指令；然后如图所示，计算机进入了第三个单位执行时间，第一条指令的地址相加开始计算，同时第一条指令的寄存器数据被读取完毕，读取寄存器的部分已空闲，于是第二条指令所指示的寄存器会被计算机读取，同样，读取指令的部分也已读完了第二条指令，变的空闲，此时，若有第三个指令，计算机便会在处理第一、二条指令相关步骤的同时读取第三条指令。第四、第五个单位执行时间里计算机所做的事情也跟上文中叙述的一样，在这就不赘述。

根据上面的执行步骤可以看出，流水线技术会和谐流畅地运行每一条由MIPS汇编指令生成的五步中的每一个原子步骤，这比执行完一条指令后再执行下一条指令要快，比如上面的两条指令就用了6个步骤，只用6个单位执行时间，而一条一条地执行会花费8个单位执行时间，当指令更多时，差距会更大。

但是仅仅做到这里就可以了吗？毫无疑问，目前的情况是漏洞百出，数据冒险问题便是破绽之一。

1.2 数据冒险问题探究

在前面的叙述中，计算机用流水线技术连续执行两条指令似乎毫不费力，没有出现什么问题，然而，必须看到一个重要的事实，那就是前面作为例子的指令中相互之间没有修改寄存器的数据，一旦后面的指令在前一条指令还没有执行结束之前便修改了前一条指令的数据，问题就来了。

但是在计算机的实际操作中却并非如此，因为我们使用了流水线技术。

现在在流水线技术的背景下来重新考虑此问题。对于这两条指令，计算机会像前文中描述的那样，将每个指令分为五个步骤来执行。

问题就在这，在第三个单位时间，寄存器$12中的数值是什么呢？在这个时候，由$1和$2相加的结果还没有来得及被写入$12中，此时$12中可能是上一次执行指令而留下来的任何数据，由此，本来第二条指令是指望使用$1和$2相加的结果，但最后寄存器$16却得到了错误的结果。

如上所述的只是两条MIPS汇编指令的执行情况，在实际操作中，指令是数以亿计的，出现错误的情况会多得多，也更复杂，这便是数据冒险问题中的最主要一种。

那么，对于这种数据冒险情况，应该如何解决呢？

2 数据冒险的转发数据解决方案

正如前文所述，数据冒险问题是一个影响计算机计算的主要罪魁祸首之一。

这种数据冒险情形可以对症下药。

2.1 数据冒险问题转发数据解决方案探究

现在事已至此，似乎这类数据冒险问题已经被很好地解决了。但是还应该解决一个问题，那就是如何检测此类数据冒险问题。

2.2 转发型数据冒险问题的检测

正如上文2.1里所述，计算机必须能检测到数据转发型的数据冒险问题，因为在流水线中，并非所有的指令都会产生这个问题。

那么，什么样的指令会产生这个问题呢？

上文中已经举出来一种情况了，即在流水线的过程中，假设有一条指令处在本身的第三个单位执行时间里，假设这个时间对于计算机来说为第N个单位执行时间，现在下一条指令会用到这条指令中最后所写入的寄存器的值，那么这就产生数据冒险问题。这如何进行检测呢？可以看到，在流水线的过程中，在这第N个单位执行时间中，计算机在用累加器进行计算的同时，还会对下一条指令进行译码并读取下一条指令中所指示的寄存器的值，因此，可以在这个时刻对上下两条指令进行检测，若其中有涉及到对相同的寄存器的修改，那便可以判断出这需要使用数据转发策略。实现这种检测不是很困难，因为MIPS指令每一条都有单独的二进制码，并且寄存器也有单独的编号，检测起来可以说完全不费吹灰之力。

除此之外，这种数据冒险还会在其他情况下会产生。

在上文中，我们的流水线只是有两条指令，倘若是一个宏大的流水线，又会如何呢？这时，计算机的五个处理步骤就会一刻不停地处理源源不断而来的原子步骤。

在源源不断的情况下，若接下来的第3、4或者第5条指令会用到某条指令修改的寄存器，情况又会如何呢？

根据流水线的过程，可以看到，当一条指令进入其本身的第三个步骤时，在第三个步骤末期，计算的结果会出来，还是假设这个单位执行时间为计算机中第N个单位执行时间。同时，下一条指令将会在第N+1个单位执行时间用到计算的结果。现在再往下看，接下来的第三、四、五条指令现在也会用到这个结果。根据流水线的过程，第三条指令将会在第N+2个单位执行时间用到该结果，此时对于第一条指令来说，刚进入其本身的第五个步骤，此时寄存器的内容会在这个时期的开始阶段被改变，但是第三条指令会在第N+1个单位执行时间里读取寄存器的值，因此在第N+2个单位执行时间里第三条指令急于求成地使用寄存器的值也会出错，因此，有必要给第三条指令也加根线；而对于第四条指令，则会在第N+3个单位时间用到计算的结果，不过第四条指令会在第N+2个单位时间的末期读取寄存器的值，此时第一条指令已在这个时间的开始阶段就将结果写入寄存器了，并且，对于第五条指令及以后的指令，再使用这个被修改的寄存器已无多大障碍，因为这已经是在第N+2个单位执行时间以后了，第一条指令早已不在流水线中，寄存器的值大局已定，完全可以被利用了。

因此，最终只需再加上检测第三条指令是否会用到被修改的寄存器便可，传送数据再加上一根从写入寄存器堆的数据总线引出到累加器的线便可。

到这里，数据转发型的数据冒险情况就可以完全被掌控了。

2.3 数据转发型数据冒险问题的解决总结

这在实际的计算机中，主要多加几根信号线和数据传送线便可实现。

3 总结

本文在简要分析了计算机中常用的加速技术——流水线技术的基础上，分析了由其引出的数据转发型数据冒险问题，并探究了其解决方案。

流水线技术是当今计算机处理器加速所使用的最主要的技术，其原理简洁明了，效果显著。数据冒险问题则是应用此技术最常碰到的问题之一。在实际应用中，流水线技术还存在其他的一些问题，例如计算机指令不一定会被分为等步骤、指令控制问题等，但是这些问题都有解决方案。相信在未来，在生物计算机、量子计算机等未来计算机中，流水线技术依旧会成为一个好用的处理加速技术。

参考资料：

[1] William Stallings.计算机组成与体系结构-性能设计[M].北京：机械工业出版社，2011.

[2] Alexander Stepanov&Paul McJones.编译原本[M].北京：机械工业出版社，2012.

[3] Patrick Juola.计算机组成及汇编语言原理[M].北京：机械工业出版社，2010.

[4] Louden， K.C.编译原理及实践[M].北京：机械工业出版社，2000.

[5] William Stallings.操作系统：精髓与设计原理[M].北京：机械工业出版社，2010.