4.2 指令的动态调度_动态调度是指令集并行的

 

4.2 指令的动态调度

在现代处理器设计中，指令的动态调度是提高指令级并行性(ILP)的关键技术之一。通过动态调度，处理器能够以非程序顺序执行指令，从而有效地利用处理器资源，减少执行停顿，提升执行效率。本节将深入探讨指令动态调度的原理与实现，特别是Tomasulo算法如何克服指令执行中的依赖和冲突，实现高效的指令并行执行。

动态调度的必要性

传统的按序执行处理器在执行指令时严格遵守程序顺序，这种方式简单直观，但在面对指令之间的数据依赖和资源冲突时，往往会导致流水线停顿。例如，SUB.D指令和DIV.D指令之间由于对F4的依赖而产生停顿，ADD.D指令虽然与当前流水线中的指令无关，但也因此被不必要地阻塞。动态调度技术通过允许指令以非程序顺序执行，使得像ADD.D这样的指令能够绕过前面的停顿，提高了流水线的利用率和处理器的整体性能。

Tomasulo算法简介

Tomasulo算法是一种高效的动态调度算法，旨在解决数据依赖和资源冲突问题，实现高度的指令并行执行。算法的核心思想是使用寄存器重命名技术来消除WAR（写后读）和WAW（写后写）冲突，同时采用保留站来动态管理指令的执行。这种方法不仅允许乱序执行指令，还支持乱序完成，极大地增加了执行指令的灵活性和并行度。

乱序执行与完成

在Tomasulo算法下，指令的流出（Issue）分为两个阶段：首先检查结构冲突，若无冲突则指令被流出；其次等待数据依赖解决后读取操作数。这种方式使得指令即使在程序顺序上后续的指令因数据依赖未解决而停顿时，也能够被执行，只要它们的操作数已经准备就绪。因此，指令的执行顺序和完成顺序可以与程序顺序不同，大大提高了处理器资源的利用率和执行效率。

异常处理与精确异常

Tomasulo算法通过复杂的逻辑保证了正确的异常行为，即只有在指令严格按程序顺序执行时才会发生的异常，才被允许产生。这种机制确保了即使在乱序执行的环境下，也能够正确处理异常。然而，动态调度也可能导致不精确异常的发生，这给异常处理带来了额外的复杂性。

结论

指令的动态调度是现代处理器设计中不可或缺的一部分，它通过允许指令以非程序顺序执行来提高并行度和处理器性能。Tomasulo算法作为动态调度的经典实现，通过寄存器重命名和保留站技术解决了数据依赖和资源冲突问题，使得处理器能够更高效地执行指令。尽管动态调度增加了处理器设计的复杂性，特别是在异常处理方面，但它所带来的性能提升使得这种复杂性成为值得的。

 

4.2.2 Tomasulo算法

Tomasulo算法，由Robert Tomasulo发明并首次在IBM 360/91的浮点部件中应用，是一种旨在克服数据依赖和资源冲突、提高指令级并行性的动态调度算法。它通过精巧的硬件机制，实现了指令的乱序执行和乱序完成，从而显著提高了处理器的性能。下面详细介绍Tomasulo算法的基本思想、实现原理和其在现代处理器设计中的应用。

基本思想

Tomasulo算法的核心思想基于两个主要方面：

• 记录和检测指令之间的相关性：算法通过动态地监测操作数的就绪状态来启动指令的执行，从而最小化了由于读后写（RAW）冲突引起的停顿。
• 寄存器换名技术：通过引入寄存器重命名机制，Tomasulo算法有效地消除了写后读（WAR）和写后写（WAW）冲突。

IBM 360/91采用Tomasulo算法的原因主要是为了在保持指令系统统一的前提下实现高性能，同时考虑到其浮点寄存器数量的限制和访存及浮点计算时间的长短，这些因素都促使了对更高效硬件调度策略的需求。

寄存器换名消除名相关

