Application Mapping on Multiprocessor Hardware Platforms with Genetic Algorithms and Simulated Annealing

MPhil Thesis Defence


Title: "Application Mapping on Multiprocessor Hardware Platforms with
Genetic Algorithms and Simulated Annealing"

By

Mr. Dongzhe Su


Abstract

Multiprocessor and multicore hardware platforms are becoming ubiquitous in 
today's embedded systems. This thesis address the problem of mapping Timed 
Homogeneous Synchronous Dataflow(HSDF), a model of computation widely used 
in signal processing and streaming applications, onto a multiprocessor 
platform, where multiple processors are connected with a communication 
substrate with guaranteed latency, e.g. a hard real-time Network-on-Chip, 
with the object of maximizing overall throughput.

Since this is a NP-hard combinatorial optimization problem, it is 
infeasible to obtain optimal solutions for realistic large-size 
applications with exact solution techniques. Instead, we adopt stochastic 
search techniques, including Genetic Algorithms (GA) and Simulated 
Annealing (SA), to tackle this challenging problem. We use GA or EA to 
search the design space of possible actor-to-processor mappings and task 
orderings on each processor, and use graph-theoretic techniques to 
evaluate each design point by calculating the maximum throughput for any 
given actor-to-processor mapping and task ordering.

We compare the performance and scalability of the stochastic search 
techniques with exact solution techniques based on SAT solvers.


Date:			Tuesday, 2 June 2009

Time:			2:00pm-4:00pm

Venue:			Room 3501
 			Lifts 25-26

Committee Members:	Dr. Zonghua Gu (Supervisor)
 			Dr. Lin Gu (Chairperson)
 			Dr. Charles Zhang


**** ALL are Welcome ****