Hardware-software partitioning in embedded system

One of the most crucial steps in the design of embedded systems is hardware-software partitioning, i.e. deciding which components of the system should be implemented in hardware and which ones in software. In this paper, different versions of the partitioning problem are defined, corresponding to real-time systems, and cost-constrained systems, respectively. The authors provide a formal mathematic analysis of the complexity of the problems: it is proven that they are NP-hard in the general case, and some efficiently solvable special cases are also presented. An ILP (integer linear programming) based approach is presented that can solve the problem optimally even for quite big systems, and a genetic algorithm (GA) that finds near-optimal solutions for even larger systems. A specialty of the GA is that non-valid individuals are also allowed, but punished by the fitness function.