Re: Progress in instruction scheduling?

Sid Touati <SidTouati@inria.fr>
Tue, 22 Apr 2008 11:18:26 +0200

          From comp.compilers
Related articles
Progress in instruction scheduling? linuxkaffee@gmx.net (Stephan Ceram) (2008-03-17)
Re: Progress in instruction scheduling? omerbeg@gmail.com (=?UTF-8?B?IO+7i++7pO+6riDvuqnvu6vvu6Dvu67vu68=?=) (2008-03-18)
Re: Progress in instruction scheduling? boldyrev+nospam@cgitftp.uiggm.nsc.ru (Ivan Boldyrev) (2008-03-19)
Re: Progress in instruction scheduling? SidTouati@inria.fr (Sid Touati) (2008-04-22)
| List of all articles for this month |
From: Sid Touati <SidTouati@inria.fr>
Newsgroups: comp.compilers
Date: Tue, 22 Apr 2008 11:18:26 +0200
Organization: I.N.R.I.A Rocquencourt
References: 08-03-068 08-03-078
Keywords: optimize
Posted-Date: 22 Apr 2008 10:23:41 EDT

> There is some recent work on optimal scheduling which compares with
> the list scheduling heuristic. The problem is that the list scheduler
> is very close to optimal and much faster than the optimal one.


Sorry to contradict you, list schedulers are far from the optimal,
twice the optimal in extreme case...
For very small basic blocks, list schedulers are good, as any scheduling
technique.


The problem comes when considering large basic blocks, which is the most
common codes: for large basic blocks, you cannot compute optimal
instruction schedules easily (because it is an NP-complete problem), so
you cannot compare list schedulers to optimal schedulers.


S.T.


Post a followup to this message

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