Grigori Fursin
email: grigori.fursin@inria.fr

Collective Tuning Initiative: automating and accelerating development and optimization of computing systems

Keywords: systematic benchmarking, performance analysis, performance tuning, energy minimization, size minimization, automatic program optimization, architecture

Computing systems rarely deliver best possible performance due to ever increasing hardware and software complexity and limitations of the current optimization technology. Additional code and architecture optimizations are often required to improve execution time, size, power consumption, reliability and other important characteristics of computing systems. However, it is often a tedious, repetitive, isolated and time consuming process. In order to automate, simplify and systematize program optimization and architecture design, we are developing open-source modular plugin-based Collective Tuning Infrastructure (http://cTuning.org) that can distribute optimization process and leverage optimization experience of multiple users.

The core of this infrastructure is a Collective Optimization Database that allows easy collection, sharing, characterization and reuse of a large number of optimization cases from the community. The infrastructure also includes collaborative R&D tools with common API (Continuous Collective Compilation Framework, MILEPOST GCC with Interactive Compilation Interface and static feature extractor, Collective Benchmark and Universal Run-time Adaptation Framework) to automate optimization, produce adaptive applications and enable realistic benchmarking. We developed several tools and open web-services to substitute default compiler optimization heuristic and predict good optimizations for a given program, dataset and architecture based on static and dynamic program features and standard machine learning techniques.

Collective tuning infrastructure provides a novel fully integrated, collaborative, "one button" approach to improve existing underperfoming computing systems ranging from embedded architectures to high-performance servers based on systematic iterative compilation, statistical collective optimization and machine learning. Our experimental results show that it is possible to reduce execution time (and code size) of some programs from SPEC2006 and EEMBC among others by more than a factor of 2 automatically. It can also reduce development and testing time considerably. Together with the first production quality machine learning enabled interactive research compiler (MILEPOST GCC) this infrastructure opens up many research opportunities to study and develop future realistic self-tuning and self-organizing adaptive intelligent computing systems based on systematic statistical performance evaluation and benchmarking. Finally, using common optimization repository is intended to improve the quality and reproducibility of the research on architecture and code optimization.

Introduction

Continuing innovation in science and technology requires increasing computing resources while imposing strict requirements on cost, performance, power consumption, size, response time, reliability, portability and design time of computing systems. Embedded and large-scale systems tend to evolve towards complex heterogeneous reconfigurable multiprocessing systems with dramatically increased design, test and optimization time. A compiler is one of the key components of computing systems responsible for delivering high-quality machine code across a wide range of architectures and programs with multiple inputs. However, for several decades compilers fail to deliver portable performance often due to restrictions on optimization time, simplified cost models for rapidly evolving complex architectures, large number of combinations of available optimizations, limitations on run-time adaptation and inability to leverage optimization experience from multiple users efficiently, systematically and automatically.

Tuning compiler optimization heuristic for a given architecture is a repetitive and time consuming process because of a large number of possible transformations, architecture configurations, programs and inputs available as well as multiple optimization objectives such as improving performance, code size, reliability among others. Therefore, when adding new optimizations or retargeting to a new architecture, compilers are often tuned only for a limited set of architecture configurations, benchmarks and transformations thus making even relatively recent computing systems underperform. Hence, most of the time, users have to resort to additional optimizations to improve the utilization of available resources of their systems.

Iterative compilation has been introduced to automate program optimization for a given architecture using an empirical feedback-directed search for good program transformations [START_REF] Whaley | Automatically tuned linear algebra software[END_REF][START_REF] Cooper | Optimizing for reduced code space using genetic algorithms[END_REF][START_REF] Bodin | Iterative compilation in a non-linear optimisation space[END_REF][START_REF] Matteo | FFTW: An adaptive software architecture for the FFT[END_REF][START_REF] Fursin | Evaluating iterative compilation[END_REF][START_REF] Fursin | Iterative Compilation and Performance Prediction for Numerical Applications[END_REF][START_REF] Cooper | Adaptive optimizing compilers for the 21st century[END_REF][START_REF]ACOVEA: Using Natural Selection to Investigate Software Complexities[END_REF][START_REF]SUIF source-to-source compiler system[END_REF][START_REF]ROSE source-to-source compiler framework[END_REF][START_REF]ESTO: Expert System for Tuning Optimizations[END_REF][START_REF]PathScale EKOPath Compilers[END_REF][START_REF] Kulkarni | Finding effective optimization phase sequences[END_REF][START_REF] Triantafyllis | Compiler optimization-space exploration[END_REF][START_REF] Singer | Learning to predict performance from formula modeling and training data[END_REF][START_REF] Pan | Fast and effective orchestration of compiler optimizations for automatic performance tuning[END_REF][START_REF] Heydemann | Iterative compilation for two antagonistic criteria: Application to code size and performance[END_REF][START_REF] Hoste | Cole: Compiler optimization level exploration[END_REF].

Collective Tuning Infrastructure

In order to enable systematic and automatic collection, sharing and reuse of profiling and optimization information from the community, we develop a fully integrated collective tuning infrastructure shown in Figure 1. The core of the cTuning infrastructure is an extendable optimization repository (Collective Optimization Database) to characterize multiple heterogeneous optimization cases from the community which improve execution time and code size, track program and compiler bugs among many others and to ensure their reproducibility. It is described in detail in Section 3. Optimization data can be searched and analyzed using web services with open APIs and external plugins. A user can submit optimization cases either manually using an online submission form at [START_REF]cTuning optimization repository (Collective Optimization Database[END_REF] or automatically using collaborative R&D tools (cTools) [START_REF]Collaborative R&D tools (GCC with ICI, CCC, cBench and UNIDAPT frameworks to enable self-tuning computing systems[END_REF] described in Section 4.

The current cTools include:

• Extensible plugin-enabled Continuous Collective Compilation Framework (CCC) to automate empirical iterative feedback-directed compilation and allow users to explore a part of large optimizations spaces in a distributed manner using multiple search strategies.

• Extensible plugin-enabled GCC with high-level Interactive Compilation Interface (ICI) to open up production compilers and control their compilation flow and decisions using external user-defined plugins. Currently, it allows selection and tuning of compiler optimizations (global compiler flags, passes at function level and fine-grain transformations) as well as program analysis and instrumentation.

• Open-source plugin-based machine learning enabled interactive research compiler based on GCC (MILEPOST GCC) [START_REF] Fursin | Milepost gcc: machine learning based research compiler[END_REF] that includes ICI and a static program feature extractor to substitute default optimization heuristic of a compiler and predict good optimizations based on static and dynamic program features (some general aspects of a program) and machine learning.

• Universal run-time adaptation framework (UNIDAPT) to enable transparent monitoring of dynamic program behavior as well as dynamic optimization and adaptation if statically compiled programs with multiple datasets for uni-core and heterogeneous reconfigurable multi-core architecture based on code multiversioning.

An automatic exploration of optimization spaces is performed using multiple publicly-available realistic programs and their datasets from the community that compose cBench [START_REF]Collective Benchmark: collection of open-source programs and multiple datasets from the community[END_REF]. However, we also plan to use our collective optimization approach when stable to enable a fully transparent collection of optimization cases from multiple users [START_REF] Fursin | Collective optimization[END_REF].

The cTuning infrastructure is available online at the community-driven wiki-based web portal [START_REF]Collective Tuning Center: automating and systematizing the design and optimization of computing systems[END_REF] and has been extended within MILEPOST project [START_REF]EU Milepost project (MachIne Learning for Embedded PrOgramS opTimization[END_REF]. It now includes plugins to automate compiler and architecture design, substitute default GCC optimization heuristic and predict good program optimizations for a wide range of architectures using machine learning and statistical collective optimization plugins [START_REF] Fursin | Collective optimization[END_REF][START_REF] Fursin | Milepost gcc: machine learning based research compiler[END_REF]. But more importantly, it creates a common platform for innovation and opens up multiple research possibilities for the academic community and industry.

Collective Optimization Database

Collective Optimization Database (COD) is the key component of the cTuning infrastructure serving as a common extensible open online repository of a large number of optimization cases from the community. Such cases include program optimizations and architecture configurations to improve execution time, code size, power consumption or detect performance anomalies and bugs, etc. COD should be able to keep enough information to describe optimization cases and characterize program compilation and optimization flow, run-time behavior and architecture parameters to ensure reproducibility and portable performance for collective optimization. Before the MILEPOST project, COD had a fully centralized design shown in Figure 2a with all the data coming directly from users. Such design may cause large communication overheads and database overloading thus requiring continuous resource-hungry pruning of the data on the database server. Therefore, the design of COD has been gradually altered to support local user-side filtering of optimization information using plugins of CCC framework as shown in Figure 2b. Currently, plugin-based filters detect optimization cases that improve execution time and code size based on Pareto-like distributions or that has some performance anomalies to allow further detailed analysis. We gradually extend these filters to detect important program and architecture optimizations as well as useful static and dynamic program features automatically based on Principle Component Analysis and similar techniques [START_REF] Cavazos | Rapidly selecting good compiler optimizations using performance counters[END_REF] to improve the correlation between program structure or behavior and optimizations.

We also investigate the possibility to develop a fully decentralized collective tuning system to enable continuous exploration, analysis and filtering of program optimizations, static/dynamic features and architecture configurations as well as transparent sharing and reuse of optimization knowledge between multiple users based on P2P networks.

Current design of COD presented in Figure 3 has been influenced by the requirements of the MILEPOST project [START_REF]EU Milepost project (MachIne Learning for Embedded PrOgramS opTimization[END_REF] to collect a large number of optimization cases for different programs, datasets and architectures during iterative feedback-directed compilation from several partners. These cases are used to train machine learning model and predict good optimizations for a given program on a given reconfigurable architecture based on program static or dynamic features [START_REF] Fursin | Milepost gcc: machine learning based research compiler[END_REF][START_REF] Cavazos | Rapidly selecting good compiler optimizations using performance counters[END_REF].

Before participating in collective tuning and sharing of optimization cases, users must register their computing systems or find similar ones from the existing records. This includes information about their computing platforms (architecture, GPUs, accelerators, memory and HDD parameters, etc), software environment (OS and libraries), compiler and run-time environment (VM or architecture simulator, if used). Users can participate in distributed exploration of optimization spaces using cBench that is already prepared to work directly with the cTuning infrastructure. Alternatively, users can register and prepare their own programs and datasets to support cTuning infrastructure using CCC framework. Currently, we are extending the cTuning infrastructure and GCC to enable transparent program optimization without Makefile or project modifications [START_REF]Google Summer of Code'2009 projects to extend CCC, GCC with ICI and UNIDAPT frameworks[END_REF] based on collective optimization concept [START_REF] Fursin | Collective optimization[END_REF] and UNIDAPT framework [START_REF]Universal adaptation framework to enable dynamic optimization and adaptation for statically-compiled programs[END_REF].

Platforms unique PLATFORM_ID

Compilers unique COMPILER_ID

Runtime environments unique RE_ID

Programs unique PROGRAM_ID

Datasets unique DATASET_ID

Platform features unique PLATFORM_FEATURE_ID

Global platform optimization flags unique OPT_PLATFORM_ID

Global optimization flags unique OPT_ID

Optimization passes unique OPT_PASSES_ID

Compilation info unique COMPILE_ID

Execution info unique RUN_ID unique RUN_ID_ASSOCIATE

Program passes associated COMPILE_ID

Program features associated COMPILE_ID

Common Optimization Database (shared among all users)

Local or shared databases with optimization cases

All the information about computing systems is recorded in COD and shared among all users. All the records have unique UUID-based identifiers to enable full decentralization of the infrastructure and unique referencing of optimization cases by the community (in reports, documentation and research publications for example).

Each optimization case is represented by a combination of program compilations (with different optimizations and architecture configurations) and executions (with the same or different dataset and run-time environment). The optimization information from a user is first collected in the Local Optimization Database to enable data filtering, minimize global communication costs and provide a possibility for internal non-shared optimizations within companies. Each record in the databases has a unique UUID-based identifier to simplify merging of the distributed filtered data in COD.

Information about compilation process is recorded in a special COD table described in Figure 4. In order to reduce the size of the database, the information that can be shared among multiple users or among multiple optimization cases from a given user has been moved to special common tables. This includes global optimization flags, architecture configuration flags (such as -msse2, -mA7, -ffixed-r16, -march=athlon64, -mtune=itanium2) and features, sequences of program passes applied to functions when using a compiler with the Interactive Compilation Interface, program static features extracted using MILEPOST GCC [START_REF] Fursin | Milepost gcc: machine learning based research compiler[END_REF] among others.

Information about program execution is recorded in a special COD table described in Figure 5. Though an absolute execution time can be important for benchmarking and other reasons, we are more interested in how optimization cases improve execution time, code size or other characteristics. In the case of "traditional" feedback-directed compilation, we need two or more runs with the same dataset to evaluate the impact of optimizations on execution time or other metrics: one with the reference optimization level such as -O3 (referenced by RUN ID ASSOCIATE) and another with a new set of optimizations and exactly the same dataset (referenced by RUN ID). When a user explores larger optimization space using CCC framework for a given program with a given dataset, the obtained combination of multiple optimization cases includes the same associated reference id (RUN ID ASSOCIATE) to be able to calculate improvements over original execution time or other metrics. We perform multiple runs with the same optimization and the same dataset to calculate speedup confidence and deal with timer/hardware counters noise. We use the MD5 CRC of the executable (OBJ MD5CRC) to compare a transformed code with the original one and avoid executing code when optimizations did not affect the code.

When sharing multiple optimization cases among users, there is a natural competition between different optimizations that can improve a computing system. Hence, we use a simple ranking system to favor stable optimization cases across the largest number of users. Currently, users rank optimization cases manually, however we plan to automate this process using statistical ranking of optimizations described in [START_REF] Fursin | Collective optimization[END_REF]. This will require extensions to the UNIDAPT framework [START_REF]Universal adaptation framework to enable dynamic optimization and adaptation for statically-compiled programs[END_REF] described later to enable transparent evaluation of program optimizations with any dataset during single execution without a need for a reference run based on static multiversioning and statistical run-time optimization evaluation [START_REF] Fursin | A practical method for quickly evaluating program optimizations[END_REF][START_REF] Fursin | Collective optimization[END_REF][START_REF]Collaborative R&D tools (GCC with ICI, CCC, cBench and UNIDAPT frameworks to enable self-tuning computing systems[END_REF].

At the moment, COD uses MYSQL engine and can be accessed either directly or through online web-services. The full description of the COD structure and web-service is available at the collective tuning website [START_REF]cTuning optimization repository (Collective Optimization Database[END_REF]. Since collective tuning is

Collaborative R&D Tools

Many R&D tools have been developed in the past few decades to enable empirical iterative feedback-directed optimization and analysis including [START_REF]ACOVEA: Using Natural Selection to Investigate Software Complexities[END_REF][START_REF]SUIF source-to-source compiler system[END_REF][START_REF]ROSE source-to-source compiler framework[END_REF][START_REF] Whaley | Automatically tuned linear algebra software[END_REF][START_REF]ESTO: Expert System for Tuning Optimizations[END_REF][START_REF]PathScale EKOPath Compilers[END_REF][START_REF] Singer | Learning to predict performance from formula modeling and training data[END_REF][START_REF] Kulkarni | Finding effective optimization phase sequences[END_REF]. However they are often slow, often domain, compiler and platform specific, and are not capable of sharing and reusing optimization information about different programs, datasets, compilers and architectures. Moreover, they are often not compatible with each other, not fully supported, are unstable and sometimes do not provide open sources to enable further extensions. As a result, iterative feedback-directed compilation has not yet been widely adopted.

Previously, we have shown the possibility for realistic, fast and automatic program optimization and compiler/architecture co-tuning based on empirical optimization space exploration, statistical analysis, machine learning and run-time adaptation [START_REF] Fursin | Evaluating iterative compilation[END_REF][START_REF] Fursin | Iterative Compilation and Performance Prediction for Numerical Applications[END_REF][START_REF] Agakov | Using machine learning to focus iterative optimization[END_REF][START_REF] Fursin | A practical method for quickly evaluating program optimizations[END_REF][START_REF] Franke | Probabilistic source-level optimisation of embedded programs[END_REF][START_REF] Cavazos | Rapidly selecting good compiler optimizations using performance counters[END_REF][START_REF] Fursin | Milepost gcc: machine learning based research compiler[END_REF][START_REF] Luo | Finding representative sets of optimizations for adaptive multiversioning applications[END_REF][START_REF] Fursin | Collective optimization[END_REF]. After we obtained promising results and our techniques become more mature, we decided to initiate a rigorous systematic evaluation and validation of iterative feedback-directed optimization techniques across multiple programs, datasets, architectures and compilers but faced a lack of generic, stable, extensible and portable open-source infrastructure to support this empirical study with multiple optimization search strategies. Hence, we decided to develop and connect all our tools, benchmarks and databases together within Collective Tuning Infrastructure using open APIs and move all our developments to the public domain [START_REF]Collaborative R&D tools (GCC with ICI, CCC, cBench and UNIDAPT frameworks to enable self-tuning computing systems[END_REF][START_REF]cTuning community mailing lists[END_REF] to extend our techniques and enable further collaborative and systematic community-driven R&D to automate code and architecture optimization and enable future self-tuning adaptive computing systems.

Instead of developing our own source-to-source transformation and instrumentation tools, we decided to reuse and "open up" existing production quality compilers using an event-driven plugin system called Interactive Compilation Interface (ICI) [START_REF]Interactive Compilation Interface: high-level event-driven plugin framework to open up production compilers and control their internal decisions using dynamically loaded user plugins[END_REF][START_REF] Fursin | A practical method for quickly evaluating program optimizations[END_REF][START_REF] Fursin | Building a practical iterative interactive compiler[END_REF][START_REF] Fursin | Milepost gcc: machine learning based research compiler[END_REF]. We decided to use GCC for our project since it is a unique open-source production quality compiler that supports multiple architectures, languages and has a large user base. Using a plugin-enabled production compiler can improve the quality and reproducibility of research and help to move research prototypes back to a compiler much faster for the benefit of the whole community.

Finally, we are developing a universal run-time adaptation framework (UNIDAPT) to enable transparent collective optimization, run-time adaptation and split compilation for statically compiled programs with multiple datasets across different uni-core and multi-core heterogeneous architectures and environments [START_REF] Fursin | A practical method for quickly evaluating program optimizations[END_REF][START_REF] Luo | Finding representative sets of optimizations for adaptive multiversioning applications[END_REF][START_REF] Fursin | Collective optimization[END_REF][START_REF] Jimenez | Predictive runtime code scheduling for heterogeneous architectures[END_REF]. We have also collected multiple datasets within Collective Benchmark (formerly MiBench/MiDataSets) to enable realistic research on program optimization with multiple inputs.

We hope that using common tools will help to avoid costly duplicate developments, will improve quality and reproducibility of the research and will boost innovation in program optimization, compiler design and architecture tuning.

Continuous Collective Compilation Framework

In [START_REF] Fursin | Evaluating iterative compilation[END_REF][START_REF] Fursin | Fast and accurate method for determining a lower bound on execution time[END_REF][START_REF] Fursin | Iterative Compilation and Performance Prediction for Numerical Applications[END_REF] we demonstrated the possibility to apply iterative feedback-directed compilation to large applications at a loop level. It was a continuation of the MHAOTEU project (1999-2000) [START_REF] Abella | The mhaoteu toolset for memory hierarchy management[END_REF] where we had to develop a source-to-source Fortran 77 and C compiler to enable parametric transformations such as loop unrolling, tiling, interchange, fusion/fission, array padding and some others, evaluate their effect on large and resource-hungry programs, improve their memory utilization and execution time on high-performance servers and supercomputers, and predict the performance upper bound to guide iterative search. The MHAOTEU project was in turn a continuation of the OCEANS project (1996)(1997)(1998)(1999) where general iterative feedback-directed compilation was introduced to optimize relatively small kernels and applications for embedded computing systems [START_REF] Aarts | OCEANS: Optimizing compilers for embedded applications[END_REF].

In order to initiate further rigorous systematic evaluation and validation of iterative code and architecture optimizations, we started developing our own open-source modular Continuous Collective Compilation framework (CCC). CCC framework is intended to automate program optimization, compiler design and architecture tuning using empirical iterative feedback-directed compilation. It enables collaborative and distributed exploration of program and architecture optimization spaces and collects static and dynamic optimization and profile statistics in COD. CCC has been designed using modular approach as shown in figure 6. It has several low-level platform-dependent tools and platform-independent tools to abstract compilation and execution of programs. It also includes routines to communicate with COD and high-level plugins for iterative compilation with multiple search strategies, statistical analysis and machine learning.

CCC is installed using INSTALL.sh script from the root directory. During installation, several scripts are invoked to configure the system, provide info about architectures, environments, compilers, runtime systems and set up an environment. Before compilation of platform-dependent tools, a user must select the how to store optimization and profile information, i.e. within local or shared COD at each step, or as a minimal off-line mode when all statistics is recorded in a local directory of each optimized program. An off-line mode can be useful for GRID-like environments with network filters such as GRID5000 [START_REF]Computing infrastructure distributed in 9 sites around France, for research in large-scale parallel and distributed systems[END_REF] where all statistics from multiple experiments can be aggregated in a text file and recorded in COD later. CCC may require PHP, PAPI library, PapiEx, uuidgen and oprofile for extended functionality and MYSQL client to work with local and shared COD (Figure 3) configured using the following environment variables: We decided to utilize a systematic top-down approach for optimizations: though originally we started our research on iterative compilation from fine-grain loop transformations [START_REF] Abella | The mhaoteu toolset for memory hierarchy management[END_REF][START_REF] Fursin | Evaluating iterative compilation[END_REF][START_REF] Fursin | Iterative Compilation and Performance Prediction for Numerical Applications[END_REF], we think that the current research on architecture and code optimizations focuses too much on solving only local issues while sometimes overlooking global and coarse-grain problems. Therefore, we first developed optimization space exploration plugins with various search algorithms for global compiler flags and started gradually adding support for finer grain program optimizations using plugin-enabled GCC with ICI (described in Section 4.2).

Originally, we started using Open64/PathScale compilers for our systematic empirical studies [START_REF] Fursin | A practical method for quickly evaluating program optimizations[END_REF][START_REF] Cavazos | Automatic performance model construction for the fast software exploration of new hardware designs[END_REF][START_REF] Fursin | Midatasets: Creating the conditions for a more realistic evaluation of iterative optimization[END_REF] but gradually moved to GCC since it is the only open-source production-quality compiler that supports multiple architectures (more than 30 families) and languages. It also features many aggressive optimizations including a unique GRAPHITE coarse-grain polyhedral optimization framework. However, CCC framework can be easily configured to support multiple compilers including LLVM,GCC4NET,Open64,Intel ICC,IBM XL and others to enable a fair comparison of different compilers and available optimization heuristics.

The first basic low-level platform-dependent tool ( ccc-time) is intended to execute applications on a given architecture, collect various row profile information such as function level profiling and monitor hardware performance counters using popular PAPI library [START_REF]PAPI: A Portable Interface to Hardware Performance Counters[END_REF], PAPIEx [START_REF]PapiEx: Performance analysis tool designed to transparently and passively measure the hardware performance counters of an application using PAPI[END_REF] and OProfile [START_REF]OProfile: A continuous system-wide profiler for Linux[END_REF] tools. This tool is very small and portable tested on a number of platforms ranging from supercomputers and high-performance servers based on Intel, AMD, Cell and NVidia processors and accelerators to embedded systems from ARC, STMicroelectronics and ARM.

Other two major platform-independent components of CCC are ccc-comp and ccc-run that provide all the necessary functionality to compile application with different optimizations, execute a binary or byte code with multiple datasets, process row profile statistics from ccc-time, validate program output correctness, etc. Currently, these tools work with specially prepared programs and datasets such as Collective Benchmark (cBench) described in section 4.3 in order to automate the optimization process and validation of the code correctness. However, the required changes are minimal and we have already converted all programs from EEMBC, SPEC CPU 95,2000,2006 and cBench to work with CCC framework. We are currently extending CCC framework within Google Summer of Code 2009 program [START_REF]Google Summer of Code'2009 projects to extend CCC, GCC with ICI and UNIDAPT frameworks[END_REF] to enable transparent continuous collective optimization, fine-grain program transformations and run-time adaptation within GCC without any Makefile modifications based on a statistical collective optimization concept [START_REF] Fursin | Collective optimization[END_REF].

The command line format of ccc-comp and ccc-run is the following:

• ccc-comp descriptive compiler name compiler optimization flags recorded in COD compiler auxiliary flags not recorded in COD

• ccc-run dataset number 1 if baseline reference run (optional)

Normally, we start iterative compilation and optimization space exploration with the baseline reference compilation and execution such as ccc-comp milepostgcc44 -O3 and ccc-run 1 1 where milepostgcc44 is the sample descriptive name of machine learning enabled GCC with ICI v2.0 and feature extractor v2.0 registered during CCC configuration of available compilers, -O3 is the best optimization level of GCC to be improved. The first parameter of ccc-run is the dataset number (for specially prepared benchmarks with multiple datasets) and the second parameter indicates that it is the reference run when the program output will be recorded to help validate correctness of optimizations during iterative compilation. #Architecture specific optimization flags for design space exploration export CCC OPT PLATFORM="-mA7 -ffixed-r12 -ffixed-r16 -ffixed-r17 -ffixed-r18 -ffixed-r19 -ffixed-r20 -ffixed-r21 -ffixed-r22 -ffixed-r23 -ffixed-r24 -ffixed-r25" export CCC OPT PLATFORM="-mtune=itanium2" export CCC OPT PLATFORM="-march=athlon64" #In case of multiprocessor and multicore system, select which processor/core to run application on export CCC PROCESSOR NUM= #Select runtime environment (VM or simulator) export CCC RUN RE=llvm25 export CCC RUN RE=ilrun export CCC RUN RE=unisim export CCC RUN RE=simplescalar #Some notes to record in COD together with experimental data export CCC NOTES="test optimizations" #The following variables are currently used in the on-going projects and can change: #Architecture parameters for design space exploration export CCC ARCH CFG="l1 cache=203; l2 cache=35;" export CCC ARCH SIZE=132 #Static parallelization and fine-grain optimizations export CCC OPT FINE="loop tiling=10;" export CCC OPT PAR STATIC="all loops=parallelizable;" #Information about power consumption, energy, dynamic dependencies that should be recorded automatically export CCC RUN POWER= export CCC RUN ENERGY= export CCC PAR DYNAMIC="no deps" We continue exploration of optimizations invoking ccc-comp and ccc-run tools multiple times with different combinations of optimizations controlled either through command-line flags or multiple environment variables shown in Figure 7. At each iterative step these tools compare program output with the output of the baseline reference execution to validate code correctness (though it is clearly not enough and we would like to provide more formal validation plugins) and prepare several text files (information packets) with compilation and execution information that are recorded locally and can be sent to COD using ccc-db-* tools as shown in Figure 8.

Iterative optimization space exploration is performed using high-level plugins that invoke ccc-comp and ccc-run with different optimization parameters. We produced a few plugins written in C and PHP that implement the following several search algorithms and some machine learning techniques to predict good optimizations:

• ccc-run-glob-flags-rnd-uniform -generates uniform random combinations of global optimization flags (each flag has 50% probability to be selected for a generated combination of optimizations)

• ccc-run-glob-flags-rnd-fixed -generates a random combination of global optimizations of a fixed length

• ccc-run-glob-flags-one-by-one -evaluate all available global optimizations one by one

• ccc-run-glob-flags-one-off-rnd -select all optimizations at first step and then remove them one by one (similar to [START_REF] Pan | Fast and effective orchestration of compiler optimizations for automatic performance tuning[END_REF] one of the modes of the PathOpt tool from PathScale compiler suite [START_REF]PathScale EKOPath Compilers[END_REF])

• milepost-gcc -a wrapper around MILEPOST GCC to automatically extract program features and query cTuning web-service to predict good optimization to improve execution time and code size substituting default optimization levels (described more in Section 5).

When distributing optimization space exploration among multiple users or on clusters and GRID-like architectures, each user may specify a different random seed number to explore different parts of optimization spaces on different machines. Best performing optimization cases from all users will later be filtered and joined in COD for further analysis and reuse by the whole community. For example, we can train machine learning models and predict good optimizations for a given program on a given architecture using collective optimization data from COD as shown in Section 5.

During iterative compilation we are interested to filter a large amount of obtained data and find only those optimization cases that improve execution time, code size, power consumption and other metrics depending on the user optimization scenarios or detect some performance anomalies and bugs for further analysis. Hence, we have developed several platform independent plugins (written in PHP) that analyze data in the local database, find such optimization cases (for example, get-all-best-flags-time finds optimization cases that improve execution time and get-all-best-flags-time-size-pareto find cases that improve both execution time and code size using Pareto-like distribution) and record them in COD. Continuously updated optimization cases can be viewed at [START_REF]cTuning optimization repository (Collective Optimization Database[END_REF].

When using random iterative search we may obtain complex combinations of optimizations without clear indication which particular code transformation improves the code. Therefore, we can also use additional pruning of each optimization case and remove those optimizations one by one from a given combination that do not influence performance, code size or other characteristics using ccc-run-glob-flags-one-off-rnd tool. It helps to improve correlation between program features and transformations, and eventually improve optimization predictions based on machine learning techniques such as decision tree algorithms, for example.

Since we also want to explore dynamic optimizations and architecture designs systematically, we are gradually extending CCC to support various VM systems such as MONO and LLVM to evaluate JIT split compilation (finding a balance between static and dynamic optimization using statistical techniques and machine learning) and support multiple architecture simulators such as UNISIM, SimpleScalar and others to enable architecture design space exploration and automate architecture and code co-optimization. More information about current CCC developments is available at our collaborative website [START_REF]Continuous Collective Compilation Framework to automate and distribute program optimization, compiler design and architecture tuning[END_REF]. Some practical CCC usage examples are presented in Section 5.

Interactive Compilation Interface

In 1999-2002, we started developing memory hierarchy analysis and optimization tools for real large high-performance applications within MHAOTEU project [START_REF] Abella | The mhaoteu toolset for memory hierarchy management[END_REF] to build the first realistic adaptive compiler (follow up of the OCEANS project [START_REF] Aarts | OCEANS: Optimizing compilers for embedded applications[END_REF]). Within MHAOTEU project, we attempted to generalize iterative feedback-directed compilation and optimization space exploration to adapt any program to any architecture empirically and automatically improving execution time over the best default optimization heuristic of the state-of-the-art compilers. We decided to focus on a few well-known loop and data transformations such as array padding, reordering and prefetching, loop tiling (blocking), interchange, fusion/fission, unrolling and vectorization as well as some polyhedral transformations. Unlike [START_REF] Cooper | Optimizing for reduced code space using genetic algorithms[END_REF][START_REF] Cooper | Adaptive optimizing compilers for the 21st century[END_REF] where only optimization orders have been evaluated on some small kernels using architecture simulator, we decided to use large SPEC95 and SPEC2000 floating point benchmarks together with a few real applications from MHAOTEU partners as well as several modern at that time architectures to evaluate our approach in practice.

Unfortunately, at that time we could not find any production compiler with fine-grain control of optimization selection while several available source-to-source transformation tools including SUIF [START_REF]SUIF source-to-source compiler system[END_REF] were not stable enough to parse all SPEC codes or enable systematic exploration of complex combinations of optimizations. Hence, we decided to develop our own source-to-source compiler and iterative compilation infrastructure [START_REF]Edinburgh Optimizing Software (EOS) to enable fine-grain source-to-source program iterative optimizations and performance prediction[END_REF] using Octave C/C++/Fortran77 front-end and MARS parallelizing compiler based on polyhedral transformation framework produced at Manchester and Edinburgh Universities [START_REF] O'boyle | Mars: a distributed memory approach to shared memory compilation[END_REF]. However, it was a very tedious and time-consuming task allowing us to evaluate evaluate iterative compilation using only loop tiling, unrolling and array padding by the end of the project. Nevertheless, we got encouraging execution time improvements for SPEC95 and several real large codes from our industrial partners across several RISC and CISC architectures [START_REF] Fursin | Evaluating iterative compilation[END_REF][START_REF] Fursin | Iterative Compilation and Performance Prediction for Numerical Applications[END_REF].

We also managed to develop a prototype of quick upper-bound performance evaluation tool as a stopping criteria for iterative compilation [START_REF] Fursin | Iterative Compilation and Performance Prediction for Numerical Applications[END_REF][START_REF] Fursin | Fast and accurate method for determining a lower bound on execution time[END_REF].

MHAOTEU project helped us to highlight multiple problems when building adaptive compilers and indicated further research directions. For example, state-of-the-art static compilers often fail to produce good quality code (to achieve better code size, execution time, etc) due to hardwired ad-hoc optimization heuristics (cost models) on rapidly evolving hardware, large irregular optimization spaces, fixed order and complex interaction between optimizations inside compiler or between compiler and source-to-source or binary transformation tools, time-consuming retuning of default optimization heuristic for all available architectures when adding new transformations, inability to retarget compiler easily for new architectures particularly during architecture design space exploration, inability to produce mixed-ISA code easily, inability to reuse optimization knowledge among different programs and architectures, lack of run-time information, inability to parallelize code effectively and automatically, lack of run-time adaptation mechanisms for statically compiled programs to be able to react to varying program and system behavior as well as multiple datasets (program inputs) with low overhead. To overcome these problems, we decided to start a long term project to change outdated compilation and optimization technology radically and build a novel realistic adaptive optimization infrastructure that allows rigorous systematic evaluation of empirical iterative compilation, run-time adaptation, collective optimization, architecture design space exploration and machine learning.

IC Plugins

High-level scripting (java, python, etc)

Selecting pass sequences

Extracting static program features <Dynamically linked shared libraries> CCC Framework ...

Local COD Filter

Figure 9: Interactive Compilation Interface: a high-level event-driven plugin framework to open up compilers, extend them and control their internal decisions using dynamically loaded user plugins. This is the first step to enable future modular self-tuning adaptive compilers.

First, we had to decide which program transformation tool to use to enable systematic performance evaluation of our research optimization techniques, i.e. continue developing our own source-to-source interactive compiler which is too time consuming or find some other solution. At the same time, we noticed that some available open-source production compilers such as Open64 started featuring many aggressive loop and array transformations that we planned to implement in our transformation tool. Considering that Open64 was a stable compiler supporting two architectures, C/Fortran languages and could process most of the SPEC codes, we decided to use it for our experiments. We provided a simple interface to open it up and enable external selection of internal loop/array optimizations and their parameters through an event-driven plugin system that we called Interactive Compilation Interface (ICI). We combined it with the Framework for Continuous Optimizations (FCO) and developed several search plugins (random, exhaustive, leave one out, hill climbing) to enable continuous and systematic optimization space exploration using ICI-enabled compiler [START_REF]Framework for Continuous Optimizations (FCO) to enable systematic optimization space exploration using Open64 with Interactive Compilation Interface (ICI)[END_REF]. Since we released ICI for Open64/PathScale compiler in 2005, it has proved to be a simple and efficient way to transform production compilers into iterative research tools and was used in several research projects to fine-tune programs for a given architecture and a dataset [START_REF] Fursin | A practical method for quickly evaluating program optimizations[END_REF][START_REF] Luo | Finding representative sets of optimizations for adaptive multiversioning applications[END_REF]. However, when we tried to extend it to combine reordering of optimizations with fine grain optimizations, we found it too time consuming to modify the rigid optimization manager in Open64.

At the same time, we noticed that there was a considerable community effort to modularize GCC, add a new optimization pass manager with some basic information about dependencies between passes and provide many aggressive optimizations including polyhedral transformations. Considering that it could open up many interesting research opportunities and taking into account that GCC is a unique stable open-source compiler that supports dozens of various architectures, multiple languages, can compile the whole Linux and has a very large community that is important for collective optimization [START_REF] Fursin | Collective optimization[END_REF], we decided to use this compiler for our further research. We developed a new ICI to "hijack" GCC and control its internal decisions through event-driven mechanisms and dynamically loaded plugins. The concept of the new ICI and interactive compilers has been described in [START_REF] Fursin | Building a practical iterative interactive compiler[END_REF] and extended during the MILEPOST project [START_REF] Fursin | Milepost gcc: machine learning based research compiler[END_REF]. Since then, we have moved all the developments to the community-driven website [START_REF]Interactive Compilation Interface: high-level event-driven plugin framework to open up production compilers and control their internal decisions using dynamically loaded user plugins[END_REF] and continued extending it based on user feedback and our research requirements.

Current ICI is an event-driven plugin framework with a high-level compiler-independent and low-level compiler-dependent API to transform production compilers into collaborative open modular interactive toolsets as shown in figure 9. ICI acts as a "middleware" interface between the compiler and the user plugins and enables external program analysis and instrumentation, fine-grain program optimizations without revealing all the internals of a compiler. This makes such ICI-enabled compilers more researchers/developers friendly allowing simple prototyping of new ideas without a deep knowledge of a compiler itself, without a need to recompile a compiler itself and avoiding building new compilation and optimization tools from scratch. Using ICI can also help to avoid time consuming revolutionary approaches to create a new "clean", modular and fast compiler infrastructure from scratch while gradually transforming current rigid compilers into a modular adaptive compiler infrastructure. Finally, we believe that using production compilers with ICI in research can help to move successful ideas back to the compiler much faster for the benefit of all users and boost innovation and research. Accessing this feature has the side effect of setting that specific pass as the "current pass" of ICI. next pass string (char) Human-readable name of the next pass to be executed after the "current pass" of ICI. Accessing this feature has the side effect of advancing the "current pass" of ICI to its immediate successor in the currently defined pass chain.

Figure 10: List of some popular features available in ICI version 2.x

We used GCC with ICI in the MILEPOST project [START_REF]EU Milepost project (MachIne Learning for Embedded PrOgramS opTimization[END_REF] to develop the first machine learning enabled research compiler and enable automatic and systematic optimization space exploration and predict good combinations of optimizations (global flags or passes on a function level) based on static program features and predictive modeling. Together with colleagues from IBM we could easily add feature extractor pass to GCC and had an ability to call it after any arbitrary optimization pass using simple dynamic plugin. Such machine learning enabled self-tuning compiler called MILEPOST GCC (GCC with ICI and static feature extractor) has been released and used by IBM and ARC to improve and speed up the optimization process for their realistic applications. This usage scenario is described more in Section 5) and in [START_REF] Fursin | Milepost gcc: machine learning based research compiler[END_REF].

Current ICI is organized around four main concepts to abstract the compilation process:

• Plugins are dynamically loaded user modules that "hijack" a compiler to control compilation decisions and have an access to some or all of its internal functions and data. Currently, the plugin programming interface consists of three kinds of functions: initialization function that is in charge of starting the plugin, checking compiler and plugin compatibility, and registering event handlers; termination function that is in charge of cleaning up the plugin data structures and closing files, etc; event handler (callback) functions that control a compiler.

• Events are triggered whenever a compiler reaches some defined point during execution. In such case, ICI invokes a user-definable callback function (event handler) referenced simply by a string name.

• Features are abstractions of selected properties of a current compiler state and of a compiled program. The brief list of some available features is shown in Figure 10 ranging from an array of optimization passes to simple string name of a compiled function.

• Parameters are abstractions of compiler variables to decouple plugins from the actual implementation of compiler internals. They are identified simply by a string name and used to get and/or set some values in the compiler such as force inlining of some function or change loop blocking or unrolling factors, for example.

Detailed documentation is available at the ICI collaborative website [START_REF]Interactive Compilation Interface wiki-based documentation[END_REF].

Since 2007, we have been participating in multiple discussions with other colleagues developing their own GCC plugin frameworks such as [START_REF] Starynkevitch | Multi-stage construction of a global static analyser[END_REF][START_REF] Glek | Using gcc instead of grep and sed[END_REF][START_REF] Sean Callanan | Extending gcc with modular gimple optimizations[END_REF], GCC community and steering committee to add a generic plugin framework in GCC. Finally, a plugin framework will be included in mainline GCC 4.5 [16]. This plugin framework is very similar to ICI but more low-level. For example, the set of plugin events is hardwired inside a compiler, plugin callbacks have a fixed, pass-by-value argument set and the pass management is very basic. However, it already provides a multi-plugin support with command-line arguments and callback chains, i.e. lists of callbacks invoked upon a single occurrence of a plugin event, and is a good step towards interactive adaptive compilers. Hence, we are synchronizing ICI with the plugin branch [START_REF]Synchronization of high-level ICI with low-level GCC plugin framework[END_REF] to provide more high-level API including:

• dynamic registration and unregistration of plugin events

• dynamic registration/definition/unregistration of event callback arguments

• arbitrary number of pass-by-name event callback arguments

• ability to substitute complete pass managers (chains of passes)

• high-level access to a compiler state (values of flags and parameters, name and selected properties of the current function, name of a current and next pass) with some modification possibilities (compiler parameters, next pass).

Comparison of ICI and some other available plugin framework for GCC is available at [START_REF]Comparison of ICI and other proposed plugin frameworks for GCC[END_REF]. ICI plugin repository with several test, pass manipulation and machine learning plugins is available at the collaborative development website [START_REF]Interactive Compilation Interface: high-level event-driven plugin framework to open up production compilers and control their internal decisions using dynamically loaded user plugins[END_REF]. During Google Summer of Code'09 program [START_REF]Google Summer of Code'2009 projects to extend CCC, GCC with ICI and UNIDAPT frameworks[END_REF] we have extended ICI and plugins to provide XML representation of the compilation flow, selection and tuning of fine-grain optimizations/polyhedral GRAPHITE transformations and their parameters using machine learning, enable code instrumentation, generic function cloning, run-time adaptation capabilities and collective optimization technology [START_REF] Fursin | Collective optimization[END_REF]. We also ported ICI and MILEPOST program feature extractor to GCC4NET [START_REF]CLI Back-End and Front-End for GCC[END_REF] to evaluate split compilation, i.e. predicting the good balance between optimizations that should be performed at a compile time and the ones that should be performed at run-time when executing code on multiple architectures and with multiple datasets based on statistical analysis and machine learning.

We hope that ICI-like plugin framework will become standard for compilers in the future, will help prototype research ideas quickly, will simplify, modularize and automate compiler design, will allow users to write their own optimization plugins, will enable automatic tuning of optimization heuristic and retargetability for different architectures and will eventually enable smart self-tuning adaptive computing systems for the emerging heterogeneous (and reconfigurable) multi-core architectures. More information about ICI and current collaborative extension projects is available at [START_REF]Interactive Compilation Interface: high-level event-driven plugin framework to open up production compilers and control their internal decisions using dynamically loaded user plugins[END_REF].

Collective Benchmark

Automatic iterative feedback-directed compilation is now becoming a standard technique to optimize programs, evaluate architecture designs and tune compiler optimization heuristics. However, it is often performed with one or several datasets (test, train and ref in SPEC benchmarks for example) with an implicit assumption that the best configuration found for a given program using one or several datasets will work well with other datasets for that program.

We already know well that different optimizations are needed for different datasets when optimizing small kernels and libraries [START_REF] Whaley | Automatically tuned linear algebra software[END_REF][START_REF] Matteo | FFTW: An adaptive software architecture for the FFT[END_REF][START_REF] Singer | Learning to predict performance from formula modeling and training data[END_REF][START_REF] Aarts | OCEANS: Optimizing compilers for embedded applications[END_REF]. For example, different tiling and unrolling factors are required for matrix multiply to better utilize memory hierarchy/ILP and improve execution time depending on the matrix size. However, when evaluating iterative feedback-directed fine-grain optimizations (loop tiling, unrolling and array padding) for large applications even with one dataset [START_REF] Fursin | Evaluating iterative compilation[END_REF][START_REF] Fursin | Iterative Compilation and Performance Prediction for Numerical Applications[END_REF] we confirmed that the effect of such optimizations on a large code can be very different then on kernels and normally much smaller often due to inter-loop and inter-procedural memory locality, complex data dependencies and low memory bandwidth among others.

In order to enable systematic exploration of iterative compilation techniques and realistic performance evaluation for programs with multiple datasets we need benchmarks that have a large number of inputs together with tools that support global inter-procedural and coarse-grain optimizations (and parallelization) based on combination of traditional fine-grain optimizations and polyhedral transformations.

Unfortunately, most of the available open-source and commercial benchmarks has only a few datasets available. Hence, in 2006, we decided to assemble a collection of data sets for a free, commercially representative MiBench [START_REF] Guthaus | Mibench: A free, commercially representative embedded benchmark suite[END_REF] benchmark suite. Originally, we assembled 20 inputs per program, for 26 MiBench programs (520 data sets in total) in the dataset suite that we called MiDataSets [START_REF] Fursin | Midatasets: Creating the conditions for a more realistic evaluation of iterative optimization[END_REF]. We started from the top-down approach evaluating first global optimizations (using compiler flags) [START_REF] Fursin | Midatasets: Creating the conditions for a more realistic evaluation of iterative optimization[END_REF] and gradually adding support to evaluate individual transformations including polyhedral GRAPHITE optimizations in GCC using Interactive Compilation Interface withing GSOC'09 program [START_REF]Google Summer of Code'2009 projects to extend CCC, GCC with ICI and UNIDAPT frameworks[END_REF].

We released MiDataSets in 2007 and since then it has been used in multiple research projects. Therefore, we decided to extend it, add more programs and kernels, update all current MiBench programs to support ANSI C and improve portability across multiple architectures, and create a dataset repository. Therefore, we developed a new research benchmark called Collective Benchmark (cBench) with an open repository [START_REF]Collective Benchmark: collection of open-source programs and multiple datasets from the community[END_REF] to keep various open-source programs with multiple inputs assembled by the community.

Naturally, the span of execution times across all programs and all datasets can be very large which complicates systematic iterative compilation evaluation. For example, when the execution time is too low, it may be difficult to evaluate the impact of optimizations due to measurement noise. In this cases, we add a loop wrapper around a main function moving most of the IO and initialization routines out of it to be able to control the length of the program execution. A user can change the upper bound of the loop wrapper through environment variable or a special text file. We provide the default setting that makes a program run about 10 seconds on AMD Athlon64 3700+. However, if execution time is too high and slows down systematic iterative compilation particularly when using architecture simulators, we are trying to detect those program variables that can control the length of the program execution and allow users to modify them externally. Of course, in such cases, the program behavior may change due to locality issues among others and may require different optimizations which is a subject of further research.

Each program from cBench currently has several Makefiles for different compilers including GCC, GCC4CLI, LLVM, Intel, Open64, PathScale (Makefile.gcc, Makefile.gcc4cli, Makefile.llvm, Makefile.intel, Makefile.open64, Makefile.pathscale respectively). Two basic scripts are also provided to compile and run a program:

• compile Makefile compiler extension Optimization flags

• run dataset number ( loop wrapper bound -using default number if omitted ) Datasets are described in file ccc info datasets that has the following format:

Total number of available datasets ==== Dataset number Command line when invoking executable for this dataset Loop wrapper bound ==== ... Since one of the main purposes of cBench is enabling rigorous systematic evaluation of empirical program optimizations, we included several scripts and files for each cBench program to work with CCC framework and record all experimental data in COD entirely automatically. These scripts and files include:

• ccc program id -file with unique CCC framework ID to be able to share optimization cases with the community within COD [START_REF]cTuning optimization repository (Collective Optimization Database[END_REF].

• ccc prep -script that is invoked before program compilation to prepare directory for execution, i.e. copying some large datasets or compile libraries, for example. It is used for SPEC2006 for example.

• ccc post -script that is invoked after program execution and can be useful when copying profile statistics from remote servers. For example, it is used when executing programs remotely on ARC simulation board using SSH.

• ccc check output.clean -script that removes all output files a program may produce.

• ccc check output.copy -script that saves all output files after a reference run.

• ccc check output.diff -script that compares all output files after execution with the saved outputs from the reference run to have a simple check that a combination of optimizations have been correct. Of course, this method does not prove correctness and we plan to add more formal methods, but it can quickly identify bugs and remove illegal combinations of optimizations.

We believe that this community-assembled benchmark with multiple dataset opens up many research opportunities for realistic code and architecture optimization, improves the quality and reproducibility of the systematic empirical research and can enable more realistic benchmarking of computing systems. For example, we believe that using just one performance metric produced by current benchmarks with some ad-hoc combinations of optimizations and a few datasets may not be enough to characterize the overall behavior of the system since using iterative optimization can result in a much better code. Our approach is to enable continuous monitoring, optimization and characterization of computing systems (programs, datasets, architectures, compilers) to be able to provide a more realistic performance upper bound and comparison after iterative compilation.

We also plan to extend cBench by extracting most time-consuming kernels (functions or loops) from programs with the snapshots of their inputs during multiple program phases (such kernels with encapsulated inputs are called codelets). We will randomly modify and combine them together to produce large training sets from kernels with various features in order to answer a research question whether it is possible to predict good optimizations for large programs based on program decomposition and kernel optimizations. Finally, we plan to add parallel programs and kernels (OpenCL, OpenMP, CUDA, MPI, etc) with multiple datasets to extend research on adaptive parallelization and scheduling for programs with multiple datasets for heterogeneous multi-core architecture [START_REF] Jimenez | Predictive runtime code scheduling for heterogeneous architectures[END_REF].

It is possible to download cBench and participate in collaborative development at [START_REF]Collective Benchmark: collection of open-source programs and multiple datasets from the community[END_REF].

Universal run-time Adaptation Framework for Statically-Compiled Programs

Extract dataset features

Monitor run-time behavior or architectural changes (in virtual, reconfigurable or heterogeneous environments) using timers or performance counters

Selection mechanism optimized for low run-time overhead

Function Version 1

…

Representative set of versions for the following optimization cases to minimize execution time, power consumption and code-size across all available datasets:

• optimizations for different datasets As already mentioned in previous sections, iterative compilation can help optimize programs for any given architecture automatically, but often performed with only one or several datasets. Since it is known that optimal selection of optimizations may depend on program inputs [START_REF] Whaley | Automatically tuned linear algebra software[END_REF][START_REF] Matteo | FFTW: An adaptive software architecture for the FFT[END_REF][START_REF] Singer | Learning to predict performance from formula modeling and training data[END_REF][START_REF] Fursin | Midatasets: Creating the conditions for a more realistic evaluation of iterative optimization[END_REF], just-in-time or hybrid static/dynamic optimization approaches have been introduced to select appropriate optimizations at run-time depending on the context and optimization scenario. However, it is not always possible to use complex recompilation framework particularly in case of resource-limited embedded systems. Moreover, most of the available systems are often limited to only a few optimizations and do not have mechanisms to select a representative set of optimization variants [START_REF] Byler | Multiple version loops[END_REF][START_REF] Diniz | Dynamic feedback: An effective technique for adaptive computing[END_REF][START_REF] Voss | High-level adaptive program optimization with adapt[END_REF][START_REF] Lau | Online performance auditing: Using hot optimizations without getting burned[END_REF].

Statically-compiled adaptive binaries and libraries

Machine learning techniques to find mapping between different run-time contexts and representative versions

Iterative and collective compilation using interactive compilers, source-tosource transformers or manual optimizations

In [START_REF] Fursin | A practical method for quickly evaluating program optimizations[END_REF] we presented a framework (UNIDAPT) that enabled run-time optimization and adaptation for statically compiled binaries and libraries based on static function multiversioning, iterative compilation and low-overhead hardware counters monitoring routines. During compilation, several clones of hot functions are created and a set of optimizations is applied to the clones that may improve execution time across a number of inputs or architecture configurations. During execution, UNIDAPT framework monitors original program and system behavior and occasionally invokes clones to build a table that associates program behavior based on hardware counters (dynamic program features) with the best performing clones, i.e. optimizations. This table is later used to predict and select good clones as a reaction to a given program behavior. It is continuously updated during executions with multiple datasets and on multiple architectures thus enabling simple and effective run-time adaptation even for statically-compiled applications. During consequent compilations the worst performing clones can be eliminated and new added to enable continuous and transparent optimization space exploration and adaptation. Similar framework has been also recently presented in [START_REF] Mars | Scenario based optimization: A framework for statically enabling online optimizations[END_REF].

Our approach is driven by simplicity and practicality. We show that with UNIDAPT framework it is possible to select complex optimizations at run-time without resorting to sophisticated dynamic compilation frameworks. Since 2004, we have extended this approach in multiple research projects. We used it to speed up iterative compilation by several orders of magnitude [START_REF] Fursin | A practical method for quickly evaluating program optimizations[END_REF] using low-overhead program phase detection at run-time; evaluate run-time optimizations for irregular codes [START_REF] Fursin | Practical run-time adaptation with procedure cloning to enable continuous collective compilation[END_REF]; build self-tuning multi-versioning libraries automatically using representative sets of optimizations found off-line and providing fast run-time selection routines based on dataset features and standard machine learning techniques such as decision tree classifiers [START_REF] Luo | Finding representative sets of optimizations for adaptive multiversioning applications[END_REF]; enable transparent statistical continuous collective optimization of computing systems [START_REF] Fursin | Collective optimization[END_REF]. We also started investigating predictive run-time code scheduling for heterogeneous multi-core architecture where function clones are targeted for different ISA together with explicit data management [START_REF] Jimenez | Predictive runtime code scheduling for heterogeneous architectures[END_REF].

Since 2006, we are gradually implementing UNIDAPT framework presented in Figure 11 in GCC. During Google Summer of Code'09 program [START_REF]Google Summer of Code'2009 projects to extend CCC, GCC with ICI and UNIDAPT frameworks[END_REF] we are extending GCC to generate multiple function clones on the fly using ICI, apply combinations of fine-grain optimizations to the generated clones, provide program instrumentation to call program behavior monitoring and adaptation routines (and explicit memory transfer routines in case of code generation for heterogeneous GPGPU-like architectures [START_REF] Jimenez | Predictive runtime code scheduling for heterogeneous architectures[END_REF]), provide transparent linking with external libraries (to enable monitoring of hardware counters or machine learning libraries to associate program behavior with optimized clones, for example) and add decision tree statements to select appropriate clones at run-time according to dynamic program features.

UNIDAPT framework combined with cTuning infrastructure opens up many research opportunities. We are extending it to improve dataset, program behavior and architecture characterization to better predict optimizations; provide run-time architecture reconfiguration to improve both execution time and power consumption using program phases based on [START_REF] Fursin | A practical method for quickly evaluating program optimizations[END_REF]; enable split-compilation, i.e. finding a balance between static and dynamic optimizations using predictive modeling; improve dynamic parallelization, data partitioning, caching, and scheduling for heterogeneous multi-core architectures; enable migration of an optimized code in virtual environments when architecture may change at run-time; provide fault-tolerance mechanisms by adding clones compiled with soft-error correction mechanisms,for example.

Finally, we started combining cTuning/MILEPOST technology, UNIDAPT framework and a Hybrid Multi-core Parallel Programming Environment (HMPP) [START_REF] Hmpp | A Hybrid Multi-core Parallel Programming Environment[END_REF] to enable adaptive practical profile-driven optimization and parallelization for the current and future hybrid heterogeneous CPU/GPU-like architectures based on dynamic collective optimization, dynamic data partitioning and predictive scheduling, empirical iterative compilation, statistical analysis, machine learning and decision trees together with program and dataset features [START_REF] Fursin | Collective optimization[END_REF][START_REF] Luo | Finding representative sets of optimizations for adaptive multiversioning applications[END_REF][START_REF] Jimenez | Predictive runtime code scheduling for heterogeneous architectures[END_REF][START_REF] Georgios Tournavitis | Towards a holistic approach to auto-parallelization: Integrating profile-driven parallelism detection and machine-learning based mapping[END_REF][START_REF] Fursin | Milepost gcc: machine learning based research compiler[END_REF][START_REF] Long | A cost-aware parallel workload allocation approach based on machine learning techniques[END_REF][START_REF] Fursin | A practical method for quickly evaluating program optimizations[END_REF].

More information about collaborative UNIDAPT R&D is available at [START_REF]Universal adaptation framework to enable dynamic optimization and adaptation for statically-compiled programs[END_REF].

5 Usage Scenarios

Manual sharing of optimization cases

Collective tuning infrastructure provides multiple ways to optimize computing systems and opens up many research opportunities.

In this section we will present several common usage scenarios. The first and the simplest scenario is manual sharing and reuse of optimization cases using an online web form at [START_REF]cTuning optimization repository (Collective Optimization Database[END_REF]. If a user finds some optimization configuration such as a combination of compiler flags, order of optimization passes, parameters of fine-grain transformations, architecture configuration, etc that improves some characteristics of a given program such as execution time, code size, power consumption, rate of soft errors, etc over default compiler optimization level and default architecture configuration with a given dataset, such optimization case can be submitted to Collective Optimization Database to make the community aware of it.

If an optimized program and a dataset are well-known from standard benchmarks such as SPEC, EEMBC, MiBench/cBench/MiDataSets or from open-source projects, they can be simply referenced by their name, benchmark suite and a version. If a program is less known in the community, have open sources and can be distributed without any limitations, a user may be interested to share it with the community together with multiple datasets within our Collective Benchmark (cBench) at [START_REF]Collective Benchmark: collection of open-source programs and multiple datasets from the community[END_REF] to help other users reproduce and verify optimization cases. This can be particularly important when using COD to reference bugs in compilers, run-time systems, architecture simulators and other components of computing systems. However, if a program/dataset pair is not an open source while a user or a company would still like to share optimization cases for it with the community or get an automatic optimization suggestion based on collective optimization knowledge, such pair can be characterized using static or dynamic features and program reaction to transformations that can capture code and architecture characteristics without revealing the sources to be able to compare programs and datasets indirectly [START_REF] Agakov | Using machine learning to focus iterative optimization[END_REF][START_REF] Fursin | Milepost gcc: machine learning based research compiler[END_REF][START_REF] Cavazos | Rapidly selecting good compiler optimizations using performance counters[END_REF][START_REF] Luo | Finding representative sets of optimizations for adaptive multiversioning applications[END_REF][START_REF] Fursin | Collective optimization[END_REF] (on-going work).

When optimizing computing systems, users can browse COD to find optimization cases for similar architectures, compilers, run-time environments, programs and datasets. Users can reproduce and improve optimization cases, provide notes and rank cases to favor the best performing ones. We plan to automate ranking of optimization cases eventually based on statistical collective optimization concept [START_REF] Fursin | Collective optimization[END_REF].

Collective tuning infrastructure also helps to improve the quality of academic and industrial research on code, compiler and architecture design and optimization by enabling open characterization, unique referencing and fair comparison of the empirical optimization experiments. It is thus intended to address one of the drawbacks of academic research when it is often difficult or impossible to reproduce prior experimental results. We envision that authors will provide experimental data in COD when submitting research papers or after publication to allow verification and comparison with available techniques. Some data can be marked as private and accessible only by reviewers until the paper is published.

When it is not possible to describe optimization cases using current COD structure, a user can record information in temporal extension fields using XML format. If this information is considered important by the community, the COD structure is continuously extended to keep more information in permanent fields. Naturally, we use a top-down approach for COD first providing capabilities to describe global and coarse-grain program optimizations and then gradually adding fields to describe more fine-grain optimizations.

Automatic and systematic optimization space exploration and benchmarking

One of the key features of cTuning infrastructure is the possibility to automate program and architecture optimization exploration using empirical feedback-directed compilation and to share profitable optimization cases with the community in COD [START_REF]cTuning optimization repository (Collective Optimization Database[END_REF]. This enables faster distributed collective optimization of computing systems and reduces release time for new programs, compilers and architectures considerably. CCC framework [START_REF]Continuous Collective Compilation Framework to automate and distribute program optimization, compiler design and architecture tuning[END_REF] is used to automate and distribute multi-objective code optimization to improve execution time and code size among other characteristics for a given architecture using multiple search plugins including exhaustive, random, one off, hill-climbing and other strategies. Figure 12 shows distribution of optimization points in the 2D space of speedups vs code size of susan corners from cBench/MiBench [START_REF]Collective Benchmark: collection of open-source programs and multiple datasets from the community[END_REF] on AMD Athlon64 3700+ architecture with GCC 4.2.2 during automatic program optimization using CCC ccc-run-glob-flags-rnd-uniform plugin after 500 uniform random combinations of more than 100 global compiler flags (each flag has 50% probability to be selected for a given combination of optimizations). Naturally, it can be very time consuming and difficult to find good optimization cases manually in such a non-trivial space and particularly during multi-objective optimizations. Moreover, the search often depends on optimization scenario, i.e. it is critical to produce the fastest for high-performance servers and supercomputers while it can be more important to find a good balance between execution time and code size for embedded systems or adaptive libraries. Hence, we developed several CCC filtering plugins to select optimal optimization cases for a given program, dataset and architecture based on Pareto-like distributions [START_REF] Heydemann | Iterative compilation for two antagonistic criteria: Application to code size and performance[END_REF][START_REF] Hoste | Cole: Compiler optimization level exploration[END_REF] (shown by square dots in Figure 12, for example) before sharing them with the community in COD.

The problem of finding good combinations of optimizations or tuning default compiler optimization levels becomes worse and more time consuming when adding more transformations, optimizing for multiple datasets, architectures and their configurations, adding more optimization objectives such as reducing power consumption and architecture size, improving fault-tolerance, enabling run-time parallelization and adaptation for heterogeneous and reconfigurable multi-core systems and so on. Hence, in practice, it is not uncommon that compiler performs reasonably well only on a limited number of benchmarks and on a small range of a few relatively recent architectures but can underperform considerably on older or emerging architectures.

For example, Figure 13 shows the best speedups achieved on a range of popular and realistic benchmarks including EEMBC, SPEC and cBench over the best GCC optimization level (-O3) after 500 iterations using relatively recent mature Figure 14 shows that it may take around 70 iterations on average before reaching 95% of the speedup available after 500 iterations for cBench/MiBench benchmark and is heavily dependent on programs and architectures. Such a large number of iterations is needed due to continuously increasing number of aggressive optimizations available in the compiler that can both considerably increase or degrade performance or change code size making it more time consuming and non-trivial to find a profitable combination of optimizations in each given case. For example, Table 1 shows such non trivial combinations of optimizations that improve both execution time and code size found after uniform random iterative compilation 1 across all benchmarks and architectures for GCC 4.2.2. One may notice that found combinations of profitable compiler optimizations also often reduce compilation time since some combinations of optimizations require only a minimal optimization level -O1 together with several profitable flags. Some combinations can reduce compilation time by 70% which can be critical when compiling large-scale applications and OS. All this empirical optimization information is now available in COD [START_REF]cTuning optimization repository (Collective Optimization Database[END_REF] for further analysis and improvement of a compiler design.

We expect that optimization spaces will increase dramatically after we provide support for a fine-grain optimization selection and tuning in GCC using ICI [START_REF]Google Summer of Code'2009 projects to extend CCC, GCC with ICI and UNIDAPT frameworks[END_REF]. In such situation, we hope that cTuning technology will considerably simplify 1 After empirical iterative compilation with random uniform distribution we obtain profitable combinations of optimizations that may consist of 50 flags on average. However, in practice, only several of these flags influence performance or code size. Hence, we use CCC ccc-run-glob-flags-one-off-rnd plugin to prune found combinations and leave only influential optimizations to improve performance analysis and optimization predictions. and automate the exploration of large optimization spaces with "one button" approach when a user just controls and balances several optimization criteria.

MILEPOST GCC and optimization prediction web services based on machine learning

Default optimization levels in compilers are normally aimed to deliver good average performance across several benchmarks and architectures relatively quickly. However, it may not be good enough or even acceptable for many applications including performance critical programs such as real-time video/audio processing systems, for example. That is clearly demonstrated in Figure 13 where we show the improvements in execution time for multiple popular programs and several architectures of nearly 3 times over the best default optimization level of GCC using random feedback-directed compilation after 500 iterations.

In [START_REF] Fursin | Milepost gcc: machine learning based research compiler[END_REF] we introduced our machine learning based research compiler (MILEPOST GCC) and integrated it with the cTuning infrastructure during the MILEPOST project [START_REF]EU Milepost project (MachIne Learning for Embedded PrOgramS opTimization[END_REF] to address the above problem by substituting default optimization levels of GCC with a predictive optimization heuristic plugin that suggests good optimizations for a given program and a given architecture.

Such framework functions in two distinct phases, in accordance with typical machine learning practice: training and deployment as shown in Figure 15.

During the training phase we gather information about the structure of programs (static program features) and record how they behave when compiled under different optimization settings (execution time or other dynamic program features such as hardware counters, for example) using CCC framework. This information is recorded in COD and used to correlate program features with optimizations, building a machine learning model that predicts a good combination of optimizations.

In order to train a useful model a large number of compilations and executions as training examples are needed. These training examples are now continuously gathered from multiple users in COD together with program features extracted by MILEPOST GCC.

Once sufficient training data is gathered, different machine learning models are created based on (probabilistic and decision trees approaches among others) [START_REF] Fursin | Milepost gcc: machine learning based research compiler[END_REF][START_REF] Agakov | Using machine learning to focus iterative optimization[END_REF][START_REF] Cavazos | Rapidly selecting good compiler optimizations using performance counters[END_REF], for example. We provided such models trained for a given architecture as multiple architecture-dependent optimization prediction plugins for MILEPOST GCC. When encountering a new program, MILEPOST GCC extracts program features and passes them to the ML plugin which determines which optimizations to apply.

When more optimization data is available (through collective optimization [START_REF] Fursin | Collective optimization[END_REF], for example) or when some new transformations are added to a compiler, we need to retrain our models for all architectures and provide new predictive optimization plugins for downloading simplifying and modularizing a compiler itself.

-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 -finline-functions -fno-tree-dce -fno-tree-loop-im -funroll-all-loops -O2 -fno-guess-branch-probability -fprefetch-loop-arrays -finline-functions -fno-tree-ter -O2 -fno-tree-lrs -O2 -fpeephole -fno-peephole2 -fno-regmove -fno-unswitch-loops -O3 -finline-limit=1481 -falign-functions=64 -fno-crossjumping -fno-ivopts -fno-tree-dominator-opts -funroll-loops -O3 -finline-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 1: Some of the profitable combinations of GCC 4.2.2 flags for multiple programs and benchmarks including EEMBC, SPEC and cBench across distinct architectures that improve both execution time and code size.

Naturally, since all filtered static and dynamic optimization data is now continuously gathered in COD, we can also continuously update optimization prediction models for different architectures at cTuning website. Hence, we decided to create a continuously updated online optimization prediction web-service as shown in Figure 16. It is possible to submit a query to this web service as shown in Figure 17 providing information about architecture, environment, compiler, static or dynamic program features and selecting a required machine learning model and an optimization criteria, i.e. improving either execution time or code size or both over best default optimization level of a compiler. At the moment, this web service returns the most profitable combination of global compiler optimizations (flags) to improve a given program. This service can be tested online at [START_REF]Demo/testing of cTuning online optimization prediction web services[END_REF] or using some plugins from CCC framework to automate prediction.

Such optimization prediction web service opens up many optimization and research possibilities: We plan to test it to improve the whole OS optimization (Gentoo-like Linux, for example), improve adaptation of downloadable applications for a given architecture (Android and Moblin mobile systems, cloud computing and virtual environments, for example), just-in-time optimizations for heterogeneous reconfigurable architectures based on program features and run-time behavior among others. Of course, we need to minimize Internet traffic and queries. Hence, we will need to develop an adaptive local optimization proxy to keep associations between local program features and optimizations for a given architecture while occasionally updating them using global cTuning web services. We leave it for the future work.

As a practical example of the usage of our service, we trained our prediction model for an ARC725D reconfigurable processor using MILEPOST GCC and cBench with 500 iterations and 50% probability of selecting each compiler flag for an individual combination of optimizations at each iteration. Figure 18 compares the speedups achieved after training (our execution time upper bound) and after one-shot optimization prediction (as described in detail in [START_REF] Agakov | Using machine learning to focus iterative optimization[END_REF]).It demonstrates that except a few pathological cases we can automatically improve original production ARC GCC by around 11% on average using cTuning infrastructure.

Conclusions and Future Work

In this paper we presented our long-term collective tuning initiative to automate, distribute, simplify and systematize program optimization, compiler design and architecture tuning using empirical, statistical and machine learning techniques. It is based on sharing of empirical optimization experience from multiple users in the Collective Optimization Database, using common collaborative R&D tools and plugin-enabled production quality compilers with open APIs and providing web services to predict profitable optimizations based on program features.

We believe that cTuning technology opens up many research, development and optimization opportunities. It can already help to speed up existing underperforming computing systems ranging from small embedded architectures to high-performance servers automatically. It can be used for a more realistic statistical performance analysis and benchmarking of computing systems. It can enable statically-compiled self-tuning adaptive binaries and libraries. Moreover, we believe that cTuning initiative can improve the quality and reproducibility of academic and industrial IT research. Hence, we decided to move all our developments to public domain [START_REF]Collective Tuning Center: automating and systematizing the design and optimization of computing systems[END_REF][START_REF]cTuning community mailing lists[END_REF] to enable collaborative community-based developments and boost research. We hope that using common cTuning tools and optimization repository can help to validate research ideas and move them back to the community much faster. We promote top-down optimization approach starting from global and coarse-grain optimizations and gradually supporting more fine-grain optimizations to avoid solving local optimization problems without understanding the global optimization problem first. Within Google Summer of Code'2009 program [START_REF]Google Summer of Code'2009 projects to extend CCC, GCC with ICI and UNIDAPT frameworks[END_REF], we plan to enable automatic and transparent collective program optimization and run-time adaptation based on [START_REF] Fursin | Collective optimization[END_REF] providing support for fine grain program optimizations and reordering, generic function cloning and program instrumentation in GCC using ICI. We will also need to provide formal validation of code correctness during transparent collective optimization. We plan to combine CCC framework with architectural simulators to enable systematic software/hardware co-optimization. We are also extending UNIDAPT framework to improve automatic profile-driven statistical parallelization and scheduling for heterogeneous multicore architectures [START_REF] Jimenez | Predictive runtime code scheduling for heterogeneous architectures[END_REF][START_REF] Luo | Finding representative sets of optimizations for adaptive multiversioning applications[END_REF][START_REF] Georgios Tournavitis | Towards a holistic approach to auto-parallelization: Integrating profile-driven parallelism detection and machine-learning based mapping[END_REF][START_REF] Long | A cost-aware parallel workload allocation approach based on machine learning techniques[END_REF] using run-time monitoring of data dependencies and automatic data partitioning and scheduling based on static and dynamic program/dataset features combined with machine learning and statistical techniques.

We are interested to validate our approach in realistic environments and help better utilize available computing systems by improving whole OS optimizations, adapting mobile applications for Android and Moblin on the fly, optimizing programs for grid and cloud computing or virtual environments, etc. Finally, we plan to provide academic research plugins and online services for optimization data analysis and visualization.

To some extent, cTuning concept is similar to biological self-tuning environments since all available programs and architectures can be optimized slightly differently continuously favoring the most profitable optimizations and designs over time. Hence, we would like to use cTuning knowledge to start investigating completely new programming paradigms and architectural designs to enable development of the future self-tuning and self-organizing computing systems.

Acknowledgments

cTuning development has been partially supported by the MILEPOST project [START_REF]EU Milepost project (MachIne Learning for Embedded PrOgramS opTimization[END_REF], HiPEAC network of excellence [START_REF]European Network of Excellence on High-Performance Embedded Architecture and Compilation (HiPEAC)[END_REF] and Google Summer of Code'2009 program [START_REF]Google Summer of Code'2009 projects to extend CCC, GCC with ICI and UNIDAPT frameworks[END_REF]. I would like to thank Olivier Temam for interesting discussions about Collective Optimization concept and Michael O'Boyle for machine learning discussions; Zbigniew Chamski for his help with the development of the new ICI; Mircea Namolaru for the development of the static program feature extractor for GCC with ICI; Erven Rohou for his help with cBench developments; Yang Chen, Liang Peng, Yuanjie Huang, Chengyong Wu CCC framework plugins and tools to query this service:

• web-service-cod -plugin to send a text query to the web service and return a string of optimization flags • milepost-gcc -a MILEPOST GCC wrapper that detects three flags -ml, -ml-e, -ml-c, extract static program features, query web service using web-service-cod and substitutes default optimization levels of a compiler with the predicted optimizations. : Speedups achieved when using iterative compilation on ARC with random search strategy (500 iterations; 50% probability to select each optimization;) and when predicting best optimizations using probabilistic ML model based on program features described in [START_REF] Agakov | Using machine learning to focus iterative optimization[END_REF]

Figure 1 :

 1 Figure 1: Collective tuning infrastructure to enable systematic collection, sharing and reuse of optimization knowledge from the community. It automates optimization of computing systems by leveraging the optimization experience from multiple users.

Figure 2 :

 2 Figure 2: (a) original centralized design of COD with large communication overheads (b) decentralized design of COD with local filters to prune optimization information and minimize communication costs.

Figure 3 :

 3 Figure 3: Collective Optimization Database structure (tables) to describe optimization cases and minimize database size: common informative part and shared or private part with optimization cases.

High-level optimizationFigure 6 :

 6 Figure 6: CCC framework enables systematic, automatic and distributed program optimization, compiler design and architecture tuning with multiple optimization strategies as well as collection of optimization and profiling statistics from multiple users in COD for further analysis and reuse.

#

  Record compiler passes (through ICI) export CCC ICI PASSES RECORD=1 #Substitute original GCC pass manager and allow optimization pass selection and reordering (through ICI) export CCC ICI PASSES USE=1 #Extract program static features when using MILEPOST GCC export CCC ICI FEATURES STATIC EXTRACT=1 #Specify after which optimization pass to extract static features export ICI PROG FEAT PASS=fre #Profile application using hardware counters and PAPI library export CCC HC PAPI USE=PAPI TOT INS,PAPI FP INS,PAPI BR INS,PAPI L1 DCM,PAPI L2 DCM,PAPI TLB DM,PAPI L1 LDM #Profile application using gprof export CCC GPROF=1 #Profile application using oprof export CCC OPROF=1 export CCC OPROF PARAM="-event=CPU CLK UNHALTED:6000" #Repeat program execution a number of times with the same dataset to detect and remove the performance measurement noise validate stability of execution time statistically export CCC RUNS=3

Figure 7 :

 7 Figure 7: Some environment variables to control ccc-comp and ccc-run tools from CCC framework

Figure 8 :

 8 Figure 8: Information packets produced by ccc-comp and ccc-run tools from CCC framework that are recorded locally or sent to COD

  Feature name: Type of contents: Purpose compiler flags array of strings (char **) Names of all known command-line options (flags) of a compiler. Individual option names are stored without the leading dash. compiler params array of strings (char **) Names of all known compiler parameters. function name string (char) Name of the function currently being compiled. function decl filename string (char) Name of the file in which the function currently being compiled was declared. Returns the filename corresponding to the most recent declaration. function decl line integer (int) Line number at which the function currently being compiled was declared. In conjuction with feature "function decl filename" gives the location of the most recent declaration of the current function. function filename string (char) Name of the file in which the function currently being compiled was defined. function start line integer (int) Line number at which the definition of the current function effectively starts. Corresponds to the first line of the body of the current function. function end line integer (int) Line number at which the definition of the current function effectively ends. Corresponds to the last line of the body of the current function. first pass string (char) Human-readable name of the first pass of a compiler.

Figure 11 :

 11 Figure 11: Universal run-time adaptation framework (UNIDAPT) based on static multiversioning and dynamic selection routines. A representative set of multiple function versions [62] optimized or compiled for different run-time optimization scenarios is used in such adaptive binaries and libraries. An optimized decision tree or rule induction techniques should be able to map clones to different run-time contexts/scenarios during program or library execution.

d ij k s tr a p a tr ic ia b lo w fi s h _ d b lo w fi s h _ e ri jn d a e l_ d ri jn d a e l_Figure 14 :

 14 Figure 14: Number of iterations needed to obtain 95% of the available speedup across cBench programs using iterative compilation with uniform random distribution (500 iterations) on 4 distinct architectures.

Figure 15 :

 15 Figure 15: Original MILEPOST framework connected with cTuning infrastructure to substitute default compiler optimization heuristic with an optimization prediction plugin based on machine learning. It includes MILEPOST GCC with Interactive Compilation Interface (ICI) and program features extractor, and CCC Framework to train ML model and share optimization data in COD.

pFigure 16 :

 16 Figure16: Using cTuning optimization prediction web services to substitute default compiler optimization levels and predict good optimizations for a given program and a given architecture on the fly based on its structure or or dynamic behavior (program static and dynamic features) and continuously retrained predictive models based on collective optimization concept[START_REF] Fursin | Collective optimization[END_REF].

Figure 17 :d ij k s tr a p a tr ic ia b lo w fi s h _ d b lo w fi s h _ e ri jn d a e l_ d ri jn d a e l_

 17 Figure 17: cTuning optimization prediction web service: URL, message format and tools.

  -going long term initiative, the COD structure may evolve over time. Hence, we provide current COD version number in the INFORMATION table to ensure compatibility between all cTuning tools and plugins that access COD.

	Field	Description:
	COMPILE ID	Unique UUID-based identifier to enable global referencing of a given
		optimization case
	PLATFORM ID	Unique platform identifier
	ENVIRONMENT ID	Unique software environment identifier
	COMPILER ID	Unique compiler identifier
	PROGRAM ID	Unique program identifier
	PLATFORM FEATURE ID	Reference to the table with platform features describing platform
		specific features for architectural design space exploration (it can include
		architecture specific flags such as -msse2 or cache parameters, etc)
	OPT ID	Reference to the table with global optimization flags
	COMPILE TIME	Overall compilation time
	BIN SIZE	Binary size
	OBJ MD5CRC	MD5-based CRC of the object file to detect whether optimizations changed
		the code or not
	ICI PASSES USE	set to 1 if compiler with Interactive Compilation Interface (ICI) has been
		used to select individual passes and their orders on a function level
	ICI FEATURES STATIC EXTRACT set to 1 if static program features has been extracted using ICI and
		MILEPOST GCC [47]
	OPT FINE	XML description of fine-grain optimizations selected using ICI (on-going
		work)
	OPT PAR STATIC	XML description of static program parallelization (on-going work)
	NOTES	User notes about this optimization case (can describe a bug or unusual
		compiler behavior for further analysis for example)
	Field	Description:
	RUN ID	Unique UUID-based identifier to enable global referencing of a given
		optimization case
	RUN ID ASSOCIATE	ID of the associated run with baseline optimization for further analysis
	COMPILE ID	Associated compilation identifier
	COMPILER ID	Duplicate compiler identifier from the compilation table to speed up SQL
		queries
	PROGRAM ID	Duplicate program identifier from the compilation table to speed up SQL
		queries
	BIN SIZE	Duplicate binary size from the compilation table to speed up SQL queries
	PLATFORM ID	Unique platform identifier
	ENVIRONMENT ID	Unique software environment identifier
	RE ID	Unique runtime environment identifier
	DATASET ID	Unique dataset identifier
	OUTPUT CORRECT	Set to 1 if the program output is the same as the reference one (supported
		when using Collective Benchmark or program specially prepared using CCC
		framework). It is important to add formal validation methods in the future
		particularly for transparent collective optimization [50].
	RUN TIME	Absolute execution time in seconds (or relative number if absolute time can
		not be disclosed by some companies or when using some benchmarks)
	RUN TIME USER	User execution time
	RUN TIME SYS	System execution time
	RUN TIME BACKGROUND Information about background processes to be able to analyze the
		interference between multiple running applications and enable better
		adaptation and scheduling when sharing resources on uni-core or multi-core
		systems [56]
	RUN PG	Function-level profile information (using gprof or oprofile):	function
		name=time spent in this function, ...
	RUN HC	Dynamic program features (using hardware counters):	hardware
		counter=value, ...
	RUN POWER	Power consumption (on-going work)
	RUN ENERGY	Energy during overall program execution (on-going work)
	PAR DYNAMIC	Information about dynamic dependencies to enable dynamic parallelization
		(on-going work)
	PROCESSOR NUM	Core number assigned to the executed process
	RANK	Integer number describing ranking (profitability) of the optimization.
		Optimization case can be ranked manually or automatically based on
		statistical collective optimization [50]
	NOTES	User notes about this optimization case
	Figure 5: Summary of current fields of the COD table to describe program executions.

Figure 4: Summary of current fields of the COD table describing compilation process.

on

  PASSES=all optimizations,strip predict hints,addressables,copyrename,cunrolli,ccp,forwprop,cdce,alias,retslot,phiprop,fre,copyprop,mergephi,... PASSES=all optimizations,strip predict hints,addressables,copyrename,cunrolli,ccp,forwprop,cdce,alias,retslot,phiprop,fre,copyprop,mergephi,... ... Information packet with program features (local filename: prog feat):

	Main compilation information packet (local filename: comp):
	COMPILE ID=19293849477085514
	PLATFORM ID=2111574609159278179
	ENVIRONMENT ID=2781195477254972989
	COMPILER ID=129504539516446542
	PROGRAM ID=1487849553352134
	DATE=2009-06-04
	TIME=14:06:47
	OPT FLAGS=-O3
	OPT FLAGS PLATFORM=-msse2
	COMPILE TIME=69.000000
	BIN SIZE=48870
	OBJ MD5CRC=b15359251b3c185dfa180e0e1ad16228
	ICI FEATURES STATIC EXTRACT=1
	NOTES=baseline compilation
	Information packet with ICI optimization passes (local filename: comp passes):
	COMPILE ID=19293849477085514
	COMPILER ID=129504539516446542
	FUNCTION NAME=corner draw
	COMPILE ID=19293849477085514
	COMPILER ID=129504539516446542
	FUNCTION NAME=edge draw
	COMPILE ID=19293849477085514
	FUNCTION NAME=corner draw
	PASS=fre
	STATIC FEATURE VECTOR= ft1=9, ft2=4, ft3=2, ft4=0, ft5=5, ft6=2, ft7=0, ft8=3, ft9=1, ft10=1, ft11=1, ft12=0, ft13=5, ft14=2, ...
	COMPILE ID=19293849477085514
	FUNCTION NAME=edge draw
	PASS=fre
	STATIC FEATURE VECTOR= ft1=14, ft2=6, ft3=5, ft4=0, ft5=7, ft6=5, ft7=0, ft8=3, ft9=3, ft10=3, ft11=2, ft12=0, ft13=11, ft14=1, ...
	...
	Execution information packet (local filename: run):
	RUN ID=22712323769921139
	RUN ID ASSOCIATE=22712323769921139
	COMPILE ID=8098633667852535
	COMPILER ID=331350613878705696
	PLATFORM ID=2111574609159278179
	ENVIRONMENT ID=2781195477254972989
	PROGRAM ID=1487849553352134
	DATE=2009-06-04
	TIME=14:35:26
	RUN COMMAND LINE=1) ../../automotive susan data/1.pgm output large.corners.pgm -c ftmp out
	OUTPUT CORRECT=1
	RUN TIME=16.355512
	RUN TIME1=0.000000
	RUN TIME USER=13.822898
	RUN TIME SYS=2.532614
	RUN PG={susan corners=12.27,782,0.0156905371}
	NOTES=baseline compilation

compilation for different architectures (heterogeneous or reconfigurable processors with different ISA such as GPGPU, CELL, etc or the same ISA with extensions such as 3dnow, SSE, etc or virtual environments) • optimizations for different program phases or different run-time environment behavior Original hot function

• optimizations/

  Variation of speedups and size of the binary for susan corners using GCC 4.2.2 on AMD Athlon64 3700+ during automatic iterative feedback-directed compilation performed by CCC framework over best available optimization level (-O3) and different profitable optimization cases detected by CCC filter plugins depending on optimization scenarios (similar to Pareto distribution).

	1.6 1.6			CCC filtered profitable optimization cases
	1.4 1.4
	1.2 1.2
	speedup speedup
	1 1
	0.8 0.8
	0.6 0.6
	30000 30000	40000 40000	50000 50000	60000 60000	70000 70000	80000 80000	90000 90000
				binary size binary size
	Figure 12:

  It clearly demonstrates that it is possible to considerably outperform even mature GCC with the highest default optimization level using random iterative search. Moreover, it also shows that achievable speedups are architecture dependent and vary considerably for each program ranging from a few percent to nearly two times improvements.

		2.4 2.4
		2.2 2.2
		2 2
	Speedup Speedup	1.6 1.8 1.6 1.8
		1.4 1.4
		1.2 1.2
		1 1
		utomotive_a2time01 automotive_a2time01	automotive_aifftr01 automotive_aifftr01	automotive_aifirf01 automotive_aifirf01	automotive_aiifft01 automotive_aiifft01	utomotive_basefp01 automotive_basefp01	utomotive_bitmnp01 automotive_bitmnp01	utomotive_canrdr01 automotive_canrdr01	automotive_iirflt01 automotive_iirflt01	utomotive_pntrch01 automotive_pntrch01	tomotive_puwmod01 automotive_puwmod01	utomotive_rspeed01 automotive_rspeed01	automotive_tblook01 automotive_tblook01	automotive_ttsprk01 automotive_ttsprk01	consumer_aes consumer_aes	consumer_cjpegv2 consumer_cjpegv2	consumer_djpegv2 consumer_djpegv2	consumer_huffde consumer_huffde	onsumer_mp2decod consumer_mp2decod	sumer_mp2decodf32 consumer_mp2decodf32	sumer_mp2decodfix consumer_mp2decodfix	consumer_mp2enf32 consumer_mp2enf32	consumer_mp2enfix consumer_mp2enfix	mer_mp3playerfixed consumer_mp3playerfixed	onsumer_rgbcmykv2 consumer_rgbcmykv2	consumer_rgbhpgv2 consumer_rgbhpgv2	consumer_rgbyiqv2 consumer_rgbyiqv2	working_ip_pktcheck networking_ip_pktcheck	networking_ospfv2 networking_ospfv2	working_routelookup networking_routelookup	networking_tcp networking_tcp	office_bezier01fixed office_bezier01fixed	office_bezier01float office_bezier01float	office_text01 office_text01	telecom_autcor00 telecom_autcor00	telecom_conven00 telecom_conven00	telecom_fbital00 telecom_fbital00
															AMD Athlon 64		Intel Xeon
													EEMBC v1.0 and v2.0
		1.9 1.9
		1.8 1.8
		1.7 1.7
	speedup speedup	1.3 1.4 1.5 1.6 1.3 1.4 1.5 1.6
		1.2 1.2
		1.1 1.1
		1 1
		motive_bitcount automotive_bitcount	utomotive_qsort automotive_qsort	omotive_susan_c automotive_susan_c	motive_susan_e automotive_susan_e	omotive_susan_s automotive_susan_s	onsumer_jpeg_c consumer_jpeg_c	onsumer_jpeg_d consumer_jpeg_d	network_patricia network_patricia	curity_rijndael_d security_rijndael_d	curity_rijndael_e security_rijndael_e	elecom_adpcm_c telecom_adpcm_c	lecom_adpcm_d telecom_adpcm_d	177.mesa 177.mesa	301.apsi 301.apsi	187.facerec 187.facerec	173.applu 173.applu	172.mgrid 172.mgrid	164.gzip 164.gzip	300.twolf 300.twolf	186.crafty 186.crafty	453.povray 453.povray	444.namd 444.namd	447.dealII 447.dealII	437.leslie3d 437.leslie3d	456.hmmer 456.hmmer	462.libquantum 462.libquantum	464.h264ref 464.h264ref	107.mgrid 107.mgrid	141.apsi 141.apsi	145.fpppp 145.fpppp
														AMD Athlon 64		Intel Xeon
											cBench v1.0, SPEC95,2000,2006
	Figure 13: Evaluation of mature GCC 4.2.2 using iterative compilation with uniform random distribution (500
	iterations) on 2 distinct architectures.
	GCC 4.2.2 (1.5 years old) and 2 mature architectures: nearly 4 years old AMD Ahtlon64 3700+ and 2 years old quad-core
	Intel Xeon 2800MHz.

MILEPOST GCC (with ICI) IC Plugins Recording pass sequences Extracting static program features Program 1 Program N … Training New program

			CCC
			Continuous Collective
			Compilation Framework
			Drivers for
			iterative
			compilation
			and model
			training
	Deployment	Extracting static program features Selecting "good" passes	MILEPOST GCC Predicting "good" passes to improve exec.time, code size and comp. time

  for cTools discussions, feedback and help with UNIDAPT framework extensions. I would also like to thank Abdul Wahid Memon and Menjato Rakototsimba for thorough testing of the Continuous Collective Compilation Framework and Collective Optimization Database. Finally, I would like to thank cTuning and GCC communities[START_REF]cTuning community mailing lists[END_REF] 17] for very useful feedback, discussions and help with software developments.Web service URL:http://ctuning.org/wiki/index.php/Special:CDatabase?request=predict_opt

	Query:
	PLATFORM_ID =	CCC framework UUID of a user platform (architecture)
	ENVIRONMENT_ID =	CCC framework UUID of a user environment
	COMPILER_ID =	CCC framework UUID of a user compiler
	ST_PROG_FEAT =	static features of a given program
	or
	DYN_PROG_FEAT =	dynamic features of a given program (hardware counters)
	ML_MODEL=	0 -nearest neighbour classifier (selecting optimization cases
		from the most similar program
		based on Euclidean distance of features.
		Other ML prediction plugins are in development.
	PREDICTION_MODE=	predict profitable optimization flags to improve code
		over the best default optimization level:
		1 -improve both execution time and code size
		2 -only execution time
		3 -only code size
	Return:
	Most profitable combination of optimizations (currently global flags)