The challenges of non-linear parameters and variables in automatic loop parallelisation
The challenges of non-linear parameters and variables in automatic loop parallelisation
复制标题
自动循环并行化中非线性参数和变量的挑战
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Armin Größlinger
中科院分区：
文献类型：
--
作者：
Armin Größlinger
随着多核处理器的兴起，并行正在成为一种主流需求。不幸的是，并行编程天生就比顺序编程更难；因此，自动并行化技术将变得不可或缺。我们的目标是扩展著名的多面体模型，该模型承诺实现自动化，超越目前的一些限制。到目前为止，建模代码中的循环边界和数组下标必须是变量和参数中的线性表达式。我们取消了这一限制，允许某些多项式表达式而不是线性表达式。通过我们的扩展，我们能够在并行化过程的所有阶段(依赖分析、程序模型转换、代码生成)处理更多的程序。我们将Banerjee的经典依赖分析推广到处理一个非线性参数p，即我们能够根据p的剩余类精确地确定具有像A[p·i]这样的非线性数组访问的输入程序的冲突等式组的解。首先，我们证明了使用我们开发的广义单纯形算法，具有θ(I)=⌊in⌋的非线性参数的调度可以被计算。此外，这样的调度可以很容易地表示为量词消除问题，但这种方法在可用实现中的计算效率被证明是较低的。作为第二个转换，我们研究了参数平铺，它用于使并行程序在运行时适应可用处理器的数量。第三，我们提出了一种本地化技术，在必须由软件处理数据缓存的体系结构上利用便签存储器。我们对给定的代码进行变换，以使其保留在便签本中的顺序循环的连续迭代中重复使用的值。从便签簿提供对在较早迭代中写入的值的访问，以加速访问。通常，此转换会在转换后的模型中引入非线性循环边界。最后，我们给出了一个生成任意半代数迭代集，即变量和参数的多项式不等式所描述的迭代集的代码的算法。这是对现有多面体代码生成技术的广泛概括。虽然我们的算法比多面体代码生成器效率低，但这为代码生成器铺平了道路，它可以处理任意参数平铺和其他引入非线性参数(如非线性调度和我们提出的本地化)甚至非线性变量的转换。从技术上讲，我们的扩展依赖于代数(多元多项式和一元拟多项式)和逻辑(实数中的量词消去)的结果。我们证明了具有一个非线性参数的线性丢番图方程组的解可以通过将一个著名的非参数情形的算法推广到参数中的一元拟多项式的系数来计算。计算时间表和其他变换与量词消除直接相关，或者可以借助于量词消除通过线性情况的算法的推广来执行。柱面代数分解(最初是作为一种量词消除方法开发的)是为具有多项式界的迭代集生成代码的关键。要生成代码，需要对索引集进行适当的分区。我们观察到这种划分是柱形的，并在此基础上提出了一种基于柱面代数分解的具有任意多项式界的迭代集的代码生成算法。
With the rise of manycore processors, parallelism is becoming a mainstream necessity. Unfortunately, parallel programming is inherently more difficult than sequential programming; therefore, techniques for automatic parallelisation will become indispensable. We aim at extending the well-known polyhedron model, which promises this automation, beyond some of its current restrictions. Up to now, loop bounds and array subscripts in the modelled codes must be expressions linear in both the variables and the parameters. We lift this restriction and allow certain polynomial expressions instead of linear ones. With our extensions, we are able to handle more programs in all phases of the parallelisation process (dependence analysis, transformation of the program model, code generation). We extend Banerjee’s classical dependence analysis to handle one non-linear parameter p, i.e., we are able to determine precisely the solutions of the system of conflict equalities for input programs with non-linear array accesses like A[p · i] in dependence of the residue class of p. We make contributions to three transformations desirable in automatic parallelisation. First, we show that using a generalised Simplex algorithm, which we have developed, schedules with non-linear parameters like θ(i) = ⌊ i n ⌋ can be computed. In addition, such schedules can be expressed easily as a quantifier elimination problem but this approach turns out to be computationally less efficient with the available implementation. As a second transformation, we study parametric tiling which is used to adapt a parallelised program to the number of available processors at run time. Third, we present a localisation technique to exploit scratchpad memories on architectures on which data caching has to be handled by software. We transform a given code such that it keeps values which are reused in successive iterations of a sequential loop in the scratchpad. An access to a value written in an earlier iteration is served from the scratchpad to accelerate the access. In general, this transformation introduces non-linear loop bounds in the transformed model. Finally, we present an algorithm for generating code for arbitrary semi-algebraic iteration sets, i.e., for iteration sets described by polynomial inequalities in the variables and parameters. This is a vast generalisation of existing polyhedral code generation techniques. Although our algorithm is less efficient than polyhedral code generators, this paves the way for a code generator that can handle arbitrary parametric tilings and other transformations which introduce non-linear parameters (like non-linear schedules and the localisation we present) or even non-linear variables. Technically, our extensions rely on results from algebra (multivariate polynomials and univariate quasi-polynomials) and logic (quantifier elimination in the reals). We prove that solutions of systems of linear Diophantine equalities with one non-linear parameter can be computed by a generalisation of a well-known algorithm for the non-parametric case to coefficients which are univariate quasi-polynomials in the parameter. Computing schedules and other transformations are directly related to quantifier elimination or can be performed by a generalisation of an algorithm for the linear case by the help of quantifier elimination. Cylindrical algebraic decomposition (originally developed as a method for quantifier elimination) is the key to generating code for iteration sets with polynomial bounds. To generate code, a suitable partitioning of the index sets is required. We observe that such partitionings are cylindrical and, based on this observation, present a code generation algorithm based on cylindrical algebraic decomposition for iteration sets with arbitrary polynomial bounds.