基于循环分割或索引阵列的循环并行化

摘要

描述了基于循环分割和/或索引阵列来提供循环并行化的方法和装置。在一个实施例中，基于误推测信息，生成与原始循环相对应的一个或多个分割循环。在其它实施例中，基于索引阵列，从原始循环中生成多个子循环。此外，还描述了其它实施例。

说明书

技术领域

概括地说，本发明涉及计算领域。具体地说，本发明的实施例涉及基 于循环分割和/或索引阵列的循环并行化。

背景技术

一种增加运算速度的方式是使用并行化。具有不规则的控制流或数据 流的大量现实世界的应用，由于它们的不规则控制流和数据流通常可能不 是编译时间可分析的，故而对于最先进优化编译器的逐步提高施加了一些 挑战。这随后可能禁止或者减少了诸如并行化和向量化之类的重要循环优 化。

关于对于具有这种不规则控制流和/或数据流的循环进行并行化的传统 常识，主要聚焦于消除或减少承载循环的控制流或数据流依赖。因此，关 于如何针对诸如并行化、向量化、循环分布和融合之类的通用循环优化来 有效地实现控制和数据推测的问题仍然是开放的。

附图说明

参照附图提供了具体实施方式。在附图中，附图标记的最左侧数字标 识该附图标记第一次出现的附图。在不同的附图中使用同一附图标记指示 类似或者相同的项。

图1示出了根据一个实施例的流程图。

图2-8示出了根据一些实施例的示例性伪代码。

图9和图10示出了计算系统的实施例的框图，其中这些计算系统可以 用于实现本申请所讨论的一些实施例。

具体实施方式

在下文的描述中，为了提供对于各个实施例的透彻理解，阐述了众多 特定的细节。但是，可以在不使用这些特定细节的情况下，实现本发明的 各个实施例。在其它实例中，没有详细地描述公知的方法、过程、组件和 电路，以避免造成本发明的这些具体实施例的模糊。此外，可以使用各种 方式来执行本发明的实施例的各个方面，例如，集成半导体电路（“硬件”）、 组织到一个或多个程序中的计算机可读指令（“软件”）、或者软硬件的某种 结合。为了本发明的说明目的，对于“逻辑”的引用应当意味着硬件、软 件（其包括例如对处理器的操作进行控制的微代码）或者其某种结合。

本申请所讨论的一些实施例可以提供基于循环分割和/或索引阵列的循 环并行化。如上所述，关于如何针对诸如并行化、向量化、循环分布和融 合之类的通用循环优化来有效地实现控制和数据推测的问题仍然是开放 的。为此，在一个实施例中，可以基于循环分割来实现循环并行化。在一 些实施例中，编译器构架可以扩展到对控制和数据推测进行统一，其能实 现更多的循环优化（特别是并行化）。此外，循环分割技术（例如，基于误 推测驱动的循环分割）可以允许对更多的循环进行推测性地优化。此外，（缓 慢的）检查代码生成方案可以实现后面的分析和优化，而无需进行任何改 变来适应推测信息。

另外，为了提高速度，一些处理器可以使用多个/很多处理核。通常， 为了充分利用多/众核体系架构，代码必须并行地执行。编写并行程序可能 是一项困难的任务，因此程序/应用通常在本质上是串行的。对于不具有数 据依赖的循环来说，针对并行化有益的代码段，可以使用自动并行化。这 对于不具有数据依赖的循环来说，通常是成立的。对于具有数据/控制依赖 的循环进行自动并行化是一个困难的问题。

在一个实施例中，对于具有某些类型的数据/控制依赖的循环进行自动 并行化的问题（它们是通常遇到的），可以基于索引阵列来解决。在一些实 施例中，索引阵列可以（例如，由编译器）生成，并用于对迭代空间进行 划分（和可能的重新排序），以便对循环进行并行化/优化。例如，可以在编 译时间执行数据/控制流分析（以及编码转换），而在运行时生成迭代子空间 的值（例如，通过预计算循环）。这提供了打破控制/数据流依赖并实现更多 的循环优化（例如，并行化）的通用技术。在一个实施例中，不需要简档 信息，但为了效率起见，可以使用该信息。因此，实施例可以使用软件只 运行时检验，而不需要任何特殊的硬件支持。

通常，当前实现不能容易地应用于包含不规则控制和/或数据流的循环。 例如，考虑从工业标准基准SPEC CPU2006/454.calculix中提取的下面热点 循环：

