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