CN108139931A - 通过重映射同步来加速任务子图 - Google Patents

Abstract

各实施例包括用于加速执行属于共同属性任务图的多个任务的计算设备、装置和计算设备实现的方法。计算设备可以识别第一后继任务，该第一后继任务是依赖于已捆绑任务的，使得可用同步机制是已捆绑任务和第一后继任务的共同属性，并且使得第一后继任务仅依赖于可用同步机制是其共同属性的前驱任务。计算设备可以将第一后继任务添加到共同属性任务图，并且将属于共同属性任务图的多个任务添加到就绪队列。计算设备可以递归地识别后继任务。同步机制可以包括用于控制逻辑流的同步机制和用于数据访问的同步机制。

Description

通过重映射同步来加速任务子图

背景技术

构建响应的、高性能的且功率高效的应用对于传递令人满意的用户体验是关键的。任务并行编程模型被广泛地用于开发这样的应用。在该模型中，计算被封装在被称为“任务”的异步单元中，其中任务通过“依赖性”来相互间进行协调或同步。任务可以在不同类型的计算设备(诸如中央处理单元(CPU)、图形处理单元(GPU)或数字信号处理器(DSP))上封装计算。任务并行编程模型的能力和依赖性的概念是它们一起抽象出特定于设备的计算和同步原语，并且在通用任务和依赖性方面简化了算法的表达。

发明内容

各个实施例的方法和装置提供了用于在计算设备上加速执行属于共同属性任务图的多个任务的电路和方法。各个实施例可以包括：识别第一后继任务，所述第一后继任务依赖于已捆绑任务，使得可用同步机制是所述已捆绑任务和所述第一后继任务的共同属性，并且使得所述第一后继任务仅依赖于所述可用同步机制是其共同属性的前驱任务，将所述第一后继任务添加到共同属性任务图，以及将属于所述共同属性任务图的所述多个任务添加到就绪队列。

一些实施例还可以包括：针对所述可用同步机制来查询所述计算设备的组件。

一些实施例还可以包括：创建用于包括属于所述共同属性任务图的所述多个任务的捆绑，其中，所述可用同步机制是所述多个任务中的每个任务的共同属性，并且其中，所述多个任务中的每个任务依赖于所述已捆绑任务，并且将所述已捆绑任务添加到所述捆绑。

一些实施例还可以包括：将所述捆绑的层级变量设置为针对所述已捆绑任务的第一值，将所述捆绑的所述层级变量修改为针对所述第一后继任务的第二值，确定所述第一后继任务是否具有第二后继任务，以及响应于确定所述第一后继任务不具有第二后继任务，将所述层级变量设置为所述第一值，其中，将属于所述共同属性任务图的所述多个任务添加到就绪队列可以包括：响应于所述层级变量被响应于确定所述第一后继任务不具有第二后继任务而设置为所述第一值，将属于所述共同属性任务图的所述多个任务添加到所述就绪队列。

在一些实施例中，识别所述已捆绑任务的第一后继任务可以包括：确定所述已捆绑任务是否具有第一后继任务，以及响应于确定所述已捆绑任务具有所述第一后继任务，确定所述第一后继任务是否具有作为与所述已捆绑任务的共同属性的所述可用同步机制。

在一些实施例中，识别所述已捆绑任务的第一后继任务可以包括：响应于确定所述第一后继任务具有作为与所述已捆绑任务的共同属性的所述可用同步机制，删除所述第一后继任务对所述已捆绑任务的依赖性，以及确定所述第一后继任务是否具有前驱任务。

在一些实施例中，对所述已捆绑任务的第一后继任务的识别是递归地执行的，直到确定所述已捆绑任务不具有其它后继任务为止，以及将属于所述共同属性任务图的所述多个任务添加到就绪队列可以包括：响应于确定所述已捆绑任务不具有其它后继任务，将属于所述共同属性任务图的所述多个任务添加到所述就绪队列。

各个实施例可以包括一种计算设备，所述计算设备具有存储器和通信地连接到彼此的多个处理器，所述多个处理器包括第一处理器，所述第一处理器被配置有用于执行上文描述的实施例方法中的一种或多种实施例方法的操作的处理器可执行指令。

各个实施例可以包括一种计算设备，所述计算设备具有用于执行上文描述的实施例方法中的一种或多种实施例方法的功能的单元。

各个实施例可以包括一种其上存储有处理器可执行指令的非暂时性处理器可读存储介质，所述处理器可执行指令被配置为使得计算设备的处理器执行上文描述的实施例方法中的一种或多种实施例方法的操作。

附图说明

并入本文并构成本说明书的一部分的附图示出了各个实施例中的示例性实施例，并且与上文给出的总体描述和下文给出的详细描述一起用于说明权利要求的特征。

图1是示出了适用于实现一个实施例的计算设备的组件框图。

图2是示出了适用于实现一个实施例的示例性多内核处理器的组件框图。

图3是示出了根据一个实施例的、包括共同属性任务图的示例性任务图的示意图。

图4是示出了在不使用共同属性任务重映射同步的情况下进行的任务执行的示例的过程流和信令图。

图5是示出了根据一个实施例的、使用共同属性任务重映射同步进行的任务执行的示例的过程流和信令图。

图6是示出了用于任务执行的实施例方法的过程流图。

图7是示出了用于任务调度的实施例方法的过程流图。

图8是示出了用于共同属性任务重映射同步的实施例方法的过程流图。

图9是示出了用于共同属性任务重映射同步的实施例方法的过程流图。

图10是示出了适用于与各个实施例一起使用的示例性移动计算设备的组件框图。

图11是示出了适用于与各个实施例一起使用的示例性移动计算设备的组件框图。

图12是示出了适用于与各个实施例一起使用的示例性服务器的组件框图。

具体实施方式

将参照附图对各个实施例进行详细描述。只要可能的话，遍及附图将使用相同的附图标记来指代相同或相似的部分。对特定示例和实现方式的引用是出于说明性目的，并不旨在限制本权利要求的范围。

术语“计算设备”和“移动计算设备”在本文中可互换地使用，以指代蜂窝电话、智能电话、个人或移动多媒体播放器、个人数字助理(PDA)、膝上型计算机、平板计算机、可转换膝上型计算机/平板计算机(2合1计算机)、智能本、超级本、上网本、掌上型计算机、无线电子邮件接收机、支持多媒体互联网的蜂窝电话、移动游戏控制台、无线游戏控制器、以及包括存储器和多内核可编程处理器的类似个人电子设备。虽然各个实施例对于具有有限的存储器和电池资源的移动计算设备(例如智能电话)特别有用，但是这些实施例通常在实现多个存储器设备和有限功率预算的任何电子设备中是有用的，其中降低功率处理器的消耗可以延长移动计算设备的电池操作时间。术语“计算设备”还可以指代静止的计算设备，包括个人计算机、台式计算机、一体化计算机、工作站、超级计算机、大型计算机、嵌入式计算机、服务器、家庭影院计算机和游戏控制台。

实施例包括方法以及实现这些方法的系统和设备，所述方法用于通过使用对共同属性任务图同步进行重映射以利用特定于设备的同步机制，来提供并行任务的高效同步，以改善设备性能。方法、系统和设备可以识别共同属性任务图，以用于使用特定于设备的同步机制来重映射同步，并且基于特定于设备的同步机制和现有任务同步来针对共同属性任务图重映射同步。使用特定于设备的同步机制来重映射同步可以包括：确保依赖方任务仅依赖于可用同步机制是其共同属性的前驱任务。依赖方任务是在执行可以开始之前要求一个或多个前驱任务的结果或完成的任务(即，依赖方任务的执行依赖于至少一个前驱任务的结果或完成)。

