使用动态宽度计算的壁垒同步

技术领域

本发明涉及计算指令的执行，且更确切地说，涉及并行执行的计算指令的同步。

背景技术

传统上，计算机程序已经被编写成连续程序，其中计算机程序的代码在单一常规处 理器上连续执行。然而，因为包含多个处理核心的专用处理器(例如图形处理单元(GPU)) 的性能不断快速增加，计算机程序越来越被编写成利用此类专用处理器。例如，计算机 程序被编写成包含数据平行代码，使得相同代码可跨越处理器的多个处理核心而执行以 对一组数据并行地操作。因为此数据平行代码被并行执行而不是连续执行，所以可能不 存在关于代码将完成处理所述组数据的次序的保证。因此，可能需要使并行执行同步以 确保多个处理核心已结束所述组数据上的操作，之后将数据的值用于任何进一步操作 中。

发明内容

一般来说，本发明描述用于使用动态壁垒宽度计算使并行处理的计算指令同步的技 术。线程块可各自对一组数据执行相同组指令，且壁垒操作可用于在线程对所述组数据 执行相应的写入操作之后且在线程对所述组数据执行相应的读取操作之前使所述线程 块同步，以防止读取操作读取不正确或无效的数据。默认地，壁垒操作可使线程块中的 所有线程同步，使得没有线程可在壁垒操作之后执行读取操作，除非所述块中的每一及 每个线程已执行相应的壁垒操作。相比而言，本文中揭示的技术可包含用于动态地计算 壁垒操作的宽度的技术，使得块的线程的子集可在执行相应的壁垒操作之后进行到执行 读取操作，即使所述块中的其它线程尚未执行它们的壁垒操作也如此。

在一个实例中，一种用于使线程同步的方法包含在主机上执行的包含将由可操作地 耦合到主机的处理单元执行的数据并行代码的应用的运行时间确定各自执行所述数据 并行代码的群组线程的壁垒操作的壁垒宽度，其中所述壁垒宽度小于所述线程群组中的 线程的总数，且其中所述线程群组中的线程在处理单元的一或多个计算单元上执行所述 数据并行代码。所述方法进一步包含响应于所述线程群组的子群组中的每一线程已执行 相应的壁垒操作，所述子群组包含与所确定的壁垒宽度相同数目的线程，使得所述线程 群组的所述子群组能够在所述相应的壁垒操作之后在所述一或多个计算单元上执行相 应的操作而无需等待所述线程群组中的其它线程执行壁垒操作，其中所述线程群组的所 述子群组小于所述线程群组中的线程的所述总数。

在另一实例中，一种计算系统包含用于使线程同步的计算系统。所述计算系统包含 主机。所述计算系统进一步包含可操作地耦合到所述主机的处理单元。所述计算系统进 一步包含定序器模块，所述定序器模块经配置以：在所述主机上执行的包含将由所述处 理单元执行的数据并行代码的应用的运行时间确定各自在所述处理单元的一或多个计 算单元上执行所述数据并行代码的群组线程的壁垒操作的壁垒宽度，其中所述壁垒宽度 小于所述线程群组中的线程的总数；及响应于所述线程群组的子群组中的每一线程已执 行相应的壁垒操作，所述子群组包含与所确定的壁垒宽度相同数目的线程，使得所述线 程群组的所述子群组能够在所述相应的壁垒操作之后在所述一或多个计算单元上执行 相应的操作而无需等待所述线程群组中的其它线程执行壁垒操作，其中所述线程群组的 所述子群组小于所述线程群组中的线程的所述总数。

在另一实例中，一种并行处理设备包含用于以下操作的装置：在主机上执行的包含 将由可操作地耦合到所述主机的处理单元执行的数据并行代码的应用的运行时间确定 各自在所述处理单元的一或多个计算单元上执行所述数据并行代码的群组线程的壁垒 操作的壁垒宽度，其中所述壁垒宽度小于所述线程群组中的线程的总数。所述并行处理 设备进一步包含响应于所述线程群组的子群组中的每一线程已执行相应的壁垒操作，所 述子群组包含与所确定的壁垒宽度相同数目的线程，用于以下操作的装置：使得所述线 程群组的所述子群组能够在所述相应的壁垒操作之后在所述一或多个计算单元上执行 相应的操作而无需等待所述线程群组中的其它线程执行壁垒操作，其中所述线程群组的 所述子群组小于所述线程群组中的线程的所述总数。

