Multi-objective mapping optimization via problem decomposition for many-core systems
Shin-haeng Kang, Hoeseok Yang, Lars Schor, Iuliana Bacivarov, Soonhoi Ha, Lothar Thiele · 2012
Due to the trend of many-core systems for dynamic multimedia applications, the problem size of mapping optimization gets bigger than ever making conventional meta-heuristics no longer effective. Thus, in this paper, we propose a problem decomposition approach for large scale optimization problems. We basically follow the divide-and-conquer concept, in which a large scale problem is divided into several sub-problems. To remove the inter-relationship between sub-problems, proper abstraction is applied. The divided sub-problems can be solved either in parallel or in a sequence. The mapping optimization problem on dynamic many-core systems is decomposed and solved separately considering the system state and architectural hierarchy. Experimental evaluations with several examples prove that the proposed technique outperforms the conventional meta-heuristics both in optimality and diversity of the optimized pareto curve.