30 Sep 2008 20:57:11 GMT

Related articles |
---|

Instruction Scheduling Complexity linuxkaffee@gmx.net (Stephan Ceram) (2008-09-30) |

Re: Instruction Scheduling Complexity WebMaster@airspace-v.com (virtuPIC) (2008-10-24) |

From: | Stephan Ceram <linuxkaffee@gmx.net> |

Newsgroups: | comp.compilers |

Date: | 30 Sep 2008 20:57:11 GMT |

Organization: | Compilers Central |

Keywords: | optimize, question |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.