3

3.1 指令级并行：概念与挑战

• 大约85年后的所有处理器都用流水线来重叠指令的执行过程,以提高性能。
• 由于指令可并行执行,所以指令之间可能实现的这种重叠称为指令级并行。
• 本章和附录H中,将研究一系列通过提高指令并行度来扩展基本流水线概念的技术。

与附录C中有关流水线的基础材料相比,本章内容要深人得多。

• 如果读者还不是特别熟悉附录C中的思想,应当在复习这个附录之后再开始探索本章内容。

本章先研究数据和控制冒险带来的局限性,然后再转而讨论如何提高编译器和处理器对并行的开发能力。

• 在这几节中介绍了大量概念,本章和下一章都以这些概念为基础。
• 尽管在理解本章中一些比较基础的材料时并不需要前两节的全部思想,但这一基础材料对于本章后面各节非常重要。

ILP大体有两种不同开发方法:

• 依靠硬件来帮助动态发现和开发并行,依靠软件技术在编译时静态发现并行。
• 使用基于硬件动态方法的处理器,包括 Intel Core系列,在桌面和服务器市场上占据主导地位。
• 在个人移动设备市场,提高能耗效率通常是个关键目标,所以设计人员开发较低级别的指令级并行。
• 因此,2011年,PMD市场的大多数处理器都采用静态方法 我们将会看到 ARM Cortex-a8中即是如此;
• 不过,未来的处理器(比如新的 ARM Cortex-a9)将采用动态方法。
• 从20世纪80年代开始到最近的 Intel Itanium系列,人们已经无数次尝试基于编译器的积极方法。
• 尽管付出了无数努力,但除了非常有限的科学应用领域之外,这些方法都没有获得成功。

过去几年,在主要基于某种方法进行设计时,也会采用大量原本为另ー方法开发的技术。

• 本章介绍这些基本概念和这两种方法,还讨论ILP方法的一些局限性,正是因为这些局限性而直接导致了向多核的转移。
• 深入了解这些局限性对于平衡ILP与线程级并行的应用仍然非常重要。

在这一节,我们将讨论程序和处理器的一些特性,它们限制了可在指令同开发的并行数量,

• 还将介绍程序结构与硬件结构之间的一些重要映射,
• 要知道某一程序特性是否会对性能造成限制以及在什么条件下会造成限制,
• 上述映射是非常关键的。

一个流水化处理器的CPI=基本CPI与因为各种停顿而耗费的全部周期之和:

• 流水线CPU=理想流水线CPI+结构化停顿+数据冒险+停顿控制停顿

理想流水线CPI可以用来度量能够实现的最佳性能。

• 通过缩短上式右侧各项,可以降低总流水线CPI,也就是提高IPC。
• 利用上面的公式,我们可以说明一项技术能够缩小总CPI的哪一部分,以此来刻画各种技术的特征。
• 表3-1显示了将在本章和附录H中研究的技术,还有一些主题将在附录C中的介绍性材料中介绍。
• 在本章将会看到,我们介绍用来降低理想流水线CPI的技术会证明应对冒险的重要性。

表3-1

3.1.1 什么是指令级并行

• 这一章的所有技术都是开发指令间的并行。
• 基本块(一段顺序执行代码,除入口外没有其他转入分支,除出口外没有其他转出分支)中可以利用的并行数非常有限。
• 对于典型的MPS程序,平均动态分支频率通常介于15%到25%之间,也就是说在一对分支之间会执行3~6条指令。
• 由于这些指令可能相互依赖,所以在基本块中可以开发的重叠数量可能要少于基本块的平均大小。
• 为了真正地提高性能,我们必须跨越多个基本块开发LP。

提高ⅡLP的最简单、最常见方法是在循环的各次迭代之间开发并行。

• 这种并行经常被称作循环级并行。
• 下面是一个简单的循环示例,它对两个分别有1000个元素的数组求和,完全可以并行实现

for(i=0;i<=999;i=i+1)
	x[i]=x[i]+y[i]

• 这个循环的每一次迭代都可以与任意其他迭代重叠,当然,在毎次循环迭代中进行重叠的机会不大,甚至没有这种机会。

我们将研究大量将这种循环级并行转换为指令级并行的技术。

• 这些技术的工作方式基本上都是采用编译器静态展开循环(下一节介绍这种方法)或者利用硬件动态展开循环(3.5节、3.6节介绍这种方法)。

开发循环级并行的一种重要替代方法是使用向量处理器和图形处理器(GPU)中的SIMD,这两种处理器都将在第4章介绍。

• SIMD指令在开发数据级并行时,并行处理少量到中等数量的数据项(通常为2~8项)。
• 而向量指令在开发数据级并行时,则通过使用并行执行单元和深流水线,并行处理许多数据项。
• 例如,上述代码序列的简单形式在每次送代中需要7条指令(2次载人、1次求和、1次存储、2次地址更新和1次分支),总共7000条指令,
• 而在每条指令可以处理4个数据项的某种SIMD体系结构中,只需要四分之一的指令就能完成任务。
• 在一些向量处理器中,这个序列可能只需要4条指令:2条指令用于从存储器中载人向量x和y,1条指
  令用于对两个向量求和,还有1条指令用于将结果向量存回存储器。
• 当然,这些指令可以是流水化的,其延迟相对较长,但可以对这些延迟进行重叠。