Beta 1


Title Optimizing Application Mapping for Network-On-Chip Systems
Author Sandvei Jensen, Bjarke
Supervisor Stidsen, Thomas K. (Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2008
Abstract The present master thesis examined the use of metaheuristics to optimize the application mapping of a Network On Chip. The focus was on generating network topologies that minimizes the period latency for applications executing on a Network On Chip. An analytical model of the worst case latency was used in the optimization. Four metaheuristics, Simulated Annealing, Tabu Search, GRASP and Variable Neighborhood Search were examined in detail. The process of parameter tuning was studied and an automatic parameter tuning heuristic was thereafter developed. A manual and automatic tuning was performed, and the parameter tuning processes were compared. The performance of the four metaheuristics was compared, using the best parameter settings found in the tuning process. Results showed that using metaheuristics in some form is the most realistic method for solving problems with the complexity and number of variables used in the present project. Also when considering the restricted execution time used. All four metaheuristics tested were able to produce close to optimal solutions to the application mapping problem within a short execution time of two minutes. The metaheuristics Variable Neighborhood Search and Simulated Annealing which only uses a random neighborhood search were found to have an inadequate performance on some of the problem settings examined in the present project. Increasing the execution time to five minutes improved the solutions found for the two tested metaheuristics, GRASP and Tabu Search. Of the metaheuristics tested, overall GRASP clearly had the best performance, mainly because of an eective construction function.
Series IMM-M.Sc.-2008-55
Fulltext
Original PDF ep08_55_net.pdf (1.14 MB)
Admin Creation date: 2008-06-18    Update date: 2008-07-29    Source: dtu    ID: 220815    Original MXD