用于实现代码划分和在异构处理器内核上执行的高效有向非循环图模式匹配

摘要

用于自动地确定如何对应用程序进行划分和卸载，用于由移动设备内的通用应用处理器和辅助处理器(例如，DSP、GPU等等)执行的方法、设备和系统。移动设备可以基于有向非循环图(DAG)的模式匹配来确定应用代码中最适合于在辅助处理器上执行的部分。特别地，移动设备可以识别代码中的(特别是代码的数据流程图中的)一种或多种模式，将每一种识别的代码模式与已知当在辅助处理器(例如，DSP)上执行时具有某种利益的预定义的图形模式进行比较。移动设备可以确定在辅助处理器上执行代码的部分的开销和/或利益，并且可以对具有与辅助处理器有关的低开销和/或高利益的部分进行卸载。

说明书

背景技术

移动电子设备(例如，蜂窝电话、手表、头戴式耳机、远程控制等等) 与以往任何时候相比变得更加复杂，并且现在通常包括多个处理器、片上 系统(SoC)、以及允许移动设备用户在其移动设备上执行复杂的和功率密 集的软件应用(例如，视频流、视频处理等等)的其它资源。随着复杂度 和功耗的增加，更好地利用移动设备的资源和能力的新的和改进的处理技 术正在开始涌现。

这些新兴的技术包括能够对被设计用于在通用应用处理器上执行的代 码进行编译，使得该代码适合于在诸如数字信号处理器(或DSP)之类的 辅助处理器上执行的系统。特别地，应用程序可以被划分成单元或块，并 且可以基于所识别的不同的处理部件(例如，DSP、图形处理单元或GPU 等等)的效率/能力来将单元/块分布到该不同的处理部件。这使得主或中央 处理单元(CPU)或应用处理器将其操作中的一些操作卸载到辅助处理器， 以节省功率和/或改善性能。

但是，确定应用程序如何被划分以及哪些部分最适合于在辅助处理器 上执行，经常是困难的设计任务。也就是说，只要存在用于识别并且将给 定的代码段划分成非常适合于在不同类型的内核或处理单元中执行的部件 的有效方式，将操作卸载到辅助处理器就可以改善移动设备的性能和功耗 特性。

现有的技术可以利用不同的技术来识别和/或处理代码。一些技术可以 利用自动代码划分，并且可以通过程序依赖图来表示应用代码，用于使用 固有的并行性和已知的通信开销来对代码进行划分。这些技术没有利用可 能已知对特定的处理单元(诸如数字信号处理器(DSP))有益的预定义的 模式。其它技术可以检测代码(或二进制)内的惯用语法(idiom)(或者已 知的/预定义的指令集)，并且利用硬件辅助指令(即，复杂指令集计算或 “CISC”指令)来取代惯用语法。这些技术通常只可以处理有限的粒度(大 部分是直线型的指令)和简单的模式，诸如精确的模式或者有限的自由度。 另外，存在用于发现重复代码和使用高级源代码来检测克隆的某些技术。 此外，图模式匹配已经被用在数据库系统中。

存在使用指令选择算法的其它技术，所述指令选择算法利用树型模式 匹配来调整代码以包括低开销指令。特别地，自底向上的重写系统(或 BURS)算法可以被用来通过迭代地匹配与输入代码(例如，应用、例程等 等)有关的输入树内的各个子树以便发现最佳开销指令集(即，覆盖整棵 树并且还提供最低开销/最高利益的指令的组合)，来确定针对输入代码的最 佳指令集。基于模式匹配，可以生成用于在计算设备上执行的新的、改进 的指令集。

但是，当对使用基于图形表示的复杂的代码的部分进行卸载时，已知 的技术可能是不适合的。换言之，现有的技术可能不使用代码的有向非循 环表示进行匹配来识别用于异构多核或分布式系统的最佳卸载方式的编译 器后端解决方案。

发明内容

在各个方面中，计算设备可以执行用于当可以自动地确定输入代码的 部分非常适合于辅助处理器时，将该输入代码的部分从CPU或应用处理器 (“第一处理器”)卸载到辅助处理器的方法。一个方面方法可以包括：生 成输入代码的基于图形的中间表示，其中，输入代码的基于图形的中间表 示可以是有向非循环图(DAG)，将每一个节点或节点的组合与预定义的语 法中的一种或多种模式进行比较，其中每一种模式可以是DAG模式并且可 以与开销度量相关联，基于比较来识别部分地覆盖所述输入代码的基于图 形的中间表示的模式集合，以及将输入代码的片段从第一处理器卸载到辅 助处理器，所述输入代码的片段与所识别的模式集合中具有最佳累积效应 的语法模式的组合相关联。在一个方面中，将每一个节点或节点的组合与 预定义的语法中的一种或多种模式进行比较可以包括：将每一个节点或节 点的组合与被存储在启发式表格中的模式信息进行比较。在一个方面中， 该计算设备可以包括片上系统。在一个方面中，所述辅助处理器可以是数 字信号处理器(DSP)和图形处理单元(GPU)中的一种。在一个方面中， 已知所述预定义的语法中的模式非常适合于辅助处理器。在一个方面中， 最佳累积效应可以是最低累积开销和最高累积利益中的一种。在一个方面 中，该方法还可以包括：基于所述每一个节点或所述节点的组合与所述预 定义的语法中的一种或多种模式的比较来生成用于向开发者呈现的信息， 所述信息指示可以被配置用于辅助处理器的输入代码的片段。

