使用延迟重构程序顺序的选择逻辑

摘要

一种处理设备，其包括调度多个指令以供执行的选择逻辑。该选择逻辑计算准备好被调度以供执行的多个指令中的每一个的重构程序顺序(RPO)值。选择逻辑基于延迟RPO值创建指令的有序列表，该延迟RPO值包括来自先前执行周期的所计算的RPO值，并基于该有序列表分派指令以供调度。

说明书

技术领域

本公开内容涉及处理设备的领域，且尤其涉及使用重构程序顺序(reconstructed program order)的用于多串乱序处理器的指令调度器的选择逻辑。

背景

带有有序提取和乱序执行能力的当代通用超标量处理器的性能受到指令级并行性(ILP)的利用率的限制，指令级并行性(ILP)表征程序算法的固有并行性。更好地利用ILP的一个障碍是大多数程序代码的连续性质以及相应的指令提取的有序性质。除了依赖于乱序分派和执行能力来利用ILP之外，某些处理器也依赖于更深的管线，因为管线化允许处理器利用ILP。

在这样的处理器中，为了取得所期望的性能目标(用每周期指令数(IPC)衡量)，可以被称为关键循环的一些逻辑片段在单个执行周期中评估，否则它们对以上所描述的更深的管线化来说是障碍。一个这样的关键循环包括由唤醒逻辑和选择逻辑构成的指令调度逻辑。

唤醒逻辑包括跟踪数据依赖性和检查指令所需要的源操作数是否可用，唤醒逻辑判断何时准备好发送指令以供执行。基于某种策略，选择逻辑判断应当发送这些就绪指令中的哪些以供执行。选择逻辑仅仅当存在比可用执行资源的数量更多的就绪指令时才可应用。由于指令不能被唤醒逻辑“认证为就绪”直到其所依赖的所有指令被选择并发送以供执行，唤醒逻辑和选择逻辑形成关键循环以供执行。另外，选择逻辑需要选择正确的指令来调度给执行单元，以使得它可以在该关键路径上向前移动指令(即，唤醒相关的指令)。因而，对于具有乱序指令执行的每一处理器，如果存在准备好占用单个执行资源且符合单周期调度循环的计时预算的多个指令，选择逻辑就确定首先选择哪个指令，这样的选择逻辑对取得所期望的性能来说是重要的。

对于多串乱序处理器(multi-strand out-of-order processor)来说，单周期调度循环的关键程度和正确的选择逻辑的重要性也是相关的，多串乱序处理器实现乱序提取技术(即，它能够从由编译器产生的多串程序表示的不同串乱序提取指令)。因而，不同于提取已经排序的指令序列并把它们按顺序分配给等待缓冲器的一些常规处理器，多串乱序处理器不知晓在串(strand)内的指令相对于来自也在等待缓冲器内分配的其他串的指令的程序顺序。

存在当前由常规乱序处理器中的选择逻辑使用的多种调度策略，诸如例如基于年龄的策略、基于位置的策略、循环法策略、编译器辅助的优先级策略、拆分调度窗口方法和免选择调度。然而，当与多串乱序处理器一起使用时，这些常规的策略具有显著的局限。例如，基于年龄的策略基于何时分配指令来调度指令以供执行，这是不适用的，这是由于这些指令是乱序分配的。基于位置的策略和循环法策略基于指令在等待缓冲器中的位置确定指令的优先级，它们具有较低的硬件成本，但需要忍受降低的性能。免选择调度通过把选择逻辑管线化成1周期唤醒循环和2周期选择循环从关键路径移除选择逻辑，它增加了时钟频率，但付出了折衷IPC的成本。

因而，需要这样的选择逻辑调度策略：可以利用ILP来在IPC方面取得更高性能，同时仍满足关键单周期调度循环的时序要求，而不增加多串乱序处理器中的选择逻辑的复杂性。

附图简述

作为示例而非限制在附图的各图中示出本公开内容。

图1是示出根据一种实施例使用延迟重构程序顺序在多串乱序处理器中的指令调度流程的框图。

图2是示出根据一种实施例把程序顺序信息附加到程序指令的流程的框图。

图3是示出根据一种实施例使用延迟重构程序顺序调度指令的方法的流程图。

图4是示出根据一种实施例重构程序顺序的方法的流程图。

图5是示出根据一种实施例重构程序顺序的硬件配置的框图。

图6是示出根据一种实施例基于重构程序顺序排序指令的方法的流程图。

图7是示出根据一种实施例基于重构程序顺序排序指令的系统的框图。

图8是示出根据一种实施例的计算机系统的框图。

详细描述

