优化并行图重写计算粒度的编译时部分调度策略  

COMPILE-TIME PARTIAL SCHEDULING STRATEGIES FOR OPTIMIZING GRANULARITY OF PARALLEL GRAPH REWRITING

作　　者：田新民[1] 王鼎兴[1] 沈美明[1] 郑纬民[1] 温冬婵[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《计算机学报》1992年第11期838-847,共10页Chinese Journal of Computers

基　　金：国家863高技术基金;高校博士学科点专项基金

摘　　要：并行图重写计算的有效实现需要压缩重写任务的频繁生成、切换和同步开销.为此本文提出了一种编译时重写粒度优化技术——编译时部分调度.其核心思想是基于对重写结点的全序性质和执行语义的分析,编译时构造 保持原有执行语义的粗粒度顺序重写体。在本文定义的形式框架下,我们建立了编译时部分调度的安全条件,并给出了严格的证明.实验研究结果表明编译时部分调度能有效地增大重写粒度,重写任务数压缩了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.

关 键 词：优化 并行图 调度策略 编译 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]