CN1841313A - 用于处理多周期非流水线指令时序的处理器和方法 - Google Patents

Abstract

一种用于处理多周期非流水线指令时序的系统和方法。利用该系统和方法，当在发布点检测到一个非流水线指令时，发布逻辑就发起一个搁置，该搁置是完成最快的非流水线指令所需的最小数目的周期。然后执行单元接管搁置，直到实际完成该非流水线指令。这使得执行单元有更多的时间来正确判定该非流水线指令将何时完成。就在执行单元刚刚完成该指令前，它向发布逻辑释放该搁置。设置执行单元释放搁置信号的定时，使得相关指令可以尽可能地旁路该结果。换言之，相关指令不必为了获得对该结果的访问，而等待该结果被写入处理器寄存器文件。

Description

用于处理多周期非流水线指令时序的处理器和方法

技术领域

本发明主要涉及一种改进的数据处理系统。更具体地，本发明提供一种用于处理多周期非流水线指令时序的系统和方法。

背景技术

典型地，由硬件执行的指令，例如乘法、除法、平方根和/或其他复杂的数学程序，采用流水线很困难而且代价高。用来计算这样复杂指令的算法本身是复杂的并且典型地必须分解为迭代解法。由于包含一个循环(loop)，这种复杂指令的处理不能是流水线的，否则当尝试循环时会出现冲突。在设计该处理器时，从功率和面积的观点看，直接执行该算法的成本太高。

与流水线处理这些运算相比，许多处理器通过一组简短的数学运算运行一种递归循环，最终得到该运算的正确结果。虽然这样得到了正确结果，但是需要额外的处理器周期来完成递归循环，因此增加了处理器中的时延。而且，从属指令--即在其可以执行之前需要非流水线指令的结果的一种指令，在该结果可以用于处理该从属指令之前，必须等待该递归循环完成，因此更进一步增加了时延。

通常处理非流水线指令很困难并且很冗长，例如以上所讨论的利用递归循环进行处理的非流水线指令。通过先假设将需要多久完成一个非流水线指令的执行，一般会损失性能。后续指令将被延迟，直至完成该非流水线指令。对该延迟的计算时间通常是不正确的并且过于悲观。结果，在执行时间纠正初始的错误假设造成了额外开销。

为了说明该时延，将美国专利No.5,948,098中描述的一种方法，在此通过参考引入，增加一个长时延执行单元以避免由于长时延指令造成的搁置(stall)。虽然该方法提供良好的性能，但是与传统处理器相比，这种额外的长时延执行单元需要额外的片上(on-chip)面积和功率。

因而，用于以一种非流水线方式处理复杂指令的系统和方法将是有益的，其不受与执行完成时间的错误假设相关联的额外开销的影响。此外，对于深流水线处理器，其需要多个周期来读取寄存器文件并从该寄存器文件旁路(bypass)，利用现有的旁路硬件和旁路检测而不增加新的旁路和检测硬件来处理这些非流水线复杂指令将是有益的。

发明内容

本发明提供一种用于处理多周期非流水线指令时序的系统和方法。利用本发明的系统和方法，当在发布点检测到一种非流水线指令时，发布逻辑初始化一个搁置，该搁置是完成最快的非流水线指令所需的最小数目的周期。然后执行单元接管搁置，直至该非流水线指令基本完成。这使执行单元有更多的时间来准确地判定该非流水线指令将何时完成。

在该执行单元刚完成该指令之前，它向发布逻辑释放该搁置。发布单元第二次发布该指令。执行单元然后把非流水线操作的结果插入到在流水线结果的第一旁路阶段之前的阶段中。尽管在第二次发布时发布的是一个流水线指令，但搁置释放的定时和把非流水线结果插入到流水线指令旁路网络，与具有相同定时和旁路特性的非流水线指令的第二次发布相对应。尽管在“第二次”发布该非流水线操作时发布的是一个流水线指令，但可以计算用于随后指令的指令结果搁置以及旁路。

以这种方式，对执行单元释放搁置信号的定时进行设置，使得从属指令可以尽可能快地旁路该结果。换言之，从属指令不必为了获得对该结果的访问，而等待该结果被写入处理器寄存器文件。相反，一旦该结果可用，该相关指令就可以“旁路”该结果，以有助于减小搁置时延。本发明的这些以及其他特征和优点将会在下面优选实施方式的详细描述中进行描述，或者对于本领域普通技术人员而言会变得显而易见。

附图说明

在所附的权利要求中阐述本发明令人信服的新颖特征。但是，通过参考下面结合附图对说明性实施方式进行的详细描述，可以更好地理解本发明本身以及其使用的优选方式、更多的目的和优点，其中：

图1A是计算设备的中央处理单元的传统执行单元的示例性图示；

图1B是图1A的执行单元的操作数旁路怎样与架构寄存器文件一起使用的示例性图示；

图2是根据本发明的计算机的示例性框图；

图3是示出根据本发明在发布单元和执行单元之间交互的示例性框图；

图4是根据本发明的示例性实施方式的流水线的示例性图示；

图5A和5B是示出根据本发明的一个示例性实施方式的示例指令时序的示例性图示；

图6是根据本发明的一个示例性实施方式的用于控制指令搁置的发布单元中的逻辑的示例性图示；

图7是根据本发明的一个示例性实施方式的状态机的示例性图示；

图8是用于概括根据本发明一种示例性实施方式的发布单元的示例性操作的流程图；

图9是用于概括根据本发明一种示例性实施方式的执行单元的示例性操作的流程图。

具体实施方式