下列描述陈述了众多特定的细节，例如特定的系统、组件、方法等等的示例，以便提供对本发明的若干实施例的充分理解。然而，本领域中的技术人员应明显看出，无需这些特定的细节就可以实践本发明的至少一些实施例。在其他实例中，没有详细示出或者以简单的框图格式呈现众所周知的组件或方法，以免不必要地模糊本发明。因而，所陈述的特定细节仅仅是示例性的。特定实现可以不同于这些示例性细节，且仍然被认为是落在本发明的范围内。

在此描述的是使用延迟重构程序顺序在多串乱序处理器中调度指令的方法和系统。在一种实施例中，使用多串乱序处理器中的各串的延迟重构程序顺序(RPO)创建准备好被分派的指令的有序列表以供执行。这一列表可以管理指令将被分派以供每一周期执行的次序。在一种实施例中，可以引入特定数量的执行周期(例如，2个或3个周期)的延迟，以使得基于来自先前若干周期的有序列表选择被分派以供在给定周期中执行的指令。这从关键路径移除了选择逻辑的一部分(即，创建有序列表)，而不会降低性能。这种方法在复杂性方面可以类似于普遍流行的选择逻辑策略(例如，基于年龄的策略)，但在乱序提取处理器中得到更好的性能(即，更高的每周期执行指令数(IPC))。

在一种实施例中，在多串乱序处理器中使用延迟重构程序顺序调度指令相比于其他选择逻辑策略更好地利用了指令级并行性(ILP)，指令级并行性(ILP)表征程序算法的内在并行性。在一种实施例中，该策略通过使用延迟重构程序顺序值，也通过从循环的关键路径移除选择逻辑中用于创建有序列表的部分优化调度(即，唤醒和选择)循环，而不会损害IPC性能(相比于在一些乱序机器中实现的免选择调度，免选择调度优化该循环但降低了IP性能)。在一种实施例中，该策略也使得编译器免于对各串的明确地和静态地指定专用附加优先权的需求(相比于类似“分支路径”、“链长度”和“最大依赖(maximum dependents)”的策略，这些策略使用编译器支持来提供优先级信息)。另外，延迟RPO策略使得指令调度适应动态情形，且允许处理非确定性等待时间，例如缓存未命中和延时变化，这比类似“链长度”、“最大依赖”和“分支路径”的静态调度策略好得多，这些静态调度策略完全依赖于编译器设置优先级。此外，不需要独立的硬件逻辑来计算所执行的指令指针(EIP)，EIP保存在所有当前执行的各串当中最老的或最小的程序顺序值，且用于在引退时排序指令，这是由于延迟RPO策略的一部分(即创建有序列表)可以重复用于这一目的。

由于乱序提取能力和程序代码的基于串的表示，在一种实施例中，处理器可以取得非常大的指令窗口。为了可以完全利用ILP且维持高度持续的执行宽度(highsustained execution width)，有必要选择正确的串(且因而选择正确的指令)，它们可能处于从调度器中的可用的准备好被分派的串中分派的关键路径上。

在一种实施例中提出的串选择算法负责标识每一周期分派的正确的串，这又将促进相依指令的唤醒，且因此可以取得机器的高度持续的执行宽度。该算法基于每一串的延迟RPO创建准备好被分派的指令的有序列表，该有序列表管理在被分派以供每一周期执行的指令的次序。

由于多串乱序处理器实现乱序指令提取技术，该处理器通常不拥有关于指令相对于程序算法中的其他指令的程序顺序的信息。在一种实施例中，在编译时间把显式程序顺序信息附加到目标代码中的指令。这可以是仅仅针对将改变系统的状态的指令(这些指令例如存储器指令(例如，加载或存储))或可以引起中断的指令的情况。在一种实施例中，为了节省指令尺寸中的空间，在指令中仅编码对实际程序顺序的递增。这可以被称为递增程序顺序(IPO)。编译器保证严格按顺序把程序顺序值指派给在串内的各指令，从而在该串中形成程序顺序值的发展序列。

由于此后各指令被乱序分配，在一种实施例中，通过把指令中已编码的IPO添加到相同的串中先前分派的指令的程序顺序(或RPO)，处理器的选择逻辑重构该串的实际程序顺序。指令调度单元(ISU)中的等待缓冲器中的每一条目保存被考虑用于调度的该串的RPO，以及用于计算该串中的下一指令的RPO的IPO。在一种实施例中，等待缓冲器可以作为串调度触发器(strand scheduled flop，SSF)出现。SSF可以包括两级结构，其中第一级(SSF1)保存非就绪(包括新近分配的)指令以供唤醒逻辑考虑，且二级(SSF2)保存就绪指令并保存这些指令的RPO以供选择逻辑考虑。在另一实施例中，该串的RPO和在指令中编码的IPO可以保存在分离的缓冲器中，且被独立地多路复用。延时缓冲器可以存储先前周期的经更新RPO值，以使得延迟RPO值可以用来创建经排序优先级列表。