上面的循环不能并行化，这是由于编译器分析假定指针a、c和sum指 向相同的指向集合（point-to set），在该循环中可能发生分支。但是，如果 可以推测性地忽略表达式*a、*c和*sum之间的依赖，假定条件表达式!f[i] 始终为FALSE，则可以对该循环进行并行化。因此，编译器可以生成两个 版本的循环，一个是并行版本和一个是串行版本。为了保证程序在运行时 的正确性，生成了检查循环，以判断这些指针是否混淆（aliased），以及是 否发生分支。如果证明这些表达式是独立的，并且在运行时从未发生分支， 则可以替代串行版本来执行并行版本。

图1示出了根据一个实施例的推测循环并行化的构架的流程图。在一 个实施例中，扩展的编译器构架例如使用软件推测方法，支持控制和数据 推测来实现相对积极的循环优化。

此外，可以将循环并行化划分成两个阶段：分析阶段和转换阶段。分 析阶段基于控制和数据依赖信息，识别循环并行化机会。如果确定一个循 环是可并行化的，并适合于并行化，则所述转换修改内部表示（IR）以生 成并行化的代码。如本申请所讨论的，如果对一个循环进行并行化将导致 加速（例如，更短的执行时间），则认为该循环是适合于并行化的。

参见图1，编译器构架包括下面操作。在操作102处的程序输入之后， 在操作104，编译器通过对控制和数据（依赖）信息进行分析（例如，基于 优化启发信息和/或简档信息的编译器分析），识别/选择被确定为适合于推 测并行化的循环（嵌套）。在操作106，编译器在早期编译器阶段，生成用 于所选定/识别的循环嵌套的推测循环占位符。在一个实施例中，编译器使 用启发规则和/或简档信息通过消除一个或多个高度不可能发生的分支来对 程序进行调整，并在优化时忽略低概率数据依赖，来（例如，推测性地） 更新用于推测占位符的控制和数据依赖图。

在一个实施例（例如，在操作106）中，编译器生成一个或多个推测防 护，以便保存随后可以用于促进检查代码的生成的推测信息。在一个实施 例中，随后通过推测防护应用后期阶段的编译器分析和转换，而无需进行 任何改变来适应推测信息。在操作108，编译器执行感应变量分析，其可以 用于寻找每一个循环中的所有感应变量，执行所需要的转换和替代。在操 作110，可以使用包括循环分布、循环互换、循环融合等等的一套循环优化 技术。

在操作112，编译器评估/判断目标循环（例如，在操作104处选定/识 别的循环）是否适合于生成检查代码。如果其是有益的（如操作114处所 确定的），则在操作116，生成（和执行）基于推测防护的运行时检查代码， 例如以便针对控制和数据推测收集/确定统一的误推测信息。在一个实施例 中，使用推测信息和/或误推测信息来更新针对推测占位符的控制表达式。 在一些实施例中，针对少量的误推测的情况（例如，与某个门限值相比）， 编译器还生成一个或多个分割循环（与操作104的选定/识别的循环相对 应）。在与原始选定/识别的循环相比时，这些分割循环（它们可以获得通过 执行所选定/识别的循环所导出的结果）可以具有不相交索引集、更少的分 支、和/或更少的循环承载的依赖。因此，在操作120，对在运行时不具有 误推测的循环进行安全地并行化。编译器基于简档和/或简单的编译器启发， 选择适合于推测并行化的循环（嵌套）。如果针对推测占位符的循环被认为 是不进行并行化，则在操作122，将其消除为死代码。

在一些实施例中，可以使用下面中的一个或多个来提供高效的并行化： （A）（缓慢）检查代码生成的方案；（B）基于推测防护的检查代码生成伪 代码（例如，当使用编译器生成的检查代码来针对数据和控制推测，收集 统一的误推测信息时）；（C）针对少量的误推测的情况，基于统一的误推测 信息进行的误推测驱动的循环分割。

参照缓慢的检查代码生成，传统的循环多版本技术可以依靠单一编译 器阶段来生成循环的多个版本、检查代码和分支检查代码，其选择要在运 行时执行的原始循环或优化的循环。图2示出了根据一些实施例用于循环 （a）的两个循环版本（其标记为循环（b）和循环（c））的一个示例。在一 个实施例中，在不同的编译器阶段，对多版本循环和检查代码的生成进行 解耦和执行。仅当可以对推测循环版本进行并行化，并且其适合于生成检 查代码（例如，如参照图1所讨论的），才生成检查代码。如果对检查代码 进行早期地生成，则那些生成的代码可能增加编译时间，禁止后面的分析 和优化。

