Parameterizing Simulated Annealing for Distributing Task Graphs on Multiprocessor SoCs
Heikki Orsila, Tero Kangas, Erno Salminen, Timo D. Hämäläinen · 2006
Mapping an application on multiprocessor system-on-chip (MPSoC) is a crucial step in architecture exploration. The problem is to minimize optimization effort and application execution time. Simulated annealing is a versatile algorithm for hard optimization problems, such as task distribution on MPSoCs. We propose a new method of automatically selecting parameters for a modified simulated annealing algorithm to save optimization effort. The method determines a proper annealing schedule and transition probabilities for simulated annealing, which makes the algorithm scalable with respect to application and platform size. Applications are modeled as static acyclic task graphs which are mapped to an MPSoC. The parameter selection method is validated by extensive simulations with 50 and 300 node graphs from the standard graph set