先前的任务调度通常涉及在特定类型的设备(例如，中央处理单元(CPU))上执行的调度器，以实现任务间依赖性并且由此调度任务图，其中，任务可以在多种类型的设备(诸如CPU、图形处理单元(GPU)或数字信号处理器(DSP))上执行。当确定任务准备好执行时，调度器可以将任务调度到适当的设备(例如，GPU)。当GPU完成对任务的执行时，CPU上的调度器被通知并且采取动作来调度依赖方任务。这种调度经常涉及在各种类型的设备之间的频繁往返，仅是为了调度和同步对任务图中的任务的执行，从而导致并非最佳(在性能、能量等方面)的任务图执行。先前的任务调度没有考虑每种类型的设备(例如，GPU或DSP)可以具有用于实现任务间依赖性的更优化的手段的事实。例如，GPU包括具有先进先出(FIFO)保证的硬件命令队列。可以通过将同步从抽象任务互依赖性的域重新映射到特定于设备的同步的域来高效地实现通过任务互依赖性表达的任务的同步。可以作出关于特定于设备的同步机制是否存在的确定，所述特定于设备的同步机制可以被实现用于帮助确定是否以及如何重映射任务同步。可以作出对设备中的一些或全部设备的查询，以确定可用同步机制。例如，GPU可以报告硬件命令队列，GPU-DSP可以报告跨越两者的中断驱动信令等。

所查询的同步机制可以被转换成任务图的属性。任务共同属性任务图中的所有任务可以通过属性而相关。总体任务图中的一些任务可以是CPU任务、GPU任务、DSP任务、或者具有GPU、DSP等上的特殊实现的多版本任务。基于任务的任务属性和其同步，共同属性任务图可以被识别用于重映射同步。图3中的示例示出了具有共同属性任务图的任务图，所述共同属性任务图包括具有CPU任务属性或GPU任务属性的任务。当具有特定任务属性的任务就绪时，该任务被添加到任务捆绑数据结构。具有相同属性的后继任务被考虑用于调度，并且当后继任务变为就绪时，这些任务被添加到相同的任务捆绑。当最后一个后继任务被添加到任务捆绑时，任务捆绑中的所有任务被认为是服从重映射同步的。

为了针对共同属性任务图来重映射同步，可以作出关于更高效的同步机制在针对任务捆绑中的任务的任务属性的执行平台上是否是可用的。响应于识别是可用的更高效的同步机制，可以将共同属性任务图中的每个依赖性变换成更高效的同步机制的相应的同步原语。在重映射共同属性任务图中的所有依赖性之后，可以将共同属性任务图中的所有任务分发给适当的处理器(例如，GPU或DSP)进行执行。

在执行共同属性任务图之前，可以识别和获取用于执行共同属性任务图的任务所要求的所有资源(诸如存储器缓冲器)，并且在完成要求资源的任务时将其释放。在执行共同属性任务图期间，可以发送任务完成信号，以向在共同属性任务图外面的依赖方任务通知完成该依赖方任务所依赖的任务。是否在完成任务之后但在完成共同属性任务图之前发送任务完成信号可以依赖于在共同属性任务图外面的依赖方任务的依赖性和关键性。

各个实施例提供对计算设备的操作的多种改进。计算设备可以经历改进的处理速度性能，这是因为将在共同设备上和/或使用共同资源一起执行的任务捆绑减少了用于跨越不同的设备和资源来同步依赖方任务的开销。此外，不同类型的处理器(诸如CPU和GPU)能够更高效地并行操作，这是因为指派给每个处理器的任务不再如此地依赖于彼此。计算设备可以经历改进的功率性能，这是因为使由于将任务合并到共同处理器而不被使用的处理器空闲的能力以及用于同步任务的共享总线上的减小的通信开销。本文公开的各个实施例还提供了计算设备在不具有高级调度框架的情况下可以将任务图映射到特定处理器所采用的方式。

图1示出了包括适于与各个实施例一起使用的、与远程计算设备50相通信的计算设备10的系统。计算设备10可以包括具有处理器14、存储器16、通信接口18和存储内存接口20的片上系统(SoC)12。计算设备还可以包括通信组件22(诸如有线或无线调制解调器)、存储内存(storage memory)24、用于建立到无线网络30的无线连接32的天线26、和/或用于将有线连接44连接到互联网40的网络接口28。处理器14可以包括多种多样的硬件内核中的任何硬件内核，例如，多个处理器内核。

本文使用术语“片上系统”(SoC)来指代一组互连的电子电路，通常但不排他性地包括硬件内核、存储器和通信接口。硬件内核可以包括各种不同类型的处理器，诸如通用处理器、中央处理单元(CPU)、数字信号处理器(DSP)、图形处理单元(GPU)，加速处理单元(APU)、辅助处理器、单内核处理器和多内核处理器。硬件内核还可以体现其它硬件和硬件组合，诸如现场可编程门阵列(FPGA)、专用集成电路(ASIC)、其它可编程逻辑电路、离散门逻辑、晶体管逻辑、性能监视硬件，看门狗硬件和时间参考。集成电路可以被配置为使得集成电路的组件驻留在单片半导体材料(例如硅)上。SoC 12可以包括一个或多个处理器14。计算设备10可以包括一个以上SoC 12，从而增加处理器14和处理器内核的数量。计算设备10还可以包括不与SoC 12相关联的处理器14。各个处理器14可以是如下文参照图2所描述的多内核处理器。处理器14可以各自被配置用于可以与计算设备10的其它处理器14相同或不同的特定目的。处理器14中的一个或多个处理器14和相同或不同配置的处理器内核可以被归组在一起。一组处理器14或处理器内核可以被称为多处理器群集。

SoC 12的存储器16可以是易失性或非易失性存储器，其被配置用于存储用于由处理器14存取的数据和处理器可执行代码。计算设备10和/或SoC12可以包括被配置用于各种目的的一个或多个存储器16。在一个实施例中，一个或多个存储器16可以包括易失性存储器，诸如随机存取存储器(RAM)或主存储器、或高速缓存存储器。这些存储器16可以被配置为暂时地保存有限量的从数据传输器或子系统接收的数据、从非易失性存储器请求的、基于各种因素从非易失性存储器加载到存储器16以期望将来访问的数据和/或处理器可执行代码指令、和/或由处理器14产生的并且暂时地存储以用于将来快速访问而不被存储在非易失性存储器中的中间处理数据和/或处理器可执行代码指令。

存储器16可以被配置为至少暂时地存储从另一个存储器设备(诸如另一个存储器16或存储内存24)加载到存储器16的数据和处理器可执行代码，以用于由处理器14中的一个或多个处理器14访问。加载到存储器16的数据或处理器可执行代码可以是响应于处理器14执行功能来加载的。响应于执行功能来向存储器16加载数据或处理器可执行代码可以是从针对存储器16的、不成功或丢失的存储器访问请求导致的，这是因为所请求的数据或处理器可执行代码不位于存储器16中。响应于丢失，可以作出针对另一个存储器16或存储内存24的存储器访问请求，以从另一个存储器16或存储内存24向存储器设备16加载所请求的数据或处理器可执行代码。响应于执行功能来向存储器16加载数据或处理器可执行代码可以是从针对另一个存储器16或存储内存24的存储器访问请求导致的，并且数据或处理器可执行代码可以被加载到存储器16以用于稍后访问。

在一个实施例中，存储器16可以被配置为至少暂时地存储从原始数据源设备(诸如传感器或子系统)加载到存储器16的原始数据。原始数据可以从原始数据源设备流传输到存储器16并且被存储器存储，直到原始数据可以被机器学习加速器接收和处理为止，如本文参照图3-19进一步论述的。

