Abstract: Branch scheduling is an effective instruction scheduling technique for VLIW machines to eliminate branch penalty. An optimized branch-delay-slot scheduling algorithm is introduced to generate an effective instruction schedule for control extensive applications. Based on program dependency graph, the proposed algorithm builds a cost model to evaluate among candidate instruction queues which are selected from the same control block, and makes an optimal choice for branch delay slot. The experimental results show that, this algorithm improves the performance of applications by 12.9% on average.

Key words: branch scheduling, delay slots, dependence analysis, Very Long Instruction Word（VLIW） architecture

摘要： 分支调度是一种有效消除分支指令延迟的指令调度技术，对于提升VLIW类处理器的性能非常重要。提出了一个针对分支延迟槽的指令调度优化算法。该算法面向VLIW体系结构，根据程序依赖图选择合适的候选指令序列；通过建立代价收益模型为分支延迟槽产生一个收益较大的指令调度序列。实验数据表明，分支调度算法可以平均提升12.9%的应用程序性能。

关键词: 分支调度, 分支延迟槽, 依赖关系, 超长指令字（VLIW）体系结构