CPC 2006 CPC 2006

Call for Participation
Current List of
Program (List of Talks)
Registration Form
Travel Information

Funded by the Vicerreitoría de Investigación of the University of A Coruña and the Ministry of Education and Science of Spain

Universidade de A Coruña Ministerio de
		      Educación y Ciencia

Classification and Generation of Schedules for VLIW Processors

Christoph Kessler and Andrzej Bednarski
PELAB, Departement of Computer and Information Science, Linköpings Universitet, Sweden

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.

Back to the Workshop Program 

Please contact our webadmin with any comments or changes.