图1是示出根据一种实施例通过使用延迟重构程序顺序的多串乱序处理器中的指令调度单元的指令流的框图。可以针对各种模块和组件在调度指令以使用延迟重构程序顺序来执行中的角色来描述它们。

在编译时间，在由编译器帮助下，可以提取多串乱序架构中的指令并将其分组在各串中。串是主要相互数据依赖且有序执行的指令的序列。但是，不同的串的指令通常是独立的，因此，在通过唤醒逻辑解析在指令之间的任何数据依赖性之后，多串乱序架构可以并行执行来自众多串的指令。因而，如果不存在数据依赖性，第二串的指令也可以超过第一串的指令，即使原始源代码中第一串指令的位置可能领先于第二串指令的位置。

图1中所示出的处理器100逻辑上被划分成前端单元110、指令调度单元120、执行单元130和存储器子系统(图1中未示出)。在一种实施例中，前端单元110包括许多指令缓冲器，每一个对应于具体的串112、114、116。指令缓冲器可以用于接收所提取的指令。可以使用队列(例如，FIFO队列)或任何其他容器类型的数据结构实现指令缓冲器。可以基于执行或程序顺序排序存储在指令缓冲器中的指令。在一种实施例中，处理器100可以是下面相对于图8描述的处理设备802的一个示例，该处理设备在计算系统800中操作。

假定每一缓冲器中的指令与串112、114、116的其中之一相关联，存储在每一缓冲器中的指令可以是相互依赖的。在这样的实施例中，可以按执行次序缓冲指令，该顺序考虑了在该串的指令当中的数据依赖性，且因而严格按顺序执行。例如，需要执行串的第一指令的结果以便评估串的第二指令。因而，在专用于该串的指令缓冲器中，第一指令将领先于第二指令。在这样的实施例中，可以把被存储在缓冲器的首部的指令指派为供分派和执行的第一指令或下一指令。

在一种实施例中，指令调度单元120可以从串112、114、116的其中之一中的指令缓冲器接收指令，作为输入。指令调度单元120可以被组织成串调度触发器(SSF)。串调度触发器可以包括两级硬件结构，它在指令被分配给指令调度单元120时把各指令保存在每一串的首部。SSF可以包括一级硬件条目(即，SSF1140)和二级硬件条目(即，SSF2 160)，用于存储指令。前述的硬件条目可以包括但不限于硬件缓冲器、触发器或能够存储指令和/或数据的任何其他硬件资源。

此外，指令调度单元120包括用于检查被存储在SSF1 140中的指令的操作数准备状态的唤醒逻辑150。唤醒逻辑包括跟踪数据依赖性和检查指令所需要的源操作数是否可用，确定何时准备好发送各指令以供执行。唤醒逻辑150可以把被存储在一级硬件条目(例如，142、144或146)中的指令用作输入，且判断用于具体指令的操作数是否就绪。例如，如果特定指令被设计为把两个操作数相加以确定结果，则在可以执行该指令之前必须计算各操作数(可能由其他指令计算)。如果操作所依赖的所有操作都已经执行，则该操作被认为是“已就绪”。如果指令已就绪，则唤醒逻辑150可以把该指令移动到SSF2 160中的相应条目(例如，162、164、166)，以使得可以认为该指令可供执行。

在一种实施例中，指令调度单元120还可以包括选择逻辑170。选择逻辑170可以把存储在SSF2 160中的一个或多个指令用作输入，且确定各执行端口对所存储的那些指令的可用性。例如，如果存在n个串的指令和x个执行端口，则选择逻辑170可以从n个已存储指令选择多达x个以便指派给x个执行端口132、134、136。一旦执行端口被指派为可用于SSF2 160中存储的操作数就绪指令，指令就被分派给执行端口。在一种实施例中，选择逻辑170使用各串的延迟重构程序顺序来创建准备好被分派以供执行的指令的有序列表。这种列表可以管理被分派以供每一周期执行的指令的次序。在一种实施例中，选择逻辑170可以引入特定数量的执行周期(例如，2个或3个周期)的延迟，以便基于通过处理来自先前若干周期的重构程序顺序值创建的有序列表选择被分派以供在给定周期中执行的指令。这从关键路径移除选择逻辑的一部分(即，创建有序列表)，而不会降低时钟频率。下面提供关于选择逻辑170的额外细节。

在一种实施例中，执行单元130包括多个执行端口132、134、136，向这些执行端口分派指令调度单元120中所存储的操作数就绪指令。一旦指令被分派给执行端口，它就被执行并产生其结果。