给定被确定为适合于推测并行化（例如，基于简档和编译器启发）的 循环，编译器在早期编译器阶段生成两个版本的循环，其中一个版本是推 测的循环占位符（例如，循环（c）），另一个版本是原始版本（例如，循环 （b））。可以使用控制和数据推测来更新推测的版本的控制和数据依赖。在 同一时间，可以引入推测防护来保存推测信息。如果确定要稍后对推测的 版本进行并行化，则在发生转换之前，编译器生成检查代码。否则，将推 测的版本消除为死代码。

在一个实施例中，在图2循环（c）中示出了使用基于软件推测的循环 并行化语义来进行推测循环占位符生成（例如，作为if-then-else控制流结 构）。If条件语句检查该推测是否是成功的。如果其是成功的，则将执行推 测的版本。否则，将执行原始的版本。由于误推测必须是很少的以使得推 测是值得的，因此将if条件被设置为高度可能发生的。基于这种显式表示， 稍后的分析和优化可以将其处理成任何其它高度偏置的if块。在这些分析 和优化期间，不需要对推测代码与非推测代码进行区分。

参照推测防护生成，在编译器分析中，可以通过检查程序控制结构并 基于边缘/路径简档和启发式规则对可能的执行路径进行估计，来支持控制 推测。可以对尝试并入控制推测的优化进行修改，了解这种注释控制推测 信息。此外，可以通过依赖图中的推测依赖边缘或者推测性弱更新，对数 据推测信息进行显式地注释。可以对尝试并入数据推测的优化进行修改， 以处理注释的推测信息。

在一个实施例中，通过将高度不可能发生的分支假定为错误，消除这 些分支，并重建控制流图，来将控制推测信息综合到控制流图中。在一些 实施例中，可以通过边缘/路径简档和/或编译器启发，来获得这些分支的概 率。可以通过一组预测性启发来执行针对这些分支的概率的静态估计，其 中这些预测性启发认识到该程序的控制流图中的频繁满足的构建。例如， 对于每一个分支，这种启发预测一个分支高度地可能发生（不发生），或者 简单地放弃。在一个实例中，预测发生循环分支，这是由于与从循环中退 出相比，循环继续更可能发生。可以基于所述一组启发来对其它分支进行 估计；例如，要向其传送控制的控制块是否包含函数调用等等。如果大部 分启发不起作用，则分支预测可以是接近于90/50，其不提供用于选择一种 或另一种执行方式的理由。此外，还可以使用边缘/路径简档来提供这种概 率性信息。假定处理的分支的条件表达式是具有非线性阵列表达式形式的 循环变量。在一些实施例中，为了稍后生成检查代码，该条件表达式不具 循环承载的数据依赖。如果条件表达式是线性的或者循环不变的，则可以 将其视作为极端情形。

在一些实施例中使用的两个简单启发规则如下所述：（1）其主体包含 异常控制流语句（其包括“返回”、“中止”、“退出”或者“中断”）的分支， 被识别为高度不可能发生的；或者（2）其主体只包含语句“继续（continue）” 的分支，被识别为高度不可能发生的。

由于可以在编译器阶段的更晚处生成检查代码，可以向循环应用一套 循环优化（其包括循环互换、循环分布等等），因此生成检查代码不是微不 足道的。为此，可以引入推测防护以保存推测信息。由于循环并行化需要 上面的情形1中的推测应当对于每一次迭代都是成功的，同时在上面的情 形2中允许少数量的误推测，因此引入了与这两种情形相对应的两种类型 的推测防护。在图3（a）中，循环之中的循环变量分支条件!a[i]禁止该循 环并行化。对该分支进行推测性地消除，可以使该循环可并行化。由于条 件!a[i]很可能为FALSE，因此编译器将该if条件用0进行替代，插入推测 防护ctrl_guard_false以指示该推测对于每一次迭代都需要成功。推测防护 的参数a[i]可以帮助编译器容易地生成检查代码。图3（c）示出了允许少数 量的误推测的不同场景。

在一个实施例中，引入了与该情形相对应的另一个推测防护 ctrl_guard_maybe_false，如图3（d）中所示。此外，可以通过在优化时忽 略低概率的循环承载的数据依赖，将数据推测并入到推测数据依赖分析中。 此外，还可以通过数据依赖简档或编译器启发，获得数据依赖边缘的概率。 使用一些简单的编译器启发规则来识别非常不可能依赖的内存引用。

例如，在一些实施例中，可以忽略下面四种情形中的循环承载的依赖。 给定以循环索引i1开始的循环嵌套，线性阵列下标具有 a1*i1+a2*i2+…+an*in的形式，其中i1、i2、…、in是循环索引变量，a1不 等于0。

情形1：在具有线性阵列下标的存储和具有非线性阵列下标的装载之间 的循环承载的依赖边缘；

