This paper studies the problem of mapping streaming applications that can be modeled by a series-parallel graph, onto a 2-dimensional tiled CMP architecture. The objective of the mapping is to minimize the energy consumption, using dynamic and voltage scaling techniques, while maintaining a given level of performance, reflected by the rate of processing the data streams. This mapping problem turns out to be NP-hard, but we identify simpler instances, whose optimal solution can be computed by a dynamic programming algorithm in polynomial time. Several heuristics are proposed to tackle the general problem, building upon the theoretical results. Finally, we assess the performance of the heuristics through comprehensive simulations using the StreamIt workflow suite and various CMP grid sizes. Energy-aware mappings of series-parallel workflows onto chip multiprocessors Résumé : Dans ce rapport de recherche, nous nous intéressons au placement d'applications de type streaming représentées sous la forme d'un graphe sérieparallèle sur un processeur multi-coeur, en essayant de minimiser l'énergie consommée tout en n'excédant pas une borne sur un critère de performance, la période. La partie théorique démontre la NP-complétude ou la polynomialité du problème, selon des propriétés structurelles du multi-coeur (chaîne de coeurs, uni-ou bi-directionnelle, grille de coeurs) et la largeur du graphe de l'application (bornée ou non). Le problème le moins contraintétant NP-complet, nous décrivons dans la partie expérimentale quatre heuristiques, puis les comparons entre elles, et donnons un programme linéaire en nombres entiers qui permet d'obtenir la solution optimale en temps exponentiel.
REF studied the problem of mapping streaming applications onto a 2-dimensional tiled CMP architecture, with the objective of minimizing the energy consumption using DVFS, while maintaining a given throughput.
Energy-Aware Mappings of Series-Parallel Workflows onto Chip Multiprocessors
2011 International Conference on Parallel Processing
2011 International Conference on Parallel Processing
Computer Science