在涉及多串乱序架构的各种实施例中，以逐个串的方式专门使用如图1中所示出的某些特征。在这样的实施例中，前端指令缓冲器、一级硬件条目、操作数检查模块和二级硬件条目可以专用于每一串。例如，第一串112可以与SSF1中的专用条目142和SSF2中的专用条目162相关联。相应地，可以仅针对第一串的指令使用这些特征。同样地，第二串114可以与SSF1中的专用条目144和SSF2中的专用条目164相关联，等等。

图2是示出根据一种实施例把程序顺序信息附加到程序指令的流程的框图。在一种实施例中，程序源代码200包括多个程序指令202、204、206和208。可以按照已定义的执行或程序顺序排列各程序指令，以使得在指令1 204之前执行指令0 202，在指令2 206之前执行指令1 204，等等。

在一种实施例中，编译器210可以把被命名为程序顺序(PO)的序号分配给被命名为经程序排序的指令(PO指令)的指令的子集中的每一个，在此把这些指令定义为访问存储器数据(的任何指令例如，加载或存储指令)，以及可以引起中断的任何指令。程序顺序值是按照升序指派的自然数，但是各值的序列不必是连贯的。例如，一个指令序列可以包括加载、加、加载、存储、减、存储和加载。可以给第一加载指派PO值1，给第二加载指派PO值2，给第一存储指派PO值4，给第二存储指派PO值5，且给第三加载指派PO值8。然后，编译器210可以跨越多个串220、230、240划分这一指令序列。基于在各指令之间依赖性，可以在各串之间划分指令。例如，依赖于另一指令的每一指令可以被放置在与它所依赖的指令相同的串中。另外，独立指令可以分布在可用的串220、230、240当中。

在一种实施例中，编译器把递增程序顺序(IPO)值附加到每一串中的每一PO指令(例如，222、224)。IPO值(例如，223、225)可以不编码指令的整个PO。相反，IPO可以仅编码递增值，递增值等于在其PO正被计算的指令的PO值和相同的串中下一PO指令的PO值之间的差异。在一种实施例中，处理器硬件使用附加到PO指令的IPO值重构各PO指令的PO值。对于诸如226之类的非PO指令，不必编码IPO信息，这是因为只有存储器指令和可以引起中断的指令才需要PO信息，以便维持存储器访问的正确次序。因而，运算指令可以不把IPO值作为它们的指令格式的一部分。因而，编译器210可以把程序拆分成多个串以供在多串架构上执行，同时通过把IPO字段附加到每一PO指令来保存程序顺序信息。

图3是示出根据一种实施例使用延迟重构程序顺序调度指令的方法的流程图。方法300可以由处理逻辑执行，处理逻辑可以包括硬件(例如，电路、专用逻辑、可编程逻辑、微代码等等)、软件(例如，在处理设备上运行以便以执行硬件仿真的指令)或其组合。处理逻辑可以基于从延迟重构程序顺序值创建的有序列表分派指令以供执行。在一种实施例中，方法300由如图1中所示出的选择逻辑170执行。

参见图3，在框310，方法300计算被选择以供分派的每一就绪指令的重构编程次序(RPO)值。在一种实施例中，如上所述，唤醒逻辑150唤醒SSF1 140中的指令并把指令移动到SSF2 160。因而，SSF2 160包括准备好以供调度的指令。每一周期中，当由选择逻辑170从SSF2 160分派特定数量的指令时，把相应数量的新指令移动到SSF2，以便代替被分派的那些。对于每一分派的指令，选择逻辑170可以计算RPO值。RPO值可以表示指令的实际(或“真实”)程序顺序。在一种实施例中，在选择指令以供分派时，选择逻辑170把附加到指令的递增程序顺序值加到从相同的串先前选择的指令的RPO值(它可以被存储在选择逻辑170中的缓冲器中)。这种操作的结果可以是这种指令的重构程序顺序(RPO)值。

在框320，方法300基于延迟RPO值创建指令的有序列表(即，延迟RPO值被用来确定应当分派哪些指令以供调度)。在一种实施例中，选择逻辑170可以基于先前的Z个周期(例如，2个或3个周期)计算的RPO值创建指令的有序列表。例如，如果在周期T中更新已分派指令的RPO值，那些经更新的RPO值可以被用于在稍后Z个周期调度指令。通常，该系统将期望，如果RPO在周期T中被更新，则选择逻辑将使用这种更新的RPO来在周期T+l(为了满足1周期调度)中创建有序列表。然而，在延迟RPO方法中，经更新的RPO将被用于周期(T+l)+Z。这从关键路径移除了选择逻辑的一部分(即，基于RPO值创建有序列表)，而不会有显著的性能损失。在一种实施例中，可以给予具有最老RPO值的指令最高优先级。

