一种基于0-1整数规划的全局数据分布优化方法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

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


A 0-1 Integer Programming Based Approach forGlobal Data Distribution
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    数据分布是影响并行程序在分布主存多处理机上执行性能的重要因素。针对分布主存多处理机中的数据分布问题,提出了一种基于0-1整数规划、利用数据变换技术进行有效数据分布的方法。该方法通过数据变换技术改变数据的存储布局,以使得数据能被有效地分布,并且该方法还利用数据分布图描述程序被并行的情况及其所含数组被访问的情况,并将全局数据分布优化问题转换为求解数据分布图中最优路径的问题,从而可用0-1整数规划求解最优路径问题。该方法能对多个嵌套循环中具有仿射数组下标的任意维数组进行有效的数据分布,并且也能使嵌套循环的并行度尽可能地大。另外,该方法也考虑了偏移常量的对准问题,从而能使数据通信量尽量地小。实验结果验证了该方法的有效性。

    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.

    参考文献
    相似文献
    引证文献
引用本文

夏军,庞征斌,张峻,等.一种基于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.

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2009-01-27
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2012-11-08
  • 出版日期:
文章二维码