Balanced Scheduling with Compiler Optimizations that Increase

Traditional list schedulers order instructions based on an optimistic estimate of the load latency imposed by the hardware and therefore cannot respond to variations in memory latency caused by cache hits and misses on non-blocking architectures. In contrast, balanced scheduling schedules instructions based on an estimate of the amount of instruction-level parallelism in the program, By scheduling independent instructions behind loads based on what the program can provide, rather than what the implementation stipulates in the best case (i.e., a cache hit), balanced scheduling can hide variations in memory latencies more effectively. Since its success depends on the amount of instruction-level parallelism in the code, balanced scheduling should perform even better when more parallelism is available. In this study, wecombinebalanced scheduling with three compiler optimization that increase instruction-level parallelism: loop unrolling, trace scheduling and cache locality analysis. Using code generated forthe DEC Alpha by the Multiflow compiler, we simulated a non-blocking processor architecture that closely models the Alpha 21164. Our results show that balanced scheduling benefits from all three optimizations, producingaverage speedups tbat range from 1.15to 1.40, across the optimizations. More importantly, because of its ability to tolerate variations in load interlocks, it improves its advantage over traditional scheduling, Without theoptimizations, balanced scheduled code is, on average, l.05times faster than that generated byatraditional scheduler; with them, its lead increases to 1.18.