摘要
数据相关是并行处理的基本依据 .该文指出 ,VLIW(very long instruction word)特有的锁步性质使其数据相关性分析具有与众不同的特点 .同一体差上的流相关形成一个线序集合 ,多体差上的特征流相关之间也存在包含关系 .据此 ,提出一种用于 VL IW的消除循环体间冗余流相关的方法 .该方法是完备的 ,可以去除所有冗余的体间流相关 ,从而减轻循环调度的负担 .文章给出判定单体差和多体差存在冗余的充分必要条件 ,以及消除冗余的线性复杂度的算法 .这种方法具有普遍意义 ,可作为 VL IW上软件流水和多指令流调度的基础 .
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.
出处
《软件学报》
EI
CSCD
北大核心
2000年第1期126-132,共7页
Journal of Software
基金
国家自然科学基金! (No.6 97730 2 8)资助
关键词
VLIW
循环调度
数据相关
冗余
并行处理
VLIW (very long instruction word), loop scheduling, data dependence, loop, redundancy.