在另一个方面中，被配置为当可以自动地确定输入代码的部分非常适 合于辅助处理器时对该输入代码的部分进行卸载的计算设备可以包括：用 于执行上面描述的方面方法的功能的单元。

在另一个方面中，被配置为当可以自动地确定输入代码的部分非常适 合于辅助处理器时对该输入代码的部分进行卸载的计算设备可以包括：存 储器、辅助处理器、以及耦合到所述存储器和所述辅助处理器的处理器， 其中所述处理器可以被配置有用于执行上面描述的方面方法的操作的处理 器可执行指令。

在另一个方面中，一种非暂时性处理器可读存储介质，其具有被存储 在其上的处理器可执行软件指令，所述处理器可执行软件指令被配置为使 处理器执行用于当可以自动地确定输入代码的部分非常适合于辅助处理器 时计算设备对该输入代码的部分进行卸载的操作，其中所存储的操作包括 上面描述的方面方法的操作。

附图说明

被并入本文并且构成本说明书的一部分的附图示出了本发明的示例性 方面，并且连同上面给出的概括描述以及下面给出的具体实施方式用来解 释本发明的特征。

图1是示出了用于基于有向非循环图(DAG)模式匹配来将用于执行 的代码从CPU或应用处理器卸载到辅助处理器的方面方法的过程流程图。

图2是示出了用于基于有向非循环图(DAG)模式匹配来将用于执行 的代码从CPU或应用处理器卸载到辅助处理器的另一个方面方法的过程流 程图。

图3是示出了适合于与各个方面一起使用的示例性语法和代码输入 DAG的图。

图4是示出了基于DAG模式匹配来将用于执行的代码部分从CPU或 应用处理器卸载到辅助处理器的方面方法的过程流程图。

图5是示出了适合于与各个方面一起使用的示例性语法和代码输入 DAG的图。

图6是适合于与各个方面一起使用的智能电话型移动计算设备的部件 框图。

具体实施方式

将参照附图来详细地描述各个方面。在任何可能的情况下，将贯穿附 图使用相同的附图标记来指代相同的或者类似的部件。对于特定示例和实 现方式的提及是出于说明性的目的的，而不旨在限制本发明或者权利要求 的范围。

本文使用词语“示例性的”来意指“充当示例、实例或说明”。本文中 被描述为“示例性的”任何实现方式不必然地被解释为优选的或者比其它 实现方式具有优势。

本文使用术语“移动计算设备”或“计算设备”来指代下列各项中的 任何一项或者全部：蜂窝电话、智能电话(例如，)、手写电脑 (web-pad)、平板计算机、具备互联网能力的蜂窝电话、具备WiFi能力的 电子设备、个人数据助理(PDA)、膝上型计算机、个人计算机、以及被装 备有至少应用处理器(或通用处理器)和辅助处理器(例如，数字信号处 理器、协处理器、片上系统上的另一个处理器等等)的类似的电子设备。

各个方面提供了用于基于模式匹配表示输入代码的有向非循环图 (DAG)来将用于执行的该输入代码的部分从CPU或应用处理器(在本文 通常被称为“第一处理器”)卸载到计算设备内的辅助处理器的方法。计算 设备可以执行该方面方法，以自动地和高效地检测该代码中已知对于利用 特定类型的内核(例如，DSP、GPU等等)来进行处理有好处的感兴趣的 模式。计算设备可以自动地识别部分地覆盖输入代码的输入数据流程图的 DAG模式集合，并且可以当在辅助处理器上执行时对代码中与最小开销相 关联的部分进行卸载，或者以其它方式从卸载中提供最高的利益。这些方 面方法可以在利用典型的输入代码(例如，典型的Java语言源代码)进行 工作的计算设备中实现，并且因此可能不需要由代码开发者进行任何特殊 的预处理或者编排格式(例如，手动地添加指示符、API调用、预定义的代 码格式化等等)。实现各个方面的计算设备可以自动地识别非常适合于卸载 到辅助处理器的代码部分，并且使用传统的机制来发送、传送或者以别的 方式规定对这样识别的非常适合的代码的卸载。

各个方面方法利用将DAG的节点与预定义的语法模式(其也包括 DAG)进行比较的模式匹配算法。各个方面方法可以由计算设备来执行， 以确定代码的中间表示(IR)，并且生成可以通过模式匹配算法来处理的 DAG表示。这样的算法可以尝试将代码的DAG表示中的模式与被存储在 存储器中的DAG模式(被称为“语法”)进行匹配，所述被存储在存储器 中的DAG模式已知非常适合于在辅助处理器上执行。可以对DAG表示进 行修整，使得不存在循环。例如，语法中的DAG模式可以与在数字信号处 理器(DSP)上高效地执行的某些简单的功能相对应。计算设备可以识别覆 盖整个DAG的语法模式(例如，表示输入代码中的代码循环或方法的 DAG)，并且可以基于与语法模式相关联的开销(或利益)来识别最佳匹配 模式。例如，可以将输入代码的特定DAG与语法内的若干模式进行匹配； 但是，匹配模式中的一种匹配模式可以具有在辅助处理器上执行相关联的 代码的相对低的开销。计算设备可以执行模式匹配，使得在输入IR代码内 一次检测预定义的语法中的多个已知的DAG模式。在各个方面中，计算设 备的操作可以在运行时间执行，例如，结合即时(JIT)编译器一起执行。 换言之，利用与输入代码相关联的节点和边的图(即，在边方向和节点类 型不能被分离情况下的DAG)，计算设备可以执行模式匹配操作，以寻找 该图中的节点/边与语法内的模式的精确匹配。从任一节点类型(例如，在 模式中的位置处的类型A或类型B)的意义上说，匹配模式本身可以是灵 活的。该精确匹配是针对输入代码的子图上的完全模式的。所以，计算设 备可以从语法中发现均部分地覆盖该输入的、但是完全地覆盖该输入的子 图的模式。