在框330，方法300基于延迟RPO值的有序列表分派最高的优先级指令。在一种实施例中，选择逻辑170把具有最老RPO值的指令分派给执行单元130。例如，如果存在五个执行端口，那么，可以分派来自有序列表的前五个指令。

图4是示出根据一种实施例重构程序顺序的方法的流程图。方法400可以由处理逻辑执行，处理逻辑可以包括硬件(例如，电路、专用逻辑、可编程逻辑、微代码等等)、软件(例如，在处理设备上运行以便执行硬件仿真的指令)或其组合。处理逻辑可以重构乱序处理器中的就绪指令的程序顺序。在一种实施例中，由如图1中所示出的选择逻辑170使用下面相对于图5描述的硬件配置500执行方法400。

参见图4，在框410，方法400读取附加到被分派给执行单元的指令的递增程序顺序(IPO)值。在一种实施例中，SSF2 160可以存储多个条目162、164、166，如果是PO指令，则每一条目都可以保存指令的相应IPO值。另外，通过从相同的串分派的先前指令计算的串的RPO值被保存在相应的SSF2条目中，或者被存储在分离的RPO缓冲器中。IPO值可以编码递增值，该递增值等于在相同的串中的先前指令的RPO值和编码IPO所针对的要计算的指令的RPO值之间的差异。因而，IPO值表示按照真实的程序顺序的指令之间的差异，该差异可归因于把各指令重新组织到各串，如上面相对于图2所述的。

在框420，方法400把IPO值添加到相应的串PO或RPO值。在一种实施例中，把串的PO值(表示从该串最近所选择的指令的PO值)和指令的IPO值应用到运算逻辑单元(ALU)，运算逻辑单元(ALU)把IPO值加到PO值(如果先前已经重构也可以称为RPO值)以便形成该串的经更新RPO值。在一种实施例中，可以使用二进制加法来组合PO和IPO。然而，备选地，可以使用其他运算操作，这取决于编译器如何针对PO计算IPO。

在框430，方法400把经更新的串RPO值存储在相应的SSF2条目或分离的RPO缓冲器中。由于在框420中新近计算的RPO值必定表示最近分派的指令，经更新的RPO值可以被用作串PO值。因而，RPO值可以被回写到RPO缓冲器，或者作为串PO值存储在SSF2的相应条目中。经更新的RPO值可以被用来排序指令以供调度，如下面将进一步描述的，并且计算(即，重构)等待缓冲器中的相应条目中后续指令的PO。出于示出的目的，图4的各框示出单个指令的过程。然而，应理解，在一些实现中，可以为SSF2中的每一已分派指令并行执行框410-430中的动作。

图5是示出根据本发明的一种实施例用于在多串乱序处理器中重构程序顺序的硬件配置500的框图。配置500可以被实现为指令调度单元(ISU)的一部分，例如在诸如处理器100之类的多串乱序处理器内的ISU 120。备选地，配置500可以是与多串乱序处理器中的ISU通信以执行程序顺序的重构的独立电路。

配置500可以包括等待缓冲器510和用于程序顺序重构的逻辑(例如程序顺序重构单元530、532和写入多路分离器540)。等待缓冲器510可以存储多个条目，每一条目保存在先前周期中通过已分派指令计算的、考虑用于执行的该串的程序顺序(PO)，以及各指令的相应IPO。在等待缓冲器510分配需要执行的每一指令这一方面，等待缓冲器510可以类似于超标量处理器中的保留站，且差别在于乱序分配。并且，在这一等待缓冲器中，一旦把各指令分派为执行，就释放这些指令。在一种实施例中，等待缓冲器被拆分成两个级别，且等待缓冲器510的第二级仅保存就绪指令。对于PO指令，等待缓冲器510的每一条目可以包括与串中的首指令相关联的PO-IPO对。例如，如果多串乱序处理器支持n个串的并行执行，则等待缓冲器510可以存储多达n个PO-IPO对。等待缓冲器510可以把PO-IPO输出到读多路复用器520。等待缓冲器510中的条目也可以对应于非PO指令，如先前所解释的，非PO指令可以不包括IPO编码。在这样的实例中，等待缓冲器510条目可以仅包括非PO指令的PO值，以及IPO字段中的0或空值。由于已经由先前的PO指令计算了该串中的下一PO指令的PO值(即，通过把所分派的先前PO指令的IPO与串PO值相加)，在分派时，该串中的下一PO指令PO值可以被设置为等于非PO指令的PO值。另外，对于串，在等待缓冲器510中不存在指令(例如已经执行了先前的指令，且还没有取出下一指令，使得用于该串的缓冲器条目为空)的时钟周期中，PO字段继续包含先前的PO指令的PO，其继续用于计算RPO。

