用于SIMD处理系统中的串行化执行的技术

摘要

本发明提供一种SIMD处理器，其可经配置以确定来自多个线程的一或多个活动线程；从所述一或多个活动线程选择一个活动线程；以及在所选择的活动线程上执行发散操作。所述发散操作可为串行操作。

说明书

技术领域

本发明涉及多线程处理，且更确切地说，涉及用于单指令多数据(SIMD)处理系统中的串行化执行的技术。

背景技术

单指令多数据(SIMD)处理系统为包含对多个数据段执行相同指令的多个处理元件的一类并行计算系统。SIMD系统可为独立计算机或计算系统的子系统。举例来说，一或多个SIMD执行单元可用于图形处理单元(GPU)中以实施支持可编程着色的可编程着色单元。

SIMD处理系统允许程序的多个执行线程以并行方式在多个处理元件上同步执行，由此增加需要对多个数据段执行相同集合的操作的程序的处理量。在一些情形中，可能需要串行地执行一或多个线程。举例来说，在需要将一个线程的输出作为一或多个其它线程的输入的情形中。在SIMD上执行串行操作可为资源密集的且低效的。

发明内容

本发明描述用于在SIMD处理系统中执行串行化操作的技术。在本发明的实例中，提议选择多个活动线程中的一个线程以执行串行指令的硬件执行的指令。所述指令可在不检查线程ID或使用指令以锁定共享变量的情况下选择线程。因而，可在对系统资源造成最小影响的情况下快速且高效地执行串行操作。

在本发明的一个实例中，经配置以执行发散操作的多线程处理器包括经配置以确定来自多个线程的一或多个活动线程且从所述一或多个活动线程选择一个活动线程的控制单元，和多个处理元件，其中与所选择的活动线程相关联的多个处理元件中的一个处理元件经配置以执行发散操作。

在本发明的另一实例中，经配置以在多线程处理器上执行发散操作的设备包括用于确定来自多个线程的一或多个活动线程的装置；用于从所述一或多个活动线程选择一个活动线程的装置；以及用于在所选择的活动线程上执行发散操作的装置。

在本发明的另一实例中，经配置以执行发散操作的设备包括多线程处理器，其包括经配置以确定来自多个线程的一或多个活动线程且从所述一或多个活动线程选择一个活动线程的控制单元和多个处理元件，其中与所选择的活动线程相关联的多个处理元件中的一个处理元件经配置以执行发散操作。

在本发明的另一实例中，在多线程处理器上执行发散操作的方法包括确定来自多个线程的一或多个活动线程；从所述一或多个活动线程选择一个活动线程；以及在所选择的活动线程上执行发散操作。

在附图及以下描述中阐述本发明的一或多个实例的细节。本发明的其它特征、目标和优点将根据所述描述和图式以及权利要求书显而易见。

附图说明

图1为说明可经配置以实施本发明的技术的装置的框图。

图2为说明可用于实施本发明的技术的实例图形处理单元(GPU)的框图。

图3为更详细地说明图2的实例GPU中的控制单元的框图。

图4为展示本发明的串行化操作技术的流程图。

图5为说明本发明的技术的实例方法的流程图。

具体实施方式

本发明描述用于在SIMD处理系统(例如，GPU)中执行串行操作的技术。用于在SIMD处理系统中执行串行操作的常规技术可为资源密集的且低效的。本发明提议在不循环所有非活动线程的情况下选择多个活动线程中的一个活动线程以执行串行操作的指令(例如，通过SIMD处理器中的硬件执行)。此可导致SIMD处理系统中的更高效的串行操作。

图1为说明可实施用于在SIMD处理系统中的串行化执行的本发明的技术的实例装置的框图。图1说明装置10，其包含GPU 12、系统存储器14以及处理器16(其可为中央处理单元(CPU))。装置10的实例包含(但不限于)视频装置(例如，媒体播放器)、机顶盒、无线手持机(例如，移动电话)、个人数字助理(PDA)、台式计算机、膝上型计算机、游戏控制台、视频会议单元、平板计算装置及其类似者。装置10除图1中所说明的那些组件之外还可包含若干组件。

系统存储器14可被视为装置10的存储器。系统存储器14可包括一或多个计算机可读存储媒体。系统存储器14的实例包含(但不限于)随机存取存储器(RAM)、电可擦除可编程只读存储器(EEPROM)、快闪存储器或可用于携载或存储呈指令和/或数据结构形式的所要程序代码且可通过计算机或处理器访问的任何其它媒体。

在一些方面中，系统存储器14可包含使处理器16和/或GPU 12执行在本发明中归于处理器16和GPU 12的功能的指令。因此，系统存储器14可为上面存储有指令的计算机可读存储媒体，所述指令在执行时致使一或多个处理器(例如，处理器16和GPU 12)执行各种功能。

