###
Journal of Software:2013.24(8):1775-1785

基于依赖分析的SPMD程序隐式同步检测及处理算法
岳峰,庞建民,赵荣彩
(解放军信息工程大学, 河南 郑州 450002)
Detecting and Treatment Algorithm of Implicit Synchronization Based on Dependence Analysis in SPMD Program
YUE Feng,PANG Jian-Min,ZHAO Rong-Cai
(PLA Information Engineering University, Zhengzhou 450002, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2547   Download 2551
Received:July 03, 2011    Revised:October 19, 2012
> 中文摘要: SPMD 翻译是指将一种特定类型的SPMD 程序编译到多种设备上,当前的细粒度SPMD 翻译研究建立在线程之间相互独立的假定上,线程之间只通过显式同步进行通信.但线程之间还隐含存在着各种数据依赖,如隐式同步,这导致了SPMD 翻译在处理隐式同步时的正确性缺陷.为了对隐式同步进行处理,对细粒度SPMD 模型CUDA中的隐式同步进行了系统的分析,指出了当前翻译CUDA 程序到多核平台的相关研究在处理隐式同步上的不足,提出了基于依赖分析的隐式同步检测方法.在检测出隐式同步的基础上,设计了循环重排序的优化处理算法,对显式同步和隐式同步进行了统一处理.实验结果表明,与现有的SPMD 翻译方法相比,该检测及处理算法能够正确而快速地检测并翻译CUDA 中的各种隐式同步,代价较小,有助于编译器产生正确而有效的翻译结果.
Abstract:SPMD translation compiles programs of one SPMD-threaded programming model to multi devices. The current researches base on the supposition that different threads are independent except in communication with explicit synchronizations. However, the data dependence relation between threads such as implicit synchronizations results in the correctness pitfalls in SPMD translation. In order to deal with implicit synchronizations, the implicit synchronizations in fine-grained SPMD programming model CUDA are analyzed systematically. The correctness pitfalls in existing SPMD translation from CUDA to Multi-core are revealed in which this paper proposes a method of detecting implicit synchronizations based on dependence analysis. On the basis of implicit synchronizations detecting, an optimized treatment algorithm is designed to treat explicit and implicit synchronizations synthetically by the loop reorder. The experimental results show that compared with existing SPMD translation, the detecting and optimized algorithm could treat kinds of implicit synchronizations in fine grained SPMD translation correctly and quickly by small expense, which helps compiler produces correct and efficient result.
文章编号:     中图分类号:    文献标志码:
基金项目:国家高技术研究发展计划(863)(2009AA012201); 国家科技重大专项(核高基)(2009ZX01036-001-001); 河南省重大科技攻关专项(092101210501) 国家高技术研究发展计划(863)(2009AA012201); 国家科技重大专项(核高基)(2009ZX01036-001-001); 河南省重大科技攻关专项(092101210501)
Foundation items:
Reference text:

岳峰,庞建民,赵荣彩.基于依赖分析的SPMD程序隐式同步检测及处理算法.软件学报,2013,24(8):1775-1785

YUE Feng,PANG Jian-Min,ZHAO Rong-Cai.Detecting and Treatment Algorithm of Implicit Synchronization Based on Dependence Analysis in SPMD Program.Journal of Software,2013,24(8):1775-1785