读多路复用器520是选择逻辑的一部分，且可以被实现为在等待缓冲器510中接收PO-IPO对的单个(n到x)多路复用器。在每一执行周期期间，基于由选择逻辑从将稍后描述的有序列表选择的指令，读多路复用器520可以把可能的n个条目中的多达x个条目转发给x个分派端口。调度向量522是进入到读多路复用器120的输入。调度向量522可以是来自选择逻辑的输出，且可以指示选择了等待缓冲器150中的可能的n个就绪指令中的x指令中哪一个以供在当前周期中分派。因此，调度向量522控制从读多路复用器520转发的x个条目。在任何给定时钟周期中被选择为被调度以供执行的条目的数量可以因周期而不同，但可以最多高达x。在另一实施例中，PO和IPO值可以被保存在分离的缓冲器中(即，等待缓冲器510被拆分成两个缓冲器)，因此可以使用两个缓冲器实现读多路复用器520，一个用于分派PO值且另一个用于分派IPO值，但这两种多路复用器将仍然受到调度向量522控制，如上所述。可以把所选择的PO-IPO对输出到PO重构单元530、532。

重构逻辑可以包括多个PO重构单元530、532，其中的每一个都被配置为通过使用从读多路复用器520输出的相应的PO-IPO对，重构进入到等待缓冲器510的指令的PO。可以为读多路复用器520的每一输出提供重构单元530(即，x个专用重构单元)。在一种实施例中，每一重构单元530可以包括把PO和IPO组合起来以便形成重构编程次序(RPO)的运算逻辑。在一种实施例中，可以使用二进制加法来组合PO和IPO。然而，备选地，可以使用其他运算操作，这取决于编译器如何针对各PO计算各IPO。

可以使用一个或多个多路复用器(例如，单个x到n多路复用器)实现写多路分离器540，一个或多个多路复用器一起从重构单元530、532接收RPO。如同读多路复用器520一样，写多路分离器540可以受到来自ISU的调度向量522的控制。因而，写多路分离器540可以选择RPO，对于该RPO，等待缓冲器510中需要更新总共n个串中的x串。以这种方式，形成了反馈循环，反馈循环中，等待缓冲器510中的先前指令的PO被用来计算(即，重构)等待缓冲器510中的相应条目中后续指令的PO，其中所重构的PO对应于已经被选择为被调度以供在给定周期中执行的PO指令的真实程序顺序。

在一种实施例中，可以最终把回写到等待缓冲器510的经更新的PO值(其等于基于先前分派的指令所计算的串的RPO值)提供给排序逻辑。下面参考图7讨论排序逻辑的一个示例。排序逻辑是选择逻辑的一部分，它可以比较RPO值且按升序RPO值重新排序指令，得到有序列表。在一种实施例中，通过使用在当前周期之前多个周期更新的RPO值，排序逻辑可以实现排序指令。例如，排序逻辑可以使用来自先前的2个周期的RPO值形成有序列表。然后，这种有序列表可以被用来确定用于分派给各执行端口的指令的优先级。等待缓冲器510或RPO缓冲器可以存储来自先前周期的RPO值，且可以把那些值直接提供给排序逻辑。

图6是示出根据一种实施例用于基于重构程序顺序排序指令的方法的流程图。方法600可以由处理逻辑执行，处理逻辑可以包括硬件(例如，电路、专用逻辑、可编程逻辑、微代码等等)、软件(例如，在处理设备上运行以执行硬件仿真的指令)或其组合。处理逻辑可以基于与各串相关联的延迟RPO值创建指令的有序列表。在一种实施例中，由如图1中所示出1的选择逻辑170使用下面参考图7描述的系统700来执行方法600。

参见图6，在框610，方法600把经更新的RPO值与所有其他经更新的串RPO值进行比较。在一种实施例中，选择逻辑并行地把一个RPO值与所有其他串的RPO值比较。选择逻辑可以实现基于矩阵的逻辑，以便产生存储并行比较的结果的比较矩阵。

在框620，方法600判断经更新的RPO值(RPOi)是否小于等待缓冲器510中当前与其比较的所有其他就绪指令的RPO值(RPOj)。如果RPOi小于(或等于)RPOj，在框630，方法600把相应的矩阵单元(单元_ij)设置为第一值(例如，1)。如果RPOi不小于或等于RPOj(即，RPOi大于RPOj)，则在框640，方法600把相应的矩阵单元(单元_ij)设置为第二值(例如，0)。在图6中，i是从0到n-1，且j是从0到n-1，这意味着把等待缓冲器中的每一条目的RPO值与等待缓冲器中的每一其他条目并行比较。

