* machine learning for loop unrolling
@ 2007-06-08 13:30 Stefan Ciobaca
2007-06-09 0:01 ` Zdenek Dvorak
2007-06-15 16:52 ` Stefan Ciobaca
0 siblings, 2 replies; 9+ messages in thread
From: Stefan Ciobaca @ 2007-06-08 13:30 UTC (permalink / raw)
To: gcc
Hello everyone,
For my bachelor thesis I'm modifying gcc to use machine learning to
predict the optimal unroll factor for different loops (inspired from
this paper: http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-938.pdf).
I've compiled gcc 4.1.2 on my machine and I've located the
loop-unroll.c file, where the unrolling is actually done (Richard
Guenther also suggested that I loop in tree-ssa-loop*.c, because some
unrolling is done at that level. From what I can tell, only complete
unrolling is done there, which is not interesting from a machine
learning point of view).
To learn the best unroll factor, I need several features for each
loop. I've already figured out how to compute some of them:
- number of operations (num_loop_insns)
- number of branches (num_loop_branches)
- loop nest level (can be easily computed by walking struct loops *)
but there are a lot of other features suggested by the authors of the
paper, for which I couldn't locate a convenient function:
The number of floating point ops. in loop body.
The number of memory ops. in loop body.
The number of operands in loop body.
The number of implicit instructions in loop body.
The number of unique predicates in loop body.
The estimated latency of the critical path of loop.
The estimated cycle length of loop body.
The language (C or Fortran).
The number of parallel "computations" in loop.
The max. dependence height of computations.
The max. height of memory dependencies of computations.
The max. height of control dependencies of computations.
The average dependence height of computations.
The number of indirect references in loop body.
The min. memory-to-memory loop-carried dependence.
The number of memory-to-memory dependencies.
The tripcount of the loop (-1 if unknown).
The number of uses in the loop.h
The number of defs. in the loop.
Of course, not all of these are relevant to gcc. I'm looking at ways
to compute some of these features, hopefully the most relevant ones.
If there is already some work done that I could use in order to
compute some of these features, I'd be glad if you could tell me about
it. Also, if anyone can think of some useful features, related to the
target architecture or the loops structure, I'd be glad to hear about
them.
Also, I'm interested in some benchmarks. Many of the research papers
that describe compiler optimizations use the SPEC* benchmarks, but
these are not free, so I'm looking for alternatives. Currently I'm
looking into:
- OpenBench
- Botan
- CSiBE
- Polyhedron
(thanks to richi of #gcc for the last 3)
Do you know any other one that would be better?
Here is how I'm thinking of conducting the experiment:
- for each innermost loop:
- compile with the loop unrolled 1x, 2x, 4x, 8x, 16x, 32x and
measure the time the benchmark takes
- write down the loop features and the best unroll factor
- apply some machine learning technique to the above data to determine
the correlations between loop features and best unroll factor
- integrate the result into gcc and measure the benchmarks again
Do you think it is ok to only consider inner-most loops? What about
the unroll factors? Should I consider bigger unroll factors? Do you
think the above setup is ok?
I welcome any feedback on this.
Thank you,
Stefan Ciobaca
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: machine learning for loop unrolling
2007-06-08 13:30 machine learning for loop unrolling Stefan Ciobaca
@ 2007-06-09 0:01 ` Zdenek Dvorak
2007-06-09 7:14 ` Maxim Kuvyrkov
2007-06-15 16:52 ` Stefan Ciobaca
1 sibling, 1 reply; 9+ messages in thread
From: Zdenek Dvorak @ 2007-06-09 0:01 UTC (permalink / raw)
To: Stefan Ciobaca; +Cc: gcc
Hello,
> The number of floating point ops. in loop body.
> The number of memory ops. in loop body.
> The number of operands in loop body.
> The number of implicit instructions in loop body.
> The number of unique predicates in loop body.
> The number of indirect references in loop body.
> The number of uses in the loop.h
> The number of defs. in the loop.
you have to scan insns in loop body, and check what they do
for this.
> The number of parallel "computations" in loop.
> The estimated latency of the critical path of loop.
> The estimated cycle length of loop body.
> The max. dependence height of computations.
> The max. height of memory dependencies of computations.
> The max. height of control dependencies of computations.
> The average dependence height of computations.
> The min. memory-to-memory loop-carried dependence.
> The number of memory-to-memory dependencies.
This is a bit more difficult; I guess you could persuade scheduler to
give you this information, but I have no idea how exactly. See
modulo-sched.c, it considers similar kind of information.
> The language (C or Fortran).
You may check name in langhooks.
> The tripcount of the loop (-1 if unknown).
See find_simple_exit and related functions in loop-iv.c.
> Here is how I'm thinking of conducting the experiment:
>
> - for each innermost loop:
> - compile with the loop unrolled 1x, 2x, 4x, 8x, 16x, 32x and
> measure the time the benchmark takes
> - write down the loop features and the best unroll factor
> - apply some machine learning technique to the above data to determine
> the correlations between loop features and best unroll factor
> - integrate the result into gcc and measure the benchmarks again
>
> Do you think it is ok to only consider inner-most loops?
We do not unroll non-innermost loops at the moment, so if you want to
test non-innermost loops, you would probably have to extend some loop
manipulation functions (loop unrolling was written to work for
non-innermost loops as well, but it was not well tested and thus it is
very likely buggy).
> What about
> the unroll factors? Should I consider bigger unroll factors?
I think unroll factors over 32 should not give you much more gain,
but you will see what results you will get.
> Do you think the above setup is ok?
I am somewhat skeptical; I would expect the results to be quite
target-dependent, and also to differ from program to program. Thus,
it may be somewhat hard to derive a useful general heuristics from
them. But I would be very happy to be proven wrong :-)
Zdenek
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: machine learning for loop unrolling
2007-06-09 0:01 ` Zdenek Dvorak
@ 2007-06-09 7:14 ` Maxim Kuvyrkov
0 siblings, 0 replies; 9+ messages in thread
From: Maxim Kuvyrkov @ 2007-06-09 7:14 UTC (permalink / raw)
To: Zdenek Dvorak; +Cc: Stefan Ciobaca, gcc
Zdenek Dvorak wrote:
...
>> The number of parallel "computations" in loop.
>> The estimated latency of the critical path of loop.
>> The estimated cycle length of loop body.
>> The max. dependence height of computations.
>> The max. height of memory dependencies of computations.
>> The max. height of control dependencies of computations.
>> The average dependence height of computations.
>> The min. memory-to-memory loop-carried dependence.
>> The number of memory-to-memory dependencies.
>
> This is a bit more difficult; I guess you could persuade scheduler to
> give you this information, but I have no idea how exactly. See
> modulo-sched.c, it considers similar kind of information.
Stefan,
You can get a DDG for an acyclic graph (which one iteration of the loop
is :) from sched-deps.c. From that DDG it should not be difficult to
compute properties you want. If you want to get interloop properties,
then take a look at ddg.c - modulo-sched.c uses it to build interloop
dependencies.
--
Maxim
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: machine learning for loop unrolling
2007-06-08 13:30 machine learning for loop unrolling Stefan Ciobaca
2007-06-09 0:01 ` Zdenek Dvorak
@ 2007-06-15 16:52 ` Stefan Ciobaca
2007-06-15 19:31 ` Zdenek Dvorak
1 sibling, 1 reply; 9+ messages in thread
From: Stefan Ciobaca @ 2007-06-15 16:52 UTC (permalink / raw)
To: gcc
Thank you everybody with the helpful input.
I ran into a small problem. I have some features ready (well, not
everything I wanted, but still good enough). I'm now trying to
instrument the resulting code to time each loop independently.
Essentially, what I want is to programatically modify loops from:
for (...)
{
}
to
s = clock()
for (...)
{
}
stuff += clock() - s
Of course, instead of clock(), I'd like to use a non-intrusive
mechanism. However, my research on this topic didn't lead to anything
but perfsuite, which doesn't work very well for me (should it?).
So here are the questions
- how can I actually insert the code (I need to do this during the
loop-unrolling phase, when the code is already in RTL form)?
- what performance measurement should I try?
- what other related work is out there?
Thanks,
Stefan Ciobaca
On 6/8/07, Stefan Ciobaca <stefan.ciobaca@gmail.com> wrote:
> Hello everyone,
>
> For my bachelor thesis I'm modifying gcc to use machine learning to
> predict the optimal unroll factor for different loops (inspired from
> this paper: http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-938.pdf).
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: machine learning for loop unrolling
2007-06-15 16:52 ` Stefan Ciobaca
@ 2007-06-15 19:31 ` Zdenek Dvorak
0 siblings, 0 replies; 9+ messages in thread
From: Zdenek Dvorak @ 2007-06-15 19:31 UTC (permalink / raw)
To: Stefan Ciobaca; +Cc: gcc
Hello,
> Of course, instead of clock(), I'd like to use a non-intrusive
> mechanism. However, my research on this topic didn't lead to anything
> but perfsuite, which doesn't work very well for me (should it?).
>
> So here are the questions
>
> - how can I actually insert the code (I need to do this during the
> loop-unrolling phase, when the code is already in RTL form)?
that is a bit difficult; you will run into all sorts of problems,
especially if you will want to emit new calls. It would be simpler
to emit the measurement code on gimple (see e.g. value-prof.c where
something similar is done), although it would then also be nontrivial
to match the loops to those found also on RTL. In some older versions
of gcc (I think 4.0) we used to have value profiling on RTL, you may
check that to see how we used to do that.
Zdenek
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: machine learning for loop unrolling
2007-06-08 14:31 Stefan Ciobaca
2007-06-08 19:04 ` Kenneth Hoste
@ 2007-06-18 6:35 ` Ken Raeburn
1 sibling, 0 replies; 9+ messages in thread
From: Ken Raeburn @ 2007-06-18 6:35 UTC (permalink / raw)
To: stefan.ciobaca+gcc; +Cc: gcc
> - compile with the loop unrolled 1x, 2x, 4x, 8x, 16x, 32x and
> measure the time the benchmark takes
The optimal unrolling factor may not be a power of two, depending on
icache size (11 times the loop body size?), iteration count (13*n for
some unknown n?), and whether there are actions performed inside the
loop once or twice every N passes (for N not a power of two).
The powers of two would probably hit a lot of the common cases, but
you might want to throw in some intermediate values too, if it's too
costly to check all practical values.
Ken
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: machine learning for loop unrolling
@ 2007-06-10 21:54 Grigori Fursin
0 siblings, 0 replies; 9+ messages in thread
From: Grigori Fursin @ 2007-06-10 21:54 UTC (permalink / raw)
To: stefan.ciobaca+gcc, gcc
Hi,
In addition to Kenneth's reply, here are a few references you may want to look at:
Edwin Bonilla, "Predicting Good Compiler Transformations Using Machine Learning",
MS Thesis, School of Informatics, University of Edinburgh, UK, October 2004.
http://www.inf.ed.ac.uk/publications/thesis/online/IM040129.pdf
It's about using machine learning to predict loop unrolling.
F. Agakov, E. Bonilla, J. Cavazos, B. Franke, G. Fursin, M.F.P. O'Boyle, J. Thomson,
M. Toussaint and C.K.I. Williams. Using Machine Learning to Focus Iterative Optimization.
Proceedings of the 4th Annual International Symposium on Code Generation and Optimization (CGO),
New York, NY, USA, March 2006
http://fursin.net/papers/abcp2006.pdf
You may also want to look at our project on GCC Interactive Compilation Interface (GCC-ICI)
to access internal GCC transformations to enable external optimizations particularly
using machine learning (we are now working on a new version which should be available
in mid/end of summer):
http://gcc-ici.sourceforge.net
http://www.hipeac.net/system/files?file=7_Fursin.pdf
Hope it will be of any help,
Grigori Fursin
=====================================
Grigori Fursin, PhD
Research Fellow, INRIA Futurs, France
http://fursin.net/research
Re: machine learning for loop unrolling
From: Kenneth Hoste <kenneth dot hoste at elis dot ugent dot be>
To: stefan dot ciobaca+gcc at gmail dot com
Cc: GCC <gcc at gcc dot gnu dot org>
Date: Fri, 8 Jun 2007 21:04:05 +0200
Subject: Re: machine learning for loop unrolling
References: <165ddd80706080731m5771f486i59a1211be1056087@mail.gmail.com>
--------------------------------------------------------------------------------
On 08 Jun 2007, at 16:31, Stefan Ciobaca wrote:
Hello everyone,
For my bachelor thesis I'm modifying gcc to use machine learning to
predict the optimal unroll factor for different loops (inspired from
this paper: http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS- TR-938.pdf).
Interesting. I'm using evolutionary algorithms for similar purposes in my current research...
<snip>
Of course, not all of these are relevant to gcc. I'm looking at ways
to compute some of these features, hopefully the most relevant ones.
If there is already some work done that I could use in order to
compute some of these features, I'd be glad if you could tell me about
it. Also, if anyone can think of some useful features, related to the
target architecture or the loops structure, I'd be glad to hear about
them.
I'm afraid I can't help here, I'm not familiar at all with GCCs internals.
Also, I'm interested in some benchmarks. Many of the research papers
that describe compiler optimizations use the SPEC* benchmarks, but
these are not free, so I'm looking for alternatives. Currently I'm
looking into:
- OpenBench
- Botan
- CSiBE
- Polyhedron
(thanks to richi of #gcc for the last 3)
Do you know any other one that would be better?
But I can help here. Polyhedron is Fortran-only, but are well-suited for timing experiments (i.e.
they run long enough to have reasonable running times, but aren't too long either).
CSiBE is more targetted to code size, I believe the runtimes are ridicously small. I'm not familiar
with the other two.
Some other possibilities:
* MiDataSets (also fairly small when run only once, but the suite allows you to adjust the outer
loop iteration count to increase runtimes) [http://sourceforge.net/projects/midatasets]
* MediaBench / MediaBench II: multimedia workloads, which typically iterate over frames for example
[http://euler.slu.edu/~fritts/ mediabench/]
* BioMetricsWorkload [http://www.ideal.ece.ufl.edu/main.php?action=bmw]
* BioPerf: gene sequence analysis, ... [http://www.bioperf.org/]
* some other benchmarks commonly used when testing GCC [http:// www.suse.de/~gcctest]
I've been using the above with GCC and most work pretty well (on x86).
Here is how I'm thinking of conducting the experiment:
- for each innermost loop:
- compile with the loop unrolled 1x, 2x, 4x, 8x, 16x, 32x and
measure the time the benchmark takes
- write down the loop features and the best unroll factor
- apply some machine learning technique to the above data to determine
the correlations between loop features and best unroll factor
Any idea which? There's a huge number of different techniques out there, choosing an appropiate one
is critical to success.
- integrate the result into gcc and measure the benchmarks again
When using machine learning techniques to build some kind of model, a common technique is
crossvalidation.
Say you have 20 benchmarks, no matter which ones. You use the larger part of those (for example 15)
to build the model (i.e. determine the correlations between loop features and best unroll factor),
and then test performance of that on the other ones. The important thing is not to use the
benchmarks you test with when using the machine learning technique. That way, you can (hopefully)
show that the stuff you've learned should work for other programs too.
Do you think it is ok to only consider inner-most loops? What about
the unroll factors? Should I consider bigger unroll factors? Do you
think the above setup is ok?
I'd say: don't be afraid to try too much. Try insane unroll factors too, just for testing purposes.
You don't want to limit yourself to 32x when the optimal could be 64x for example.
I welcome any feedback on this.
Who is your advisor on this? Where are you doing your bachelors thesis?
greetings,
Kenneth
--
Computer Science is no more about computers than astronomy is about telescopes. (E. W. Dijkstra)
Kenneth Hoste
ELIS - Ghent University
email: kenneth.hoste@elis.ugent.be
blog: http://www.elis.ugent.be/~kehoste/blog
website: http://www.elis.ugent.be/~kehoste
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: machine learning for loop unrolling
2007-06-08 14:31 Stefan Ciobaca
@ 2007-06-08 19:04 ` Kenneth Hoste
2007-06-18 6:35 ` Ken Raeburn
1 sibling, 0 replies; 9+ messages in thread
From: Kenneth Hoste @ 2007-06-08 19:04 UTC (permalink / raw)
To: stefan.ciobaca+gcc; +Cc: GCC
On 08 Jun 2007, at 16:31, Stefan Ciobaca wrote:
> Hello everyone,
>
> For my bachelor thesis I'm modifying gcc to use machine learning to
> predict the optimal unroll factor for different loops (inspired from
> this paper: http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-
> TR-938.pdf).
Interesting. I'm using evolutionary algorithms for similar purposes
in my current research...
> <snip>
>
> Of course, not all of these are relevant to gcc. I'm looking at ways
> to compute some of these features, hopefully the most relevant ones.
> If there is already some work done that I could use in order to
> compute some of these features, I'd be glad if you could tell me about
> it. Also, if anyone can think of some useful features, related to the
> target architecture or the loops structure, I'd be glad to hear about
> them.
I'm afraid I can't help here, I'm not familiar at all with GCCs
internals.
>
> Also, I'm interested in some benchmarks. Many of the research papers
> that describe compiler optimizations use the SPEC* benchmarks, but
> these are not free, so I'm looking for alternatives. Currently I'm
> looking into:
>
> - OpenBench
> - Botan
> - CSiBE
> - Polyhedron
>
> (thanks to richi of #gcc for the last 3)
>
> Do you know any other one that would be better?
But I can help here. Polyhedron is Fortran-only, but are well-suited
for timing experiments (i.e. they run long enough to have reasonable
running times, but aren't too long either).
CSiBE is more targetted to code size, I believe the runtimes are
ridicously small. I'm not familiar with the other two.
Some other possibilities:
* MiDataSets (also fairly small when run only once, but the suite
allows you to adjust the outer loop iteration count to increase
runtimes) [http://sourceforge.net/projects/midatasets]
* MediaBench / MediaBench II: multimedia workloads, which typically
iterate over frames for example [http://euler.slu.edu/~fritts/
mediabench/]
* BioMetricsWorkload [http://www.ideal.ece.ufl.edu/main.php?action=bmw]
* BioPerf: gene sequence analysis, ... [http://www.bioperf.org/]
* some other benchmarks commonly used when testing GCC [http://
www.suse.de/~gcctest]
I've been using the above with GCC and most work pretty well (on x86).
>
> Here is how I'm thinking of conducting the experiment:
>
> - for each innermost loop:
> - compile with the loop unrolled 1x, 2x, 4x, 8x, 16x, 32x and
> measure the time the benchmark takes
> - write down the loop features and the best unroll factor
> - apply some machine learning technique to the above data to determine
> the correlations between loop features and best unroll factor
Any idea which? There's a huge number of different techniques out
there, choosing an appropiate one is critical to success.
> - integrate the result into gcc and measure the benchmarks again
When using machine learning techniques to build some kind of model, a
common technique is crossvalidation.
Say you have 20 benchmarks, no matter which ones. You use the larger
part of those (for example 15) to build the model (i.e. determine the
correlations between loop features and best unroll factor), and then
test performance of that on the other ones. The important thing is
not to use the benchmarks you test with when using the machine
learning technique. That way, you can (hopefully) show that the stuff
you've learned should work for other programs too.
>
> Do you think it is ok to only consider inner-most loops? What about
> the unroll factors? Should I consider bigger unroll factors? Do you
> think the above setup is ok?
I'd say: don't be afraid to try too much. Try insane unroll factors
too, just for testing purposes. You don't want to limit yourself to
32x when the optimal could be 64x for example.
>
> I welcome any feedback on this.
Who is your advisor on this? Where are you doing your bachelors thesis?
greetings,
Kenneth
--
Computer Science is no more about computers than astronomy is about
telescopes. (E. W. Dijkstra)
Kenneth Hoste
ELIS - Ghent University
email: kenneth.hoste@elis.ugent.be
blog: http://www.elis.ugent.be/~kehoste/blog
website: http://www.elis.ugent.be/~kehoste
^ permalink raw reply [flat|nested] 9+ messages in thread
* machine learning for loop unrolling
@ 2007-06-08 14:31 Stefan Ciobaca
2007-06-08 19:04 ` Kenneth Hoste
2007-06-18 6:35 ` Ken Raeburn
0 siblings, 2 replies; 9+ messages in thread
From: Stefan Ciobaca @ 2007-06-08 14:31 UTC (permalink / raw)
To: gcc
Hello everyone,
For my bachelor thesis I'm modifying gcc to use machine learning to
predict the optimal unroll factor for different loops (inspired from
this paper: http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-938.pdf).
I've compiled gcc 4.1.2 on my machine and I've located the
loop-unroll.c file, where the unrolling is actually done (Richard
Guenther also suggested that I loop in tree-ssa-loop*.c, because some
unrolling is done at that level. From what I can tell, only complete
unrolling is done there, which is not interesting from a machine
learning point of view).
To learn the best unroll factor, I need several features for each
loop. I've already figured out how to compute some of them:
- number of operations (num_loop_insns)
- number of branches (num_loop_branches)
- loop nest level (can be easily computed by walking struct loops *)
but there are a lot of other features suggested by the authors of the
paper, for which I couldn't locate a convenient function:
The number of floating point ops. in loop body.
The number of memory ops. in loop body.
The number of operands in loop body.
The number of implicit instructions in loop body.
The number of unique predicates in loop body.
The estimated latency of the critical path of loop.
The estimated cycle length of loop body.
The language (C or Fortran).
The number of parallel "computations" in loop.
The max. dependence height of computations.
The max. height of memory dependencies of computations.
The max. height of control dependencies of computations.
The average dependence height of computations.
The number of indirect references in loop body.
The min. memory-to-memory loop-carried dependence.
The number of memory-to-memory dependencies.
The tripcount of the loop (-1 if unknown).
The number of uses in the loop.h
The number of defs. in the loop.
Of course, not all of these are relevant to gcc. I'm looking at ways
to compute some of these features, hopefully the most relevant ones.
If there is already some work done that I could use in order to
compute some of these features, I'd be glad if you could tell me about
it. Also, if anyone can think of some useful features, related to the
target architecture or the loops structure, I'd be glad to hear about
them.
Also, I'm interested in some benchmarks. Many of the research papers
that describe compiler optimizations use the SPEC* benchmarks, but
these are not free, so I'm looking for alternatives. Currently I'm
looking into:
- OpenBench
- Botan
- CSiBE
- Polyhedron
(thanks to richi of #gcc for the last 3)
Do you know any other one that would be better?
Here is how I'm thinking of conducting the experiment:
- for each innermost loop:
- compile with the loop unrolled 1x, 2x, 4x, 8x, 16x, 32x and
measure the time the benchmark takes
- write down the loop features and the best unroll factor
- apply some machine learning technique to the above data to determine
the correlations between loop features and best unroll factor
- integrate the result into gcc and measure the benchmarks again
Do you think it is ok to only consider inner-most loops? What about
the unroll factors? Should I consider bigger unroll factors? Do you
think the above setup is ok?
I welcome any feedback on this.
Thank you,
Stefan Ciobaca
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2007-06-18 5:29 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-06-08 13:30 machine learning for loop unrolling Stefan Ciobaca
2007-06-09 0:01 ` Zdenek Dvorak
2007-06-09 7:14 ` Maxim Kuvyrkov
2007-06-15 16:52 ` Stefan Ciobaca
2007-06-15 19:31 ` Zdenek Dvorak
2007-06-08 14:31 Stefan Ciobaca
2007-06-08 19:04 ` Kenneth Hoste
2007-06-18 6:35 ` Ken Raeburn
2007-06-10 21:54 Grigori Fursin
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).