情形2：在具有非线性阵列下标的存储和具有线性阵列下标的装载之间 的循环承载的依赖边缘；

情形3：在具有非线性阵列下标的存储和具有非线性阵列下标的装载之 间的循环承载的依赖边缘；

情形4：在具有非线性阵列下标的存储和具有非线性阵列下标的其它存 储之间的循环承载的依赖边缘；

在一些实施例中，循环并行化针对情形2、3和4，使用对于每一次迭 代来说都成功的数据推测，对于情形1，允许少量的误推测。推测防护可以 用于不同的情形，使得可以以更加直接的方式来生成运行时检查代码。在 数据依赖分析以及阵列简化分析中，可以对所生成的推测防护进行特殊地 处理。例如，数据依赖分析将涉及推测防护的所有循环承载的数据依赖改 变为独立于循环的依赖。阵列简化分析可以减少涉及推测防护的所有边缘， 使得可以有效地认识简化候选。

图4（a）示出了表达式a[i]不可能与表达式a[b[i]]相重叠的循环。在一 个实施例中，编译器去除相应的循环承载的依赖边缘，插入新的固有a[b[i]] =data_guard_maybe_false(a[i])。图4（c）示出了表达式a[b[i]]与表达式c[i] 混淆的循环。可以忽略这种低概率依赖，因此将表达式a[b[i]]视作为阵列简 化候选，可以对该循环进行并行化。在缓慢的检查代码生成中，编译器插 入推测防护data_guard_false，以指示推测对于每一次循环迭代都应当是成 功的。在图4（c）中，在推测性地忽略a[b[i]]和c[d[i]]之间的依赖边缘之后， 将这两个表达式视作为阵列简化候选。

参照基于推测防护的检测代码生成，由于编译器在编译器阶段的早期 生成两个版本的循环，因此通过继续存在循环分析和优化，可以获得更多 的循环并行化机会，而无需进行任何改变来适应这种推测信息。如果不能 对推测的版本进行推测性地并行化，则编译器可以简单地将其去除为死代 码。否则，编译器针对每一个推测防护都生成检查代码，以便保证推测并 行化的循环的正确性。随后，在生成检查代码之后，从IR中删除这些推测 防护。检查代码在运行时收集的误推测信息可以用于选择正确的版本来执 行。在一个实施例中，使用统一的误推测信息对控制和数据推测进行建模。 如果需要推测在每一次迭代都成功，则一个误推测标志就可以表示误推测 信息。否则，可以使用误推测表来处理少数量的误推测的情形，其中误推 测表的大小等于循环次数计数值，误推测表中的每一个元素的值指示：针 对相应的迭代，该推测是否成功。

图5示出了根据一个实施例如何例如基于推测防护生成检测代码的伪 代码。图6列出了根据一个实施例如何生成用于不同的推测防护的检查代 码的示例。在编译器IR（中间表示）中，将违规的控制依赖表示成推测防 护ctrl_guard_false或者ctrl_guard_maybe_false。在图6（a）中，推测防护 ctrl_guard_false(a[i])假定：对于每一次迭代，表达式!a[i]都是false。在检查 循环生成中，构造误推测标志，以便当该推测始终是成功时，选择并行化 的版本。图6（b）示出了针对推测防护ctrl_guard_maybe_false(a[i])的检查 循环生成的示例，其中在该情况下，构造误推测表，以便记录发生了误推 测的迭代。此外，编译器还构造计数器mis_count来记录误推测的数量。用 于推测防护ctrl_guard_maybe_false(a[i])的误推测是：条件表达式a[i]为false。 类似地机制可以应用于违规的数据依赖。

在图6（c）中，推测防护a[b[i]]=data_guard_maybe_false(a[i])假定：阵 列引用a[i]和a[b[i]]是不可能依赖的。针对迭代i的误推测指代下面情形： a[i]和a[b[j]]存取相同的内存地址，其中在该情况下，表达式条件0<=i,j<n 保持。为了高效地收集误推测信息，编译器在一个实施例中构造256个条 目的地址表，例如，将地址&a[b[j]]使用成映射到该地址表中的条目里的一 个的键值。随后，对循环进行构造，以检测&a[i]是否映射到某个地址&a[b[j]] 已经映射到的某个条目。如果地址&a[i]和&a[b[j]]映射到了地址表中的同一 条目，则将该迭代i被表示为具有误推测。可以将误推测表的相应元素设置 为true。