在一个方面中，对于输入代码的DAG中的每一个节点而言，计算设备 可以计算与该节点连同预定义的语法的匹配规则/模式相匹配的所有可能 “类型”的表格(如可以在BURS解决方案中类似地进行)。计算设备还可 以自动地识别和/或存储针对以每一个节点为根的模式的累积开销(如可以 在BURS解决方案中类似地进行)。计算设备还可以从根部的DAG执行自 底向上的传递(如可以在BURS解决方案中类似地进行)。但是，当计算设 备将节点与预定义的语法内的已知模式进行匹配时，计算设备可以使用先 前针对该模式计算的结果，而无需重新计算该表格。另外，每当节点与语 法中的特定模式相匹配时，计算设备就可以确认DAG中的节点之间的连接 (或者经由有向边的共享)是否用匹配规则或模式来类似地表示。例如， 当与功能(例如，‘存储’功能)相对应的节点匹配语法模式或规则时，计 算设备可以检查共享(或者其它节点之间的连接)，以确定匹配语法模式是 否指示模式节点之间的类似关系(例如，“加载”和“存储”操作是否均在 分别对于相同的数组数据结构进行读取和写入等等)。这些方面方法可以由 计算设备来执行，以在与执行常规的树模式匹配相同的时间复杂度的情况 下，将输入代码的中间表示中的DAG模式和预定义的语法进行匹配。

在一个方面中，计算设备可以利用适合于表达模式的模式规范语言 (PSL)或PSL技术。例如，计算设备可以使用PSL来定义可以与代码表 示进行比较的语法内的模式。此外，计算设备可以基于输入代码的数据流 程图来使用PSL自动地生成代码。通过使用PSL，可以使得计算设备能够 表达输入代码中的精确模式和‘宽松’模式二者。例如，宽松模式可以是 包括一些通用算术计算，而无需实际地指定该算术计算应当是什么的模式。 换言之，使用PSL可以由计算设备实现关联的或交换的模式匹配。在一个 方面中，PSL还可以被用来利用宽松模式表达“包含仿射数组访问的循环”。

当前，很多软件开发者可能不具有对执行其应用的计算设备内的不同 处理单元或内核的能力的理解，并且因此可能不知道其应用的部分是被定 为目标还是以别的方式设计，以有效地使用这些不同的内核。在一个方面 中，计算设备可以被配置为实现开发者工具包，其辅助这样的软件开发者 识别其应用(或源代码)中的可以被优化或者被配置用于特定的辅助处理 器或内核(例如，DSP或GPU)的代码部分(或者片段)。使用与下面描述 的用于识别要被自动地卸载的代码部分的那些操作类似的操作，计算设备 可以被配置为对代码进行处理和评估，以识别与语法内的预定义的DAG模 式相对应的代码部分，并且生成指示所评估的代码中的某些部分可能非常 适合于哪些内核的有帮助的信息或暗示。计算设备还可以被配置为呈现所 生成的有帮助的信息(例如，向软件开发者提交有帮助的信息的呈现)。这 样的有帮助的信息可以包括用于向开发者指示目标为了与编译器和/或手动 配置操作一起使用以当在计算设备上被执行时增加整体代码效率的代码部 分的建议。因此，利用该技术，软件开发者可能不需要理解特定的处理器 细节，而可以用他们最喜爱的高级语言来简单地编写代码，并且计算设备 可以识别和呈现用于指示用于与该代码的各个部分一起使用的正确的处理 器的信息。

在下面的附图以及与图3和图5有关的描述中，描绘并且描述了示例 性语法(关于规则和开销)和输入结构(例如，输入DAG)，以说明各个 方面方法和实现方式。这样的示例以及被包括在内部的任何特定的值、操 作、功能或结构仅仅是出于说明的目的的，并不旨在限制权利要求书中记 载的新颖的方面方法和设备的范围。特别地，在这样的说明中指示的具体 示例性值(例如，与特定的功能、规则或结构相关联的数字“开销”)可以 是任意的，并且仅仅出于说明的目的而提供，并且可能不具有与实际的功 能或结构的实际开销或利益的任何关系。

图1示出了用于计算设备基于DAG模式匹配来选择用于从CPU或应 用处理器卸载到辅助处理器(例如，DSP、GPU等等)的代码的方面方法 100。方面方法100可以由计算设备(例如，膝上型计算机、智能电话等等) 来执行，以针对包括DAG模式(即，已知DAG模式和相关联的开销和/ 或利益的库)的已知语法来执行模式匹配。

各种BURS算法可以通过对指令进行组合并且将与每一个指令/节点相 关联的开销模型和每一个可能的指令组合的开销进行比较，来发现用于完 成代码段的功能的最佳指令集。同样地，当BURS指令选择方法被应用于 DAG时，其会需要对生成原始输入代码的复本以发现用于完成该原始输入 代码的目的的最佳指令集的可能性进行探索，并且因此解决了“np完全” 问题。方法100和下面描述的其它方面方法不生成用于输入代码的新指令 (或替代指令)，而是自动地识别针对DAG中的每一个节点或节点的组合 的非常适合于将CPU或应用处理器卸载到辅助处理器(例如，DSP)的多 种模式。换言之，方面方法可以由计算设备执行成非指数型算法以识别多 种模式，并且选择最有性价比的代码来进行卸载，因此与BURS算法相比， 解决了更简单的问题。