通信接口18、通信组件22、天线26、和/或网络接口28可以一致地工作，以使得计算设备10通过无线网络30经由无线连接32和/或有线网络44与远程计算设备50进行通信。无线网络30可以使用多种无线通信技术来实现，包括例如用于无线通信的射频频谱，以提供计算设备10与互联网40的连接，通过该连接其可以与远程计算设备50交换数据。

存储内存接口20和存储内存24可以一致地工作，以允许计算设备10将数据和处理器可执行代码存储在非易失性存储介质上。存储组件24可以被配置成很像存储器16的实施例，其中，存储内存24可以存储数据或处理器可执行代码，以用于处理器14中的一个或多个处理器14访问。即使在计算设备10的电源已被切断之后，作为非易失性的存储内存24也可以保存信息。当电源再次接通并且计算设备10重新启动时，存储在存储内存24上的信息对于计算设备10来说可以是可用的。存储内存接口20可以控制对存储内存24的存取，并允许处理器14从存储内存24读取数据和向存储内存24写入数据。

计算设备10的组件中的一些或全部可以被不同地布置和/或组合，同时仍供应必须的功能。此外，计算设备10可以不限于这些组件中的每个组件中的一个组件，并且每个组件的多个实例可以被包括在计算设备10的各种配置中。

图2示出了适用于实现一个实施例的多内核处理器14。多内核处理器14可以具有多个同构或异构的处理器内核200、201、202、203。处理器内核200、201、202、203可以是同构的，因为单个处理器14的处理器内核200、201、202、203可以被配置用于相同的目的，并且具有相同或相似的性能特性。例如，处理器14可以是通用处理器，并且处理器内核200、201、202、203可以是同构的通用处理器内核。替代地，处理器14可以是图形处理单元或数字信号处理器，并且处理器内核200、201、202、203可以分别是同构的图形处理器内核或数字信号处理器内核。为便于参考，可以在本文中可互换地使用术语“处理器”和“处理器内核”。

处理器内核200、201、202、203可以是异构的，因为单个处理器14的处理器内核200、201、202、203可以被配置用于不同的目的和/或具有不同的性能特性。这样的异构处理器内核的异构性可以包括不同的指令集架构、管线、工作频率等。这样的异构处理器内核的示例可以包括被称为“big.LITTLE”架构的处理器内核，在该架构中，较慢的、低功率处理器内核可以与较强大和耗电(power-hungry)的处理器内核相耦合。在类似的实施例中，SoC12可以包括多个同构或异构处理器14。

在图2中示出的示例中，多内核处理器14包括四个处理器内核200、201、202、203(即，处理器内核0、处理器内核1、处理器内核2和处理器内核3)。为了便于说明，本文的示例可以指代图2中示出的四个处理器内核200、201、202、203。然而，在图2中所示出和本文所描述的四个处理器内核200、201、202、203仅仅作为示例来提供，无论如何并不意味着将各个实施例限制于四内核处理器系统。计算设备10、SoC 12或多内核处理器14可以单独或组合地包括比本文示出和描述的四个处理器内核200、201、202、203更少或更多。

图3示出了根据一个实施例的、包括共同属性任务图302的示例性任务图300。共同属性任务图可以包括共享共同属性以用于利用单个进入点执行的一组任务。共同属性可以包括控制逻辑流的共同属性或数据访问的共同属性。控制逻辑流的共同属性可以包括可由相同的硬件使用相同的同步机制执行的任务。例如，仅CPU可执行任务(CPU任务)304a-304e或仅GPU可执行任务(GPU任务)306a-306e可以表示两组不同的任务，这两组不同的任务基于使用相同同步机制的相同硬件来共享控制逻辑流的共同属性。在一个示例中，在CPU任务304c完成执行之前，GPU任务306a可以变为就绪任务并且可以被调度给GPU，这阻止GPU任务306b变为就绪任务。因此，GPU任务306a可以在GPU任务306b-306e之前被调度，这将GPU任务306a从共同属性任务图302中排除。在另外的示例中，GPU任务306b-306e可以要求与GPU任务306a相比不同的同步机制，例如，用于基于不同的应用编程接口(API)的编程语言的任务的不同的缓冲器，诸如用于基于OpenCL的编程语言的缓冲器和基于OpenGL的编程语言的缓冲器。因此，可以将GPU任务306a从共同属性任务图302中排除。数据访问的共同属性可以包括多个任务对相同的数据存储设备的访问，并且还可以包括对数据存储设备的访问的类型。例如，共同属性任务图的任务可以全部要求对相同的数据缓冲器的访问，并且它们在访问相同的数据存储设备时可以被归组在一起以用于由相同的硬件执行。在另外的示例中，要求只读访问的任务可以与要求读取/写入访问的任务归组在分离的共同属性任务图中。共同属性任务图还可以是由共同属性任务图中的单个进入点定义的，所述共同属性任务图可以包括共同属性任务图的所有其它任务所依赖的并且不依赖于在共同属性任务图外面的任何任务的任务。共同属性任务图可以具有多个退出依赖性，使得在共同属性任务图外面的任务可以依赖于共同属性任务图的各种任务。

在图3中示出的示例中，CPU任务304a-304e和GPU任务306a-306e可以通过依赖性彼此相关，由连接个体任务304a-304e、306a-306e的箭头示出的。在任务304a-304e、306a-306e当中，计算设备可以识别包括可以仅GPU执行的GPU任务306b-306e的共同属性任务图302。对于共同属性任务图302，进入点可以是GPU任务306b，其中，GPU任务306b是GPU任务306b-306e中的、唯一一个依赖于CPU任务304a-304e(例如，CPU任务304c)的GPU任务。在该示例中，共同属性任务图302还包括GPU任务306c和GPU任务306d，它们依赖于GPU任务306b但是不依赖于彼此，并且GPU任务306e依赖于GPU任务306c和GPU任务306d。此外，GPU任务306c可以包括退出依赖性，使得CPU任务304e依赖于GPU任务306c。如本文进一步详细描述的，参照图5和7-9，共同属性任务图302可以由GPU任务306b-306e的捆绑来表示，使得共同属性任务图302的所有GPU任务306b-306e可以被调度用于由相同的硬件和同步机制一起执行。

图4示出了在不使用共同属性任务重映射同步的情况下进行的任务执行的示例，如在现有技术下已知的。虽然任务并行编程模型提供了编程便利，但是其可以导致性能降级。任务并行程序的执行可以导致调度依赖方任务在不同的硬件上执行的乒乓效应，使得资源密集型通信必须在不同的硬件之间执行，以向调度器通知完成前驱任务。

使用参照图3描述的GPU任务306b-306e作为示例，GPU任务306b被CPU 400调度用于在GPU 402上执行404。一旦GPU任务306b变为就绪以进行执行(在任务调度中，当任务的所有前驱任务已经完成执行时，将该任务称为就绪)，就将其分发(406)给GPU 402。GPU 402执行408GPU任务306b。当GPU任务306b完成时，通知410 CPU 400。继而，CPU 400确定GPU任务306c和306d两者就绪，并且GPU任务306c和306d被调度用于在GPU 402上执行412、414，并且被分发(416)给GPU 402。GPU任务306c和306d均由GPU 402来执行418、422。向CPU 400通知420、424GPU任务306c和306d中的每个GPU任务的执行的完成。CPU 400确定GPU任务306e就绪，并且调度426GPU任务306e用于由GPU 402执行，并且将GPU任务306e分发428给GPU402。GPU任务306e由GPU 402来执行430，GPU 402向CPU 400通知完成432GPU任务306e的执行。该过程继续进行，直到整个任务图(在该示例中为包括GPU任务306b-306e的任务图)被处理为止。在CPU 400和GPU 402之间来回往返以调度任务用于GPU 402进行连续执行经常引入足以抵消通过将任务卸载到GPU 402获得的任何益处够的延迟。

