About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Int. J. Parallel Program
Paper
Optimal Modulo Scheduling Through Enumeration
Abstract
Resource-constrained software-pipelining has played an increasingly significant role in exploiting instruction-level parallelism and has drawn intensive academic and industrial interest. The challenge is to find a schedule which is optimal : i.e., given the data dependence graph (DDG) for a loop, find the fastest possible schedule under given resource constraints while keeping register usage minimal. This paper proposes a novel enumeration based modulo scheduling approach to solve this problem. The proposed approach does not require any awkward reworking of constraints into linear form and employs a realistic register model. The set of schedules enumerated also allows us to characterize the schedule space and address questions such as whether schedules using a small number of registers tend to require a large number of function units. The proposed approach has been implemented under the MOST testbed at McGill University. Experimental results on more than 1000 loops from popular benchmark programs show that enumeration is generally faster at obtaining optimal schedules than integer linear programming approaches. Compared to Huff's Slack Scheduling, enumeration found a faster schedule for almost 15% of loops, with a mean improvement of 18%. 10% of the remaining loops required fewer registers under enumeration, with a mean reduction of 16%.