如上所述，本发明提供一种用于处理多周期非流水线指令时序的系统和方法。运行本发明的机制以便于以非流水线方式处理复杂指令，即多周期指令，同时向指令流水线的一个合适阶段提供该非流水线多周期指令的结果，以便于允许对相关指令的流水线执行。在提供对本发明的机制和操作的详细解释之前，首先描述一种传统流水线执行单元的操作是有帮助的。

图1A是通用计算机的CPU(中央处理单元)(未示出)的一种传统执行单元100的示例性说明。执行单元100包括流水线102，用于执行计算机程序的某些指令。流水线102具有连续的流水线阶段S1至S9，用于执行流水线102中的每个指令。流水线阶段S1至S9包括操作数选择阶段S1，操作数处理(即，执行)阶段S2，其他流水线阶段S3至S6，有效性判定阶段S7，另一个流水线阶段S8，以及操作数写入阶段S9。流水线阶段S1和S3至S9的每一个发生在一个机器周期中，并且操作数处理阶段S2可发生在可变数目的机器周期中，这将在后面描述。

首先由CPU将流水线102中的每个指令151发布给执行单元100的分发控制器104。接着，在操作数选择阶段S1期间，分发控制器104在控制逻辑111向流水线102分发所发布的指令。分发控制器104还对该指令进行预解码，并且作为响应，在流水线阶段S1至S9期间，产生用于该指令的控制信号，用于以下述方式控制流水线102和架构寄存器文件(ARF)106的操作。

流水线102的操作数选择阶段S1包括复用器(MUX)128。在操作数选择阶段S1期间，对于流水线102中的每个指令，MUX128选择一个或多个源操作数S1SSOP1和/或S1SSOP2，用于流水线102的操作数处理阶段S2处理。如下所述，从以下之中作出该选择，即接收自ARF106的源操作数S1SOP1和S1SOP2，分别接收自操作数旁路114至120的本地目的地操作数S2LDOP至S8LDOP，分别接收自另一个流水线(未示出)的操作数旁路121至127的外部目的地操作数S2XDOP至S8XDOP，以及接收自流水线102的控制逻辑110的立即源操作数IMMDSOP。

ARF106包括计算机的架构寄存器。在操作数选择阶段S1期间，对于流水线102中的每个指令，ARF106从所选择的ARF106的架构寄存器中选择性地将源操作数S1SOP1和S1SOP2提供给流水线102的操作数选择阶段S1。如果分发控制器104判定源操作数S1SOP1或者S1SOP2目前在ARF106的架构寄存器之一中可用，则将由MUX128之一选择ARF106所提供的源操作数S1SOP1或S1SOP2。由该指令指定这个架构寄存器作为一个源。

然而，对于流水线102中的每个指令，分发控制器104可以判定该指令需要的是一个来自控制逻辑110的立即源操作数IMMD SOP而不是源操作数S1SOP1或S1SOP2。在这种情况中，MAX128之一选择该立即源操作数IMMD SOP。

在操作数选择阶段S1期间，对于流水线102中的每个指令，分发控制器还可以判定源操作数S1SOP1或S1SOP2在ARF106的架构寄存器中仍不可用，但是在其他地方闲置(in flight)且可用。在这种情况中，它可以用作本地目的地(或结果)操作数S2LDOP至S8LDOP之一或外部目的地操作数S2XDOP至S8XDOP之一，并且然后由MUX128之一进行选择。在流水线阶段S2至S8期间，对于流水线102中的其他指令，由流水线102分别产生本地目的地操作数S2LDOP至S8LDOP。在流水线阶段S2至S8期间，对于另一个流水线(由X表示，但未示出)中的指令，分别产生外部目的地操作数S2XDOP至S8XDOP。这是通过这个流水线的各自外部操作数旁路源来完成的。

在操作数处理阶段S2中，对于流水线的102中的每个指令，由操作数处理阶段S2的寄存器134首先锁存一个或多个所选的源操作数S1SSOP1和/或S1SSOP2，作为一个或多个所选的源操作数S2SSOP1和/或S2SSOP2。而且，在操作数处理阶段S2中，对于该指令，流水线102的控制逻辑110产生控制信号，该控制信号使操作数处理阶段S2的算术逻辑132处理该一个或多个所选的源操作数S2SSOP1和/或S2SSOP2，并且作为响应而产生用于该指令目的地操作数S2LDOP。这些控制信号是响应于解码该指令而产生的。

流水线阶段S3至S8分别包括寄存器138至143。这样，在流水线阶段S3中，对于流水线102中的每个指令，寄存器138锁存在操作数处理阶段S2中对于该指令所产生的本地目的地操作数S2LDOP，作为本地目的地操作数S3LDOP。同样地，在流水线阶段S4至S8，对于流水线中的每个指令，寄存器139至143把在以前的流水线阶段S3至S7中分别锁存的本地目的地操作数S3LDOP至S7LDOP分别锁存，分别作为目的地操作数S4DOP至S8LDOP。因而，目的地操作数S3LDOP至S8LDOP都是目的地操作数S2LDOP的延时版本。

由于在执行单元100中发生其他处理，因此需要流水线阶段S3至S6和S8。而且，在有效性判定阶段107中，分发控制器104判定该指令是有效还是无效。

对于在流水线102中每个被分发控制器104判定为有效的指令，在操作数写入阶段S9期间，被该指令指定为目的地的ARF106中的架构寄存器存储用于该指令的目的地操作数S8LDOP。因而，对于执行单元100的流水线102中或者另一个流水线中的后来的指令，用于上述特殊指令的目的地操作数S8LDOP现在在ARF106中将是可用的，并作为在操作数选择阶段S1中的源操作数S1SOP1或S1SOP2。

