Communications - February 2012

contributed;articles

Doi: 10.1145/2076450.2076469

Avoid premature commitment, seek design
alternatives, and automatically generate
performance-optimized software.
By hoLGeR h. hoos
Programming
by
optimization

when Creating SOFtware, developers usually explore different ways of achieving certain tasks. These alternatives are often eliminated or abandoned early in the process, based on the idea that the flexibility they afford would be difficult or impossible to exploit later. This article challenges this view, advocating an approach that encourages developers to not only avoid premature commitment to certain design choices but to actively develop promising alternatives for parts of the design. In this approach, dubbed Programming by Optimization, or PbO, developers specify a potentially large design space of programs that accomplish a given task, from which versions of the program optimized for various use contexts are generated automatically, including parallel versions derived from the same sequential sources. We outline a simple, generic programming language extension that supports the specification of such design spaces and discuss ways specific programs

that perform well in a given use context can be obtained from these specifications through relatively simple source-code transformations and powerful design-optimization methods. Using PbO, human experts can focus on the creative task of devising possible mechanisms for solving given problems or subproblems, while the tedious task of determining what works best in a given use context is performed automatically, substituting human labor by computation.

The potential of PbO is evident from recent empirical results (see the table here). In the first two use cases—mixed integer programming and planning— existing software exposing many design choices in the form of parameters was automatically optimized for speed. This resulted in, for example, up to 52- fold speedups for the widely used commercial IBM ILOG CPLEX Optimizer software for solving mixed-integer programming problems. 21 In the third use case—verification problems encoded into propositional satisfiability—the proactive development of alternatives for important components of the program were an important part of the design process, enabling even greater performance gains.

Performance Matters

Computer programs and the algo-

key insights

;;; Premature commitment to design choices during software development often leads to loss of performance and limited flexibility.

;;; Pbo aims to avoid premature design choices and actively develop design alternatives, leading to large and rich design spaces of programs that can be specified through simple generic extensions of existing programming languages.

;;; advanced optimization and machine-learning techniques make it possible to perform automated performance optimization over the large spaces of programs arising in Pbo-based software development; per-instance algorithm selectors and parallel algorithm portfolios can be obtained from the same sequential source.