摘要
计算和数据自动划分是并行化编译中一种自动分配计算和数据到各个处理机的优化技术,划分的结果直接影响程序并行的性能。数组是划分处理的主要对象之一,一些数组分布后的收益不高,但带来的并行约束却能对其它数组的划分产生干扰,导致大量数据重分布通信的产生。现有的划分算法中没有约定数组分布的优先次序,因此无法限制这些数组并行约束的传播,降低了优化编译器后端自动生成并行代码的性能。提出了一种基于主导值的计算和数据自动划分算法:将划分过程中数组对程序并行性的影响量化为主导值,并依据主导值的大小约定数组分布的优先次序,限制干扰数组并行约束的传播速度,提高划分结果的合理性。实验结果表明,算法能够获得良好的划分效果。
Automatic computation and data decomposition are an optimization technique that distributes computations and data onto different processors. The decomposition result has a direct impact on the performance of program＇s parallelization. Array is one of main targets of treatment for the decomposition algorithm, and some profits of them are not enough after parallelization, but it will bring constraints and disrupt the other distribution of array, leading to large amounts communication of data re-distribution. The decomposition algorithm in existing has no agreement in the order of array distribution,therefore can＇t restrict propagation of constraint of array＇s parallelization, reducing performance of optimized parallel code automatically generated by the hack-end compiler. This paper presented an automatic computation and data decomposition based on the＂ dominant values. Algorithm quantified the impact of array on the programs＇ parallelism as the dominant value, and agreed priorities of distribution based on the size of the dominant values of array, limited the spread speed of constraints of interference array, improved the reasonableness of decomposition results. Experimental results show that the algorithm can get good decomposition results.
出处
《计算机科学》
CSCD
北大核心
2012年第3期290-294,303,共6页
Computer Science
基金
"核高基"重大专项子课题(863)(2009AA01220
2009zx10036-001-001)资助
关键词
自动并行化
计算划分
数据分布
主导值
约束
Automatic parallelization, Computation decomposition, Data decomposition, Dominant values, Constraint
