Instruction Scheduling Complexity

Stephan Ceram <>
30 Sep 2008 20:57:11 GMT

          From comp.compilers

Related articles
Instruction Scheduling Complexity (Stephan Ceram) (2008-09-30)
Re: Instruction Scheduling Complexity (virtuPIC) (2008-10-24)
| List of all articles for this month |

From: Stephan Ceram <>
Newsgroups: comp.compilers
Date: 30 Sep 2008 20:57:11 GMT
Organization: Compilers Central
Keywords: optimize, question
Posted-Date: 30 Sep 2008 19:19:11 EDT


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

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).


Post a followup to this message

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