thumb|Répartition de charge entre deux serveurs accédés par 4 postes clients, ici le switch et le répartiteur sont deux points de panne potentiels, aucun des deux n'est doublé.En informatique, la répartition de charge () désigne le processus de répartition d’un ensemble de tâches sur un ensemble de ressources, dans le but d’en rendre le traitement global plus efficace. Les techniques de répartition de charge permettent à la fois d’optimiser le temps de réponse pour chaque tâche, tout en évitant de surcharger de manière inégale les nœuds de calcul.
La répartition de charge est issue de la recherche dans le domaine des ordinateurs parallèles. Deux principales approches coexistent : les algorithmes statiques, qui ne tiennent pas compte de l’état des différentes machines, et les algorithmes dynamiques, qui sont en général plus généraux et performants, mais nécessitent des échanges d’information entre les différentes unités de calculs, au risque d’une perte d’efficacité.
Ces techniques sont par exemple très utilisées dans le domaine des services HTTP où un site à forte audience doit pouvoir gérer des centaines de milliers de requêtes par seconde.
Spécifications d'un algorithme de répartition Un algorithme de répartition des charges cherche toujours à répondre à un problème spécifique. Entre autres, la nature des tâches qui seront exécutées, la complexité algorithmique que l’on s’autorise, l’architecture matérielle sur laquelle les algorithmes vont fonctionner ou encore la tolérance d’erreurs que l’on s’accorde doivent être pris en compte. Un compromis doit donc être trouvé pour répondre au mieux à un cahier des charges précis.
Nature des tâches Selon la nature des tâches, les algorithmes de répartitions seront plus ou moins efficaces. De ce fait, plus on dispose d’information sur les tâches au moment de la prise de décision, plus les possibilités d’optimisation des algorithmes seront grandes.
Taille des tâches La connaissance parfaite du temps d’exécution de chacune des tâches permet d’arriver à une répartition de charge optimale (voir l'algorithme de somme préfixale décrit ci-dessous). Malheureusement, il s’agit en fait d’un cas idéalisé. Il est en effet extrêmement rare que l’on connaisse le temps exact d’exécution de chaque tâche.
Il existe cependant plusieurs techniques pour avoir une idée des différents temps d’exécution. Tout d’abord, si l’on a la chance d’avoir des tâches de taille relativement homogène, il est possible de considérer que chacune d’entre elles nécessitera environ le temps moyen d’exécution. Si en revanche, le temps d’exécution est très irrégulier, il faut avoir recours à des techniques plus subtiles. L’une d’elles consiste à ajouter quelques métadonnées à chacune des tâches. En fonction des temps d’exécution précédents pour des métadonnées similaires, il est possible de faire des inférences pour une tâche future en se basant sur les statistiques.
Dépendances Dans certains cas, les taches dépendent les unes des autres. Ces interdépendances peuvent s’illustrer par un graphe orienté acyclique. Intuitivement, certaines tâches ne peuvent pas commencer tant que d’autres n’ont pas été terminées.
À supposer que le temps requis pour chacune des tâches soit connu à l’avance, il faut donc préalablement trouver un ordre d’exécution qui minimise le temps total de calcul. Bien qu’il s’agisse ici d’un problème NP-difficile, donc souvent impossible à résoudre informatiquement, il existe toutefois des algorithmes d'ordonnancement qui calculent des répartitions des tâches honorables par des méthodes métaheuristiques.
Séparabilité des tâches Une autre particularité des tâches est leur capacité à pouvoir être découpée en sous-tâches en cours d’exécution. L’algorithme de « Tree-Shaped Computation » présenté ensuite tire justement partie de cette spécificité.
Algorithmes statiques et dynamiques
Algorithmes statiques Un algorithme de répartition de charge est dit “statique” lorsqu’il ne prend pas en compte l’état du système dans la répartition des tâches. Par état du système, on entend ici le niveau de charge (voire parfois surcharge) de certains processeurs. Bien entendu, le nombre de processeurs, leur puissance respective et les vitesses de communications sont connues. Il s’agit donc d’associer les tâches aux processeurs de manière à minimiser une certaine fonction de performance. Toute l’astuce réside donc dans la conception de cette fonction de performance.
Les techniques sont toujours centralisées autour d’un organe qui distribue les charges et assure la minimisation de ladite fonction. Cette minimisation peut prendre en compte des informations liées aux tâches à distribuer, et en tirer un temps d’exécution probable.
L’avantage des algorithmes statiques est qu’ils sont faciles à mettre en place et sont, dans le cas de tâches assez régulières (comme dans le traitement des requêtes HTTP d’un site internet), extrêmement efficace. Cependant, il subsiste une variance statistique dans l’assignation des tâches qui peut entraîner une surcharge de certaines unités de calcul.
Algorithmes dynamiques Contrairement aux algorithmes de répartition de charge statiques, on qualifie de dynamiques ceux dont la charge de chacune des unités de calcul (aussi appelées nœuds) du système est pris en compte. Dans cette approche, les tâches peuvent se déplacer dynamiquement d’un nœud surchargé à un nœud en sous-charge, afin d'être traitées plus rapidement. Si ces algorithmes sont bien plus compliqués à mettre en place, ils peuvent produire, lorsqu’ils sont bien écrits, d’excellents résultats. Notamment lorsque le temps d’exécution varie fortement d’une tâche à l’autre.
L’architecture est cette fois-ci beaucoup plus modulable puisqu’il n’est pas obligatoire d’avoir un organe spécialement destiné à la distribution du travail. Lorsque les tâches sont assignées de manière unique à un processeur en fonction de son état à un moment donné, on parle d’assignation unique. Si par-contre, celles-ci peuvent être redistribuées en permanence en fonction de l’état du système et de ses évolutions, on parle d’assignation dynamique. Dans ce dernier cas, il faut faire attention à ne pas engendrer des coûts de communication trop importants entre les différentes unités, au risque de ralentir la résolution du problème global. Le pire des cas étant une partie de ping-pong entre les processeurs, résultant en un blocage indéfini de la résolution.
Architecture matérielle
Machines de puissance hétérogènes Les infrastructures informatiques parallèles sont souvent composées de machines de différentes puissances. Dès lors, ce paramètre peut être pris en compte dans la répartition de charge.
Par exemple, les unités de plus faible puissance peuvent recevoir en priorité les requêtes demandant une plus petite quantité de calcul, ou dans le cas où la taille des requêtes est homogène ou inconnue, en recevoir moins que les plus grosses unités.
Mémoire partagée ou distribuée On distingue souvent les ordinateurs parallèles en deux grandes catégories : ceux où tous les processeurs partagent une unique mémoire commune sur laquelle ils lisent et écrivent en parallèle (modèle PRAM), et ceux où chaque unité de calcul a sa propre mémoire (modèle de la mémoire distribuée), et où les échanges d’informations se font par messages.
Pour les ordinateurs à mémoire commune, la gestion des conflits d’écriture ralentit grandement la vitesse d’exécution individuelle de chacune des unités de calcul. Celles-ci peuvent cependant parfaitement travailler en parallèle. À l’inverse, dans le cas d’échange de message, chacun des processeurs peut travailler à plein régime. En revanche, quand vient le moment des échanges de messages, tous les processeurs sont obligés d’attendre les processeurs les plus lents pour commencer la phase de communication. On parle de synchronisation.
En réalité, rares sont les systèmes appartenant exactement à une seule des catégories. En général, les processeurs ont chacun une mémoire interne pour stocker les données nécessaires aux prochains calculs, et sont organisés dans des clusters successifs. Il n’empêche que les ordinateurs parallèles ont habituellement une tendance structurelle distribuée ou partagée. Il convient donc d’adapter de manière unique l’algorithme de répartition de charge à une architecture parallèle. Sinon, on risque de perdre grandement en efficacité dans la résolution parallèle du problème.
Hiérarchie En s’adaptant aux structures matérielles vues précédemment, on retrouve parmi les algorithmes de répartition de charge deux grandes catégories. D’une part celle où les tâches sont attribuées par un « maître », et exécutées par des « travailleurs » (modèle maître-esclave) qui tiennent le maître au courant de l’évolution de leur travail, celui-ci pouvant alors se charger d’attribuer (voire réattribuer) la charge de travail. La littérature parle d’architecture « Master-Worker ». À l’inverse, le contrôle peut être distribué entre les différents nœuds. L’algorithme de répartition de charge est alors exécuté sur chacun d’entre eux et la responsabilité de l’attribution des tâches (ou parfois ré-attribution pour certains algorithmes) est partagée. Cette dernière catégorie suppose un algorithme de répartition des charges dynamique.
Encore une fois, la conception de chaque algorithme de répartition de charge étant unique, il convient de nuancer la distinction précédente. Ainsi, il est également possible d’avoir une stratégie intermédiaire, avec par exemple des nœuds « maîtres » pour chaque sous cluster eux-mêmes soumis à un « maître » global. On rencontre aussi, des organisations en plusieurs niveaux, avec une alternance entre stratégie de contrôle « maître-esclave » et distribuée. Ces dernières stratégies devenant rapidement complexes, on ne les rencontre que rarement. Les concepteurs préférant des algorithmes plus facilement pilotables.
Adaptabilité à des architectures plus grandes (scalabilité) Dans le cadre d’algorithmes s’exécutant sur du très long terme (serveurs, cloud…), l’architecture de l’ordinateur évolue avec le temps car elle s’adapte à la demande. Il est toutefois préférable de ne pas devoir concevoir un nouvel algorithme à chaque fois.
Un paramètre extrêmement important d’un algorithme de répartition de charge est donc sa capacité à s’adapter à une architecture matérielle évolutive. On appelle cela la scalabilité (de l’anglais « scalable ») de l’algorithme. On dit aussi qu’un algorithme est scalable pour un paramètre d’entrée lorsque ses performances restent relativement indépendantes de la taille de ce paramètre.
Lorsque l’algorithme est capable de s’adapter à un nombre variant d’unités de calculs, mais que celui doit être fixé avant son exécution, on parle de version moulable (« moldable » en anglais). Si à l’inverse, l’algorithme est capable de s’adapter en temps réel aux ressources disponibles, on dit que l’algorithme est malléable. La plupart des algorithmes de répartition de charge sont au moins moulables.
Tolérance d'erreurs Dans les grands centres informatique, il n'est pas envisageable qu’une exécution n’aboutisse pas en raison d’une panne sur l’une des machines. Il est donc nécessaire de trouver des solutions pour détecter ces dysfonctionnements matériels et redistribuer la charge de travail sur des unités fonctionnelles, tout en signalant la panne matérielle à la maintenance.
Approches
Répartition statique avec connaissance complète des tâches : la somme préfixale Si les tâches sont indépendantes les unes des autres, si l’on connait parfaitement leur temps d’exécution respectif, et si enfin les tâches sont divisibles, il existe un algorithme simple et optimal.