Application mapping on multiprocessor hardware platforms using genetic algorithms

Synchronous Dataflow (SDF) is a widely-used model-of-computation for signal processing and multimedia applications. As Moore’s law comes to an end, multiprocessor systems are becoming ubiquitous in today’s embedded systems design. In this thesis, I address the problem of mapping a Homogeneous Synchronous Dataflow (HSDF) graph onto a multiprocessor platform with the objective of maximizing system throughput. The hardware platform consists of multiple processors connected with a communication substrate with guaranteed inter-processor communication latency, e.g. a hard real-time Network-on-Chip. Since the problem is a NP-hard combinatorial optimization problem, it is generally infeasible to use exhaustive search to obtain optimal solutions for realistic-sized applications. In this thesis, I adopt Genetic Algorithms, to search the design space of all possible actor-to-processor mappings and actor orderings on each processor to find the optimal solution, and compare the performance and scalability of GA with the exact solution technique based on SAT solving