图5示出了根据一个实施例的、使用共同属性任务重映射同步进行的任务执行的示例。使用参照图3描述的共同属性任务图302(包括GPU任务306b-306e)作为示例，GPU任务306b-306e全部可以被CPU 400调度用于在GPU 402上执行500-506。一旦GPU任务306b变为就绪以进行执行，就可以将GPU任务306b-306e分发508给GPU 402。GPU 402可以执行510-516GPU任务306b-306e，执行的顺序可以由GPU任务306b-306e之间的依赖性和它们如何被调度的来指定。当完成GPU任务306b-306e的执行时，可以向CPU 400通知518完成所有GPU任务306b-306e。

在各个实施例中，共同属性任务图302的GPU任务可以具有在共同属性任务图302外面的依赖性后继任务。例如，GPU任务306c可以具有依赖于GPU任务306c的后继任务，CPU任务304e。向CPU 400通知完成GPU任务306c可以发生在完成整个共同属性任务图302的结束处，如本文描述的。因此，CPU任务304e可以不被调度用于执行，直到完成共同属性任务图302为止。替代地，在完成前驱任务(例如GPU任务306c)之后，可以可选地向CPU 400通知520完成前驱任务，而不是等待完成共同属性任务图302。是否要实现这些各个实施例可以依赖于后继任务的关键性。后继任务越关键，通知就在时间上就越有可能离前驱任务的完成更近。关键性可以是对后继任务的执行的延迟可以如何增加任务图300的执行的延时的测量。后继任务对任务图300的延时的影响越大，后继任务就可以是越关键的。

图6示出了用于任务执行的实施例方法600。可以用处理器中执行的软件、用通用硬件或专用硬件来在计算设备中实现方法600。在各个实施例中，可以由多个处理器或硬件组件上的多个线程来实现方法600。在各个实施例中，可以与本文参照图7-9进一步描述的其它方法同时地实现方法600。

在确定框602中，计算设备可以确定就绪队列是否为空。就绪队列可以是由一个或多个处理器实现的逻辑队列，或者在通用或专用硬件中实现的队列。方法600可以使用多个就绪队列来实现；然而，为了简洁起见，对各个实施例的描述引用单个就绪队列。当就绪队列为空时，计算设备可以确定不存在就绪以用于执行的挂起任务。换句话说，要么不存在任务等待执行，要么存在任务等待执行，但是其依赖于尚未完成执行的前驱任务。当就绪队列填充有至少一个任务或者不为空时，计算设备可以确定存在不依赖于前驱任务或者不再等待前驱任务完成的任务等待执行。

响应于确定就绪队列为空(即，确定框602＝“是”)，在可选框604中，计算设备可以进入等待状态中。在各个实施例中，计算设备可以被触发退出等待状态并且在确定框602中确定就绪队列是否为空。在满足某一参数之后，诸如定时器到期，应用发起，或者处理器苏醒，或者响应于完成执行任务的信号，可以触发计算设备退出等待状态。在不实现可选框604的各个实施例中，计算设备可以在确定框602中确定就绪队列是否为空。

响应于确定就绪队列不为空(即，确定框602＝“否”)，在框606中，计算设备可以从就绪队列中移除就绪任务。在框608中，计算设备可以执行就绪任务。在各个实施例中，就绪任务可以由通过中止方法600以执行就绪任务并且在完成就绪任务之后恢复方法600、通过使用多线程能力，或者通过使用组件的可用部分(诸如多内核处理器的可用处理器内核)来执行方法600的相同组件来执行，。

在各个实施例中，实现方法600的组件可以将就绪队列提供给用于执行来自特定就绪队列的就绪任务的相关联的组件。在框610中，计算设备可以将已执行的任务添加到调度队列。在各个实施例中，调度队列可以是由一个或多个处理器实现的逻辑队列，或者在通用或专用硬件中实现的队列。方法600可以使用多个就绪队列来实现；然而，为了简洁起见，对各个实施例的描述引用单个就绪队列。

在框612中，计算设备可以通知或以其它方式提示组件检查调度队列。

图7示出了用于任务调度的实施例方法700。可以用处理器中执行的软件、用通用硬件或专用硬件来在计算设备中实现方法700。在各个实施例中，可以由多个处理器或硬件组件上的多个线程来实现方法700。在各个实施例中，可以与参照图6、8和9描述的其它方法同时地实现方法700。

在确定框702中，计算设备可以确定调度队列是否为空。如参照图6提及的，调度队列可以是由一个或多个处理器实现的逻辑队列，或者在通用或专用硬件中实现的队列。方法700可以使用多个就绪队列来实现；然而，为了简洁起见，对各个实施例的描述引用单个就绪队列。

响应于确定调度队列为空(即，确定框702＝“是”)，在可选框704中，计算设备可以进入等待状态中。在各个实施例中，计算设备可以被触发退出等待状态并且在确定框702中确定调度队列是否为空。在满足某一参数之后，诸如定时器到期，应用发起，或者处理器苏醒，或者信号(例如，参照图6描述的框612中的通知)，可以触发计算设备退出等待状态。在不实现可选框704的各个实施例中，计算设备可以在确定框702中确定调度队列是否为空。

响应于确定调度队列不为空(即，确定框702＝“否”)，在框706中，计算设备可以从调度队列中移除已执行的任务。

在确定框708中，计算设备可以确定从调度队列中移除的已执行的任务是否具有任何后继任务，即，依赖于已执行的任务的任务。已执行的任务的后继任务可以是直接依赖于已执行的任务的任何任务。计算设备可以对关于任务的依赖性和对任务的依赖性进行分析，以确定其与其它任务的关系。已执行的任务的后继任务自其前驱任务已被执行开始可以是就绪任务也可以不是就绪任务，因为这是取决于该后继任务是否具有尚未执行的其它前驱任务。

响应于确定已执行的任务不具有后继任务(即，确定框708＝“否”)，在确定框702中，计算设备可以确定调度队列是否为空。

响应于确定已执行的任务确实具有后继任务(即，确定框708＝“是”)，在框710中，计算设备可以获得作为已执行的任务的后继的任务(即，后继任务)。在各个实施例中，已执行的任务可以具有多个后继任务，并且可以针对后继任务中的每个后继任务并行或串行地执行方法700。

在框712中，计算设备可以删除已执行的任务和其后继任务之间的依赖性。作为删除已执行的任务和其后继任务之间的依赖性的结果，已执行的任务可以不再是后继任务的前驱任务。

在确定框714中，计算设备可以确定后继任务是否具有前驱任务。与在框708中识别后继任务类似，计算设备可以对任务之间的依赖性进行分析，以确定一个任务是否直接依赖于另一个任务，即，依赖方任务是否具有前驱任务。如上文提及的，已执行的任务可以不再是后继任务的前驱任务，因此，计算设备可以检查除了已执行的任务之外的前驱任务。

响应于确定后继任务确实具有前驱任务(即，确定框714＝“是”)，在确定框708中，计算设备可以确定从调度队列中移除的已执行的任务是否具有任何后继任务。

响应于确定后继任务不具有前驱任务(即，确定框714＝“否”)，在框716中，计算设备可以将后继任务添加到就绪队列。在各个实施例中，当后继任务不具有该后继任务在被实现之前必须等待其完成的任何前驱任务时，后继任务可以变为就绪任务。在框718中，设备可以通知或以其它方式提示组件检查就绪队列。