此外，图6（d）中的推测防护e[i]=data_guard_false(a[b[i]])假定：表达 式a[b[i]]不可能与表达式e[i]混淆。由于表达式a[b[i]]是存储操作，因此编 译器可以检查形式为a[b[i]]=…的所有存储语句是否被标记为稀疏阵列简 化。如果不是，则根据一些实施例，编译器对针对多版本循环的条件表达 式进行重置，循环并行化将放弃该循环。否则，编译器生成一个循环，以 便收集针对引用a[b[i]]的所有限制信息。可以根据循环下限和上限，导出用 于引用c[i]的阵列限制信息。如果阵列段a和c彼此之间重叠，则将误推测 标志设置为true。

图6（e）示出了根据一个实施例的另一种情形，其中在该情形下，将 表达式a[b[i]]假定为与c[d[i]]混淆。如果稀疏阵列简化分析检测到表达式 a[b[i]]和c[d[i]]都是阵列简化候选，则编译器可以简单地在检查代码生成中 检查它们的结构（alignment）是否是相同，以替代生成一个循环来检测这 些阵列段是否彼此之间重叠。随后，其对误推测标志进行更新，使得当该 推测是成功时，可以执行推测并行化代码。

参照误推测驱动的循环分割，根据一个实施例，当确定要对推测的版 本进行并行化，并允许少量的误推测时，编译器生成用于进行进一步循环 分割的第三版本，如图7中所示。如果误推测的数量低于某个门限T，则编 译器假定推测的循环并行化是有益的。由于误推测表中的每一个元素的值 指示该推测在相应的迭代是否成功，因此可以基于误推测表，对循环进行 简单地分割。在一个实施例中，将循环分割成多个不相交循环，这些不相 交的循环具有更小的索引集。因此，在运行时不具有误推测的这些更小循 环被安全地并行化。根据一个实施例，图8示出了编译器如何生成用于对 图7中的循环（版本3）进行分割的代码。在图8中，编译器构造穿越误推 测表中的每一个元素的循环，计算不具有误推测的间隔。如果存在不具有 误推测的间隔，并且该间隔长度大于某个门限T1，则可以对用于该相应的 索引集的循环进行推测性的并行化。因此，编译器构造了具有该索引集的 如图8中所示的更小循环函数1，并从版本1（推测版本）中复制循环主体。 否则，编译器从版本2（原始版本）中复制循环主体，用于该更小循环函数 2，如图8中所示。

参照基于索引阵列的循环优化，实施例使用一种新方法来打破循环中 的控制和数据流依赖，例如为循环优化或自动并行化产生更多机会。如本 申请所讨论的，索引阵列是通过选择迭代集所构造的循环的迭代空间的一 个子集，其中所选定的迭代集拥有下面两种属性中的一种：（1）对于该给 定的迭代集，循环中的if条件始终是TRUE，而其它迭代集不是；或者（2） 对于该给定的迭代集，在循环中存在流或者逆向流依赖边缘，而其它迭代 集不是。此外，针对拥有属性1的迭代所构造的索引阵列，帮助打破循环 中的控制流依赖，而针对拥有属性2的迭代所构造的索引阵列，帮助打破 循环中的数据流依赖。在这两种情况下，可以通过基于索引阵列对迭代空 间进行划分（以及可能的重新排序），将原始循环转换成两个或更多循环（下 文的子循环），使得可以对一个或多个子循环进行并行化。这进而可以允许： （i）通过打破控制流和数据流依赖来实现更多的并行化，和/或帮助其它循 环优化（例如，软件管道化和冗余消除），而无需简档信息；（ii）最小运行 时开销；（iii）无需特殊的硬件支持。

由于控制或数据流依赖通常禁止并行化，因此一些实施例提供了在真 实应用和基准中频繁遇到的循环结构。例如，在循环中存在IF条件，则产 生控制流依赖，其禁止循环优化。下面是spec2006/462.libquantum中的热点 循环的简化版本：

由于（j=j+1;B[j]=C[i]..）是依赖于条件（A[i]!=0）的控制，因此该 循环不能并行化。一种克服该问题的方法是使用控制/数据流推测。但是， 在一些实现中，控制/数据流推测通常是不适用/无益的：若要转换是适用的 /有益的，if条件应当大部分情况下为TRUE或者大部分情况下为FALSE（在 大多情况下，始终为TRUE或者始终为FALSE）。此外，其依赖于简档信息， 而后者是非常受限的。但是，针对（A[i]!=0）为TRUE的迭代空间的子集， 是可并行化的。为此，实施例尝试识别和划分出该迭代子集。

参照禁止并行化的数据流依赖，下面是spec2006/482.sphinx3中的热点 循环的简化版本：