在一些实例中，系统存储器14可被视为非暂时性存储媒体。术语“非暂时性”可指示存储媒体未体现于载波或传播信号中。然而，术语“非暂时性”不应解释为意味着系统存储器14为非可移动的或其内容为静态的。作为一个实例，可从装置10去除系统存储器14，及将所述系统存储器移动到另一装置。作为另一实例，实质上类似于系统存储器14的存储器可插入到装置10中。在某些实例中，非暂时性存储媒体可存储可随时间推移而变化的数据(例如，存储在RAM中)。

在一些实例中，例如装置10为无线手持机通信装置的实例，处理器16和GPU 12可形成在(IC)中。举例来说，IC可被视为芯片封装内的处理芯片。在一些实例中，例如装置10为台式或膝上型计算机的实例，处理器16和GPU 12可容纳在不同集成电路(即，不同芯片封装)中。然而，在装置10为无线手持机通信装置的实例中，处理器16和GPU 12容纳在不同集成电路中可为有可能的。

处理器16和GPU 12的实例包含(但不限于)数字信号处理器(DSP)、通用微处理器、专用集成电路(ASIC)、现场可编程逻辑阵列(FPGA)或其它等效集成或离散逻辑电路。在一些实例中，GPU 12可为包含集成和/或离散逻辑电路的专用硬件，所述电路为GPU 12提供适合于图形处理的大规模并行处理能力。在一些情况下，GPU 12还可包含通用处理能力，且在实施通用处理任务(即，非图形相关任务)时可被称为通用GPU(GPGPU)。

处理器16可执行各种类型的应用程序。应用程序的实例包含web浏览器、电子邮件应用程序、电子数据表、视频游戏或产生供显示的可视对象的其它应用程序。用于执行一或多个应用程序的指令可存储在系统存储器14内。处理器16可将可视对象的图形数据传输到GPU 12以供进一步处理。

举例来说，处理器16可将处理任务分担到GPU 12，例如需要大规模并行操作的任务。作为一个实例，图形处理需要大规模并行操作，且处理器16可将此些图形处理任务分担到GPU 12。处理器16可根据特定应用程序处理接口(API)与GPU 12通信。此些API的实例包含的API、克罗诺斯(Khronos)小组的API以及OpenCL^TMAPI；然而，本发明的各方面不限于DirectX、OpenGL或OpenCL>

为了执行图形操作，GPU 12可实施图形处理管道。图形处理管道包含执行如由执行于GPU 12上的软件或固件定义的功能，和通过经硬接线以执行极特定功能的固定功能单元执行功能。执行于GPU 12上的软件或固件可被称为着色器程序(或仅仅着色器)，且着色器程序可在GPU 12的一或多个着色器核心上执行。着色器程序为用户提供功能灵活性，由于用户可设计着色器程序以任何可设想方式执行所要任务。然而，固定功能单元针对固定功能单元执行任务的方式而经硬接线。因此，固定功能单元可不提供大量功能灵活性。

举例来说，处理器16可执行应用程序，例如视频游戏；且处理器16可产生图形数据作为执行的一部分。处理器16可输出图形数据以供GPU 12处理。GPU 12可接着处理图形管道中的图形数据。在一些实例中，为了处理图形数据，GPU 12可需要执行一或多个着色器程序。举例来说，处理器16上执行的应用程序可致使处理器16指示GPU 12以从系统存储器14检索着色器程序且指示GPU 12以执行着色器程序。

装置10还可任选地包含显示器60、用户界面62以及收发器模块64。装置10可包含出于清楚起见而未展示在图1中的额外模块或单元。举例来说，装置10可包含扬声器和麦克风(两者都不展示在图1中)以在装置10为移动无线电话的实例中实现电话通信。此外，装置10中所展示的各种模块和单元可并不在装置10的每一实例中都是必要的。举例来说，在装置10为桌上型计算机的实例中，用户界面62和显示器60可在装置10外部。作为另一实例，在显示器60为移动装置的触敏或存在敏感型显示器的实例中，用户界面62可为显示器60的一部分。

用户界面62的实例包含(但不限于)跟踪球、鼠标、键盘和其它类型的输入装置。用户界面62也可为触摸屏且可并入作为显示器60的一部分。收发器模块64可包含电路以允许装置10与另一装置或网络之间的无线或有线通信。收发器模块64可包含调制器、解调器、放大器和用于有线或无线通信的其它此类电路。显示器60可包括液晶显示器(LCD)、阴极射线管(CRT)显示器、等离子显示器、触敏显示器、存在敏感型显示器或另一类型的显示装置。

如将在下文中更详细地解释，根据本发明的技术，GPU 12可经配置以执行在多线程处理器上执行发散操作的方法。GPU 12可经配置以确定来自多个线程的一或多个活动线程；从所述一或多个活动线程选择一个活动线程；以及在所选择的活动线程上执行发散操作。