在另一实例中，一种计算机可读存储媒体可含有指令，所述指令在由至少一个处理 器执行时致使所述至少一个处理器执行操作。所述操作包含：在主机上执行的包含将由 可操作地耦合到所述主机的处理单元执行的数据并行代码的应用的运行时间确定各自 执行所述数据并行代码的群组线程的壁垒操作的壁垒宽度，其中所述壁垒宽度小于所述 线程群组中的线程的总数，且其中所述线程群组中的线程在所述处理单元的一或多个计 算单元上执行所述数据并行代码。所述操作进一步包含响应于所述线程群组的子群组中 的每一线程已执行相应的壁垒操作，所述子群组包含与所确定的壁垒宽度相同数目的线 程，使得所述线程群组的所述子群组能够在所述相应的壁垒操作之后在所述一或多个计 算单元上执行相应的操作而无需等待所述线程群组中的其它线程执行壁垒操作，其中所 述线程群组的所述子群组小于所述线程群组中的线程的所述总数。

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

附图说明

图1是说明根据本发明的一些方面的线程的同步的概念图。

图2是说明根据本发明的一些方面的并行处理计算系统的框图。

图3是说明根据本发明的一些方面的使用动态壁垒宽度使线程同步的概念图。

图4是说明根据本发明的一些方面的实例并行缩减的概念图。

图5是说明根据本发明的一些方面的使用动态壁垒使线程同步的实例过程的流程 图。

图6是说明可经配置以实施本发明的一或多个方面的装置的实例的框图。

具体实施方式

一般来说，本发明描述用于使用动态壁垒宽度计算使并行处理的计算指令同步的技 术。在数据并行处理中，计算机程序可包含数据并行代码。数据并行代码是可经由多个 执行线程在多个处理元件上同时运行的一组计算指令，使得可执行相同组计算指令以对 多个不同数据点并行地执行相同操作。在多个数据点中的一者上操作的相同数据并行代 码的每一个别调用是线程，且线程可同时执行以执行多个数据点上的相同指令。通常， 数据并行代码可包含写入一组数据的写入操作以及在写入操作之后读取由写入操作写 入的所述组数据的读取操作。然而，不是执行的每个线程可同时完成写入操作的执行。 如果在每一线程已完成写入到所述组数据的写入操作之前执行读取一组数据的读取操 作，那么所述读取操作可读取不正确或无效的结果。为确保读取操作不读取不正确或无 效的结果，可要求每一线程在对所述组数据执行数据并行写入操作之后在进行到对所述 组数据执行读取操作之前执行壁垒操作，且可不允许用于执行数据并行代码的线程在执 行壁垒操作之后进行执行所述读取操作，直到所有线程也已执行所述壁垒操作为止。

图1是说明根据本发明的一些方面的线程的同步的概念图。如图1中所示，线程102、 104、106及108可并行执行数据并行代码以各自对一组数据执行写入操作，且随后各自 对所述组数据执行读取操作。在时间t1处，线程106已结束其写入操作且到达壁垒操作 110。壁垒操作110指示线程106已完成其写入操作的执行。然而，因为不是每个线程 都已到达壁垒操作(即，线程102、104及108尚未完成相应的写入操作的执行)，所以线 程106必须等待，直到其它线程102、104及108也已到达壁垒操作为止，之后进行到 执行读取所述组数据的读取操作。在时间t2处，线程102到达壁垒操作112，因为线程 102已完成执行其写入操作。类似于线程106，因为线程104及108还尚未到达壁垒操 作，所以线程102必须也等待，直到线程104及108也已到达壁垒操作，之后进行到执 行读取所述组数据的读取操作。在时间t3处，线程104到达壁垒操作114。类似于线程 102及106，因为线程108还尚未到达壁垒操作，所以线程104必须也等待，直到线程 108也已到达壁垒操作，之后进行到执行读取所述组数据的读取操作。在时间t4处，线 程108到达壁垒操作116。因为所述线程群组中的每个线程102、104、106及108已到 达壁垒操作，所以线程102、104、106及108中的每一者现在各自允许执行读取所述组 数据的读取操作。

