RFC: Prefetch instruction support

[norbert.juffa@amd.com]

Do you have any pieces of C code that would benefit from 
prefetching that Jan can use to test his changes? I agree
that more complex real world code is better than a small
benchmark for assessing the quality of an optimization. Of 
course STREAM is the ultimate memory bandwidth limited 
program so is valid data point in this case although an
artificial benchmark.

In general for Athlon, aggressive unrolling is recommended.
The ICache is huge (64K). Depending on the loop unrolling
anywhere from 4x to 16x seems helpful for "typical" code,
independent from the prefetching issue. YMMV. For example
in compilers that don't perform scalar replacement unrolling 
get's you most of the benefits anyhow. The aggressive loop 
unrolling plays jibes with the goal of having non-overlapping 
prefetches. I agree you'd probably would want a heuristic
that prevents the unroller becoming overly aggressive, e.g.
by considering code size etc. The best solution would be to
have the unrolling stage benefit from profiling information,
i.e. feedback directed optimization. Performing loop 
transformations in order to maximize the number of unit stride 
accesses is recommended for Athlon (and seems like a sensible 
policy on just about every CPU short of vector machines with 
scatter/gather capability).

I will admit that I have never thought of using prefetch for
code with large strides, e.g. 8K or some such. To first order
one would think that adding the prefetch could never hurt and 
would often improve performance. On the other hand couldn't
it increase the likelihood of conflict misses? I.e., the 
prefetch could kick data out of the cache which we are currently
working on. E.g. in a 2-way set associative cache where each
way is x KByte, prefetching accesses with stride x KByte, several
units head seems like it could be pretty deadly.

Can you point us to any relevant research on this topic. I know
that research on SW prefetching goes back at least to the early
1990, but having no easy access to a university library I am
not aware of any seminal papers on heuristics for prefetch support
in compilers (C, Fortran, or otherwise).


-- Norbert




> -----Original Message-----
> From: Tim Prince [ mailto:tprince@computer.org ]
> Sent: Tuesday, April 11, 2000 3:23 PM
> To: Frank Heldt; Jan Hubicka
> Cc: egcs@egcs.cygnus.com; Dreyzen, Alex; Juffa, Norbert
> Subject: Re: RFC: Prefetch instruction support
> 
> 
> Very interesting, and thanks for posting such a full explanation.  My
> experience with prefetch and unrolling (on hppa and mips 
> processors) would
> indicate that it is not generally useful to increase the 
> amount of unrolling
> in order to increase prefetch distance, or, to put it the other way,
> prefetch distance should not be made so large that more 
> unrolling is used
> than otherwise would be desirable.  Also, prefetch may not be 
> desirable for
> sequential (unit stride) access while it may be quite useful 
> for larger
> strides.  That depends on the application as well as the
> processor.  It's not good to base the optimizations on simple 
> benchmarks, if
> the problems of real interest stress the cache size much more than the
> benchmarks.
> 
> 
> ----- Original Message -----
> From: "Frank Heldt" <Frank.Heldt@t-online.de>
> To: "Jan Hubicka" <hubicka@atrey.karlin.mff.cuni.cz>
> Cc: <egcs@egcs.cygnus.com>; <alex.dreyzen@amd.com>; 
> <norbert.juffa@amd.com>
> Sent: Tuesday, April 11, 2000 1:17 PM
> Subject: Re: RFC: Prefetch instruction support
> 
> 
> > Hello Jan,
> >
> > really nice work. I hope this will become part of gcc, it will be
> > usefull not only on the Athlon (IIRC, the new Intel VTune 
> Compiler makes
> > massive use of prefetching on the PIII, which gives it a 
> *big* boost).
> >
> > > During last weekend I've implemented basic prefetch instruction
> framework
> > > (tested on Athlon) based on the suggestions of Alex 
> Dreyzen and Norbert
> Juffa
> > > from AMD.
> > One question: Do the prefetch instructions only work on the Athlon?
> > I remember vague, that the K6-II has them also (partly). It would be
> > nice if the K6-II can use this feature too.
> >
> > Well done, Jan. Thanks alot.
> >
> > Frank
> >
> > --
> > Frank Heldt
> > mailto:Frank.Heldt@t-online.de
> > mailto:Frank.Heldt@mahr.de
> >
>