Proceedings of the 29th Annual Hawaii International Conference on System Sciences- 1996 Extending List Scheduling to Consider Execution Frequency*

Frequency-Based List Scheduling (FBLS) extends stan-dard List Scheduling by considering execution frequencies within a schedule. This is useful for global instruction scheduling methods that schedule groups of basic blocks, called meta-blocks, as though they were a single block Traditional local schedulers operate on the premise that each instruction is executed the same number of times as every other instruction in the “block”, an unwarrented as-sumption for meta-blocks. This assumption can lead meta-blocks schedulers to produce ineficient code. FBLS pro-vides an answer to this problem by considering the diflering execution frequencies within meta-blocks when scheduling operations. To evaluate our contention that FBLS is a useful ex-tension to stana’ard list scheduling, we implemented FBZ.S and compared it to standard list scheduling within the con-text of dominator-path scheduling [l], a meta-block global scheduling algorithm. Experimental results show overall run-time improvement of 10.9 % for livermore loops.