然而，在允许群组中的线程进行之前要求线程群组中的线程等待所述线程群组中的 每个线程都到达壁垒操作的壁垒操作可为低效的。例如，在执行写入之后执行的读取操 作可仅取决于结束其写入操作的相应执行的一些线程(而不是全部)。因此，即使所有线 程取决于额外操作已到达壁垒操作，但那些线程不可执行其相应的读取操作，直到群组 中的每个线程都已结束其相应的写入操作且到达壁垒操作为止。

以下展示以C语言编写的实例代码片段，其展示壁垒操作的此用途：

如以上代码片段中所展示，壁垒操作是在执行后续x＝ptr[thread_id％32]读取操作之 前各自执行if(thread_id％32){ptr[thread_id％32]＝value；}写入操作的线程群组的同步 点，进而确保仅在群组中的每一线程已结束执行if(thread_id％32){ptr[thread_id％32]＝ value；}操作且已到达同步点之后从其读取ptr[thread_id％32]且x变量被指派 ptr[thread_id％32]的值。然而，因为thread_id％32将产生仅0到31的值，所以如果群组 包含多于32个线程，那么所述线程群组中的每个线程可没有必要在执行x＝ ptr[thread_id％32]操作之前一直等到每一线程已执行壁垒操作。而是，32个线程的群组 可仅需要等待确保x＝ptr[thread_id％32]操作将正确地操作。因此，如果所述线程群组包 含多于32个线程，壁垒操作可需要过度等待更多线程而不是必须确保x＝ ptr[thread_id％32]操作的完整性。

减少壁垒操作的低效率的一个方法可包含指定壁垒操作的宽度。壁垒操作的宽度可 为在允许线程在壁垒操作之后继续进行之前到达壁垒操作所需的线程的数目，且宽度可 通常被指定为少于所述线程群组中的线程的总数。例如，壁垒操作可采取宽度作为参数。 在另一实例中，所述宽度可被指定为常量。在编译时间，壁垒操作的宽度可被硬编码为 调用壁垒操作的计算机程序。对于以上实例代码片段，可在壁垒操作的编译时间处指定 32的宽度。

然而，在编译时间硬编码壁垒操作的宽度可限制壁垒操作的有用性及灵活性，因为 其可能不可用于其中在编译时间未知壁垒操作的所要宽度的情形。此外，编写数据并行 代码的程序员可不知晓指定的适当宽度。因此，可能需要在运行时间动态地计算壁垒操 作的宽度。

图2是说明根据本发明的一些方面的用于执行数据并行代码的并行处理计算系统的 框图。如图2中所展示，主机220可以可通信地耦合到处理单元202。处理单元202可 包含计算单元204A到204N(“计算单元204”)，且计算单元204中的每一者可包含处 理元件206A到206N(“处理元件206”)。

在一些实例中，主机220可为微处理器，例如中央处理单元(CPU)，其经配置以处 理计算机程序的指令以用于在并行处理计算系统内执行。在一些实例中，主机220可在 执行计算机程序期间在遇到数据并行代码之后将数据并行代码传送到处理单元202以用 于执行。

处理单元202可为图形处理单元(GPU)或经配置以处理计算机程序的指令中的至少 一些指令的任何其它合适的处理单元。处理单元202可以可操作地耦合到主机220且可 从主机220接收计算机程序的数据并行代码。处理单元202可包含一或多个可编程处理 器，例如计算单元204。计算单元204可各自包含处理元件206。计算单元204可各自 包含本地存储器(即，高速缓冲存储器)。处理元件206可为相应的计算单元204的处理 核心。例如，处理元件206可各自包含一或多个算术逻辑单元(ALU)或经配置以执行算 术及逻辑操作的其它电路。

