Robust Software Partitioning with Multiple Instantiation

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 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.


Published in:
INFORMS Journal on Computing, 24, 3, 500-515
Year:
2012
ISSN:
1526-5528
Keywords:
Laboratories:




 Record created 2014-01-21, last modified 2018-03-17

External link:
Download fulltext
URL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)