图2为说明可用于实施本发明的串行处理技术的GPU 12的实例配置的框图。GPU 12经配置以以并行方式执行程序指令。GPU 12包含控制单元72，处理元件74A到74D(统称为“处理元件74”)，指令存储器76，数据存储器78以及通信路径80、82、84、86A到86D。通信路径86A到86D可被统称为“通信路径86”。在一些实例中，GPU 12可经配置为单指令多数据(SIMD)处理系统，其经配置以使用处理元件74执行程序的多个执行线程。在此SIMD系统中，处理元件74可一起对于不同数据项同时处理单个指令。在与程序相关联的所有线程完成执行之后，程序可注销。

控制单元72经配置以控制GPU 12执行存储于指令存储器76中的程序指令。对于每一程序指令，控制单元72可经由通信路径80从指令存储器76检索指令，且处理指令。在一些实例中，控制单元72可通过使得在处理元件74中的一或多者上执行与指令相关联的操作而处理指令。举例来说，由控制单元72检索到的指令可为算术指令，其指示GPU 12执行关于由指令指定的数据项的算术运算；且控制单元72可致使处理元件74中的一或多者对指定数据项执行算术运算。在另外的实例中，控制单元72可处理指令而无需使得在处理元件74上执行操作。

控制单元72可通过经由通信路径82将指令提供到处理元件74而致使在处理元件74中的一或多者上执行操作。指令可指定通过处理元件74执行操作。提供到处理元件74中的一或多者的指令可与从指令存储器76所检索到的指令相同或不同。在一些实例中，控制单元72可通过激活特定子集的处理元件74(在此之后应执行操作)和去激活另一子集的处理元件74(在此之后不应执行操作)中的一者或两者而致使在特定子集的处理元件74(包含单个处理元件)上执行操作。控制单元72可通过经由通信路径82将相应激活和/或去激活信号提供到处理元件74中的每一者而激活和/或去激活处理元件74。在一些实例中，控制单元72可通过将激活和/或去激活信号提供到处理元件74以及将指令提供到处理元件74而激活和/或去激活处理元件74。在另外的实例中，控制单元72可在将指令提供到处理元件74之前激活和/或去激活处理元件74。

控制单元72可使用处理元件74执行程序的多个执行线程。并行执行的多个线程有时被称为波。处理元件74中的每一者可经配置以针对多个线程中的相应线程而处理程序指令。举例来说，控制单元72可将每一执行线程分配到处理元件74中的个别者以供处理。相对于数据项集合中的不同数据项，程序的执行线程可执行相同指令集。举例来说，处理元件74A可关于多个数据项中的第一数据项子集执行存储于指令存储器76中的程序的第一执行线程，且处理元件74B可关于多个数据项中的第二数据项子集执行存储于指令存储器76中的程序的第二执行线程。第一执行线程可与第二执行线程包含相同指令，但第一数据项子集可不同于第二数据项子集。

在一些实例中，控制单元72可激活并去激活多个执行线程中的个别线程。当控制单元72去激活线程时，控制单元72也可去激活和/或停用经分配以执行所述线程的处理元件74A到74D。此些经去激活的线程可被称为非活动线程。类似地，当控制单元72激活线程时，控制单元72也可激活经分配以执行所述线程的处理元件74A到74D。此些经激活的线程可被称为活动线程。如将在下文中更详细地解释，控制单元72可经配置以在不需要考虑其它活动或非活动线程的情况下选择激活线程以执行发散操作(例如，串行操作)。

如本文中所使用，活动线程可指代经激活的线程，且非活动线程可指代经去激活的线程。对于在给定处理周期期间GPU 12上执行的多个线程，活动线程中的每一者可经配置以在处理周期期间处理通过用于多个线程的全局程序计数器寄存器所识别的程序指令。举例来说，控制单元72可激活处理元件74，其经分配到活动线程以便配置此些处理元件74以在处理周期期间处理程序指令。另一方面，对于在给定处理周期期间GPU 12上执行的多个线程，非活动线程中的每一者可经配置以不在处理周期期间处理程序指令。举例来说，控制单元72可去激活处理元件74，其经分配到非活动线程以配置此些处理元件74从而不在处理周期期间处理程序指令。

在一些实例中，处理周期可指程序计数器的连续加载之间的时间间隔。举例来说，处理周期可指代当程序计数器加载第一值时与当程序计数器加载第二值时之间的时间。第一和第二值可为相同或不同值。在程序计数器归因于恢复检查技术而以异步方式加载的实例中，此些异步加载在一些实例中可不用以区分处理周期。换句话说，在这些实例中，处理周期可指代程序计数器的连续同步加载之间的时间间隔。在一些实例中，程序计数器的同步加载可指由时钟信号触发的加载。

