Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond

Motivation

Reusable components and software composition support the construction of large and reliable software systems from pre-defined and tested partial solutions. When maximizing reusability, we end up with components that are very general and do not fit one particular scenario perfectly. Therefore, adaptation, especially optimization, is established as a technique to deal with such mismatches.

We observe that composition and optimization are currently discussed almost in isolation in two different scientific communities. Composition is understood as a problem in software engineering for general-purpose computing; techniques include meta-/generative programming, configuration and (self-)adaptation, and architecture and component systems. Optimization is typically understood as a problem of high-performance and stream computing, and compiler construction; techniques include auto-tuning, scheduling, parallelization, just-in-time compilation, run-time optimizations, and performance prediction.

The goal of this seminar is to bring together outstanding researchers from these two communities. We focus on a common topic of interest: the optimized generation and composition of programs from components, which includes the automatic adaptation to advanced execution platforms. It addresses solutions for both sequential and parallel components and target systems. This issue requires the integration of techniques from both subdomains. We expect that this seminar will encourage future cooperations beyond community boundaries.

We will review the current state of the art, discuss strengths and limitations of current approaches, identify challenging problems to be attacked in the near future, and look for further application domains and improved techniques. In particular, we will address the following questions:

• What structures and artifacts in programs or program components are suitable variation points for optimizations? How should they be exposed, explicitly or implicitly? How can the programmer of a (third-party) component influence the optimization spectrum or the predictions during the composition process? What are necessary extensions to component interfaces and contracts to enable more aggressively optimized compositions? How should software architectures be organized to support optimized composition? Are there different appropriate solutions for different target platforms, e.g. for many-core processors vs. computational grids?
• What is the limit for the application of auto-tuning methods? Are they confined to a few “benign” application domains, or can they be generalized to a much wider area? How can they support optimizing composition in the general sense?
• Which program optimizations and optimizing composition issues should be considered together (solved globally) for what type of target platform? Which problems can be solved locally under what conditions?
• How can we reduce the complexity of the optimization space exploration especially for combined problems? What methods have been useful in previous approaches, and how can they be adapted or improved?
• What are the appropriate prediction methods for time, energy or space on various platforms to be used when deciding about optimizing composition? What are the trade-offs between analysis cost and accuracy? How much can or should be precomputed earlier in the composition process, e.g. at deployment time? How can such precomputed information be stored and retrieved efficiently?
• What is the complexity of the variant malleable task scheduling problem that appears when optimizing several calls to functions with multiple parallel and sequential implementation variants? What are suitable solution methods for it?
• How can adaptivity to changes in the available resources (e.g., handling grid nodes joining or leaving dynamically, discovering new system components, or handling failure) or software components (dynamic update or addition) be properly taken into account in optimizing composition?
• How can this technology be transferred to sensor-grid and ubiquitous computing applications?