《指级并行及其动态开发.doc》由会员分享，可在线阅读，更多相关《指级并行及其动态开发.doc（99页珍藏版）》请在金锄头文库上搜索。
1、第三章 指令级并行及其动态开发“谁第一？”“美国。”“谁第二？”“没有第二，先生”对话发生于观看帆船竞赛的两个人之间，这个后来叫做“美国杯”的帆船竞赛每几年就要举行一次。灵感来自John Cocke命名的，由IBM公司研制的称为“美国” 的处理器，这个处理机就是第一个采用超标量结构的RS/6000系列微处理器。3.1 指令级并行：概念及挑战1985年以来，包括那些嵌入式处理器在内的所有处理器，都使用流水线方式使指令的执行可以重叠进行以提高效率。这种潜在的重叠被称为指令级并行（ILP），因为在这里指令可以并行处理。在本章和下一章中，我们将深入探讨扩展并行思想的一系列技术，这些技术主要表现在增加指
2、令之间的并行度。本章的内容比附录A的内容更加深入，如果你们对附录A中的内容还不够熟悉的话，请先复习其中的内容。在本章的开始部分，先介绍由数据冒险和控制冒险所带来的一些限制，然后进入我们的主题，学习如何才能通过提高处理器的并行性以最终提高处理器的运算能力。这一小节将介绍很多这两章要用到的基本概念，本章也有一些基础知识并不建立在这一小节上，但这些概念对本章的其他小节和第四章来说也是十分重要的。提高指令级并行度有两种不同的方法，本章主要介绍动态的和以硬件为主的技术，而静态的和更依赖于软件的一些技术将在下一章中介绍。实际上，这种动态和静态，以硬件为主和以软件为主的划分并不是绝对的，其中的一种技术常常对
3、另一种技术也有用。不过，为了清楚起见，我们还是把他们分开来研究，并在适当的地方会指出那些方法是可以借鉴过来的。以硬件为主的动态技术被用在以桌面电脑和服务器为主的许多处理器中，包括Pentium和Pentium4，Athlon，MIPS R10000/12000，Sun UltraSPARC，PowerPC603、G3、G4和Alpha21264等等。而我们下一章所关注的静态的以软件为主的相关技术则被更多地用在嵌入式处理器中，虽然一些桌面和服务器产品，如IA-64体系和Intel的Itanium也使用了很多这种静态技术。本章我们将分别从程序和处理器两个方面来讨论它们对指令级并行性的限制。我们还将
4、研究程序结构和硬件结构之间的一些相当重要的映射关系，这对我们理解和掌握某些问题是至关重要的，这些问题包括一个程序实体是否会影响，和在什么情况下会影响处理器的性能。我们知道，流水线机器的CPI（执行每条指令所用的时钟周期数）等于基本CPI加上各种暂停所使用周期数的和：流水线CPI = 理想流水线CPI + 结构暂停 + 写读暂停+ 读写暂停 + 写写暂停 + 控制暂停其中，理想流水线CPI是指可实现的最大指令流量。减少等式右边的每一项，可以减少总的流水线CPI，从而增加IPC（每个时钟周期的指令流量）。在本章中将看到，我们要介绍的增加IPC的技术使得处理结构、数据和控制方面的问题如何显得更为重要
5、。上面的等式描述了本章中将要讨论的用以减少流水线实际CPI的各种技术。图3.1表示一些将要讨论的技术及它们对CPI的影响。技术减少等式右边的某项章节继续执行和绕行潜在的数据暂停A.2延迟分支和简单分支调度控制暂停A.2基本动态调度（记分板）由真相关性产生的数据暂停A.8重命名的动态调度数据暂停、反依相关和输出相关产生的暂停3.2动态分支预测控制暂停3.4每个周期发射多条指令理想CPI3.6预测所有数据暂停和控制暂停3.7动态内存非二义化涉及内存的写读暂停3.2，3.7循环展开控制暂停4.1基本编译器流水线调度写读暂停A.2，4.1编译器进行相关性分析理想CPI和数据暂停4.4软件流水和路径调度
6、理想CPI和数据暂停4.3编译器预测理想CPI和数据暂停4.4图3.1 附录A、第三章和第四章将要讨论的主要技术及影响到的上面CPI等式中的相关项目。其中，数据暂停是指各种各样的数据冒险造成的暂停，就是写读（先写后读）暂停、读写（先读后写）暂停或写写（写后再写）暂停。在详细讨论上述技术以前，需对这些技术所涉及到的概念加以解释说明，它们决定了指令级并行性可以被开发的程度。3.1.1 指令级并行性在本章和下一章中讨论的所有技术都是用于开发指令序列中的并行性的。从上面可以看出，这种类型的并行性就叫做指令级并行性或ILP（instruction-level parallelism）。在一个基本块（除了
7、入口和出口之外没有其它分支的线性指令序列）中可开发的并行性是很小的。例如，在第三章中看到的定点程序中平均动态转移频率在15%到20%之间，即每4条到7条指令中间将执行一条分支指令。由于这些指令很可能是相互关联的，所以我们在一个基本块中可以开发的指令重叠数将会远小于7。为了能够取得更大性能的提高，就必须开发多个基本块之间的指令级并行性。提高指令级并行性的最简单也最常用的方法，是一个循环中的不同循环体并行执行。这类并行即通常所说的循环级并行。以下是一个简单的循环程序，完成由1000个元素组成的两个数组的相加，此程序是完全可并行的：for (I = 1; i = 1000; i = I + 1)xi
8、 = xi + yi;这个循环的每一个循环体都可以与其它任何一个循环体重叠执行，虽然在每一个循环体内部可重叠的机会几乎没有。有多种技术可以将上述循环级的并行转化成指令级并行，这些技术基本上要么由编译器静态地（下一章的内容）或由硬件动态地（本章要讨论的内容）对循环展开。开发循环级并行的另一种重要方法是使用向量指令（见附录G）。基本上，一条向量指令是对一系列数据项进行操作。例如，上述代码可以在一个典型的向量处理机上用4条指令执行：2条从内存中读取向量x和向量y的指令、一条加法指令和一条保存结果的指令。当然，这些指令可以采用流水线方式执行，虽然有相对比较长的延迟时间，但这些延迟时间是可以被重叠的。向
9、量指令和向量处理机的操作在附录G中有详细描述。虽然向量处理的思想要早于本章中大部分将要讨论的指令级并行技术，但是，采用指令级并行技术的处理机还是正在取代着基于向量处理的处理机，而向量指令集则有望在图象处理、数字信号处理和多媒体技术中得到应用。3.1.2 数据相关性和数据冒险判断指令之间是否有相关关系，对于判断程序中有多少并行性以及如何开发并行性是十分重要的。具体说来，要开发指令之间的指令级并行性，就必须清楚哪些指令是可以并行执行的。如果两条指令是可并行的，那么它们可以在流水线上同时执行而不会造成暂停，当然这里假定流水线资源部件是充足的（因此不存在任何资源冲突）。若两条指令是相关的，那么是不可并
10、行的，虽然有时它们可以部分地重叠执行。因此，最重要的问题就是要判断指令之间是否存在有相关关系。3.1.2.1 数据相关有3种不同类型的相关：数据相关（也叫真数据相关）、命名相关和控制相关。如果下面的条件之一成立，则指令j数据相关于指令i：l 指令i产生的结果为j引用。l 指令j数据相关于指令k，而指令k数据相关于指令i。第2个条件指出，如果两条指令之间存在有上述一条相关链的话，即它们之间也是相关的。这条相关链甚至可以贯穿整个程序。举个例子，考虑如下使数组元素增值的一段代码。在下面的代码段中，0(R1)存放数组元素的首地址，8(R2)存放数组元素的尾地址，F2中存放增加量S。Loop: L.DF
11、0, 0(R1)；F0=数组元数ADD.DF4, F0, F2；加上F2中的标量S.DF4, 0(R1)；保存结果DADDUIR1, R1, # -8；数组指针递减8个字节BNE R1, R2, Loop；R1R2时转移在上述例子中，相关序列包括浮点数：Loop:L.DF0, 0(R1)；F0=数组元素ADD.DF4, F0, F2；加上F2中的标量S.DF4, 0(R1)；保存结果和定点数：DADDIUR1, R1, # -8；数组指针递减；8个字节（一个双字）BNER1, R2, Loop；如果R10，则转移图中箭头所示的都是相关序列，每条指令均相关于前面一条指令。此处的箭头及以后例子中将
12、要出现的箭头都表示为了得到正确结果指令之间必须保持的执行顺序。箭头从一条必须先执行的指令指向后执行的指令（即箭头头部所指的指令）。如果两条指令之间有数据相关，那么它们就不能同时执行或是完全重叠执行，这种相关性说明它们之间存在一条有一个或多个写读冒险的相关链，同时执行这些指令会造成正在流水的处理机检测到这种冒险并插入暂停，从而减少甚至取消指令之间的重叠。在一个依靠编译器进行调度来消除冒险的处理机中，编译器不能调度相关的指令使它们完全地重叠执行，因为那样会使执行结果出错。指令序列中存在的数据相关反映出产生该指令序列的程序源代码中也存在有这种相关关系，这种源代码中的相关性一般是不能破坏的。相关性是程
13、序的一个特性，是否一个相关会导致实际的冒险，是否该冒险会造成暂停，这是流水线结构的基本特性。这一特性对于理解指令级并行性如何被开发利用是很重要的。在所举的例子中，指令DADDIU和BNE之间存在有数据相关，由于我们把流水线的分支检测移到了ID流水段，因此相关造成了1次暂停。若分支检测仍保留在EX流水段的话，这个相关就不会引起暂停。当然，循环的延时仍然是两个周期，而不是一个。相关性的存在只是预示着存在有冒险的可能性，而是否确实有冒险及造成多少个暂停周期，则是具体流水线的特性。数据相关性有以下几个重要特性：（1）相关性预示存在有冒险的可能性；（2）相关性决定必须遵循的计算顺序；（3）相关性决定可被
14、开发的并行性的上界。这几个限制在第3.8节中还会详细地展开阐述。由于数据相关性会限制可以开发的指令级并行性，因此本章和下一章的一个主要任务就是克服这些限制。这可以从两个不同的方面来解决：保持相关关系但避免冒险，或通过变换代码来消除相关关系。对代码进行调度是保持相关关系并避免冒险常用的一个最基本方法。在本章中我们将考虑通过硬件策略在程序执行过程中动态调度指令。由此我们可以发现，有一些相关性将被消除，这主要是由软件方法实现的，并在某些情况下使用了一些硬件技术。一个数据在指令中的流动既可能通过寄存器也可能通过内存。当数据流发生在寄存器中时，由于指令中的寄存器名均是固定的，因而相关关系可以简单明了地检
15、测出来，虽然有分支指令存在时会复杂一些，因为为了保证正确性，编译器和硬件的一些功能都会受到限制。而涉及到内存操作的数据流之间的相关关系则相对较难被检测出来，因为即使两个形式上完成不相同的地址，也有可能指向同一个内存单元。例如，100（R4）和20（R6）有可能表示同一个内存地址。此外，load和store指令的有效地址在不同的时刻执行的地址也有可能是不同的（即20（R4）和20（R4）可以是不同的值）。这些都进一步使相关性的检测工作复杂化了。在本章里，我们将研究采用硬件开发存储器中的数据相关性，虽然这种方法也存在有种种限制。检测这种相关的编译器技术将在下一章中讨论，这在开发循环级并行性时也是一个很重要的方法。3.1.2.2 名字相关第二类相关关系是名字相关，当两条指令使用同一个寄存器或是同一个内存地址时，即发生了名字相关，有名字相关的指令之间不存在数据值的流动。对于指令i和j（i在j之前），它们之间可能存在的名字相关有两种类型：1反相关，指令j写一个寄存器或一个内存单元，而指令i则去读该寄存器或内存单元，且i的执行在前。此时必须保证指令的原来顺序，以确保i能读到正确的值。2输出相关，指令i和j对同一个寄存器或内存地址执行写