有时，在检索下一指令之前，控制单元72确定待由GPU 12处理的下一指令。控制单元72确定待处理的下一指令的方式取决于先前通过GPU 12所检索到的指令是否为控制流指令而不同。如果先前通过GPU 12所检索到的指令不是控制流指令，那么控制单元72可确定待由GPU 12处理的下一指令对应于存储于指令存储器76中的下一顺序指令。举例来说，指令存储器76可以经排序序列存储程序指令，且下一顺序指令可为紧接在先前所检索到的指令之后出现的指令。

如果先前通过GPU 12所检索到的指令为控制流指令，那么控制单元72可基于控制流指令中所指定的信息而确定待由GPU 12处理的下一指令。举例来说，控制流指令可为非条件性控制流指令(例如，无条件分支指令或跳转指令)，在此状况下控制单元72可确定待由GPU 12处理的下一指令为通过控制流指令识别的目标指令。作为另一实例，控制流指令可为条件控制流指令(例如，条件分支指令)，在此状况下控制单元72可从指令存储器76选择通过控制流指令所识别的目标指令或存储于指令存储器76中的下一顺序指令中的一者作为待处理的下一指令。

如本文中所使用，控制流指令可指代包含识别指令存储器76中的目标指令的信息的指令。举例来说，控制流指令可包含指示控制流指令的目标程序计数器值的目标值。目标程序计数器值可指示目标指令的目标地址。在一些实例中，目标指令可不同于存储于指令存储器76中的下一顺序指令。高级程序代码可包含控制流语句，例如如果、开关、进行、对于、在…时、继续、中断和转到语句。编译程序可将高级控制流语句转译成低级(例如，机器级)控制流指令。并非控制流指令的指令可在本文中被称作顺序指令。举例来说，顺序指令可不包含识别目标指令的信息。

对于控制流指令，识别目标指令的信息可为指示存储于指令存储器76中的目标指令的值。在一些实例中，指示指令存储器76中的目标指令的值可为指示指令存储器76中的目标指令的指令地址的值。在一些状况下，指示目标指令的指令地址的值可为指令存储器76中的目标指令的地址。在额外状况下，指示目标指令的指令地址的值可为用于计算目标指令的地址的值。在另外的实例中，指示目标指令的指令地址的值可为指示对应于目标指令的目标程序计数器值的值。在一些状况下，指示目标程序计数器值的值可为对应于目标指令的目标程序计数器值。在额外状况下，指示目标程序计数器值的值可为用于计算目标程序计数器值的值。在一些实例中，对应于目标指令的目标程序计数器值可等于目标指令的地址。

控制流指令可为前向控制流指令或后向控制流指令。前向控制流指令可为目标指令出现在存储于指令存储器76中的指令的经排序序列中的控制流指令之后的控制流指令。后向控制流指令可为目标指令出现在存储于指令存储器76中的指令的经排序序列中的下一顺序指令之前的控制流指令。下一顺序指令可紧接在指令的经排序序列中的控制流指令之后出现。

控制流指令可为条件性控制流指令或非条件性控制流指令。条件控制流指令包含指定用于跳转到与控制流指令相关联的目标指令的条件的信息。当处理条件控制流指令时，如果控制单元72确定满足条件，那么控制单元72可确定待处理的下一指令为目标指令。另一方面，如果控制单元72确定并不满足条件，那么控制单元72可确定待处理的下一指令为存储于指令存储器76中的下一顺序指令。非条件性控制流指令并不包含指定用于跳转到与控制流指令相关联的目标指令的条件的信息。当处理非条件性控制流指令时，控制单元72可无条件地确定待处理的下一指令为通过控制流指令所识别的目标指令。换句话说，此状况下的确定并不取决于非条件性控制流指令中所指定的任何条件。如本文中所使用，条件控制流指令可在本文中被称作分支指令，除非分支指令以其它方式被指定为无条件分支指令。并且，非条件性控制流指令可在本文中被称作跳转指令。

条件性分支指令可包含关于一或多个数据项值所指定的条件。举例来说，一种类型的条件可为比较GPU 12中执行的每一活动线程的第一数据项值与第二数据项值的比较条件。比较数据项值可包含例如确定第一数据项值是否大于、小于、不超过、不低于、等于或不等于第二数据项值。另一类型的条件可为确定执行于GPU 12上的每一活动线程的数据项值是否等于或不等于零的零检查条件。由于处理元件74中的每一者对不同数据项进行操作，因此对于GPU 12上执行的每一活动线程来说，评估条件的结果可不同。

如果GPU 12上执行的所有活动线程均满足分支条件或GPU 12上执行的所有活动线程不满足分支条件，那么均匀分支条件出现且线程的分支发散据称为均匀的。另一方面，如果GPU 12上执行的活动线程中的至少一者满足分支条件和GPU 12上执行的活动线程中的至少一者不满足分支条件，那么发散分支条件出现且线程的分支发散据称为发散的。

发散操作的一个实例为串行操作。串行操作(或一系列串行操作)为需要一个线程的输出(例如，来自串行操作)作为一或多个其它线程的输入的操作。即完成其它线程可不继续并行地处理成一或多个其它线程的输出。在此意义上，SIMD装置中的线程可串行执行一段时间。

