Les graphes sont une manière de représenter une multitude de systèmes réels dans des modèles d'optimisation, ou de simulation. De nombreuses variantes existent, telles que les graphes bipartis ou les hypergraphes. Ils peuvent être orientés ou non. Ses sommets et arêtes/arcs peuvent être valués, coloriés, étiquetés etc.

La versatilité de cette abstraction de modèle de données permet de représenter, entre autres, aussi bien des automates à états, des réseaux de communication, des interactions sociales, que des circuits électroniques. Une multitude d'algorithmes de référence peut alors être appliquée, selon les besoins applicatifs : parcours, plus court chemin, coloration, partitionnement, flots ... La complexité algorithmique de ces méthodes est très étudiée et est prise en compte par toute personne cherchant à optimiser la performance de solveurs basés sur ces dernières. Un autre aspect, au contraire bien souvent peu pris en compte, est la performance d'exécution (comprendre~: le temps d'exécution) des implémentations logicielles de ces méthodes sur des ordinateurs modernes. Il existe en effet une multitude de manières d'implémenter un même algorithme, avec des résultats de performance très différents pour une même tâche.

Cet exposé présentera les contraintes que posent les architectures matérielles modernes et discutera de comment en tenir compte lors des choix d'implémentation. Cette présentation est un retour d'expérience d'un projet de développement d'un outil de partitionnement d'hypergraphes, dans le cadre du projet européen DeepHealth.