Journal of Software:2000.11(1):126-132

Eliminate Redundant Loop-Carried Flow Dependences for VLIW Architectures
RONG Hong-bo,TANG Zhi-zhong
Chart / table
Similar Articles
Article :Browse 2435   Download 2532
Received:December 01, 1998    Revised:February 01, 1999
> 中文摘要: 数据相关是并行处理的基本依据.该文指出,VLIW(very long instruction word)特有的锁步性质使其数据相关性分析具有与众不同的特点.同一体差上的流相关形成一个线序集合,多体差上的特征流相关之间也存在包含关系.据此,提出一种用于VLIW的消除循环体间冗余流相关的方法.该方法是完备的,可以去除所有冗余的体间流相关,从而减轻循环调度的负担.文章给出判定单体差和多体差存在冗余的充分必要条件,以及消除冗余的线性复杂度的算法.这种方法具有普遍意义,可作为VLIW上软件流水和多指令流调度的基础.
Abstract:Data dependence is the basic guideline and constraint for parallel processing. The structural distinctiveness of VLIW (very long instruction word), i.e., the lockstep property, leads to remarkable uniqueness in its data dependence analysis, as is shown in this paper. Flow dependences with the same iteration distance comprise a linear ordered set, while characteristic flow dependences with different iteration distances may also have inclusion relationship between each other. From such discovery, a novel method is presented to eliminate redundant loop-carried flow dependences for VLIW architectures, so as to facilitate loop scheduling. The method is complete in that it gets rid of all redundancies. The sufficient and necessary preconditions to identify redundancy for single and multiple iteration distances are given, and a linear ordered algorithm is described. The method is generic, and can serve as a foundation for research on VLIW, such as software pipelining and multi-instruction stream scheduling.
文章编号:     中图分类号:    文献标志码:
基金项目:本文研究得到国家自然科学基金(No.69773028)资助. 本文研究得到国家自然科学基金(No.69773028)资助.
Foundation items:
Reference text:


RONG Hong-bo,TANG Zhi-zhong.Eliminate Redundant Loop-Carried Flow Dependences for VLIW Architectures.Journal of Software,2000,11(1):126-132