通常，GPU 12上执行的线程可以步调一致方式执行相同指令。换句话说，对于所有活动线程，处理元件74中的每一者可在处理周期期间共同执行相同指令。然而，当出现发散分支条件时，满足分支条件的线程可经调度以执行不同于经调度以由并不满足分支条件的线程所执行的下一指令的下一指令。如上文所论述，一个此类发散分支条件可为串行操作。

控制单元72经由通信路径800以通信方式耦合到指令存储器76；经由通信路径82耦合到处理元件74；以及经由通信路径84耦合到数据存储器78。控制单元72可使用通信路径800以将读取指令发送到指令存储器76。读取指令可指定指令存储器76中的指令地址，应根据所述地址检索指令。响应于发送读取指令，控制单元72可从指令存储器76接收一或多个程序指令。控制单元72可使用通信路径82以将指令提供到处理元件74，且在一些实例中从处理元件74接收数据，例如用于评估分支条件的比较指令的结果。在一些实例中，控制单元72可使用通信路径84以从数据存储器78检索数据项值例如以确定分支条件。尽管图2将GPU 12说明为包含通信路径84，但在其它实例中，GPU 12可不包含通信路径84。

处理元件74中的每一者可经配置以处理存储于指令存储器76中的程序的指令。在一些实例中，处理元件74中的每一者可经配置以执行相同操作集合。举例来说，处理元件74中的每一者可实施相同指令集架构(ISA)。在额外实例中，处理元件74中的每一者可为算术逻辑单元(ALU)。在另外的实例中，GPU 12可经配置为向量处理器，且处理元件74中的每一者可为向量处理器内的处理元件。在额外实例中，GPU 12可为SIMD执行单元，且处理元件74中的每一者可为SIMD执行单元内的SIMD处理元件。

由处理元件74所执行的运算可包含算术运算、逻辑运算、比较运算等。算术运算可包含例如加法运算、减法运算、乘法运算、除法运算等的运算。算术运算还可包含(例如)整数算术运算和/或浮点算术运算。逻辑运算可包含例如逐位“与”运算、逐位“或”运算、逐位异或运算等的运算。比较运算可包含例如大于运算、小于运算、等于零运算、不等于零运算等的运算。大于运算和小于运算可确定第一数据项大于还是小于第二数据项。等于零运算和不等于零运算可确定数据项等于零还是不等于零。用于运算的操作数可存储于数据存储器78中所含有的寄存器中。

处理元件74中的每一者可经配置以响应于经由通信路径82从控制单元72接收指令而执行操作。在一些实例中，处理元件74中的每一者可经配置以经激活和/或经去激活，与其它处理元件74无关。在这些实例中，处理元件74中的每一者可经配置以响应于在激活相应处理元件74A到74D时从控制单元72接收指令而执行操作；和响应于在去激活(即，未激活)相应处理元件74A到74D时从控制单元72接收指令而并不执行操作。

处理元件14A到14D中的每一者可经由相应通信路径86A到86D以通信方式耦合到数据存储器78。处理元件74可经配置以经由通信路径86从数据存储器78检索数据且将数据存储到数据存储器78。在一些实例中，从数据存储器18所检索到的数据可为用于由处理元件74所执行的操作的操作数。在一些实例中，存储到数据存储器78的数据可为由处理元件74所执行的操作的结果。

指令存储器76经配置以存储程序以供GPU 12执行。程序可存储为指令序列。在一些实例中，每一指令可由唯一指令地址值寻址。在此些实例中，指令序列中的稍后指令的指令地址值大于指令序列中的先前指令的指令地址值。在一些实例中，程序指令可为机器级指令。即，在这些实例中，指令可呈对应于GPU 12的ISA的格式。指令存储器76经配置以经由通信路径80从控制单元72接收读取指令。读取指令可指定指令地址，应根据所述地址检索指令。响应于接收读取指令，指令存储器76可经由通信路径80将对应于读取指令中所指定的指令地址的指令提供到控制单元72。

指令存储器76可为任何类型的存储器、高速缓冲存储器或其组合。当指令存储器76为高速缓冲存储器时，指令存储器76可高速缓存存储于GPU 12外部的程序存储器中的程序。尽管指令存储器76经说明为在GPU 12内，但在其它实例中，指令存储器76可在GPU 12外部。

数据存储器78经配置以存储由处理元件74所使用的数据项。在一些实例中，数据存储器78可包括多个寄存器，每一寄存器经配置以将相应数据项存储在GPU 12上操作的多个数据项内。数据存储器78可耦合到一或多个通信路径(未展示)，其经配置以在数据存储器78中的寄存器与存储器或高速缓冲存储器(未展示)之间分支数据。