图8示出了用于共同属性任务重映射同步的实施例方法800。可以用处理器中执行的软件、用通用硬件或专用硬件来在计算设备中实现方法800。在各个实施例中，可以由多个处理器或硬件组件上的多个线程来实现方法800。在各个实施例中，可以与本文参照图6、7和9进一步描述的其它方法同时地实现方法800。在各个实施例中，可以代替方法700的确定框714来实现方法800，如参照图7描述的。

在确定框802中，计算设备可以确定后继任务是否具有前驱任务。如上文提及的，已执行的任务可以不再是后继任务的前驱任务，因此，计算设备可以检查除了已执行的任务之外的前驱任务。

响应于确定后继任务确实具有前驱任务(即，确定框802＝“是”)，在参照图7描述的方法700的确定框708中，计算设备可以确定从调度队列中移除的已执行的任务是否具有任何后继任务。

响应于确定后继任务不具有前驱任务(即，确定框802＝“否”)，在确定框804中，计算设备可以确定后继任务是否与其它任务共享共同属性。在做出该确定时，计算设备可以查询计算设备的组件以确定可用于执行任务的同步机制。计算设备可以将任务的执行特性与可用同步机制匹配。计算设备可以将具有与可用同步机制相对应的特性的任务与其它任务进行比较，以确定其是否具有共同属性。

共同属性可以包括控制逻辑流的共同属性或数据访问的共同属性。控制逻辑流的共同属性可以包括可由相同的硬件使用相同的同步机制执行的任务。例如，仅CPU可执行任务、仅GPU可执行任务、仅DSP可执行任务、或者仅任何其它特定硬件可执行任务。在另外的示例中，仅特定硬件可执行任务可以要求与仅可由相同的特定硬件执行的任务相比不同的同步机制，诸如基于不同的编程语言将不同的缓冲器用于任务。数据访问的共同属性可以包括多个任务对相同的数据存储设备(包括易失性和非易失性存储器设备)的访问。数据访问的共同属性还可以包括对数据存储设备的访问的类型。例如，数据访问的共同属性可以包括对相同的数据缓冲器的访问。在另外的示例中，数据访问的共同属性可以包括只读或读取/写入访问。

响应于确定后继任务不与另一个任务共享共同属性(即，确定框804＝“否”)，在如参照图7描述的方法700的框716中，计算设备可以将后继任务添加到就绪队列。

响应于确定后继任务确实与另一个任务共享共同属性(即，确定框804＝“是”)，在确定框806中，计算设备可以确定是否存在针对共享共同属性的任务的捆绑。如本文进一步描述的，可以将共享共同属性的任务捆绑在一起，使得它们可以使用共同属性一起被调度用于执行。

响应于确定不存在针对共享共同属性的任务的捆绑(即，确定框806＝“否”)，在框808中，计算设备可以创建针对共享共同属性的任务的捆绑。在各个实施例中，捆绑可以包括用于指示捆绑内的任务的层级的层级变量，使得添加到捆绑的第一任务在定义的层级处，例如，在为“0”的深度处。在框810中，计算设备可以将后继任务添加到所创建的针对共享共同属性的任务的捆绑。

响应于确定存在针对共享共同属性的任务的捆绑(即，确定框806＝“是”)，在框810中，计算设备可以将后继任务添加到现有的针对共享共同属性的任务的捆绑。

添加到捆绑的后继任务可以被称为已捆绑任务。在各个实施例中，针对共享共同属性的任务的捆绑可以仅包括共享共同属性的任务，其中那些任务中的仅一个任务可以是作为就绪任务的任务，并且余下的任务可以是就绪任务的、具有与就绪任务的不同程度的分离的后继任务。此外，后继任务也可能是或不是从针对共享共同属性的任务的捆绑中排除的其它任务(即，不共享共同属性的任务)的后继任务。响应于所排除的任务被执行，仍然可以将初始作为所排除的任务的后继任务的任务添加到捆绑，由此移除后继任务对所排除的任务的依赖性，如针对参照图7的方法700的框712描述的。因此，针对共享共同属性的任务的捆绑中包括的任务构成了共同属性任务图。

在框812中，计算设备可以识别共享共同属性的已捆绑任务的后继任务，以添加到针对共享共同属性的任务的捆绑中。参照图9更加详细地论述了识别共享共同属性的已捆绑任务的后继任务。

在确定框814中，计算设备可以确定层级变量是否满足与添加到捆绑的第一任务的层级的指定关系，诸如等于添加到捆绑的第一任务的层级。

响应于确定层级变量不满足与添加到捆绑的第一任务的层级的指定关系(即，确定框814＝“否”)，在参照图7的方法700的确定框708中，计算设备可以确定从调度队列中移除的已执行的任务是否具有任何后继任务。

响应于确定层级变量满足与添加到捆绑的第一任务的层级的指定关系(即，确定框814＝“是”)，在框816中，计算设备可以将针对共享共同属性的任务的捆绑中的任务添加到就绪队列。在框818中，计算设备可以通知或以其它方式提示组件检查就绪队列。计算设备可以确定调度队列是否为空，如针对参照图7的方法700的框712描述的。

图9示出了用于共同属性任务重映射同步的实施例方法900。可以用处理器中执行的软件、用通用硬件或专用硬件来在计算设备中实现方法900。在各个实施例中，可以由多个处理器或硬件组件上的多个线程来实现方法900。在各个实施例中，可以与本文参照图6-8进一步描述的其它方法同时地实现方法900。在各个实施例中，可以递归地执行方法900，直到不再存在满足方法900的条件的任务为止。在各个实施例中，可以代替方法800的确定框812来实现方法900，如参照图8描述的。

在确定框902中，计算设备可以确定已捆绑任务是否具有任何后继任务。响应于确定已捆绑任务不具有任何后继任务(即，确定框902＝“否”)，在参照图8的方法800的确定框814中，计算设备可以确定层级变量是否满足与添加到捆绑的第一任务的层级的指定关系。而且，执行方法900的任务可以如本文更进一步所述的那样被重新设置。

响应于确定已捆绑任务确实具有任何后继任务(即，确定框902＝“是”)，在框904中，计算设备可以获得作为已捆绑任务的后继的任务。

在确定框906中，计算设备可以确定后继任务是否与已捆绑任务共享共同属性。对后继任务是否与已捆绑任务共享共同属性的确定可以是以与在参照图8的方法800的确定框804中对后继任务是否与其它任务共享共同属性的确定类似的方式实现的。在各个实施例中，对后继任务是否与已捆绑任务共享共同属性的确定可以是不同的，这是因为仅需要检查在已捆绑任务之间共享的共同属性，而不是从更大的潜在共同属性集合中检查。

响应于确定后继任务不与已捆绑任务共享共同属性(即，确定框906＝“否”)，在确定框902中，计算设备可以确定已捆绑任务是否具有任何后继任务。

响应于确定后继任务确实与已捆绑任务共享共同属性(即，确定框906＝“是”)，在框908中，计算设备可以删除已捆绑任务与其后继任务之间的依赖性。作为删除已捆绑任务与其后继任务之间的依赖性的结果，已捆绑任务可以不再是后继任务的前驱任务。然而，这未必暗示已捆绑任务和后继任务可以乱序地执行。实际上，当捆绑被添加到就绪队列时，指派给捆绑中的每个任务的层级变量可以用于控制调度任务所采用的顺序，如在参照图8的方法800的框816中。