由于在A[i]和A[B[i]]之间存在数据依赖边缘，因此该循环不能并行化。 应当注意，range(B[i])<=range(i)，其中range(k)是k可以采用的值的集合， 迭代空间的子集（range(i)-range(B[i])）是可并行化的。在一个实施例中， 使用索引阵列来识别和并行化该迭代子集。致力于打破循环中的一个或多 个控制流和数据流依赖的索引阵列，用于实现更多的并行化。在一个或多 个实施例中，可以使用下面的项目：

I．当可以时，对用于打破控制流依赖的索引阵列进行构造的机制；

II．（使用索引阵列）对循环迭代空间进行划分（以及可能的重新 排序），以便打破控制流依赖的机制，其导致子循环的生成；

III．当可以时，对用于打破数据流依赖的索引阵列进行构造的机 制；和/或

IV．（使用索引阵列）对循环迭代空间进行划分（以及可能的重 新排序），以便打破数据流依赖的机制，其导致子循环的生成。

参照使用机制I、II、III、IV所获得的循环转换，根据一个实施例，下 面的伪代码旨在呈现该方法的高层级梗概，故省略了实际实现中所需要的 众多细节和合法性检验：

Control-And-Data-Flow-Analysis-For-Parallelization();//寻找控制和数据 流依赖//禁止并行化

当发现具有单一分支的if条件（其使得if条件的预测依赖于循环索引 变量）负责控制依赖时，可以触发用于控制流优化的索引阵列方法。

在一个实施例中，机制1（generate_controlflow_indexarray_loop(if_cond, tripcount(loop),&index_array)）针对索引阵列的构造，生成下面的预计算循 环：

因此，索引阵列可以存储if条件为TRUE的索引的集合。由于if条件 评估为FALSE的迭代的集合，不影响该循环之内的计算，因此可以对它们 进行丢弃。在一个实施例中，迭代空间的仅仅一个子集（如索引阵列中所 存储的）需要进行迭代。该子集是没有控制依赖的，并且可以并行化。

在一个实施例中，机制2（generate_controlflow_loop_transformation(loop, index_array)）通过使用相应的索引阵列元素替换索引变量的一个或多个出 现，去除if条件，使用索引阵列的大小来替换次数计数，来生成原始循环 的一个子循环。所获得的子循环在索引阵列（其是原始迭代空间的一个子 集）的元素之上进行迭代，该子循环是没有控制依赖的。

在一个实施例中，使用所述伪代码（机制1和2），将循环1转换成下 面代码：

当发现形式A[i]和A[B[i]]的阵列访问之间的数据依赖禁止并行化时， 可以触发用于数据流优化的索引阵列方法。B可以是调用的内部阵列。B[i] 是i的迭代空间的一个子集。该子集是存在数据依赖的迭代空间的子集。剩 余的迭代是可以变成没有数据依赖的，并可以并行化。随后，索引阵列可 以对B[i]获得的值进行存储。

在一个实施例中，机制3（generate_dataflow_indexarray_loop(inner_array, tripcount,&index_array)）针对索引阵列的构造，生成下面的两个预计算循 环：

在一个实施例中，机制4（generate_dataflow_loop_transformation(loop, index_array)）将原始的循环转换成两级的循环嵌套，其可以被认识为是可 并行化子循环的集合。外部循环在索引阵列的元素上进行迭代，而内部循 环在两个连续的索引阵列元素之间的间隔上进行迭代，其后跟着与索引阵 列的元素相对应的单一迭代。两个连续的索引阵列元素之间的每一个间隔 是没有数据依赖的，并可以并行化。此外，使用所述伪代码（机制3和4）， 将循环2转换成下面代码：

因此，一些实施例具有最小的运行时开销。在一个实施例中，可以通 过对循环次数计数值进行运行时检查，来保护基于索引阵列的转换。仅当 循环次数计数值与某个门限相比更高时，才执行转换的代码。如果在编译 时已知循环次数计数值，则编译时检查是足够的。关于索引阵列的大小的 运行时检查，可以用于进一步提高该方法的利益率。此外，如果简档信息 是可用的，则该方法可以仅应用于热点循环。

另外，可以将该伪代码推广到也处理具有两个分支的条件语句。例如， 如果两个分支在它们之间不具有数据依赖边缘，则可以将原始循环分布到 两个循环中，一个循环包含if条件和then分支的主体，另一个循环包含该 if条件的余集和else分支的主体。随后，如本申请所描述的伪代码可以单 独地应用于这两个循环，以便产生可并行化的子循环。此外，还可以将该 伪代码推广到处理多个if条件语句以及同一循环之中的多个数据依赖。这 涉及构造多个索引阵列，以及具有可能的一些显著运行时开销的复杂转换。

