用于在微处理器中使用多个阶段执行来对指令发布进行调度的方法和设备

摘要

一种微处理器，该微处理器被配置为执行被划分为多个离散阶段的程序，该微处理器包括：用于调度待在处理器上执行的程序指令的调度器；用于执行由调度器发布的编程指令的多个资源；其中所述调度器被配置为仅在接收到所述程序的先前阶段的执行已经完成的指示后调度所述程序的每一个阶段。通过把程序分离为多个阶段并且提供一能够确定是否阶段的执行已经完成的调度器，每一个阶段能够分别被调度并且先前阶段的结果能够用于告知随后阶段的调度。

说明书

技术领域

本发明涉及微处理器领域并特别有益于单指令多数据（SIMD）处理器。

背景技术

对于一些类型的数据，诸如图形数据，大块的数据经常需要经历相同的 处理操作。一个示例是当改变图像的亮度时。SIMD处理对于该处理是有益 的。正如任何其它处理器，SIMD处理器是具有执行单元、高速缓存和存储 器的微处理器，但额外包含了多数据流的并行执行的概念。并非单独地提取 数据实例，而是单提取指令能够被用于提取数据块。然后单指令能够被用于 在提取的数据块上操作，诸如“添加”操作。因此与传统的单指令单数据 （SISD）处理相比，SIMD处理减少了在处理器上的负载。

然而，SIMD处理仅仅能够被用于有限的情况。例如，甚至在大块数据 首先以相同方式被处理的情况下，程序经常包含条件指令或分支指令而导致 块中的一些数据由指令的一个分支对齐进行操作以及余下的数据由指令的 另一个分支进行操作。提前预测多少数据实例将需要由一个分支处理及多少 数据实例由另一个分支处理常常是不可能的。

通常在SIMD处理器中，调度器被用于调度程序的执行，分配由在开端 处的程序请求的资源。对于在一部分程序期间不同部分的数据集由不同指令 进行处理的程序的一个解决方案已经在所有数据上执行每一个分支，然后丢 弃不需要的结果。显然这是处理器资源和时间的低效使用。

相应地，在SIMD处理器中的程序执行期间能够更好地分配资源是可取 的，既减少了功率消耗又优化了资源利用。

发明内容

在第一方面，本发明提供了一种多线程的SIMD微处理器，该微处理器 被配置为执行被划分为多个离散编程指令阶段的程序，还被配置以使多个数 据实例能够由编程指令的单线程处理，该微处理器包括：

调度器，用于调度待在处理器上执行的程序指令；以及

多个资源，用于执行由所述调度器发布的编程指令；

其中所述调度器被配置为仅在接收到所述程序的先前阶段的执行已经 完成的指示后，调度所述程序的每一个阶段，以及被配置为在所述程序的每 一个阶段的调度期间，确定待分配给用于所述程序的该阶段的每一线程的数 据实例的数量。

所述调度器被配置为重新计算用于所述程序的每一个阶段的SIMD比 率。SIMD比率是由单指令处理的数据实例的数量。

处理器包括对于调度器的反馈环路，通过该反馈环路，程序的每一个阶 段的完成被传达给调度器。

优选地，在每一被调度的程序的每一个阶段执行期间，调度器保持用于 该程序的该阶段的记录。

优选地，所述处理器还包括线程完成计数器，其中当每一个线程完成所 述程序的阶段时，指示被发送到所述线程完成计数器，并且所述处理器被配 置为仅当所述线程完成计数器指示用于所述程序的先前阶段的所有线程已 经完成时，使调度器调度所述程序的下一个阶段。线程完成计数器可以是所 述调度器的一部分或被提供作为单独的部件。所述线程完成计数器可以包括 存储用于程序的每一个阶段的线程的数量的存储器，并且所述线程完成计数 器在每一次线程完成一个阶段时减少，并被配置以使当所述线程完成计数器 达到零时，所述调度器被命令调度所述程序的下一个阶段。

所述线程完成计数器可以存储用于程序的阶段的每一个线程的数据实 例的数量的记录。

优选地，所述调度器被配置为基于先前阶段的结果动态地分配用于所述 程序的每一个阶段的线程的数量。

在第二方面，本发明提供了一种用于在多线程的SIMD微处理器中调度 程序的方法，该微处理器包括用于调度编程指令的程序的调度器，所述程序 被划分为多个离散编程指令阶段，所述方法包括以下步骤：

调度待在处理器上执行的程序的第一阶段，该步骤包括确定多少数据实 例被分配给第一阶段的多个线程的每一个线程的步骤；

