language: en

Efficient Formulation for Optimal Modulo Schedulers

Alexandre E. Eichenberger Edward S. Davidson
ECE Department EECS Department North Carolina State University University of Michigan
Raleigh, NC 27695-7911 Ann Arbor, MI 48109-2122
alexe@eos.ncsu.edu davidson@eecs.umich.edu

Abstract Modulo scheduling algorithms based on optimal solvers have been proposed to investigate and tune the performance of modulo scheduling heuristics. While recent advances have broadened the scope for which the optimal approach is applicable, this approach increasingly suffers from large execution times. In this paper, we propose a more efficient formulation of the modulo scheduling space that significantly decreases the execution time of solvers based on integer linear programs. For example, the total execution time is reduced by a factor of 8.6 when 782 loops from the Perfect Club, SPEC, and Livermore Fortran Kernels are scheduled for minimum register requirements using the more efficient formulation instead of the traditional formulation. Experimental evidence further indicates that significantly larger loops can be scheduled under realistic machine constraints.

1 Introduction