在Tomasulo算法中，寄存器换名通过引入临时寄存器来解决名相关问题。例如，通过将代码中重复出现的寄存器F6和F8分别换为临时寄存器S和T，可以消除ADD.D和MUL.D之间的输出相关（WAW冲突）以及ADD.D和SUB.D之间的反相关（WAR冲突）。

基于Tomasulo算法的MIPS处理器浮点部件结构

在基于Tomasulo算法的MIPS处理器设计中，特别关注浮点和load/store部件。这种设计采用了多个功能部件，并利用保留站来跟踪指令的执行状态、操作数的可用性以及结果的输出。浮点操作和load/store操作通过一个公共的数据总线（CDB）与保留站和寄存器文件相连，确保数据的正确分发。

保留站的引入是Tomasulo算法的关键，它们不仅负责存储即将执行的操作数，也为等待执行的指令提供了缓存。通过这种机制，算法能够在操作数准备就绪时立即启动指令的执行，而不必等待程序顺序上的前序指令完成，从而实现了高度的并行性和效率。

结论

Tomasulo算法通过其独特的动态调度机制，在现代处理器设计中仍然发挥着重要作用。它不仅解决了指令之间的数据依赖和资源冲突问题，还提高了处理器的吞吐率和执行效率。尽管其实现增加了处理器的复杂性，但所带来的性能提升使其成为高性能计算领域的重要技术之一。

在Tomasulo算法的实现框架中，各组成部分协同工作，以实现指令的高效执行和并行处理。下面是对图4.1中描述的Tomasulo算法实现框架各组成部分的简要说明：

① 保留站

保留站位于功能部件的入口，为即将执行的指令提供缓存。每个保留站负责存储一条已经流出等待执行的指令，包括操作码、操作数以及用于冲突检测和解决的信息。例如，浮点加法器前的保留站分为Add1、Add2、Add3，浮点乘法器前的保留站则分为Mult1和Mult2。保留站的关键作用在于指令流出时的寄存器换名，以及操作数的缓存和冲突解决。

② 公共数据总线（CDB）

公共数据总线（CDB）是一个关键的数据通路，用于将所有功能部件的计算结果广播到所有需要这些结果的地方，包括其他保留站和浮点寄存器。它使得计算结果能够直接从产生它的保留站传送到所有等待该结果的保留站，无需经过寄存器，从而提高了数据传输的效率和处理速度。

③ Load缓冲器和Store缓冲器

Load缓冲器和Store缓冲器类似于保留站，但专门用于处理存储器读/写操作。Load缓冲器负责存放读取存储器数据的地址和数据，Store缓冲器则负责存放写入存储器的地址和数据。这些缓冲器使得访存操作能够并行进行，并且与CPU的计算操作重叠，提高了处理器的整体效率。

④ 浮点寄存器（FP）

浮点寄存器组包含一系列的浮点寄存器，例如FO、F2、F4等，总共16个。这些寄存器通过一对总线连接到功能部件，并能通过CDB接收计算结果，是存储浮点数值的主要地方。

⑤ 指令队列

指令队列负责存储从指令部件送来的指令，并按照先进先出的原则流出指令。这保证了指令的按序流出，为后续的寄存器换名和执行提供了基础。

⑥ 运算部件

运算部件包括浮点加法器和浮点乘法器，分别负责执行加法/减法操作和乘法/除法操作。这些功能部件是执行浮点运算的核心，与保留站紧密配合，实现指令的并行执行。

Tomasulo算法通过这些组成部分的协同工作，有效地解决了指令执行过程中的数据依赖和资源冲突问题，实现了高度的指令级并行性。通过动态调度和寄存器换名技术，该算法使得多个指令能够在不同的执行阶段并行处理，从而显著提高了处理器的性能和效率。

 

 

在Tomasulo算法的实现中，各个组成部分协同工作，确保了高效的指令执行和数据流动。下面是对图4.1中各组成部分的简要说明，展示了这些部件如何在算法中发挥作用。

