一种基于0-1整数规划的全局数据分布优化方法  

A 0-1 Integer Programming Based Approach for Global Data Distribution

作　　者：夏军[1] 庞征斌[1] 张峻[1] 李永进[1] 

机构地区：[1]国防科技大学计算机学院,湖南长沙410073

出　　处：《国防科技大学学报》2009年第4期62-67,共6页Journal of National University of Defense Technology

基　　金：国家杰出青年科学基金资助项目(69825104)

摘　　要：数据分布是影响并行程序在分布主存多处理机上执行性能的重要因素。针对分布主存多处理机中的数据分布问题,提出了一种基于0-1整数规划、利用数据变换技术进行有效数据分布的方法。该方法通过数据变换技术改变数据的存储布局,以使得数据能被有效地分布,并且该方法还利用数据分布图描述程序被并行的情况及其所含数组被访问的情况,并将全局数据分布优化问题转换为求解数据分布图中最优路径的问题,从而可用0-1整数规划求解最优路径问题。该方法能对多个嵌套循环中具有仿射数组下标的任意维数组进行有效的数据分布,并且也能使嵌套循环的并行度尽可能地大。另外,该方法也考虑了偏移常量的对准问题,从而能使数据通信量尽量地小。实验结果验证了该方法的有效性。Data distribution is one of the key factors that affect the performance of programs running on distributed memory multiprocossors. This paper presents a 0-1 integer programming based approach for effective data distribution using data transformation tech-niques. This approach uses data transformations to change memory layouts and hence makes effective data distribution possible. Moreover, it also uses data distribution graphs to describe how programs are parallelized and how arrays are accessed, and transforms global data distribution problems into the problems of finding optimal paths in data distribution graphs. Therefore, 0- 1 integer programming can be used to solve optimal path problems. The approach can effectively distribute multidimensional arrays with affine subscripts accessed in multiple loop nests and can exploit the parallehsms of loop nests as much as possible. In addition, it can also solve offset alignment problems. Thus data communication overheads can be reduced as much as possible. The experimental results show that the approach presented in this paper is effective.

关 键 词：分布主存多处理机 数据变换 数据分布 数据存储布局 0—1整数规划 

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