Hardware-software partitioning in embedded system design

One of the most crucial steps in the design of embedded systems is hardware-software partitioning, i.e. deciding which components of the system are implemented in hardware and which ones in software. 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 are solving 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 nonvalid individuals are also allowed, but punished by the fitness function.