摘要
并行图重写计算的有效实现需要压缩重写任务的频繁生成、切换和同步开销.为此本文提出了一种编译时重写粒度优化技术——编译时部分调度.其核心思想是基于对重写结点的全序性质和执行语义的分析,编译时构造 保持原有执行语义的粗粒度顺序重写体。在本文定义的形式框架下,我们建立了编译时部分调度的安全条件,并给出了严格的证明.实验研究结果表明编译时部分调度能有效地增大重写粒度,重写任务数压缩了30—60％,并且计算的安全性得到了保证.
In this paper, a compilation optimizing technique called compile- time partial scheduling for reducing the overheads of graph rewriting task creation, switching and synchronization, and supporting the efficient implementation of parallel graph rewriting computation, is presented. The compile-time' partial scheduling technique divides at compile-ti-me a C1L program into threads of totally ordered graph nodes, whose relative ordering is determined at run-time. The safety conditions within an abstract formal framework defined in this paper are established and proved strictly. The experimental results have shown that this technique enables the creation of tasks to be reduced by 30-60%, the granularity of tasks increased, task synchronization partially removed and safety conditions satisfied.
出处
《计算机学报》
EI
CSCD
北大核心
1992年第11期838-847,共10页
Chinese Journal of Computers
基金
国家863高技术基金
高校博士学科点专项基金
关键词
优化
并行图
调度策略
编译
Compile-time partial scheduling, parallel graph rewriting, granularity, compile optimization technique.