在框650，方法600把与经更新的RPO值(RPOi)相关联的所有矩阵单元转换成单个代表值。在一种实施例中，1计数逻辑计数每一行中的1的数量，且产生4比特代表值(即，从表示具有最小RPO的指令的1111到表示具有最高RPO的指令的0000)。在一种实施例中，1计数逻辑可以被实现为并行操作的加法器的树(对于每一行)。

在框660，方法600可以基于每一指令的代表值排序指令并设置指令优先级。在一种实施例中，排序逻辑取出4比特代表值中的每一个并基于它们的值在有序列表中排序它们(例如，1111可以占用有序列表的最高位置，而0000占用最低位置)。以此方式，基于增加RPO值创建有序列表(即，最老旧的就绪指令占用第一位置，而SSF2中的最年轻的就绪指令占用最后的位置)。在一种实施例中，有序列表将仅保存代表值(即，4比特值)。然后，可以基于有序列表分派各指令以供执行。

图7是示出根据一种实施例用于基于重构程序顺序排序指令的系统的框图。在一种实施例中，系统700包括比较矩阵710、1计数逻辑720和排序逻辑730。比较矩阵710可以接收作为输入的如上所述所计算的经更新的RPO值。在一种实施例中，使用延迟RPO值。例如，如果在周期T中为已分派指令更新了RPO值，则那些经更新的RPO值可以用于在比预期晚的Z周期中调度指令。通常，该系统将预期，如果RPO在周期T中被更新，则在周期T+l中选择逻辑将使用这一经更新RPO来创建有序列表。然而，在延迟RPO方法中，经更新的RPO将用于周期(T+l)+Z。这从关键路径移除了选择逻辑的一部分(即，基于RPO值创建有序列表)，而不会有显著的性能损失。系统700可以使用Z周期的延时来创建有序列表，如下面将描述的。

在一种实施例中，同时把每一RPO值与每一其他RPO值进行比较。这些比较的结果可以被存储在比较矩阵710中。在一种实施例中，可以存在n个串，其中n等于16(且因而，对于每一周期，等待缓冲器510中有16个就绪指令和16个串RPO值)。因而，比较矩阵710可以具有16行(i＝0到15)和16列(j＝0到15)。为了减少进行所有比较所需要的时间，可以并行执行所有比较，且可以基于矩阵的逻辑实现所有比较，其中，把每一串RPO与所有其他串RPO并行比较。

在比较矩阵710中，RPOi表示SSF2的条目i中所存储的指令的RPO。矩阵710的每一单元的表示两个RPO的比较结果。例如，行0具有串0的RPO(RPO0)与所有其他串的RPO(由RPO0到RPO15表示串0到15)进行比较的结果。根据已定义条件，每一比较的结果可以是单个比特。在一种实施例中，该条件可以被定义为如果RPOi(其中i＝0-15)≤RPOj(其中j＝0-15)，然后，则单元_ij＝1。否则，单元_ij＝0。在其他实施例中，可以以某种其他方式定义该条件。

因此，在使用第一串RPO0的示例中，如果RPO0是小于12个其他串的RPO，那么，矩阵的行0中将具有12个l(表示串0的指令比SSF2中的12个其他就绪串更加老旧)。这意味着，在该矩阵中，也将存在全部为1的行，表示该路径中的指令在SSF2的16个条目当中是最老旧的。另外，也将存在全部为0的行，表示它是在16个条目当中最年轻的指令。如果存在具有相等的RPO值的两个串，那么，选择逻辑可以基于该串的位置(例如按照降序路径号的优先级)选择。而且，由图中的X表示路径中与自身的RPO比较(由于不要求进行比较)。在一种实施例中，X可以被看作是1。可以把比较矩阵710中所得到的值提供给1计数逻辑720。

一旦完成了RPO比较并填充了比较矩阵710，该矩阵的每一行将具有特定数量的1，其表示SSF2中有多少就绪指令比对应于该行的指令更年轻。这种信息可以用来基于RPO值排序指令。在一种实施例中，1计数逻辑720并行统计每一行中的1的数量，且产生4比特代表值(即，从表示具有最小RPO的指令的1111到表示具有最高RPO的指令的0000)。在一种实施例中，1计数逻辑720可以被实现为并行操作的加法器的树(对于每一行)。然后，排序逻辑730取出这些16个4比特代表值中的每一个，且基于它们的值在有序列表735中排序它们(1111可以占用有序列表中的最高位置，而0000占用最低位置)。以此方式，基于递增的RPO值创建有序列表(即，最老旧的就绪指令占用第一位置，而SSF2中的最年轻的就绪指令占用最后的位置)。在一种实施例中，有序列表735将仅保存代表值(即，4比特值)。在一种实施例中，排序逻辑730可以被实现为1分16多路分离器(一路对应于要在有序列表中排序的每一路径)。在一种实施例中，基于有序列表735，可以分派指令以供执行。例如，如果存在五个执行端口，那么，可以分派来自有序列表735的前五个指令。

