指令级流水指令级并行

计算机体系结构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) 采用分支历史表BHT BHT 是记录分支历史信息的表格，用于判定一条分支指令是否token ；这儿记录的是跳转信息，简单点的，可以用1bit 位记录，例如1表示跳转，0表示不跳转，而这个表格的索引是指令PC 值；考虑在32位系统中，如果要记录完整32位的branch history ，则需要4Gbit 的存储器，这超出了系统提供的硬件支持能力；所以一般就用指令的后12位作为BHT 表格的索引，这样用4Kbit 的一个表格，就可以记录branch history了。研究发现在BHT 中用1bit 位记录分支是否跳转还不够准确，用2bit 位记录就非常好了，而用3bit 或者更多位记录，效果与2bit 类似。所以在BHT 中，一般就用2bit 位记录分支是否跳转：例如11和10表示这条分支会跳转；01和00表示分支不会跳转。这个2bit 计数器大伙叫做饱和计数器（书126页转换图）。

2) 采用分至目标缓冲器BTB

用于记录一条分支指令的跳转地址，由于这儿存储的是指令地址，例如32

位地址，因此，这个表格就不能做到存储BHT 那样多的内容了，如果也支持4K 条指令，则需要128Kbit 的存储空间，这几乎可以赶上一个L1Cache 的容量了，所以BTB 一般很小，就32项或者64项。由于这个BTB 容量小，并且其用于是记录分支指令的跳转地址，因此，如果这条指令不跳转，即其下一条指令就是PC+4，则不会在BTB 中记录的。

3) 基于硬件的前瞻执行

前瞻执行能很好解决控制相关的问题，它对分支指令的结果进行猜测，并假

设这个猜测总是正确的，然后按指令继续取、流出、执行指令。知识执行指令的结果不是写回到寄存器或存储器，而是放到一个称为ROB 的缓存器中。等到相应指令确认后，才将结果写入寄存器或存储器。

基于硬件的前瞻执行是吧三种思想结合在一起：

1) 动态分支预测。用来选择后续的指令。

2) 在控制相关的结果尚未出来之前，前瞻地执行后续指令。

3) 用动态调度对基本块的各种组合进行跨基本块的调度。

4、多指令流出

单流出的情况下，CPI 就不可能小于一。前面的讨论可以减少因为冲突导致的停顿，是CPI 尽可能小。如果想进一步提高技能，使CPI 小于1，就必须采用多流出技术，在每个时钟周期流出多条指令。

多流出处理机有两种基本风格：超标量和超长指令字。书中134页表4.2给出了各种多流出技术以及它们的优缺点。下面介绍四种重要的多流出技术。他们是：基于静态调度的多流出技术、基于动态调度的多流出技术、超长指令字技术、超流水技术。

基于静态调度的多流出技术

在静态调度的超标量处理机中，指令按序流出。所有冲突检测都在流出中实施，由硬件检测当前流出的指令之间是否存在冲突以及当前流出的指令和正在执行的指令是否存在冲突。如果在当前流出的指令序列中，某条指令存在上述冲突，那么久只能流出该指令以前的指令。

因此，使用基于静态调度的多流出技术的超标量处理机只能顺序执行指令。为了能有效利用超标量处理机所具有的并行性，需要采用更有效的编译技术或者硬件调度技术。如果不采用这些技术，超标量技术所能带来性能上的提高可能很小。 基于动态调度的多流出技术

动态调度不仅在有数据冲突的情况下提高性能，而且还有可能克服指令流出所受的限制。换句话说，尽管从硬件角度来说，在每个时钟周期最多只能启动一个整

数操作和一个浮点操作的执行，但是动态调度可以使指令流出不受这个限制。这一部分不作具体学习。

超长指令字技术

超长指令字技术是另一种多指令流出技术，与超标量不同，他在指令流出时不需要进行复杂的冲突检测，而是依靠编译器编译时找出指令之间潜在的并行性，并通过指令调度把可能出现的数据冲突减少到最少，最后把能并行执行的多条指令组装成一天很长的指令。这种指令字经常是100多位到几百位，超长指令字因此得名。 超流水线技术

超流水线技术是通过细化流水, 提高主频, 使得机器在一个周期内完成一个甚至多个操作, 其实质是用时间换取空间。

超流水处理器是相对于基准处理器而言的，一般CPU 的流水线是基本的指令预取, 译码, 执行和写回结果四级。超流水线（superpiplined ）是指某型CPU 内部的流水线超过通常的5~6步以上，例如Pentium pro 的流水线就长达14步。将流水线设计的步（级）数越多，其完成一条指令的速度越快，因此才能适应工作主频更高的CPU 。

这一点我们可以用日常事例来说明，比如有5个人接力传送木头（对应一个5级的流水线），超流水是说细化该流水过程，即由10个人接力（此时为10级流水），显然完成全部任务的速度会快。

5、循环展开和指令调度 循环展开，是一种牺牲程序的尺寸来加快程序的执行速度的优化方法。可以由程序员完成，也可由编译器自动优化完成。循环展开通过将循环体代码复制多次实现。循环展开能够增大指令调度的空间，减少循环分支指令的开销。循环展开可以更好地实现数据预取技术。

四、 总结

整个第三章第四章，我们围绕结构、原理、方法，深度挖掘了指令级流水和指令级并行潜在的性能。这条路永无休止，随着计算机体系结构的变化、革新，新的方法层出不穷。在研究过程中我们也看出来：不存在两全其美的策略。想要提升性能，要么通过软件调度，要么通过硬件支持，两者各有千秋。而软硬件向结合的办法也不是“万金油”，不会在所有情况下都适用。或许在将来的某一天，我们真的会追求到那梦寐以求的“完美”。