执行由所述调度器调度的所述程度的第一阶段；

当所述程序的第一阶段的执行完成时，提供所述程序的第一阶段的执行 完成的指示给所述调度器；以及

在所述调度器已经接收到所述程序的第一阶段的执行完成的指示之后， 调度所述程序的第二阶段，该步骤包括确定多少数据实例被分配给所述第二 阶段的多个线程的每一个线程的步骤。

优选地，所述方法还包括在所述被调度的程序的每一个阶段的执行期 间，保持该阶段的记录。

优选地，所述方法还包括当每一个线程完成所述程序的阶段时，更新记 录，以及仅当所述记录指示用于所述程序的先前阶段的所有线程已经完成 时，调度所述程序的下一个阶段。

优选地，所述方法还包括存储用于程序的阶段的每一个线程的数据实例 的数量的记录。

优选地，所述方法还包括基于先前阶段的结果动态地分配用于所述程序 的每一个阶段的线程的数量。

在第三方面，本发明提供了一种计算机程序产品，包括能够在SIMD处 理器上执行的计算机程序的形式的计算机可执行代码，其中所述程序由阶段 指令划分为多个阶段，所述阶段指令在所述程序中可能出现分支的点处被提 供，并且允许调度器分别地调度所述程序的每一个阶段。在这些位置处，所 述SIMD比率可能需要改变。例如在所述SIMD比率可能需要改变的位置处 遵从分支指令或条件指令。另一个示例是用于在图形处理程序中进行α混合 或图形保真的子例程。

附图说明

本发明的实施方式现在将参照附图仅通过示例的方式进行详细描述，其 中：

图1是根据本发明的处理器的示意图；

图2是根据本发明的程序调度方案的示意图；

图3是示出由图2的调度器执行的步骤的流程图；以及

图4是示出由用于调度新线程的调度器执行的处理的流程图。

具体实施方式

图1是根据本发明的实施方式的多线程的SIMD处理器10的示意图。 该处理器被配置为调度和执行每一个程序的单独的阶段，彼此分开，而不是 同时调度完整的程序然后执行它。

正如传统的处理器，随着调度器100的调度，指令提取单元110从存储 器中提取指令。提取到的指令被指令解码单元120解码并且被馈送到发布逻 辑130。发布逻辑将指令和提取到的数据馈送到算数逻辑单元（ALU）140 并且将结果存储在寄存器或存储器150中。

该ALU140还被配置为反馈线程完成指令到调度器100。正如将要解释 的，线程完成指令在程序的每一个阶段结束时提供。

新程序被提供到被划分为多阶段的调度器100。该程序被划分的方式由 程序设计员确定，但当程序的资源需求可以改变时，新阶段将通常在程序中 的某一点开始。

例如，程序可以包括传统指令以致如果数据值小于阈值则由指令的一个 分支处理，否则由指令的另一个分支处理。确定是否所有由程序处理的数据 实例都将由单分支处理或是否数据将被分离在两个分支之间也许是不可能 的，如果这样的话，需要确定多少数据实例将分配给（go dwon）哪一个分 支。所以在条件指令的时候，需要的线程的数量和需要的指令提取的数量可 以用此方示改变，该方式不能可靠预测。通过在此时分离程序，资源调度能 够被动态管理以响应所述数据结果。

新程序阶段的有利点的另一示例是在图形程序中用于混合背景颜色和 透明的前景对象的例程。前景对象可以具有统一的颜色并因此用于整个对象 的数据实例能够以相同的方式进行处理以用于颜色计算。然而，对象覆盖的 背景可以具有可变的颜色并因此对象的不同部分在混合例程中必须进行不 同的处理。因此混合例程可以被有利地放置到颜色例程的程序的分开的阶 段。

新程序阶段的有利点的又一个示例是图形保真（anti-aliasing）例程。当 在低分辨率屏幕上表示高分辨率图像时，图形保真被使用。为了移除不需要 的假象，诸如锯齿边缘，图形保真程序被用于使所述图像平滑。但是图形保 真仅在图形对象的边缘处需要。如果统一颜色的块在图像中，则在高分辨率 处处理大量的图像并且执行图形保真是没有必要的。仅在具有其它对象的边 界图形保真是必要的。因此程序可以包括分支指令以便使用图形保真程序处 理图像数据的边界部分，然而更大的数据块以计算上比较便宜的方式进行处 理。

