Re: Operation Latencies

tmk@netvision.net.il (Michael Tiomkin)
12 Feb 2004 11:03:53 -0500

          From comp.compilers

Related articles
Operation Latencies kernel_learner@yahoo.com (2004-02-08)
Re: Operation Latencies touati-nospamplease@nospam-prism.uvsq.fr (TOUATI Sid) (2004-02-12)
Re: Operation Latencies tmk@netvision.net.il (2004-02-12)
Re: Operation Latencies tommy.hoffner@ericsson.com (Tommy Hoffner) (2004-02-13)
| List of all articles for this month |

From: tmk@netvision.net.il (Michael Tiomkin)
Newsgroups: comp.compilers
Date: 12 Feb 2004 11:03:53 -0500
Organization: http://groups.google.com
References: 04-02-090
Keywords: optimize, architecture
Posted-Date: 12 Feb 2004 11:03:53 EST

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.


Post a followup to this message

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