图9示出了计算系统900的实施例的框图。在各个实施例中，可以在 各种电子设备中提供系统900的组件中的一个或多个，其能够执行本申请 参照本发明的一些实施例所讨论的操作中的一个或多个。例如，系统900 的组件中的一个或多个可以用于执行参照图1-8所讨论的操作，例如，通过 根据本申请所讨论的操作来处理指令、执行子例程等等。此外，本申请（例 如，参照图9和/或10）所讨论的各种存储设备可以用于存储数据、运算结 果等等。

具体而言、计算系统900可以包括：通过互连网络（或总线）904进行 通信的一个或多个中央处理单元（CPU）902或者处理器。因此，在一些实 施例中，本申请所讨论的各种操作可以由CPU来执行。此外，处理器902 可以包括通用处理器、网络处理器（其对通过计算机网络903传输的数据 进行处理）或者其它类型的处理器（其包括精简指令集计算机（RISC）处 理器或复杂指令集计算机（CISC））。此外，处理器902可以具有单核或多 核设计。具有多核设计的处理器902可以将不同类型的处理器核集成到同 一集成电路（IC）芯片上。此外，可以将具有多核设计的处理器902实现 成对称或非对称多处理器。此外，参照图1-8所讨论的操作可以由系统900 的一个或多个组件执行。

芯片集906还与互连网络904进行通信。芯片集906可以包括图形和 内存控制中枢（GMCH）908。GMCH908可以包括与存储器912进行通信 的存储器控制器910。存储器912可以对数据进行存储，其中数据包括由 CPU902或者计算系统900中所包括的任何其它设备执行的指令序列。在 一个实施例中，存储器912可以存储编码器913，后者与参照图1-8所讨论 的编译器相同或者类似。可以将相同的数据（其包括指令）或者该数据的 至少一部分存储在磁盘驱动器928和/或处理器902之内的一个或多个高速 缓存中。在本发明的一个实施例中，存储器912可以包括一个或多个易失 性存贮（或存储器）设备，例如，随机存取存储器（RAM）、动态RAM （DRAM）、同步DRAM（SDRAM）、静态RAM（SRAM）或者其它类型 的存贮设备。此外，还可以使用诸如硬盘之类的非易失性存储器。另外的 设备（例如，多个CPU和/或多个系统存储器）可以通过互连网络904进行 通信。

GMCH908还可以包括与显示器916进行通信的图形接口914。在本发 明的一个实施例中，图形接口914可以通过加速图形端口（AGP）与显示 器916进行通信。在本发明的一个实施例中，显示器916可以是通过例如 信号转换器与图形接口914进行通信的平板显示器，其中信号转换器将诸 如视频存储器或系统存储器之类的存贮设备中保存的图像的数字表示，转 换成由显示器916进行解释和显示的显示信号。接口914所产生的显示信 号可以在由显示器916进行解释并随后显示之前，穿过各种控制设备。在 一些实施例中，处理器902和一个或多个其它组件（例如，存储器控制器 910、图形接口914、GMCH908、ICH920、外围桥接924、芯片集906等 等）可以提供在同一IC芯片上。

中枢接口918使GMCH908和输入/输出控制中枢（ICH）920能够进 行通信。ICH920可以向与计算系统900进行通信的I/O设备提供接口。ICH 920可以通过诸如外围组件互连（PCI）桥、通用串行总线（USB）控制器、 或者其它类型外围桥或控制器之类的外围桥（或者控制器）924与总线922 进行通信。桥924可以在CPU902和外围设备之间提供数据路径。也可以 使用其它类型的拓扑。此外，多个总线可以例如通过多个桥或控制器与ICH 920进行通信。此外，在本发明的各个实施例中，与ICH920通信的其它外 围设备可以包括集成驱动电子器件（IDE）或者小型计算机系统接口（SCSI） 硬盘驱动器、USB端口、键盘、鼠标、并口、串口、软盘驱动器、数字输 出支持（例如，数字视频接口（DVI））或其它设备。

总线922可以与音频设备926、一个或多个磁盘驱动器928以及网络接 口设备930进行通信，其中网络接口设备930可以与计算机网络903进行 通信。在一个实施例中，设备930可以是能无线通信的NIC。其它设备可 以通过总线922进行通信。此外，在本发明的一些实施例中，各个组件（例 如，网络接口设备930）可以与GMCH908进行通信。此外，可以对处理 器902、GMCH908和/或图形接口914进行组合，以形成单一芯片。

此外，计算系统900可以包括易失性和/或非易失性存储器（或者存贮 设备）。例如，非易失性存储器可以包括下面中的一个或多个：只读存储器 （ROM）、可编程ROM（PROM）、可擦除PROM（EPROM）、电EPROM （EEPROM）、磁盘驱动器（例如，928）、软盘、紧致碟ROM（CD-ROM）、 数字多用途光碟（DVD）、闪存、磁光碟、或者能够存储电子数据（例如， 其包括指令）的其它类型的非易失性机器可读介质。在一个实施例中，系 统900的组件可以用点对点（PtP）配置进行布置，例如，参照图10所讨论 的。例如，可以通过多个点对点接口，对处理器、存储器和/或输入/输出设 备进行互连。

具体而言，图10示出了根据本发明的一个实施例用点对点（PtP）配置 进行布置的计算系统1000。具体而言，图10示出了通过多个点对点接口， 对处理器、存储器和/或输入/输出设备进行互连的系统。参照图1-9所讨论 的操作可以由系统1000的一个或多个组件执行。

如图10中所示，系统1000包括一些处理器，为了清楚说明起见，仅 示出了其中的两个处理器1002和1004。处理器1002和1004均可以包括本 地内存控制器中枢（MCH）1006和1008（在一些实施例中，它们可以与图 9的GMCH908相同或者类似），以便与存储器1010和1012相耦合。存储 器1010和/或1012可以存储各种数据，例如参照图9的存储器912所讨论 的那些。

处理器1002和1004可以是任何适当的处理器，例如参照图10的处理 器1002所讨论的那些。处理器1002和1004可以分别使用点对点（PtP）接 口电路1016和1018，通过PtP接口1014来交换数据。处理器1002和1004 均可以使用点对点接口电路1026、1028、1030和1032，通过各自PtP接口 1022和1024与芯片集1020交换数据。此外，芯片集1020还可以使用PtP 接口电路1037，通过高性能图形接口1036与高性能图形电路1034交换数 据。

可以通过使用处理器1002和1004来提供本发明的至少一个实施例。 例如，处理器1002和/或1004可以执行图1-9的操作中的一个或多个。但 是，本发明的其它实施例可以存在于图10的系统1000之内的其它电路、 逻辑单元或设备中。此外，本发明的其它实施例可以分布在图10中所示的 一些电路、逻辑单元或设备之中。

芯片集1020可以使用PtP接口电路1041耦接到总线1040。总线1040 可以具有耦接到其的一个或多个设备，例如，总线桥1042和I/O设备1043。 通过总线1044，总线桥1043可以耦接到其它设备，例如，键盘/鼠标1045、 参照图10所讨论的网络接口设备1030（例如，可以耦接到计算机网络903 的调制解调器、网络接口卡（NIC）等等）、音频I/O设备和/或数据存贮设 备1048。数据存贮设备1048可以存储由处理器1002和/或1004执行的代 码1049。

在本发明的各个实施例中，本申请所讨论的操作（例如，参照图1-10 所讨论的操作）可以实现成硬件（例如，逻辑电路）、软件（例如，其包括 对处理器（例如，本申请所讨论的处理器）的操作进行控制的微代码）、固 件或者其组合，其中它们可以被提供成计算机程序产品，例如其包括有形 （例如，非临时性）机器可读介质或计算机可读介质，而这些介质存储有 用于对计算机（例如，计算设备的处理器或其它逻辑）进行编程以执行本 申请所讨论的操作的指令（或者软件过程）。所述机器可读介质可以包括存 贮设备，例如本申请所讨论的那些。

贯穿本说明书对于“一个实施例”或者“某个实施例”的引用意味着， 结合该实施例描述的具体特征、结构或特性包括在至少一个实现中。在贯 穿本说明书的各个地方中出现的短语“在一个实施例中”，可以全部指代同 一实施例，也可以并不都指代同一实施例。

此外，在说明书和权利要求书中，可以使用术语“耦接”和“连接” 连同它们的派生词。在本发明的一些实施例中，“连接”用于指示两个或更 多元件彼此之间直接地物理接触或者电接触。“耦接”可以意味着两个或更 多元件处于直接地物理接触或电接触。但是，“耦接”也可以意味着两个或 更多元件可以不处于彼此之间的直接接触，但彼此之间仍然能进行协作或 交互。

另外，可以将这种计算机可读介质作为计算机程序产品进行下载，其 中所述程序可以通过数据信号的方式，例如通过载波波形或者其它传播介 质，经由通信链路（例如，总线、调制解调器或者网络连接），从远程计算 机（例如，服务器）传送给请求的计算机（例如，客户端）。

因此，虽然本发明的实施例用特定于结构特征和/或方法动作的语言进 行了描述，但应当理解的是，本申请所要求保护的主题并不限于所描述的 特定特征或动作。相反，只是将这些特定特征和动作公开成用于实现所要 求保护的主题的示例形式。