Re: Instruction Scheduling Complexity

virtuPIC <>
Fri, 24 Oct 2008 04:50:29 -0700 (PDT)

          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: virtuPIC <>
Newsgroups: comp.compilers
Date: Fri, 24 Oct 2008 04:50:29 -0700 (PDT)
Organization: Compilers Central
References: 08-09-141
Keywords: code, theory
Posted-Date: 25 Oct 2008 06:37:09 EDT

On 30 Sep., 22:57, Stephan Ceram <> wrote:

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

If I remember correctly the problem of scheduling for a multi-issue
processor with maximum latency of more than one cycle is NP-complete.
Usually heuristical algorithms of run time linear in number of
instructions are used.

Airspace V - international hangar flying! for tools & toys

Post a followup to this message

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