The nal publication is available at:

[Link]
Collective Optimization: A Practical Collaborative
Approach
GRIGORI FURSIN and OLIVIER TEMAM
INRIA Saclay, France
HiPEAC members
Iterative optimization is a popular and ecient research approach to optimize programs using
feedback-directed compilation. However, one of the key limitations that prevented widespread
use in production compilers and day-to-day practice is the necessity to perform a large number of
program runs with the same dataset and environment (architecture, OS, compiler) to test many
dierent combinations of optimizations. In this article, we propose to overcome such a practical
obstacle using collective optimization, where the task of optimizing a program or tuning default
compiler optimization heuristic leverages the experience of many other users continuously, rather
than being performed in isolation, and often redundantly, by each user. During this unobtrusive
approach, performance information is sent to a central database after each run and statistically
combined with the data from all users to suggest most protable optimizations for a given program
and an architecture, or to gradually improve default optimization level of a compiler for a given
architecture.
In this article, we address two key challenges of collective optimization. We show that it is
possible to simultaneously learn and improve performance while avoiding long training phases.
We also demonstrate how to use our approach with static compilers to learn optimizations across
multiple datasets and architectures without even a reference run normally needed to compute
speedups over the baseline optimization by using static function cloning and dynamic adaptation.
We present a novel probabilistic approach based on competition among pairs of optimizations
(program reaction to optimizations) to enable optimization knowledge reuse and achieve nearly
the best possible iterative optimization performance. We implemented our technique in GCC
(widespread production open-source compiler that supports multiple architectures) and connected
it to a public collective optimization database at [Link] to gather prole and optimization
data continuously and transparently in realistic environments ranging from desktop PCs and
mobile systems to supercomputers and data centers.
Categories and Subject Descriptors: D.3.4 [Programming Languages]: Processors-Compilers;
optimization; B.8.2 [Performance and Reliability]: Performance Analysis and Design Aids;
C.4 [Computer Systems Organization]: Performance of Systems-Measurement techniques;
modeling techniques
A preliminary version of this research is described in Proceedings of the International Conference
on High Performance and Embedded Architectures and Compilers (HiPEAC09).
This work has been partially supported by the EU IST FP6 STREP MILEPOST Project
(035307) [Link-MILEPOST ] and Google Summer of Code Program09.
Authors address: [Link] (corresponding author), [Link], INRIA Saclay, 3, rue Jean Ros-
tand, Orsay, 91893, France; email:[Link]@[Link] or [Link]@[Link]
Permission to make digital/hard copy of all or part of this material without fee for personal
or classroom use provided that the copies are not made or distributed for prot or commercial
advantage, the ACM copyright/server notice, the title of the publication, and its date appear, and
notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish,
to post on servers, or to redistribute to lists requires prior specic permission and/or a fee.
c 2010 ACM 1544-3566/2010/12-ART20$10.00
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
2
General Terms: Design, Languages, Measurement, Experimentation, Performance
Additional Key Words and Phrases: Collective optimization, iterative compilation, continuous op-
timization, statistical optimization, adaptive compiler, self-tuning computing systems, collective
optimization database, multiple datasets, program characterization, program reaction to opti-
mization, function cloning, runtime adaptation
1. INTRODUCTION
Many recent research eorts have shown how iterative compilation can outperform
static compiler optimizations and quickly adapt to complex processor architectures
obtaining signicant performance improvements [Whaley and Dongarra 1998; Mat-
teo and Johnson 1998; Bodin et al. 1998; Cooper et al. 1999; Kisuki et al. 2000;
Fursin et al. 2002; Cooper et al. 2002; Kulkarni et al. 2003; Triantafyllis et al.
2003; Singer and Veloso 2000; Pan and Eigenmann 2004; 2006; Hoste and Eeck-
hout 2008]. Over the years, the approach has been perfected with fast optimization
space search techniques, sophisticated machine-learning algorithms, and continu-
ous optimization [Voss and Eigenmann 2000; Monsifrot et al. 2002; Stephenson
et al. 2003; Lu et al. 2004; Lattner and Adve 2004; Franke et al. 2005; Stephenson
and Amarasinghe 2005; Zhao et al. 2005; Agakov et al. 2006; Qasem et al. 2006;
Cavazos et al. 2007; Bailey et al. 2008; Fursin et al. 2008; Dubach et al. 2009].
Nevertheless, empirical iterative optimization is far from mainstream in production
environments. Besides the usual inertia for adopting novel approaches, there are
hard technical hurdles which hinder the adoption of iterative approaches.
One of the key challenges is that iterative techniques almost always rely on a
large number of training runs (either from the target program or other training
programs) to learn the best candidate optimizations. Moreover, all these runs
must be performed with the same programs, generated with the same compiler
on the same architecture with the same datasets, and repeated a large number of
times (tens, hundreds, or thousands of times) in order to deduce the shape of the
optimization space. Naturally, in practice, a user can rarely aord execution of
the same dataset multiple times, will change architectures every so often, and may
eventually upgrade a compiler as well. We believe this practical issue of collecting
a large number of training information, relying only on production runs (as opposed
to training runs where produced results are not used) to achieve good performance
is the crux of the slow adoption of iterative techniques in real environments.
We propose to address this issue with the notion of collective optimization. The
principle is to consider that the task of optimizing a program is not an isolated
task performed by each user separately, but a collective task where users can mu-
tually benet from the experience of others. Collective optimization makes sense
because most of the programs executed in servers, data centers, and cloud comput-
ing systems or that we use daily on our mobiles and desktop PCs are also run by
many other users, either globally if they are general tools or within one or a few
institutions if they are more domain specic.
Achieving collective optimization requires to solve both an engineering and a
research issue. The engineering issue is that users should be able to seamlessly
share the outcome of their runs with other users, without slowing down execution
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
3
or compilation, should support statically compiled programs, and should avoid
complicating compiler usage. The key research issue is that we must progressively
improve overall program and compiler performance while, at the same time, we
learn how programs react to the various optimizations using production runs. In this
approach training phase and test/use phase occur simultaneously unlike traditional
iterative compilation. Hence, we must understand whether or not it is possible and
how to learn across datasets, programs or platforms at the same time. An associated
research issue is to develop a knowledge representation scheme that is relevant
across datasets, programs, and platforms. Finally, because a user will generally
run a dataset only once, we must learn the impact of optimizations on program
performance without even a reference run to decide whether selected optimizations
improve or degrade performance compared to the baseline optimization.
In this article, we show that it is possible to continuously learn across datasets,
programs, or platforms, relying solely on production runs, and progressively im-
prove overall performance across runs, reaching close to the best possible iterative
optimization performance, itself achieved under idealized (and nonrealistic) condi-
tions. We show that extensively relying on statistical competition among pairs of
optimizations provides a robust and ecient method for capturing the impact of op-
timizations on program performance, without requiring reference runs to calculate
speedups and while remaining relevant across datasets, programs, and architec-
tures. While most recent research studies are focused on learning across programs
[Stephenson and Amarasinghe 2005; Agakov et al. 2006; Cavazos et al. 2007; Fursin
et al. 2008; Dubach et al. 2009], we found that in the case of collective optimization,
learning across datasets, and to a lesser extent, across architectures, is signicantly
more important and useful. Finally, we present a solution to the engineering is-
sue in the form of an extension to GCC with collective optimization plugins which
we connected to a central optimization repository through public Web services at
[Link] [Link-repository ; Link-ICI ; Fursin 2009] to eectively distribute opti-
mization process among many users, aggregate multiple proling and optimization
data, and perform program behavior characterization and continuous competitions
between optimizations during runs.
2. EXPERIMENTAL SETUP
Benchmarks, datasets, and architectures used throughout the article are briey
introduced in this section.
Benchmarks and datasets. In order to perform a realistic evaluation of col-
lective optimization, each benchmark has to come with several datasets in order to
emulate truly distinct runs. To our knowledge, only the MiDataSets/cBench bench-
mark and dataset suite [Fursin et al. 2007; Link-MiDatasets ; Fursin 2009] based
on the MiBench [Guthaus et al. 2001] currently provides more than 20 datasets for
each of the 26 benchmarks.
Compiler and proler. All programs are optimized using the GCC 4.2.0 com-
piler; several benchmarks (qsort, dijkstra, patricia, stringsearch) had to be
modied in order to successfully compile with GCC. The collective optimization
approach and framework are compatible with other compilers, but GCC is now be-
coming a competitive optimizing compiler with a large number of program transfor-
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
4
mation techniques and support for more than 30 dierent families of architectures.
We currently use the standard gprof tool to prole programs at function level.
This tool may introduce some overhead which we briey analyze in Section 5 and
suggest possible solutions to reduce it. We use the Interactive Compilation Interface
(ICI) [Link-ICI ; Fursin et al. 2008; Huang et al. 2010] to perform function cloning,
select combinations of optimizations per function and instrument programs. ICI is a
plugin system that acts as a middleware interface between production compilers
such as GCC and user-denable research plugins. The ICI framework provides
a high-level compiler-independent and a low-level compiler-dependent API that
open up and reuse the available functionality of production compilers in order to
transform them into stable, portable, and modular compiler research infrastructure
and enable interactive control of all internal decisions.
Optimizations. We selected 88 program transformations such as inlining, un-
rolling, scheduling, register allocation, constant propagation among many others
and which are known to inuence performance, and 8 parameters for each para-
metric optimization. One should bear in mind that GCC has not been originally
designed for research so it is not possible to explore the whole optimization space
by simply combining multiple compiler optimization ags, since some of them
are initiated only with a given global GCC optimization level (-Os,-O1,-O2,-O3).
We overcome this issue by selecting a global optimization level -O1 .. -O3 rst
and then either turning on a particular optimization through a corresponding ag
-f<optimization name> or turning it o using -fno-<optimization name> ag.
For our study, we selected 200 combinations of optimizations using a random
search strategy with 50% probability to select each ag and either turn it on or
o. We use this strategy to allow uniform unbiased exploration of unknown op-
timization search spaces. In order to validate the resulting diversity of program
transformations, we have checked that no two combinations of optimizations gen-
erated the same binary for any of the benchmarks using the MD5 checksum of
the assembler code obtained through objdump -d command. Occasionally, random
selection of ags in GCC may result in an invalid code. In order to avoid such
situations, we validated all generated combinations of optimizations by comparing
the outputs of all benchmarks used in our study with the recorded outputs during
reference runs when compiled with -O3 global optimization level.
Platforms. The programs were compiled and run on three distinct architectures:
AMD Athlon XP 2800+ (AMD32) - 5 machines, AMD Athon 64 3700+ (AMD64)
- 16 machines, and Intel Xeon 2.80GHz (IA32) - 2 machines.
Collective Optimization Database. We gradually make all our experimen-
tal data publicly available through the online collective optimization database at
[Link] repository [Link-repository ] to help end-users improve their computing
systems and help researchers reproduce the experimental results.
3. MOTIVATION
The performance upper bound of iterative optimization. Because the ex-
perimental methodology of research in iterative optimization consists of running
many times the same program on the same dataset and on the same platform, it
can be interpreted as an idealized case of collective optimization, where the experi-
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
5
S
p
e
e
d
u
p
0.0
0.5
1.0
1.5
2.0
s
u
s
a
n
_
e
s
u
s
a
n
_
c
s
u
s
a
n
_
s
t
if
f
m
e
d
ia
n
is
p
e
ll
r
ijn
d
a
e
l_
d
b
it
c
o
u
n
t
p
a
t
r
ic
ia
r
ijn
d
a
e
l_
e
p
g
p
_
e
C
R
C
3
2
jp
e
g
_
c
d
ijk
s
t
r
a
jp
e
g
_
d
q
s
o
r
t
a
d
p
c
m
_
c
t
if
f
d
it
h
e
r
t
if
f
2
b
w
g
h
o
s
t
s
c
r
ip
t
b
lo
w
f
is
h
_
e
b
lo
w
f
is
h
_
d
p
g
p
_
d
s
t
r
in
g
s
e
a
r
c
h
la
m
e
t
if
f
2
r
g
b
a
m
a
d
a
d
p
c
m
_
d
g
s
m
(a)