保留站

保留站位于运算部件的入口处，为浮点加法器和乘法器提供缓冲和调度功能。每个保留站都有一个唯一的标识字段，用于存储已经流出并等待执行的指令，包括操作码、操作数及处理冲突所需的信息。当指令到达保留站时，如果源操作数已就绪，则直接取入；如果未就绪，保留站将记录下产生这个操作数的保留站标识。

公共数据总线(CDB)

CDB是所有功能部件计算结果的共享数据通路，用于将计算结果直接广播到所有需要该结果的地方，包括其他保留站、浮点寄存器、和store缓冲器。这种直接广播机制最大限度减少了读后写（RAW）冲突的影响。

load缓冲器和store缓冲器

load缓冲器和store缓冲器类似于保留站，用于处理读/写存储器的指令。它们存放用于计算有效地址的分量、记录正在进行的访存操作以及保存操作结果，直到数据可以被传输或接收。

浮点寄存器(FP)

共有16个浮点寄存器，它们通过CDB与系统的其他部分连接，用于存储计算结果或提供操作数。这些寄存器是执行浮点运算操作的基础。

指令队列

指令队列按照先进先出的原则存储从指令部件送来的指令，并控制指令的流出。指令的流出顺序决定了程序执行的顺序。

运算部件

运算部件包括浮点加法器和乘法器，分别负责完成加法、减法以及乘法、除法操作。这些部件根据保留站中的指令和操作数就绪状态执行相应的运算。

通过上述组件的配合，Tomasulo算法能够在不同阶段动态地调度指令执行，解决数据依赖和资源冲突问题，实现高效的指令级并行。保留站的引入允许了寄存器换名，有效地避免了WAR和WAW冲突，而CDB的使用则最大化地减少了RAW冲突的影响。此外，通过在指令流出时进行寄存器换名和操作数缓冲，Tomasulo算法确保了即使在高度并行的环境下，也能保持正确的程序执行顺序和数据一致性。

 

 

 

 

在Tomasulo算法中，每条指令从流出到执行再到写结果，都通过保留站、寄存器状态表、和其他组件的相互协作来管理。这种管理确保了即使在出现数据依赖的情况下，处理器也能尽可能地维持高效的执行流程。下面是对例4.1的分析，展示了第一条L.D F6,34(R2)指令完成并写入结果时，Tomasulo算法所用的各信息表中的内容。

保留站内容

• Load1保留站（对应第一条L.D F6,34(R2)指令）在指令执行完毕后，会将结果写入CDB，并通过CDB更新等待该数据的其他保留站和寄存器状态。这时，Load1的状态变为空闲（Busy标志设置为no），因为它已经完成了任务。
• Load2保留站（对应第二条L.D F2,45(R3)指令）计算了有效地址，正等待存储器响应以加载数据。
• Mult1和Add1保留站分别对应MUL.D FO,F2,F4和SUB.D F8,F2,F6指令。这些保留站会记录操作类型（Op字段）、是否忙碌（Busy字段）、源操作数是否就绪（通过Qj/Qk字段检查）、以及已就绪的源操作数值（Vj/Vk字段）。

寄存器状态表

寄存器状态表（Qi字段）指示了某个寄存器的值将由哪个保留站提供。在第一条L.D指令完成后，如果F6是该指令的目标寄存器，Qi字段对应F6的条目会清空，表示F6中的值现在是就绪的。其他指令如MUL.D、SUB.D、DIV.D和ADD.D如果依赖于F6的值，它们在对应保留站的Qj/Qk字段会随之更新。

指令执行状态

虽然图4.3中的指令执行状态表仅为了帮助理解，并非硬件的一部分，但它展示了各条指令流出、执行、和写结果的状态。例如，第一条L.D指令已经完成并写结果，而其他指令依旧在它们的执行阶段中。

总结

