Whole-Function Vectorization: Related Work

[ysh329]

paper: https://compilers.cs.uni-saarland.de/papers/karrenberg_wfv.pdf

[ysh329]

自从向量计算机和阵列处理器出现以来，为并行硬件架构生成代码就一直在被研究。大量研究投入到了科学（Fortran）程序的并行化中。

特别是循环嵌套的分析和自动转换[3, 10]。Allen等人[2]开创了控制流到数据流转换，帮助依赖性分析处理更复杂的控制结构。

而我们的实现方法（Whole-Function Vectorization），不需要执行依赖性分析或寻找任何并行性；它在我们考虑的编程模型中是隐含的。我们使用控制流到数据流转换作为一种技术，在SIMD处理器上实现数据并行程序。此外，Allen等人在语法树级别执行他们的转换。然而，我们考虑在 SSA 形式的任意控制流图上进行控制流到数据流的转换。

[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）：当一个语句的执行需要另一个语句计算的数据时，称这两个语句之间存在数据依赖。