Automatic Parallelization of Recursive Functions Using Quantifier Elimination
Automatic Parallelization of Recursive Functions Using Quantifier Elimination
复制标题
使用量词消除的递归函数的自动并行化
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Kiminori Matsuzaki
中科院分区：
文献类型：
--
作者：
Akimasa Morihata;Kiminori Matsuzaki
尽管最近并行计算环境的流行要求并行程序，但非专业人员很难开发出高效的并行程序。我们需要的是能够从顺序程序自动生成高效并行程序的并行化方法。本文提出了一种递归函数的自动并行化方法。关键是基于量词消除的运算符派生，该运算符缩小表示部分计算的函数闭包。一旦我们获得了这样一个运算符，我们就可以拆分输入结构并对每个部分并行执行计算。我们的方法有几个特点：它不需要任何人工帮助，它保证生成的程序的计算效率，它处理复杂的递归函数，如非线性递归、非自递归和累积函数。
Although the recent popularity of parallel-computing environments has called for parallel programs, it is difficult for nonspecialists to develop those that are efficient. What is required are parallelization methods that can automatically generate efficient parallel programs from sequential ones. In this paper, we propose an automatic method of parallelization for recursive functions. The key is a quantifier-elimination-based derivation of an operator that shrinks function closures representing partial computations. Once we obtain such an operator, we can split the input structure and perform computation on each part in parallel. Our method has several features: it does not require any human help, it guarantees computational efficiency of generated programs, and it deals with complicated recursive functions such as those that are nonlinear recursive, non-self recursive, and accumulative.