| 引用本文: | 夏军,庞征斌,张峻,等.一种基于0-1整数规划的全局数据分布优化方法.[J].国防科技大学学报,2009,31(4):62-67.[点击复制] |
| XIA Jun,PANG Zhengbin,ZHANG Jun,et al.A 0-1 Integer Programming Based Approach for Global Data Distribution[J].Journal of National University of Defense Technology,2009,31(4):62-67[点击复制] |
|
| |
|
|
| 本文已被：浏览 6975次 下载 5937次 |
| 一种基于0-1整数规划的全局数据分布优化方法 |
| 夏军, 庞征斌, 张峻, 李永进 |
|
(国防科技大学 计算机学院，湖南 长沙 410073)
|
| 摘要: |
| 数据分布是影响并行程序在分布主存多处理机上执行性能的重要因素。针对分布主存多处理机中的数据分布问题，提出了一种基于0-1整数规划、利用数据变换技术进行有效数据分布的方法。该方法通过数据变换技术改变数据的存储布局，以使得数据能被有效地分布，并且该方法还利用数据分布图描述程序被并行的情况及其所含数组被访问的情况，并将全局数据分布优化问题转换为求解数据分布图中最优路径的问题，从而可用0-1整数规划求解最优路径问题。该方法能对多个嵌套循环中具有仿射数组下标的任意维数组进行有效的数据分布，并且也能使嵌套循环的并行度尽可能地大。另外，该方法也考虑了偏移常量的对准问题，从而能使数据通信量尽量地小。实验结果验证了该方法的有效性。 |
| 关键词: 分布主存多处理机 数据变换 数据分布 数据存储布局 0-1整数规划 |
| DOI： |
| 投稿日期：2009-01-27 |
| 基金项目:国家杰出青年科学基金资助项目(69825104) |
|
| A 0-1 Integer Programming Based Approach for Global Data Distribution |
| XIA Jun, PANG Zhengbin, ZHANG Jun, LI Yongjin |
|
(College of Computer, National Univ. of Defense Technology, Changsha 410073, China)
|
| Abstract: |
| Data distribution is one of the key factors that affect the performance of programs running on distributed memory multiprocessors. This paper presents a 0-1 integer programming based approach for effective data distribution using data transformation techniques. 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 parallelisms 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. |
| Keywords: distributed memory multiprocessors data transformations data distribution data memory layouts 0-1 integer programming |
|
|
|
|
|