尽管图2说明用于存储由处理元件74所使用的数据的单个数据存储器78，但在其它实例中，GPU 12可包含用于处理元件74中的每一者的单独、专用数据存储器。出于例示性目的，GPU 12说明四个处理元件74。在其它实例中，GPU 12可具有呈相同或不同配置的更多处理元件。

图3为更详细地说明图2的实例GPU 12中的控制单元72的框图。控制单元72包含程序计数器88、提取模块90、解码模块92以及控制流模块94。控制流模块94可替代地在本文中被称作控制流单元。

程序计数器288经配置以存储程序计数器值。在一些实例中，程序计数器88可为硬件寄存器，例如程序计数器寄存器。程序计数器值可指示存储于指令存储器76中的指令。在一些状况下，程序计数器值可等于存储于指令存储器76中的指令的指令地址。在额外状况下，程序计数器值可用于计算存储于指令存储器76中的指令的指令地址。举例来说，程序计数器值可加到偏移值以产生指令地址。程序计数器88可在本文中被称作“全局程序计数器”或“全局程序计数器寄存器”，这是因为程序计数器88可用作所有处理元件74的单个程序计数器。

提取模块90经配置以基于存储于程序计数器88中的程序计数器值而从控制单元72提取(例如，检索)指令。举例来说，提取模块90可根据通过存储于程序计数器88中的程序计数器值所识别的指令地址提取指令。提取模块90可将所提取的指令提供到解码模块92以供进一步处理。

解码模块92经配置以解码从提取模块90接收的指令。解码指令可涉及确定指令是否为可由处理元件74处理的类型的指令。如果指令为可由处理元件74处理的类型的指令，那么解码模块92可致使在处理元件74中的一或多者上执行指令。在一些实例中，解码模块92可致使在所有处理元件74上执行指令。在其它实例中，解码模块92可致使在不到全部处理元件74上执行指令。在一些状况下，使得在处理元件74中的一或多者上执行指令可包含将指令发布到处理元件74中的一或多者以供执行。举例来说，提取模块90可提取通过程序计数器88识别的顺序指令，且将顺序指令发布到对应于活动线程的所有处理元件74以供处理。如果指令并非可由处理元件74处理的指令类型，那么控制单元72可在并不将指令发布到处理元件74中的任一者以供处理的情况下处理指令。举例来说，指令可为并不需要由处理元件74处理的控制流指令类型，在此状况下控制单元72可在并不将指令发布到处理元件74中的任一者的情况下处理指令。

在任一状况下，解码模块92可将控制信息转发到控制流模块94以供进一步处理。在一些实例中，控制信息可为指令自身。在另外的实例中，控制信息可包含以下信息：例如指示指令为控制流指令还是顺序指令的信息，如果指令为控制流指令，那么信息指示指令为分支指令还是跳转指令；如果指令为分支或跳转指令，那么信息指示分支或跳转指令为前向还是后向分支或跳转指令；以及如果指令为分支指令，那么信息指定分支条件。

为可由处理元件74处理的类型的指令可包含算术指令和逻辑指令。算术指令可指指示处理元件74执行算术运算的指令，且逻辑指令可指指示处理元件74执行逻辑运算的指令。在一些实例中，控制流指令可为可由处理元件74处理的指令，例如控制流指令可包含通过处理元件74评估的分支条件。并非可由处理元件74处理的类型的指令可包含通过控制单元72评估分支条件的控制流指令和/或并不具有分支条件的控制流指令。

控制流模块94可确定与待由控制单元72处理的下一指令相关联的程序计数器值，且将程序计数器值加载到程序计数器88中。如果先前提取的指令为顺序指令，那么控制流模块94可选择指示存储于指令存储器76中的下一顺序指令的程序计数器值以加载到程序计数器88中。如果先前提取的指令为控制流指令，那么控制流模块94可利用恢复计数器技术。

控制流模块94可存储GPU 12上执行的每一线程的恢复计数器值。举例来说，存储于控制流模块94中的恢复计数器值的数目可等于GPU 12中含有的处理元件74的数目。对于每一恢复计数器值，如果对应于相应恢复计数器值的线程为非活动的，那么恢复计数器值可指示程序计数器值，在所述程序计数器值下应激活或重新激活非活动线程。否则，如果对应于相应恢复计数器值的线程为活动的，那么恢复计数器值在一些实例中可被设置成最大值，即，为用于恢复计数器的存储槽或寄存器中可表示的最大值的值。

控制流模块94可存储GPU 12上执行的每一线程的活动旗标。举例来说，存储于控制流模块94中的活动旗标的数目可等于GPU 12中含有的处理元件74的数目。每一活动旗标可指示与活动旗标相关联的线程是活动的还是非活动的。在一些实例中，活动旗标可为经设置以指示与活动旗标相关联的线程为活动的和经重新设置以指示与活动旗标相关联的线程为非活动的单一位。