在框102中，计算设备可以生成输入代码的有向非循环图(DAG)中 间表示。例如，DAG可以是基于方法的源代码、方法集或者整个应用来生 成的。这样的基于图形的中间表示可以被称为数据流程图。通常，可以通 过对输入代码(例如，软件应用程序或软件程序的部分)进行解析，并且 确定该代码的结构的图形的或符号的映射来生成代码的中间表示。例如， 诸如用于某种方法的输入代码的DAG之类的中间表示，可以指示代码内的 句法和其它功能的或操作的要素。中间表示可以包括诸如注释之类的额外 的信息，其可以由动态的或即时(JIT)编译器用来对该程序进行分析和配 置。

DAG中间表示可以包括具有单向连接的节点(有时被称为顶点)，该 单向连接可以被称为边。DAG节点之间的这样的连接可以表示节点之间的 逻辑关系。例如，叶节点和根节点之间的连接可以指示该叶节点是函数的 操作数。此外，DAG可以不包括诸如表示代码循环的环。特别地，可以对 所生成的DAG进行修整或调整，使得在中间表示中不存在环，而不管输入 代码内固有的任何循环或环。在各个方面中，可以由计算设备来利用编译 器例程、模块、指令或其它部件，以将应用的输入代码(例如，源代码、 二进制代码等等)转换成连接的叶子和/或节点的DAG结构。

应当注意的是，DAG不与如可以在BURS算法中使用的输入树(或句 法输入树)相同。例如，在各种BURS实现方式中，可以将输入代码转换 为表达式输入树，其包括各种叶节点和子树，并且可以沿单个方向从任意 叶节点遍历到根节点。方面方法可以生成包括比树更多的关于节点之间的 连接的信息的DAG。DAG节点可以沿各个方向被连接和/或具有多个连接， 因此如下文描述的需要另外的操作来评估节点和模式匹配。

在框104中，计算设备可以将所生成的DAG的每一个节点或节点的组 合与语法中的一种或多种预定义的DAG模式进行比较，每一种模式与开销 度量相关联。换言之，计算设备可以遍历所生成的DAG的节点，以检测与 语法模式的匹配。计算设备可以以自底向上的方式来访问所生成的DAG的 每一个节点，在访问一个节点自身之前，基本上访问该节点的子节点(或 者叶节点)。当计算设备访问一个节点时，其可以搜索与该节点匹配的所有 DAG模式(或子模式)，并且将所有可能类型(例如，语法中的“非终结 符(non-terminal)”)的表格更新为该节点可以与它们的启用模式规则标识 符和相关联的开销(例如，以该节点为根的DAG模式的开销)相匹配。在 所生成的DAG的根处，计算设备可以利用来自该语法的模式规则来发现覆 盖所生成的DAG的每一个节点(或节点的组合)的低开销方式。

在各个方面中，该语法可以仅仅是存储预定义的DAG模式连同有关信 息的数据结构。例如，该语法可以是与已知用某些方式、效率或开销在特 定的架构、设备、操作系统等等上执行的指令相关联的DAG模式(或结构) 的列表。不同于其它技术，方面方法可以在语法内存储多个预定义的DAG 模式，而不是树。例如，可以将所存储的预定义的模式表达成根DAG的集 合，所述根DAG的集合中的每一个根DAG可以包括针对相关联的模式的 开销和/或利益度量。在各个方面中，该语法可以包括已知非常适合于特定 的内核(例如，移动设备内的DSP或GPU)的DAG模式。下面描述了这 样的方面语法的非限制性说明。

框104中的操作可以自动地确定非常适合用于卸载的代码，而无需任 何开发者来手动地指示这样的非常适合的代码。在各个方面中，框104中 操作的比较可以包括：基于节点特性或类型(例如，叶子、对应于特定的 操作等等)和节点配置、连接或者排列(例如，特定的节点之间的有向连 接)来确定语法模式是否匹配DAG节点。当进行该比较时，计算设备可以 确定DAG内节点的方位、连接和依赖关系。例如，计算设备可以确定所生 成的DAG内的节点的子组包括两个寄存器叶子(例如，被存储在寄存器内 的整数值)和一个根节点，所述根节点与某个数学运算(例如，加法、乘 法等等)相对应。在一个方面中，节点与语法的比较可以包括：将所生成 的DAG的每一个节点或节点的组合与被存储在启发式表格中的模式信息 进行比较。

在框106中，计算设备可以基于比较来识别部分地覆盖所生成的DAG 的语法模式集合。换言之，基于框104中的操作中的比较，计算设备可以 将语法中定义的各种DAG模式识别成与DAG的所有节点有关或者链接到 DAG的所有节点(并且因此，输入代码的所有要素)。例如，识别的语法 模式集合可以包括：与用所生成的DAG表示的每一个变量和函数相关联的 语法模式。在各个方面中，所识别的集合可以包括针对所生成的DAG的特 定要素的一种以上的语法模式(例如，具有相关联的开销/利益的多个存储 的模式可以匹配所生成的DAG的特定的节点或节点的组合)。

在框108中，计算设备可以卸载输入代码的片段，所述输入代码的片 段与所识别的模式集合中具有最佳识别的累积效应的语法模式的组合相关 联。这可以通过确定所识别的语法模式集合的开销和利益，并且将与识别 的模式组合相关联的具有最低开销的代码的片段从CPU或应用处理器卸载 到辅助处理器(例如，DSP、GPU等等)来完成。在各个方面中，当最低 累积开销(或最高/最大累积利益)超过预定义的门限值时，可以卸载该片 段。例如，当所识别的语法模式集合与组合的开销相关联时，可以将输入 代码(或者输入代码的片段)卸载到DSP，所述组合的开销不超过用于有 益地从CPU或应用处理器卸载到DSP的最大开销门限值。

