Academic
Publications
EPIC Instruction Scheduling Based on Optimal Approaches

EPIC Instruction Scheduling Based on Optimal Approaches,Steve Haga,Rajeev Barua

EPIC Instruction Scheduling Based on Optimal Approaches   (Citations: 11)
BibTex | RIS | RefWorks Download
This paper presents a method for instruction scheduling that considers the scheduling restrictions in- herent in VLIW processors, particularly EPIC. EPIC architectures have the potential to offer substantial speedups versus superscalars; however, development of a number of new compiler technologies, such as improved instruction scheduling, is critical to EPIC's success. EPIC imposes restrictions on the nature and code-order of the instructions that can issue together in the same cycle. To express these restric- tions, the instructions are grouped into instruction classes such as arithmetic, memory, floating point and branch instructions. Allowable ordered combinations of instruction types are called templates. Most existing methods for instruction scheduling do not consider templates except at their last stage. For example, trace scheduling and similar methods focus on moving instructions across basic blocks. Af- ter movement, the instructions are usually put in templates using greedy algorithms such as list schedul- ing. There is a significant opportunity to improve performance if algorithms superior to greedy are used for template scheduling. The scheduling method in this paper takes the following approach. It begins with a provably op- timal algorithm for template scheduling. This algorithm is not feasible, however, since it results in an exponential compile time. Two classes of methods are used therefore to drastically reduce the compile time. First, aggressive branch-and-bound techniques are used to prune portions of the search space while retaining the optimality guarantee. Second, non-optimal heuristics are used to guide the search towards more promising solutions quickly. Results show that our techniques are able to reduce the number of NOPs in integer programs by 56% on average compared to the list-scheduling based greedy algorithm in the SGICC compiler, with only a 17% increase in compile time. Floating point programs see a 35% reduction in NOPs with a 22% increase in compile time.
Published in 2001.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: