一个用于数据并行语言计算划分的时序优化模型(英文)  

A Time-Slicing Optimization Framework of Computation Partitioning for Data-Parallel Languages

作　　者：余华山[1] 胡长军 黄其军[1] 丁文魁[1] 许卓群[1] 

机构地区：[1]北京大学计算机科学技术系,北京100871

出　　处：《软件学报》2001年第10期1434-1446,共13页Journal of Software

基　　金：Supported by the National High Technology Development 863 Program of China under Grant No.86 3- 30 6 - ZT0 1- 0 2 - 3 (国家86 3高科技发展计划 )

摘　　要：一个程序中数据并行语句的计算划分 (CP)对该程序的运行性能有决定性的作用 .尽管人们对这一问题已经进行了广泛的研究 ,但这些研究的重点都集中在如何提高被选择计算划分的空间局部性上 .针对并行循环结构的计算划分问题 ,提出了一个时序优化模型 .在该模型中 ,一个计算划分被表示成一个有向图 ,在把并行语句中的操作映射到各个处理器的同时 ,给出了被分配到不同处理器上的操作之间的相关性 .对于一条数据并行语句 ,时序优化模型对它的每个计算划分选择方案分别采用多种有效的优化策略进行优化 ;并综合考虑各个计算划分选择方案的负载平衡性、处理器间的操作依赖性、数据访问的空间局部性和时间局部性四个方面的因素 ,估算每个方案的执行效率 ;最后从这些方案中选择一个执行效率最优的方案作为该语句的计算划分 .作者已在 HPF编译器 p-HPF采用时序优化模型实现了对 FORAL L结构的支持 .实验结果表明 ,该模型具有非常好的通用性 ,对不同领域多种数据并行问题均取得了理想的加速比 .同时 ,只需略微改动 ,该模型也可用于其他类型数据并行语句的计算划分 .Computation partitionings (CP) for the data parallel statements in a program have a dramatic impact on its performance. Although the problem has been widely studied, previous approaches focus on improving spatial locality of the chosen CP. A time slicing optimization framework is presented, which integrates many important optimization strategies, to select optimal CPs for parallel loop constructs. In the framework, a CP is represented by a directed graph, which not only represents a mapping of the operations in a parallel statement into processors, but also specifies the dependency constraints for operations in different processors. This approach is to evaluate the efficiency of each CP choice and to find the one with the best overall execution time. The evaluation method synthesizes the four aspects of load balance, operation independence between processors, spatial locality and temporal locality for each CP. The framework has been implemented in a HPF compiler p -HPF for FORALL construct. Experimental results show that the framework is of generality with desired speedups for a wide variety of data parallel applications. With a very little modification, it can also be applied to many other kinds of data parallel statement.

关 键 词：计算划分 数据相关 数据重用 时序优化模型 数据并行语言 程序 

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