To increase productivity, today's compilers offer a two-fold abstraction: they hide hardware complexity from the software developer, and they support many architectures and programming languages. At the same time, due to fierce market competition, most processor vendors do not disclose many of their implementation details. These factors force software developers to treat both compilers and architectures as black boxes. In practice, this leads to a suboptimal compiler behavior where the maximum potential of improving an application's resource usage, such as execution time, is often not realized. This paper exposes missed optimization opportunities and is of interest to all three communities, compiler engineers, software developers and hardware architects. By exploiting the behavior of the standard optimization levels, such as the -O3, of the LLVM v6.0 compiler, we show how to reveal hidden cross-architecture and architecture-dependent potential optimizations on two popular processors: the Intel i5-6300U, widely used in portable PCs, and the ARM Cortex-A53-based Broadcom BCM2837 used in the Raspberry Pi 3B+. The classic nightly regression testing can then be extended to use the resource usage and compilation information collected while exploiting subsequences of the standard optimization levels. This provides a systematic means of detecting and tracking missed optimization opportunities. The enhanced nightly regression system is capable of driving the improvement and tuning of the compiler's common optimizer
Iterative compilation typically randomly samples the optimization configuration space until finding a configuration that outperforms a predefined optimization level @cite_2 . The technique has in many cases proven to provide significant performance gains @cite_7 @cite_15 , but typically a large number of optimization configurations, in the order of hundreds to thousands, need to be evaluated before reaching any performance gains over standard optimization levels. Thus, iterative compilation has been traditionally used as a baseline to assess the performance of MLB compiler auto-tuning techniques @cite_0 @cite_2 @cite_12 . MLB techniques aim to beat the performance of iterative compilation by finding a better optimization configuration in a shorter time. Thus, MLB techniques try to strategically sample the optimization configuration space based on the models built during their training phase. Such models are being trained on either static code features @cite_0 or profiling information @cite_19 , such as performance counter values that characterize the programs in the training set, and a performance metric for the dependent variable. An example of such a performance metric is the execution time of programs when applying a specific optimization configuration.
@cite_7 @cite_0 @cite_19 @cite_2 @cite_15 @cite_12
2156560068 2142079700 2751901133 2785111092
Tuning compiler optimizations for rapidly evolving hardware makes porting and extending an optimizing compiler for each new platform extremely challenging. Iterative optimization is a popular approach to adapting programs to a new architecture automatically using feedback-directed compilation. However, the large number of evaluations required for each program has prevented iterative compilation from widespread take-up in production compilers. Machine learning has been proposed to tune optimizations across programs systematically but is currently limited to a few transformations, long training phases and critically lacks publicly released, stable tools. Our approach is to develop a modular, extensible, self-tuning optimization infrastructure to automatically learn the best optimizations across multiple programs and architectures based on the correlation between program features, run-time behavior and optimizations. In this paper we describe Milepost GCC, the first publicly-available open-source machine learning-based compiler. It consists of an Interactive Compilation Interface (ICI) and plugins to extract program features and exchange optimization data with the cTuning.org open public repository. It automatically adapts the internal optimization heuristic at function-level granularity to improve execution time, code size and compilation time of a new program on a given architecture. Part of the MILEPOST technology together with low-level ICI-inspired plugin framework is now included in the mainline GCC. We developed machine learning plugins based on probabilistic and transductive approaches to predict good combinations of optimizations. Our preliminary experimental results show that it is possible to automatically reduce the execution time of individual MiBench programs, some by more than a factor of 2, while also improving compilation time and code size. On average we are able to reduce the execution time of the MiBench benchmark suite by 11 for the ARC reconfigurable processor. We also present a realistic multi-objective optimization scenario for Berkeley DB library using Milepost GCC and improve execution time by approximately 17 , while reducing compilation time and code size by 12 and 7 respectively on Intel Xeon processor. Applying the right compiler optimizations to a particular program can have a significant impact on program performance. Due to the non-linear interaction of compiler optimizations, however, determining the best setting is nontrivial. There have been several proposed techniques that search the space of compiler options to find good solutions; however such approaches can be expensive. This paper proposes a different approach using performance counters as a means of determining good compiler optimization settings. This is achieved by learning a model off-line which can then be used to determine good settings for any new program. We show that such an approach outperforms the state-ofthe- art and is two orders of magnitude faster on average. Furthermore, we show that our performance counter-based approach outperforms techniques based on static code features. Using our technique we achieve a 17 improvement over the highest optimization setting of the commercial PathScale EKOPath 2.3.1 optimizing compiler on the SPEC benchmark suite on a recent AMD Athlon 64 3700+ platform. Recent compilers offer a vast number of multilayered optimizations targeting different code segments of an application. Choosing among these optimizations can significantly impact the performance of the code being optimized. The selection of the right set of compiler optimizations for a particular code segment is a very hard problem, but finding the best ordering of these optimizations adds further complexity. Finding the best ordering represents a long standing problem in compilation research, named the phase-ordering problem. The traditional approach of constructing compiler heuristics to solve this problem simply cannot cope with the enormous complexity of choosing the right ordering of optimizations for every code segment in an application. This article proposes an automatic optimization framework we call MiCOMP, which Mi tigates the Com piler P hase-ordering problem. We perform phase ordering of the optimizations in LLVM’s highest optimization level using optimization sub-sequences and machine learning. The idea is to cluster the optimization passes of LLVM’s O3 setting into different clusters to predict the speedup of a complete sequence of all the optimization clusters instead of having to deal with the ordering of more than 60 different individual optimizations. The predictive model uses (1) dynamic features, (2) an encoded version of the compiler sequence, and (3) an exploration heuristic to tackle the problem. Experimental results using the LLVM compiler framework and the Cbench suite show the effectiveness of the proposed clustering and encoding techniques to application-based reordering of passes, while using a number of predictive models. We perform statistical analysis on the results and compare against (1) random iterative compilation, (2) standard optimization levels, and (3) two recent prediction approaches. We show that MiCOMP’s iterative compilation using its sub-sequences can reach an average performance speedup of 1.31 (up to 1.51). Additionally, we demonstrate that MiCOMP’s prediction model outperforms the -O1, -O2, and -O3 optimization levels within using just a few predictions and reduces the prediction error rate down to only 5 . Overall, it achieves 90 of the available speedup by exploring less than 0.001 of the optimization space. Developing efficient software and hardware has never been harder whether it is for a tiny IoT device or an Exascale supercomputer. Apart from the ever growing design and optimization complexity, there exist even more fundamental problems such as lack of interdisciplinary knowledge required for effective software hardware co-design, and a growing technology transfer gap between academia and industry. We introduce our new educational initiative to tackle these problems by developing Collective Knowledge (CK), a unified experimental framework for computer systems research and development. We use CK to teach the community how to make their research artifacts and experimental workflows portable, reproducible, customizable and reusable while enabling sustainable RD crowdsource experimentation across diverse platforms; share experimental results, models, visualizations; gradually expose more design and optimization choices using a simple JSON API; and ultimately build upon each other's findings. As the first practical step, we have implemented customizable compiler autotuning, crowdsourced optimization of diverse workloads across Raspberry Pi 3 devices, reduced the execution time and code size by up to 40 , and applied machine learning to predict optimizations. We hope such approach will help teach students how to build upon each others' work to enable efficient and self-optimizing software hardware model stack for emerging workloads.