Optimization Online


Robust Software Partitioning with Multiple Instantiation

Simon Spacey (simon.spacey***at***sase.biz)
Wolfram Wiesemann (wwiesema***at***doc.ic.ac.uk)
Daniel Kuhn (dkuhn***at***doc.ic.ac.uk)
Wayne Luk (wl***at***doc.ic.ac.uk)

Abstract: The purpose of software partitioning is to assign code segments of a given computer program to a range of execution locations such as general purpose processors or specialist hardware components. These execution locations differ in speed, communication characteristics, and in size. In particular, hardware components offering high speed tend to accommodate only few code segments. The goal of software partitioning is to find an assignment of code segments to execution locations that minimizes the overall program run time and respects the size constraints. In this paper we demonstrate that an additional speedup is obtained if we allow code segments to be instantiated on more than one location. We further show that the program run time not only depends on the execution frequency of the code segments but also on their execution order if there are multiply instantiated code segments. Unlike frequency information, however, sequence information is not available at the time when the software partition is selected. This motivates us to formulate the software partitioning problem as a robust optimization problem with decision-dependent uncertainty. We transform this problem to a mixed-integer linear program of moderate size and report on promising numerical results.

Keywords: Robust optimization, software partitioning, decision-dependent uncertainty, multiple instance partitioning

Category 1: Robust Optimization

Citation: Working paper, Department of Computing, Imperial College London, October 2009

Download: [PDF]

Entry Submitted: 10/12/2009
Entry Accepted: 10/12/2009
Entry Last Modified: 06/22/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society