图2示出了用于计算设备基于DAG模式匹配来选择用于卸载到辅助处 理器(例如，DSP、GPU等等)的代码的方面方法250。除了方法250包括 用于对模式进行重新评估以便确认匹配模式包括与DAG内定义的节点之 间的连接相同的连接的显示操作之外，方法250类似于上面描述的方法100。 在框102中，如上所述，计算设备可以生成输入代码的有向非循环图(DAG) 中间表示。在框104中，计算设备可以将所生成的DAG的每一个节点或节 点的组合与语法中的一种或多种预定义的DAG模式进行比较，每一种模式 与开销度量相关联。在框252中，当节点或节点的组合与语法中的模式相 匹配时，计算设备可以对DAG进行重新评估以识别另外的模式和累积开 销。换言之，由于DAG包括节点之间的有向边或连接，因此计算设备可以 被配置为执行确认评估传递(例如，重新遍历该DAG)，以便确保语法的 任何匹配的模式与所生成的DAG内的节点的配置以及与该节点相关联的 边的任何方向二者相匹配。在框106中，计算设备可以基于比较来识别部 分地覆盖所生成的DAG的语法模式集合。例如，基于对DAG的遍历和重 新遍历，计算设备可以识别被确认为与DAG的配置、节点类型和边相匹配 的语法模式集合。在框108中，计算设备可以卸载输入代码的片段，所述 输入代码的片段与所识别的模式集合中具有最佳累积效应的语法模式的组 合相关联。

图3示出了适合于与各个方面一起使用的示例性语法300以及与输入 代码有关的输入DAG320。语法300可以包括规则304-306，其均包括规则 标识符(例如，“[r]”、“[r’]”等等)、非终结符符号、与该规则相关联的开 销(或开销度量)、以及与该规则相关联的DAG模式(例如，形成DAG模 式或末端节点的节点集合，例如，整数)。由规则指示的开销和/或利益可以 是对于计算设备和/或辅助处理器的、与执行和语法的DAG模式相关联的 操作有关的费用、收费、时间或价值的一般表示，并且可以是处理周期、 利用的资源、或者用于对其执行进行量化的其它度量的近似值。例如，规 则的开销可以表示执行与单个规则相关联的指令所需要的处理器周期的数 量、时间、电池寿命、或者其它资源。模板项302可以示出语法300内的 规则的结构。在各个方面中，非终结符符号可以包括术语、符号、或者可 以与结构或末端值相关联的其它信息，例如，寄存器或者函数或表达式的 名称。

通常，为了访问或者处理已经被存储在寄存器中的值，可能不需要设 备来花费任何资源。因此，各个方面语法可以包括用于引用寄存器的、以 及可以与零(0)开销相关联(即，这样的语法规则可以不具有开销)或者 可以不与零(0)开销相关联的规则。在各个方面中，DAG叶节点通常可 以是末端(例如，整数)或者非末端。

规则304-306中的每一个规则可以与可能非常适合于在辅助处理器(例 如，DSP)上执行的方法或其它操作相关联。例如，第一规则304(即，“[r]” 规则)可以与“array_copy(数组复制)”操作相关联，当在DSP上被执行 时，所述“array_copy”操作具有某个开销。这样的操作可以是用于将被存 储在数组数据结构内的特定索引处的值(例如，整数)复制到该数组数据 结构的另一个索引中的函数或例程。第二规则306(即，“[r’]”规则)可以 与索引表达式相关联(例如，结合数组数据结构使用的整数索引值)，并且 可以具有另一个相关联的开销。

如上所述，输入代码可以是包括各种功能的软件指令，例如，源代码 或二进制代码。例如，输入代码可以包括数学运算，例如，用于将被存储 在寄存器中的两个值相加以存储在另一个寄存器中的运算。关于图3，用于 与语法300一起使用的示例性输入代码可以是用以将数组的元素从一个索 引复制到另一个索引的代码(即，数组复制函数)。例如，输入代码可以是 由“A[6]＝A[5]”表示的操作，其中‘A’可以是数组变量名。用于识别该 数组分配函数的模式可以不被表达为简单的树，这是由于输入代码的特定 要素可以被连接到一个以上的其它节点(例如，共享的节点)。因此，输入 代码可以用输入DAG来表示。在一个方面中，解析器函数可以将“A[6]＝ A[5]”操作转换成下面的操作集：array_copy＝store(array_base,index_expr, load(array_base,index_expr))，其中‘array_copy’是已知的函数，‘store(存 储)’是用于将值存储或保存在特定位置(例如，与某个数组索引相关联的 存储器位置)中的已知的函数，‘array_base’表示与数组数据结构有关的存 储器位置，‘index_expr’是对数组索引进行寻址的指示，以及‘load(加载)’ 是使存储的值可访问的已知的函数，例如，通过将存储的值放在寄存器中。 计算设备可以将这样的示例性输入代码转换成输入DAG320。

