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.