通过例4.1的分析，我们可以看到Tomasulo算法如何在指令执行过程中动态管理数据依赖和资源分配，以优化执行效率。算法通过保留站来跟踪指令的执行状态和操作数的就绪状态，通过寄存器状态表来管理寄存器值的来源，以及通过CDB来广播计算结果。这种机制使得即便在数据依赖频繁的情况下，处理器也能有效地执行多条指令，最大限度地提高并行度和资源利用率.

 

 

Tomasulo算法的两个主要优点相比于其他动态调度方法（例如记分牌方法）体现在其高效处理冲突和并行度的能力上。通过分布式冲突检测和解决WAW（写后写）及WAR（写后读）冲突的机制，Tomasulo算法能够优化并行执行指令，提高处理器性能。以下是这些优点的具体解释：

1. 分布式冲突检测

在Tomasulo算法中，冲突检测是通过保留站和公共数据总线（CDB）分布式地完成的。当多条指令等待同一运算结果时，这个结果一旦通过CDB产生，就可以立即广播给所有等待的指令，允许它们同时执行。这与使用集中寄存器组的方法形成对比，在后者中，指令必须等待结果被写入寄存器后才能依次从寄存器组读出，这限制了并行度。

2. 消除WAW和WAR冲突

Tomasulo算法通过保留站进行寄存器换名，并在操作数就绪时立即将其放入保留站，从而消除了WAW和WAR冲突导致的停顿。在传统的调度方法中，这些冲突可能导致指令执行的延迟，因为必须等待先前的指令完成并更新了寄存器的值。

例4.2 解析

在例4.2中，假设操作的延迟分别为：load指令1个时钟周期，加法2个时钟周期，乘法10个时钟周期，除法40个时钟周期。当MUL.D指令准备写结果时，它已经完成了乘法操作，并准备将结果通过CDB广播。此时，MUL.D指令的执行并不受前面指令的WAR冲突影响，因为通过保留站和CDB的机制，ADD.D可以在不等待DIV.D完成的情况下，先于DIV.D完成并将结果写入F6。

图4.4显示了MUL.D指令准备写结果时的状态表内容。从图中可以看出，MUL.D（Mult1保留站）的结果准备广播，而此时F6、F8、F10等寄存器的状态表显示了它们的值将由哪个操作更新。例如，如果F0是MUL.D指令的目的寄存器，它将被更新为Mult1的结果。

具体算法步骤

Tomasulo算法中，指令流出、执行和写结果的条件及操作如下：

• 流出（Issue）：检查是否有空闲的保留站。如果有，将指令送入保留站，并记录操作数状态。如果操作数已就绪，记录其值；如果未就绪，记录产生该操作数的保留站标识。
• 执行（Execute）：监视CDB，等待未就绪操作数的结果。一旦所有操作数就绪，开始执行指令。
• 写结果（Write Result）：操作完成后，将结果通过CDB广播给所有等待该结果的保留站和寄存器。

通过这一系列步骤，Tomasulo算法能够有效地管理指令执行，最大化指令级并行，并优化处理器资源的利用。

 

 

Tomasulo算法通过其独特的设计，有效地解决了指令在执行过程中可能遇到的各种依赖和冲突问题，特别是如何通过动态调度技术来优化指令的执行流程。下面是对指令流出阶段的处理细节的进一步解释，特别是针对浮点运算指令和load/store指令。

浮点运算指令的流出

当一条浮点运算指令准备流出时，系统首先检查是否有空闲的保留站可用（设为r）。以下步骤将被执行：

• 第一操作数的检查与处理： 如果第一操作数（源操作数）已经就绪（即Qi[rs]=0，表示寄存器rs中的数据已就绪），则将该操作数的值（Regs[rs]）直接存入保留站r的Vj字段，并将Qj设置为0，表示该操作数在保留站中已就绪。如果第一操作数未就绪，则将产生该操作数的保留站编号存入Qj，以便于后续的数据依赖解决。

