归约识别及其单模变换  

REDUCTION RECOGNITION AND UNIMODULAR TRANSFORMATION

作　　者：李剑慧[1] 臧斌宇[1] 陈彤[1] 朱传琪[1] 

机构地区：[1]复旦大学并行处理研究所,上海200433

出　　处：《计算机学报》1998年第1期1-9,共9页Chinese Journal of Computers

基　　金：国家自然科学基金;863高科技基金;攀登计划;上海市重点学科;学科带头人基金

摘　　要：数组归约的识别是提高并行化编译能力的有效方法，单模变换是开发程序并行性的重要手段．然而，由于归约语句间相关的特殊性，影响了单模变换的实施．本文从归约语句引起的相关本质特征入手，分析了旧约语句和单模变换的相互影响，提出了在归约语句存在的情况下单模变换的具体方法．The recognition of array reduction is effective on enhancing the ability ofparallelizing compiler, while unimodular transformation remains a significant ap-proach to exploit the parallelism of application programs. Traditionally the paral-lelizing compiler uses the method of pattern match to find out array reduction,which lacks the theoretical basis for further study. This paper analyzes the speclalcharacteristic of the dependence caused by reduction, defines reduction preciselywith the conception of dependence, and illustrates several ways to transform theDo loop with array reduction to parallel version. When the parallelizing compilertries to trans form a serial program to parallel version, it occurs often that the de-pendence between reduction statements handicapped the implementation of unimod-ular transformation. In order to apply the unimodular transformation under the sit-uation of existing reduction dependence, this paper starts from studying the essen-tial characteristic of the reduction dependence, analyzes the behavior of unimodulartrans formation, discusses the reciprocal effect between reduction and unimodulartransformation, brings forward a useful conclusion theoretically, on the basis of which modifies the unimodular transformation algorithm for removing the negativeeffect caused by the reduction dependence- At the end of this paper,an exam-ple demonstrates the effectiveness of the new algorithm.

关 键 词：单模变换 数组归约 并行化编译 归约识别 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]