然而，由于分支错误预测、陷阱或者指令再循环，流水线102中的指令可能是无效的。用BMP(分支错误预测)信号152指示一个分支错误预测，该BMP信号152由分发控制器104从执行单元100的另一个流水线接收。陷阱可以由分发控制器104在本地检测，或者从TRP(陷阱)信号152检测，该TRP信号152由分发控制器104从执行单元的其他流水线接收。而且，指令再循环将由RCL(指令再循环)信号152指示，当发生了数据缓存错误时由分发控制器104从CPU的数据缓存(未示出)接收该RCL信号152。

如果分发控制器104判定流水线102中的一个指令是无效的，则ARF106不为该指令存储目的地操作数S8LDOP。以这种方式，由于在分发控制器104判定该指令为有效之前不会为该指令在ARF106中存储目的地操作数S8LDOP，因此ARF106不会被破坏。

然而，流水线102中的后续指令取决于流水线102中早先指令的本地目的地操作数S2LDOP至S8LDOP，和/或其他流水线中早先指令的外部目的地操作数S2XDOP至S8XDOP，它们闲置并且还没有被存储在ARF106中。同样地，其他流水线中的后续指令可以取决于流水线102中早先指令的本地目的地操作数S2LDOP至S8LDOP，它们处于队列中并且还没有被存储在ARF106中。因此，必须在最小时延内使这些本地目的地操作数S2LDOP至S8LDOP和外部目的地操作数S2XDOP至S8XDOP可用，以保存CPU的性能。为达到这点，执行单元100包括来自流水线102的操作数旁路114至120和来自另一个流水线的操作数旁路121至127。

更特别地，对于操作数处理阶段S2，由操作数旁路114把算术逻辑132耦合到MUX128。同样地，对于中间阶段S3至S8，分别由操作数旁路115至120把寄存器138至143耦合到MUX128。以这种方式，算术逻辑132和寄存器138至143分别是本地目的地操作数S2LDOP至S8LDOP的本地操作数旁路源。并且，如前所述，对于流水线阶段S2至S8，由操作数旁路121至127把另一个流水线中的外部操作数旁路源耦合到MUX128，以提供外部目的地操作数S2XDOP至S8XDOP。

因此，在操作数选择阶段S1中，对于流水线102中的每个指令，这种特殊指令可以把在ARF106中同样选择的寄存器规定为源，在执行单元100的流水线102中或另一个流水线中的早先指令将所述源规定为目的地。这个早先指令可以在流水线102或其他流水线的流水线阶段S2，……，S7或S8中。在这种情况下，对于早先指令产生的本地或外部目的地操作数S8LDOP或S8XDOP从所选寄存器还不可用，但是作为对应操作数旁路114，……，126或127上的本地或外部目的地操作数S2LDOP，……，S6XDOP或S7XDOP将是可用的。结果，MUX128会选择这个本地或外部目的地操作数S2LDOP，……，S6XDOP或S7XDOP，用于算术逻辑132的处理。

图1B对流水线102作出更明确的说明。如图所示，流水线102中的初始指令ADD，从ARF106的寄存器r0和r1获得它的源操作数S1SOP1和S1SOP2，ARF106的寄存器r0和r1在用于ADD指令的操作数选择阶段S1期间被指定为源。在用于指令ADD的操作数处理阶段S2期间，产生目的地操作数S2LDOP。然而，只是在用于指令ADD的操作数写入阶段S9期间，把目的地操作数S8LDOP写入被指定为目的地的ARF106的寄存器r2中。因此，通过指定寄存器r2作为源，在指令ADD的流水线阶段S2，…，S7或S8期间具有自身操作数选择阶段S1并且依赖于指令ADD的任何指令SUB，…，或AND，必须使用相应的操作数旁路114，…，119或120来获得目的地操作数S2LDOP，…，S7LDOP或S8LDOP，作为所选的源操作数S1SOP1或S1SOP2。并且，只是对于指令XNOR等，其在指令ADD的流水线阶段S2至S8之后具有它们的操作数选择阶段S1，所选的源操作数S1SOP1或S1SOP2才会从寄存器r2中直接可用。因此，由于对于每个指令，仅在操作数写入阶段S9中写入ARF106，所以流水线102必须具有用于流水线102中的流水线阶段S2至S8的操作数旁路114至120，并且流水线102还必须耦合到来自其他流水线的操作数旁路121至127。

在许多CPU中，算术逻辑132配置用于对于预定义算术指令类型的所有指令，处理(即，对其执行算术运算)一个或多个所选的源操作数S1SSOP1和/或S1SSOP2。这可以包括性能关键的算术指令，由于经常用到它们，因此对于CPU的性能至关重要。对于每个性能关键的算术指令，操作数处理阶段S2发生在一个机器周期中。预定义算术指令类型的指令还可以包括非性能关键的算术指令，它们不会经常被使用，因此对于CPU的性能并非至关重要。对于这种非性能关键的算术指令的每一个，操作数处理阶段S2具有子阶段并且发生在多个机器周期中，其机器周期数随指令而改变。

当一个需要多个周期进行处理的复杂指令被发布到执行单元时，使用算术逻辑132和操作数处理阶段S2的这些子阶段，由执行单元处理该指令。这种复杂指令的例子包括乘法、除法、点乘积(dot-product)、平方根以及其他复杂的数学例程。当在处理这种指令的同时，将要发布到流水线102的所有其他指令在发布单元中搁置一段时间，这段时间取决于对完成该复杂指令的时间的初始估计。

