Lianjie Luo
email: luolianjie@ict.ac.cn

Yang Chen
email: chenyang@ict.ac.cn

Chengyong Wu

Shun Long
email: tlongshun@jnu.edu.cn

Grigori Fursin
email: grigori.fursin@inria.fr

Iterative compilation is a widely adopted technique to optimize programs for different constraints such as performance, code size and power consumption in rapidly evolving hardware and software environments. However, in case of statically compiled programs, it is often restricted to optimizations for a specific dataset and may not be applicable to applications that exhibit different run-time behavior across program phases, multiple datasets or when executed in heterogeneous, reconfigurable and virtual environments. Several frameworks have been recently introduced to tackle these problems and enable run-time optimization and adaptation for statically compiled programs based on static function multiversioning and monitoring of online program behavior. In this article, we present a novel technique to select a minimal set of representative optimization variants (function versions) for such frameworks while avoiding performance loss across available datasets and code-size explosion. We developed a novel mapping mechanism using popular decision tree or rule induction based machine learning techniques to rapidly select best code versions at run-time based on dataset features and minimize selection overhead. These techniques enable creation of self-tuning static binaries or libraries adaptable to changing behavior and environments at run-time using staged compilation that do not require complex recompilation frameworks while effectively outperforming traditional singleversion non-adaptable code.

Finding representative sets of optimizations for adaptive multiversioning applications 1 Introduction

The past two decades have seen a rapid evolution of architectural designs and growth of their complexity. Modern compilers employ many advanced optimizations to achieve better performance on such architectures. However, they often fail due to simplified hardware models used for static analysis and a lack of runtime information. Iterative compilation became a widely adopted technique to optimize programs for different constraints such as performance and code size without a priori knowledge of the underlying hardware [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] Fursin | Evaluating iterative compilation[END_REF][START_REF] Triantafyllis | Compiler optimization-space exploration[END_REF][START_REF] Cooper | ACME: adaptive compilation made efficient[END_REF][START_REF] Kulkarni | Finding effective optimization phase sequences[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][START_REF]ESTO: Expert System for Tuning Optimizations[END_REF]. However, it is often used to optimize programs for a specific dataset which may not be practical as shown in [START_REF] Fursin | Midatasets: Creating the conditions for a more realistic evaluation of iterative optimization[END_REF] where an influence of multiple datasets on iterative compilation has been studied using a number of programs from MiBench benchmark suite.

Hybrid static/dynamic optimization approaches have been introduced to tackle those problems and allow compilers make better optimization decisions at run-time. Search-based methods have been adopted in several well-known library generators such as ATLAS [START_REF] Whaley | Automatically tuned linear algebra software[END_REF], FFTW [START_REF] Matteo | FFTW: An adaptive software architecture for the FFT[END_REF] and SPIRAL [START_REF] Singer | Learning to predict performance from formula modeling and training data[END_REF] to identify different optimization variants for different inputs that fit the computer architecture best at run-time. Some more general approaches have also been introduced in [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] to make static programs adaptable at run-time by generating different code versions statically or dynamically and selecting them based on a given context, performance prediction or according to the changing run-time behavior. However, most of these frameworks are limited to only a few optimizations and do not have mechanisms to select a representative set of optimization variants. [START_REF] Fursin | A practical method for quickly evaluating program optimizations[END_REF] presents a framework which creates adaptive binaries and statically enables run-time adaptation based on function multiversioning, iterative compilation and low-overhead hardware counters monitoring routines. It searches for complex combinations of optimizations in an off-line iterative manner. However, it is based on a reactive model and provides no pruning mechanism in order to avoid code size explosion. This paper presents a novel approach to generate only a limited number of representative optimization variants across all datasets without performance loss or code-size explosion. It is based on finding good optimizations for hot program or library functions with different datasets using traditional off-line random iterative compilation in large optimization spaces and then iteratively pruning those variants while controlling overall performance and code size. When representative set of optimizations is found, we utilize several standard classification algorithms (decision trees or rule induction) to correlate some characteristics of the datasets with the best optimized function version. The learned decision trees or rules are then converted into executable code for runtime version selection. We evaluated our techniques using Open64 research compiler and plan to implement this framework inside GCC. However, hand-written optimization versions, libraries or versions generated using other optimization techniques or even compiled for different ISA (in virtual or heterogeneous environments) can be easily plugged into our framework.

