基于依赖分析的SPMD程序隐式同步检测及处理算法

摘要

SPMD翻译是指将一种特定类型的SPMD程序编译到多种设备上，当前的细粒度SPMD翻译研究建立在线程之间相互独立的假定上，线程之间只通过显式同步进行通信。但线程之间还隐含存在着各种数据依赖，如隐式同步，这导致了 SPMD 翻译在处理隐式同步时的正确性缺陷。为了对隐式同步进行处理，对细粒度 SPMD 模型 CUDA中的隐式同步进行了系统的分析，指出了当前翻译CUDA程序到多核平台的相关研究在处理隐式同步上的不足，提出了基于依赖分析的隐式同步检测方法。在检测出隐式同步的基础上，设计了循环重排序的优化处理算法，对显式同步和隐式同步进行了统一处理。实验结果表明，与现有的SPMD翻译方法相比，该检测及处理算法能够正确而快速地检测并翻译CUDA中的各种隐式同步，代价较小，有助于编译器产生正确而有效的翻译结果。%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.