Classification and generation of schedules for VLIW processors
Christoph W. Keßler, Andrzej Bednarski
Proc. of CPC'06 12th Int. Workshop on Compilers for Parallel Computers, A Coruna, Spain, Jan. 2006, pp. 60-72.
Abstract:
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 an in-order VLIW compaction heuristic,
which is just the static equivalent of the dynamic instruction dispatch
algorithm of in-order issue superscalar processors.
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
a time-optimal schedule.
Key words:
Instruction-level parallelism, instruction scheduling, code generation,
code compaction, integer linear programming, VLIW architecture.
BibTeX:
@inproceedings{ KesslerBednarski-CPC06-Classification,
author = {Christoph W. Kessler and Andrzej Bednarski},
title = {Classification and generation of schedules for {VLIW} processors},
booktitle = {Proc. 12th Int.\ Workshop on Compilers for Parallel Computers (CPC-2006)},
location = {A Coruna (Spain)},
year = 2006, month = jan,
pages = {60--72}
}
Download:
PDF
Christoph Kessler