The paper is organized as follows. Section 2 provides a motivation example for multiversioning and outlines the proposed framework. Section 3 describes a heuristic to find representative set of optimization versions while maximizing performance and minimizing code size. Section 4 evaluates different machine learning models to map some dataset characteristics to the selected versions to maximize overall performance and minimize overheads. Section 5 summarizes related work in this area, before concluding remarks and future work in Section 6.

2 Static Multiversioning Framework to Enable Run-time Adaptation

Motivation

Some prior works show that different optimization combinations are needed for kernels or programs with multiple datasets [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] Fursin | Midatasets: Creating the conditions for a more realistic evaluation of iterative optimization[END_REF]. We decided to confirm these findings using FFT benchmark with 15 different input sizes on a recent architecture such as dual-core AMD Opteron 2.6GHz with RedHat Linux AS4. We use Open64 4.0 compiler with the Interactive Compilation Interface [START_REF]Open64 ICI: Interactive Compilation Interface for Open64 research compiler[END_REF] to apply combinations of fine-grain transformations such as loop tiling and unrolling with random parameters to the most time consuming loops in the kernel. We found 8 best optimization variants across those datasets. Figure 1 shows the speedups over -O3 optimization level of Open64 for these optimization variants, and how they vary across different datasets. It shows that the relative performance of a version can vary significantly on different input data, and no one single version can outperform all the other versions across all datasets. This motivates us to develop an automatic adaptive multiversioning technique which can select proper version based on a given runtime context. Moreover, having all 8 versions may not be practical due to considerable code-size increase and hence pruning technique is needed to select a small representative set of such optimizations, when given thresholds for tolerable code size increase and performance loss across all datasets.

Framework

The aim of our work can be formulated as a multi-objective problem as follows: given a set of semantically equivalent but differently optimized versions of a given program, kernel or library function (or compiled for different architecture in heterogeneous and virtual environments) for multiple input datasets, find the smallest subset of versions while maximizing overall performance (or reduce power consumption for example) and minimizing code size. When such set is found, use machine learning to build the mapping between dataset features (or run-time context such as hardware counters) and all versions in this representative set while minimizing the decision tree and hence run-time overhead using machine learning. The framework implementing this approach is presented in Figure 2. It takes three steps to achieve these goals. First, we evaluate a large number of combinations of optimizations for a given program with multiple datasets using traditional iterative compilation techniques. This step can be considerably accelerated using techniques such as collective optimization [START_REF] Fursin | Collective optimization[END_REF][START_REF]CCC: Continuous Collective Compilation Framework[END_REF]. Then, we use a heuristic presented in Section 3 to select the representative versions. Finally, we

Adaptive Binaries and Libraries

When the representative set of versions for different run-time optimization cases is selected and the mapping function is prepared, we produce the final adaptive binary or library as shown in Figure 3. Such binaries or libraries include runtime routines for dataset/program/environment feature extraction and programs runtime behavior monitoring in order to select appropriate versions to improve performance, reduce power consumption or improve reliability, etc. Though compiled statically, this code is now adaptable to different datasets, run-time program and system behavior or even different heterogeneous, reconfigurable and virtual architectures.

3 Selection of Representative Optimization Versions

Experimental Setup and Iterative Compilation

Iterative compilation is traditionally performed using global compiler flags or source-to-source transformation tools which is not always satisfactory, particularly for function-level optimizations. Interactive Compilation Interface (ICI) has

Step 1:

Step 2:

Step 3:

Program, kernel or library function

Best optimization variants for all datasets

Adaptive Binary or Library

Model to map input features to versions

Representative code versions

Building mapping function between dataset features and representative versions using machine learning

Selecting representative set and controlling performance and code size

Iterative compilation with multiple datasets

Datasets

Fig. 2. Static multiversioning framework to enable run-time optimization and adaptation while pruning number of versions, monitoring overall performance, reducing code size and finding mapping between dataset characteristics and representative versions

