Part of Advances in Neural Information Processing Systems 10 (NIPS 1997)
J. Moss, Paul Utgoff, John Cavazos, Doina Precup, Darko Stefanovic, Carla Brodley, David Scheeff
Program execution speed on modem computers is sensitive, by a factor of two or more, to the order in which instructions are presented to the proces(cid:173) sor. To realize potential execution efficiency, an optimizing compiler must employ a heuristic algorithm for instruction scheduling. Such algorithms are painstakingly hand-crafted, which is expensive and time-consuming. We show how to cast the instruction scheduling problem as a learning task, ob(cid:173) taining the heuristic scheduling algorithm automatically. Our focus is the narrower problem of scheduling straight-line code (also called basic blocks of instructions). Our empirical results show that just a few features are ad(cid:173) equate for quite good performance at this task for a real modem processor, and that any of several supervised learning methods perform nearly opti(cid:173) mally with respect to the features used.