图8示出计算机系统800的示例性形式的机器的略图，其中，可以执行用于引起该机器执行在此讨论的方法中的任何一种或多种的一组指令。在备选实施例中，机器可以连接(例如，联网)到局域网(LAN)、内联网、外联网或因特网中的其他机器。该机器可以在客户机-服务器网络环境中作为服务器或客户机机器操作，或在对等(或分布式)网络环境中作为对等机器操作。该机器可以是个人计算机(PC)、平板PC、机顶盒(STB)、个人数字助理(PDA)、蜂窝式电话、网络设备、服务器、网络路由器、交换机或桥、或能够执行指定由该机器采取的动作的一组指令(连续或不连续)的任何机器。进一步，尽管仅示出了单台机器，但将也采用术语“机器”来包括单独地或共同地执行一组(或多组)指令以便执行在此讨论的方法中的任何一种或多种的机器的任何集合。在一种实施例中，计算机系统800可以表示计算设备，例如包括处理器100的计算设备。

示例性计算机系统800包括处理设备802、主存储器804(例如只读存储器(ROM)、闪速存储器、动态随机存取存储器(DRAM)(例如同步DRAM(SDRAM)或Rambus DRAM(RDRAM)等等)、静态存储器806(例如闪速存储器、静态随机存取存储器(SRAM)等等)和数据存储设备818，它们经由总线830相互通信。在此描述的各种总线上提供的任何信号可以与其他信号时分复用，且在一个或多个公共总线上提供它们。另外，在电路组件或模块之间的互连可以被示出为总线或单信号线。备选地，每一总线可以是一个或多个单信号线，且备选地单信号线中的每一个可以是总线。

处理设备802表示一个或多个通用处理设备，例如微处理器、中央处理单元等等。处理设备实现多串架构，其允许对由编译器安排成多个串的指令进行乱序提取和执行。通过由编译器把复杂指令集计算(CISC)架构、精简指令集计算机(RISC)架构、超长指令字(VLIW)架构或其他指令集、或各指令集的组合的二进制码翻译成多串架构，处理设备可以实现上述指令集。处理设备802也可以是一个或多个专用处理设备，例如专用集成电路(ASIC)、现场可编程门阵列(FPGA)、数字信号处理器(DSP)、网络处理器等等。处理设备802被配置为执行处理逻辑826，处理逻辑826用于执行在此讨论的操作和步骤。

计算机系统800还可以包括网络接口设备808。计算机系统800也可以包括视频显示单元810(例如，液晶显示器(LCD)或阴极射线管(CRT))、字母数字输入设备812(例如，键盘)、光标控制设备814(例如，鼠标)和信号产生设备816(例如，扬声器)。

数据存储设备818可以包括机器可访问存储介质828，其上存储有一组或多组指令822(例如，软件)，一组或多组指令822实现在此描述的功能的方法中的任何一种或多种。在计算机系统800执行指令822期间，指令822也可以完全地或至少部分地驻留在主存储器804和/或处理设备802内；主存储器804和处理设备802也构成机器可访问存储介质。还可以经由网络接口设备808在网络820上发送或接收指令822。在一种实施例中，可以在处理设备802的硬件中执行指令。然而，在其他实施例中，指令可以被存储在存储器804或存储设备818中且由软件执行。

机器可读存储介质828也可以用来存储用于基于在此描述的延迟重构处理次序调度处理器中的指令的指令。尽管在示例性实施例中机器可读存储介质828被示出为单个介质，但应理解，术语“机器可读存储介质”包括存储一组或多组指令的单个介质或多个介质(例如，集中式或分布式数据库和/或关联的缓存和服务器)。机器可读介质包括用于以机器(例如，计算机)可读的形式(例如，软件、处理应用)存储信息的任何机制。机器可读介质可以包括但不限于磁存储介质(例如，软盘)；光存储介质(例如，CD-ROM)；磁-光存储介质；只读存储器(ROM)；随机存取存储器(RAM)；可擦除可编程存储器(例如，EPROM和EEPROM)；闪速存储器；或适用于存储电子指令的另一类型的介质。

尽管在此以具体次序示出和描述了各方法的操作，但可以改变每一方法的操作次序，以使得可以以相反次序执行某些操作，或者以使得可以至少部分地与其他操作同时地执行某些操作。在另一实施例中，不同的操作的指令或子操作可以采用间歇和/或交替方式。