Application mapping on multiprocessor hardware platforms using genetic algorithms

Abstract

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.

Date of Award	2009
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology