Conversion of control dependence to data dependence

[ysh329]

J. R. Allen, Ken Kennedy, Carrie Porterfield, and Joe Warren. Conversion of control dependence to data dependence. In POPL, pages 177–189. ACM, 1983. https://dl.acm.org/doi/pdf/10.1145/567067.567085

1. 试图解决的问题：

文章解决的问题是如何将控制依赖（Control Dependence）转换为数据依赖（Data Dependence），以便在复杂的控制流情况下，能够更有效地进行程序分析和自动向量化。在存在复杂的控制流时，仅依赖数据依赖是不够的，因为控制依赖可能会引入循环，这些循环可能无法被向量化。

2. 论文的关键思想和关键见解：

关键思想：通过消除goto语句并引入逻辑变量，将所有的控制依赖转换为数据依赖。这样，语句间的控制依赖就变得显式，并可以通过控制逻辑变量的定义和使用来表达。 关键见解：文章提出了一种系统化的方法，将控制依赖转换为数据依赖，使得原本因控制流复杂而无法向量化的代码区域得以转换和向量化。

3. 关键机制及其实现：

IF转换（IF Conversion）：一种将控制流转换为基于条件的执行流程的技术。在IF转换中，所有的goto语句被消除，并通过逻辑变量来控制语句的执行。例如，原本通过goto实现的跳转，通过设置条件变量来实现相同的逻辑。 前向转换（Forward Conversion）：一种特殊类型的IF转换，它处理前向分支，即分支目标在分支语句之后。通过设置条件变量来控制语句的执行，从而消除goto语句。 分支重定位（Branch Relocation）：一种处理退出分支（exit branches）的技术，它通过引入退出标志（exit flags）和逻辑变量来重新组织程序流，确保在修改后的程序中仅在原始程序中会执行该语句时才执行。 前向分支（Forward Branch）：指分支目标在分支语句之后的控制流。例如，IF (condition) GOTO label，如果条件满足，则程序会跳转到label处执行。 后向分支（Backward Branch）：指分支目标在分支语句之前的控制流，这种分支会创建隐含的循环。由于它们不能直接被消除，需要特别的处理方法。

4. 主要结果和结论：

文章展示了IF转换算法在PFC（一个在莱斯大学开发的实验性向量化程序）中的实现，并证明了该算法能够处理复杂的控制流问题，使得原本无法向量化的代码区域得以转换和向量化。通过将控制依赖转换为数据依赖，PFC能够向量化包含条件转移的循环语句。此外，文章还讨论了布尔简化（Boolean Simplification）在IF转换中的应用，以及如何通过简化逻辑条件来提高输出程序的可读性。

最终，文章得出结论，IF转换是一个极其有价值的转换过程，它不仅对向量化有重要意义，还可以应用于数据流语言、代码结构化和goto消除等领域。它证明了在实际的程序转换系统中，任何分支构造都可以成功地转换为结构化构造。

关键词解释：

• 向量化（Vectorization）：一种程序优化技术，将标量操作转换为可以并行执行的向量操作，以提高性能。
• 控制依赖（Control Dependence）：当一个语句的执行流依赖于另一个语句的执行结果时，称这两个语句之间存在控制依赖。
• 数据依赖（Data Dependence）：当一个语句的执行需要另一个语句计算的数据时，称这两个语句之间存在数据依赖。

[ysh329]

摘要

程序分析方法，特别是那些支持自动向量化（Automatic Vectorization，一种编译器优化技术，它能够自动识别并转换程序中的循环或代码段，使其能够在向量处理器上并行执行，从而提高性能），基于语句间依赖的概念，当一个语句计算的值被另一个语句需要时，两个语句之间就存在依赖。基于这个概念，已经开发出了强大的程序转换系统，这些系统能够将顺序程序转换成更适合向量或并行机器的形式。

语句间依赖（Inter-statement Dependence）：在程序分析中，指一个语句的执行可能依赖于另一个语句的执行结果或计算值：

• 数据依赖（Data Dependence）：程序中一个操作需要另一个操作的数据作为输入，这种依赖关系限制了操作可以并行执行的方式。
• 控制依赖（Control Dependence）：程序的执行流程中的一个决策点（如条件语句）会影响其他语句的执行，这种依赖关系与数据流动无关，而是与控制流相关。

这些系统中的依赖分析是基于数据依赖的。在复杂控制流存在的情况下，仅仅数据依赖不足以转换程序，因为控制依赖的引入。当一个语句的执行可以阻止另一个语句的执行时，就存在控制依赖。控制依赖并不适合方便地融入基于依赖的程序转换器。

一种解决方案是通过消除goto语句（goto Statement，一种无条件跳转语句，允许程序流程从一个位置跳转到另一个位置，这可能会使得程序的控制流变得复杂）并引入逻辑变量来控制程序中语句的执行，将所有控制依赖转换为数据依赖。在这个方案中，动作语句被转换为IF语句。IF语句的条件表达式中的变量可以被视为控制被控制语句的输入。结果是，语句之间的控制依赖变成了通过控制逻辑变量的定义和使用明确表达的数据依赖。

本文提出了一种系统化的方法，以这种方式将控制依赖转换为数据依赖。这里介绍的算法已在PFC中实现，PFC是一个在莱斯大学编写的实验性向量化程序。

[ysh329]

这篇文章描述了一个名为PFC（Parallel Form Converter）的系统，它能够将用Fortran编写的顺序程序转换成Fortran 8x形式的并行程序。转换的核心思想是识别并替换循环（loops）为数组操作（array operations），以利用向量计算机和阵列处理器的能力。下面是PFC转换标量程序为向量程序的一般步骤，以及一个具体的Fortran代码示例和其转换过程：

转换步骤概述：

1. 子标标准化（Subscript Standardization）：将所有子标转换为循环变量的线性函数。
2. 依赖性测试（Dependence Testing）：检测循环中的语句是否依赖于自身，即是否在循环迭代中使用了之前迭代的结果。
3. 向量代码生成（Vector Code Generation）：如果语句不依赖于自身，则将其转换为向量语句。

具体Fortran代码示例：

考虑以下Fortran代码片段，它是一个简单的温度更新循环，其中使用了嵌套循环：

DO 100 I = 1, N
  T(I) = T(I) + DT * (Q(I) - Q(I+1))
100 CONTINUE

这里，T 是温度数组，Q 是热流数组，DT 是时间步长，N 是数组的大小。

转换过程：

1. 子标标准化：首先，我们需要确保循环中的所有数组索引都是循环变量的线性函数。在上面的例子中，T(I) 和 Q(I) 已经是 I 的线性函数，而 Q(I+1) 需要被转换，以避免循环中的递归依赖。

2. 循环变量替换：如果 Q(I+1) 可以被替换为不依赖于当前迭代的表达式，例如，如果 Q 的值在每次迭代中都是独立的，我们可以简单地将 Q(I+1) 替换为 Q(MOD(I, N) + 1)，以避免递归引用。

3. 依赖性测试：使用依赖性测试来确定是否可以将循环转换为向量形式。这通常涉及到检查循环中的语句是否形成了依赖链，即一个语句是否使用了另一个在同一循环中较早迭代的语句的输出。

4. 向量代码生成：如果依赖性测试表明没有自身依赖，那么可以将循环转换为向量形式，如下所示：

T(1:N) = T(1:N) + DT * (Q(1:N) - Q(2:N+1))

这里，我们使用了数组切片来表示整个数组的操作，这是Fortran 8x或更高版本中支持的向量操作。

注意：

• 实际的转换过程可能更复杂，需要考虑多种因素，如循环的嵌套、条件语句、数组的多维性等。
• PFC系统可能还包含其他优化步骤，如死代码消除、循环展开等，以进一步提高并行效率。

这个例子展示了如何将顺序Fortran程序转换为可能在向量计算机上更高效执行的并行形式。在实际应用中，PFC会使用更复杂的算法来分析和转换程序，以充分利用硬件的并行处理能力。

[ysh329]

2.6 用户定义的子程序

有一些用来增强用户定义的sub-routines和函数的方法：

1. array会作为subroutines的传参
2. 一个函数的返回值可能是array
3. 标量函数的声明可以用在array或vector上，来进行elementwise的操作。

3. The Translation Process

现在把 Fortran 程序转换为 Fortran 8x的向量化的陈鼓型，下面将会描述几个重要的问题。如下是被转换的程序：

最终目的是，将(3)和(4)这两条移除，并转为向量赋值。只要没有在串行循环和向量语句之间的语义上的不同，就是有可能的。考虑一个更加简单的例子：

如果将这个转为如下的向量赋值：

我们必须确保转换前后没有语义上的不同。

[ysh329]

1

[ysh329]

主要的不同点，就在parallel assignment上，右手边是假定

[ysh329]