Constraint Analysis and Heuristic Scheduling Methods
Scheduling is one of the main problems that need to be solved by
high-level hardware and software compilers. Existing heuristics are
often incapable of finding feasible solutions for practical
examples, because the tight time and resource constraints make the
feasible-solution subspace very small compared to the size of the
full search space. For that reason, constraint-analysis techniques
that help the scheduler find feasible solutions are nowadays a
subject of research. In this paper, the effect of constraint
analysis on heuristic schedulers is experimentally quantified to
investigate to which extent constraint analysis improves the quality
of such schedulers, and also to see which heuristics complement it
well. The results show that, for most experiments,
constraint analysis helps to improve the obtained schedules in terms
of the latency of the schedule. It combines particularly well with
the freeing-count heuristic.
(postscript /
pdf
version of the complete paper)
Back to the list of publications.