在多个数据点中的一者上操作的相同数据并行代码的每一个别调用是线程，且线程 可同时执行以在多个数据点上执行相同指令。在一些实例中，线程还可被称为工作项。 处理单元202可将线程一起分组为块。通常，处理单元202可将由相同数据并行代码产 生的所有线程分组为一或多个块。在一些实例中，块还可被称为工作组。在一些实例中， 单一块中的所有线程可限制在计算单元204中的一者上执行。在一些实例中，线程的块 可为线程群组，其中如果壁垒操作的宽度未指定或确定小于群组中的线程的数目，那么 壁垒操作可应用于群组中的每一线程。因此，如果所述线程群组中的线程到达此壁垒， 那么线程可能必须等到所述群组中的每一线程也到达所述壁垒，之后才允许线程在壁垒 之后继续进行。

处理单元202可将块内的线程分组为一或多个翘曲或波前。波前是计算单元204的 调度的基本单元且可通常包含块中的线程的子集。例如，给定512个线程的块，波前可 包含32个线程，且所述块中的线程可被分组为512/32＝16个翘曲。波前可通常与单一计 算单元(即，计算单元204A)中的处理元件206一样多的线程，使得单一计算单元的处理 元件206可同时处理波前中的每个线程。

因为线程的波前对多个数据元素执行相同指令，所以主机220可将待由波前处理的 数据向量化为数据向量且可将所述向量传送到处理单元202。通常，数据被分组为具有 与单一波前中的线程一样多的元素的向量。换句话说，波前中的线程的数目与其操作的 数据的向量的宽度相同。因此，波前中的线程的数目可被称作波前的向量宽度。

如上文所论述，波前含有与单一计算单元中存在的处理元件206一样多的线程或比 其少的线程。因此，波前的所有线程可由单一计算单元的处理元件206同时平行执行， 因为波前中没有线程必须等待忙的处理单元完成处理相同波前中的另一线程。因此，可 保证单一波前的线程实质上并行执行，使得可不需要壁垒操作以使单一波前内的线程同 步。

计算单元204中的一者可使用计算单元204的处理元件206并行执行一或多个波前。 在执行块的线程时，壁垒操作可用于使所述块的线程同步。如上文所论述，壁垒操作可 操作以使得可需要块的线程一直等到块的所有线程已执行壁垒操作为止。

定序器208可经配置以管理及安排数据并行代码在计算单元204之间的执行。例如， 定序器208可安排线程的块及线程的波前在计算单元204上的执行。定序器208还可经 配置以使线程的块同步。例如，如果线程已执行壁垒操作且空闲，同时等待其块的另一 线程执行它们的相应的壁垒操作以允许等待的其它线程执行以由处理元件206处理，那 么定序器208可从处理元件206卸载那些线程。定序器208还可在确定块的线程已全部 执行壁垒操作之后将空闲线程重新加载回到处理元件206。

定序器208可动态地基于将由群组中的线程执行的数据并行代码而确定在众多数据 点上执行相同数据并行代码的线程群组的壁垒操作的宽度，其中所确定的宽度小于群组 中的线程的总数。在一些实例中，所述群组可为线程块。壁垒操作的宽度可为块中的必 须到达壁垒操作的线程的数目，之后才允许所述线程中的任一者在壁垒操作之后执行操 作。因为所确定的宽度小于所述群组中的线程的总数，所以定序器208可通过确定壁垒 宽度而允许所述群组的线程在壁垒操作之后执行操作，即使所述群组中不是每个线程都 已到达相应的壁垒操作也如此。

定序器208可基于在壁垒操作之前及/或在壁垒操作之后将由群组中的线程执行的 数据并行代码而确定线程群组的壁垒操作的宽度。例如，基于以上代码片段，定序器208 可确定数据并行代码将在壁垒操作之前写入到32ptr阵列位置，且数据并行代码将在壁 垒操作之后从32ptr阵列位置读取。因此，定序器可确定所述特定壁垒操作的32的壁 垒宽度。

