指令级流水指令级并行

1/10计算机体系结构Report2指令级流水和指令级并行——永无休止的“完美”追求戚洪源2/10目录一、性能瓶颈来源................................................................41、单周期、多周期MIPS结构性能瓶颈.........................................................................................42、简单的五级流水MIPS性能瓶颈来源.........................................................................................4相关.................................................................................................................................................4冲突.................................................................................................................................................5二、突破瓶颈的可能性............................................................5三、性能提升的具体方法..........................................................61、简单的硬件实现方法...................................................................................................................6定向技术.........................................................................................................................................6投机.................................................................................................................................................62、基于软件（编译器）的静态调度方法.......................................................................................7预测分支.........................................................................................................................................73、软硬件结合的动态调度方法.......................................................................................................8Tomasulo算法................................................................................................................................8动态分支预测.................................................................................................................................84、多指令流出...................................................................................................................................9基于静态调度的多流出技术.........................................................................................................9基于动态调度的多流出技术.........................................................................................................9超长指令字技术...........................................................................................................................10超流水线技术...............................................................................................................................105、循环展开和指令调度.................................................................................................................10四、总结.......................................................................103/10摘要：有人说，如果计算机科学与技术是一座金字塔，位于塔尖的一定是高性能计算。从计算机诞生至今，每一次进步都是对于计算机性能极限的一次刷新。人类对于计算性能日益膨胀的需求，前沿科技对于高性能计算的考验，都促使这一领域不断发展。单纯硬件技术上的改革是非常重要的：主频的提高、稳定的晶体管……但我们同样惊艳于并行技术在其中发挥的神奇的作用。各种并行技术犹如催化剂一般，使提高计算机性能的进程大大加快。这些技术的应用，不断挖掘着计算机潜在的性能，也让人类在一条追求“完美”的道路上不断前行。何谓“完美”？这是一个看起来复杂实际上非常简单的问题。“完美”，就是让计算机每一个部件每时每刻全负荷运作，发挥最高的性能。看似简单，但却很难实现，也不可能实现。并行技术的发展，也是追求“完美”的尝试。然而程序“性本恶”，程序本身的许多特性为并行化带来了不小的麻烦。我们其实是在和自己斗争。“榨干计算机每一滴性能”，这是ASC15上浪潮集团首席科学家王恩东演讲时说的一句话。在我看来，不论是指令级流水还是指令级并行，目的都是为了“榨干计算机每一滴性能”。在这个过程中，出于需要又出现了一些非常特殊的结构上的支持。本文将基于MIPS结构，通过对于性能瓶颈的来源、性能突破的可能性、性能提升的具体方法这三方面全面系统地阐述指令级流水和指令级并行的相关知识。最后再提出一些感想。在第一部分中，我们会讲述单周期到多周期再到流水线的发展过程，并对流水线的性能瓶颈进行具体分析。在限制流水线性能的三个方面中，前两点只与硬件工艺有关，最后一点相关和冲突却可以通过许多技术来实现突破。第二部分中，我们会继续讨论第一部分中提出的限制流水线性能的重要因素：相关和冲突。这一部分，我们将从原理层面阐述突破这一瓶颈是可行的。最后一部分，我们按照分类，具体阐述了多种提升性能的方法。4/10一、性能瓶颈来源这一部分将由简单到复杂，只提出限制性能的原因，不提出解决方案。这一部分的讨论结果对后面的研究至关重要。1、单周期、多周期MIPS结构性能瓶颈单周期和多周期最大的问题就是部件利用率不高。将每一条指令的执行过程粒度化，我们可以发现：并不是每时每刻所有的部件都处于工作状态。大多数时刻只有一个部件在工作。这种浪费是非常可怕的，不能让其他部件都闲在那里等一个部件。如果在同一时刻能让更多部件运行起来，性能一定会大大提高。2、简单的五级流水MIPS性能瓶颈来源简单的五级流水是一种最基本的流水结构，在一定程度上解决了单周期和多周期部件空闲的问题。然而，折中简单的五级流水结构并不是没有缺陷的。一方面，如果在设计流水线的时候考虑不周全，使流水线各段不均匀，即有的段比别的段要长的多，这个段就成了瓶颈。计算机的时钟周期取决于这个瓶颈段的延迟时间。因此，在设计流水线式要尽可能使各段时间相等。另一方面，由于流水寄存器延迟和时钟偏移开销，流水线增加了许多额外开销。由于这些额外开销的存在，会使每条指令的执行时间有所增加。这些开销也限制了流水级数的加深。最后，也是最关键的，指令的相关和冲突。当一个流水线设计完成后，上面的两种问题对使用流水线影响就不会太大了。因为这些开销是现实存在的，不会消亡。我们只能合理设计，提升工艺，尽量缩小它们对于流水线性能的影响。但指令的相关和冲突，是确确实实限制流水性能的重大瓶颈！相关1、数据相关对于两条指令i（在前，下同）和j（在后，下同），如果下述条件之一成立，则称这两条指令数据相关。i.指令j使用指令i产生的结果ii.指令j与指令k数据相关，而指令k又与指令i数据相关5/102、名相关当指令i与指令j出现如下两种情况，都属于名相关。i.反相关。如果指令j写的名与指令i读的名相同，则称指令i与指令j发生了反相关。ii.输出相关。如果指令j与指令i写的名相同，则指他们发生了输出相关。名相关的两条指令之间并没有数据流动，只是使用了相同的名。冲突1、结构冲突因硬件资源满足不了指令重叠执行的要求而发生的冲突。如：当只有一个存储器时，存数和取指就会发生结构冲突。2、数据冲突当指令重叠执行时，因需要用前面指令产生的结果而发生的冲突。这其中又分为写后读冲突和写后写冲突。其中写后读冲突只发生在这样的流水线中：流水线中不止一个段可以进行写操作。3、控制冲突流水线遇到分支指令和其他会改变PC值的指令所引起的冲突。总的来说，确定指令之间存在什么样的相关，对于确定程序中有多少并行性以及如何开发并行性具有重要的意义。如果两条指令相关，它们就不可以并行执行，只能部分重叠执行。冲突时针对具体的流水线来说的，由于相关的存在，使指令流中下一条指令不能在指定的时钟周期内执行。相关是程序固有的一种属性，即“性本恶”，它反映了程序中指令相互依赖的关系。而具体的一次相关是否会带来冲突以及会导致多长时间的停顿，则是由流水线自身决定的。二、突破瓶颈的可能性自上世纪80年代中期以来，几乎所有的处理机都利用流水线来使指令重叠并行执行。6/10这种指令之间存在的潜在并行性成为指令级并行。但上一个部分出现的问题，大多限制了指令级并行。我们在这一部分首先概述开发并行性的可能性。为下一部分的具体策略做铺垫。程序的执行应当有自身的一个顺序。但是这个顺序并不是一成不变的。有些语句的调度并不会影响程序的执行结果，这也是我们可以进行指令调度的一个前提。我们介绍的各种软硬件技术的目标是开发程序并行性，但同时也不能护士程序顺序执行的要求。那么为了保证程序执行结果正确，我们必须保证程序的什么属性不受破坏呢？这两个属性就是数据流和异常行为。保持异常行为是指无论怎么改变指令的执行顺序都不能改