输入DAG320可以包括节点322-330，其表示如用于完成输入代码所 需要的由解析器识别的操作和要素的集合。特别地，输入DAG320可以包 括：表示第一‘index_expr’元素(例如，数组索引‘5’)的第一节点324、 表示第二‘index_expr’元素(例如，数组索引‘6’)的第二节点326、表 示‘array_base’元素(例如，‘A’数组在计算设备存储器中的位置)的第 三节点322、表示‘load(加载)’函数的第四节点328、以及表示‘store (存储)’函数的第五节点330。第三节点322可以是共享节点，这是由于 其具有至第四节点328和第五节点330二者的连接(或边)。换言之，对于 “A[6]＝A[5]”的示例性输入代码而言，可能需要单个的‘load’和‘store’ 函数二者来访问数组‘A’，以分别对值进行加载和存储。

如上所述，可以将输入DAG320与语法300进行比较。特别地，计算 设备可以识别出：第一节点324与第二规则306(即，“[r’]”)相匹配，第 二节点326也与第二规则306(即，“[r’]”)相匹配，以及输入DAG的整个 模式(即，所有节点322-330)与第一规则304(即，“[r]”)相匹配。在各 个方面中，输入DAG320要素与语法300的匹配可以包括：将节点类型以 及还有节点之间的连接进行匹配(即，确认要素之间的正确的共享)。基于 这些匹配，计算设备可以确定输入DAG320的要素的累积效应，以及因此 在辅助处理器上执行的输入代码的开销或利益。出于非限制性说明的目的， 基于图3的任意开销值：计算设备可以确定与第二规则306相匹配的两个 节点均与开销一(1)相对应，并且整个输入DAG320的匹配与开销十(10) 相对应，达总开销十二(12)。

图4示出了用于计算设备基于DAG模式匹配来选择用于从CPU或应 用处理器卸载到辅助处理器的代码的方面方法400。方法400可以被视为上 面参照图1-2描述的方面方法的详细的实现方式。

在框402中，计算设备可以定义与已知非常适合于辅助处理器(例如， DSP、GPU等等)的函数有关的语法。该语法可以包括存储的集合、表格 或者规则的数据库，它们与非终结符、操作数和/或具有相关联的开销度量 的DAG模式相对应。例如，该语法可以包括规则，所述规则包括与已知非 常适合于DSP的快速傅里叶变换(FFT)函数有关的开销或利益度量以及 相关联的DAG模式。这样的语法可以是预先确定的，并且被加载或以其它 方式被存储在计算设备上。

在框404中，计算设备可以生成输入代码的下一个部分的DAG中间表 示。例如，计算设备可以生成针对应用内的方法的DAG。当第一次执行方 法400时(即，第一次迭代)，下一个部分可以是输入代码内的代码的第一 部分。在一个方面中，计算设备可以利用模块、例程、软件或其它指令来 将输入代码划分成方法或者其它的操作码块。此外，计算设备可以执行用 于从所生成的DAG中去除环的操作，例如，当输入代码是循环时。在各个 方面中，计算设备可以对输入代码进行划分，以使DAG表示操作循环(例 如，‘for’循环等等)的代码。例如，计算设备可以只执行方法400来确定 输入代码的方法中的循环是否非常适合于在辅助处理器上执行。

在框406中，计算设备可以将所生成的DAG的节点与所定义的语法模 式进行比较，以识别匹配。例如，计算设备可以将所生成的DAG的被存储 在计算设备的寄存器中的输入值(例如，整数、浮点值等等)与在语法的 规则中定义的结构进行比较。所比较的节点可以是所生成的DAG内的叶节 点、根节点、以及其它节点的组合。在各个方面中，针对方法400的每一 个循环的所比较的节点可以是所生成的DAG的子集、所生成的DAG的预 先确定数量的节点、或者经由边连接的节点的组合(例如，与所生成的DAG 内表示的子例程或子函数有关的节点)。例如，与框406中的操作相比较的 节点可以是所生成的DAG的节点的集合，其与‘load’函数或者‘store’ 函数(例如，表示数组的节点、表示索引表达式的节点、以及‘load’函数 节点)相对应。替代地，可以在逐节点的基础上进行比较(例如，将叶节 点与语法中的单个节点模式进行比较等等)。

此外，由于DAG利用节点之间的有向连接(例如，节点之间的有向边)， 因此识别匹配模式可能仅仅在所生成的DAG的节点与语法的模式相匹配 时发生，所述语法的模式具有相同的节点(例如，被连接到另一种类型的 另一个节点的某种类型的两个叶节点)配置和节点之间相同的边方向。换 言之，模式匹配可以在所生成的DAG的节点类型和连接二者与语法相同时 发生。因此，当所生成的DAG中的节点是共享的时(即，该节点是对于一 个以上节点的输入)，计算设备还可以对边方向进行比较，以确认任何匹配 语法模式包括针对相应的节点的相同的边方向。例如，计算设备可以确定 来自所生成的DAG的节点的组合和语法内的匹配模式是否共享匹配节点 之间的相同的边方向。这可以被认为关于所比较的节点，对所生成的DAG 进行重新遍历。

框406中的操作可以与上面参照图1-2描述的框104和252中的操作相 类似。例如，计算设备可以识别在所定义的语法模式和所生成的DAG内的 叶节点(例如，整数节点、寄存器节点等等)之间是否存在任何匹配。此 外，框406中的操作可能不需要由代码开发者提供任何手动的指示(即， 该比较可以是自动的)。

在判断框412中，计算设备可以基于比较来确定在所生成的DAG的节 点和所定义的语法模式之间是否存在任何匹配。例如，计算设备可以确定 所生成的DAG的叶节点是否与语法的规则内的任何模式/节点类型相匹配。 如上所述，该语法可以包括多种模式(例如，叶节点和根节点)，其表示不 同的配置，但是仍然可以与DAG中的某种操作和/或各种操作(例如，移 位、加载等等)相匹配。例如，计算设备可以将DAG(或者DAG的子集) 与该语法进行比较，并且识别该语法内匹配的若干DAG模式。