在确定框910中，计算设备可以确定已捆绑任务的后继任务是否具有任何前驱任务。响应于确定已捆绑任务的后继任务具有前驱任务(即，确定框910＝“是”)，在确定框902中，计算设备可以确定已捆绑任务是否具有任何其它后继任务。

响应于确定已捆绑任务的后继任务不具有前驱任务(即，确定框910＝“否”)，在框912中，计算设备可以以预定方式来改变层级变量的值，诸如递增层级变量的值。

如上文提及的，可以递归地执行方法900，由虚线箭头描绘的，直到不再存在满足方法900的条件的任务为止。因此，在如参照图8的方法800的框810中，可以在由层级变量指示的当前层级处将已捆绑任务的后继任务添加到共同属性任务捆绑，并且计算设备可以使用新捆绑的后继任务来重复方法900。

在各个实施例中，响应于确定新捆绑的后继任务不具有后继任务(即，确定框902＝“否”)，在参照图8的方法800的确定框814中，计算设备可以将针对其执行方法900的任务重置回第一已捆绑任务，并且确定层级变量是否满足与添加到捆绑的第一任务的层级的指定关系。在本文使用的示例中，已捆绑任务的层级变量值满足与添加到捆绑的第一任务的层级的指定关系，例如等于“0”。

各个实施例(包括但不限于上文参照图1-9论述的实施例)可以实现在广泛的多种多样的计算系统中，其可以包括适用于与图10中示出的各个实施例一起使用的示例性移动计算设备。移动计算设备1000可以包括处理器1002，处理器1002耦合到触摸屏控制器1004和内部存储器1006。处理器1002可以是被指定用于通用或特定处理任务的一个或多个多内核集成电路。内部存储器1006可以是易失性或非易失性存储器，并且还可以是安全的和/或加密的存储器、或不安全的和/或未加密的存储器、或其任意组合。可以利用的存储器类型的示例包括但不限于DDR、LPDDR、GDDR、WIDEIO、RAM、SRAM、DRAM、P-RAM、R-RAM、M-RAM、STT-RAM和嵌入式DRAM。触摸屏控制器1004和处理器1002还可以耦合到触摸屏面板1012，诸如电阻式感测触摸屏、电容式感测触摸屏、红外线感测触摸屏等。另外，计算设备1000的显示器不必具有触摸屏能力。

移动计算设备1000可以具有用于发送和接收通信的一个或多个无线电信号收发机1008(例如，Peanut、蓝牙、Zigbee、Wi-Fi、RF无线电)和天线1010，其彼此耦合和/或耦合到处理器1002。收发机1008和天线1010可以与上文提到的电路一起使用以实现各种无线传输协议栈和接口。移动计算设备1000可以包括蜂窝网络无线调制解调器芯片1016，其实现经由蜂窝网络的通信并且耦合到处理器。

移动计算设备1000可以包括耦合到处理器1002的外围设备连接接口1018。外围设备连接接口1018可以被单独地配置为接受一种类型的连接，或者可以被配置为接受各种类型的物理和通信连接，公共或专有的，诸如USB、火线、雷电接口或PCIe。外围设备连接接口1018还可以耦合到类似地配置的外围设备连接端口(未示出)。

移动计算设备1000还可以包括用于提供语音输出的扬声器1014。移动计算设备1000还可以包括壳体1020，其由塑料、金属或材料的组合构成，用于包含本文所讨论的组件中的一些或全部。移动计算设备1000可以包括耦合到处理器1002的电源1022，诸如一次性或可再充电电池。可再充电电池也可以耦合到外围设备连接端口以从在移动计算设备1000外部的源接收充电电流。移动计算设备1000还可以包括用于接收用户输入的物理按钮1024。移动计算设备1000还可以包括用于使移动计算设备1000开启和关闭的电源按钮1026。

各个实施例(包括但不限于上文参照图1-9论述的实施例)可以实现在广泛的多种多样的计算系统中，其可以包括多种多样的移动计算设备(例如在图11中示出的膝上型计算机1100)。许多膝上型计算机包括触摸板触摸表面1117，其用作计算机的定点设备，并且因此可以接收与在配备有触摸屏显示器和上述的计算设备上实现的那些手势类似的拖拽、滚动和轻击手势。膝上型计算机1100通常将包括处理器1111，处理器1111耦合到易失性存储器1112和大容量非易失性存储器，诸如闪存的磁盘驱动器1113。另外，计算机1100可以具有用于发送和接收电磁辐射的一个或多个天线1108，天线1108可以连接到无线数据链路和/或蜂窝收发机1116(其耦合到处理器1111)。计算机1100还可以包括耦合到处理器1111的软盘驱动器1114和压缩盘(CD)驱动器1115。在笔记本配置中，计算机壳体包括触摸板1117、键盘1118和显示器1119，它们都耦合到处理器1111。计算设备的其它配置可以包括如所公知的耦合到处理器的计算机鼠标或跟踪球(例如，经由USB输入)，其也可以结合各个实施例来使用。

各个实施例(包括但不限于上文参照图1-9论述的实施例)可以实现在广泛的多种多样的计算系统中，其可以包括用于在服务器缓存存储器中对数据进行压缩的多种多样的商业上可用的服务器中的任何一种中。图12中示出了示例服务器1200。这样的服务器1200通常包括一个或多个多内核处理器组装件1201，其耦合到易失性存储器1202和大容量非易失性存储器，诸如磁盘驱动器1204。如图12中所示出的，可以通过将多内核处理器组装件1201插入组装件的架子来将其添加到服务器1200。服务器1200还可以包括耦合到处理器1201的软盘驱动器、压缩盘(CD)或数字多功能光盘(DVD)光盘驱动器1206。服务器1200还可以包括耦合到多内核处理器组装件1201的网络接入端口1203，用于与网络1205(例如到其它广播系统计算机和服务器的局域网、互联网、公共交换电话网络和/或蜂窝数据网络(例如，CDMA、TDMA、GSM、PCS、3G、4G、LTE或任何其它类型的蜂窝数据网络))建立网络接口连接。

用于在可编程处理器上执行以实现各个实施例的操作的计算机程序代码或“代码”可以以诸如C、C++、C#、Smalltalk、Java、JavaScript、Visual Basic、结构化查询语言(例如，Transact-SQL)、Perl之类的高级编程语言或以各种其它编程语言来编写。如本申请中所使用的，存储在计算机可读存储介质上的程序代码或程序可以指其格式是处理器可理解的机器语言代码(例如，目标代码)。

提供前述的方法描述和过程流程图仅仅作为说明性示例，而不旨在需要或暗示各个实施例的操作必须按照所给出的顺序执行。如本领域普通技术人员将意识到的，前述实施例中的操作的顺序可以按照任何顺序来执行。诸如“此后”、“随后”、“接着”等词不是旨在限制操作的顺序；这些词仅用于引导读者通读方法的描述。此外，任何以单数形式引用权利要求要素，例如，使用冠词“一”、“一个”、“所述”不应被解释为将该元素限制成单数。

结合各个实施例所描述的各种说明性的逻辑框、模块、电路和算法操作可以实现成电子硬件、计算机软件、或者两者的组合。为了清楚地描绘硬件和软件的这种可互换性，上文已经对各种说明性的组件、框、模块、电路以及操作围绕其功能进行了总体描述。至于这种功能是实现成硬件还是实现成软件，取决于具体应用和施加在整体系统上的设计约束。本领域技术人员可以针对每个特定应用，以变化的方式实现所描述的功能，但是，这样的实现决定不应被解释为导致脱离本权利要求的范围。

