time in an e-commerce application; and Li et al. 26 automatically created hybrid sorting algorithms that outperform those provided by several widely used libraries, including the C++ Standard Template Library.

 

Where the Road Goes…

The PbO paradigm offers numerous benefits to software developers and users alike, including better performance of programs created this way and easier, more effective adaptation to different (and changing) use contexts, as well as better use of human capabilities and skills throughout the development process.

To be effective, PbO needs to be used in combination with other techniques and established practices. In particular, careful consideration of design patterns, memory-access and communication patterns, data organization, and threading will still be crucially important for achieving high performance in many cases, as will performance-profiling approaches. PbO should be seen as complementing, rather than superseding, these considerations, which conversely inform and constrain the design choices realized in the context of a PbO-based development process. The cost of PbO induces additional constraints and may in certain cases limit the degree to which the approach can be applied. Still, many areas of computing science and its applications have much to gain from PbO, particularly for software using techniques from artificial intelligence, machine learning, and data mining, as well as simulation software, performance-critical procedures from standard libraries, and even data transmissions protocols, basically any situation involving heuristic design choices.

While lower levels of PbO, in combination with existing tools, are already able to achieve substantial benefits, we believe the full potential of PbO is realized through higher levels of PbO-based software development and dedicated support in the form of the language extensions and tools outlined here. A first version of a weaver for PbO-C was implemented by the author and now available at http://www.prog-by-opt.net. PbO design optimization can be achieved

Because it
enables empirical
investigation into
the interaction
between
problem-instance
characteristics
and the efficacy
of certain solver
components,
Pbo promises to
facilitate insight
into what renders
certain problems
so difficult to solve.

through readily available automated algorithm-configuration procedures (such as ParamILS19, 20), and we expect even better performing procedures to be available within the next two years. Similarly, meta-algorithmic procedures that effectively produce per-instance algorithm selectors from a single, highly parametric design are available today (see, for example, Xu et al. 39) and will likely be further improved in the near future. We are currently working on automated procedures for generating parallel portfolios from a given design-space specification and expect to obtain useful results soon. We plan to integrate these (and possibly other) meta-algorithmic optimization procedures into a single PbO design optimizer that facilitates their use in the context of PbO-based software development.

The High Performance Algorithm Laboratory (HAL) environment29 is designed to support computer-aided design and empirical analysis of high-performance algorithms through ready-to-use, state-of-the-art analysis and design procedures. HAL provides an ideal platform for realizing and operating an integrated PbO design optimizer and could thus provide strong support for PbO-based software development. Furthermore, extensions and enhancements of widely used development platforms, particularly the Eclipse integrated development environment ( http://www.eclipse. org), will provide useful support for PbO-based software development. Besides syntax highlighting and folding for PbO constructs, we envision tools that support developers tracking and navigating parameters and choices (especially distributed choices) declared in PbO sources, and in using PbO weavers and optimizers in their various modes.

We expect PbO to also facilitate scientific insight into the efficacy of algorithms and their components, as well as into the empirical complexity of computational problems. For example, to measure the extent to which a particular instance of a design choice contributes to overall performance, one would simply remove that instance (or instruct the weaver to ignore it) and compare the performance obtained in one or more use