36
CPU中指令流水线技术研究
由于线性流水线在执行每个任务的过程中，各段只通过一次，因此每拍都可以将一个新的任务送入流水线，这些任务不会争用同一个流水段。非线性流水线则不同。因为段间设置有反馈回路，一个任务在流水的全过程中，可能会多次通过同一个段或越过某些段。这样，如果每一拍向流水线送入一个新的任务，都将会发生几个任务争用同一段的功能使用冲突现象。要想不发生冲突，就得间隔适当的拍数之后，再向流水线送入下一个任务。究竟间隔几个拍再送入下一个任务，才能既不发生功能段使用冲突，又能使流水线有较高的吞吐率和效率，这就是流水线调度所要解决的问题。
为了能对流水线的任务进行优化调度和控制，1971年 E.S.Ddavidson 提出使用一个二维的预约表。（如图5.1）
图5.1 预约表示例 根据预约表可以很容易得出一个任务使用各段所需间隔的拍数。例如1段相隔3拍，2段相隔3拍。那么两个任务相隔3拍流入流水线必将会争用1段和2段。我们将流水席那中所有各段对一个任务流过时会争用同一段的节拍间隔数汇集在一起，构成一个延迟禁止表F。如本例为{3.4}。就是说，要是流水线的各功能段不发生被争用的冲突，相邻两个任务送入流水线的间隔拍数不能为3、4拍，这些间隔拍数应当被禁止使用。另外还有个冲突向量的概念，此为一个N-1位的位向量（cN?1?c1），其第i位的状态用以表示后当时隔i拍给流水线送入后继任务是否会发生功能段的使用冲突。如果不发生冲突，令该位为“0”；否则，让该位为“1”，表示禁止送入。
不难看出，输入后续任务还需等待的拍数与前一个任务在流水线中已经进行了几拍有关。当第一个任务第一拍送入流水线时，根据禁止表F={2，4，6}，可以形成此时的冲突向量C为（101010），称此为刚流入流水线时的初始冲突向量。由此可以看出第二个任务距第一个任务1，3，5拍流入流水线，因为冲突向量所第五章 中断处理与流水线调度
37
对应位为“0”，表示不会有冲突。当第二个任务流入流水线后，应当产生新的冲突向量。以便决定第三个任务可以相隔多少拍流入流水线，才不会与已进入流水线的第一、第二个任务争用功能段，如此顺序类推。
那我们如何判断下一条冲突向量呢?随着流水线中第一个任务每向前推进一段，原先禁止第二个任务流入流水线的各种间隔拍数均相应减去1拍。这意味着可以将初始冲突向量放在一个移位器中，每拍逻辑右移1位，让左面移空的位补“0”，以表示如果间隔6个拍流入后续任务的话，前一个任务必定已流出流水线而不会发生功能部件使用冲突。因此，随着任务在流水线中的推进，会不断动态地形成当时的冲突向量。如果选择第1条任务在间隔1拍时进入流水线，对第2个任务而言，冲突向量右移1位成了（010101）。这样要想使第3个任务流入流水线后，既不会与第1个任务发生冲突，也不会与第2个任务发生冲突，新的冲突向量就应当是第1个任务当前的初始冲突向量（010101）与第2个任务的初始冲突向量（101010）按位“或”，其结果为（111111）。由此，可以根据前面一个冲突向量求出接下来的冲突向量。
按照这样的思路，以各种可能的拍数流入新的任务，从而又可以产生新的冲突向量，一直进行到不再产生不同的冲突向量为止。由此可以画出用冲突向量表示的流水线状态转移图。本例的流水线状态转移图如图（5.2）
图5.2 状态转移图
因此，只要按流水线状态图中由初始状态出发，能构成一种间隔拍数呈周期性重复的方案来进行流水线调度，都不会发生功能段的使用冲突。然而，我们还希望能寻找一种最佳的调度方案，以便使流水线的吞吐率最高。显然，只需要分
38
CPU中指令流水线技术研究
别计算出每种调度方案的平均间隔拍数，或者称之为平均启动距离，找出其中最小者，就是流水线各后续任务流入流水线所用间隔的最佳调度。本例的几种调度方案如图（5.3）
简单循环 （1，7） （3，7） （5，7） （3，5，7） （5，3，7） （3，5） （5） （7） 图5.3 调度方案
平均启动距离 4 5 6 5 5 4 5 7
以上只是结合单功能流水线讨论了有关流水线调度的基本思想和方法。在此基础上不难解决多个功能流水线的调度。对于一个多功能流水线，只需要将对应每种功能的预约表都重叠在一起，组成一张新的预约表，然后在按照此方法进行调度即可。
第六章 总结与展望
39
第六章 总结与展望
流水线技术是一项可以应用于任何ISA的微体系结构技术。RISC体系结构的特性确定确实能够使流水线的设计更加容易。流水线技术已经被证明是提高处理器性能的一项十分强大的技术，并且在流水线深度方面仍然有很多上升空间。不难想象，以后还会有更深的流水线出现。
流水线性能的主要障碍是指令相关引起的流水线停顿。其中，控制相关引起的分支开销是最主要的部分。随着流水线深度的增加，分支开销也会增大并成为主要的挑战。另外，流水线处理器设计将传统CPU设计中的数据通路设计和控制通路设计放到了一起进行处理，它们可以被合并到一条流水线来实现。
CPU中指令流水线技术是现代计算机中提高处理机运行速度的关键性技术，也是超标量流水线技术与超流水线技术的基础。在目前，国内计算机硬件技术，特别是CPU的研究起步较晚，技术相对比较落后。在这种形势下进行CPU中指令流水线技术进行学习研究，其意义是及其重要的，同时困难和挑战也是比较大的。对我来说，这是一个非常好学习的过程，很多的基本知识，基础理论都让我受益匪浅。无论在以后的工作或者是学习中，这些宝贵的经验都将一直伴随着我。虽然我们国家目前在此领域的研究还比较落后，但是我相信以后会有更多的人投入进来，我们的资料和技术也会一天天的发展起来，最后达到甚至超过国际先进水平也未可知。
在此次毕业设计过程中，学习资料比较少，内容比较浅，经过去图书室，上网等多种途径基本解决了这一问题。在此过程中，我经历了困难，也享受了知识所带来的乐趣。
40
CPU中指令流水线技术研究