顺序扫描实现程序并行化

提出扩展选择调度,统一处理循环和非循环代码,对它们不加区分但却分别产生软件流水和全局压缩的效果;程序并行化不需要分层简化,只要顺序扫描一遍即可.该方法打破了有环调度和无环调度的界限,是一种基于一般图而不是路径或有向无环图的全局调度算法.它从一个全新的角度来看待多重循环,通过恰当地计算可用集合和活变量集合,实现了多重循环的直接调度,对任意控制流程序都是适用的.

Parallelizing Programs with Sequential Scanning

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.