论文标题
一种受隐式计算复杂性启发的新型循环裂变技术
A Novel Loop Fission Technique Inspired by Implicit Computational Complexity
论文作者
论文摘要
这项工作探讨了隐式计算复杂性（ICC）在命令程序中平行循环的意外应用。得益于轻巧的依赖性分析，我们的算法允许将循环分为可以并行运行的多个循环，从而在执行时间上获得的增长，类似于最先进的自动并行工具，同时适用。我们的基于图的算法是直观的，语言的不可思议的，可证明的正确且适用于所有类型的循环，即使它们的循环迭代空间在静态或编译时未知，如果它们不采用规范形式，或者它们包含循环的依赖性。作为贡献，我们提供了计算技术，证明其语义正确性的证明以及实验结果，以量化预期的性能增长。我们的基准还表明，该技术可以无缝集成到编译器通行证或其他自动并行化套件中。我们断言，由于ICC提供的“正交”方法，发现了这种原始且自动的循环转换方法。
This work explores an unexpected application of Implicit Computational Complexity (ICC) to parallelize loops in imperative programs. Thanks to a lightweight dependency analysis, our algorithm allows splitting a loop into multiple loops that can be run in parallel, resulting in gains in terms of execution time similar to state-of-the-art automatic parallelization tools when both are applicable. Our graph-based algorithm is intuitive, language-agnostic, proven correct, and applicable to all types of loops, even if their loop iteration space is unknown statically or at compile time, if they are not in canonical form or if they contain loop-carried dependency. As contributions we deliver the computational technique, proof of its preservation of semantic correctness, and experimental results to quantify the expected performance gains. Our benchmarks also show that the technique could be seamlessly integrated into compiler passes or other automatic parallelization suites. We assert that this original and automatable loop transformation method was discovered thanks to the "orthogonal" approach offered by ICC.