在一个实例中，定序器208可将壁垒操作的动态地确定的壁垒宽度存储在一或多个 宽度寄存器中。响应于线程到达具有存储在宽度寄存器中的其壁垒宽度的壁垒操作，递 减一或多个宽度寄存器中的数目。响应于一或多个宽度寄存器中的数目到达零，可允许 在已到达壁垒操作之后等待的块中的任何线程继续执行。在另一实例中，定序器208可 包含存储指示壁垒操作的宽度的数目的宽度寄存器及存储等待块中的其它线程到达壁 垒的线程的数目的等待寄存器两者。响应于线程到达壁垒操作，递增等待寄存器中的数 目。响应于等待寄存器中的数目等于宽度寄存器中的数目，可允许在到达壁垒操作之后 等待的块中的任何线程继续执行。

在一些实例中，动态地确定壁垒宽度可使得含有数据并行代码的计算机程序的开发 者能够更容易地编写可跨越多种并行计算系统执行的跨平台数据并行代码。例如，一些 并行计算系统可保证单一波前中的每个线程可同时执行，使得如果壁垒的宽度小于波前 的向量宽度，那么壁垒操作是不必要的。例如，如果波前的向量宽度是16(例如因为计 算单元含有16个处理元件)，那么具有16或更小的壁垒宽度的壁垒操作可为不必要的。 然而，因为计算机程序员可能不知晓他的数据并行代码将确切在哪一并行计算系统上运 行，并且因此可能不知晓并行处理系统的计算单元含有多少处理元件，所以如果计算机 程序员硬编码小于特定并行计算系统的波前的向量宽度的壁垒宽度，那么所述数据并行 代码在所述特定并行计算系统上运行时可执行额外的壁垒操作且可减慢数据并行代码 的执行。相比而言，定序器208可针对所述特定并行计算系统确定壁垒操作的壁垒宽度 以及波前的向量宽度，且可在所确定的壁垒宽度小于数据并行代码在上面执行的并行计 算系统的波前的向量宽度的情况下确定不执行所述壁垒操作。在一些实例中，定序器208 可确定大于波前的向量宽度的壁垒宽度。

动态地计算壁垒宽度还可实现壁垒操作在动态控制流的条件语句中的使用，其中条 件语句不贯穿所述线程群组统一地进行评估。考虑以下伪码：

通常，对于线程群组，如果条件x<y在每个线程中都未评估为真，那么包含壁垒操 作以使得仅在条件x<y评估为真的情况下才执行其可导致群组中的线程的群组死锁，因 为其中x<y被评估为假的线程将永不执行壁垒操作。相比而言，在本发明中，定序器208 可例如通过针对所述组值x及y预先评估x<y而将壁垒的宽度动态地设定为等于x<y评 估为真的次数。因此，如果壁垒的宽度设定为四，那么有壁垒的线程可一旦四个线程已 执行壁垒操作便在壁垒之后继续而无需必须等待工作项的群组中的其余线程执行壁垒 操作。

定序器208还可确定壁垒操作的壁垒宽度以使线程子组一起同步，其中子组的线程 是块的连续线程。例如，给定十六个线程t₀、t₁,…,t₁₅的块，如果将线程的壁垒操作的 壁垒宽度指定为四，那么块t₀到t₃的前四个线程可一起同步，块t₄到t₇的第二四个线程 可一起同步，第三组四个线程t₈到t₁₁可一起同步，且第四组四个线程t₁₂到t₁₅可一起同 步。在此实例中，线程群组中的每一线程t₀到t₃可仅需要等待群组中的所有线程t₀到t₃执行壁垒操作，之后便能够进行其执行，线程群组中的每一线程t₄到t₇可仅需要等待群 组中的所有线程t₄到t₇执行壁垒操作，之后便能够进行其执行，线程群组中的每一线程 t₈到t₁₁可仅需要等待群组中的所有线程t₈到t₁₁执行壁垒操作，之后便能够进行其执行， 且线程群组中的每一线程t₁₂到t₁₅可仅需要等待群组中的所有线程t₁₂到t₁₅执行壁垒操 作，之后便能够进行其执行。因此，例如，如果线程t₁、t₈、t₂及t₃是到达壁垒操作的前 四个线程，那么线程t₁、t₂及t₃可需要等待线程t₄到达壁垒操作，之后才允许那些线程 t₁、t₂及t₃在壁垒操作之后继续执行，即使十六个线程的块中的四个线程已到达壁垒操 作也如此。