正如上面提到的，完成时间的初始估计通常是不正确的，并且实际上需要或多或少的处理器周期来处理这些指令。如果需要较少的处理器周期来处理该指令，那么在发布单元根据处理该指令所需时间的初始预测而继续搁置时，就会浪费处理器周期。

如果需要较多的处理器周期，在复杂多周期非流水线指令的处理时间中的这种错误计算，会导致发布单元必需重新计算该指令在执行单元中的处理时间。而且，发布单元还必须搁置用于额外的处理器周期的指令发布。这种重新计算增加了处理器中的额外开销，并且典型地通常导致发布单元搁置比用于完成指令处理所需要的更多的处理器周期。结果，由于发布单元搁置了对流水线的额外指令的发布，直到经过处理器周期的预计量，所以浪费了处理器周期。

本发明通过在发布单元和执行单元中提供逻辑以允许处理多周期非流水线指令时序，从而避免了这样的开销。利用本发明的机制，当在发布点检测到非流水线指令时，发布逻辑初始化一个搁置，该搁置是最快的非流水线指令能够完成的最小数目的周期。然后执行单元继续搁置，直到实际完成该非流水线指令。这使得执行单元有更多的时间来准确判定何时将完成该非流水线指令。在执行单元刚完成该指令之前或者基本上在同时，执行单元向发布逻辑释放该搁置，该发布逻辑然后可以继续发布指令。

图2是一种计算设备的示例性框图，在该设备中可以实施本发明的示例性方面。如图2所示，计算机200包括CPU202、外部缓存204、主存储器206、辅助存储器208、图形设备210以及网络连接212。

CPU202包括指令缓存214、数据缓存216、外部存储器控制器218和系统接口220。外部存储控制器218连接到指令缓存214、数据缓存216、外部缓存204和主存储器206。系统接口220连接到数据缓存216、辅助存储器208、图形设备210和网络连接212。

CPU202还包括发布单元224，其从指令缓存214中获取计算机程序的指令。发布单元224然后发布所获取的指令，用于在执行单元226的不同流水线中执行。CPU202还包括执行单元226，其包括执行单元内核228、算术逻辑230和控制逻辑294。

执行单元内核228包括一个执行流水线，例如图1A中的流水线102。算术逻辑230包括用于执行流水线指令和非流水线指令的逻辑。本发明在发布单元224和控制逻辑294中提供逻辑，使得当由算术逻辑230处理多周期非流水线指令时，发布单元224初始处理指令的搁置。在指令初始搁置之后，发布单元224然后把处理指令搁置交给执行单元226的控制逻辑294。

图3是示出根据本发明在发布单元和执行单元之间交互的示例性框图。如图3所示，当发布单元310从指令缓存320获取一个用于发布给执行单元330的指令时，发布单元的发布逻辑312判定该指令是流水线指令还是非流水线指令。例如可以通过处理与该指令相关联的操作代码(未示出)，并且将该操作代码和驻留在发布单元310中的流水线指令操作代码表(未示出)相比较，作出该判定。如果该操作代码在这个表中，则该相关指令是一个流水线指令。如果该操作代码不在这个表中，则该相关指令是一个非流水线指令。

对于流水线指令，发布单元310以正常形式向执行单元330的流水线334发布指令。如果该指令是非流水线指令，则发布单元310的发布逻辑312向指令单元330的非流水线算术逻辑336发布非流水线指令。

该发布逻辑312判定在执行单元330中完成最快的非流水线指令所需最小数目的周期，并且针对该数目的处理器周期，在发布单元310中初始化一个搁置。在本发明的优选实施方式中，周期的这个最小数目是一个固定的数目，其存储在发布单元310中。对于不同的处理器结构和执行单元，周期的最小数目可以是不同的。在一种示例性的处理器结构中，执行单元能够完成的最快非流水线指令的最小数目的周期是5个处理器周期。

然后对于最小数目的周期，例如5个处理器周期，发布单元310搁置对执行单元330的更多指令发布。该搁置的初始化可以包含，例如，计数器初始化为零，该计数器随着每一个处理器周期而递增。在其他实施方式中，由在状态机中从一个状态到另一个状态的转换来控制管理搁置的初始化和搁置本身，如以下更加详细的描述。因而，在该示例性实施方式中，发布单元310将不会向执行单元330发布任何更多的指令，直到初始搁置时段已经过去，这通过与发布单元310相关联或者可由发布单元310访问的计数器/状态机等来判定。

在发布单元310中初始化搁置并且初始搁置时段终止之后，把要发布给执行单元330的指令的搁置控制移交给执行单元330中的控制逻辑332。在初始搁置时段终止之后，执行单元的控制逻辑332判定该指令的处理是否已完成。在初始搁置时段内，即在其中可以完成最快的非流水线指令的最小数目的周期内，如果算术逻辑336没有完成指令的处理，那么执行单元330的控制逻辑332发送一个信号给发布单元310，该信号指示发布单元310应该继续搁置另一个处理器周期。在初始搁置时段之后，在每一个随后的处理周期中执行该判定和来自执行单元330的搁置信号的发布，直到在算术逻辑336中已完成该指令处理。

如果根据执行单元330向发布单元310发送的搁置信号，在初始搁置时段内或者在延长的搁置时段内完成了该指令，则控制逻辑332将向发布单元310回送一个信号指示该指令的完成，或者简单地对搁置信号去声明(de-assert)，以此指示指令处理的完成。结果，发布单元310释放发布单元310的搁置状态并且将该指令作为一个流水线指令重新发布给执行单元330的流水线334。执行单元330把这个重新发布的指令看作一个流水线指令，例如，ADD指令等，并且使用流水线334执行该指令。