been recently introduced [START_REF] Fursin | Milepost gcc: machine learning based research compiler[END_REF][START_REF]Open64 ICI: Interactive Compilation Interface for Open64 research compiler[END_REF][START_REF]GCC ICI: Interactive Compilation Interface[END_REF] to enable fine-grain optimizations in production compilers with the ability to select different combinations, phase orders and parameters of available transformations. We decided to use Open64 4.0 compiler with ICI enabled [START_REF]Open64 ICI: Interactive Compilation Interface for Open64 research compiler[END_REF] since it is a well-known research compiler with multiple aggressive optimizations available. We evaluated the following transformations using hill-climbing search similar to [START_REF] Fursin | Evaluating iterative compilation[END_REF].

- To validate our framework, we selected two widely used kernels: DGEMM from level-3 BLAS [1] library of NetLib, and FFT from UTDSP [START_REF]UTDSP Benchmark Suite[END_REF]. We evaluated 100 different combinations of optimizations on DGEMM and 280 on FFT (this

Extract dataset features

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

¡¢£¤£¥ ¦ § ¡¢¨© ¦ £¤ § ¥ £ § £¡ ¥ ¥ ¦ £ § ¡ ¥ ¡¨¡ © Function Version1 … !"#$"%"&'(')0" %"' 1 2 0"$%)1&% 2 1$ '3" 2 14415)&6 1#')7)8(')1& 9(%"% '1 7)&)7)8" "@"9A')1& ')7" B #15"$ 91&%A7#')1& (&C 91C" D %)

Fig. 3. Adaptive binaries or libraries with a representative set of multiple function versions optimized or compiled for different run-time cases and with the decision tree or rule induction to map them with different run-time contexts

number is program dependent). We randomly generated 1000 distinct datasets for BLAS and 280 for FFT with different input sizes and data values. All experiments are performed on a dual-core AMD Opteron at 2.6GHz, with 64KB L1 cache and 1MB L2 cache for each core, and 16GB memory, running RedHat AS4 (kernel 2.6.9-42).

Heuristic to Select the Representative Set of Optimizations

Given a potentially large number of combinations of optimizations (code versions) for a set of sample inputs, we would like to select only a minimal set of representative ones that obtain best performance on a maximum set of inputs. A heuristic algorithm for this is presented in Figure 4. Depending on the user's optimization priority (overall achieved performance vs maximum number of allowed versions to control code-size explosion), this algorithm tries to prune these versions and leaves only the representative ones that outperform the single version code for as many datasets as possible. To achieve this, it adopts a greedy strategy that is explained in Figure 4. And we plan to use multi-objective Pareto optimization for optimal performance/code size ratio as described in [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] in the future work. Further more, we plan to extend the presented heuristic to take into account the mapping mechanism (described later in this paper) to be sure that all the representative versions can be effectively mapped with the dataset characteristics. Evaluate all versions from C across all datasets from D all for a given program: S = { s 11 , s 21 , …,s X1 , s 12 , s 22 , s X2 , …, s XO } , where s is the speedup obtained over -O3. Calculate s max which is the geometric mean of the best achievable speedups for each dataset from D all . It is used as a reference for achievable performance across all datasets.

2)

Find a code version c i from C with a maximum geometric mean of speedups s Xi across all datasets from D. Note, that if s ij < 1, we set it to 1 to favor those optimizations that perform the best on a maximum number of datasets even if it may have a low performance on some others since we continue the search for optimization variants to obtain speedups across all datasets iteratively in this algorithm. We use geometric mean since speedups distribution is usually unknown.

3) Add c i to the representative set of versions C R and remove it from C.

4)

Calculate s Rmax which is a geometric mean of the best speedups for each dataset from D all using versions from the representative set C R . Remove all the datasets from D where c i (from C R ) achieves the best speedup (or within some predefined threshold which can be a monitoring system routine precision, etc).

5)

If the number of representative versions M < V or 1 -[S Rmax / S max ] > P / 100 (note that it can be a Pareto optimal for two conditions at the same time or some other optimization scenario of a user) then iteratively continue from the step 2.

Fig. 4. Algorithm to find a minimal representative set of versions that minimizes performance loss across all datasets

Using our algorithm in Figure 4 we obtained 3 representative optimization versions for DGEMM and 4 for FFT. Evaluation of overall obtained performance and different overheads for these programs is presented in Sections 4.2 and 4.3 respectively.

Run-time Version Mapping Mechanism

Objective