• 第二操作数的检查与处理： 同样地，第二操作数（目标操作数）的就绪性也会被检查。如果就绪，其值会被存入Vk字段；如果未就绪，相应的保留站编号会被存入Qk。

• 设置保留站状态与操作码： 保留站被标记为忙（Busy=yes），并记录当前指令的操作码（Op）。

• 更新寄存器状态表： 寄存器状态表中的目的寄存器rd的项会被更新为当前保留站的编号r，预示着该寄存器将来的值将由这个保留站提供。

load和store指令的流出

对于load和store指令，流出的处理流程有所不同，主要体现在对地址的处理和数据的准备上：

• 地址的准备： 如果地址计算所需的基地址已经就绪，其值会被直接存入缓冲器单元的Vj字段，并将Qj设置为0。如果基地址未就绪，将产生该地址的保留站编号存入Qj。

• 目标寄存器的处理（仅限于load指令）： load指令的目标寄存器（即要将数据加载到的寄存器rt）在寄存器状态表中将被更新为当前缓冲器单元的编号r，以指示将来该寄存器的值将由这个缓冲器单元提供。

• 数据的准备（仅限于store指令）： 如果要存储的数据已经就绪，其值会被存入Vk字段；如果未就绪，相应的保留站编号会被存入Qk。

通过这种方式，Tomasulo算法不仅优化了指令的执行顺序，减少了执行过程中的停顿，同时也通过寄存器换名技术解决了WAR和WAW冲突，保证了高效和正确的程序执行。

 

 

Tomasulo算法通过其独创的设计，在动态调度方面为现代处理器的性能优化提供了重要的策略。该算法主要依靠保留站、寄存器状态表、和公共数据总线（CDB）来实现对指令执行流程的优化。通过对执行阶段和写结果阶段的详细讨论，我们可以更深入地理解这一算法的工作原理及其在解决数据依赖和资源冲突方面的优势。

执行阶段

对于浮点操作指令和load/store指令的执行条件主要考虑操作数的就绪性以及指令在队列中的位置。

• 浮点操作指令的执行条件是两个源操作数都就绪，即保留站中的Qj和Qk字段都为0。当这一条件满足时，指令可以执行其指定的运算，并最终产生结果。

• load/store指令的执行则稍有不同。load指令的执行分为计算有效地址和访存读取数据两个步骤。store指令在写结果阶段进行数据的实际写入操作。对于这类指令，关键的执行条件是地址计算所需的基地址就绪，并且指令处于缓冲队列的头部。

写结果阶段

这一阶段是算法中至关重要的部分，涉及到计算结果的广播和对等待该结果的寄存器或保留站的更新。

• 浮点运算指令和load指令的结果一旦通过执行阶段产生，就会在CDB就绪的情况下被广播。这一广播操作使得所有等待该结果的寄存器和保留站能够在同一个时钟周期内接收到结果，从而可能使得多条指令在下一个时钟周期同时开始执行。

• store指令的写入操作在数据和地址都就绪的情况下进行。这一操作不仅涉及数据的实际写入存储器，还包括释放当前使用的缓冲器单元。

Tomasulo算法的优势与挑战

Tomasulo算法的主要优势在于其能够有效地解决WAW和WAR冲突，提高处理器在面对复杂数据依赖情况时的执行效率。算法通过分布式的冲突检测逻辑和动态的寄存器换名机制，实现了高度的指令级并行性。然而，这种算法的实现复杂度较高，需要大量的硬件资源，尤其是在单个CDB的带宽限制下。

尽管存在挑战，Tomasulo算法在多流出处理器设计中的重要性逐渐增加，特别是对于难以静态调度的代码。算法不仅为硬件前瞻执行提供了基础，而且还为处理分支指令和控制相关问题提供了有效的策略。

随着对更高性能处理器的需求不断增长，Tomasulo算法及其变体将继续在现代处理器设计中发挥关键作用，帮助设计者克服指令执行过程中的各种挑战，实现更高的执行效率和处理器性能。