计算机科学与技术专业毕业论文

1目录计算机科学与技术专业毕业论文 .5第一章 绪论目录第一章绪论31.1现代RISC中的流水线技术31.1.1超流水线技术31.1.2超标量技术41.1.3流水技术在Pentium系列微处理器中的实现4第二章流水线基础72.1流水线概念72.1.1指令重叠72.1.2流水线82.1.3流水线的特点92.1.4流水线的分类102.2流水线的主要性能112.2.1吞吐率122.2.2加速比和效率12第三章指令流水线设计153.1流水线理想假设153.1.1一致的运算分量153.1.2重复的运算163.1.3独立的运算173.2指令流水线183.2.1指令流水线设计183.2.2指令集体系结构的影响193.2.3流水线分级的考虑203.3流水线处理器设计213.3.1保持流水段均衡213.3.2统一指令类型223.3.3减少流水线停顿26第四章流水线中各种相关及中断处理274.1流水线中相关274.2资源相关274.3数据相关284.3.1指令相关284.3.2主存空间操作数相关294.3.3通用寄存器组相关294.4控制相关314.4.1猜测法314.4.2加快和提前形成条件码324.4.3采取转移延迟324.4.4加快短循环程序的处理32第五章中断处理与流水线调度355.1中断处理355.2流水线调度35第六章总结与展望39致谢41参考文献42第1章 绪论流水线技术是提高系统吞吐率的一项强大的实现技术，并且不需要大量重复设置硬件。20世界60年代早期的一些高端机器中第一次采用了流水线技术。第一个采用指令流水线的机器是IBM7030（又称作Stretch计算机）。后来的CDC 6600同时采用了流水线和多功能部件。到了20世纪80年代，流水线技术成为RISC处理器设计方法中最基本的技术之一。RISC设计方法的大部分技术都直接或者间接以提高流水线性能为目标。从此以后，流水线技术也被有效地应用到CISC处理器的设计中。Intel i486是IA32体系结构中的第一个流水线实现。Digital的VAX和Motorola的M68K的流水线版本在商业上也取得了成功。流水线技术是当前指令集处理器设计中广泛采用的技术。在这里我们将重点放在（标量）流水线处理器的设计。流水线处理器设计中的许多方法和技术，例如用于检测和化解相关的流水线互锁机制，都是标量处理器设计的基本方法。当前的趋势是朝着超深度流水线的方向发展。流水线的深度已经从不到10发展到超过20.深度流水是获得高速始终频率的必要条件，这是提高处理器性能的一个非常有效的方法。有迹象表明。这种趋势还将持续下去。1.1 现代RISC中的流水线技术1.1.1 超流水线技术超流水线（Super Pipeline）技术是RISC采用的一种并行处理技术。他通过细化流水，增加级数和提高主频，使得在每个机器周期内能完成一个甚至两个浮点操作。其实质就是以时间换取空间。超流水机器的特征就是在所有的功能单元都才用流水，并有更高的时钟频率和更深的流水深度。1.1.2 超标量技术超标量（Super Scalar）技术是RISC采用的有一种处理技术。它通过内装多条流水线来同时执行多个处理。其实质就是以空间换取时间。流水线实现中的问题及解决:流水线实现的一个问题是使流水线连续不断地流动，即不出现流断，才能获得高效率。断流的原因很多，除了编译生成的目标程序不能发挥流水结构的作用，或者存储系统不能及时供应连续流动所需的指令和操作数外，主要还与出现了相关、转移以及中断指令有关。解决局部性相关有两种方法：退后法和通路法；解决全局性相关有三种方法：猜测转移分支、加快和提前形成条件码、加快短循环程序处理。1.1.3 流水技术在Pentium系列微处理器中的实现流水线技术早在Intel的X86芯片中均得到了实现。而Pentium系列CPU产品更是一个高级的超标量处理器。它是建筑在两个通用的整型流水线和一个可流水作业的浮点单元上的，这使处理器能够同时执行两条整型指令。一个对软件透明的动态分支预测机制能够使分支的流水线阻塞达到最小化。奔腾处理器可以在一个时钟周期内完成两条指令，一个流水线完成一条指令。第一个逻辑管道称之为“U”管道，第二个称之为“V”管道。在任何一条给定的指令译码期间，它安排的后面两条指令将被检查。并且，如果有可能，第一条指令被安排到“U”管道执行，第二条指令被安排到“V”管道执行。如果不能，则第一条指令被安排到“U”管道执行，“V”管道中不安排指令运行。指令在两个管道中运行与它们顺序执行所产生的效果是完全一样的。当发生管道阻塞时，后继的指令无法通过被阻塞的指令所在的任一管道中。具有MMX?技术的奔腾处理器为整型流水线增加了一个额外的处理阶段。指令从代码的高速缓冲区中预取出来，被送入到“预取”(PF)阶段，并且在“提取”(F)阶段中进行指令的语法分析。 另外， 全部的前缀译码都在F阶段中进行。 指令在先进先出(FIFO)的指令缓冲区中将语法分析与指令译码分开， 这个缓冲区位于F阶段与译码1(D1)阶段之间。FIFO缓冲区的空间能够将被处理的指令上升到四条指令。FIFO缓冲区是透明的，当它为空时，不增加额外的迟延。在每个时钟周期内，可将两条指令压到指令的FIFO缓冲区中(根据有效的代码字节，以及其它因素，如前缀)。然后，再将成对的指令从FIFO缓冲区中弹出来，送到D1阶段中。由于指令的平均执行效率为每个时钟周期内不超过两条指令，所以FIFO通常是满的。只要FIFO是满的，就可以防止在指令提取和进行语法分析时产生的阻塞。如果发生了这样的阻塞，FIFO也可以使阻塞不在管道的执行阶段上发生。但如果FIFO空，由于流水线中无指令运行，则可能会导致一个执行阻塞。较长的指令或前缀可能会在FIFO入口处产生阻塞。超流水线(Super Pipeline)在本质上仍为一种流水线技术，但它做了以下的改进：1. 流水线条数从奔腾的两条增至三条，还有十一个独立的执行单元并行支持。2. 在执行中采取了无序执行(outoforder processing)技术。即当某条指令需要一些数据而未能立即执行完毕时，它将被剔出流水线并等待数据，CPU则马上执行下条指令，就好比在装配线上发现某件产品不太合格，而被淘汰，等待返工一个道理。这样，可以防止一条指令不能执行而影响了整个流水线的效率。3. 在P6中将指令划分成了更细的阶段，从而使逻辑设计、工序等等更为简化，提高了速度。在486芯片中，一条指令一般被划分为五个标准的部分，奔腾亦是如此。而在P6中，由于采用了近似于RISC的技术，一条指令被划分成了创纪录的十四个阶段。这极大地提高了流水线的速度。P6系列处理器使用动态执行结构。该结构通过硬件寄存器重命名和分支预测的方法，将乱序执行和推测执行合成在一起。这些处理器有一个有序进入的流水线，它将Intel 386的宏指令支解成简单的微操作(或UOP)和一个可以处理这些微操作的乱序的超标量处理器内核。这个乱序的处理器内核包含了几条流水线，连接了整型、跳转、浮点和内存执行单元。几种不同的执行单元可以集成在同一条流水线上。例如：一个整型地址逻辑单元和浮点执行单元(加法器、乘法器和除法器)同享一个流水线。数据高速缓冲区由一个专用的读取端口和其它的存储端口交错而成。大多数简单操作(整型ALU，浮点加法，甚至浮点乘法)可以按每时钟周期完成一至两个操作的吞吐量进行流水作业。浮点除法不可以进入流水线，长迟延操作可以和短迟延操作并行处理。P6系列的流水线由三部分构成：有序组织的前端(In-Order Issue Front-end)单元，乱序内核（Out-of-order Core）单元和有序的退出（In-Order Retirement）单元。Intel新近推出的奔腾处理器使用了P6中的动态执行技术，包括多分枝预测、数据流分析、投机执行。同时奔腾处理器具有一个流水线式的浮点运算单元(FPU)，可支持32位、64位和80位的浮点运算。最近Intel又发表奔腾4，奔腾4基本的指令流水线长度达到了20级，是 P6架构的2倍，也超过了AMD的Athlon。更长的流水线可以使处理器运行在更高的主频下，从而提高处理器的性能，但有可能带来一些指令执行上的延迟。13第二章 流水线基础第2章 流水线基础加快机器语言的解释过程提高机器的运算速度是设计计算机的基本任务之一。这可以通过两个途径来实现。一个途径是提高器件的速度，采用更好的算法，增加指令内各微操作的并行程度，减少解释过程所需要的拍数等多项措施来加快机器指令的解释。另一个途径则是采用重叠和流水方法，同时解释两条、多条以至整段程序，从而加快整个机器语言程序的解释。流水线技术是目前广泛应用于微处理芯片中的一项关键技术,Intel公司更是这项技术在微处理器中应用的首先实现者。2.1 流水线概念指令的三种控制方法：顺序方法、重叠方式、流水方式。顺序方法是指各条机器指令之间顺序串行地执行，而且每条机器指令内部的各个微指令也是串行执行。这种方法虽然控制简单但速度上不去，机器各部件的利用率低。重叠方式是指在解释第K条指令的操作完成之前就开始解释第K+1条指令。通常都是采用一次重叠，即在任何时候，指令分析部件和指令执行部件都只有相邻两条指令在重叠解释。这种方式使指令的解释速度有所提高，控制也不太复杂但会出现冲突、转移、相关等问题，这些都需要在设计时想办法解决。流水方式就是把并行性或并发性镶嵌到计算机系统里的一中形式。它是把重叠的顺序处理过程分解为若干过程，每个过程能在专用的独立模块上有效地并发工作的技术。在概念上“流水”可以看成“重叠”的延伸。不同的是“一次重叠”只是把一条指令的解释分解成两个子过程，而“流水”则是分解为更多的子过程。2.1.1 指令重叠一条指令的执行过程可分为取指令、分型与执行三个过程（如图2.1）。取指令，取出该指令送到指令寄存器。指令的分析指的是对指令的操作码进行译码，按寻址方式合地址字段形成操作数真地址，并用此真地址去取操作数，还要为准备取下一条指令提前形成下一条指令的地址等。指令的执行则是指对操作数进行运算、处理，或存储运算结果。指令的重叠解释方式指的是，在解释第k条指令的操作完成之前，就开始解释第k+1条指令。假设这三个过程分别在3个不同的硬件（指令控制器、分析器和执行部件）上进行，则当第k条指令处于分析阶段的时候，控制器就处于空闲状态，这个时候可以对第k+1条指令进行取指令操作，当第k条指令处于执行状态时，分析器就处于空闲状态，这时可以进行对第k+1条指令的分析（图2.2）。很显然，重叠解释的方式并不能加快一条指令的实现，但是可以加快两条相邻指令以至一段程序的解释。图2.1 机器指令的顺序执行方式图2.2 指令的重叠解释方式2.1.2 流水线流水其实就是重叠的引申，上面谈到的重叠模型实际上就是一个简单的3级流水模型。如果将分析与执行阶段再细分为指令解码、取操作数、执行运算和存储结果，当第k+1条指令在第k条指令执行去操作数的时候就可以开始解码，而不必等到分析k完全结束。这样子在一个指令周期内就可以同时执行5条指令。流水线工作方式是把一个重复的过程分解为若干个子过程，每个子过程可以与其他子过程同时进行。由于这种工作方式与工程中的生产流水线十分相似，因此，把他成为流水线工作方式。在处理机的各个部分几乎都可以采用流水线工作方式。指令的执行过程可以采用流水线，成为指令流水线。运算中的操作部件，如浮点加法器，浮点乘法器等可以采用流水线，成为操作部件流水线。访问主存储器部件也可以采用流水线。甚至在处理机之间，机器之间也可以采用流水线。图2.3 指令流水线2.1.3 流水线的特点从上面的分析中可以看到，在处理机中采用流水线方式与采用传统的串行方式相比，具有一下特点：1. 在流水线中处理的必须是连续任务，只有连续不断的提供任务才能充分发挥流水线的效率。例如。要是浮点加法器充分发挥作用，需要连续提供浮点加法运算。然而，由于程序本身的原因和程序设计过程中人为造成的一些原因，入数据相关等，不可能为浮点加法器连续的提供同一种操作。因此，在采用流水线工作方式的处理器中，特别是当流水线的级数较多时，要在软件和硬件等多方面为流水线提供连续的任务，以提高流水线的效率。2. 把一个任务分解成几个有联系的子任务，每个任务由一个专门的功能部件来实现。因此，流水线实际上是把一个大的功能部件分解为多个独立的功能部件，并依靠多个功能部件并行工作来缩短程序的执行时间。在流水线中，一个子任务通常称为一个子过程，或者一个功能段。3. 在流水线每一个功能部件后面都要有一个缓冲寄存器，或称为锁存器等，用于保存本段执行的结果。这是因为流水线中每一段的延迟一般都不可能相等，因此，在段与段之间传递子任务时，必须要通过缓冲寄存器。当某一个功能段的时间变化范围比较大的时候，要设置多个缓冲寄存器。4. 流水线中各个段要尽量匀称，即时间要求尽量相等，否则将容易引起“阻塞”、“断流”等问题。执行时间最长的段将成为整个流水线的“瓶颈”，这时，流水线中各段将受到限制而不能充分发挥作用。只有当整个流水线完全充满时，整个流水线的效率才能得到充分的发挥。为了设计出高效率的流水线，要充分注意上述问题。2.1.4 流水线的分类从不同的角度，按照不同的观点，可以把流水线分成多种不同的类型。平时所说的某种流水线，往往是按照某种观点，或者从某一个特定的角度对流水线进行分类的结果。因此，从名称上只能反应出这种流水线在某一个方面的特点或者功能。按照流水线的各功能段之间是否有反馈信号，可以把流水线分为线性流水线合非线性流水线。线性流水线是将流水线各个功能段逐个串联起来，输入数据从流水线的一段进入，从另外一段流出。数据在流水线中经过时，没一个功能段都流过一次，且仅仅流过一次。一条线性流水线通常只完成固定的一种功能，在现代计算机系统中，线性流水线已经被广泛的应用于指令执行过程、各种算术运算操作、存储器访问操作等。图2.4 非线性流水线非线性流水线经常用于递归调用，或者构成多功能流水线。按照流水线使用的不同级别，可以把流水线分为功能部件级、处理器级以及处理机之间等多种类型。处理机级流水线即指令流水线，他把一条指令执行过程分解为多个子过程，每一个子过程在一个独立的功能部件中完成。功能部件级流水线也称为运算操作流水线，如浮点加法器流水线、浮点乘法器流水线等。处理机间流水线又称为宏流水线，一般是两台以上处理机通过存储器串行连接起来，每一个处理机对一个数据流的不同部分分别进行处理。 图2.6 指令流水线流水线又可分为单功能流水线和多功能流水线。顾名思义，单功能流水线只能完成固定的单一功能，多流水线通过各个段间进行不同的连接，在不同的时间内或者统一时间内通过不同的连接方式完成不同的功能。在多功能流水线中，根据同一时间内是否可以连接成多种方式，同时执行多种任务，可以把多功能流水线分为静态流水线合动态流水线。所谓静态流水线指的是在同一时间段内，多功能流水线各段只能按照一定固定的方式连接，实现一种固定的功能。只有当按照这种连接方式工作的所有任务都流出流水线之后，才能重新进行连接，完成其他功能。动态流水线则在同一时间段内，可以按照不同的连接方式，完成多种不同的功能。这个时候要求流水线中个功能部件之间不能发生冲突。除了以上几种分类方法外，还可以根据其他标准，从不同角度对流水线进行分类。2.2 流水线的主要性能衡量流水线主要性能的指标主要有吞吐率，加速比和效率。2.2.1 吞吐率吞吐率是指在单位时间内流水线所完成的任务数量或者输出的结果数量。即： 式(2.1)中，n为任务数，是处理完成n个任务做用的时间。本式为计算吞吐率最基本的公式。有的时候我们还需要求一条流水线的最大吞吐率： 式(2.2)中为第k个子过程所花费的时间。最大吞吐率受限于流水线中最慢子过程即瓶颈子过程所需要的时间。为了提高流水线的最大吞吐率，首先要找出瓶颈，然后设法消除此瓶颈。消除瓶颈有两种办法，一是将瓶颈子过程再细分，另一种办法是通过重复设置多套瓶颈段并联，让他们交叉进行。后一种方法需要解决好在各并行子过程之间的任务分配合同步控制，比起瓶颈子过程再细分控制要复杂、设备量要多一些。2.2.2 加速比和效率完成一批任务，不使用流水线所花的时间与使用流水线所用时间直比即为流水线的加速比。如果不使用流水线，即顺序执行所用时间为，使用流水线的执行时间为,则流水线的加速比为： 这是计算流水线加速比的基本公式。流水线的效率是指流水线的设备利用率。在时空图上，流水线的效率定义为n个任务所占的时空区域与k个功能区域所占时空区域之比。因此，流水线的效率包含有时间和空间两方面的因素。实际上，n个任务所占的时空区域就是顺序执行n个任务所用的总的时间。而一条k段流水线完成n个任务总的时空区域为k，其中是流水线完成n个任务所用的总时间。则一条k段流水线的效率可表示为： 此式是计算流水线效率的一般公式。如果流水线各段执行时间均相等，且输入的n个任务是连续的，则一条k段流水线的效率为： 从流水线的时空图上来看，上式分母部分是完成n个任务所用时间与k个功能段所围成的总面积，而分子部分则是k个功能段实际所占有的面积。因此，利用时空图来计算流水线的效率十分方便。25第三章 指令流水线设计第3章 指令流水线设计我们做任何事情，都希望能够达到理想状态，但这往往是不现实的，我们研究理想状态的意义就在于给出一个衡量的标准，并且努力向这个标准靠近，这在指令流水线的设计过程中也不例外。3.1 流水线理想假设对于指令流水线的目的，我们是希望能最大限度的提高系统的性能。然而在实际中却往往做不到，因为只有在理想状态下，k级流水线的设计才能将提高k倍的吞吐率，理想状况主要基于3条假设，我们称之为“流水线理想假设”，他是正确评估流水线设计的关键。设计各种方案解决实际流水线与流水线理想假设之间的矛盾，这就组成了流水线设计的主要技术。流水线理想假设包括：1. 一致的运算分量：要完成的整个运算量可以均匀的分成延迟一只的若干分量。2. 重复的运算：输入数据有大量相同的、重复的运算。3. 独立的运算：所有相同的重复运算之间没有相关性。3.1.1 一致的运算分量第一条流水线的理想假设说明，将要进行流水化的运算分量均匀的分成k个延迟相同的分量。这意味着以前的设计可以均匀的分成k个均衡的流水段。如果以前总的运算延迟，也就是非流水设计的式中周期为T，那么k级流水线的设计式中周期就是T/k，也就是流水段中每一段的延迟。基于这个理想假设，时钟频率能够提高k倍，并且吞吐率也提高了k倍。在实际的流水线设计中，这个理想假设可能并不成立。将总的运算分量完全均匀的分成若干分量是不可能的。在一个具有3级流水线的浮点加法器的例子中，设总的延迟为500ns,流水线分3段，每一段的延迟分别为200ns,100ns,200ns.显然，总的延迟并没有均匀的分布到流水线的三段当中。由于流水线的时钟周期决定于延迟最长的那一段，因此延迟较短的段会有一些无效或者失效的时间。比如浮点加法器的第二段，它就有100ns的无效时间，我们可以把它称之为“内部碎片”。由于内部碎片的存在，完成同样的运算的延迟将会增加。还有一个内在的假设，即流水段之间引入的缓冲不会带来额外的延迟，并且流水线的时钟信号也不会引入额外的延迟。同样，这一假设在实际当中也是不能成立的。在相应的例子中，为了保证信号的时钟信号的准确建立，设置了暂存器，因此总的时钟周期又延长了，从而导致了实际性能不可能提高3倍。第一条流水线理想假设主要包含了以下两种观点：在将以前的运算分量分成若干分量是时，没有引入无效时间；段间缓冲的引入及时钟没有带来额外的延迟。在芯片级的设计中，可以采用一些锁存器，比如Earle锁存器可以使流水线时钟产生的延迟尽可能地小。因此如何将总的运算量均匀的分到各流水段中构成了流水线设计的第一个挑战。我们的目标是，尽可能使各个流水段保持均衡，以减少内部碎片。由于各个流水段不能完全均衡内部碎片是不满足第一条流水线理想假设的主要原因，这将成为一种开销，并导致k级流水线设计的吞吐率提高达不到理想的k倍。3.1.2 重复的运算第二条流水线理想假设说明，流水线不断地重复执行相同的运算。这意味着在多组输入数据中，有些运算是相同的并且这些运算要反复执行。每次执行时，流水线提供的分量执行顺序都是一样的。对于浮点加法器的例子，将包含大量的浮点数对要进行相加，每一对操作数都要通过相同的3级流水线。这以一设说明，每一次的重复运算都会 使用流水线中的所有段。对于我们的例子这显然是成立的。浮点加法器满足这条假设，是因为该流水线只完成了一个功能，即浮点加法运算。如果你要设计的流水线要完成多个功能，这一假设就不满足了。例如，设计一条既可以计算加法又可以计算乘法的算术流水线。在多功能流水线中，单独一项功能可能并不需要所有的流水段，而可能由流水段的不同子集来完成不同功能。由于输入数据以同步方式通过流水线，有些数据可能不需要某些流水段，当他们通过这些段的时候，将什么也不执行。这种没有使用或者空闲的流水段带来了另一种形式的流水线失效，可以称之为“外部碎片”。与内部碎片相似，外部碎片也是一种流水线开销，应该尽量减小。第二条流水线理想假设认为所有的流水段总是被充分利用。除了说明不存在外部碎片之外，这条假设还说明要处理的数据是大量的。第一个数据达到流水线的最后一个段需要k个周期，这k个周期称为流水线的“填充时间”。最后一个数据进入流水线的第一个段后，还需要k个周期排空流水线。在填充合排空过程中，不是所有的流水段都处于工作状态。如果有大量的输入数据要进行处理，可以使流水线的填充和排空时间只占总时间的很小一部分。因此，多有流水段都可以认为总是处于工作状态的。3.1.3 独立的运算第三条流水线假设说明，流水线要处理的运算是彼此独立的。这意味着，所有同时间驻留在流水线中的运算是不相关的，也就是说，任何两个运算之间不存在数据或者是控制相关。这一假设保证流水线处于“流动”的工作方式，即后面的运算不会因为存在相关性而等待前面运算的完成。对于浮点加法器的例子中，这一假设是成立的。如果有多对操作数要进行相加，一对操作数的相加不会以来另一个加法的结果。这些操作数可以按照“流动”的方式进行处理。这一条假设对于一些流水线可能不成立。后面的运算可能需要前面的结果，而这两条运算可能同时驻留流水线中。如果后面的运算已经进入到需要结果的流水段，而这时候前面的运算还没有到达产生结果的流水段，哪么后面的运算必须在那一段等待。这种等待称为“流水线停顿”。如果某一运算停顿在流水线的某一段，所有后续的运算可能都要被迫停顿。流水线停顿不可避免地导致某些段处于空闲状态，这可以看作是一种动态的外部碎片，因此会导致流水线吞吐率降低。如果相关是不可避免的，那么再设计流水线的时候，就要尽量减少流水线的停顿次数。3.2 指令流水线前面三条流水线是流水线的理想假设。在大多数情况下，算术流水线的实际情况与理想假设相差不是太大。然而，对于指令流水线，实际情况与理想假设之间的差距就要大一些。而连接这一差距的桥梁正式指令流水线设计的趣味性合挑战性所在。在设计流水线处理器时，这三条假设成为三个主要的挑战。这三大挑战同时也提供了一条探索流水线处理器设计技术的思路。3.2.1 指令流水线设计在设计指令流水线时，三条流水线假设成为设计的目标。一条指令的处理过程就是要流水化的运算，它必须被划分成多个尽量一只的子运算，以获得尽量均衡的流水线。处理一条指令的时间延迟成为“指令周期”，每一段的时间延迟决定了“机器周期”。指令周期是一个逻辑概念，它是指指令的执行周期。一个程序包含多条指令，程序的执行相当于相应运算的反复执行。机器周期是一个物理的概念，它包含数字逻辑电路中存储单元的时钟等，同时它也是流水线的时钟周期。指令流水线设计的主要任务可以看作是将逻辑指令周期映射到物理机器周期。换句话说，就是将指令周期所对应的运算分成一个子运算的序列，由流水线的各段运行。要有效的进行这种分割或者映射，必须考虑三条流水线的理想假设。一致的运算分量 我们将指令周期分解成多个机器周期的过程称为“量化流水段”。在进行量化流水段时，要尽量减少内部碎片。如果在量化流水段时考虑不充分，就会引入内部碎片，从而影响流水线的利用率。第一条流水线理想假设带来了指令流水线设计的第一个挑战，称之为流水线的均衡。流水线越均衡，内部碎片越少。重复的运算 与单一功能的算术流水线不一样的是，指令流水线天生就是多功能流水线，即它必须能处理多种不同的指令类型。不同的指令类型需要子运算序列稍微不同，所对应的硬件资源也有所不同。指令流水线设计的第二个挑战就是，连接或者整合不同指令类型对不同资源的需求。流水线应能够支持所有的指令类型；同时应该尽量减少每种指令类型的无效或者空闲的机器周期，也就是减少外部碎片。独立的运算 算术流水线处理的是数组数据，他们一般都不相关。与算术流水线不同的是，指令流水线所处理的指令彼此不是完全独立的。因此，指令流水线必须要有一套内部机制，用来检测指令间发生的相关并保证指令相关不会导致错误。指令相关可能会导致流水线停顿，从而引起失效。前面提到过，流水线停顿是是一种动态的外部碎片，它会降低流水线的吞吐率。因此，指令流水线设计的第三个挑战就是尽量减少流水线停顿。3.2.2 指令集体系结构的影响在正式讨论指令流水线设计的三个主要挑战之前，简单的考虑一下指令集体系结构对于指令流水线的影响，将很有启发意义。下面将一次考虑三条流水线理想假设。一致的运算分量 使流水段保持均衡的第一个挑战说明，必须保证分量的延迟是一致的。考察一条指令处理过程中的所有运算分量，其中一定有一个分量的延迟最长，并且这个分量不容易再分解成细的运算分量。在流水线处理器设计中，这样的关键分量是对存储器的访问。由于处理器和存储器的速度差异，存储器访问将成为关键的运算分量。为了近况使指令流水线效率更高，应该对寻址模式进行优化，并且应该采用能够跟上处理器速度的快速cache。重复的运算 第一个挑战是将不同的指令类型对资源的要求统一起来，这是RISC体系结构的主要目的之一。降低指令类型的复杂性和多样性可以降低整合不同指令类型任务的难度。复杂的寻址模式不仅需要额外的访存，而且增加了资源需求的多样性。将所有这些资源需求整合到一条指令流水线当中是意见相当困难的事情，并且所得到的流水线对于很多指令其效率很低。这些指令将会产生外部碎片，从而降低了流水线的利用率。对于一个RISC体系结构的流水线而言，资源整合要简单一些并且得到的流水线效率更高，外部碎片更少。独立的运算 第三个挑战是尽量减少由于指令的相关而引起的流水线停顿，这可能是流水线处理器设计中最吸引人的地方。要正确地完成操作，指令流水线必须检测并化解指令相关。复杂寻址模式，尤其是与存储器访问有关的模式，会因为存储器地址标识符的问题而导致相关检测非常困难。一般来说，寄存器相关比较容易检测，因为寄存器在指令中是明确指出来的。简单而且堆成的指令合适便于进行译码和相关检测。相关的检测和化解可以由编译器静态完成，也可以在运行时由硬件动态完成。在编译和运行时分别进行怎样的处理决定于动态静态界面（DSI）的定义。DSI的定义将导致许多有趣而微妙的权衡。在进行权衡时，必须将编译器、（微）体系结构和微处理器设计紧密结合起来。3.2.3 流水线分级的考虑理想流水化设计所获得的性能与流水线的深度（即流水线的段数）是成正比的，因此似乎最好的设计就是尽量增加流水线的段数。但是，由于时钟的限制，流水线划分的段数总是有一个物理局限的。流水线的每一个段可以看作一个组合逻辑F加上一个锁存器L，信号通过F之后在L出锁存。定义为通过F的最大传输延迟，即通过最长信号路径的延迟；为通过F的最小传输延迟，即通过最短信号路径的延迟；为正确建立时钟信号所需要的额外时间，包括必要的建立和保持时间，以保证正确的锁存，同时还包括可能的时钟扭曲，即达到不同锁存器的时钟沿的最大时间差。假设第一组信号在时刻作用在某一级的输入端，那么F的输出最迟将在时刻有效。当第二组信号在时刻作用的F的输入端时，最快只要时刻就能传到锁存器L。要保证第二组信号不覆盖第一组信号，必须满足： 该公式说明，信号可能到达的最早时刻不能早于信号正确锁存的时刻。该不等式可以重写为：其中就是最短时钟周期T。因此，时钟周期T必须比大，而最大时钟频率不能超过1/T。由此我们可以看到，时钟限制最终决定了流水线的深度，除了这一限制外，如果考虑价格，即流水线的费用开销，最佳设计通常也不会采用最大的流水线深度。在流水线系统的硬件设计中，必须考虑价格和性能的权衡。一般来说，流水线的价格相对于流水线的深度成线性增长。流水线深度一直是影响处理器效率的重要因素，流水线深度的增加可以让处理器时钟频率进一步提高，但随着流水线深度的增长带来的处理器的单周期执行效率降低、发热量上升，同时容易产生分支预测等问题反面影响也会加剧，因此流水线长度的尺度把握一直是处理器设计中的一个重要核心问题。在设计流水线，要综合各方面的因素，根据最佳性价比的要求来选择流水线的最佳段数。3.3 流水线处理器设计流水线处理器设计中的主要问题就是缩小实际情况与理想假设之间的差异。所有关于流水线处理器的设计技术，都可以看作是为解决这三个挑战而进行的努力。3.3.1 保持流水段均衡要流水化的运算就是每个指令周期所要进行的工作。一个典型的指令周期可以根据功能划分成以下5个基本分量：1. 取指（IF,Instruction fetch）2. 译码（ID,Instruction decode）3. 取操作数（OF,Operand(ds) fetch）4. 执行（EX，Instruction execution）5. 存储（OS，Operand store）典型的指令周期从指令的取指开始，然后进行译码，以决定这条指令完成什么操作。一条指令通常带有一个或者多个操作数，这些操作数存放在寄存器或者存储器中，这取决于所使用的寻址方式。一旦所需要的错作数已准备好，就可以执行这条指令所规定的操作。将执行所产生的结果存储起来之后，指令周期就算结束了。分割指令周期的一种很自然的方法就是按照5个基本运算分量来划分，即将每一个运算分量对应到一个流水段，从而得到一个5级指令流水线，我们称这条流水线为基本指令流水线，简称GNR流水线。在GNR流水线中，逻辑指令周期将映射到5个物理机器周期中。机器周期与指令周期之比为5，这个值反应了流水化的程度以及流水段的粒度。量化流水段的目的是将指令周期分割到均衡的流水段中，以尽量减少内部碎片的数目。量化流水段可以从自然的功能划分开始。例如5个基本运算分量。多个延迟较小的分量可以合并到一个新的分量，以获得更均衡化的流水线。另外一种均衡流水线的方法则相反，不是将具有较短延迟的分量合并起来，而是将一个延迟比较长的运算分量分割成多个延迟较短的分量。该方法以延迟较短的分量为参考，将长延迟的运算分量分割成更小的分量，使得各个分量的延迟与参考分量的延迟差不多。这将导致机器周期的粒度更细，流水化的程度更高。在具体进行指令流水线设计的时候，这两种方法可以结合起来使用。不管在什么情况下，量化流水段的目标都是尽量减小内部碎片的开销。3.3.2 统一指令类型第二条流水线理想假设则要求流水线要尽量反复进行同样的运算。对于大多数指令流水线， 重复完成相同运算的理想假设并不成立。指令流水线重复处理的指令具有不同的指令类型。虽然指令周期不断重复，但每次可能处理的是不同类型的指令。不同的指令类型有不同的资源需求，并且各个运算分量的顺序也可能不一样。指令流水线要求能满足不同的需求，必须提供所有指令类型所需要的所有运算分量的超集。单独一种指令类型可能不需要流水线中的所有流水段。对于单独一种指令类型，不需要的流水段成为某种形式的失效或者开销，即外部碎片。统一指令类型的目的，就是尽量减少所有指令类型的外部碎片。要完成一次运算，计算机必须完成一下三个基本任务：1. 算术操作2. 数据移动3. 指令定序算术操作包括对指定的操作数执行算术合逻辑运算，这是整个运算中最突出的部分，所以经常和整个运算等同起来。一个处理器能够支持大量的算术操作类型。数据移动负责将操作数和结果在存储地址之间进行移动。通常存储器地址是分层次的并有专门的指令来进行数据移动。指令定序负责指令顺序的确定。通常一个程序中的运算包含很多条指令，通过执行一个指令序列来完成所需要的运算。这个指令序列，或者叫程序流，可以由指令自身来确定。如何将这三个基本任务分派给ISA中的各种指令，是指令集实际中的关键问题。受RISC体系结果的影响，现在的大多数指令集体系结构都有一些共同的特征。这些体系结果包括Hewlett-Packard的Precision体系结构，IBM的Power体系结构，IBM/Motorola的PowerPC体系结构，还有Digital的Alpha体系结构。这些现代ISA倾向于采用定长指令、正交的指令格式、load/store型体系结构和简单的寻址模式。这些体系结构中的大多数都能与指令流水线很好的协调起来。在一个典型的现代RISC体系结构中，指令集采用一种专门的指令类型来完成三个基本任务中的一个，也就是说，每一种指令类型只完成三个基本任务中的一个。根据三个基本任务，可以将指令分成三种类型：1. ALU指令 完成算术和逻辑运算2. Load/store指令 完成数据在寄存器及存储器间的移动3. 分支指令 控制执行指令的顺序ALU指令所执行的算术逻辑操作严格地针对寄存器操作数进行，只有load和store指令能访问数据存储器。Load/store指令和分支指令都采用比较简单的寻址模式，通常只支持带偏移量的寄存器间接寻址模式。对于分支指令，还支持PC相对寻址。在下面列出关于前两种指令类型的详细规范，其中假设使用了指令cache(I-cache)和数据cache(D-cache)。比较表3.1与表3.1中的两种主要指令类型规范，我们可以看到，两种指令类型的初始化分量比较类似，然而后面的分量有些差异。这些语意上的差异将导致不同的资源需求。基本运算分量 ALU指令类型 IF -取指令（访问I-cache） ID -解码指令 OF -访问寄存器文件 EX -执行ALU操作 OS -回写寄存器文件表3.1 ALU指令类型规范基本运算分量Load指令store指令 IF-取指令（访问I-cache）-取指令（访问I-cache） ID-解码指令-解码指令 OF-访问寄存器文件（基地址）-生成有效地址（基地址+偏移量）-访问（读）内存（访问D-cache）-访问FP寄存器文件（寄存器操作数及基地址） EX- OS-回写寄存器文件-生成有效地址（基地址+偏移量）-访问（写）内存（访问D-cache）表3.2 Load/store指令类型规范统一不同指令类型主要是将不同资源需求有效的整合到一条指令流水线中去，使得这条流水线适合于所有的指令类型。整合的目标是，尽量减少流水线所需要的资源总数，同时尽量提高流水线中所有资源的利用率。通常，资源的整合过程包含以下三个步骤。1. 分析每种指令类型的运算分量序列，确定相应的资源需求。2. 找出指令类型之间的共性，合并相同的运算分量，已使用相同的流水段。3. 如果在不违背指令语意的情况下存在一定的灵活性，可以改变或者重新排列分量的顺序，以便进一步的整合。可以将这一过程应用到表3.1和表3.2中。ALU，load,store指令类型的规范总结如图3.3所示。现在我们由上至下实施统一的过程，检查3个分量的序列合要求提供支持的硬件资源。这个过程产生了指令流水线各段的定义。 ALU LOAD STORE 取指令 取指令 取指令 更新PC 更新PC 更新PC IF 解码 解码 解码 ID 读寄存器 读寄存器 读寄存器 RD ALU.Op 生成地址 生成地址 ALU 读内存 写内存 MEM 写寄存器 写寄存器 WB图3.3 ALU，load,store指令类型的规范总结所有3种指令类型都有相同的IF和ID分量,因此，这两个运算分量可以很容易的合并起来，并用来定义流水线的前两个段，即IF和ID段，从而完成取指和译码工作。所有3种指令类型的OF分量都要读寄存器文件。ALU指令访问两个寄存器并且获得寄存器操作数；load指令访问一个寄存器并获得地址；store指令访问一个寄存器并且获得操作数，访问另外一个寄存器以获得基地址。在3中情况下都要访问一个或者两个寄存器，这些相似的分量可以合并到流水线的第三段，成RD段并从寄存器文件读取最多两个寄存器操作数。因此寄存器文件在每个时钟周期内必须支持两个独立的并行操作数。ALU指令要求有一个ALU功能单元来完成必要的算术逻辑运算。虽然load,store指令不需要执行这样的操作，但是他们需要生成有效的地址来访存。可以看出，地址生成可以由ALU功能单元来完成。因此，这些分量可以合并到流水线第4段，成为ALU段并包含一个ALU功能单元，完成算术逻辑运算或者有效地址的生成。ALU和load指令都需要想寄存器写回结果，这是他们的最后一个运算分量。ALU指令将寄存器操作的结果写回寄存器，load将访存的数据写入到目标寄存器。ALU指令不需要访存，因此，理论上向目标寄存器回写这一过程可以在ALU段之后立即进行。然而为了load指令回写分量统一起来，ALU指令的寄存器回写分量向后推迟了一段，在流水线的第6段进行，成为WB段。这将导致ALU指令在MEM段产生一个空闲周期。这是一种外部碎片并将给流水线带来一些效率损失。通过对不同指令类型的整合，可以得到一条6级流水线，如图3.3右侧所示。3.3.3 减少流水线停顿第三条流水线理想假设则认为流水线执行的运算是相互独立的。在一个k级流水线中，可能有k个不同运算同时进行处理。对于指令流水线，最多可能有k条不同指令同时存在于流水线中。这些指令可能不是彼此独立的。实际上，这些指令之间通常都存在着相关。如果流水线中的指令不相关，将有助于流水线的流动，或者说，指令流过流水线而不会产生任何流水线停顿。如果指令间存在相关，则必须检测并化解相关。相关的化解可能要求流水线停顿。设计的挑战和目标就是减少流尽量减少流水线停顿，防止吞吐率下降。关于具体怎样判断各种相关并且将其化解，将在下一章中进行讨论。31第四章 流水线中各种相关及其处理第4章 流水线中各种相关及其处理我们知道级数为n的流水线，在理想情况下可以提高处理性能n倍。但是，在实际中，有一些情况会阻止指令流中的下一条指令在预定的时钟周期内执行，这些情况就称为“相关冒险”或者“相关”。这一章，我们详细的讨论流水线中各种相关产生的原因及其处理方法。4.1 流水线中相关流水线相关阻止了流水线以理想的加速比改进处理器的性能。在流水线设计中，我们需要考虑以下三种相关：资源相关：当硬件不能支持所有可能出现的、同时重叠执行的指令组合时，就会出现资源冲突，从而导致资源相关，又称为“结构相关”。数据相关：在流水线中重叠执行的指令中，如果一条指令依赖于前面另一条指令的执行结果，从而导致流水线停顿，此时即发生数据相关。控制相关：这种相关主要是由于转移指令和其他能够改变PC内容的指令，在流水线进行处理时产生的。在接下来几节中我们将对这三种相关分别进行讨论。4.2 资源相关通常，一些功能部件没有完全流水化是产生资源相关的基本原因。这时，当一个指令序列中的许多指令都要使用这样的功能部件时，指令就不能在流水线中连续启动处理了。另外一个导致流水线冲突的主要原因是，在系统中没有针对流水线中的所有指令组合情况，设置足够多的硬件资源。例如，一台机器可能只设了一个寄存器写口，然而在一些情况下，流水线可能需要在一个周期内向寄存器进行两次写动作，于是导致了资源相关。当一个指令序列遇到资源相关时，流水线将暂停一条指令的执行知道需要的资源空闲为止。许多采用流水线技术的处理机对于指令和数据的存取仅使用一条存储器流水线。这样，当一条指令需要对操作数存储器访问操作时，数据访问将占用存储器口，于是处理器就不能及时进行下一条指令的存取了，也就是说流水线不得不暂停一个时钟周期，才能对后续指令进行取指。我们在设计时是完全可以避免发生资源冲突的。而且，在其他因素相同的情况下，没有资源冲突的处理器总是比允许资源冲突存在的处理器具有更小的CPI。尽管如此，在具体设计时，很多情况下我们还是允许资源冲突的存在的，这主要有两个原因，一是降低成本，另外，就是减小部件的延迟。流水化所有部件可能会使机器的成本超出人们的承受能力。如果在实际中，某些资源的冲突出现的不太频繁，可能就不值得我们为了完全避免他们的出现而付出很高的代价了。而且，设置一个非流水化的部件或者没有完全流水化的部件，有可能会比一个完全流水化的部件产生的总延迟更小。例如通过权衡，CDC 7600和MIPS 2012的浮点部件放弃了完全流水化的设计，而选取了具有较小延迟（每个操作几个周期）的方案。允许某些资源冲突的存在可以减小部件的等待时间，于是，设计人员就可以在其他一些方面对机器的性能进行改进，从而弥补资源冲突产生的不利。4.3 数据相关数据相关主要有3种，分别是指令相关、主存空间数相关和通用寄存器组相关。解决数据相关的方法主要有两种，一种是退后分析法，在遇到数据相关时，退后本条指令的分析，直至所需要的数据写入到相关的存储单元中。另一种方法是设置专用通路，即不必等待所需要的数据写入到相关的存储单元中，而是经专门设置的数据通路读取所需要的数据。4.3.1 指令相关如果某一条指令的内容取决与前面一条指令的执行结果时，就会产生指令相关。之所以会出现指令相关，关键是由于Von Neumann型机器的指令允许修改所带来的。如果规定在程序运行过程中不允许修改指令，就不会出现指令相关。而且，不准修改指令还带来更重要的好处是可以实现程序的可再入性和程序的递归调用。然而，为了满足程序设计灵活性的需要，有时需要在程序运行过程中修改指令时，可以通过设置“执行”指令来解决。“执行”指令是IBM 370 机器为此设置的一条指令。由于被修改的指令是以“执行”指令的操作形式出现的，将指令相关转成了数相关，所以只需统一按照数相关进行处理就可以了。4.3.2 主存空间操作数相关由于操作数可能存放于主存，也可能存放在寄存器中，因此数相关可以分为主存空间操作数相关合通用寄存器组相关。主存空间数相关就是相邻两条指令之间出现要求对主存同一单元先写入而后再读出的关联。如果让前面一条指令的“执行”与后面相邻指令的“分析”在时间上重叠，就会使得后一条指令“分析”读出的操作数不是程序要求的前一条指令执行完成应当写入的结果，从而造成错误。这种情况下要想避免错误，只有退后下一条指令“分析”的读操作。为了推后读，常见的方法是由存控给读数、写数申请安排不同的访存优先级来解决。因为中央处理机和不止一个的通道都能直接访问主存，中央处理机的访存可能是取指令、读数或写数，通道访存可能是读、写数据，取通道控制字，存通道状态字等。这些访存申请如果同时发出，就会出现访存冲突，因此需要由存控按照预定的优先级别排队处理。只要让写数级别高于读数级别被响应，就自然解决了这种主存空间的数相关。4.3.3 通用寄存器组相关在寄存器-寄存器型（RR型）指令和寄存器-存储器型（RS）型指令的执行过程中可能发生通用寄存器组数相关。看下面两条指令：k: OP , ； = () OP ()K+1： OP ； = () OP ()如果发生： 称数相关。如果发生： 称数相关。发生通用寄存器数相关的情况与寄存器本身的结构合所采用的控制时序等也有关系。解决通用寄存器数相关主要有以下几种方法: 1.如果通用寄存器是用D触发器构成，而且在通用寄存器到运算器之间建立有直接数据通路，即不设置缓冲寄存器或者锁存器，则不会发生通用寄存器数据相关。因为D触发器允许在同一个节拍中实现寄存器之间的循环传递。这中情况下，实际上不需要分析周期，在一个节拍中就可以完成从通用寄存器中通过两个多路选择分别读两个操作数到运算器，操作数在运算器完成运算，并把结果写回到寄存器中。如果构成通用寄存器的不是D触发器，或者在通用寄存器到运算器之间设有缓冲寄存器或者锁存器，则会发生寄存器数相关。2.将分析指令推后一个周期执行。此方法跟前面处理主存空间数相关一样，完全可以解决问题。3.将分析指令推后一个节拍。这种方法