首页 | 本学科首页   官方微博 | 高级检索  
     

基于区域图数据流分析的通信优化算法
引用本文:钟洪涛,舒继武,温冬婵,郑纬民.基于区域图数据流分析的通信优化算法[J].软件学报,2003,14(2):175-182.
作者姓名:钟洪涛  舒继武  温冬婵  郑纬民
作者单位:清华大学,计算机科学与技术系,北京,100084
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60103019 (国家自然科学基金)
摘    要:减少通信开销对于并行化编译器生成高效的分布代码是非常重要的.首先提出了一个冗余并行执行模型(RPEM)作为通信优化算法生成的目标程序的执行模型,之后给出了区域图的概念和区域最大化算法,在最大化区域图的基础上进行数据流分析可以增大数据流分析粒度,提高分析的效率,同时也有助于通信的提前与合并.最后提出了一种基于区域图数据流分析的通信优化算法.该算法能够进行跨循环、跨过程的数据流分析,提高分析的精度,改善通信优化效果.实验结果表明,该算法对于通信量较大的程序能够有效地减少通信的次数和通信量,具有良好的可扩展性.

关 键 词:通信优化  数据流分析  区域图  分布存储系统
文章编号:1000-9825/2003/14(02)0175
收稿时间:2001/12/5 0:00:00
修稿时间:2001年12月5日

A Communication Optimization Algorithm Based on Data-Flow Analysis of Region Graph
ZHONG Hong-Tao,SHU Ji-Wu,WEN Dong-Chan and ZHENG Wei-Min.A Communication Optimization Algorithm Based on Data-Flow Analysis of Region Graph[J].Journal of Software,2003,14(2):175-182.
Authors:ZHONG Hong-Tao  SHU Ji-Wu  WEN Dong-Chan and ZHENG Wei-Min
Abstract:Reducing communication overhead is extremely important for parallelizing compiler to generate efficient codes for distributed-memory systems. In this paper, a redundant parallel execution model (RPEM) is proposed as an execution model for target programs optimized by the new algorithm. The region graph is introduced, and an effective algorithm is proposed to maximize the regions in the region graph. A region-based data-flow analysis algorithm is proposed to perform communication optimization. The overhead of data-flow analysis can be reduced by performing analysis on the maximized region graph. The coarse grain analysis also helps to communication lift up and aggregation. This communication optimization algorithm is able to perform inter-loop and inter-procedure analysis. Experimental results show that this algorithm is effective in reducing both communication volume and number of messages in programs with a large communication amount.
Keywords:communication optimization  data-flow analysis  region graph  distributed memory system
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号