Journal of Software:2000.11(12):1648-1655

(清华大学 计算机科学与技术系,北京,100084)
Parallelizing Programs with Sequential Scanning
RONG Hong-bo,TANG Zhi-zhong
Chart / table
Similar Articles
Article :Browse 2622   Download 2736
Received:May 17, 1999    Revised:September 23, 1999
> 中文摘要: 提出扩展选择调度,统一处理循环和非循环代码,对它们不加区分但却分别产生软件流水和全局压缩的效果;程序并行化不需要分层简化,只要顺序扫描一遍即可.该方法打破了有环调度和无环调度的界限,是一种基于一般图而不是路径或有向无环图的全局调度算法.它从一个全新的角度来看待多重循环,通过恰当地计算可用集合和活变量集合,实现了多重循环的直接调度,对任意控制流程序都是适用的.
Abstract:Generalized selective scheduling (GSS) is presented to uniformly process loops and acyclic code. GSS does not differentiate acyclic code from cyclic code, but generates the result of global compaction and software pipelining for them respectively. The program is parallelized not by hierarchical simplification, but by only one-pass sequential scanning. As the first global scheduling based on general graphs instead of traces or directed acyclic graphs, GSS breaks the boundary between acyclic and cyclic code scheduling. It views nested loops from a fresh angle, realizing the direct scheduling of nests by properly calculating availability sets and live variable sets. It is applicable to programs with arbitrary control flow.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金资助项目(69773028) 国家自然科学基金资助项目(69773028)
Foundation items:
Reference text:


RONG Hong-bo,TANG Zhi-zhong.Parallelizing Programs with Sequential Scanning.Journal of Software,2000,11(12):1648-1655