如果基于比较不存在匹配(即，判断框412＝“否”)，则计算设备可以 继续判断框416中的操作。

在可选的方面中，如果基于比较不存在匹配(即，判断框412＝“否”)， 则计算设备可以继续判断框426中的操作。换言之，当任何节点或者节点 的组合不能与所定义的语法内的模式匹配时，计算设备可以确定输入代码 的当前部分不能被卸载到辅助处理器，并且可以继续下一个部分(如果有 的话)。

但是，如果基于比较存在至少一个匹配(即，判断框412＝“是”)，则 在框414中，计算设备可以选择具有最佳利益或开销的匹配模式。换言之， 当所生成的DAG的当前节点或者节点的子集与语法内的多种DAG模式相 匹配时，计算设备可以挑选具有最低开销或最高利益的匹配语法模式。例 如，计算设备可以将与该模式匹配相关联的开销和语法内定义的开销进行 比较，并且可以选择具有最低开销的模式。替代地，基于所定义的语法内 的信息，计算设备可以评估与匹配模式相关联的任何利益，并且可以选择 具有超过其它匹配模式中的任何一种模式的开销的利益的模式。例如，计 算设备可以选择已知尤其非常适合于辅助处理器的匹配模式，例如，该模 式由于DAG的节点的配置而具有非常低的开销或某种附加的利益。如上所 述，可以关于每一种模式来将针对语法内的模式(或规则)的开销或利益 存储在诸如关系数据库或其它数据结构内。在一个方面中，计算设备可以 诸如通过将匹配模式的标识、指令的开销、或者在框418中的操作中可以 访问和使用的其它标识信息存储在数据结构中来存储用于指示所选择的具 有最佳效果的匹配模式的信息。

在判断框416中，计算设备可以确定是否已经对整个生成的DAG进行 了评估。例如，当已经利用框406中的操作只将所生成的DAG的节点的子 集与语法进行比较时，计算设备可以继续遍历所生成的DAG，直到已经对 整个代码部分进行了评估为止。在各个方面中，所生成的DAG的根节点可 以表示：输入代码内被用来生成该DAG的最终的或末端的操作、步骤、指 令或连接器。

如果尚未对整个生成的DAG进行评估(即，判断框416＝“否”)，则 计算设备可以通过在框406中，将所生成的DAG的更多节点与语法模式进 行比较来继续对代码的其余部分进行评估。以这种方式，计算设备可以迭 代地评估针对输入代码的部分所生成的DAG的节点中的所有节点。

当已经对整个生成的DAG进行了评估时(即，判断框416＝“是”)， 在框418中，计算设备可以识别该输入代码部分针对辅助处理器的累积效 应(例如，利益或开销)。例如，计算设备可以基于与该DAG相匹配的语 法的单个模式的开销度量来确定组合的开销。计算设备可以通过将针对所 生成的DAG内的每一个单个部分识别的开销和/或利益进行相加来识别该 累积效应，并且框418中的操作可以包括：访问和组合在框414的操作期 间存储的数据。在判断框420中，计算设备可以确定该累积效应对于辅助 处理器(例如，DSP、GPU等等)是否有好处。在一个方面中，计算设备 可以将如在框418中识别的累积利益或开销与被存储在该计算设备中的预 定义的门限值进行比较。在另一个方面中，当所生成的DAG被完全地覆盖 时，计算设备可以确定输入代码的该部分对于辅助处理器是有好处的。换 言之，在当前DAG内的所有节点或节点的组合与所定义的语法内的模式相 匹配时，计算设备可以确定有关的代码部分适合于卸载。如果累积效应对 于辅助处理器有好处(即，判断框420＝“是”)，则在框424中，计算设备 可以将输入代码的该部分从CPU或应用处理器卸载到辅助处理器。

如果计算设备确定累积效应对于辅助处理器没有好处(即，判断框420＝ “否”)，或者如果该部分被卸载，则计算设备可以在判断框426中确定是 否存在更多的代码部分要评估。例如，当计算设备被配置为在逐个方法的 基础上对输入代码进行解析时，计算设备可以迭代地执行框404-424中的操 作，直到已经对输入代码的全部进行了评估为止。如果存在更多的输入代 码部分(即，判断框426＝“是”)，则计算设备可以继续框404中的操作。 当不存在更多的输入代码部分时(即，判断框426＝“否”)，方法400可以 结束。

图5示出了适合于与各个方面一起使用的示例性语法500以及与输入 代码有关的输入DAG550。图5的示例性语法500包括可以与输入DAG550 的各种模式和节点相匹配的众多规则504-514。模板项502可以示出语法500 内的规则的结构。第一规则504(即，“[r0]”规则)可以与用DAG模式“S” 表示的节点或节点的组合相关联，第二规则506(即，“[r1]”规则)可以与 用DAG模式“A”表示的节点或节点的组合相关联，第三规则508(即，“[r2]” 规则)可以与用DAG模式“B”表示的节点或节点的组合相关联，第四规 则510(即，“[r3]”规则)可以与用DAG模式“C”表示的节点或节点的 组合相关联，以及第五规则512(即，“[r4]”规则)可以与用DAG模式“D” 表示的节点或节点的组合相关联。与规则504-512相关联的DAG模式可以 表示各种节点类型和/或操作(例如，整数、寄存器、‘加载’、‘存储’、‘加’ 等等)。另外，规则506-512均可以具有第一开销，以及规则504可以具有 第二开销。

