主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第4期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
余华山,胡长军,黄其军,丁文魁,许卓群.一个用于数据并行语言计算划分的时序优化模型.软件学报,2001,12(10):1434-1446
一个用于数据并行语言计算划分的时序优化模型
A Time-Slicing Optimization Framework of Computation Partitioning for Data-Parallel Languages
投稿时间:2000-06-28  修订日期:2000-06-28
DOI:
中文关键词:  数据并行  集群并行计算  计算划分  数据相关  数据重用  负载平衡  通信优化
英文关键词:data parallelism implementation  cluster parallel computing  computation partitioning  data dependency analysis  data reuse analysis  load balancing  communication optimization
基金项目:Supported by the National High Technology Development 863 Program of China under Grant No.863-306-ZT01-02-3 (国家863高科技发展计划)
作者单位
余华山 北京大学计算机科学技术系,北京 100871 
胡长军 北京大学计算机科学技术系,北京 100871 
黄其军 北京大学计算机科学技术系,北京 100871 
丁文魁 北京大学计算机科学技术系,北京 100871 
许卓群 北京大学计算机科学技术系,北京 100871 
摘要点击次数: 2176
全文下载次数: 2443
中文摘要:
      一个程序中数据并行语句的计算划分(CP)对该程序的运行性能有决定性的作用.尽管人们对这一问题已经进行了广泛的研究,但这些研究的重点都集中在如何提高被选择计算划分的空间局部性上.针对并行循环结构的计算划分问题,提出了一个时序优化模型.在该模型中,一个计算划分被表示成一个有向图,在把并行语句中的操作映射到各个处理器的同时,给出了被分配到不同处理器上的操作之间的相关性.对于一条数据并行语句,时序优化模型对它的每个计算划分选择方案分别采用多种有效的优化策略进行优化;并综合考虑各个计算划分选择方案的负载平衡性、处理器间的操作依赖性、数据访问的空间局部性和时间局部性四个方面的因素,估算每个方案的执行效率;最后从这些方案中选择一个执行效率最优的方案作为该语句的计算划分.作者已在HPF编译器p-HPF采用时序优化模型实现了对FORALL结构的支持.实验结果表明,该模型具有非常好的通用性,对不同领域多种数据并行问题均取得了理想的加速比.同时,只需略微改动,该模型也可用于其他类型数据并行语句的计算划分.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利