一种基于代表元的划分算法

• 作者: 张为华 朱传琪 王鹏 臧斌宇
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 计算划分 数据划分 代表元 非紧密嵌套循环 数据划分一致性 并行编译
• 年，卷（期）: 2008,（3）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 400-410
• 页数: 11页
• 分类号: TP302
• 字数: 9909字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2008.03.005

摘要

划分是把程序中不同的计算和数据分配到并行处理系统的不同处理机来充分利用并行系统的计算资源、提高程序处理速度的一种优化技术.划分的效果对程序在并行系统上的执行效率将产生至关重要的影响,因此划分问题一直是并行领域研究的一个热点.但是应用程序的一些特性,如非紧密嵌套循环、一条语句对非只读数组的多次引用间存在重叠、不同语句对同一数组不同步长的引用,给有效解决划分问题设置了极大的障碍.已有的划分算法无法对具有这些特征的程序进行自动划分.虽然在对具有这些特征的程序进行手工优化过程中,存在一些直观上的划分策略,但这些策略无法应用到编译器中来指导编译器完成对程序的自动划分.文中根据这类程序的特点,提出了一种基于代表元的划分算法.该算法通过使用程序中对划分计算产生实际影响的数组引用作为代表元素构造各种划分的限制条件,完成程序的划分.同时通过寻找最大一致性数据划分方向有效减少了程序划分过程中的数据重组织通信.该算法已经在AFT2004中实现,并对应用程序获得了很好的效果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王鹏	复旦大学并行处理研究所	64	321	10.0	15.0
2	臧斌宇	复旦大学并行处理研究所	46	315	8.0	15.0
3	朱传琪	复旦大学并行处理研究所	32	201	7.0	12.0
4	张为华	复旦大学并行处理研究所	33	234	7.0	14.0