1.71
1
1.1
1.2
1.3
1.4
1.5
S
p
e
e
d
u
p
(b)
Fig. 1. (a) Distribution of speedups for all benchmarks and datasets. (b) Performance upper
bound of collective optimization averaged across datasets (AMD Athlon 64 3700+; GCC 4.2.0;
88 program transformations applied globally; 200 iterations with random search strategy; 50%
probability to select each transformation; speedups computed over the highest GCC optimization
level -O3).
ence of others (program, dataset, platform) would always perfectly match the target
run, in other words, a case where no experimental noise would be introduced by dif-
ferences in datasets, programs, or platforms. Consequently, iterative optimization
can be considered as a performance upper bound of collective optimization.
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
6
-O1 -falign-loops=10 -fpeephole2 -fschedule-insns -fschedule-insns2 -fno-tree-ccp -fno-tree-
dominator-opts -funroll-loops
-O1 -fpeephole2 -fno-rename-registers -ftracer -fno-tree-dominator-opts -fno-tree-loop-
optimize -funroll-all-loops
-O2 -nline-functions -fno-tree-dce -fno-tree-loop-im -funroll-all-loops
-O2 -fno-guess-branch-probability -fprefetch-loop-arrays -nline-functions -fno-tree-ter
-O2 -fno-tree-lrs
-O2 -fpeephole -fno-peephole2 -fno-regmove -fno-unswitch-loops
-O3 -nline-limit=1481 -falign-functions=64 -fno-crossjumping -fno-ivopts -fno-tree-
dominator-opts -funroll-loops
-O3 -nline-limit=64
-O3 -fno-tree-dominator-opts -funroll-loops
-O3 -frename-registers
-O3 -fsched-stalled-insns=19 -fschedule-insns -funroll-all-loops
-O3 -fschedule-insns -fno-tree-loop-optimize -fno-tree-lrs -fno-tree-ter -funroll-loops
-O3 -funroll-all-loops
-O3 -funroll-loops
Table I. Some of the Best combinations of GCC ags for MiBench across all datasets on
AMD64 (these are pruned combinations of optimizations where ags that do not inuence per-
formance have been removed)
The violin graphs in Figure 1(a) show the distribution of the speedups for all
benchmarks and datasets for AMD64 when applying 200 random combinations of
optimizations over the highest GCC optimization level (-O3). Figure 1(b) shows the
best speedup achieved for each benchmark averaged over 20 distinct datasets. The
combinations of optimizations corresponding to the best speedups across all pro-
grams and datasets are presented in Table I or can be found online at [Link]
repository [Link-repository ].
1
The diversity of compiler optimizations involved
demonstrates that the compiler optimization space is not trivial; the compiler best
optimization heuristic (-O3) is far from optimal and half of the benchmarks can
achieve more than 20%speedup after iterative compilation. Interestingly, some indi-
vidual transformations have to be turned o in order to achieve higher speedup that
can also help to reduce compilation time. The benchmarks that have sharp peaks of
speedup density usually require the longest time to obtain the best speedup. Over-
all, these experiments implicitly show that collective optimization has the potential
to yield high speedups if it is possible to learn from the experience of others.
It seems possible but not straightforward to learn from the experience
of others. Let us illustrate and quantify the diculty of learning from the expe-
rience of others by using a simple strategy, comparable to what users would do:
selecting the best optimization for a given context (dataset, program, architecture)
and applying it to another context. Next, we consider learning across datasets,
programs, and architectures.
We consider learning across datasets rst. In Figure 2, for each program, we
select the dataset (among 20) which exhibits the best speedup, and apply the corre-
sponding combination of optimizations to all other datasets. We then report the %
dierence between this performance and the best performance obtained for each
1
The ags that do not inuence performance have been iteratively removed from the original
combination of random optimizations to simplify the analysis of the results.
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
7
19
10
20
30
40
1
3
5
7
9
11
13
15
17
19
0
Fig. 2. Learning across datasets.
dataset. While programs like susan e can almost perfectly learn across datasets,
for other programs like dijkstra,patricia,adpcm c, the best optimizations for a
given dataset can yield much lower than optimal performance for other datasets.
This observation further conrms other similar experiments using the commercial
compiler PathScale [Fursin et al. 2007].
We performed similar experiments for programs. We selected the combination of
optimizations which yields the best performance averaged over the 20 datasets of
each program; see reference in Figure 3 (these combinations are listed in Table I).
Then, we apply all the best combinations to all other programs (see applied
to) and report the performance dierence (again averaged over the 20 datasets). A
program like susan c, which is fairly stable across data sets seems to behave poorly
using the best combinations of other programs. Conversely, the best combination
for patricia, a program which does not easily learn across datasets, provides a
good trade-o for many programs.
Finally, we performed similar experiments again for the three aforementioned
architectures (AMD64, AMD32, and IA32). Performance is again averaged over all
datasets, and we rst select the best combination of optimizations for a given pro-
gram on one of the architectures: AMD64. Then, we apply this combination to the
other two architectures, and report the performance dierence in Figure 4. Not sur-
prisingly, AMD32 exhibits the closest performance behavior to AMD64, while the
discrepancy between IA32 and AMD64 performance is likely due to their architec-
tural dierences. Again, these simple observations suggest that experience gathered
on an architecture is potentially useful but cannot always straightforwardly apply
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
8
Reference
A
p
p
l
i
e
d

