A Finite Domain Model for Design Space Exploration

Abstract

Engineering design is a process of tradeoff analysis. Design decisions are evaluated, often involving quantitative comparisons between relevant metrics of goodness. Design space exploration formalizes the process of tradeoff evaluation through a mathematical representation of design decisions and outcomes in a compositional design model. The set of all possible outcomes of tradeoff evaluation is called a design space. The quantitative evaluation of metrics defined over the space is referred to as design space exploration. The goal of design space exploration is to determine, through the evaluation of design metrics, a design composition or small set of compositions which meet a set of formally specified design criteria. Design space exploration has arisen in the field of embedded system design, where complexities imposed by the physical environment of a system complicate the design process. The formal representations offered by most existing design space exploration tools are limited in scope to a particular problem or problem domain. Attempts to generalize existing exploration algorithms over a broad class of design space problems reveal scalability limitations. This dissertation describes a hybrid approach to design space exploration, embodied in the DesertFD toolset. DesertFD offers a finite domain constraint implementation of a domain-independent formal design space model, together with pruning algorithms facilitating the application of OCL constraints to the design space. The tool offers an expressive language for specifying complex formulas for modeling evaluation metrics over the space, and provides an interpretation of the language into a finite domain constraint specification. DesertFD integrates the finite domain constraint based pruning with an existing symbolic pruning tool based on Ordered Binary Decision Diagrams, facilitating a hybrid approach to design space exploration.