To be able to statically create adaptive applications and libraries, we need an effective mechanism to select the representative optimization versions at runtime based on dataset characteristics or other run-time context such as dynamic feature vector of performance counters, information about process migration in multi-core heterogeneous architectures and virtual environments. Machine learning [START_REF] Mitchel | Machine Learning[END_REF] has been effectively used to learn and build such mappings automatically. We evaluated some commonly used classification algorithms available in the popular WEKA [START_REF]WEKA 3: The Waikato Environment for Knowledge Analysis[END_REF] machine learning suite that supporting multiple standard techniques such as clustering, classification, and regression.

All these algorithms vary in applicability and complexity depending on the problem encountered. In order to find one suitable for our version mapping mechanism, we decided to evaluate two widely adopted methods with several variants: direct classification (DC) and performance prediction model (PPM). Given a test case of a dataset, DC returns the most similar case from its prior experience (the training set), i.e. the optimization for another dataset most similar to the given one, expecting that the speedup will also be similar. On the contrary, PPM usually uses a probabilistic approach to correlate dataset features with available optimizations and speedups, uses probability distribution to suggest a set of good optimizations for a dataset before selecting the best out of these optimizations. Generally speaking, PPM performs better than DC, but at the extra cost in performance estimation, prediction and comparison. In our case, though the training cost can be tolerated , it is critical to link an optimized run-time decision tree to the adaptive binary or library in order to select appropriate versions online without considerable overhead. Six most commonly used heuristics for DC and PPM are evaluated, among which the best is selected.

It is vitally important for all machine learning techniques to find the suitable characterization of datasets in order to correlate dataset attributes with influential optimizations. It is a challenging task and beyond the scope of this paper. As a first step, we decided to use only the dimensions of input arrays since they are known to influence most of the transformations evaluated in this paper. There are other attributes that we plan to use in the future, such as the values of the entire array. However, it inevitably leads to a larger number of attributes to consider and may result in overfitting, while Li et al [START_REF] Li | A dynamically tuned sorting library[END_REF] suggested that the characteristics of input array elements may not be as important as the distribution of the values of them. Implicit attributes such as pointer type could also describe programs and library functions. However, if they point to an array, it may not be enough to learn from the value of the pointer itself. Therefore, we should consider high-level information about loops and array dimensions. We plan to combine all these characteristics with dynamic attributes such as performance counters, available hardware and software resources, system workload in the extension of this work. We can find or even generate as many features as possible and then automatically find the important ones using standard machine learning techniques such as Principle Component Analysis in order to keep the number of attributes low while maintaining the accuracy of learning and prediction.

Evaluation of Direct Classification vs Performance Prediction Model

Six different learning methods are adopted in DC [START_REF] Witten | Data Mining[END_REF][START_REF]WEKA 3: The Waikato Environment for Knowledge Analysis[END_REF]: We used a representative set of optimizations, a large number of datasets in our experiments, which were carried out in a ten-fold cross validation. We decided to use array dimension as the dataset characterization as mentioned earlier. Error rate is used as the performance evaluation metric for DC, and root relative squared error [START_REF] Witten | Data Mining[END_REF] for PPM which are standard metrics for these algorithms in WEKA.

-SMO -Support
Figure 5 shows that the classification accuracy depends on the given program and a machine learning method. J48 achieves the lowest error rate for DGEMM, while REPTree minimizes it for FFT. It is worth noting that the error rate of most of the classification algorithms have a very high error rate for FFT, more than 40% in most cases. This could be caused by a poor dataset characterization which needs further study in the future.

Six different learning methods are available for PPM:

- Figure 6 demonstrates that M5Rules outperforms all other methods for both DGEMM and FFT. It is interesting to note that the best performing algorithms from DC and PPM are either decision tree or rule based which suggests that these methods suit our mapping objective best. We leave the detailed comparison of different algorithms for the future work.

