一个用于数据并行语言计算划分的时序优化模型
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

Supported by the National High Technology Development 863 Program of China under Grant No.863-306-ZT01-02-3 (国家863高科技发展计划)


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

Fund Project:

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

    一个程序中数据并行语句的计算划分(CP)对该程序的运行性能有决定性的作用.尽管人们对这一问题已经进行了广泛的研究,但这些研究的重点都集中在如何提高被选择计算划分的空间局部性上.针对并行循环结构的计算划分问题,提出了一个时序优化模型.在该模型中,一个计算划分被表示成一个有向图,在把并行语句中的操作映射到各个处理器的同时,给出了被分配到不同处理器上的操作之间的相关性.对于一条数据并行语句,时序优化模型对它的每个计算划分选择方案分别采用多种有效的优化策略进行优化;并综合考虑各个计算划分选择方案的负载平衡性、处理器间的操作依赖性、数据访问的空间局部性和时间局部性四个方面的因素,估算每个方案的执行效率;最后从这些方案中选择一个执行效率最优的方案作为该语句的计算划分.作者已在HPF编译器p-HPF采用时序优化模型实现了对FORALL结构的支持.实验结果表明,该模型具有非常好的通用性,对不同领域多种数据并行问题均取得了理想的加速比.同时,只需略微改动,该模型也可用于其他类型数据并行语句的计算划分.

    Abstract:

    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 aparallel state-ment into processprs,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.

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

余华山,胡长军,黄其军,丁文魁,许卓群.一个用于数据并行语言计算划分的时序优化模型.软件学报,2001,12(10):1434-1446

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2000-06-28
  • 最后修改日期:2000-06-28
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号