Conception de réseau d'interconnexion
Un interconnection networkdans une machine parallèle transfère les informations de n'importe quel nœud source vers n'importe quel nœud de destination souhaité. Cette tâche doit être effectuée avec une latence aussi faible que possible. Il devrait permettre à un grand nombre de ces transferts d'avoir lieu simultanément. De plus, il devrait être peu coûteux par rapport au coût du reste de la machine.
Le réseau est composé de liens et de commutateurs, ce qui permet d'envoyer les informations du nœud source au nœud de destination. Un réseau est spécifié par sa topologie, son algorithme de routage, sa stratégie de commutation et son mécanisme de contrôle de flux.
Structure organisationnelle
Les réseaux d'interconnexion sont composés des trois éléments de base suivants:
Links- Une liaison est un câble d'une ou plusieurs fibres optiques ou fils électriques avec un connecteur à chaque extrémité attaché à un commutateur ou un port d'interface réseau. Grâce à cela, un signal analogique est transmis d'une extrémité, reçu à l'autre pour obtenir le flux d'informations numériques d'origine.
Switches- Un commutateur est composé d'un ensemble de ports d'entrée et de sortie, d'une «barre transversale» interne connectant toutes les entrées à toutes les sorties, d'une mémoire tampon interne et d'une logique de contrôle pour effectuer la connexion d'entrée-sortie à chaque instant. Généralement, le nombre de ports d'entrée est égal au nombre de ports de sortie.
Network Interfaces- L'interface réseau se comporte très différemment des nœuds de commutation et peut être connectée via des liaisons spéciales. L'interface réseau formate les paquets et construit les informations de routage et de contrôle. Il peut avoir un tampon d'entrée et de sortie, par rapport à un commutateur. Il peut effectuer une vérification des erreurs de bout en bout et un contrôle de flux. Par conséquent, son coût est influencé par sa complexité de traitement, sa capacité de stockage et le nombre de ports.
Réseau d'interconnexion
Les réseaux d'interconnexion sont composés d'éléments de commutation. La topologie est le modèle permettant de connecter les commutateurs individuels à d'autres éléments, tels que les processeurs, les mémoires et autres commutateurs. Un réseau permet l'échange de données entre les processeurs dans le système parallèle.
Direct connection networks- Les réseaux directs ont des connexions point à point entre les nœuds voisins. Ces réseaux sont statiques, ce qui signifie que les connexions point à point sont fixes. Quelques exemples de réseaux directs sont les anneaux, les maillages et les cubes.
Indirect connection networks- Les réseaux indirects n'ont pas de voisins fixes. La topologie de communication peut être modifiée dynamiquement en fonction des demandes de l'application. Les réseaux indirects peuvent être subdivisés en trois parties: les réseaux de bus, les réseaux à plusieurs étages et les commutateurs crossbar.
Bus networks- Un réseau de bus est composé d'un certain nombre de lignes de bit sur lesquelles un certain nombre de ressources sont attachées. Lorsque les bus utilisent les mêmes lignes physiques pour les données et les adresses, les données et les lignes d'adresse sont multiplexées dans le temps. Lorsque plusieurs maîtres de bus sont connectés au bus, un arbitre est nécessaire.
Multistage networks- Un réseau à plusieurs étages se compose de plusieurs étages de commutateurs. Il est composé de commutateurs «axb» qui sont connectés en utilisant un modèle de connexion interétage (ISC) particulier. Les petits éléments de commutation 2x2 sont un choix courant pour de nombreux réseaux à plusieurs étages. Le nombre d'étages détermine le retard du réseau. En choisissant différents modèles de connexion inter-étages, divers types de réseau à plusieurs étages peuvent être créés.
Crossbar switches- Un commutateur crossbar contient une matrice d'éléments de commutation simples qui peuvent s'allumer et s'éteindre pour créer ou interrompre une connexion. En activant un élément de commutation dans la matrice, une connexion entre un processeur et une mémoire peut être établie. Les commutateurs crossbar ne sont pas bloquants, c'est-à-dire que toutes les permutations de communication peuvent être effectuées sans blocage.
Évaluation des compromis de conception dans la topologie de réseau
Si la principale préoccupation est la distance de routage, alors la dimension doit être maximisée et un hypercube créé. Dans le routage store-and-forward, en supposant que le degré de commutation et le nombre de liens ne constituent pas un facteur de coût significatif, et que le nombre de liens ou le degré de commutation sont les principaux coûts, la dimension doit être minimisée et un maillage construit.
Dans le pire des cas, le modèle de trafic pour chaque réseau, il est préférable d'avoir des réseaux de grande dimension où tous les chemins sont courts. Dans les modèles où chaque nœud communique avec seulement un ou deux voisins proches, il est préférable d'avoir des réseaux de faible dimension, car seules quelques-unes des dimensions sont réellement utilisées.
Routage
L'algorithme de routage d'un réseau détermine lequel des chemins possibles de la source à la destination est utilisé comme routes et comment la route suivie par chaque paquet particulier est déterminée. Le routage par ordre de dimension limite l'ensemble des chemins légaux de sorte qu'il y ait exactement un itinéraire de chaque source à chaque destination. Celle obtenue en parcourant d'abord la bonne distance dans la dimension d'ordre supérieur, puis la dimension suivante et ainsi de suite.
Mécanismes de routage
L'arithmétique, la sélection de port basée sur la source et la recherche de table sont trois mécanismes que les commutateurs à grande vitesse utilisent pour déterminer le canal de sortie à partir des informations contenues dans l'en-tête de paquet. Tous ces mécanismes sont plus simples que le type de calcul de routage général implémenté dans les routeurs LAN et WAN traditionnels. Dans les réseaux informatiques parallèles, le commutateur doit prendre la décision de routage pour toutes ses entrées à chaque cycle, le mécanisme doit donc être simple et rapide.
Routage déterministe
Un algorithme de routage est déterministe si la route empruntée par un message est déterminée exclusivement par sa source et sa destination, et non par un autre trafic sur le réseau. Si un algorithme de routage ne sélectionne que les chemins les plus courts vers la destination, il est minimal, sinon il est non minimal.
Liberté de blocage
Un blocage peut se produire dans diverses situations. Lorsque deux nœuds tentent de s'envoyer des données et que chacun commence à envoyer avant que l'un ou l'autre ne les reçoive, un blocage «frontal» peut se produire. Un autre cas de blocage se produit, lorsqu'il y a plusieurs messages en concurrence pour les ressources au sein du réseau.
La technique de base pour prouver qu'un réseau est sans blocage, consiste à effacer les dépendances qui peuvent survenir entre les canaux à la suite de messages circulant à travers les réseaux et à montrer qu'il n'y a pas de cycles dans le graphe de dépendance de canal global; il n'y a donc pas de modèles de trafic pouvant conduire à une impasse. La manière courante de procéder consiste à numéroter les ressources de canal de telle sorte que tous les itinéraires suivent une séquence particulière croissante ou décroissante, de sorte qu'aucun cycle de dépendance ne se produise.
Conception de commutateur
La conception d'un réseau dépend de la conception du commutateur et de la manière dont les commutateurs sont câblés ensemble. Le degré du commutateur, ses mécanismes de routage internes et sa mise en mémoire tampon interne déterminent quelles topologies peuvent être prises en charge et quels algorithmes de routage peuvent être implémentés. Comme tout autre composant matériel d'un système informatique, un commutateur réseau contient le chemin des données, le contrôle et le stockage.
Les ports
Le nombre total de broches est en fait le nombre total de ports d'entrée et de sortie multiplié par la largeur du canal. Comme le périmètre de la puce croît lentement par rapport à la zone, les commutateurs ont tendance à être limités par les broches.
Chemin de données interne
Le chemin de données est la connectivité entre chacun de l'ensemble de ports d'entrée et chaque port de sortie. Elle est généralement appelée barre transversale interne. Une barre transversale non bloquante est celle où chaque port d'entrée peut être connecté à une sortie distincte dans n'importe quelle permutation simultanément.
Tampons de canal
L'organisation du stockage tampon au sein du commutateur a un impact important sur les performances du commutateur. Les routeurs et commutateurs traditionnels ont tendance à avoir de grands tampons SRAM ou DRAM externes à la structure du commutateur, tandis que dans les commutateurs VLSI, le tampon est interne au commutateur et provient du même budget de silicium que le chemin de données et la section de contrôle. Au fur et à mesure que la taille et la densité de la puce augmentent, plus de mémoire tampon est disponible et le concepteur de réseau a plus d'options, mais l'immobilier tampon reste un choix de premier ordre et son organisation est importante.
Contrôle de flux
Lorsque plusieurs flux de données dans le réseau tentent d'utiliser les mêmes ressources réseau partagées en même temps, certaines mesures doivent être prises pour contrôler ces flux. Si nous ne voulons perdre aucune donnée, certains des flux doivent être bloqués tandis que d'autres continuent.
Le problème du contrôle de flux se pose dans tous les réseaux et à plusieurs niveaux. Mais il est qualitativement différent dans les réseaux informatiques parallèles que dans les réseaux locaux et étendus. Dans les ordinateurs parallèles, le trafic réseau doit être fourni à peu près aussi précisément que le trafic sur un bus et il existe un très grand nombre de flux parallèles sur une très petite échelle de temps.