在程序的每一个阶段结束时通过包含“阶段完成”指令将程序划分为多 个阶段。在执行反馈给调度器100阶段完成的指示时发出阶段完成指令。阶 段完成指令包括程序标识符。

程序指令还包括程序的资源需求的指示，但是并非在程序开始（start） 的时候被提供以覆盖整个程序，而是在程序的每一个阶段的开始（beginning） 提供。然后调度器100能够评定是否有足够的可利用的资源来执行该阶段。 因为需求资源可以基于先前阶段的结果，所以需求资源的指示在形式上可以 是算法以计算需求的资源。这种资源需求的动态计算移除了总是供给最差情 形场景的需要并导致了更有效的资源配置。

调度器100包括多阶段执行控制单元或存储了用于每一个调度的程序的 记录的线程完成计数器160，以及当前阶段调度的线程的数量。在新程序开 始时，调度器在线程完成计数器160中创建了新的记录，并且在每一次程序 的新阶段被调度时更新该记录。正如每一个线程完成阶段一样，线程完成计 数器接收指示并且调整执行程序的线程的数量的记录。每一次线程完成，只 是用于程序的线程的计数被减少直到线程计数达到零。当用于程序的线程计 数达到零时，该程序的新阶段可以被调度。线程完成计数器可以被提供为调 度器的一部分或为单独的部件。

图2是根据本发明的调度和执行过程的示意图，显示了程序队列和线程 完成计数器的内容。程序流在程序队列中作为对调度器的输入被提供。每一 个程序200被划分为以上描述的阶段，并且每一个程序具有预定数量的数据 实例，在程序队列中表明为值I。每一线程的实例的数量由值R指示。调度 器100调度程序的单独阶段并且等待在调度下一阶段先前该阶段完成的指 示。图2示出的例子中在程序队列中有三个程序还没有被调度以及程序A和 程序B两个程序当前正在被执行，但剩余的下一阶段将被调度。每一线程的 实例的数量R，对于每一程序的初始阶段是已知的但是基于先前阶段的结果 对于程序的随后阶段R可以被改变。因此R值对于已经被调度的程序A和 B的阶段是未知的。

正被执行的程序A的阶段有17个线程，通过值T指示在线程完成计数 器160中。每一个线程包含单个数据实例，因此R=1。正在被执行的程序B 的阶段有2个线程，每一个线程具有5个实例。图2显示了由进入执行管线 210的调度器调度的多线程。执行管线包括指令获取，发布逻辑和图1中示 出的ALU管线。

如参照图1已经描述的，线程完成计数器160存储已调度的用于每一个 程序的记录，以及用于当前阶段的调度的线程的数量。如每一个线程完成阶 段一样，线程完成计数器160接收来自执行管线210结束的指示220并且调 整执行该程序的线程的数量的记录。每一次线程完成，只有用于程序的线程 T的计数被减少直到线程计数达到零。当用于程序的线程计数达到零时，该 程序的新阶段能够被调度。

图3是示出由调度器执行的决定怎样调度新线程的处理步骤。在步骤 300中，调度器首先检查是否存在可用于运行来自可用于运行的程序队列的 程序的线程。如果没有可用的线程，那么调度器继续检查直到存在可用的线 程。

在步骤310，评估是否存在可用于运行队列中的第一程序的线程。在步 骤320，调度器检查是否第一程序已经具有运行的阶段并且调度器正在等待 用于指示该阶段已经完成的反馈。如果是，则执行步骤325，以同样的方式 评估队列中的下一个程序。如果调度器未等待来自第一程序的阶段的反馈， 则在步骤330，调度器评定是否存在任何要执行的下一阶段。如果没有下一 阶段，如步骤340示出的，该程序从队列中移除，并且其记录从线程完成计 数器移除。

如果存在更多遗留运行的阶段，则在步骤350中调度器确定该程序是否 仍在运行。如果该程序仍然在运行，则调度器移动到步骤325并且评估队列 中的下一个程序。如果程序没有在运行，则如步骤360指示的，调度器创建 程序的下一个阶段的新线程。随着新线程的创建，调度器返回步骤300以检 查是否存在空间以用于任何下一线程。

图4详细显示出了用于创建步骤360的新线程的由调度器采取的步骤。 在第一个步骤，步骤400中，调度器检查存在用于新线程的空间。如果没有， 则调度器继续检查直到空间成为可用的。当用于新线程的空间是可用的时， 如步骤410示出的，调度器创建新线程。新线程中的数据实例的数量是每一 线程（由硬件限制）允许的实例的最大数量和遗留的数据实例的数量之中较 少者。