t
o
bitcount
qsort
susan_c
susan_e
susan_s
jpeg_c
jpeg_d
tiff2bw
tiff2rgba
tiffdither
tiffmedian
dijkstra
patricia
ghostscript
ispell
stringsearch
blowfish_d
blowfish_e
pgp_d
pgp_e
rijndael_d
rijndael_e
CRC32
adpcm_c
adpcm_d
b
i
t
c
o
u
n
t
q
s
o
r
t
s
u
s
a
n
_
c
s
u
s
a
n
_
e
s
u
s
a
n
_
s
j
p
e
g
_
c
j
p
e
g
_
d
t
i
f
f
2
b
w
t
i
f
f
2
r
g
b
a
t
i
f
f
d
i
t
h
e
r
t
i
f
f
m
e
d
i
a
n
d
i
j
k
s
t
r
a
p
a
t
r
i
c
i
a
g
h
o
s
t
s
c
r
i
p
t
i
s
p
e
l
l
s
t
r
i
n
g
s
e
a
r
c
h
b
l
o
w
f
i
s
h
_
d
b
l
o
w
f
i
s
h
_
e
p
g
p
_
d
p
g
p
_
e
r
i
j
n
d
a
e
l
_
d
r
i
j
n
d
a
e
l
_
e
C
R
C
3
2
a
d
p
c
m
_
c
a
d
p
c
m
_
d
% difference with best performance
0% 60%
Fig. 3. Learning across programs.
to another architecture, even if the compiler platform is identical, as is the case
here.
4. COLLECTIVE OPTIMIZATION OVERVIEW
This section provides an overview of the proposed approach for collective optimiza-
tion. The general principle is that performance data about each run is transparently
collected and sent to a collective optimization database; and, after each run, based
on all the knowledge gathered so far, a new combination of optimizations is selected
and the program is recompiled accordingly. The key issue is which combination of
optimizations to select for each new run, in order to both gather new knowledge
and keep improving average program performance as we learn.
In collective optimization, several global and program-specic probability distri-
butions capture the accumulated knowledge. Combinations are randomly selected
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
9
0
5
10
15
20
25
30
35
40
45
b
i
t
c
o
u
n
t
q
s
o
r
t
s
u
s
a
n
_
c
s
u
s
a
n
_
e
s
u
s
a
n
_
s
j
p
e
g
_
c
j
p
e
g
_
d
t
i
f
f
2
b
w
t
i
f
f
2
r
g
b
a
t
i
f
f
d
i
t
h
e
r
t
i
f
f
m
e
d
i
a
n
d
i
j
k
s
t
r
a
p
a
t
r
i
c
i
a
g
h
o
s
t
s
c
r
i
p
t
i
s
p
e
l
l
s
t
r
i
n
g
s
e
a
r
c
h
b
l
o
w
f
i
s
h
_
d
b
l
o
w
f
i
s
h
_
e
p
g
p
_
d
p
g
p
_
e
r
i
j
n
d
a
e
l
_
d
r
i
j
n
d
a
e
l
_
e
C
R
C
3
2
a
d
p
c
m
_
c
a
d
p
c
m
_
d
%

D
i
f
f
e
r
e
n
c
e

w
i
t
h

b
e
s
t

p
e
r
f
o
r
m
a
n
c
e

AMD32
IA32

Fig. 4. Attempting to learn across architectures: % dierence of the best speedup achieved for
a given program on AMD32 and IA32 (averaged across all datasets) with the speedup obtained
when applying best found combination of optimizations for a program on AMD64.
from one of several probability distributions which are progressively built at the
remote server.
The dierent maturation stages of a program. For each program, and
depending on the amount of accumulated knowledge, we distinguish three scenarios:
(1) the server may not know the program at all (new program), (2) only have
information about a few runs (infrequently used or a recently developed program),
or (3) have information about many runs.
Stage 3: Program well known, heavily used. At this maturation stage, enough
runs have been collected for that program that it does not need the experience of
other programs to select the most appropriate combinations of optimizations for
itself. This knowledge takes the form of a program-specic probability distribution
called d
3
. Stage 3 corresponds to learning across datasets.
Stage 2: Program known, a few runs only. At this maturation stage, there is still
insucient information (program runs) to correctly predict the best combinations
by itself, but there is already enough information to start characterizing the
program behavior. This characterization is based on the comparison of the impact
of combinations of optimizations tried so far on the program against their impact
on other programs (program reaction to optimizations). If two programs behave
alike for a subset of combinations, they may well behave alike for all combinations.
Based on this intuition, it is possible to nd the best matching program, after
applying a few combinations to the target program. Then, the target program
probability distribution d
2
is given by the distribution d
3
of the matching program.
This matching can be revisited with each additional information (run) collected for
the target program. Stage 2 corresponds to learning across programs.
Stage 1: Program unknown. At this stage, almost no run has been performed,
so we leverage and apply optimizations suggested by the general experience col-
lected over all well-known programs. The resulting d
1
probability distribution is the
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
10
unweighted average of all d
3
distributions of programs which have reached Stage 3.
Stage 1 is an elementary form of learning across programs and allows us to auto-
mate and simplify the tuning of the default compiler optimization heuristic using
realistic programs, datasets and collective knowledge from multiple users instead
of ad hoc, repetitive training with some dedicated and not always representative
benchmarks.
Selecting stages. A program does not follow a monotonic process from Stage
1 to Stage 3, even though it should intuitively mature from Stage 1 to Stage 2
and then to Stage 3 in most cases. There is a permanent competition between the
dierent stages distributions (d
1
, d
2
, d
3
). At any time, a program may elect to draw
combinations of optimizations from any stage distribution, depending on which one
appears to perform best so far. In practice and on average, we nd that Stage 3
(learning across datasets) is by far the most useful stage. Stage 1 and Stage 2 are
respectively useful in the rst ten, and the rst hundreds of runs of a program on
average, but Stage 3 rapidly becomes dominant. The competition between stages
is implemented through a meta distribution d
m
, which reects the current score
of each stage distribution for a given program. Each new run is a two-step random
process: rst, the server randomly selects the distribution to be used, and then, it
randomly selects the combination using that distribution. How scores are computed
is explained in Section 6. Using that meta-distribution, the distribution with the
best score is favored.
5. COLLECTIVE OPTIMIZATION FRAMEWORK
In Figure 5, we show the collective optimization framework and two key compo-
nents to enable continuous aggregation and reuse of optimization knowledge: col-
lective compiler and collective optimization database (repository hosted at cTun-
[Link] [Link-repository ]).
Collective compiler. Our collective compiler is based on GCC with the Inter-
active Compilation Interface (ICI) [Link-ICI ; Fursin et al. 2008; Huang et al. 2010].
ICI abstracts the optimization process from a particular production compiler and
helps us reuse the same collective optimization framework with other compilers.
The extended compiler functionality and ICI collective optimization plugins allow
to clone functions, instrument programs to select original functions or clones at
runtime, control internal decisions, apply optimizations on a function level, and
intercept main and exit routines to collect proling statistics and send it to the
optimization repository or obtain a new combination of optimizations to improve
a program based on collective knowledge.
Usage scenarios. The collective optimization framework is compatible with the
original unmodied GCC and invokes collective optimization plugins only when a
user decides to participate in the collective learning by setting an environment
variable CTUNING to nonzero value. Currently, the collective compiler supports
two optimization scenarios: training mode with a reference run and production
mode with transparent runtime evaluation of optimizations using function cloning.
In both cases, the compiler adds gprof proling routines to a compiled program,
produces clones of all or only the most time consuming functions (if this statistic is
available after several executions) and applies some combinations of optimizations
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
11

Save profile statistics
and query server for
better optimization
User
X

Program
A
Architecture
B

Collective Compiler
Binary
Dataset
1


Dataset
N

Internet/Intranet
Web Server
Collective Optimization
Web Services
- Register events
- Query database
- Get statistics

Collective Optimization
Database
- COMPILATION table
- EXECUTION table
- AUXILARY tables
- Pool of validated
random optimizations



MySQL
Execution
User
Y

Program
C
Architecture
D

- Profiling Routines
- Collective Stats
- Unique IDs

