## The focus on Embedded System Design

In the last years the diffusion of embedded systems has been growing at a surprising rate: automotive control engines, cellular phones, multimedia electronic devices are common examples of the pervasivity of such devices.

Being widely employed in portable devices, these systems need energy efficient platforms with real-time performance: Multiprocessor Systems on Chips (MPSoCs) are among the most appealing solutions to these issues. MPSoCs are multi core, general purpose, architectures developed on a single chip; each core has low energy consumption and limited computational power: real time level performance is thus achieved by extensive parallelization.

Given a target application, usually described as a dataflow graph, a complete system design aims to allocate hardware resources to processes and to compute a deadlock-free schedule. The problem of allocating and scheduling precedence-constrained tasks on the resources of a distributed real-time system is NP-hard. For this reason, heuristic approaches are widely used, such as genetic algorithms, simulated annealing and tabu search. However, they do not provide any guarantees on the optimality of the final solution.

On the other hand, complete approaches, which compute the optimal solution at the cost of an increasing computational effort, can be attractive for statically scheduled systems, where the solution is computed once and applied throughout the entire lifetime of the system. Since embedded devices always run the same application in a well-characterized context, it is possible to spend a large amount of time for finding an optimal allocation and scheduling off-line and then deploy it.