Dynamic and Speculative Polyhedral Parallelization Using Compiler-Generated Skeletons
Dynamic and Speculative Polyhedral Parallelization Using Compiler-Generated Skeletons
复制标题
DOI：
10.1007/s10766-013-0259-4
复制
发表时间：
2014-08-01
影响因子：
1.5
通讯作者：
Caamano, Juan Manuel Martinez
中科院分区：
文献类型：
--
作者：
Jimborean, Alexandra;Clauss, Philippe;Caamano, Juan Manuel Martinez
我们提出了一个基于原始生成和算法骨骼的使用，并致力于对科学嵌套循环内核的投机平行化的框架，能够在运行时多面体转换应用于目标代码，以展示并行性和数据本地性。通过使用二进制算法骨骼在编译时生成的二进制算法骨骼几乎无需实现并行代码生成，并嵌入了用于实例化多面体并行化转换的原始代码和操作，并验证依赖性的猜测。骨骼在运行时进行修补以生成可执行的代码。运行时过程包括使用代码的仪器版本在短示例上在线分析阶段指导的转换选择。在此阶段，访问的内存地址用于计算即时依赖距离向量，并且也被插值以构建即将到来的访问的预测指标。然后使用插值函数和距离向量进行依赖分析，以选择一个并行的转换，如果预测是正确的，则在执行过程中不会引起任何回滚。为了确保回滚时间开销保持较低，代码是在巢的最外面原始环的连续切片中执行的。每个切片可以是实例化骨架，顺序原始版本或仪器版本的并行版本。此外，执行的这种切片提供了通过对观察到的执行阶段进行不同的代码转换不同的机会，通过对预先构建的骨架进行了不同的修补，以适应观察到的执行阶段。该框架已通过LLVM编译器的扩展和X86-64运行时系统实现。在一组基准上显示了明显的速度，这些基准无法有效地由编译器处理。
We propose a framework based on an original generation and use of algorithmic skeletons, and dedicated to speculative parallelization of scientific nested loop kernels, able to apply at run-time polyhedral transformations to the target code in order to exhibit parallelism and data locality. Parallel code generation is achieved almost at no cost by using binary algorithmic skeletons that are generated at compile-time, and that embed the original code and operations devoted to instantiate a polyhedral parallelizing transformation and to verify the speculations on dependences. The skeletons are patched at run-time to generate the executable code. The run-time process includes a transformation selection guided by online profiling phases on short samples, using an instrumented version of the code. During this phase, the accessed memory addresses are used to compute on-the-fly dependence distance vectors, and are also interpolated to build a predictor of the forthcoming accesses. Interpolating functions and distance vectors are then employed for dependence analysis to select a parallelizing transformation that, if the prediction is correct, does not induce any rollback during execution. In order to ensure that the rollback time overhead stays low, the code is executed in successive slices of the outermost original loop of the nest. Each slice can be either a parallel version which instantiates a skeleton, a sequential original version, or an instrumented version. Moreover, such slicing of the execution provides the opportunity of transforming differently the code to adapt to the observed execution phases, by patching differently one of the pre-built skeletons. The framework has been implemented with extensions of the LLVM compiler and an x86-64 runtime system. Significant speed-ups are shown on a set of benchmarks that could not have been handled efficiently by a compiler.