Classification and generation of schedules for VLIW processors

Exact methods for optimal instruction scheduling are gaining importance. They differ, however, considerably in the assumed processor model and in the space of schedules searched for an optimal solution. We identify and analyze different classes of schedules for VLIW processors. The classes are induced by various common techniques for generating or enumerating them, such as integer linear programming or list scheduling with backtracking. In particular, we study the relationship between VLIW schedules and their equivalent linearized forms (which may be used, e.g., with superscalar processors), and we identify classes of VLIW schedules that can be created from a linearized form using VLIW compaction methods that are just the static equivalents of dynamic instruction dispatch algorithms of in-order and out-of-order issue superscalar processors. For example, we study the class of greedy schedules and show that, if all instructions have multiblock reservation tables, it is safe for time optimization to consider greedy schedules only. We also show that, in certain situations, certain schedules generally cannot be constructed by incremental scheduling algorithms that are based on topological sorting of the data dependence graph. We summarize our findings as a hierarchy of classes of VLIW schedules. These results can sharpen the interpretation of the term 'optimality' used with various methods for optimal VLIW scheduling, and may help to identify classes that can be safely ignored when searching for an optimal schedule. Copyright (c) 2007 John Wiley & Sons, Ltd.