Re: Operation Latencies

kernel_learner@yahoo.com (Learner) wrote in message news:04-02-090...
> Many operations have variable latencies...so I was wondering how
> compilers do scheduling for VLIW and how they calculate the critical
> path of a data dependence graph when the latencies of operations are
> not known at compile time.. Some scheduling like s/w pipelining
> requires calculation of RecMII which needs to know the critical path
> in the ddg... How can you be sure you have the critical path when the
> latencies can vary?


    Notice that most scheduling problems are at least NP hard
(e.g. basic block scheduling with constant latencies, loop scheduling
is related to the stopping problem, it's EXP-space hard for most
languages), and heuristics are usually used for solving them. One of
these heuristics is assuming constant latencies, e.g. Level 1 cache
hit for the loads.
    BTW, you can have many critical paths in your DDG.
What is usually important is the max distance from the start/to the end
of the DDG etc.. If your VLIW isn't infinitely wide, your scheduling
wouldn't always be perfect, and the critical paths length is only a rough
lower bound for performance anyway.


> What are the usual approaches ?


    First, the optimistic one, assuming most frequently appearing latencies.
  Another possibility is to use a more detailed processor model and
compute better estimations of the latencies, at least for the top-down
scheduling of a DDG. It might need recomputation of the distances,
but recall that you might need it anyway when your scheduler sees
that it's not minimal length anymore.

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