可以利用被设计为执行本文所描述的功能的通用处理器、数字信号处理器(DSP)、专用集成电路(ASIC)、现场可编程门阵列(FPGA)或其它可编程逻辑器件、分立门或晶体管逻辑、分立硬件组件、或者其任意组合来实现或执行用于实施结合本文公开的实施例所描述的各种说明性的逻辑、逻辑块、模块、以及电路的硬件。通用处理器可以是微处理器，但在替代的方案中，处理器可以是任何常规的处理器、控制器、微控制器或状态机。处理器还可以实现为计算设备的组合，例如，DSP和微处理器的组合、多个微处理器、一个或多个微处理器结合DSP内核、或者任何其它这样的配置。或者，一些操作或方法可以由特定于给定功能的电路来执行。

在一个或多个实施例中，所述功能可以用硬件、软件、固件或其任意组合来实现。如果用软件实现，则可以将所述功能作为一个或多个指令或代码存储在非暂时性计算机可读介质或者非暂时性处理器可读介质上。本文所公开的方法或算法的操作可以体现在处理器可执行的软件模块中，该处理器可执行的软件模块可以驻留在非暂时性计算机可读的或处理器可读的存储介质上。非暂时性计算机可读的或处理器可读的存储介质可以是可以由计算机或处理器存取的任何存储介质。通过举例而非限制性的方式，这种非暂时性计算机可读的或处理器可读的介质可以包括RAM、ROM、EEPROM、闪存、CD-ROM或其它光盘存储、磁盘存储或其它磁存储设备、或者可以用于以指令或数据结构的形式存储期望的程序代码并可以由计算机存取的任何其它介质。如本文所使用的，磁盘和光盘包括压缩盘(CD)、激光光盘、光盘、数字多功能光盘(DVD)、软盘和蓝光光盘，其中磁盘通常磁性地复制数据，而光盘则用激光来光学地复制数据。上述的组合也包括在非暂时性计算机可读和处理器可读介质的范围之内。此外，方法或算法的操作可以作为代码和/或指令中的一个或任何组合、或代码和/或指令集驻留在非暂时性处理器可读介质和/或计算机可读介质上，所述非暂时性处理器可读介质和/或计算机可读介质可以并入计算机程序产品。

提供所公开的实施例的以上描述使任何本领域技术人员能够实施或使用本权利要求。对于本领域技术人员来说，对这些实施例的各种修改将是显而易见的，并且在不脱离本权利要求的范围的情况下，可以将本文定义的总体原理应用于其它实施例。因此，本公开内容并不旨在受限于本文示出的实施例，而是要符合与所附权利要求书和本文所公开的原理和新颖特征的相一致的最宽的范围。

Claims (32)

1.一种用于在计算设备上加速执行属于共同属性任务图的多个任务的方法，包括：

识别第一后继任务，所述第一后继任务依赖于已捆绑任务，使得可用同步机制是所述已捆绑任务和所述第一后继任务的共同属性，并且使得所述第一后继任务仅依赖于所述可用同步机制是其共同属性的前驱任务；

将所述第一后继任务添加到共同属性任务图；以及

将属于所述共同属性任务图的所述多个任务添加到就绪队列。

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

针对所述可用同步机制来查询所述计算设备的组件。

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

创建用于包括属于所述共同属性任务图的所述多个任务的捆绑，其中，所述可用同步机制是所述多个任务中的每个任务的共同属性，并且其中，所述多个任务中的每个任务依赖于所述已捆绑任务；以及

将所述已捆绑任务添加到所述捆绑。

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

将所述捆绑的层级变量设置为针对所述已捆绑任务的第一值；

将所述捆绑的所述层级变量修改为针对所述第一后继任务的第二值；

确定所述第一后继任务是否具有第二后继任务；以及

响应于确定所述第一后继任务不具有第二后继任务，将所述层级变量设置为所述第一值，

其中，将属于所述共同属性任务图的所述多个任务添加到就绪队列包括：响应于所述层级变量被响应于确定所述第一后继任务不具有第二后继任务而设置为所述第一值，将属于所述共同属性任务图的所述多个任务添加到所述就绪队列。

5.根据权利要求1所述的方法，其中，识别所述已捆绑任务的第一后继任务包括：

确定所述已捆绑任务是否具有第一后继任务；以及

响应于确定所述已捆绑任务具有所述第一后继任务，确定所述第一后继任务是否具有作为与所述已捆绑任务的共同属性的所述可用同步机制。

6.根据权利要求5所述的方法，其中，识别所述已捆绑任务的第一后继任务还包括：

响应于确定所述第一后继任务具有作为与所述已捆绑任务的共同属性的所述可用同步机制，删除所述第一后继任务对所述已捆绑任务的依赖性；以及

确定所述第一后继任务是否具有前驱任务。

7.根据权利要求6所述的方法，其中：

对所述已捆绑任务的第一后继任务的识别是递归地执行的，直到确定所述已捆绑任务不具有其它后继任务为止；以及

将属于所述共同属性任务图的所述多个任务添加到就绪队列包括：响应于确定所述已捆绑任务不具有其它后继任务，将属于所述共同属性任务图的所述多个任务添加到所述就绪队列。

8.根据权利要求1所述的方法，其中，所述可用同步机制是用于控制逻辑流的同步机制和用于数据访问的同步机制中的一者。

9.一种计算设备，包括：

存储器；以及

通信地连接到彼此和所述存储器的多个处理器，所述多个处理器包括第一处理器，所述第一处理器被配置有用于执行包括以下各项的操作的处理器可执行指令：

识别第一后继任务，所述第一后继任务依赖于已捆绑任务，使得所述多个处理器中的第二处理器的可用同步机制是所述已捆绑任务和所述第一后继任务的共同属性，并且使得所述第一后继任务仅依赖于所述可用同步机制是其共同属性的前驱任务；

将所述第一后继任务添加到共同属性任务图；以及

将属于所述共同属性任务图的多个任务添加到就绪队列。

10.根据权利要求9所述的计算设备，其中，所述第一处理器被配置有用于执行还包括以下各项的操作的处理器可执行指令：

针对所述可用同步机制来查询所述第二处理器。

11.根据权利要求9所述的计算设备，其中，所述第一处理器被配置有用于执行还包括以下各项的操作的处理器可执行指令：

创建用于包括属于所述共同属性任务图的所述多个任务的捆绑，其中，所述可用同步机制是所述多个任务中的每个任务的共同属性，并且其中，所述多个任务中的每个任务依赖于所述已捆绑任务；以及

将所述已捆绑任务添加到所述捆绑。

12.根据权利要求11所述的计算设备，其中，所述第一处理器被配置有用于执行还包括以下各项的操作的处理器可执行指令：

将所述捆绑的层级变量设置为针对所述已捆绑任务的第一值；

将所述捆绑的所述层级变量修改为针对所述第一后继任务的第二值；

确定所述第一后继任务是否具有第二后继任务；以及

响应于确定所述第一后继任务不具有第二后继任务，将所述层级变量设置为所述第一值，

其中，所述第一处理器被配置有用于执行操作的处理器可执行指令，使得将属于所述共同属性任务图的所述多个任务添加到就绪队列包括：响应于所述层级变量被响应于确定所述第一后继任务不具有第二后继任务而设置为所述第一值，将属于所述共同属性任务图的所述多个任务添加到所述就绪队列。

13.根据权利要求9所述的计算设备，其中，所述第一处理器被配置有用于执行操作的处理器可执行指令，使得识别所述已捆绑任务的第一后继任务包括：

确定所述已捆绑任务是否具有第一后继任务；以及

响应于确定所述已捆绑任务具有所述第一后继任务，确定所述第一后继任务是否具有作为与所述已捆绑任务的共同属性的所述可用同步机制。

