Power-aware Manhattan routing on chip multiprocessors

Résumé : Nous nous intéressons au routage des communications dans un processeur multi-cœur (CMP). Le but est de trouver un routage valide, c'est-à-dire un routage dans lequel la quantité de données routée entre deux cœurs voisins ne dépasse pas la bande passante maximale, et tel que la puissance dissipée dans les communications est minimale. Nous nous positionnons au niveau système : nous supposons que des applications, sous forme de graphes de tâches, s'exécutent sur le CMP, chaque tâche étant déjà assignée à un cœur. Nous avons donc un ensemble de communications à router entre les cœurs. Nous utilisons un modèle classique, dans lequel la puissance dissipée par un lien de communication est la somme d'une partie statique et d'une partie dynamique, cette dernière dépendant de la fréquence du lien. Cette fréquence est ajustable et proportionnelle à la bande passante. La politique la plus utilisée est le routage XY : chaque communication est en- voyée horizontalement, puis verticalement. Cependant si nous nous autorisons à utiliser les chemins de Manhattan entre la source et la destination, la puissance dissipée peut être considérablement réduite. De plus, il est parfois possible de trouver une solution, alors qu'il n'en existait pas avec un routage XY. Dans ce papier, nous comparons le routage XY et le routage via des chemins de Manhattan, aussi bien d'un point de vue théorique que d'un point de vue pratique. Nous considérons deux variantes du routage par chemins de Manhattan : dans un routage à chemin unique, un seul chemin peut être utilisé pour chaque communication, tandis que le routage à chemin multiples nous permet d'éclater une communication et de lui faire emprunter plusieurs routes. Nous établissons la NP-complétude du problème consistant à trouver un routage Manhattan qui minimise la puissance dissipée, exhibons la borne supérieure minimale du ratio entre la puissance dissipée par un routage XY et celle dissipée par un routage Manhattan, et pour terminer, nous effectuons des simulations pour étudier les performances de nos heuristiques de routage Manhattan.
Type de document :
Pré-publication, Document de travail
RR-7752. 2011
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00629804
Contributeur : Paul Renaud-Goud <>
Soumis le : jeudi 6 octobre 2011 - 17:26:39
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : dimanche 4 décembre 2016 - 05:31:17

Fichier

RR-7752.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00629804, version 2

Collections

Citation

Anne Benoit, Rami Melhem, Paul Renaud-Goud, Yves Robert. Power-aware Manhattan routing on chip multiprocessors. RR-7752. 2011. 〈inria-00629804v2〉

Partager

Métriques

Consultations de la notice

330

Téléchargements de fichiers

142