自动并行化中不规则问题的划分方法  

Partition Method for Automatic Parallelization of Irregular Problems

作　　者：丁锐[1] 赵荣彩[1] 刘晓娴[1] 傅立国[1] 

机构地区：[1]信息工程大学,河南郑州450001

出　　处：《信息工程大学学报》2013年第2期235-242,共8页Journal of Information Engineering University

基　　金：国家863计划资助项目(2009AA01120;2009ZX10036-001-001)

摘　　要：许多大规模计算程序包含了不规则问题。在面向分布存储的自动并行化中,以往的研究在编译时划分不规则问题的循环和数组较难。文章提出了一种划分方法自动为一类常见的不规则问题寻找计算和数据分解,能在编译时通过计算分解分配不规则数组的数据空间,并根据规则数组之间的相关性来减少数组重分布。该方法通过计算分解和数组引用的访问表达式来分配不规则数组访问的数据到各处理器,并通过数组重分布图在循环间寻找一致的分解。实验结果表明了方法的有效性,并对测试用例取得了预期的加速比。Many large-scale scientific applications contain irregular problems. But the prior work of automatic parallelization on distributed memory is hardly to partition loop and array of irregular problems at compile-time. This paper proposes a partition approach for automatically finding computation and data decomposition of a common class of irregular loops. It＇ s able to partition the data space of irregular arrays at compile-time and reduce array redistributions by the relativity of regular arrays. The approach distributes data accessed by irregular arrays onto each processor by computation decomposition and access expression of array references, and searches consistent decomposition be- tween loops by array redistribution graph. Experiment results show the validity of the approach and the speedup of test applications.

关 键 词：自动并行化 计算分解 不规则循环 不规则数组 

分 类 号：TP314[自动化与计算机技术—计算机软件与理论]