TRACE SCHEDULING - A SECOND LOOK

 Utpal Banerjee
 Intel Corporation
 Santa Clara, CA
 USA

Abstract:  Almost every processor built today tries to exploit instruction
level parallelism (ILP) to some extent.  Advanced compiler techniques
are needed to fully expose the amount of ILP present in a given program. 
Since the time of its introduction, trace scheduling has influenced much
of the work on compile-time ILP transformations.  Treatments of trace
scheduling found in the literature tend to be long, quite complicated,
and rather mysterious.  This talk gives a rigorous mathematical presentation
of the theory of trace scheduling that clearly explains the main
concepts. 

We give simple proofs of existing results, and present several key
theorems that are completely new.