图3是说明根据本发明的一些方面的使用动态壁垒宽度使线程同步的概念图。如图 3中所展示，定序器(例如图2中展示的定序器208)可确定线程302及304可一起同步， 且线程306及308可一起同步。因此，定序器可确定用于可并行执行数据并行代码的线 程302、304、306及308的2的壁垒宽度。因此，线程302及304被分组为线程子群组， 且线程306及308可被分组为另一线程子群组。在时间t1处，线程306已结束执行其写 入操作且到达壁垒操作310。然而，因为不是其子群组中的每个线程都也已结束执行其 相应的写入操作且到达壁垒操作，所以线程306必须等待，直到子群组中的另一线程(即， 线程308)也已结束执行其写入操作且到达壁垒操作，之后才进行到执行在壁垒操作310 之后的读取操作。在时间t2处，线程302结束执行写入操作且到达壁垒操作312。类似 地，因为作为与线程302的子群组的另一成员的线程304还尚未完成执行写入操作且到 达壁垒操作，所以线程302必须还要等待，之后才进行到执行在壁垒操作312之后的代 码。在时间t3处，线程304到达壁垒操作314。因为线程302及304两者已到达壁垒操 作312及314，所以线程302及304可进行到执行在壁垒操作314之后的相应的读取操 作。在时间t4处，线程308到达壁垒操作316。因为线程306及308两者已到达壁垒操 作，所以现在允许线程306及308执行在其相应的壁垒操作之后的相应的读取操作。如 可在图3中看出，通过设定小于线程群组中的线程的总数的壁垒宽度，线程可能够快得 多地恢复在壁垒之后的执行。举例来说，由于不设定小于线程群组中的线程的总数的壁 垒宽度，线程302、304及306将在执行相应的壁垒操作310、312及314之后保持闲置， 直到线程308在比时间t1、t2及t3晚的时间t4处执行了壁垒操作316为止。

动态地确定壁垒操作的宽度可用于并行，尤其在将缩减的数目的集合的大小在运行 时间之前是未知时。减少是对数目的集合求和的技术，且并行缩减可为其中数据并行代 码可执行以对缩减的元素并行求和的缩减。图4是说明根据本发明的一些方面的实例并 行缩减的概念图。如图4中所展示，阵列402可包含将一起求和的八个数目的集合。执 行缩减的数据并行代码可执行以使得每一工作项对阵列402的两个连续元素一起求和。 因此，在并行缩减的第一遍次中，求和操作404A到404D(“求和操作404”)可经由四 个并行线程并行执行，从而各自对阵列402的元素中的两者求和，以将八元素阵列402 缩减为含有由求和操作404中的每一者产生的四个所得的和的四元素阵列406。

然而，因为集合的大小在运行时间可为未知的，所以程序员在编译时间可能不可能 知晓数据并行代码中的壁垒操作所需的确切壁垒宽度以执行并行缩减。例如，集合的大 小可取决于用户输入，使得用户可输入8个数目、20个数目，或任何其它组数目。在图 4中展示的特定实例中，定序器(例如图2中展示的定序器208)可基于阵列402的大小(8) 而确定用于将由四个线程在执行求和操作404之后执行的壁垒操作的4的壁垒宽度。

经由求和操作404的第一轮缩减可产生含有四个所得的元素的阵列406。为进一步 缩减阵列406的元素，可仅需要两个线程执行求和操作408A及408B(“求和操作408”)。 因此，定序器可基于阵列406的大小(4)而确定用于将由两个线程在执行求和操作408之 后执行的壁垒操作的2的壁垒宽度。

经由求和操作408的第二轮缩减可产生含有两个所得元素的阵列410。为进一步缩 减阵列410的元素，可仅需要单一线程执行求和操作412。因此，定序器可确定将不需 要执行壁垒操作。因此，定序器可确定在执行求和操作412之后忽略代码中指定的壁垒 操作。