在一些实例中，控制流模块94还可存储程序状态。举例来说，第一程序状态可指示所有线程均为活动的；第二程序状态可指示至少一个线程为活动的且至少一个线程为非活动的；以及第三程序状态可指示所有线程均为非活动的。程序状态可在此些实例中用于选择用以加载到程序计数器88中的程序计数器值。

在一些实例中，控制流模块94可经配置以经由通信路径82激活和去激活处理元件74中的一或多者。在额外实例中，控制流模块94可指示解码模块92从而激活和去激活特定处理元件74。在另外的实例中，控制流模块94可经由通信路径82从处理元件74中的一或多者接收比较指令的结果。在一些实例中的比较指令的结果可用于评估分支条件。在又另外的实例中，出于评估分支条件的目的，控制流模块94可经由通信路径84从数据存储器78检索一或多个数据项。

如上文所论述，在并行机器(例如，SIMD处理系统)内，常常存在执行发散操作(例如，串行化操作)的需要。举例来说，GPU 12可经指示以执行‘前缀求和’，其中在处理元件74上执行的给定线程的输入取决于处理元件74上执行的另一线程的输出。

在SIMD处理系统上执行串行化操作的一个常规途径涉及使用原子本机指令，从而所有线程将争取对共享变量执行锁定(即，因此在某一时间处仅处理元件74中的一者可访问所述变量)。然而，使用原子指令和锁定可为低效的，由于其为有限资源且通常需要长时延以供执行。

用于执行串行操作的另一途径涉及产生每一线程的唯一值(例如，thread_id)。经由控制单元72，GPU 12将接着经配置以循环通过所有线程，从而对于每一循环迭代仅选择单一线程(通过线程ID)。此操作的实例伪码展示如下：

对于(i＝0；i)//i可表示波中的线程的总数目

{如果(thread_id＝＝i){执行串行化操作}}

上述途径需要额外测试和测试变量，也迫使甚至针对可为非活动的的那些线程的循环迭代。此在资源和时间两者上均为低效的。

鉴于这些缺点，本发明提议用于在并行处理系统(例如，SIMD处理系统)中执行串行化操作的技术。在以下实例中，本发明描述指令(例如，硬件执行的指令)，从而可在不需要访问任何非活动线程的情况下选择来自多个线程的活动线程以执行串行化操作。

本发明中提议的解决方案为“GetOne”指令(GetOne_and_branch())，其可由GPU 12的控制单元72执行。控制单元72可经配置以从多个线程(例如，波中的线程)当中选择单个活动线程以供执行。控制单元72可使用通过控制流模块94所存储的活动旗标确定当前哪些线程为活动的。一旦选择单个活动线程，波中的所有其它活动线程可执行分支条件，而所选择的线程执行发散操作(例如，串行操作)。“GetOne”指令可接着用于执行如通过以下伪码所示的串行操作：

在以上实例中，控制单元72最初经指示以转到代码的LOOP指令。LOOP指令包含从多个活动线程(例如，波)选择单个活动线程且前进到串行指令({执行串行化操作})且接着离开控制块(转到CONTINUE)且变为非活动的“GetOne”指令(GetOne_and_branch)。未选线程执行GetOne_and_branch指令的分支指令。在以上实例中，分支指令为“TRY_AGAIN”指令，其基本上将所有未选活动线程发送回到Loop指令。接着，可选择剩余活动线程中的另一者以执行串行化操作。

“GetOne”指令的机制允许在无额外变量和不需要非活动线程的循环迭代的情况下波内的高效串行化。本发明的技术利用波内的并行线程已经归因于其共享的单个指令而具有一定程度的同步的事实。以此方式，本发明的“GetOne”指令允许选择一个活动线程以供串行操作，而同时使得所有其它活动线程为非活动的。

图4为更详细地展示本发明的串行化操作技术的流程图。最初，GPU 12的控制单元72可接收“GetOne”指令(100)。响应于“GetOne”指令，控制单元72经配置以确定多个线程(例如，波)中的哪些线程为活动的(102)。在一个实例中，控制单元72可经配置以读取与线程中的每一者相关联的活动旗标以确定哪些线程为活动的。如果控制单元72确定未剩余活动线程(103)，那么控制块结束(返回112)。

如果控制单元72确定存在活动线程剩余(103)，那么控制单元72可选择所述多个线程中的一个活动线程(104)。所选择的线程(106为是)接着在处理元件74中的一者上执行串行操作(108)。在执行串行操作之后，所选择的活动线程经去激活(110)。未选中的剩余活动线程可循环回到“Get One”指令(106为否)。

经配置以执行“GetOne”指令以供上文所描述的串行执行的GPU 12还可经配置以使用“GetOne”指令以分裂呈现发散成多个子波(其中的每一者均可为均匀的)的单波。猜想需要执行(有可能发散)的子例程调用的实例。即，仅波中的线程的一部分将执行子例程的情形。用于执行发散子例程的一个常规技术涉及唯一地执行每一线程。此可为低效的。