Intercept exit() and call
Collective Stats Handler
Collective Optimization Server
([Link]
Initiate recompilation if better optimization setting
is suggested based on Collective Knowledge
Prolog of the time consuming code
Start profiling and
Randomly select version
(original or clone)

Original code
(Optimizations
1
)

Cloned code
(Optimizations
2
)

Stop profiling
Function clones
with different
optimizations
GCC with Interactive
Compilation Interface:
- create code clones
- instrument program
- apply optimizations per
clone
- intercept main()and
add auxiliary routines
Epilog of the time consuming code
Select validated combination of
optimizations
Fig. 5. Collective iptimization framework.
to both original and cloned functions through ICI.
During training mode invoked by setting CTUNING variable to 1, a program is
executed at least twice with the same dataset (similar to traditional iterative com-
pilation approaches [Fursin et al. 2008]) to be able to correctly evaluate the eect
of optimizations on the execution time. It is used for automatic oine search for
protable combinations of optimizations for a given architecture using standard
benchmarks, programs, and datasets. This approach can be used along with col-
lective optimization to speed up learning. Moreover, since the compiler sometimes
generates an invalid random combination of optimizations, our training mode can
reduce such risks and help to validate the correctness of a given combination by
comparing the original and new outputs of a program on a number of datasets.
A similar validation technique is commonly used in current compilers including
GCC. On the collective optimization server, we gradually build a pool of validated
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
12
optimizations favoring the best performing ones as shown in Table I, for example.
During production mode, invoked by setting CTUNING variable to 2, a pro-
gram is compiled with random combinations of optimizations validated during the
training mode and applied to both original and cloned functions. During con-
tinuous production runs of this program at data centers, PCs, mobiles, or other
computing systems, random combinations of optimizations are statistically evalu-
ated at runtime as described in Section 6. Furthermore, this and other proling
statistics are sent to the collective optimization server to both help other users im-
prove their systems and return better optimization suggestions based on collective
knowledge. A user can turn o this mode at any time by unregistering the envi-
ronment variable CTUNING when reasonable performance improvement is achieved
or when executing condential programs. In this case, a user can either recom-
pile the original program with the best found combination of optimizations while
removing clones and proling routines, or use the latest modied binary that will
automatically invoke clones with the best optimizations and skip proling and com-
munication with the collective optimization server. In the latter scenario, the user
may later easily resume the collective learning process.
S
l
o
w
d
o
w
n
1.0
1.2
1.4
1.6
1.8
2.0
2.2
b
it
c
o
u
n
t
is
p
e
ll
q
s
o
r
t
b
lo
w
f
is
h
_
d
b
lo
w
f
is
h
_
e
m
a
d
r
ijn
d
a
e
l_
e
p
a
t
r
ic
ia
r
ijn
d
a
e
l_
d
g
h
o
s
t
s
c
r
ip
t
t
if
f
d
it
h
e
r
jp
e
g
_
c
jp
e
g
_
d
a
d
p
c
m
_
c
d
ijk
s
t
r
a
p
g
p
_
e
t
if
f
2
b
w
p
g
p
_
d
s
t
r
in
g
s
e
a
r
c
h
t
if
f
2
r
g
b
a
t
if
f
m
e
d
ia
n
s
u
s
a
n
_
s
a
d
p
c
m
_
d
s
u
s
a
n
_
e
s
u
s
a
n
_
c
C
R
C
3
2
g
s
m
la
m
e
Fig. 6. Distribution of slowdown for all benchmarks and datasets due to gprof function-level
proling overheads (AMD64).
Proling. We decided to use standard gprof proling routines for execution
time per function and number of calls. Though this tool introduces some overhead
as shown in Figure 6, for half of the used benchmarks it is negligible and it is
used only for the proof of the concept and to simplify the implementation. In the
future, we plan to minimize this overhead by using our own optimized routines to
obtain cycle-accurate proling through performance counters or using tools such as
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
13
oprofile with nonintrusive proling through sampling [Link-OProle ]. Also, as
mentioned earlier, a user can turn o collective optimization mode with proling
at any time and leave the best found combination of optimizations.
During proling, we select the most time-consuming program routines (in this
work we select up to 3 functions that cover 75% or more of the execution time in our
benchmarks). The denition of the top routines can change across runs. Therefore,
we progressively build an average ranking of the program routines, possibly learning
new routines as they are exercised by dierent datasets.

METHODDEF(boolean)
decode_mcu (j_decompress_ptr cinfo, JBLOCKROW
*MCU_data) {

(Original function)
METHODDEF(boolean)
decode_mcu (j_decompress_ptr cinfo, JBLOCKROW
*MCU_data) {
if ((rand() % 2) == 0)
return decode_mcu1 (cinfo, MCU_data);
else
return decode_mcu2 (cinfo, MCU_data);
}
(Modified function to select clones randomly at
run-time)
METHODDEF(boolean)
decode_mcu1 (j_decompress_ptr cinfo, JBLOCKROW
*MCU_data) {


METHODDEF(boolean)
decode_mcu2 (j_decompress_ptr cinfo, JBLOCKROW
*MCU_data) {


(Two clones to compare combinations of
optimizations C1 and C2)
Fig. 7. Function cloning to evaluate combinations of optimizations transparently or to enable
dynamic adaptation for statically compiled programs.
Cloning. We modied GCC to implement function cloning. That required
changes in the core of the compiler since we had to implement full replication of
parts of a program AST. This functionality is controlled by the interactive com-
pilation interface. When collective optimization plugins trigger GCC to clone a
function, it inserts proling calls at the prolog and epilog of the function, replaces
static variables, and inserts additional instructions to randomly select either the
original or the cloned version as shown in Figure 7 for function decode mcu of
jpeg d. This enables continuous transparent evaluation of combinations of op-
timizations at runtime for statically compiled programs as described in detail in
Section 6.
Transparently collecting runtime information and reoptimizing. In or-
der to unobtrusively collect information on a program run, and reoptimize the
program, we modied GCC to intercept the compilation of the main() function,
and insert another interceptor on the exit() function to call a termination rou-
tine. Whenever the program execution nishes, this routine is invoked and it in
turn checks whether the Collective Stats Handler exists, invokes it to send compi-
lation and execution information to the collective optimization server and database
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
14
[Fursin 2009].

COMPILE_ID 17053973767718039
PLATFORM_ID 2111574609159278179
ENVIRONMENT_ID 2781195477254972989
COMPILER_ID 7548127843267843
PROGRAM_ID 37097459005644868
DATE 2007-07-09
TIME 18:32:43
OPT_FLAGS decode_mcu1={-O3 }
decode_mcu2={-O3 -fno-inline-functions
-fno-tree-ccp -fmove-loop-invariants}
COMPILE_TIME 3.4
BIN_SIZE 356655
OBJ_MD5CRC a420280c164310a47e2d8655028d1a66
(compilation stage)
RUN_ID 5572268172923323
COMPILE_ID 17053973767718039
PLATFORM_ID 2111574609159278179
ENVIRONMENT_ID 2781195477254972989
PROGRAM_ID 37097459005644868
DATE 2007-07-09
TIME 18:32:52
OUTPUT_CORRECT 1
RUN_TIME 10.32
RUN_TIME_USER 8.94
RUN_PROFILE {decode_mcu1=3.16, calls=139223}
{decode_mcu2=3.21, calls=142948}
(execution stage)
Fig. 8. Example of information packets sent to the Collective Optimization Server/Database
(hosted at [Link]) for the program jpeg d.
Figure 8 shows compilation and execution information packets sent to the database
for the program jpeg d. Each computer system is assigned several unique identi-
ers (generated by the UUID tool unless such system already exists in the collective
optimization database) describing architecture, environment, and compiler utilized.
Compilation and execution information packets as well as a program are also as-
signed unique IDs to allow easy distributed sharing and referencing of optimization
cases between multiple users. One should note that the OUTPUT CORRECT eld is used
only during the training mode when a program can be executed with the same
dataset more than once and program outputs can be compared to minimize the risk
of invalid combinations of optimizations as described earlier. Only validated com-
binations of optimizations can be later used for transparent optimizations without
a reference run.
When starting the optimization process, a user can either provide a program ID if
such a program has already been registered in the collective optimization database,
or use a tool we provide to dene the program ID as the MD5 checksum of compiled
source les. Eventually, after a few runs, we characterize programs using a portable
method based on dynamic features, as described in details in Section 6.2.
The termination routine queries a Web service on the collective optimization
server in order to obtain potentially better combination of optimizations for future
runs. If such combinations exist, a recompilation takes place periodically (period
set by the user) in the background, between several runs.
2
At any time, the user
can opt in or out of collective optimization by setting or resetting an environment
variable CTUNING.
Security. The concept of collective optimization raises new issues, especially
security. Therefore, we never send any source code to the collective optimization
2
Note that if the recompilation is not completed before another run starts, this latter run just
uses the same optimizations as the previous run, and the evaluation of the new optimizations is
just slightly delayed by one or a few runs.
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
15
server (only MD5 or dynamic features vectors). If a user would like to submit
optimization data from some privacy-critical applications to the common reposi-
tory, we provide an option to obfuscate program and function names. Furthermore,
the collective optimization server supports both public and private databases (for
companies). Note that companies can then get the best of both worlds: lever-
age/read information accessible from the common database, while recording infor-
mation about their runs solely to their private database.
6. COLLECTIVE LEARNING
In this section, we explain in more detail how to compute the aforementioned
distributions to achieve collective learning.
6.1 Building the Program Distribution d
3
Using Statistical Comparison of Combina-
tions of Optimizations
Comparing two combinations C
1
, C
2
. In order to build the aforementioned dis-
tributions, one must be able to compare the impact of any two combinations of
optimizations C
1
, C
2
on program performance. However, even the simple task of de-
ciding whether C
1
> C
2
can become complex in a real context. Since the collective
optimization process only relies on production runs, two runs usually correspond
to two distinct datasets. Therefore, if two runs with respective execution times T
1
and T
2
, and where combinations of optimizations C
1
and C
2
have been respectively
applied, are such that T
1
< T
2
, it is not possible to deduce that C
1
> C
2
.
To circumvent that issue, we perform runtime comparison of two combinations
of optimizations using cloned functions. C
1
and C
2
are respectively applied to the
clones f
1
and f
2
of a function f. At runtime, for each call to f, either f
1
or f
2
is
called; the clone called is randomly selected using an additional branch instruction
and a simple low-overhead pseudorandom number generation technique emulating
uniform distribution. We have shown in [Fursin et al. 2005] the possibility to
evaluate optimizations for statically compiled programs with stable behavior using
function cloning and runtime low-overhead phase detection. [Stephenson 2006]
and [Lau et al. 2006] demonstrated how to evaluate dierent optimizations for
programs with irregular behavior in dynamic environments using random function
invocations and averaging collected time samples across a period of time. We
combined these techniques to enable transparent runtime performance evaluation
for statically compiled programs with any behavior here. Even if the workload of
the routine varies upon each call, we observed that in many cases, if the routine
is executed a large number of times (> 100), the average workload performed by
each randomly selected clone can be similar during one execution. As a result,
the nonoptimized versions of f
1
and f
2
account for about the same fraction of the
overall execution time of f. Therefore, if the average execution time of the clone
optimized with C
1
is smaller than the average execution time of the clone optimized
with C
2
, it is often correct to deduce that C
1
is better than C
2
, that is, C
1
> C
2
.
This statistical comparison of combinations of optimizations requires no reference,
test or training run, and the overhead is negligible.
Naturally, it is not always possible to use the preceding technique to evaluate two
combinations of optimizations if there are only a few invocations of the function
during the whole program execution, if the workload varies considerably across
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
16
invocations, or there is too much noise during proling. Therefore, we continuously
monitor the speedups across runs until the speedup converges to some constant
value. Otherwise, a user has to resort to other evaluation methods, such as an
additional reference run with the same dataset, as for the training mode.
0.6 0.8 1.0 1.2 1.4 1.6 1.8
speedup
d
e
n
s
i
t
y
0.6 0.8 1.0 1.2 1.4 1.6 1.8 0.6 0.8 1.0 1.2 1.4 1.6 1.8 0.6 0.8 1.0 1.2 1.4 1.6 1.8
average
O3 vs O3, after 10 runs
O3 vs O3, after 100 runs
O3 vs best, after 10 runs
O3 vs best, after 100 runs
Fig. 9. Speedup convergence during runtime comparison of combinations of optimizations across
multiple runs of jpeg d with random datasets on IA32.
For example, Figure 9 demonstrates how the speedups for the hot function
decode mcu of jpeg d evolve during runtime comparison of optimizations across
multiple program executions with random datasets on IA32 using two scenarios. In
the rst scenario, decode mcu is compiled with the baseline optimization level (-O3)
while its clone is compiled with the top performing combination of optimizations.
In the second scenario, both original function and its clone are compiled with -O3.
The solid and dashed line show the evolution of the density of speedups after 10 and
100 program runs for the rst and second scenario, respectively. This experiment
demonstrates that in both scenarios the average speedup gradually converges to
some constant value and in the second scenario the average speedup converges to
1.0 thus conrming the possibility to use our runtime approach to compare opti-
mizations for this program and function.
Computing d
3
. When two combinations C
1
and C
2
are compared on a program
using the aforementioned cloned routines, the only information recorded is whether
C
1
> C
2
or C
1
< C
2
. Implicitly, a run is a competition between two combinations of
optimizations, and the winning combination scores 1, the other 0, as shown in Fig-
ure 10. These scores are cumulated for each combination and program. The scores
are then normalized per combination, by the number of times the combination was
tried (thus implicitly decreasing the average score of the losing combination). Then
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
17
the overall distribution is normalized so that the sum of all combinations scores
(probabilities) is 1. Note that we also experimented with scoring using
TimeC
1
TimeC
2
1
instead of 0/1 depending on C
1
> C
2
, which should provide a potentially richer,
program, dataset, and platform-dependent information, but found no signicant
performance benet. As a result, we decided to use more the independent, and
thus potentially more robust information.
1 2 3 4 5
Combinations of optimizations
After 1 iteration
(1 < 2)
0
0.2
After N
iterations
1 2 3 4 5 1 2 3 4 5
Fig. 10. Computing the probability distribution used for selecting a combination of optimizations.
Because this distribution only reects the relative merit of each combination,
and not the absolute performance (e.g., execution time or speedup), it is a fairly
resilient metric, tolerant to variations in measurements.
6.2 Building the Matching Distribution d
2
Stage 2 is based on the intuition that it is unlikely that all programs exhibit widely
dierent behavior with respect to compiler optimizations, or conversely that, once
the database is populated with a sucient number of programs, it is likely that a
new program may favor some of the same combinations of optimizations as some of
the programs already in the database. The main diculty is then to identify which
programs best correspond to the current target one. Therefore, we must somehow
characterize programs, and this characterization should reect which combinations
of optimizations a program favors.
As for d
3
, we use the metric-independent comparison between two combinations
of optimizations C
1
and C
2
. For example, C
1
> C
2
is a reaction to program opti-
mizations and is used as one characterization of the program. Let us assume that
C
1
> C
2
for the target program P and C
1
> C
2
for a program P

and C
1
< C
2
for
a program P

compared against P. Then, P

gets a score of 1, and P

a score of
0. The program with the best score is considered the matching program, and d
2
is
set to the d
3
of that program. In other words, for d
2
we use a competition among
it programs. The more pairs (reactions to optimizations) are compared, the more
accurate and reliable the program matching.
Still, we observed that beyond 100 characterizing pairs of combinations of opti-
mizations (out of C
2
100
=
200
199
/2 = 19900 possible pairs of combinations), perfor-
mance barely improves. In addition, it would not be practical to recompute the
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
18
matching upon each run based on an indenitely growing number of characteri-
zations. Therefore, we restrict the characterization to 100 pairs of combinations,
which are collected within a rolling window (FIFO). However, the window only con-
tains distinct pairs of combinations of optimizations. The rolling property ensures
that the characterization is permanently revisited and rapidly adapted if neces-
sary. The matching is attempted as soon as one characterization is available in
the window, and continuously revisited with each new modication of the rolling
window.
[Cavazos et al. 2006] have shown that it is possible to improve similar program
characterizations by identifying and then restricting to optimizations which carry
the most information using the mutual information criterion. However, these op-
timizations do not necessarily perform best; they are the most discriminatory and
one may not aord to test them in production runs. Moreover, we will later see
that this approach could only yield marginal improvement in the start-up phase
due to the rapid convergence of Stage 3/d
3
.
6.3 Building the Aggregate Distribution d
1
d
1
is simply the average of all d
3
distributions of each program. d
1
reects the
most common cases: which combinations of optimizations perform best in general.
For example, it can be already used to systematically and continuously improve
default optimization level of a given compiler on a given architecture by distributing
the tuning process among many users and taking into account real applications
and datasets thus avoiding specialized and often limited benchmarks. So even
users not relying on collective optimization could benet in a simple way from the
collective knowledge gathered by others. Furthermore, it is also possible to compose
more restricted aggregate distributions, such as per architecture, per compiler, per
programs, or dataset subsets. We leave this for the future work.
6.4 Scoring Distributions
As mentioned in Section 4, a meta-distribution is used to select which stage distri-
bution is used to generate the next combination of optimizations. For each run, two
distributions d and d

are selected using two draws from the meta-distribution (they

can be the same distributions). Then, a combination of optimizations is drawn from
each distribution (C
1
using d and C
2
using d

), which will compete during the run.

Scoring is performed upon the run completion; note that if C
1
and C
2
are the same
combinations, no scoring takes place.
Let us assume, for instance, that for the run, C
1
> C
2
. If, according to d,
C
1
> C
2
also, then one can consider that d predicted the result right, and gets
a score of 1. Conversely, it would get a score of 0. The server also keeps track of
the number of times each distribution is drawn, and the distribution value in the
meta-distribution is the ratio of the sum of all its scores so far and the number of
times it was drawn. Implicitly, its score decreases when it gets a 0, increases when
it gets a 1, as for individual distributions.
This scoring mechanism is robust. If a distribution has a high score, but starts to
behave poorly because the typical behavior of the program has changed (e.g., a very
dierent kind of datasets is used), then its score will plummet, and the relative score
of other distributions will comparatively increase, allowing to discover new strong
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
19
combinations. Note that d
3
is updated upon every run (with distinct combinations),
even if it was not drawn, ensuring that it converges as fast as possible.
7. PERFORMANCE EVALUATION
0.96
1
1.05
1.1
1.15
S
p
e
e
d
u
p
Collective
d1
d2
d3
Best
Baseline
0
0.5
1
1 10 100 1000 10000
M
e
t
a

S
c
o
r
e
s
# Runs
Fig. 11. Average performance of collective optimization and individual distributions averaged
across all programs and datasets for AMD64 (bottom: metascores of individual distributions;
gray is d
3
, black is d
2
, white is d
1
).
In Figure 11, Collective corresponds to the full process described in earlier sections
across all programs and data sets for AMD64, where the appropriate distribution
is selected using the meta-distribution before every run; performance is averaged
over all programs (for instance, Run=1 corresponds to performance averaged over 1
random run for each program). For each program, we have collected 20 datasets and
can apply 200 dierent combinations of optimizations, for a total of 4000 distinct
runs per program. The main approximation of our evaluation lays in the number
of datasets; upon each run, we (uniformly) randomly select one among 20 datasets.
While 20 datasets is higher than in most other studies to the best of our knowledge,
it is still much fewer than the number of runs in our experiments. However, several
studies have shown that datasets are often clustered within a few groups breeding
similar behavior [Eeckhout et al. 2003], so that 20 datasets exhibiting suciently
distinct behavior, as suggested by the experiments of Section 3, may be considered
a nonperfect but reasonable emulation of varying program behavior across datasets.
In order to further assess the impact of using a restricted number of datasets, we
have evaluated the extreme case where a single dataset is used. These results
are reported in Figure 14 (see Single dataset), where a single dataset is used per
program in each experiment, and then, for each x-axis value (number of runs),
performance is averaged over all programs and all datasets. Using a single dataset
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
20
improves convergence speed though only moderately, suggesting Collective could be
a slightly optimistic but reasonable approximation of a real case where all datasets
are distinct.
After 10000 runs per program, the average Collective speedup, 1.11, is fairly
close to the Best possible speedup, 1.13, the asymptotic behavior of single-dataset
experiments, see (Section 3). The other graphs (d1, d2, d3) report the evolution
of the average performance of combinations of optimizations drawn from each dis-
tribution. At the bottom of the gure, the gray lled curve corresponds to the
metascore of d
3
, the black one to d
2
, and the white one to d
1
.
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
1.1
1.2
12.5 percent
S
p
e
e
d
u
p
Optimization Rank
0.95
C
u
m
u
l
a
t
e
d

P
r
o
b
a
b
i
l
i
t
y
Speedup
Distribution
Fig. 12. Average speedups and d
3
distributions prole (across all programs and datasets for
AMD64).
Convergence versus performance. d
3
converges fairly rapidly as it starts getting
signicant performance improvements after about 10 runs. The shape of distribu-
tions for combinations explains this rapid convergence. Figure 12 shows the aver-
age prole of cumulated program distributions d
3
, as well as the average program
speedup prole; such proles are computed for each program, with optimizations
ranked on the x-axis according to the distribution, and then these proles are av-
eraged over all programs. On average, 12.5% of combinations bring a speedup
greater than 1, that is, 1 in 8; so, on average, drawing 8 combinations should yield
one combination improving performance. This is why after 10 runs, d
3
distribu-
tions have usually identied one good candidate combination; performance keeps
improving because new, better candidates are later discovered. In other words,
there are relatively many good combinations.
Still, the majority ( 87.5%) of combinations are poor, degrading performance.
And even a distribution skewed toward good combinations, like d
3
, will draw poor
combinations more often than a user might tolerate. In order to lter these poor
combinations out and to achieve consistently good performance, the d
3
distributions
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
21
are not polled over the whole probability interval [0, 1], but only the interval [0.95, 1];
in other words, only the 5% best combinations suggested by d
3
are used. These
combinations yield about 10% performance improvement or more on average, as
shown in Figure 12. This same restricted polling principle is applied to all d
i
distributions, but not to the meta-distribution. Collective optimization performed
with individual distributions polling in interval [0, 1] yield poor performance for
several reasons: individual distributions more frequently draw poor combinations;
as a consequence, their score frequently decreases, and the meta-distribution has
diculties identifying a winning distribution.
The downside of polling in interval [0.95, 1] is that a distribution may be stuck
drawing almost always the same combination(s), thus being not reactive. That is
where the competitions and the meta-distribution come into play. Even if distribu-
tions are strongly skewed toward one or a few combinations, once in a while these
top combinations will be challenged against other combinations (drawn from one
or the other distributions). If it turns out the choices recommended by d
3
have
become poor, after a few such challenges, both the scores of the previously top
combinations and the metascore of d
3
will plummet, allowing new combinations to
emerge.
0.8
0.9
1.0
1.1
1.2
1.3
1.4
1.5
1.6
1.7
a
u
t
o
m
o
t
i
v
e
_
b
i
t
c
o
u
n
t
a
u
t
o
m
o
t
i
v
e
_
s
u
s
a
n
_
c
a
u
t
o
m
o
t
i
v
e
_
s
u
z
a
n
_
e
a
u
t
o
m
o
t
i
v
e
_
s
u
s
a
n
_
s
c
o
n
s
u
m
e
r
_
j
p
e
g
_
c
c
o
n
s
u
m
e
r
_
j
p
e
g
_
d
c
o
n
s
u
m
e
r
_
l
a
m
e
c
o
n
s
u
m
e
r
_
m
a
d
c
o
n
s
u
m
e
r
_
t
i
f
f
2
b
w
c
o
n
s
u
m
e
r
_
t
i
f
f
2
r
g
b
a
c
o
n
s
u
m
e
r
_
t
i
f
f
d
i
t
h
e
r
c
o
n
s
u
m
e
r
_
t
i
f
f
m
e
d
i
a
n
o
f
f
i
c
e
_
g
h
o
s
t
s
c
r
i
p
t
o
f
f
i
c
e
_
i
s
p
e
l
l
o
f
f
i
c
e
_
r
s
y
n
t
h
s
e
c
u
r
i
t
y
_
b
l
o
w
f
i
s
h
_
d
s
e
c
u
r
i
t
y
_
b
l
o
w
f
i
s
h
_
e
s
e
c
u
r
i
t
y
_
p
g
p
_
d
s
e
c
u
r
i
t
y
_
p
g
p
_
e
s
e
c
u
r
i
t
y
_
r
i
j
n
d
a
e
l
_
d
s
e
c
u
r
i
t
y
_
r
i
j
n
d
a
e
l
_
e
s
e
c
u
r
i
t
y
_
s
h
a
t
e
l
e
c
o
m
_
a
d
p
c
m
_
c
t
e
l
e
c
o
m
_
a
d
p
c
m
_
d
t
e
l
e
c
o
m
_
C
R
C
3
2
t
e
l
e
c
o
m
_
g
s
m
A
V
E
R
A
G
E
S
p
e
e
d
u
p
Best
d1
d2 (N=10)
d2 (N=100)
d2 (Best)
d3
Fig. 13. Distribution of performance per program using maximum available knowl-
edge (speedups averaged across all datasets on AMD64).
Learning across programs. While the behavior of d
2
in Figure 11 suggests that
learning across programs yields modest performance improvements, this experiment
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
22
is partly misleading. d
3
rapidly becomes a dominant distribution, and as explained
earlier, quickly converges to one or a few top combinations due to restricted interval
polling. d
2
performance will improve as more characterizing pairs of combinations
of optimizations ll up the rolling window.
This is further outlined in Figure 13 that shows the steady-state performance
for each distribution and program, where only a single distribution is used, that
is, no meta-distribution, and distributions are built using all available data. For
instance, for each program, the d
1
distribution is built using all 104000 collected
runs for programs other than the target program (20 datasets, 200 combinations of
optimizations for 25 out of 26 programs); the reported performance is the average
speedup of 100 runs using 100 draws from that distribution. For the d
3
distribution
of one program, 20 d
3
distributions are in fact built for each of the 20 datasets, us-
ing all programs runs except for that dataset (19 other datasets, 200 combinations
per dataset, for a total of 3800 runs), the performance for one dataset is the average
speedup of 100 runs using 100 draws from these dataset-specic distributions, and
the reported performance is itself averaged over all datasets. For the d
2
distribu-
tions, the N pairs of characteristic combinations of optimizations are drawn using
d
1
(recall d
1
is itself built excluding all runs from the target program), and the
dataset is (uniformly) randomly selected among 20. These N runs are then used to
score all other programs, or more exactly their own d
3
distributions as explained in
Section 6.2, and the program with the best score is considered the matching pro-
gram; d
2
is then equal to the d
3
of that program, and the performance is evaluated
by averaging over 100 runs using 100 draws from that distribution.
Even though the average performance of d
2
is still signicantly lower than that
of d
3
and the variability is high due to occasional poor matching, the performance
is close to d
3
for some codes, such as susan c. These results conrm previous stud-
ies which have shown that learning across programs can yield good performance
[Cavazos et al. 2006; Agakov et al. 2006; Fursin et al. 2008]. More sophisticated
techniques for selecting characterizing combinations of optimizations, as proposed
in [Cavazos et al. 2006] for instance, might improve performance. However, in prac-
tice, this eort is not critical since, even if matching were optimal (see d2 (Best)),
the average d
2
performance would still be lower than d
3
(best matching is ob-
tained by selecting the matching program which yields the highest speedups for the
target program, averaged over 100 random draws from the d
3
candidate matching
program distribution). But more importantly, the comparison of Figure 11 and
Figure 13 highlights that the few runs necessary to characterize the behavior of
a new program, with the intent of later matching it to fellow programs, usually
gathers enough knowledge on the program itself, so that program matching then
becomes useless. In other words, self-learning converges so fast that learning across
programs is in fact not necessary. As a result, even though d
2
performance keeps
increasing to a reasonable level in Figure 11, its metascore keeps decreasing be-
cause, in the meantime, d
3
contains even more relevant knowledge. Note that when
training is purely static and requires no target program training runs [Stephenson
and Amarasinghe 2005], program matching may still be useful at start-up.
Collective versus d
3
. While the better performance of d
3
over Collective, shown
in Figure 11, suggests this distribution should solely be used, one can note that its
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
23
0.98
1
1.02
1.04
1.06
1.08
1.1
1.12
1 10 100 1000 10000
S
p
e
e
d
u
p
# Runs
Collective
Architectures
No d1
No d2
No d1,d2
Single data set
Fig. 14. Several collective optimization variants (learning with d1 removed, d2 removed,
d1 and d2 removed, using only one dataset, learning across multiple architectures including
AMD64,AMD32,IA32).
performance is not necessarily the best in the rst few runs, which is important
for infrequently used codes. Moreover, the average Collective performance across
runs becomes in fact very similar after d
3
has become the dominant distribution,
since mostly d
3
combinations are then drawn. But a more compelling reason for
privileging Collective over d
3
is the greater robustness of collective optimization
thanks to its meta-distribution scheme.
In Figure 14, we have tested collective optimization without either d
1
, d
2
, or
neither one. In the latter case, we use the uniform random distribution to discover
new optimizations, and the meta-distribution arbitrates between d
3
and uniform;
by setting the uniform distribution initial meta-score to a low value with respect
to d
3
, we can both quickly discover good optimizations without degrading average
performance;
3
the uniform distribution is not used when only d
1
or d
2
are removed.
As shown in Figure 14, collective optimization converges more slowly when either
d
1
, d
2
, or both are not used. These distributions help in two ways. d
1
plays its main
role at start-up, by bringing a modest average 2% improvement, and performance
starts lower when it is not used. Conversely, d
2
is not useful at start-up, but provides
a performance boost after about 50 to 100 runs when its window is lled and the
matching is more accurate. When contrasting Figure 13, where the performance of
d
2
is modest even with N = 100 characterizing runs, and Figure 14, one can notice
3
This is important since the average speedup of the uniform distribution alone is 0.7.
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
24
that d
2
does in fact signicantly help improve the performance of Collective after
100 runs, but essentially by helping discover good new optimizations, later adopted
by d
3
, rather than due to the intrinsic average performance of the combinations of
optimizations suggested by d
2
.
Learning across architectures. Besides learning across datasets and programs,
we have also experimented with learning across architectures. We have collected
similar runs on an Athlon 32-bit (AMD32) architecture and an Intel 32-bit (IA32)
architecture (recall all experiments reported before are performed on an Athlon
64-bit architecture), and we have built the d
3
distributions for each program. At
start-up time, on the 64-bit architecture, we now use a d
4
distribution corresponding
to the d
3
distribution for this program but other architectures (and 19 datasets,
excluding the target data set); the importance of d
4
will again be determined by
its meta-score. The rest of the process remains identical. The results are reported
in curve Architectures on Figure 14. Start-up performance does benet from the
experience collected on the other architectures. However, this advantage fades away
after about 2000 runs. We have also experimented with simply initializing d
3
with
the aforementioned d
4
instead of using a separate d
4
distribution. However the
results were poorer because the knowledge acquired from other architectures was
slowing down the rate at which d
3
could learn the behavior of the program on the
new architecture.
8. BACKGROUND AND RELATED WORK
Iterative or adaptive compilation techniques usually attempt to nd the best possi-
ble combinations and settings of optimizations by scanning the space of all possible
optimizations. [Whaley and Dongarra 1998; Cooper et al. 1999; Bodin et al. 1998;
Matteo and Johnson 1998; Cooper et al. 2002; Fursin et al. 2002; Kulkarni et al.
2003; Triantafyllis et al. 2003; Singer and Veloso 2000; Pan and Eigenmann 2004;
2006; Qasem et al. 2006; Bailey et al. 2008; Hoste and Eeckhout 2008] demonstrated
that optimization search techniques can eectively improve performance of stati-
cally compiled programs on rapidly evolving architectures, thereby outperforming
state-of-the-art compilers, albeit at the cost of a large number of exploration runs.
Recently, machine-learning and statistical techniques have been used [Monsifrot
et al. 2002; Stephenson et al. 2003; Stephenson and Amarasinghe 2005; Zhao et al.
2005] to select or tune programtransformations based on programfeatures. [Agakov
et al. 2006], [Cavazos et al. 2007] and [Dubach et al. 2009] use machine-learning to
focus iterative compilation and architectural design space exploration using either
syntactic program features or dynamic hardware counters and multiple program
transformations. In [Fursin et al. 2008] we demonstrated real machine-learning
enabled research compiler based on GCC with ICI and plugins for static feature
extraction and prediction of optimizations. Most of these works still require a large
number of training runs. [Stephenson and Amarasinghe 2005] show more com-
plementarity approach with collective optimization as program matching is solely
based on static features.
Several frameworks have been proposed for continuous program optimization
[Anderson et al. 1997; Voss and Eigenmann 2000; Lu et al. 2004; Lattner and Adve
2004]. Such frameworks tune programs either during execution or o-line, trying
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
25
dierent program transformations. Such recent frameworks like [Lattner and Adve
2004] and [Lu et al. 2004] pioneer lifelong program optimization, but they expose
the concept rather than research practical knowledge management and selection
strategies across runs, or unobtrusive optimization evaluation techniques. Several
recent research eorts [Fursin et al. 2005; Lau et al. 2006; Stephenson 2006] suggest
to use procedure cloning to search for best optimizations at runtime or create
adaptive applications that can react to runtime behavior. In this article we combine
and extend techniques from [Fursin et al. 2005] that are compatible with regular
scientic programs and use low-overhead runtime phase detection, and methods
from [Stephenson 2006; Lau et al. 2006] that can be applied to programs with
irregular behavior in dynamic environments by randomly executing code versions
and using statistical analysis of the collected execution times with a condence
metric. Another recent research project investigates the potential of optimizing
static programs across multiple datasets [Fursin et al. 2007] and suggests this task
is tractable though not necessarily straightforward.
The approaches closest to ours are presented in [Arnold et al. 2005] and [Stephen-
son 2006]. The system in [Arnold et al. 2005] collects prole information across
multiple runs of a program in IBM J9 Java VM to selectively apply optimizations
and improve further invocations of a given program. However it does not enable
optimization knowledge reuse from dierent users, programs and architectures. On
the contrary, Stephenson tunes a Java JIT compiler across executions by multiple
users. While several aspects of his approach are applicable to static compilers,
much of his work focuses on Java specics, such as canceling performance noise due
to methods recompilation, or the impact of garbage collection. Another distinctive
issue is that, in a JIT, the time to predict optimizations and to recompile must be
factored in, while our framework tolerates well long lapses between recompilations,
including several runs with the same optimizations. Finally, we focus more on the
impact of datasets from multiple users and the optimization selection robustness
(through competitions and meta-distribution).
Interestingly, in [Mytkowicz et al. 2009] the authors raise an important issue
of the measurement bias demonstrating that the obtained speedups can dier due
to dierent experimental setup settings. The authors suggest to use more diverse
benchmarks and experimental setup randomization among other solutions to min-
imize this bias. The collective optimization approach already inherently takes into
account these eects and ensures optimization portability by obtaining experimen-
tal results from multiple users with diverse setups, architectures, programs, and
datasets.
9. CONCLUSIONS AND FUTURE WORK
The rst contribution of this article is to identify the true limitations of the adop-
tion of iterative optimization in production environments, while most studies keep
focusing on showing the performance potential of iterative optimization. We be-
lieve the key limitation is the large amount of knowledge (runs) that must be
accumulated to eciently guide the selection of compiler optimizations. The sec-
ond contribution is to show that it is possible to simultaneously learn and improve
performance across runs. The third contribution is to propose multi-level competi-
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
26
tion (among optimizations and their distributions which capture dierent program
knowledge maturation stages, and among programs) to understand the impact of
optimizations without even a reference run for computing speedups, while ensuring
optimization robustness. The program reactions to transformations used to build
such distributions provide a simple and practical way to characterize programs
based solely on execution time. The fourth contribution is to highlight that knowl-
edge accumulated across datasets for a single program is more useful, in the real
and practical context of collective optimization, than the knowledge accumulated
across programs, while most iterative optimization studies focus on knowledge ac-
cumulated across programs; we also conclude that knowledge across architectures
is useful at start-up but does not bring any particular advantage in steady-state
performance. The fth and nal contribution is to address the engineering issue of
unobtrusively collecting information on runs for statically compiled programs and
for reoptimizing programs across runs, based on optimizations suggestions.
Furthermore, we started disseminating all the prototypes of our open collec-
tive optimization research platform based on GCC (and other compilers, including
LLVM, ROSE, ICC, Open64, are also partially supported), connected to a public
collective optimization database [Fursin 2009; Link-repository ; Link-ICI ]. We ini-
tiated a long-term collaborative community-driven eort at [Link] to extend
and deploy our framework in current cloud computing environments, data centers,
mobile systems (based on Moblin or Android), or traditional personal computers
to automate program and whole system optimization as well as compiler tuning.
The convergence time of collective optimization, while perfectly acceptable for
largely used programs, remains long for programs which will be used tens or hun-
dreds of times only. For that purpose, we intend to combine static and dynamic
program characterization techniques from [Agakov et al. 2006; Stephenson and
Amarasinghe 2005; Cavazos et al. 2007; Fursin et al. 2008] with our statistical
collective optimization approach and program characterization by optimization re-
actions, to dene initial d
3
distributions for the rst runs.
While we have evaluated learning across datasets, programs and architectures,
we have not yet evaluated learning across compilers. In the present article, all op-
timizations are dened as combinations of individual compiler transformations. As
a result, they cannot be directly translated to other compilers. For that reason,
we are in the process of expressing optimizations as combinations of standard com-
piler optimization algorithms (e.g., loop unrolling, induction variable elimination,
etc.), a denition which would span all compiler platforms. Moreover, using the
Interactive Compilation Interface and plugin system for GCC and other compilers
[Fursin et al. 2008; Link-ICI ], we can directly invoke transformations, change their
parameters, and their order at the function or loop level, and add plugins with new
transformations.
The collective optimization approach opens up many other research directions.
For instance, thanks to the transparent collection of a large amount of optimization
data, we can perform statistically rigorous evaluation of iterative optimization.
Analyzing multiple performance anomalies we can detect weaknesses of current
architectures and suggest possible improvements. Since dierent program versions
may most likely benet from runs of past versions, we can speed up the optimization
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
27
of new software versions. Optimizations could be further rened at the dataset level
by clustering datasets and using our cloning and runtime comparison mechanism to
select the most appropriate combinations of optimizations or even recongure the
processor at runtime. By combining our approach with program instrumentation of
loads and stores, we might be able to distribute the burden of analysis of runtime
data dependencies of multiple programs and datasets to automate and simplify
program parallelization. And, after sucient knowledge has been accumulated,
the collective database may become a useful tool for dening truly representative
benchmarks. Finally, we believe that the framework and the public optimization
repository might also help improve research methodology by allowing to faithfully
repeat and share experimental results.
ACKNOWLEDGMENTS
We would like to thank our colleagues from INRIA, University of Edinburgh, In-
stitute of Computing Technology of Chinese Academy of Science and users from
GCC, cTuning, and HiPEAC communities for their useful feedback. We would also
like to thank anonymous reviewers for their insightful comments to improve this
article.
REFERENCES
Agakov, F., Bonilla, E., Cavazos, J., Franke, B., Fursin, G., OBoyle, M., Thomson, J.,
Toussaint, M., and Williams, C. 2006. Using machine learning to focus iterative optimization.
In Proceedings of the International Symposium on Code Generation and Optimization (CGO).
Anderson, J., Berc, L., Dean, J., Ghemawat, S., Henzinger, M., Leung, S., Sites, D., Van-
devoorde, M., Waldspurger, C., and Weihl, W. 1997. Continuous proling: Where have
all the cycles gone. In Technical Report 1997-016. Digital Equipment Corporation Systems
Research Center, Palo Alto, CA.
Arnold, M., Welc, A., and [Link]. 2005. Improving virtual machine performance us-
ing a cross-run prole repository. In Proceedings of the ACM Conference on Object-Oriented
Programming, Systems, Languages and Applications (OOPSLA).
Bailey, D. H., Chame, J., Chen, C., Dongarra, J., Hall, M., Hollingsworth, J. K., Hov-
land, P., Moore, S., Seymour, K., Shin, J., Tiwari, A., Williams, S., and You, H. 2008.
Peri auto-tuning. Journal of Physics: Conference Series (SciDAC 2008) 125.
Bodin, F., Kisuki, T., Knijnenburg, P., OBoyle, M., and Rohou, E. 1998. Iterative com-
pilation in a non-linear optimisation space. In Proceedings of the Workshop on Prole and
Feedback Directed Compilation.
Cavazos, J., Dubach, C., Agakov, F., Bonilla, E., OBoyle, M., Fursin, G., and Temam,
O. 2006. Automatic performance model construction for the fast software exploration of new
hardware designs. In Proceedings of the International Conference on Compilers, Architecture,
And Synthesis For Embedded Systems (CASES).
Cavazos, J., Fursin, G., Agakov, F., Bonilla, E., OBoyle, M., and Temam, O. 2007. Rapidly
selecting good compiler optimizations using performance counters. In Proceedings of the 5th
Annual International Symposium on Code Generation and Optimization (CGO).
Cooper, K., Schielke, P., and Subramanian, D. 1999. Optimizing for reduced code space using
genetic algorithms. In Proceedings of the Conference on Languages, Compilers, and Tools for
Embedded Systems (LCTES). 19.
Cooper, K., Subramanian, D., and Torczon, L. 2002. Adaptive optimizing compilers for the
21st century. Journal of Supercomputing 23, 1, 722.
Dubach, C., Jones, T. M., Bonilla, E. V., Fursin, G., and OBoyle, M. F. 2009. Portable
compiler optimization across embedded programs and microarchitectures using machine learn-
ing. In Proceedings of the 42nd International Symposium on Microarchitecture (MICRO).
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
28
Eeckhout, L., Vandierendonck, H., and Bosschere, K. D. 2003. Quantifying the impact
of input data sets on program behavior and its applications. Journal of Instruction-Level
Parallelism 5, 133.
Franke, B., OBoyle, M., Thomson, J., and Fursin, G. 2005. Probabilistic source-level opti-
misation of embedded programs. In Proceedings of the Conference on Languages, Compilers,
and Tools for Embedded Systems (LCTES).
Fursin, G. 2009. Collective tuning initiative: automating and accelerating development and
optimization of computing systems. In Proceedings of the GCC Developers Summit.
Fursin, G., Cavazos, J., OBoyle, M., and Temam, O. 2007. Midatasets: Creating the conditions
for a more realistic evaluation of iterative optimization. In Proceedings of the International
Conference on High Performance Embedded Architectures & Compilers (HiPEAC).
Fursin, G., Cohen, A., OBoyle, M., and Temam, O. 2005. A practical method for quickly eval-
uating program optimizations. In Proceedings of the 1st International Conference on High Per-
formance Embedded Architectures & Compilers (HiPEAC). Number 3793 in LNCS. Springer
Verlag, 2946.
Fursin, G., Miranda, C., Temam, O., Namolaru, M., Yom-Tov, E., Zaks, A., Mendelson, B.,
Barnard, P., Ashton, E., Courtois, E., Bodin, F., Bonilla, E., Thomson, J., Leather, H.,
Williams, C., and OBoyle, M. 2008. Milepost gcc: machine learning based research compiler.
In Proceedings of the GCC Developers Summit.
Fursin, G., OBoyle, M., and Knijnenburg, P. 2002. Evaluating iterative compilation. In
Proceedings of the Workshop on Languages and Compilers for Parallel Computers (LCPC).
305315.
Guthaus, M. R., Ringenberg, J. S., Ernst, D., Austin, T. M., Mudge, T., and Brown, R. B.
2001. Mibench: A free, commercially representative embedded benchmark suite. In Proceedings
of the IEEE 4th Annual Workshop on Workload Characterization. Austin, TX.
Hoste, K. and Eeckhout, L. 2008. Cole: Compiler optimization level exploration. In Proceedings
of International Symposium on Code Generation and Optimization (CGO).
Huang, Y., Peng, L., Wu, C., Kashnikov, Y., Renneke, J., and Fursin, G. 2010. Transforming
gcc into a research-friendly environment: plugins for optimization tuning and reordering, func-
tion cloning and program instrumentation. In 2nd International Workshop on GCC Research
Opportunities (GROW), colocated with HiPEAC10 conference.
Kisuki, T., Knijnenburg, P., and OBoyle, M. 2000. Combined selection of tile sizes and unroll
factors using iterative compilation. In Proceedings of the International Conference on Parallel
Architectures and Compilation Techniques (PACT). 237246.
Kulkarni, P., Zhao, W., Moon, H., Cho, K., Whalley, D., Davidson, J., Bailey, M., Paek,
Y., and Gallivan, K. 2003. Finding eective optimization phase sequences. In Proceedings of
the Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES). 1223.
Lattner, C. and Adve, V. 2004. Llvm: A compilation framework for lifelong program analysis
& transformation. In Proceedings of the 2004 International Symposium on Code Generation
and Optimization (CGO). Palo Alto, California.
Lau, J., Arnold, M., Hind, M., and Calder, B. 2006. Online performance auditing: Using hot
optimizations without getting burned. In Proceedings of the ACM SIGPLAN Conference on
Programming Languaged Design and Implementation (PLDI).
Link-ICI. ICI: Interactive Compilation Interface: unied plugin system to convert black-box
production compilers into interactive research toolsets. [Link]
Link-MiDatasets. MiDataSets: multiple datasets for MiBench benchmark to enable realistic
research on iterative compilation and adaptive optimization. [Link]
Link-MILEPOST. MILEPOST project archive (MachIne Learning for Embedded PrOgramS
opTimization). [Link]
Link-OProfile. OProle: system-wide proler for Linux systems, capable of proling all running
code at low overhead. [Link]
Link-repository. Public collaborative repository and tools for program and architecture char-
acterization and optimization. [Link]
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.
29
Lu, J., Chen, H., Yew, P.-C., and Hsu, W.-C. 2004. Design and implementation of a lightweight
dynamic optimization system. In Journal of Instruction-Level Parallelism. Vol. 6.
Matteo, F. and Johnson, S. 1998. FFTW: An adaptive software architecture for the FFT. In
Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing.
Vol. 3. Seattle, WA, 13811384.
Monsifrot, A., Bodin, F., and Quiniou, R. 2002. A machine learning approach to automatic
production of compiler heuristics. In Proceedings of the International Conference on Articial
Intelligence: Methodology, Systems, Applications. LNCS 2443. 4150.
Mytkowicz, T., Diwan, A., Hauswirth, M., and Sweeney, P. F. 2009. Producing wrong
datawithout doing anything obviously wrong! In Proceedings of the Architectural Support for
Programming Languages and Operating Systems (ASPLOS).
Pan, Z. and Eigenmann, R. 2004. Rating compiler optimizations for automatic performance
tuning. In Proceedings of the International Conference on Supercomputing.
Pan, Z. and Eigenmann, R. 2006. Fast and eective orchestration of compiler optimizations
for automatic performance tuning. In Proceedings of the International Symposium on Code
Generation and Optimization (CGO). 319332.
Qasem, A., Kennedy, K., and Mellor-Crummey, J. 2006. Automatic tuning of whole ap-
plications using direct search and a performance-based transformation system. Journal of
Supercomputing 36, 2, 183196.
Singer, B. and Veloso, M. 2000. Learning to predict performance from formula modeling and
training data. In Proceedings of the Conference on Machine Learning.
Stephenson, M. and Amarasinghe, S. 2005. Predicting unroll factors using supervised classi-
cation. In Proceedings of the IEEE/ACM International Symposium on Code Generation and
Optimization (CGO).
Stephenson, M., Martin, M., and OReilly, U. 2003. Meta optimization: Improving com-
piler heuristics with machine learning. In Proceedings of the ACM SIGPLAN Conference on
Programming Language Design and Implementation (PLDI). 7790.
Stephenson, M. W. 2006. Automating the construction of compiler heuristics using machine
learning. Ph.D. thesis, MIT, USA.
Triantafyllis, S., Vachharajani, M., Vachharajani, N., and August, D. 2003. Compiler
optimization-space exploration. In Proceedings of the International Symposium on Code Gen-
eration and Optimization (CGO). 204215.
Voss, M. and Eigenmann, R. 2000. Adapt: Automated de-coupled adaptive program transfor-
mation. In Proceedings of the International Conference on Parallel Processing (ICPP).
Whaley, R. and Dongarra, J. 1998. Automatically tuned linear algebra software. In Proceedings
of the Conference on High Performance Networking and Computing.
Zhao, M., Childers, B. R., and Soffa, M. L. 2005. A model-based framework: an approach for
prot-driven optimization. In Proceedings of the Interational Conference on Code Generation
and Optimization (CGO). 317327.
Received November 2008; revised February 2010; accepted June 2010
ACM Transactions on Architecture and Code Optimization, Vol. 7, No. 4, December 2010.