14.根据权利要求13所述的计算设备，其中，所述第一处理器被配置有用于执行操作的处理器可执行指令，使得识别所述已捆绑任务的第一后继任务还包括：

响应于确定所述第一后继任务具有作为与所述已捆绑任务的共同属性的所述可用同步机制，删除所述第一后继任务对所述已捆绑任务的依赖性；以及

确定所述第一后继任务是否具有前驱任务。

15.根据权利要求14所述的计算设备，其中，所述第一处理器被配置有用于执行操作的处理器可执行指令，使得：

对所述已捆绑任务的第一后继任务的识别是递归地执行的，直到确定所述已捆绑任务不具有其它后继任务为止；以及

将属于所述共同属性任务图的所述多个任务添加到就绪队列包括：响应于确定所述已捆绑任务不具有其它后继任务，将属于所述共同属性任务图的所述多个任务添加到所述就绪队列。

16.根据权利要求9所述的计算设备，其中，所述可用同步机制是用于控制逻辑流的同步机制和用于数据访问的同步机制中的一者。

17.一种计算设备，包括：

用于识别第一后继任务的单元，所述第一后继任务依赖于已捆绑任务，使得可用同步机制是所述已捆绑任务和所述第一后继任务的共同属性，并且使得所述第一后继任务仅依赖于所述可用同步机制是其共同属性的前驱任务；

用于将所述第一后继任务添加到共同属性任务图的单元；以及

用于将属于所述共同属性任务图的多个任务添加到就绪队列的单元。

18.根据权利要求17所述的计算设备，还包括：

用于针对所述可用同步机制来查询所述计算设备的组件的单元。

19.根据权利要求17所述的计算设备，还包括：

用于创建用于包括属于所述共同属性任务图的所述多个任务的捆绑的单元，其中，所述可用同步机制是所述多个任务中的每个任务的共同属性，并且其中，所述多个任务中的每个任务依赖于所述已捆绑任务；以及

用于将所述已捆绑任务添加到所述捆绑的单元。

20.根据权利要求19所述的计算设备，还包括：

用于将所述捆绑的层级变量设置为针对所述已捆绑任务的第一值的单元；

用于将所述捆绑的所述层级变量修改为针对所述第一后继任务的第二值的单元；

用于确定所述第一后继任务是否具有第二后继任务的单元；以及

用于响应于确定所述第一后继任务不具有第二后继任务，将所述层级变量设置为所述第一值的单元，

其中，用于将属于所述共同属性任务图的所述多个任务添加到就绪队列的单元包括：用于响应于所述层级变量被响应于确定所述第一后继任务不具有第二后继任务而设置为所述第一值，将属于所述共同属性任务图的所述多个任务添加到所述就绪队列的单元。

21.根据权利要求17所述的计算设备，其中，用于识别所述已捆绑任务的第一后继任务的单元包括：

用于确定所述已捆绑任务是否具有第一后继任务的单元；以及

用于响应于确定所述已捆绑任务具有所述第一后继任务，确定所述第一后继任务是否具有作为与所述已捆绑任务的共同属性的所述可用同步机制的单元。

22.根据权利要求21所述的计算设备，其中，用于识别所述已捆绑任务的第一后继任务的单元还包括：

用于响应于确定所述第一后继任务具有作为与所述已捆绑任务的共同属性的所述可用同步机制，删除所述第一后继任务对所述已捆绑任务的依赖性的单元；以及

用于确定所述第一后继任务是否具有前驱任务的单元。

23.根据权利要求22所述的计算设备，其中：

用于识别所述已捆绑任务的第一后继任务的单元包括：用于递归地识别所述已捆绑任务的所述第一后继任务，直到确定所述已捆绑任务不具有其它后继任务为止的单元；以及

用于将属于所述共同属性任务图的所述多个任务添加到就绪队列的单元包括：用于响应于确定所述已捆绑任务不具有其它后继任务，将属于所述共同属性任务图的所述多个任务添加到所述就绪队列的单元。

24.根据权利要求17所述的计算设备，其中，所述可用同步机制是用于控制逻辑流的同步机制和用于数据访问的同步机制中的一者。

25.一种其上存储有处理器可执行指令的非暂时性处理器可读存储介质，所述处理器可执行指令被配置为使得计算设备的处理器执行包括以下各项的操作：

识别第一后继任务，所述第一后继任务依赖于已捆绑任务，使得可用同步机制是所述已捆绑任务和所述第一后继任务的共同属性，并且使得所述第一后继任务仅依赖于所述可用同步机制是其共同属性的前驱任务；

将所述第一后继任务添加到共同属性任务图；以及

将属于所述共同属性任务图的多个任务添加到就绪队列。

26.根据权利要求25所述的非暂时性处理器可读存储介质，其中，所存储的处理器可执行指令被配置为使得所述处理器执行还包括以下各项的操作：

针对所述可用同步机制来查询所述计算设备的组件。

27.根据权利要求25所述的非暂时性处理器可读存储介质，其中，所存储的处理器可执行指令被配置为使得所述处理器执行还包括以下各项的操作：

创建用于包括属于所述共同属性任务图的所述多个任务的捆绑，其中，所述可用同步机制是所述多个任务中的每个任务的共同属性，并且其中，所述多个任务中的每个任务依赖于所述已捆绑任务；以及

将所述已捆绑任务添加到所述捆绑。

28.根据权利要求27所述的非暂时性处理器可读存储介质，其中，所存储的处理器可执行指令被配置为使得所述处理器执行还包括以下各项的操作：

将所述捆绑的层级变量设置为针对所述已捆绑任务的第一值；

将所述捆绑的所述层级变量修改为针对所述第一后继任务的第二值；

确定所述第一后继任务是否具有第二后继任务；以及

响应于确定所述第一后继任务不具有第二后继任务，将所述层级变量设置为所述第一值，

其中，将属于所述共同属性任务图的所述多个任务添加到就绪队列包括：响应于所述层级变量被响应于确定所述第一后继任务不具有第二后继任务而设置为所述第一值，将属于所述共同属性任务图的所述多个任务添加到所述就绪队列。

29.根据权利要求25所述的非暂时性处理器可读存储介质，其中，所存储的处理器可执行指令被配置为使得所述处理器执行操作，使得识别所述已捆绑任务的第一后继任务包括：

确定所述已捆绑任务是否具有第一后继任务；以及

响应于确定所述已捆绑任务具有所述第一后继任务，确定所述第一后继任务是否具有作为与所述已捆绑任务的共同属性的所述可用同步机制。

30.根据权利要求29所述的非暂时性处理器可读存储介质，其中，所存储的处理器可执行指令被配置为使得所述处理器执行操作，使得识别所述已捆绑任务的第一后继任务还包括：

响应于确定所述第一后继任务具有作为与所述已捆绑任务的共同属性的所述可用同步机制，删除所述第一后继任务对所述已捆绑任务的依赖性；以及

确定所述第一后继任务是否具有前驱任务。

31.根据权利要求30所述的非暂时性处理器可读存储介质，其中，所存储的处理器可执行指令被配置为使得所述处理器执行操作，使得：

对所述已捆绑任务的第一后继任务的识别是递归地执行的，直到确定所述已捆绑任务不具有其它后继任务为止；以及

将属于所述共同属性任务图的所述多个任务添加到就绪队列包括：响应于确定所述已捆绑任务不具有其它后继任务，将属于所述共同属性任务图的所述多个任务添加到所述就绪队列。

32.根据权利要求25所述的非暂时性处理器可读存储介质，其中，所述可用同步机制是用于控制逻辑流的同步机制和用于数据访问的同步机制中的一者。