替代地，GPU 12可经配置以执行“GetOne”指令以将子例程存储在共享寄存器中，所述共享寄存器可接着通过可访问所述共享寄存器的所有线程(即，可以访问所述共享寄存器的处理元件74)执行。共享寄存器可为数据存储器78、指令存储器76或可用于处理元件74的其它存储器的一部分。

使用“GetOne”指令和共享寄存器，GPU 12可经配置以使用“GetOne”指令选择子例程目标(即，存储子例程指令的位置)；将所述目标广播到所有线程(即，提供子例程位置存储于共享寄存器中的指示)；以及在所有匹配线程上执行子例程(即，在可访问共享寄存器的处理元件74上执行子例程)。对于可访问不同共享寄存器的其它线程，可接着重复此过程。此过程的实例伪码展示如下。

最初，控制单元72将继续进行到代码的LOOP区段且执行如先前所描述的“GetOne”指令。“GetOne”指令选择一个活动线程以执行操作。在以上实例中，所选活动线程将执行将位置的地址(subroutine_target)存储在共享寄存器(shared_R0)中的操作。未选中的任何活动线程将执行CONTINUE1操作。在CONTINUE1操作中，可访问共享寄存器shared_R0的每一线程(即，处理元件74)执行位于subroutine_target的代码且在CONTINUE 2处离开控制块。如果任何未被选择的活动线程不可访问共享寄存器，那么未被选择的活动线程返回到循环操作，其中另一子例程调用可存储于不同共享寄存器中。同样，如同串行操作的实例，跳过任何非活动线程且进行最小数目的唯一子例程调用。

图5为说明本发明的实例方法的流程图。图5的技术可通过GPU 12(包含GPU 12的控制单元72)实施。在本发明的一个实例中，GPU 12经配置以执行在多线程处理器上执行发散操作的方法。GPU 12可经配置以确定来自多个线程的一或多个活动线程(152)；从所述一或多个活动线程选择一个活动线程(154)；以及在所选择的活动线程上执行发散操作(156)。

在本发明的一个实例中，多线程处理器为SIMD处理器。在本发明的另一实例中，所述多个线程形成波，其中通过SIMD处理器并行地执行所述波。

在本发明的另一实例中，GPU 12经配置以通过在所选择的活动线程上执行串行化操作而在所选择的活动线程上执行发散操作。在本发明的另一实例中，发散操作将子例程目标存储在共享寄存器中，且GPU 12进一步经配置以在可访问共享寄存器的一或多个活动线程上执行存储在子例程目标处的代码。

本发明中所描述的技术可至少部分在硬件、软件、固件或其任何组合中实施。举例来说，所描述技术的各种方面可在一或多个处理器内实施，包含一或多个微处理器、数字信号处理器(DSP)、专用集成电路(ASIC)、现场可编程门阵列(FPGA)，或任何其它等效集成或离散逻辑电路，以及此些组件的任何组合。术语“处理器”或“处理电路”可大体上指前述逻辑电路中的任一者(单独或结合其它逻辑电路)或例如执行处理的离散硬件的任何其它等效电路。

此硬件、软件和固件可实施于同一装置内或单独装置内以支持本发明中所描述的各种操作和功能。另外，所描述单元、模块或组件中的任一者可一起或单独作为离散但可互操作逻辑装置而实施。将不同特征描述为模块或单元意在强调不同功能方面并且未必暗示此些模块或单元必须由单独硬件或软件组件实现。相反地，与一或多个模块或单元相关联的功能性可由单独硬件、固件和/或软件组件执行，或整合在共用或单独硬件或软件组件内。

本发明中所描述的技术也可存储、体现或编码于计算机可读媒体(例如，存储指令的计算机可读存储媒体)中。嵌入或编码于计算机可读媒体中的指令可致使一或多个处理器执行本文中所描述的技术(例如，当由一或多个处理器执行指令时)。计算机可读存储媒体可包含随机存取存储器(RAM)、只读存储器(ROM)、可编程只读存储器(PROM)、可擦除可编程只读存储器(EPROM)、电可擦除可编程只读存储器(EEPROM)、快闪存储器、硬盘、CD-ROM、软盘、盒式磁带、磁性媒体、光学媒体或其它有形计算机可读存储媒体。

计算机可读媒体可包含计算机可读存储媒体，其对应于例如上文所列的那些的有形存储媒体。计算机可读媒体也可包括通信媒体，其包含促进计算机程序从一个位置到另一位置的传送(例如，根据通信协议)的任何媒体。以此方式，短语“计算机可读媒体”大体上可对应于(1)非暂时性有形计算机可读存储媒体，和(2)例如暂时性信号或载波等非有形计算机可读通信媒体。

已描述各种方面和实例。然而，可在不脱离以下权利要求书的范围的情况下对本发明的结构或技术作出修改。