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:				Thursday, 21 August 2008

Time:				10:30a.m.-12:30p.m.

Venue:				Room 5510
				Lifts 25-26

Committee Members:		Dr. Zonghua Gu (Supervisor)
				Prof. Cunsheng Ding (Chairperson)
				Dr. Jogesh Muppala


**** ALL are Welcome ****