Hardware/Software Partitioning for Heterogenous MPSoC Considering Communication Overhead

Hardware/software partitioning (HSP) is an important step in the co-design of hardware/software. This paper addresses the problem of HSP with communication (HSPC) on heterogeneous multiprocessor system-on-chip (MPSoC). The classic HSP is modeled as an optimization problem with an objective of minimizing the finishing time in system under the hardware area constraints. First, we put forward an optimal method, integer linear programming (ILP) algorithm, for solving the problem for small inputs. Then, we propose two other algorithms using dynamic programming (DP) method, i.e., Optimal Tree Partitioning (OTP) method for tree-structured graphs and Tree Cover Partitioning (TCP) algorithm for general graphs in polynomial time. The overall performance of the proposed algorithms is evaluated through comparisons with that of a genetic algorithm (GA) and a greedy algorithm which are commonly used to solve HSP problem. We have conducted experimental performance evaluation on various benchmarks with different combinations of computation to communication ratios and hardware area constraints. The experimental results show that OTP algorithm can generate optimal solutions with much faster speed than ILP, and TCP algorithm can obtain near-optimum with higher quality than those produced by GA and greedy algorithm.