计算机体系结构Report2指令级流水和指令级并行——永无休止的“完美”追求戚洪源目录一、性能瓶颈来源 (4)1、单周期、多周期MIPS结构性能瓶颈 (4)2、简单的五级流水MIPS性能瓶颈来源 (4)相关 (4)冲突 (5)二、突破瓶颈的可能性 (5)三、性能提升的具体方法 (6)1、简单的硬件实现方法 (6)定向技术 (6)投机 (6)2、基于软件（编译器）的静态调度方法 (7)预测分支 (7)3、软硬件结合的动态调度方法 (8)Tomasulo算法 (8)动态分支预测 (8)4、多指令流出 (9)基于静态调度的多流出技术 (9)基于动态调度的多流出技术 (9)超长指令字技术 (10)超流水线技术 (10)5、循环展开和指令调度 (10)四、总结 (10)摘要：有人说，如果计算机科学与技术是一座金字塔，位于塔尖的一定是高性能计算。
从计算机诞生至今，每一次进步都是对于计算机性能极限的一次刷新。
人类对于计算性能日益膨胀的需求，前沿科技对于高性能计算的考验，都促使这一领域不断发展。
单纯硬件技术上的改革是非常重要的：主频的提高、稳定的晶体管……但我们同样惊艳于并行技术在其中发挥的神奇的作用。
各种并行技术犹如催化剂一般，使提高计算机性能的进程大大加快。
这些技术的应用，不断挖掘着计算机潜在的性能，也让人类在一条追求“完美”的道路上不断前行。
何谓“完美”？这是一个看起来复杂实际上非常简单的问题。
“完美”，就是让计算机每一个部件每时每刻全负荷运作，发挥最高的性能。
看似简单，但却很难实现，也不可能实现。
并行技术的发展，也是追求“完美”的尝试。
然而程序“性本恶”，程序本身的许多特性为并行化带来了不小的麻烦。
我们其实是在和自己斗争。
“榨干计算机每一滴性能”，这是ASC15上浪潮集团首席科学家王恩东演讲时说的一句话。
在我看来，不论是指令级流水还是指令级并行，目的都是为了“榨干计算机每一滴性能”。
在这个过程中，出于需要又出现了一些非常特殊的结构上的支持。
本文将基于MIPS结构，通过对于性能瓶颈的来源、性能突破的可能性、性能提升的具体方法这三方面全面系统地阐述指令级流水和指令级并行的相关知识。
最后再提出一些感想。
在第一部分中，我们会讲述单周期到多周期再到流水线的发展过程，并对流水线的性能瓶颈进行具体分析。
在限制流水线性能的三个方面中，前两点只与硬件工艺有关，最后一点相关和冲突却可以通过许多技术来实现突破。
第二部分中，我们会继续讨论第一部分中提出的限制流水线性能的重要因素：相关和冲突。
这一部分，我们将从原理层面阐述突破这一瓶颈是可行的。
最后一部分，我们按照分类，具体阐述了多种提升性能的方法。
一、性能瓶颈来源这一部分将由简单到复杂，只提出限制性能的原因，不提出解决方案。
这一部分的讨论结果对后面的研究至关重要。
1、单周期、多周期MIPS结构性能瓶颈单周期和多周期最大的问题就是部件利用率不高。
将每一条指令的执行过程粒度化，我们可以发现：并不是每时每刻所有的部件都处于工作状态。
大多数时刻只有一个部件在工作。
这种浪费是非常可怕的，不能让其他部件都闲在那里等一个部件。
如果在同一时刻能让更多部件运行起来，性能一定会大大提高。
2、简单的五级流水MIPS性能瓶颈来源简单的五级流水是一种最基本的流水结构，在一定程度上解决了单周期和多周期部件空闲的问题。
然而，折中简单的五级流水结构并不是没有缺陷的。
一方面，如果在设计流水线的时候考虑不周全，使流水线各段不均匀，即有的段比别的段要长的多，这个段就成了瓶颈。
计算机的时钟周期取决于这个瓶颈段的延迟时间。
因此，在设计流水线式要尽可能使各段时间相等。
另一方面，由于流水寄存器延迟和时钟偏移开销，流水线增加了许多额外开销。
由于这些额外开销的存在，会使每条指令的执行时间有所增加。
这些开销也限制了流水级数的加深。
最后，也是最关键的，指令的相关和冲突。
当一个流水线设计完成后，上面的两种问题对使用流水线影响就不会太大了。
因为这些开销是现实存在的，不会消亡。
我们只能合理设计，提升工艺，尽量缩小它们对于流水线性能的影响。
但指令的相关和冲突，是确确实实限制流水性能的重大瓶颈！相关1、数据相关对于两条指令i（在前，下同）和j（在后，下同），如果下述条件之一成立，则称这两条指令数据相关。
i.指令j使用指令i产生的结果ii.指令j与指令k数据相关，而指令k又与指令i数据相关2、名相关当指令i与指令j出现如下两种情况，都属于名相关。
i.反相关。
如果指令j写的名与指令i读的名相同，则称指令i与指令j发生了反相关。
ii.输出相关。
如果指令j与指令i写的名相同，则指他们发生了输出相关。
名相关的两条指令之间并没有数据流动，只是使用了相同的名。
冲突1、结构冲突因硬件资源满足不了指令重叠执行的要求而发生的冲突。
如：当只有一个存储器时，存数和取指就会发生结构冲突。
2、数据冲突当指令重叠执行时，因需要用前面指令产生的结果而发生的冲突。
这其中又分为写后读冲突和写后写冲突。
其中写后读冲突只发生在这样的流水线中：流水线中不止一个段可以进行写操作。
3、控制冲突流水线遇到分支指令和其他会改变PC值的指令所引起的冲突。
总的来说，确定指令之间存在什么样的相关，对于确定程序中有多少并行性以及如何开发并行性具有重要的意义。
如果两条指令相关，它们就不可以并行执行，只能部分重叠执行。
冲突时针对具体的流水线来说的，由于相关的存在，使指令流中下一条指令不能在指定的时钟周期内执行。
相关是程序固有的一种属性，即“性本恶”，它反映了程序中指令相互依赖的关系。
而具体的一次相关是否会带来冲突以及会导致多长时间的停顿，则是由流水线自身决定的。
二、突破瓶颈的可能性自上世纪80年代中期以来，几乎所有的处理机都利用流水线来使指令重叠并行执行。
这种指令之间存在的潜在并行性成为指令级并行。
但上一个部分出现的问题，大多限制了指令级并行。
我们在这一部分首先概述开发并行性的可能性。
为下一部分的具体策略做铺垫。
程序的执行应当有自身的一个顺序。
但是这个顺序并不是一成不变的。
有些语句的调度并不会影响程序的执行结果，这也是我们可以进行指令调度的一个前提。
我们介绍的各种软硬件技术的目标是开发程序并行性，但同时也不能护士程序顺序执行的要求。
那么为了保证程序执行结果正确，我们必须保证程序的什么属性不受破坏呢？这两个属性就是数据流和异常行为。
保持异常行为是指无论怎么改变指令的执行顺序都不能改变程序中异常的发生情况。
而这两个特性经常被具体化为：如果能做到保证程序的数据相关和控制相关，就能保持程序的数据流和异常行为。
下面一个部分论述的所有技术，都是在保证程序的数据相关和控制相关的基础上，最大限度地开发程序的并行性。
三、性能提升的具体方法书上的第三章和第四章都提到了很多技术来提升流水线性能。
总的来说，第三章大多采用了基于软件的实现方法或者基于简单硬件的实现方法。
第四章主要讲解了较为复杂的软硬件结合的实现方法。
此外第四章还包括对于对指令流出和循环展开技术的介绍。
按照这种分类，我们来具体看一看提升性能1、简单的硬件实现方法定向技术定向技术是针对数据冲突的。
具体思想是：在某条指令产生结果前，其他指令并不是真正需要这条指令的计算结果，如果能将该计算结果从其产生的地方直接送到其他指令需要它的地方，那么就可以避免停顿了。
实现方式如下：●EX段和MEM段之间的流水寄存器中保存的ALU运算结果总是送回到ALU入口。
●当定向硬件检测到一个ALU运算结果写入的寄存器就是当前ALU操作的源寄存器时，那么控制逻辑就选择定向的数据作为ALU入口，而不采用通用寄存器读出来的值。
投机这是一种正对控制冲突的方法，在流水线中加入一个ALU部件，专门用来计算转移的地址。
使分支目的地址尽早得出。
这是一种硬件上的处理方法，在书中提到了。
2、基于软件（编译器）的静态调度方法编译器实现的指令调度为了减少停顿，对于无法用定向技术解决的数据冲突，可以通过在编译时让编译器重新组织指令执行顺序来消除冲突。
实际上，对于各种冲突都有可能用指令调度来解决。
这里的指令调度，通过编译器实现，具体实现方法不展开了。
预测分支当在译码段ID检测到分支指令时，如果流水不空等，而是预测分支的两条执行路径中的一条，继续处理后续指令，就可以体改分支指令的处理性能。
预测有两种选择，即预测分支成功或预测分支失败。
不管采用哪一种，都可以通过编译器来优化性能。
1)预测分支失败预测分支失败的方法就是沿失败的分支继续处理指令。
当确定分支是失败的，就把分支指令看成一条普通的指令；当确定分支是成功的，就把分支之后取出的所有指令转化为空操作，并按照目的地址重新取指执行。
2)预测分支成功基本与上述一致，但是有一个不同的地方：在没有投机的流水线中，转移地址和分支判断结果是同时得出的，这时候预测分支成功就没有意义了。
因此，预测分支成功要在投机的流水线中才可以使用。
3)延迟分支这种方法的主要思想就是在分支指令的后面加上几条指令，把它们看成一个整体。
不管分支是否成功，都要按照顺序执行这些指令。
这几条指令被称为指令槽。
放入延迟槽的指令是由编译器完成的，实际上延迟分支是否能带来好处完全取决于编译器能否把有用的指令调入延迟槽。
常用的调度策略有三种：从前调度，从目标处调度，从失败处调度。
上述的方法受两方面限制：一方面是可以被放入延迟槽中的指令要满足一定要求，另一个是编译器预测分支转移方向的能力。
3、软硬件结合的动态调度方法第三章中讨论的简单流水线有一个主要的局限性，即指令是按程序顺序流出和按序执行的。
如果某条指令在流水线中被停顿了，则后面所有的指令都将停止执行。
如果系统中有多个部件，这些部件可能会因为没有指令处理而处于空闲状态，系统效率低下。
动态调度可以实现多指令同时处于执行状态，可以最大限度地利用系统中每一个部件。
Tomasulo算法Tomasulo算法致力于解决程序的数据冲突，这个算法核心思想如下：●记录和检测指令相关，操作数一旦就绪立即执行，把发生RAW冲突的可能性降到最低。
●通过寄存器换名来消除WAR冲突和WAW冲突。
相比较于记分牌算法，它在硬件上增加了CDB总线、保留站等结构，但是它的记录表要比记分牌算法简单一些，并且无需等待写回后再调用，提高了执行速度（书112页开始介绍）。
动态分支预测与Tomasulo算法不同，虽同为动态调度方法，动态分支预测则主要解决控制冲突。
当所开发的指令级并行越多，控制相关的制约就越大，分支预测就需要有更高的精准度。
1)采用分支历史表BHTBHT是记录分支历史信息的表格，用于判定一条分支指令是否token；这儿记录的是跳转信息，简单点的，可以用1bit位记录，例如1表示跳转，0表示不跳转，而这个表格的索引是指令PC值；考虑在32位系统中，如果要记录完整32位的branch history，则需要4Gbit的存储器，这超出了系统提供的硬件支持能力；所以一般就用指令的后12位作为BHT表格的索引，这样用4Kbit的一个表格，就可以记录branch history了。