用于执行求和缩减的数据并行代码通常被编写为循环，使得壁垒操作包含在循环 内。因此，如果将在编译时间设定壁垒操作的宽度，假设程序员知晓要缩减的集合中的 元素的初始数目，那么程序员可必须展开所述循环以将特定宽度的壁垒操作手动地插入 在每一组求和操作之后。相比而言，在当前实例中，合成器可动态地确定壁垒操作的每 一迭代的壁垒宽度。

图5是说明根据本发明的一些方面的使用动态壁垒使线程同步的实例过程的流程 图。如图5中所展示，定序器(例如图2中展示的定序器208)可在主机(例如图2中展示 的主机220)上执行的包含将由可操作地耦合到所述主机的处理单元(例如图2中展示的 处理单元202)执行的数据并行代码的计算机应用的运行时间动态地确定各自执行数据 并行代码的群组线程的壁垒操作的壁垒宽度，其中所述壁垒宽度小于所述线程群组中的 线程的总数(502)。在图5的实例中，所述线程群组可包含64个线程，且定序器可确定 32的壁垒宽度。因此，所述64个线程可包含各自为32个线程的两个子组，其中子群组 的线程与相同子群组的另一线程同步。在第一时间，所述线程群组的第一子群组的第一 线程可到达壁垒(504)且可等待第一子群组的其余线程也到达所述壁垒。在第二时间，所 述线程群组的第二子群组的第一线程可到达壁垒(506)且可等待第二子群组的其余线程 也到达所述壁垒。

在第三时间，第一子群组的所有线程可到达壁垒(508)。响应于所述线程群组的第一 子群组中的每一线程已执行相应的壁垒操作，所述第一子群组包含与所确定的壁垒宽度 相同数目的线程，定序器可使得所述线程群组的第一子群组能够在相应的壁垒操作之后 在一或多个计算单元上执行而无需等待所述线程群组中的其它线程执行壁垒操作，其中 所述线程群组的第一子群组小于所述线程群组中的线程的总数(510)。

在第四时间，第二子群组的所有线程可到达壁垒(512)。响应于所述线程群组的第二 子群组中的每一线程已执行相应的壁垒操作，所述第二子群组包含与所确定的壁垒宽度 相同数目的线程，定序器可使得所述线程群组的第二子群组能够在相应的壁垒操作之后 在一或多个计算单元上执行而无需等待所述线程群组中的其它线程执行壁垒操作，其中 所述线程群组的第二子群组小于所述线程群组中的线程的总数(514)。

在一些实例中，确定壁垒宽度可包含至少部分基于数据并行代码而确定壁垒操作的 壁垒宽度。在一些实例中，壁垒操作的壁垒宽度大于一或多个处理器的波前的向量宽度。 在一些实例中，定序器可进一步在壁垒操作的壁垒宽度小于一或多个处理器的波前的向 量宽度的情况下确定不执行壁垒操作。在一些实例中，壁垒操作包含在条件语句中，且 所述条件语句不贯穿所述线程群组统一地进行评估。在一些实例中，所述线程群组的子 群组中的线程是所述线程群组中的连续线程。在一些实例中，壁垒操作包含在循环中。 在一些实例中，定序器可为循环的每一迭代动态地确定壁垒操作的壁垒宽度，其中所确 定的壁垒宽度在循环的至少两个迭代中是不同的。

图6是说明可经配置以实施本发明的一或多个方面的装置的实例的框图。例如，图 6说明装置602。装置602的实例包含(但不限于)视频装置、媒体播放器、机顶盒、无线 手持机(例如移动电话以及所谓的智能电话)、个人数字助理(PDA)、桌上型计算机、膝上 型计算机、游戏控制台、视频会议单元、平板计算装置及类似者。

在图6的实例中，装置602可包含主机610、系统存储器618及处理单元620。主 机610可类似于图2中展示的主机220，且处理单元620可类似于图2中展示的处理单 元202。出于简洁的目的，不相对于图6进一步描述主机610、系统存储器618及处理 单元620。装置622还可包含显示处理器624、收发器模块626、用户接口628及显示器 630。收发器模块626及显示处理器624两者可为与主机610及/或处理单元620相同的 集成电路(IC)的部分、可两者在包含主机610及/或处理单元620的所述IC外部，或可 形成于在包含主机610及/或处理单元620的IC外部的IC中。

