Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

This talk considers instruction scheduling, an important problem from the area of compiler optimization. The instruction scheduling problem is to order a computer program's instructions, while maintaining program correctness, such that the instructions execute in a minimum number of clock cycles. Because the instruction scheduling problem is NP-complete, existing compilers use heuristic-based methods to produce approximate solutions. We describe a new approach to instruction scheduling that produces optimal instruction schedules in a reasonable time for all the scheduling problems in the industry-standard SPEC benchmark suite. The new instruction scheduler increases total compile time by only 3%. The new instruction scheduling approach is based in part on a novel set of graph transformations and on a novel branch and bound technique.

This research is joint work with Jack Liu and Mark Heffernan.