ASCENT: An Algorithmic Technique for Designing Hardware and Software in Tandem
Search-based software engineering is an emerging paradigm that uses automated search algorithms to help designers iteratively find solutions to complicated design problems. For example, when designing a climate monitoring satellite, designers may want to use the minimal amount of computing hardware to reduce weight and cost while supporting the image processing algorithms running onboard. A key problem in these situations is that the hardware and software designs are locked in a tightly coupled cost-constrained producer/consumer relationship that makes it hard to find a good hardware/software design configuration. Search-based software engineering can be used to apply algorithmic techniques to automate the search for hardware/software designs that maximize the image processing accuracy while respecting cost constraints. This paper provides the following contributions to research on search-based software engineering: 1) We show how a cost-constrained producer/consumer problem can be modeled as a set of two multidimensional multiple-choice knapsack problems (MMKPs), 2) we present a polynomial-time search-based software engineering technique, called the Allocation-baSed Configuration Exploration Technique (ASCENT), for finding near optimal hardware/software codesign solutions, and 3) we present empirical results showing that ASCENT's solutions average over 95 percent of the optimal solution's value.
algorithms computer aided software engineering optimization methods distributed computing