一旦新线程已经创建，如步骤420示出的，用于线程的记录被创建或在 多阶段执行控制单元中被更新。

在步骤430，调度器评定是否存在下一数据实例在该阶段中运行。如果 是，则调度器尝试创建下一线程或多个线程以适应它们。如果不是，在步骤 440中线程创建过程结束并且调度器返回步骤300。

本发明允许程序的SIMD比率在程序执行期间被动态地改变。通过把程 序分离为多个阶段并且提供能够确定阶段的执行是否已经完成的调度器，每 一个阶段能够分别地被调度并且先前阶段的结果能够被用于告知随后步骤 的调度。

权利要求书(按照条约第19条的修改)

1.一种多线程的单指令多数据（SIMD）微处理器，该微处理器被配置 为执行被划分为多个离散编程指令阶段的程序，还被配置以使多个数据实例 能够由编程指令的单线程处理，该微处理器包括：

调度器，用于调度待在处理器上执行的程序指令的多个阶段；以及

多个资源，用于执行由所述调度器发布的编程指令；

其中所述调度器被配置为仅在接收到所述程序的先前阶段的执行已经 完成的指示后，调度所述程序的每一个阶段，以及被配置为在所述程序的每 一个阶段的调度期间，基于所述程序的先前阶段的结果，确定待分配给用于 所述程序的该阶段的每一线程的数据实例的数量。

2.根据权利要求1所述的微处理器，其中在每一被调度的程序的执行 期间，所述调度器保持用于该程序的记录。

3.根据以上权利要求中任一项权利要求所述的微处理器，该微处理器 还包括线程完成计数器，其中当每一个线程完成所述程序的阶段时，指示被 发送到所述线程完成计数器，并且其中所述处理器被配置为仅当所述线程完 成计数器指示用于所述程序的先前阶段的所有线程已经完成时，使所述调度 器调度所述程序的下一个阶段。

4.根据权利要求3所述的微处理器，其中所述线程完成计数器是所述 调度器的一部分。

5.根据权利要求3或4所述的微处理器，其中所述线程完成计数器包 括存储用于程序的每一个阶段的线程的数量的存储器，并且所述微处理器被 配置以使每一次线程完成一个阶段时所述线程完成计数器被减少，并且当所 述线程完成计数器达到零时，所述调度器被命令调度所述程序的下一个阶 段。

6.根据权利要求3、4或5所述的微处理器，其中所述线程完成计数器 存储用于程序的阶段的每一个线程的数据实例的数量的记录。

7.一种用于在多线程的单指令多数据微处理器中调度程序的方法，该 微处理器包括用于调度编程指令程序的调度器，所述程序被划分为多个离散 编程指令阶段，所述方法包括以下步骤：

调度待在处理器上执行的程序的第一阶段，该步骤包括确定多少数据实 例被分配给所述第一阶段的多个线程的每一个线程的步骤；

执行由所述调度器调度的所述程序的第一阶段；

当所述程序的第一阶段的执行完成时，提供所述程序的第一阶段的执行 完成的指示给所述调度器；以及

在所述调度器已经接收到所述程序的第一阶段的执行完成的指示之后， 调度所述程序的第二阶段，该步骤包括基于所述程序的第一阶段的结果来确 定多少数据实例被分配给所述第二阶段的多个线程的每一个线程的步骤。

8.根据权利要求7所述的方法，该方法还包括在被调度所述程序的每 一阶段的执行期间，保持该阶段的记录。

9.根据权利要求8所述的方法，该方法还包括当每一个线程完成所述 程序的阶段时，更新所述记录，以及仅当所述记录指示用于所述程序的先前 阶段的所有线程已经完成时，调度所述程序的下一个阶段。

10.根据权利要求7、8或9所述的方法，该方法还包括存储用于程序 的阶段的每一个线程的数据实例的数量的记录。

11.根据权利要求7至10中任一项权利要求所述的方法，该方法还包 括基于所述程序的第一阶段的结果，动态地分配用于所述程序的第二阶段的 线程的数量。

12.一种计算机程序产品，该计算机程序产品包括能够在SIMD处理器 上执行的计算机程序的形式的计算机可执行代码，所述程序由阶段指令划分 为多个阶段，所述阶段指令在所述程序中可能出现分支的点处被提供，并且 允许调度器分别地调度所述程序的每一个阶段并确定多少数据实例被分配 给用于所述程序的每一个阶段的每一个线程。