[LLVMdev] [Fwd: Optimization: Conclusions from Evolutionary Analysis]

[Vikram Adve]

On Nov 19, 2003, at 2:05 PM, Reid Spencer wrote:

> On Tue, 2003-11-18 at 15:11, Vikram Adve wrote:
>> This is a hot topic in the compiler research community, but the focus
>> there is on
>> (a) choosing the right optimization sequences internally and
>> transparently, rather than through combinations of options,
>> (b) performance prediction techniques so you don't actually have to 
>> run
>> gazillion different choices, and perhaps can even avoid the problem of
>> choosing representative inputs, as you talked about, and
>
> My experience with performance prediction (over a 20 year career) is
> that its useless.  The simulation world has long sought to be able to
> predict outcomes, performance, scalability, etc. I haven't seen a model
> yet that gets lower than a +/-50% error rate.


We should probably take this discussion of this list, but here's a 
counterpoint :)  This is a paper that is to appear in ACM TOCS and 
describes a manual, analytical modeling technique that gets 0-10% 
prediction errors for complex, real-world parallel programs on real 
systems:
		http://www.cs.uiuc.edu/~vadve/Papers/detmodel.tocsfinal.pdf

My experience (after having done my Ph.D. thesis on performance 
prediction and then abandoned it) is that it is really hard to do 
comprehensive performance prediction for all aspects of program 
behavior, but much more tractable to do it for individual performance 
issues.  Also certain issues (e.g., processor pipelines) are much 
harder than others.

But I think your other points below are quite valid:

> In the general case, the
> only *reliable* way to do it is through collecting actual data.

In fact, combining real data with models is what is often needed (and 
what we used).

> Of
> course, in the specific case of compiler output, it might be possible 
> to
> get higher levels of accuracy. It'll be interesting to follow this
> research.

This can also make it more practical for programmers to actually use.


>
>> (c) developing flexible internal representations so that you can
>> dynamically generate appropriate code sequences.
>
> Now THAT I agree with :)
>
>> We are actually involved in a project with IBM that aims to look at 
>> all
>> of these issues.  Needless to say, I'm hoping that they will use LLVM
>> as one of the components of the infrastructure for this work :)  They
>> do seem interested.
>
> I hope so too .. great validation.
>
> Reid.


--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.cs.uiuc.edu/