流水线的调度问题相对来说比较复杂，我们只讲单功能的非线性流水线调度问题，已经可以从中深刻体会流水线的调度思想了。

下面我将用最最通俗的大白话来讲述你们课本看不懂的流水线调度问题，看完不懂来打我。

疑惑1：流水线为什么会产生冲突？

首先，只有非线性流水线才需要调度，为什么呢？因为会产生过程冲突啊才需要调度的。

那我们继续想，为什么非线性流水线会产生过程冲突呢，而线性流水线不会有过程冲突呢？ 我们要先弄懂非线性流水线是啥子玩意：非线性流水线是指有反馈回路的流水线，如下图（之前讲流水线分类的时候捎带提过一下）： 也就是说，一轮运算任务的结束，需要执行某些部件多次。这就有个问题了，假如说我们像线性流水线那样子源源不断给输入喂入任务，在线性流水线里面我们知道：一旦某个任务执行过第一个步骤就不会回头的，这和工厂的履带一样，不会倒着转的，但是非线性的流水线不同，他可能第一次执行该部件的结果来作为第二次的输入。

那非线性流水线的冲突到底是个什么样子呢？ 假设有如下的处理部件 可以假象一下：首先，第一个任务开始执行，经过S1，然后经过S2，好，此时如果按照线性流水线来说，不会倒着回去S1的，所以我们可以放心传入任务二

但是，很不幸的是非线性流水线倒着回来了，假设我们在第一个任务计算完S2的时候传入第二个任务，

那此时S1就纠结了，“哎，那我到底是用第二个任务的输入作为计算输入，还是用第一次任务S2产生的结果作为计算输入呢？” 这里就产生了冲突矛盾。

疑惑2：那我们要怎样规避冲突？

现在我们知道了非线性流水线会产生冲突了，那到底需要怎样规避冲突呢？ 我们继续思考，冲突发生在什么地方？

答案是因为第一次的任务还没有完全计算完，更细节来说是在S1这个部件计算冲突。 解决这个问题，我们就需要把两次冲突的计算时间错开来。

有人会说：让第一次任务完全计算完才放行第二个任务的，这样可以吗？

这样太婆妈了，已经失去了流水线并行处理的意义了，变成顺序处理了，否决。

我们可以发现，其实不一定完全处理完第一次任务，只要两次冲突的计算不在一起即可，我们需要“不在一起”这个事情量化计算，可以选择用 “时间间隔” 的多少来作为计算单位。

所以，解决冲突本质上就是一个计算时间间隔的问题。

疑惑3：怎样求出禁止启动周期？

在开始讲调度之前，我们需要先理解两个概念，第一个叫 “启动周期”，意思是输入两个任务之间的时间间隔，另外一个叫 “禁止启动周期”，意思是当启动一个任务之后在禁止启动周期的时间点输入新的任务就会发生冲突。

如果要满足我们规避冲突的需求，你觉得我更需要知道 “启动周期” 还是 “禁止启动周期” ？

当然是 “ 禁止启动周期” 啦！

你想，如果我们知道了当启动一个任务之后再输入新的任务就会发生冲突的时间点，我们避开这些时间点，不就完成任务了！？

问题是，怎样去求出 “禁止启动周期” 呢？ 我们先看一个叫 预约表 的东西。预约表 可以表达出 和 时空图一样多的信息。你看下面就知道了。 那为啥我们不用时空图分析非线性流水线呢？

首先，时空图不大方便表达有反馈回路的流水线，所以我们用预约表来表达非线性流水线，但预约表是可以表达线性流水线的，另外预约表还有一个超强的功能，利用表格可以转化为二进制位化成逻辑运算问题，在计组的很多问题里面，使用二进制标位可以简化理解很多复杂问题。

知道了预约表之后，我们就要找冲突的时间间隔到底发生在哪里了，先看S1，运算事件发生在时间点1和时间点9，差值是8，也就说一旦任务启动，在8个时间间隔之后你偏要在这个点输入第二任务就会发生冲突。

那好，我们依样画葫芦对S2，S3，S4，S5计算差值，不难找出，第一行（S1）有差值8，第二行（S2）有差值：1，5，6，第三行没有（因为只有一次发生），第四行和第五行都只有一个：1。

这里讲一下第二行的1，5，6是怎样计算出来的： 首先找出时间点：2，3，8，，，

综合以上所有行（段）的差值，去重，之后得到一个数集F={1,5,6,8}

我们管像F这样的数集叫做“禁止表”

但数集不适合我们进行逻辑思考，我们转化为更加直观的二进制的标签; F = { 1 , 5 , 6 , 8 } → C 0 = 10110001 F=\{1,5,6,8\}\rightarrow C_0=10110001 F={1,5,6,8}→C0​=10110001