此外，使用流水线334的旁路控制，把如上所述在算术逻辑336中的非流水线指令的执行结果加入到流水线334中的一个合适的阶段中。以这种方式，在一个如果重新发布的流水线指令在流水线334中实际执行则将会出现实际结果的阶段中，把重新发布的流水线指令的结果插入到流水线334。以这种方式，在流水线334中给出多周期非流水线指令的结果，使得其他相关指令可以不用访问寄存器文件，例如ARF106，而使用该流水线现有的旁路控制来获得多周期非流水线指令的结果。然后可以将重新发布的流水线指令的结果以本领域通常熟知的方式写入寄存器文件。

图4是根据本发明的示例性实施方式的一种流水线的示例性图示。除了提供有一个额外的非流水线算术逻辑单元410以用于处理非流水线指令的执行之外，图4所示的流水线与图1A中的类似。这个非流水线算术逻辑单元410可以包括算术逻辑132的子阶段，例如，其用于执行非流水线指令。加法器420可以组成用于流水线指令的主算术逻辑132。提供复用器430，用于使非流水线算术逻辑单元410的结果和加法器420的结果(即，流水线指令)复用。由控制逻辑，例如图1中的控制逻辑110，提供控制信号给复用器430，用于选择两个输入中的一个。

如图4所示，在发布阶段(IS)，在执行单元中接收所发布的指令，既有流水线指令也有非流水线指令。然后将所发布指令的读取地址用于在第一寄存器文件阶段(RF1)期间读取来自寄存器文件440的操作数数据。在第二寄存器文件阶段(RF2)期间，把从寄存器文件440读取的操作数数据提供给复用器450和460。在第一执行阶段(EX1)期间，将一个例如来自控制逻辑110的控制信号输入到复用器450和460，以将进入复用器450和460的所选输入输出给加法器420和非流水线算术逻辑单元410。

将加法器420和非流水线算术逻辑单元410的输出提供给复用器430。将一个例如来自控制逻辑410的控制信号提供给复用器430，用于在来自加法器420的流水线输出和来自非流水线算术逻辑单元410的非流水线输出之间进行选择。把来自复用器430的输出输入到用于每一个随后的执行阶段EX2至EX5的锁存器中。把每一个执行阶段EX2至EX5中的每个锁存器的输出输入到复用器450和460。执行阶段5(EX5)的输出还被发送到写回锁存器(WB)并且被写回到寄存器文件440。

图4所示的流水线400在控制逻辑的控制下工作，该控制逻辑用于判定哪些操作数是完成指令所必需的。该控制逻辑包括从属性判定逻辑、从属性搁置逻辑等，用于判定从属指令需要的操作数在哪些阶段(IS-EX5)，并判定为获得从属指令需要的操作数，搁置是否是必要的。来自每个执行阶段(EX2-EX5)的循环反馈提供一个旁路，其允许从属指令在写回至寄存器文件440之前获得操作数。

因而，如图4所示，在第一执行阶段(EX1)期间，非流水线指令的操作数被发送至非流水线算术逻辑单元410，而且还提供给加法器420。非流水线算术逻辑单元410对这些操作数进行操作以产生一个输出，作为一个输入提供给复用器430。在该处理期间，对于完成一个最快的非流水线算术操作所必需的最小数目的周期，即初始搁置时段，发布单元(例如可参考图3中的发布单元310)不再发布指令给执行单元以及流水线400。结果，当该非流水线算术逻辑单元410对该非流水线指令的操作数执行操作时，没有相关指令经过该流水线。

在每一个处理器周期，将操作数输入到该非流水线算术逻辑单元410，会发起一个执行单元搁置信号(XU_STALL)的声明(assert)，该信号输入到发布单元的搁置控制逻辑，例如发布逻辑312。在这个XU_STALL信号被声明的同时，在初始搁置时段之后，发布单元以一个周期接一个周期地继续搁置。

当该非流水线算术逻辑单元410产生一个输出时，它就对XU_STALL信号去声明，并且解除对要发布给执行单元的指令的搁置。发布单元把该非流水线指令作为一个流水线指令重新发布给流水线400。在阶段EX1，经由复用器430，把该非流水线算术逻辑单元410的输出插入流水线400。

图5A和5B是说明根据本发明的一种示例性实施方式的示例指令时序的示例性图示。在所描述的指令时序中，指令结果被旁路给RF2阶段，如图4所示，并且可以从执行阶段EX2、EX3、EX4、EX5、EX6(写回(WB))以及EX7(写回+1(WB+1))旁路。

在图5A中所示的指令时序中，第一流水线加法指令的操作数r2和r1，r10＝r2+r1，被输入到流水线400。此后，第二流水线加法指令r11＝r3+r4，被发布至流水线400。第二加法指令不依赖于第一加法指令。

第三流水线加法指令r12＝r11+r2，被输入到流水线400，其取决于第二流水线指令的结果。如图5A所示，当第三流水线加法指令处于旁路阶段(RF2)时，第二流水线加法指令的结果处于执行阶段EX2，并且控制信号被发送至复用器450和460，以旁路(在图中用从EX2至RF2的曲线箭头标示)用于执行第三流水线加法指令的第二流水线加法指令的结果。

然后一个非流水线乘法指令r13＝r12*r3被发布给执行单元。该非流水线乘法指令依赖于第三加法指令的结果。当非流水线乘法指令被发布给执行单元时，发起一个初始搁置时段，使得不发布从属指令，直至得到该乘法结果。当非流水线乘法指令处于第二寄存器文件(RF2)阶段时，该非流水线乘法指令接收来自执行阶段EX2的第三加法指令的结果。

