Iterative compilation in a non-linear optimisation space

Abstract

This paper investigates the applicability of iterative search techniques in program optimisation. Iterative com-pilation is usually considered too expensive for general pur-pose computing but is applicable to embedded applications where the cost is easily amortised over the number of em-bedded systems produced. This paper presents a case study, where an iterative search algorithm is used to investigate a non-linear transformation space and find the fastest execu-tion time within a fixed number of evaluations. By using profile feedback in the form of execution time, it searches a large but restricted transformation space and shows per-formance improvement over existing approaches. We show that in the case of large transformation spaces, we can achieve within 0.3 % of the best possible time by visiting less then 0.25 % of the space using a simple algorithm and find the minimum after visiting up to less than 1 % of the space. 1.