Performance Evaluation of the Multiversioning Approach Once the best performing mapping algorithm is found, we can evaluate the mapping in a realistic environment by creating an adaptive binary or library linked with the selection function and representative optimization versions (3 versions for DGEMM, 4 for FFT). Then the produced binaries were executed with randomly generated test inputs (990 distinct inputs for DGEMM, 82 for FFT, none of them identical to the training data) on our experiment platform specified in section 3.1. Figure 7 summaries the performance results which include the dynamic version selection time (except for the estimated "ideal" case). The "ideal" numbers in Figure 7 for DGEMM and FFT refers to the estimated average speedup which could be achieved when the predication accuracy of the machine learned model for runtime version selection were 100%. It demonstrates by combining static multiversioning with dynamic version selection from 3 4 representative optimizations based on J48 and REPTree mapping mechanism using simple dataset features we can gain 98% of the available speedup. The introduction of multiple code versions in the binary or library as well as the run-time version selection inevitably results in code growth and run-time overhead. Table 1 presents the number of representative versions found for DGEMM and FFT. It demonstrates that the run-time overhead and the code growth for the version selection can be negligible whilst the overall code growth is not, due to multiversioning. However, depending on the user optimization scenarios, this overhead could be tolerable or reduced during the multi-objective tuning of the performance, representative optimization set and the overall code size. We believe that such an approach can, without a complex error-prone dynamic recompilation framework, automatically create static binaries and libraries which are adaptable to different behavior and environments at run-time. Iterative compilation has been widely used to optimize both kernels and larger programs on a given architecture [START_REF] Bodin | Iterative compilation in a non-linear optimisation space[END_REF][START_REF] Kisuki | Iterative compilation in program optimization[END_REF][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][START_REF] Fursin | Evaluating iterative compilation[END_REF][START_REF] Kulkarni | Finding effective optimization phase sequences[END_REF][START_REF]ESTO: Expert System for Tuning Optimizations[END_REF][START_REF] Cooper | ACME: adaptive compilation made efficient[END_REF][START_REF] Triantafyllis | Compiler optimization-space exploration[END_REF][START_REF] Franke | Probabilistic source-level optimisation of embedded programs[END_REF][START_REF] Fursin | A practical method for quickly evaluating program optimizations[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][START_REF] Fursin | Collective optimization[END_REF] . Various optimization search spaces (composed of various parametric transformations and of different phase orders) are considered in order to minimize the execution time or code size. However it is a very time-consuming process which is unacceptable in many practical scenarios. To accelerate the iterative search process, most of the above works use some heuristics to focus optimizations. Machine learning techniques have been used recently to enable optimization knowledge reuse, predict good optimizations and speedup iterative compilation [START_REF] Monsifrot | A machine learning approach to automatic production of compiler heuristics[END_REF][START_REF] Stephenson | Meta optimization: Improving compiler heuristics with machine learning[END_REF][START_REF] Stephenson | Predicting unroll factors using supervised classification[END_REF][START_REF] Cavazos | Inducing heuristics to decide whether to schedule[END_REF][START_REF] Zhao | A model-based framework: an approach for profit-driven optimization[END_REF][START_REF] Agakov | Using machine learning to focus iterative mization[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], such techniques include genetic programming, supervised learning, decision trees, predictive modeling etc.

Iterative compilation is usually used to optimize program with one dataset which is not be practical. This is demonstrated in [START_REF] Fursin | Midatasets: Creating the conditions for a more realistic evaluation of iterative optimization[END_REF] where the influence of multiple datasets on iterative compilation has been studied using a number of programs from MiBench benchmark. Hybrid static/dynamic approaches have been introduced to tackle such problems. They are used in a well-known library generators such as ATLAS [START_REF] Whaley | Automatically tuned linear algebra software[END_REF], FFTW [START_REF] Matteo | FFTW: An adaptive software architecture for the FFT[END_REF] and SPIRAL [START_REF] Singer | Learning to predict performance from formula modeling and training data[END_REF] to identify different optimization variants for different inputs to improve overall execution time. Some general approaches have also been introduced in [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] to make static programs adaptable to changes in run-time behavior by generating different code versions for different contexts. However, most of these frameworks are limited to simple optimizations or need complex run-time recompilation frameworks. None of them provide techniques to select a representative set of optimization variants.