如图5A所示，在非流水线算术单元中需要5个处理器周期来完成该非流水线乘法指令(参见在发布阶段(IS)乘法指令第二次发布的搁置)。然后第二次把该非流水线乘法指令重新发布给执行单元作为流水线指令。由于该乘法指令的结果可从第一次指令的发布得到，所以第二次指令的发布可以经过流水线。通过旁路输入使得乘法指令的结果可用于复用器450和460。任何随后的相关指令，例如第四流水线加法指令r13＝r10+r12，从对执行单元的第二次乘法指令的发布，接收所需要的乘法指令的结果(如从EX2至RF2的曲线箭头所示)。

图5B示出指令时序的另一个例子，其中第二流水线加法指令r13＝r11+r4取决于第一流水线加法指令r11＝r10+r2，但是不取决于非流水线乘法指令r12＝r10*r3。图5B示出尽管流水线指令不依赖于非流水线乘法指令，由于需要处理该非流水线乘法指令，所以要搁置第二流水线加法指令。如以上所提到的，在执行单元中，这种时序由控制逻辑单元的相关性判定逻辑和从属性搁置逻辑，例如控制逻辑110来控制。

图6是根据本发明的一种示例性实施方式用于控制指令搁置的发布单元中的逻辑的示意图。这个逻辑例如可以是图3中发布单元310的发布逻辑312的一部分。

如图6所示，提供从属性搁置产生逻辑610，用于判定在流水线指令之间是否搁置对执行单元的指令发布。从属性搁置产生逻辑610计算并跟踪所发布指令之间的相关性，并控制对执行单元的指令发布的搁置。

把相关性搁置产生逻辑610的输出提供给OR门620和AND门630。当对执行单元的指令发布被搁置时，由相关性搁置产生逻辑610声明一个输出信号。

如图6所示，至AND门630的输入是来自相关性搁置产生逻辑610的相关性搁置信号、来自解码器(未示出)的解码成对发布(decode double issue)信号、以及来自成对发布状态机640的“第一半已发布”  (“first half issued”)的输出信号。解码成对发布信号是这样的信号，即，如果指令的操作代码指示该指令是一种非流水线指令，则由CPU的传统指令解码器(未示出)声明该信号。第一半已发布的信号是这样的信号，即，当成对发布状态机640从流水线指令状态转变为非流水线指令的“已发布第一半”(“issued firsthalf”)状态时，由成对发布状态机640声明该信号，这将在之后参照图7进行更详细的讨论。当声明了解码成对发布信号、未发布第一半非流水线指令、并且相关性搁置产生逻辑610没有指示需要搁置时，AND门630将“发布第一半”(“issue first half”)信号输出给成对发布状态机640。

OR门620接收执行单元搁置信号XU_STALL、来自相关性搁置产生逻辑610的相关性搁置信号、以及来自成对发布状态机640的成对搁置信号(db_STALL)，作为输入。如果声明这些信号的任何一个，OR门620就将发布单元搁置信号(IU_STALL)输出给相关性搁置产生逻辑610。

在一个初始搁置时段期间，由成对发布状态机640声明成对搁置信号，以向执行单元实施指令发布的最小数目周期的搁置，该最小数目的周期为在非流水线算术单元中由执行单元执行最快的非流水线指令所需的周期。成对发布状态机640可以是一个单状态机或者是多个状态机，用于跟踪由执行单元执行的指令的状态，不管该指令是流水线指令还是非流水线指令。

图7是根据本发明的一个示例性实施方式的状态机的示例性图示。图7中的弧线由一组数值标记，该组数值表示引起状态转换的图6所示信号的状态。这组数值构成如下：dependency_STALL，issue-first-half/first-half-issued，dn_STALL。这些组中的“X”值代表一个“不关心”的值，意味着在进行状态转换时不考虑该信号的实际状态。

如图7所示，使用一个简单的状态机700以跟踪处理成对发布指令。该状态机700可以是一个单状态机或者实际上可以实施为两个独立的状态机：一个两状态的状态机可以用来跟踪是否已经首次发布了一个成对发布指令，以及一个第二状态机可以使用计数器、一系列状态转换等来控制指令的搁置。这个第二状态机可以与其他需要搁置预定数量周期的搁置机制结合，即同步指令。

如所描述的状态机700中所示，如果一个成对发布指令不在发布阶段(IS)中，或者成对发布指令在发布阶段但是没有首次发布，则该状态机700保持在状态P710。当首次发布一个成对发布指令时，状态从状态P710转换至“已发布第一半指令”(“issued first halfinstruction”)状态720的状态S1。状态机700输出声明第一半已发布信号。通过状态S1，S2，S3，…S^*的转换，状态机700还对于预定的周期数目声明db_STALL信号。这将阻止非流水线指令的第二次发布以及任何其他随后指令，直到初始搁置时段过去。

当该状态机700到达状态S^*时，状态机700将对db_STALL信号去声明。至此，执行单元已确定它是否需要额外的搁置周期。如果需要，则该状态机700会停留在状态S^*，直到不再声明XU_STALL信号。当不再声明XU_STALL信号时，释放搁置条件，并且允许发布非流水线指令和随后指令。该执行单元忽略该第二次发布，但是要在相同的位置把该非流水线结果插回到流水线，此时就像是一个在该时间发布的流水线指令。控制逻辑将这个第二次发布看作是流水线指令的正常发布，并且设置复用器控制以正确地将数据转发到任何依赖于该数据的随后指令。