装置622可包含图6中出于清楚起见而未展示的额外模块或单元。例如，装置622 可包含扬声器及麦克风(其在图6中都未展示)以在其中装置622是移动无线电话的实例 中实现电话通信，或在其中装置622是媒体播放器的实例中实现扬声器。装置622还可 包含摄像机。此外，装置622中展示的各种模块及单元可能没有必要在装置622的每个 实例中。例如，用户接口628及显示器630可在其中装置622是桌上型计算机或经装备 以与外部用户接口或显示器介接的其它装置的实例中在装置622的外部。

用户接口628的实例包含(但不限于)跟踪球、鼠标、键盘和其它类型的输入装置。 用户接口628还可为触摸屏且可作为显示器630的一部分而并入。收发器模块626可包 含用以允许装置622与另一装置或网络之间的无线或有线通信的电路。收发器模块626 可包含调制器、解调器、放大器和用于有线或无线通信的其它此类电路。

在一些实例中，处理单元620可为可将完全形成的图像存储在系统存储器618中的 GPU。显示处理器624可从系统存储器618检索图像且输出致使显示器630的像素照明 以显示图像的值。显示器630可为装置622的显示由处理单元620产生的图像内容的显 示器。显示器630可为液晶显示器(LCD)、有机发光二极管显示器(OLED)、阴极射线管 (CRT)显示器、等离子显示器，或另一类型的显示装置。

在一或多个实例中，所描述的功能可实施在硬件、软件、固件或其任何组合中。如 果实施于软件中，则可将所述功能作为一或多个指令或代码而存储在计算机可读媒体上 或经由计算机可读媒体发射。计算机可读媒体可包含计算机数据存储媒体。数据存储媒 体可为可由一或多个计算机或一个或多个处理器存取以检索用于实施本发明中描述的 技术的指令、代码及/或数据结构的任何可用媒体。借助于实例而非限制，此类计算机可 读媒体可包括RAM、ROM、EEPROM、CD-ROM或其它光盘存储装置、磁盘存储装置 或其它磁性存储装置，或可以用于运载或存储呈指令或数据结构的形式的所要程序代码 且可以由计算机存取的任何其它媒体。存储在数据存储媒体上的软件可使用同轴电缆、 光纤电缆、双绞线、数字订户线(DSL)或例如红外线、无线电及微波等无线技术从网站、 服务器或其它远程源传输，于是所述同轴电缆、光纤电缆、双绞线、DSL或例如红外线、 无线电及微波等无线技术包含在媒体的定义中。如本文中所使用，磁盘和光盘包含压缩 光盘(CD)、激光光盘、光学光盘、数字多功能光盘(DVD)、软性磁盘和蓝光光盘，其中 磁盘通常以磁性方式再现数据，而光盘利用激光以光学方式再现数据。以上各者的组合 也应该包含在计算机可读媒体的范围内。

代码可以由一或多个处理器执行，所述一或多个处理器例如是一或多个数字信号处 理器(DSP)、通用微处理器、专用集成电路(ASIC)、现场可编程逻辑阵列(FPGA)或其它 等效的集成或离散逻辑电路。因此，如本文中所使用的术语“处理器”可指代上述结构 或适合于实施本文中所描述的技术的任何其它结构中的任一者。另外，在一些方面中， 可在专用硬件和/或软件模块内提供本文中所描述的功能性。另外，可以将所述技术完全 实施于一或多个电路或逻辑元件中。

本发明的技术可在广泛多种装置或设备中实施，包含无线手持机、集成电路(IC)或 一组IC(即，芯片组)。本发明中描述各种组件、模块或单元是为了强调经配置以执行所 揭示的技术的装置的功能方面，但未必需要通过不同硬件单元实现。实际上，如上文所 描述，各种单元可以结合合适的软件及/或固件组合在编码解码器硬件单元中，或者通过 互操作硬件单元的集合来提供，所述硬件单元包含如上文所描述的一或多个处理器。

描述了各种实例。这些和其它实例属于所附权利要求书的范围内。