但是，第六规则514(即，“[r’]”规则)可以与DAG模式相关联，所 述DAG模式是DAG模式的针对规则506-512的组合(例如，DAG模式“A”、 “B”、“C”和“D”的组合)。例如，第六规则514可以与特定的代码循环 (例如，‘loop_a’)相对应。虽然第六规则514包括这些DAG模式中的所 有DAG模式，但是针对第六规则514的开销可能非常低(即，低于与针对 “A”、“B”、“C”和“D”的单个规则相关联的开销的组合)。这可能是辅 助处理器特别好地执行某种操作组合时的情形，并且因此当输入代码包括 该组合时获得极大的利益。

输入DAG550示出了用于指示与DAG要素相匹配的最佳规则的注释。 特别地，当计算设备执行如上面参照图1、图2或图4描述的方面方法时， 节点552、562和564均可以与第一规则504(即，“[r0]”)相匹配。但是， 节点554、556、558和560可以共同地与第六规则514(即，“[r’]”)相匹 配。换言之，虽然节点554-560可以分别地与对应于某个累积开销的规则 506-512相匹配，但是计算设备可以识别：可以对节点554-560进行组合， 以匹配对应于更低开销(或更高利益)的第六规则514的模式。出于非限 制性说明的目的，基于图5的任意开销值，可以将与节点552、562和564 相关联的对应于第一规则504的开销与对应于第六规则514的开销组合， 以发现对应于输入DAG550的总开销十(10)。

图6是适合于与各个方面一起使用的智能电话型移动计算设备600的 系统框图。该智能电话移动计算设备600可以包括耦合至内部存储器602、 显示器603和至扬声器654的处理器601。该智能电话移动计算设备600还 可以包括诸如数字信号处理器或DSP606之类的辅助处理器。在各个方面 中，DSP606和处理器601可以诸如经由内部总线或作为片上系统设计的一 部分被连接。另外，该智能电话移动计算设备600可以包括天线604用于 发送和接收电磁辐射，所述天线604可以被连接到无线数据链路和/或远程 无线信号收发机605(诸如蜂窝网络或WiFi无线电装置)，所述远程无线信 号收发机605被耦合到处理器601并且能够通过广域无线通信网络进行通 信。在一个方面中，天线604还可以被耦合到DSP606。智能电话移动计算 设备600可以包括单独的短程无线收发机624，其能够与其它移动计算设备 进行通信或配对。智能电话移动计算设备600通常还可以包括用于接收用 户输入的菜单选择按钮或者摇杆开关608。另外，该智能电话移动计算设备 600可以包括耦合到处理器601和/或DSP606的加速计610、陀螺仪611 和GPS接收机芯片614。在一个方面中，该智能电话移动计算设备600还 可以包括耦合到处理器601和/或DSP606的麦克风612和照相机613。在 另一个方面中，该智能电话移动计算设备600还可以包括其它辅助处理器， 例如，图形处理单元(未示出)。

处理器601和606可以是能够由软件指令(应用)来配置以执行各种 各样的功能(其包括上面描述的各个方面的功能)的任何可编程的微处理 器、微计算机或多个处理器芯片或数个芯片。在各个设备中，处理器601 和606可以专用于特定的指令、软件、命令或其它用途。例如，一个处理 器可以专用于无线通信功能，以及一个处理器可以专用于运行其它应用。 通常，在访问软件应用并且将其加载到处理器601和606之前，可以将软 件应用存储在内部存储器602中。处理器601和606可以包括足以存储应 用软件指令的内部存储器。在很多设备中，内部存储器可以是易失性存储 器或者非易失性存储器(例如，闪存)、或者二者的混合。出于该描述的目 的，对于存储器的一般提及指代由处理器601和606可访问的存储器，包 括内部存储器或者被插入到各个设备中的可移动存储器、以及处理器601 和606内的存储器。

前述方法描述和过程流程图仅仅作为说明性的示例而提供，并不旨在 要求或者暗示必须以呈现的顺序来执行各个方面的步骤。如将由本领域技 术人员意识到的，可以以任何顺序来执行前述方面中的步骤的顺序。诸如 “其后”、“然后”、“接着”等等之类的词语不旨在限制步骤的顺序；这些 词语仅仅被用来引导读者从头到尾阅读该方法的描述。此外，任何对权利 要求要素的单数提及，例如，使用冠词“一(a)”、“一个(an)”或者“所 述(the)”不应当被解释为将该要素限制为单数形式。

结合本文公开的方面描述的各种说明性的逻辑框、模块、电路和算法 步骤可以被实现为电子硬件、计算机软件或二者的组合。为了清楚地说明 硬件和软件的这种可交换性，上面已经对各种说明性的部件、框、模块、 电路和步骤围绕其功能进行了总体描述。至于这样的功能是被实现为硬件 还是软件，取决于特定的应用和施加到整个系统上的设计约束。熟练的技 术人员可以针对每个特定的应用，以变通的方式实现所描述的功能，但是， 这样的实现决策不应当被解释为导致背离本发明的范围。

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

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

为了使得本领域的任何技术人员能够实现或者使用本发明，提供了所 公开的方面的先前描述。对于本领域技术人员来说，对这些方面的各种修 改是显而易见的，并且本文定义的一般原理可以在不背离本发明的精神或 范围的情况下被应用于其它方面。因此，本发明不旨在被限定到本文示出 的方面，而是要符合与所附权利要求书和本文公开的原理和新颖性特征相 一致的最宽的范围。