因此，使用上述机制，本发明提供一种系统和方法，用于以一种有效的方式处理多周期非流水线指令时序，其中使用于执行指令所需的处理器周期最小化，并且使由处理时间的错误计算造成的开销最小化。对于本发明，等待完成一个非流水线指令所使用的处理器周期数恰好是完成该非流水线指令所需的处理器周期数。即，由于初始搁置时段等于最快的非流水线指令执行所需的最小数目的周期，并且在一个处理器周期接一个处理器周期的基础上控制这个搁置时段的延长，因此在不必要地搁置指令时不会浪费处理器周期。

图8是根据本发明的一个示例性实施方式概括发布单元的示例性操作的流程图。图9是根据本发明的一个示例性实施方式概括执行单元的示例性操作的流程图。可以理解，流程图示意的每个方框以及流程图示意中方框的组合，都可以通过计算机程序指令来实施。可以把这些计算机程序指令提供给一个处理器或其他可编程数据处理装置以产生一种机器，使得在处理器或其他可编程数据处理装置上执行的指令，创建用于实现流程图的一个或多个方框中所指定的功能的装置。这些计算机程序指令也可以被存储在一个计算机可读存储器或存储介质中，其可以以一种特定的方式指导处理器或其他可编程数据处理装置实现功能，使得存储在计算机可读存储器或存储介质的指令生产一种制造产品，包括实施流程图的一个或多个方框中所指定功能的指令装置。

因此，流程图示意的方框支持用于执行指定功能的装置的组合、用于执行指定功能的步骤的组合以及用于执行指定功能的程序指令装置。还可以理解，该流程图示意的每个方框以及流程图示意中方框的组合，可以通过执行指定功能或步骤的基于硬件的专用计算机系统来实施，或者可以通过专用硬件和计算机指令的组合来实施。

如图8所示，根据本发明，通过从指令缓存获取一个指令，使发布单元(例如图3中的发布单元310)的操作开始(步骤810)。然后，由发布逻辑312例如关于该指令是否是流水线指令作出判定(步骤820)。如果是，则以一种本领域熟知的方式，例如通过执行单元的发布单元310将该指令发送到流水线(步骤830)，并且按照根据本发明的操作而结束该操作。实际上，发布单元继续从指令缓存获取指令，并且对每个所获取的指令重复图8所述处理。

如果该指令是一个非流水线指令，那么发布单元把该指令发布给执行单元的算术逻辑作为一个非流水线指令(步骤840)。发布单元然后发起在发布单元内用于一个初始搁置时段的搁置条件，该初始搁置时段等于完成一个最快的非流水线指令所需的最小数目的处理器周期(步骤850)。

发布单元然后等待初始搁置时段的过去，在这期间发布单元不再向执行单元发布指令(步骤860)。在该初始搁置时段之后，发布单元判定是否接收到来自执行单元的搁置信号(步骤870)。如果接收到来自执行单元的搁置信号，则发布单元搁置一个额外的处理器周期(步骤880)，并且返回到步骤870。如果没有接收到搁置信号，那么接收到一个指令完成信号并且解除发布单元的搁置条件(步骤890)。然后发布单元把该非流水线指令作为一个流水线指令重新发布给执行单元(步骤895)，并且该操作结束。此外，虽然根据本发明在此结束该操作，但对于每一个随后获取的指令，总体上发布单元的操作继续进行所重复的图8所示的处理。

现在参照图9，关于本发明，执行单元例如图3中的执行单元330的操作，开始于接收到来自发布单元的指令(步骤910)。如果该指令是一个流水线指令，则由执行单元的流水线以一种在本领域中熟知的方式执行该指令(步骤920)。如果该指令是一个非流水线指令，则通过执行单元的算术逻辑执行它(步骤930)。例如通过图4中的非流水线算术逻辑单元410，关于该指令是否已经完成执行作出判定(步骤940)。如果是，则例如通过非流水线算术逻辑单元410向发布单元发送一个完成信号(步骤950)，并且在一个阶段把该指令的执行结果加入到流水线，在该阶段将出现该指令的结果，使得在流水线中执行该指令(步骤960)。如前所述，这个完成信号可以是一个指示该非流水线指令处理完成的实际信号，或者可以是例如对执行单元搁置信号(XU_STALL)的去声明。

在完成该非流水线指令的处理并且把该结果加回到流水线中之后，然后按照本发明结束该操作。然而，对于由执行单元接收的每一个随后指令，执行单元的实际操作继续进行所执行的图9所描述的处理。

如果没有完成该指令执行，则例如通过非流水线算术逻辑单元410，关于初始搁置时段是否已过去作出判定(步骤970)。如果初始搁置时段没有过去，则操作返回到步骤930。如果初始搁置时段已经过去并且还没有完成该指令，则例如从非流水线算术逻辑单元410向发布单元发送一个搁置信号，例如搁置信号XU_STALL，使发布单元继续将指令搁置另一个处理器周期(步骤980)。然后操作返回到步骤930。

因此，本发明提供用于处理多周期非流水线指令调度的机制，其不需要片上额外面积并且不需要额外功率。而且，本发明提供一种用于处理这样的非流水线指令的机制，其消除了与对于非流水线指令执行时间的错误预计相关联的开销。

要注意到，尽管在整个功能数据处理系统的上下文中描述了本发明，但本领域的普通技术人员会明白，能够以一种指令的计算机可读介质的形式以及各种形式来分配本发明的过程，并且不管实际用于执行该分配的信号承载介质的具体类型，本发明都同等适用。计算机可读介质的例子包括记录类介质，例如软盘、硬盘驱动器、RAM、CD-ROM、DVD-ROM，和传输类介质，例如数字和模拟通信链路、有线或无线通信链路，其使用例如射频和光波传输的传输形式。计算机可读介质可以采用编码的形式，其经过解码用于在特定的数据处理系统中实际应用。