Another hybrid static/dynamic framework has been introduced in [START_REF] Fursin | A practical method for quickly evaluating program optimizations[END_REF][START_REF] Fursin | Collective optimization[END_REF] to create self-tuning binaries. Run-time adaptation is achieved by first using offline iterative search for arbitrary combinations of available optimizations and then inserting into the static binary multiple versions of hot functions as well as low-overhead hardware counters monitoring routines. None of the above techniques addresses the issue of automatic selection of a minimal representative set of optimizations for kernels or programs with multiple datasets in order to maximize overall performance and minimize code size explosion. The version selection mechanisms should be based on program input characteristics. This paper attempts to address these issues.We believe that this is an important practical step forward toward automatic creation of static self-tuning programs or libraries adaptable to different run-time behavior and environments automatically and without the help of a complex dynamic recompilation frameworks. This paper presented a static multiversioning approach with dynamic version selection which enables run-time optimizations based on iterative compilation, dataset characteristics and machine learning. It is capable of generating static binaries adaptive to different environments at run-time. We demonstrate that it is possible to effectively prune a large number of versions optimized for different datasets in order to build a representative set across available datasets. This is achieved without considerable performance loss nor code size explosion, which makes this approach practical. We also demonstrate how to use popular decision tree and rule induction classification algorithms to build an effective and lowoverhead run-time mapping mechanism in order to correlate different datasets and optimized versions from the representative set.

Experimental results on several kernels demonstrate that our techniques can improve the overall performance of static programs or libraries with low runtime overhead. We plan to extend our algorithm to select representative set of optimizations not only based on performance but also taking into account both dataset characterization and possible run-time mapping at the same time. We will investigate the performance of different machine learning algorithms for runtime version mapping in detail and evaluate them for different multi-objective optimization scenarios. We plan to automate dataset and run-time feature generation in order to improve our version mapping technique. We believe that using staged compilation and self-tuning binaries can simplify automatic adaptation and optimization of the migrated code in virtual heterogeneous environments. Furthermore, we plan to combine our technique with collective optimization method [START_REF] Fursin | Collective optimization[END_REF][START_REF]CCC: Continuous Collective Compilation Framework[END_REF] and performance counters monitoring routines [START_REF] Fursin | A practical method for quickly evaluating program optimizations[END_REF][START_REF] Cavazos | Rapidly selecting good compiler optimizations using performance counters[END_REF] to evaluate it in a large number of heterogeneous, reconfigurable and virtual environments.

1 )

 1 c 1 , c 2 , …, c O } = a set of code versions (combinations of optimizations) to evaluate for a given program where O is the total number of versions to evaluate for a given program using iterative compilation D = { d 1 , d 2 , …, d X } = a set of inputs (datasets) available for a given program where X is the total number of inputs available P = threshold for possible performance loss for representative versions (percent) V = threshold for the maximum allowed number of representative versions Output: M = minimal number of representative versions C R = { c R1 , c R2 , …, c RM } = a final set of representative versions to minimize performance loss Heuristic: Save a copy of D into D all , because we need to change the content of D in the following steps for version selection but all the inputs are still needed for representative version set performance evaluation.

Fig. 5 .

 5 Fig. 5. Error rate of Direct Classification

Fig. 6 .

 6 Fig. 6. Root relative squared error of Performance Prediction Model

Fig. 7 .

 7 Fig. 7. Performance of DGEMM and FFT with multiversioning

V8 FFT input size Speedup Selection of some random optimizations

	1.15
	1.13
	1.11
	1.09	V1
		V2
	1.07	V3
		V4
	1.05	V5
		V6
	1.03	V7
	1.01
	0.99
	Fig. 1. Speedup variation of 8 different optimization variants of FFT kernel for differ-
	ent input sizes on Opteron 2.6GHz machine using Open64 compiler V4.0 with ICI and
	with -O3 default optimization level
	build a model to map features of a program input to the representative versions
	using traditional machine learning techniques as described in Section 4. All rep-
	resentative versions with the resulted selection mechanism are statically linked
	into the final executable or library.

Table 1 .

 1 Overheads of the static multiversioning approach

		No of	Run-time	Code size growth	Code size growth
		representative	selection	due to selection	due to
		versions	overhead	mechanism	multiversioning
	DGEMM	3	0.7%	1.8%	4.2%
	FFT	4	0.5%	8.8%	76.5%
	5 Related Work
	Iterative compilation is an effective technique to optimize programs on a wide
	range of different architectures without a priori knowledge of the hardware/software

Acknowledgments

We would like to thank Yuanjie Huang, Mingjie Xing, Lujie Zhong, and Liang Peng for their help on the writing of the paper and implementation of the framework. We would like to thank Olivier Temam and Albert Cohen for fruitful discussions.

This work was supported by a grant from the National Natural Science Foundation of China (No.60873057). This work was also partially supported by the MILEPOST project [4].