Compiler and performance optimization using similarity analysis

Maintaining and improving program performance in the multi-core era requires a large engineering effort (e.g., a large number of time consuming trials & tests). It involves finding, as efficiently as possible, a combination of attributes that characterize (i.e., expose similarity in) algorithmic optimizations, compiler optimizations, execution environment settings and hardware configurations to reach certain performance goals. This problem currently is not solved in its entirety because the number of attributes involved is very large. Thus programs are optimized based on a very limited number of such attributes at a time.
This project investigates how to construct empirical performance models that provide program performance prediction across system configurations, where the term system includes the development environment, e.g., compilers, libraries and their settings, and execution environment, e.g., operating system, run-time environment, hardware and their settings. Predictions are required to be sufficiently accurate to reduce engineering effort (e.g., by replacing trials & tests with predictions).
Specifically, the following issues are investigated: (i) the definition of two types of signatures, feature-aware and feature-agnostic respectively, to characterize programs and/or systems; (ii) techniques to expose and analyze the structure of similarity induced by a given type of signature on programs and systems; and (iii) techniques that leverage (learn from) such a structure of similarity and suggest ways for optimizing both serial and parallel programs.
Feature-aware program signatures are constructed from a subset of hardware performance counters. The counters are tied to a specific performance task to accomplish, e.g., system evaluation, selection of compiler heuristics. Feature-agnostic program signatures are constructed from a collection of completion times for some combinations of (program, system). For this type of signature, the characterization of program and system is combined. Techniques that leverage this type of performance modeling can be applied to characterizing and comparing hardware configurations, compilers, run-time environments and even all the above combined.

Supported by the National Science Foundation