不懂？解释就是： 1 8 0 1 6 1 5 000 1 1 1^801^61^50001^1 180161500011，这该懂了吧，按位置看就行。

我们管像 C 0 C_0 C0​这样的二进制数叫冲突向量

由于这是我们一开始在预约表得出来的，所以叫做“初始冲突向量”

到这里我们捋一下，我们是怎样得到 这个“初始冲突向量”的。

预约表 ⇒ \Rightarrow ⇒逐行求逐元素差值 ⇒ \Rightarrow ⇒禁止表 ⇒ \Rightarrow ⇒二进制位元化 ⇒ \Rightarrow ⇒初始冲突向量

至此，我们得到了我们的禁止启动周期的集合：禁止表，我们还进一步得到了冲突向量。

疑惑4：找出初始的禁止启动周期，冲突就解决了吗？

哈哈，还没呢！！！！

你是否忘记考虑这样一件事情，当第一个任务没有计算完的时候，你输入第二个任务，那第二个任务是否和第三个任务冲突呢，第三个和第四个呢？？？？嘿，是不是有点想撞墙了

但是在掌握了解决第一次和第二次任务的经验之后，我们至少有这样的情报：禁止启动周期是可以被枚举出来的，而且进一步分析，禁止启动周期的变化可以被逻辑计算出来的，实际上，我们分析完第一次和第二次之后，第一次的禁止启动周期就不是我们考虑的重点了，第二次的禁止启动周期变成了我们关注的事情，现在有没有发现有种证明归纳法的味道了？

我们想一下，新的冲突是怎样产生的？

答案是第二次的计算占用了新的时间点，我们假设第二任务和第一个任务相隔了 j j j 个时间周期，当第二个任务进入流水线的时候，第一个任务已经在流水线前进了 j j j 个时间周期，那么初始的禁止表里面的间隔对于第二任务而言就是偏移了 j j j 个周期而已，我们对冲突向量右移 j j j 位即可。

这样还不够，我们还需要和初始冲突变量做一次或运算来去重。

这样我们就得到了产生新的冲突向量的公式： n e w C 0 = s h r j ( C 0 ) ∨ C 0 new C_0=shr^j(C_0)\lor C_0 newC0​=shrj(C0​)∨C0​

举个例子，之前我们拿到了一个初始冲突向量： C 0 = 10110001 C_0=10110001 C0​=10110001，根据这个冲突向量给出的情报，我们能在第一个任务启动之后的2，3，4，7个周期之后进入，其他都不行。

我们分情况考虑，假如在2个周期之后进入，那么执行产生新的冲突向量公式就是对 C 0 C_0 C0​算术右移2位之后做或运算， 00101100 ∨ 10110001 = 10111101 00101100\lor 10110001=10111101 00101100∨10110001=10111101，接下来对3，4，7依样画葫芦即可。

对于所有的情况，我们做类似的操作，就可以得到一个流水线状态机，如下图： 需要注意的是，我们所有的状态最后都要回到初始状态，这就是 9 + 9^+ 9+的含义。

出现了状态机，至此，我们已经有能力规避所有的冲突了。

为什么？！还问为什么，状态都被你枚举出来了，还能怎样冲突，你已经掌握了所有可能不发生冲突的走法了。

从初始状态出发，任何一个闭合回路都可以看成一种调度方案，比如(2,7)，我们反复循环使用2和7这两个启动周期即可规避所有的冲突。

最优调度方法的选择

我们进一步思考，到底哪一种调度方案更好呢？我们需要使用延迟时间来判断，因为我们当然希望接近不间断地并发处理任务，延迟时间我们只需要计算启动周期的平均值即可。

如下表：

如图所示，延迟最小的就是最优的调度策略，（3，4）策略荣获此名。

但（3，4）策略是不等间隔的策略，不等间隔会给计算机控制变得更复杂，我们在实际应用中更偏向于等间隔的调度策略。

推理总结：

至此，所有的单功能流水线调度问题解释完毕，我们来捋一下逻辑。

首先，我们讨论了为什么流水线产生冲突的原因，分析出我们需要计算禁止启动周期，然后利用预约表计算出 禁止表（禁止启动周期集），然后计算出初始冲突向量，推理归纳，得出冲突向量的变化公式，计算出所有的状态（所有的冲突向量），画出了状态机，最后计算启动周期的平均值得出延迟周期，分析出最优的流水线调度策略。

如果给一个方便记忆的： 题目一般会先给出预约表的 预约表 → \rightarrow →禁止表 → \rightarrow →初始冲突向量 → \rightarrow →所有的冲突向量 → \rightarrow →状态机 → \rightarrow →最优调度策略

题目的套路也不过如此，一次搞通，终身轻松，祝考研成功！