Instruction Scheduling Complexity

Hi,


I've a question concerning the complexity of a local instruction
scheduling.


In the paper "Optimal Instruction Scheduling Using Integer
Programming" by Kent Wilken, the authors say:


"The complexity of local instruction scheduling can depend on the
maximum data-hazard latency which occurs among the target processor's
instructions. In this paper, latency is defined to be the difference
between the cycle in which instruction i executes and the first cycle
in which data-dependent instruction j can execute. Note that other
authors define latency (delay) to be the cycle difference minus one
..."


Further they make some statements about the schedulers' complexity:
"Instruction scheduling for a single-issue processor with a maximum
latency of two is easy. Instructions can be optimally scheduled in
polynomial time following the approach proposed by Bernstein and
Gertner [2]. Instruction scheduling for more complex processors is
hard. No polynomial-time algorithm is known for optimally scheduling
a single-issue processor with a maximum latency of three or more
[2]. Optimal scheduling is NP-complete for realistic multiple-issue
processors [3]."


Unfortunately, it becomes not clear which complexity a local scheduler
has for a multi-issue processor with a maximal latency of two
cycles. This is exactly what I'm interested in. Do you have an idea
what the complexity might be in that case? (Publications on that topic
are highly welcomed).


Cheers,
Stephan

Return to the comp.compilers page.
Search the comp.compilers archives again.