Control-flow dependence is an intrinsic limiting factor for pro- gram acceleration. With the availability of instruction-level par- allel architectures, if-conversion optimization has, therefore, be- come pivotal for extracting parallelism from serial programs. While many if-conversion optimization heuristics have been proposed in the literature, most of them consider rigid criteria regardless of the underlying hardware and input programs. In this paper, we propose a novel if-conversion scheme that preforms an efficient if-conversion transformation using a machine learning technique (NEAT). This method enables if-conversion customization overall branches within a program unlike the literature that considered in- dividual branches. Our technique also provides flexibility required when compiling for heterogeneous systems. The efficacy of our approach is shown by experiments and reported results which il- lustrate that the programs can be accelerated on the same archi- tecture and without modifying the original code. Our technique applies for general purpose programming languages (e.g. C C++) and is transparent for the programmer. We implemented our tech- nique in LLVM 3.6.1 compilation infrastructure and experimented on the kernels of SPEC-CPU2006 v1.1 benchmarks suite running on a multicore system of Intel(R) Xeon(R) 3.50GHz processors. Our findings show a performance gain up to 8.6 over the stan- dard optimized code (LLVM -O2 with if-conversion included), in- dicating the need for If-conversion compilation optimization that can adapt to the unique characteristics of every individual branch.
Other methods use dynamic if-conversion in which a profiling process during runtime is used to capture some characteristics (e.g. misprediction rate) to be used in optimization. In @cite_24 , runtime information is used to construct a dynamic optimizer that complements the static one in a previously presented algorithm. It can convert branches, or reverse their conversion, targeting the higher performance based on profiling the program to discover the highly mispredicted branches. Although this algorithm chooses the conversions that improve performance, it does not consider any correlation between the different s which are most probably related to each other especially within the same function.
@cite_24
2142362286
Dynamic Optimization is an umbrella term that refers to any optimization of software that is performed after the initial compiles time. It is a complementary optimization opportunity that may greatly improve performance on any computer system, but plays an especially important role in statically scheduled code. Several groups are working on developing dynamic optimization systems, yet the area of dynamic optimization algorithms can still benefit from further research. We introduce a lightweight algorithm that can be used in any modern dynamic optimizer to balance control flow and predication based on actual runtime behavior. In addition, we study the effectiveness of predicting overall runtime behavior based on a small sample size. Preliminary results show that if we skip the warm-up period of programs, profiles based on a small sample size of a particular run can be quite representative of overall runtime behavior (up to 98 correlation). This profile information can be used effectively in a number of dynamic optimizations. We found that our dynamic if-conversion algorithm can use this collated profile data to incorporate actual branch misprediction rates into the if-conversion decision process. This method acts as an effective means for balancing the results of static if-conversion, achieving speedup values of up to 14.7 , and can be easily incorporated into modern dynamic optimizers.