下载文档原格式
第 29 卷 第 12 期2008 年12 月井冈山学院学报（自然科学）Journal of Jinggangshan University(Science and Technology)Vol 〃29 No 〃12Dec 〃2008多发射处理器的指令调度算法研究孙凌宇，冷 明，夏洁武，李金忠（井冈山大学 信息科学与传媒学院， 江西 吉安 343009）[摘要] RI S C 体系作为精简指令集计算机的兴起，使得多发射处理器的指令调度算法成为研究热点。
本文从程序 块划分和执行角度，讨论了多发射处理器的指令调度算法，介绍了几种局部指令和全局指令调度的影响力较大 的算法。
它们通过指令调度的优化，提高多发射处理器内部功能部件的执行并行性。
本文还给出了进一步研究 方向，构造多发射结构多处理器并行处理系统，实现处理器之间的并行技术和处理器内部的并行技术的整合。
[关键词] 精简指令集计算机；处理器；多发射结构；指令调度算法 [中图分类号] TP391[文献标识码] A[文章编号] 1673－4718（2008）12－0025－030 引言由于VLSI 工艺迅速发展改变了传统计算机设 计思想、指令系统运行效率的二八法则、计算机系 统的软硬件间优化划分等因素，使得20世纪80年代 初 兴起的精简指令集计算机 （RISC ：Reduce Instruction Set Computer ）技术一直是计算机处理器 发展的主流，其发展方向是尽量减少平均每条指令 执行的所需周期数 （CPI ：Cycle PerInstruction ），或 者尽量提高平均每个周期可执行的指令数 （IPC ： Instruction Per Cycle ），使得流水线设计和优化编译 成为关键技术。
然而，即使假设在理想情况下，IPC 因 为单发射的RISC 使得在每个周期只发射一条指令， 限制IPC 只能小于或等于1。
因此，RISC 由单发射逐 渐演变成多发射，在流水线基础上每个周期可以发 射多条指令，但这也使得多发射处理器中的指令调 度算法更为重要[1]。
超标量处理机和超流⽔线处理机——计算机系统结构在表5.2中，基准标量处理机是⼀台普通的单流⽔线处理机。
为了便于进⾏⽐较，把基准标量处理机的机器流⽔线周期和指令发射等待时间都假设为1个时钟周期，同时发射的指令条数为⼀条，它的指令级并⾏度ILP（Instruction Level Parallelism）假设为1。
另外三种指令级并⾏处理机，即并⾏度为m的超标量处理机，并⾏度为n的超流⽔线处理机，以及并⾏度为（m，n）的超标量超流⽔线处理机，它们的性能都相对于基准标量处理机进⾏⽐较。
单流⽔线处理机只有⼀条指令流⽔线，只有⼀个多功能的操作部件，每个时钟周期"取指令"和"分析"完成⼀条指令。
在许多流⽔线处理机中，指令流⽔线的流⽔段数k＝4；它把⼀条指令的执⾏过程主要分解为"取指令"、"分析"、"执⾏"和"写结果"4个阶段。
指令所要执⾏的功能主要在多功能操作部件中，在"执⾏"这⼀流⽔段完成。
多数流⽔线处理机的多功能操作部件采⽤流⽔线结构。
有的简单指令，只要⼀个时钟周期就能够在"执⾏"流⽔段中完成，⽽⽐较复杂的指令往往需要多个时钟周期。
另外，还有条件转移等的影响；因此，⼀般流⽔线标量处理机每个时钟周期平均执⾏指令的条数⼩于1，即它的指令级并⾏度ILP＜1。
超标量、超流⽔线和超标量超流⽔线三种处理机在⼀个时钟周期内可以执⾏完成多条指令，即它们的指令级并⾏度ILP都⼤于1。
超标量处理机基本结构超标量处理机的典型结构是有多个操作部件，⼀个或⼏个⽐较⼤的通⽤寄存器堆，⼀个或两个⾼速Cache。
先进的超标量处理机⼀般都包含有三个处理单元，⼀个是定点处理单元，通常称为中央处理单元（CPU），它由⼀个或多个整数处理部件组成；第⼆个是浮点处理单元（FPU），它由浮点加减法部件和浮点乘除法部件等组成；第三个是图形加速部件，也称为图形处理单元（GPU），这是现代处理机中不可缺少的⼀个部分。
mips中为了减少停顿采用的技术MIPS是一种常用的指令集架构，它采用了一系列的技术来优化指令的执行过程，从而减少停顿，提高程序的执行效率。
本文将介绍MIPS中为了减少停顿所采用的一些技术。
一、流水线技术流水线技术是指将指令的执行过程分为若干个阶段，然后将不同指令的不同阶段交错在一起，从而使得多条指令可以同时执行，提高了程序的执行效率。
MIPS中采用了五级流水线技术，将指令的执行过程分为取指阶段、译码阶段、执行阶段、访存阶段和写回阶段。
这样，每条指令在执行时都可以同时进行不同的阶段，从而提高了程序的执行效率。
二、分支预测技术分支指令是指在程序执行过程中需要根据条件进行跳转的指令。
在MIPS中，分支指令的执行会影响到流水线的执行顺序，从而导致停顿的发生。
为了减少这种停顿，MIPS采用了分支预测技术。
分支预测技术是指根据历史执行情况，对分支指令的跳转方向进行预测。
如果预测正确，程序可以继续执行；如果预测错误，程序会回滚到分支指令的位置重新执行。
通过这种技术，可以减少分支指令带来的停顿，提高程序的执行效率。
三、乱序执行技术乱序执行技术是指在流水线执行过程中，根据指令之间的依赖关系，动态调整指令的执行顺序，从而减少停顿的发生。
MIPS中采用了乱序执行技术，将指令的执行顺序动态调整，使得不同指令之间的依赖关系得到了更好的处理。
通过这种技术，可以充分利用流水线的并行性，提高程序的执行效率。
四、多发射技术多发射技术是指在一个时钟周期内同时发射多条指令，从而提高程序的执行效率。
MIPS中采用了多发射技术，将流水线分为多个单元，并且每个单元都可以发射一条指令。
通过这种技术，可以使得多条指令可以同时执行，提高程序的执行效率。
五、数据前推技术数据前推技术是指在指令执行过程中，将计算结果直接传递给需要使用这个结果的指令，从而减少停顿的发生。
MIPS中采用了数据前推技术，将计算结果直接传递给需要使用这个结果的指令，从而避免了停顿的发生，提高了程序的执行效率。
并行计算机体系结构的分类并行计算机体系结构是指在计算机系统中，通过多个处理单元同时执行任务以提高计算性能的架构框架。
根据不同的设计思想和实现方式，可以将并行计算机体系结构分为多种分类。
本文将介绍几种常见的并行计算机体系结构分类，并对其特点和应用进行讨论。
1.指令级并行体系结构指令级并行体系结构（ILP）是基于指令级并行技术的一种体系结构。
ILP通过将单个指令分解为多个子操作，并在不同的处理单元上同时执行这些子操作，从而实现指令级并行。
这种体系结构适用于需要大量计算的应用，如科学计算和图像处理。
其中，超标量和超流水线是常见的ILP体系结构。
超标量体系结构通过在一个时钟周期内同时发射多条指令，利用指令之间的独立性实现指令级并行。
而超流水线体系结构则通过将指令的执行过程分解为多个阶段，并在每个阶段上同时执行不同的指令，进一步提高了并行度。
这两种体系结构能够充分利用处理器资源，提高计算性能。
2.向量处理体系结构向量处理体系结构是基于向量处理器的一种体系结构。
向量处理器是一种特殊的处理器，能够同时处理多个数据元素。
在向量处理体系结构中，处理器通过执行向量指令，对向量数据进行并行操作。
这种体系结构适用于需要对大规模数据进行相同类型操作的应用，如科学计算和图像处理。
向量处理体系结构具有高度的并行性和数据吞吐量，能够充分利用数据级并行性，提高计算性能。
然而，由于向量处理器对数据的访问具有一定的限制，对于不适合向量化的应用，其性能优势可能会受到限制。
3.多核体系结构多核体系结构是指在一个计算机系统中，使用多个处理核心来执行任务的体系结构。
每个处理核心都具有独立的处理器和内存，能够同时执行不同的指令流。
多核体系结构适用于需要同时执行多个任务的应用，如服务器和大数据处理。
多核体系结构具有良好的可扩展性和并行性，能够提供更高的计算性能。
通过将任务分配给不同的处理核心，可以充分利用系统资源，提高系统的吞吐量和响应速度。
然而，多核体系结构也面临着任务调度和数据共享的挑战，需要采用合适的并行编程模型和调度算法来优化性能。
综述：ILP开发的技术前言：自1985年以来，所有的处理器都采用流水线方式使指令的执行可以重叠进行以提高性能。
由于可以将指令间的关系看做是并行的，因此将指令间的这种潜在重叠称为指令级并行。
于是可以提高对并行的开发能力的相关技术越来越受到人们的关注。
开发指令级并行的方法大致可以分为两类，一种方法是依赖硬件，动态地发现和开发指令级并行；另一种方法是依赖与软件技术，在编译阶段静态地发现。
本文中将着重讨论一系列技术，这些技术都是用来提高指令序列的并行度和扩展流水线的。
1.静态编译技术基本流水线调度：要保持一条流水线不停顿，就要去发现可以流水重叠的不想关的指令序列，并加以充分利用，为避免流水线的停顿，就要事先找出指令代码中的相关指令并将它们分离，使其相隔的时钟周期能正好等于原来指令在流水执行时的时延，编译器进行这类调度的能力既依赖与程序的指令级并行度，也依赖与流水线中功能单元的时延循环展开：为了增加有效操作对转移和开销指令的比重，循环展开可以通过多次复制循环体和调整循环中止码来实现。
循环展开因为它可以消除转移，所以它也可以用来改进调度。
并且循环展开这种转换方法对于各种处理器，从简单流水线到超标量多发射结构等等都适用。
但是这种转换也确实增加了现代编译器的复杂度。
预测技术：由于需要通过转移冒险和停顿来保持控制相关，因此转移会降低流水线的性能，上文提到的循环展开是减小转移冒险的方法之一，另外还可以通过转移预测技术来减小转移引起的性能损耗。
而且想要开发指令级并行，转移预测的准确率是个关键问题。
可以通过缓存的容量，增加每次预测所使用的预测方案的准确率。
2.动态调度机制一个简单的静态调度流水线负责取指令并将它发射出去，除非流水线中的指令与取到的指令之间存在数据相关，而且无法通过旁路技术和直接通路技术避免数据相关，如果有无法避免的数据相关，那么检测冒险的硬件将从使用相关结果的指令开始暂停流水线，停止取指令和发射指令的工作，直到相关被清除，而动态调度技术就是通过硬件对指令执行顺序进行重组，在保持数据流和异常行为的同时减少停顿，它可以处理一些在编译阶段无法预见的相关情况，同时它简化了编译器的设计，但是动态调度的这些优势是以硬件复杂度的显著增加为代价的。