为了说明和描述，已经给出了本发明的描述，并且本发明的描述不意味着这是公开的本发明的全部形式或者受此限制。许多修改和变化对本领域普通技术人员来说是显而易见的。选择并描述本实施方式是为了最好地解释本发明的原理和实际应用，并且使本领域的其他普通技术人员能够理解，本发明进行各种修改的不同实施方式适合于预期的具体应用。

Claims (20)

1.一种在数据处理系统中用于处理非流水线指令的方法，包括：

向一个执行单元发布所述非流水线指令；

将对所述执行单元的其他指令的发布搁置一个初始搁置时段；

判定在所述初始搁置时段之后是否从所述执行单元接收到一个搁置请求；以及

如果接收到来自所述执行单元的一个搁置请求，则将对所述执行单元的其他指令的发布的搁置延长一个额外的处理器周期。

2.根据权利要求1所述的方法，其中所述初始搁置时段是完成对一个最快的非流水线指令的执行所需的最小数目的处理器周期。

3.根据权利要求1所述的方法，还包括：

如果没有从所述执行单元接收到一个搁置请求，则停止搁置对其他指令的发布；以及

如果没有接收到一个搁置请求，则把所述非流水线指令作为一个流水线指令重新发布给所述执行单元。

4.根据权利要求1所述的方法，其中在所述数据处理系统的一个处理器的一个发布单元内执行所述方法。

5.根据权利要求1所述的方法，还包括：

接收一个用于通过执行单元处理的指令；以及

判定所述指令是一个流水线指令还是一个非流水线指令。

6.根据权利要求5所述的方法，其中判定所述指令是一个流水线指令还是一个非流水线指令包括：

处理与所述指令相关联的一个操作代码；以及

比较所述操作代码和流水线指令操作代码表，其中如果所述操作代码不在所述流水线指令操作代码表中，则判定所述指令是一个非流水线指令。

7.根据权利要求1所述的方法，其中，对所述执行单元的其他指令的发布搁置一个初始搁置时段包括：

使用一个状态机来把一个发布逻辑单元置于一个搁置状态；以及

从一个搁置状态转换至另一个搁置状态，直至一个初始搁置时段终止。

8.根据权利要求7所述的方法，其中，在向所述执行单元发布所述指令之前，所述状态机处于非搁置状态，并且当向所述执行单元发布所述指令时，所述状态机就转换至第一搁置状态。

9.根据权利要求3所述的方法，其中，如果没有接收到一个搁置请求，则把所述非流水线指令作为一个流水线指令重新发布给所述执行单元，包括在允许把所述非流水线指令的结果旁路到下一个相关指令时，重新发布所述非流水线指令。

10.根据权利要求1所述的方法，其中，所述非流水线指令是乘法、除法、点乘积或平方根指令中的一种。

11.一种处理器，包括：

一个发布逻辑单元；和

一个执行单元，其耦合到所述发布逻辑单元，其中所述发布逻辑单元包括用于执行以下操作的逻辑：

向所述执行单元发布一个非流水线指令；

将对所述执行单元的其他指令的发布搁置一个初始搁置时段；

判定在所述初始搁置时段之后是否从所述执行单元接收到一个搁置请求；以及

如果从所述执行单元接收到一个搁置请求，则将对所述执行单元的其他指令的发布的搁置延长一个额外的处理器周期。

12.根据权利要求11所述的处理器，其中，所述初始搁置时段是完成对一个最快的非流水线指令的执行所需的最小数目的处理器周期。

13.根据权利要求11所述的处理器，其中，所述发布逻辑单元还包括用于执行以下操作的逻辑：

如果没有从所述执行单元接收到一个搁置请求，则停止搁置对其他指令的发布；以及

如果没有接收到一个搁置请求，则把所述非流水线指令作为一个流水线指令重新发布给所述执行单元。

14.根据权利要求11所述的处理器，其中，所述发布逻辑单元还包括用于执行以下操作的逻辑：

接收一个用于通过执行单元处理的指令；以及

判定所述指令是一个流水线指令还是一个非流水线指令。

15.根据权利要求14所述的处理器，其中，所述发布逻辑单元的所述逻辑，通过以下步骤判定所述指令是一个流水线指令还是一个非流水线指令：

处理与所述指令相关联的一个操作代码；以及

将所述操作代码与流水线指令操作代码表相比较，其中，如果所述操作代码不在所述流水线指令操作代码表中，则判定所述指令是一个非流水线指令。

16.根据权利要求11所述的处理器，其中，所述发布逻辑单元的所述逻辑，通过以下步骤将对所述执行单元的其他指令的发布搁置一个初始搁置时段：

使用一个状态机来把所述发布逻辑单元置于一个搁置状态；以及

从一个搁置状态转换至另一个搁置状态，直至一个初始搁置时段终止。

17.根据权利要求16所述的处理器，其中，在向所述执行单元发布所述指令，以及当向所述执行单元发布所述指令并且所述状态机转换至第一搁置状态之前，所述状态机处于非搁置状态。

18.根据权利要求13所述的处理器，其中，如果没有接收到一个搁置请求，则所述发布逻辑单元的所述逻辑把所述非流水线指令作为一个流水线指令重新发布给所述执行单元，包括用于在允许把所述非流水线指令的结果旁路给下一个相关指令时重新发布所述非流水线指令的逻辑。

19.根据权利要求11所述的处理器，其中，所述非流水线指令是乘法、除法、点乘积或平方根指令中的一种。

20.一种计算机可读介质中的计算机程序产品，用于处理非流水线指令，以执行权利要求1-10中任一权利要求的操作。

Images