迭代式全局指令调度  

The Iterative Global Instruction Scheduler

作　　者：杨书鑫[1] 薛丽萍[1] 张兆庆[1] 

机构地区：[1]中科院计算技术研究所先进编译技术研究组,北京100080

出　　处：《计算机科学》2004年第7期118-122,共5页Computer Science

基　　金：国家863计划(合同号 2001AA11061);国家自然科学基金(批准号69933020)

摘　　要：基于非线性控制流图的全局指令调度由于非线性控制流的控制流图的复杂性不易计算出一条指令在其所在控制流图中的优先级,因此也不易判断来自不同基本块的指令的优先顺序,从而导致在决定一条指令何时被调度出该指令所在的基本块以及调度到哪儿时倾向于保守和随意。例如D.Bernstetin的全局指令调度的启发性方法优先来自这些基本块的指令:调度器当前正在调度的基本块以及与当前基本块控制等价的基本块。然而,这种启发性方法往往导致处在关键路径上的指令被滞后。本文提出的迭代式全局指令调度算法基于D.Bernstein的全局调度算法。它采用与D.Bernstein相同的启发性方法,但有选择地多次调度一个基本块使得处在关键路径上的指令被尽早调度。实验结果表明该算法以增加10%的调度时间开销提高调度器8%的性能。It is quite difficult for a non-linear control flow based acyclic global scheduler to determine an instruction's priority with respect to the control flow graph that scheduler deals with due to the complexity of the control flow. And hence, the approach to determine when an instruction should be moved across block boundary is ad hoc. Take D. Bernstein's global scheduling algorithm as an example, its heuristic favors the candidates come from the block that scheduler currently deals with and those blocks that are control equivalent with that block. Despite the straightfor- ward nature of this scheme, it may postpone some instructions on critical path and hence lengthen the execution time. The iterative scheduling proposed in this paper is the extension to the D. Bernstein's algorithm. It employs the same heuristic approach as the D'Bernsteins'. However, it schedules an instruction on critical path as early as possible by selectively scheduling a block multiple times. The experiment indicates that the iterative scheduling can improve the performance of scheduler by as much as 8% at the cost the extra 10% scheduling time.

关 键 词：迭代式 全局指令调度 非线性控制流图 启发性方法 

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