Re: Instruction Scheduling Complexity

virtuPIC <WebMaster@airspace-v.com>
Fri, 24 Oct 2008 04:50:29 -0700 (PDT)

          From comp.compilers

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)
| List of all articles for this month |

From: virtuPIC <WebMaster@airspace-v.com>
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 <linuxkaf...@gmx.net> 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.


Thomas
--
Airspace V - international hangar flying!
http://www.airspace-v.com/ggadgets for tools & toys


Post a followup to this message

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