Interconnection Network Design

Ein interconnection networkIn einer parallelen Maschine werden Informationen von einem beliebigen Quellknoten zu einem beliebigen Zielknoten übertragen. Diese Aufgabe sollte mit möglichst geringer Latenz abgeschlossen werden. Es sollte möglich sein, dass eine große Anzahl solcher Übertragungen gleichzeitig stattfindet. Darüber hinaus sollte es im Vergleich zu den Kosten des Restes der Maschine kostengünstig sein.

Das Netzwerk besteht aus Links und Switches, mit deren Hilfe die Informationen vom Quellknoten zum Zielknoten gesendet werden können. Ein Netzwerk wird durch seine Topologie, seinen Routing-Algorithmus, seine Vermittlungsstrategie und seinen Flusssteuerungsmechanismus spezifiziert.

Organisatorische Struktur

Verbindungsnetzwerke bestehen aus folgenden drei Grundkomponenten:

• Links- Eine Verbindung ist ein Kabel aus einer oder mehreren Glasfasern oder elektrischen Drähten mit einem Anschluss an jedem Ende, der an einen Switch oder einen Netzwerkschnittstellenanschluss angeschlossen ist. Dadurch wird ein analoges Signal von einem Ende gesendet und am anderen empfangen, um den ursprünglichen digitalen Informationsstrom zu erhalten.

• Switches- Ein Switch besteht aus einer Reihe von Eingangs- und Ausgangsanschlüssen, einer internen „Querleiste“, die alle Eingänge mit allen Ausgängen, der internen Pufferung und der Steuerlogik verbindet, um zu jedem Zeitpunkt die Eingangs- / Ausgangsverbindung herzustellen. Im Allgemeinen entspricht die Anzahl der Eingangsports der Anzahl der Ausgangsports.

• Network Interfaces- Die Netzwerkschnittstelle verhält sich ganz anders als Switch-Knoten und kann über spezielle Links verbunden werden. Die Netzwerkschnittstelle formatiert die Pakete und erstellt die Routing- und Steuerinformationen. Es kann im Vergleich zu einem Schalter eine Eingangs- und Ausgangspufferung haben. Es kann eine durchgehende Fehlerprüfung und Flusskontrolle durchführen. Daher werden seine Kosten durch die Verarbeitungskomplexität, die Speicherkapazität und die Anzahl der Ports beeinflusst.

Verbindungsnetz

Verbindungsnetzwerke bestehen aus Vermittlungselementen. Die Topologie ist das Muster zum Verbinden der einzelnen Switches mit anderen Elementen wie Prozessoren, Speichern und anderen Switches. Ein Netzwerk ermöglicht den Datenaustausch zwischen Prozessoren im Parallelsystem.

• Direct connection networks- Direkte Netzwerke haben Punkt-zu-Punkt-Verbindungen zwischen benachbarten Knoten. Diese Netzwerke sind statisch, was bedeutet, dass die Punkt-zu-Punkt-Verbindungen fest sind. Einige Beispiele für direkte Netzwerke sind Ringe, Maschen und Würfel.

• Indirect connection networks- Indirekte Netzwerke haben keine festen Nachbarn. Die Kommunikationstopologie kann basierend auf den Anwendungsanforderungen dynamisch geändert werden. Indirekte Netzwerke können in drei Teile unterteilt werden: Busnetzwerke, mehrstufige Netzwerke und Crossbar-Switches.

  • Bus networks- Ein Busnetz besteht aus mehreren Bitleitungen, an die mehrere Ressourcen angeschlossen sind. Wenn Busse dieselben physischen Leitungen für Daten und Adressen verwenden, werden die Daten- und Adressleitungen zeitmultiplexiert. Wenn mehrere Busmaster an den Bus angeschlossen sind, ist ein Arbiter erforderlich.

  • Multistage networks- Ein mehrstufiges Netzwerk besteht aus mehreren Switch-Stufen. Es besteht aus 'Axb'-Schaltern, die über ein bestimmtes Interstage-Verbindungsmuster (ISC) verbunden sind. Kleine 2x2-Switch-Elemente sind eine häufige Wahl für viele mehrstufige Netzwerke. Die Anzahl der Stufen bestimmt die Verzögerung des Netzwerks. Durch Auswahl verschiedener Verbindungsmuster zwischen den Stufen können verschiedene Arten von mehrstufigen Netzwerken erstellt werden.

  • Crossbar switches- Ein Crossbar-Schalter enthält eine Matrix einfacher Schalterelemente, die ein- und ausgeschaltet werden können, um eine Verbindung herzustellen oder zu trennen. Durch Einschalten eines Schalterelements in der Matrix kann eine Verbindung zwischen einem Prozessor und einem Speicher hergestellt werden. Crossbar-Switches sind nicht blockierend, dh alle Kommunikationspermutationen können ohne Blockierung durchgeführt werden.

Bewertung von Design-Kompromissen in der Netzwerktopologie

Wenn das Hauptanliegen die Routing-Entfernung ist, muss die Dimension maximiert und ein Hypercube erstellt werden. Beim Store-and-Forward-Routing muss unter der Annahme, dass der Grad des Switches und die Anzahl der Links kein wesentlicher Kostenfaktor waren und die Anzahl der Links oder der Switch-Grad die Hauptkosten sind, die Dimension minimiert und ein Netz erstellt werden gebaut.

Im schlimmsten Fall ist es für jedes Netzwerk bevorzugt, hochdimensionale Netzwerke zu haben, in denen alle Pfade kurz sind. In Mustern, in denen jeder Knoten nur mit einem oder zwei benachbarten Nachbarn kommuniziert, werden niedrigdimensionale Netzwerke bevorzugt, da nur einige der Dimensionen tatsächlich verwendet werden.

Routing

Der Routing-Algorithmus eines Netzwerks bestimmt, welcher der möglichen Pfade von der Quelle zum Ziel als Routen verwendet wird und wie die Route bestimmt wird, der jedes bestimmte Paket folgt. Das Routing für Dimensionsreihenfolgen begrenzt die Anzahl der zulässigen Pfade, sodass von jeder Quelle zu jedem Ziel genau eine Route vorhanden ist. Diejenige, die erhalten wird, indem zuerst die richtige Strecke in der Dimension höherer Ordnung zurückgelegt wird, dann die nächste Dimension und so weiter.

Routing-Mechanismen

Arithmetik, quellenbasierte Portauswahl und Tabellensuche sind drei Mechanismen, mit denen Hochgeschwindigkeits-Switches den Ausgabekanal aus Informationen im Paket-Header bestimmen. Alle diese Mechanismen sind einfacher als die Art der allgemeinen Routing-Berechnungen, die in herkömmlichen LAN- und WAN-Routern implementiert sind. In parallelen Computernetzwerken muss der Switch die Routing-Entscheidung für alle seine Eingaben in jedem Zyklus treffen, daher muss der Mechanismus einfach und schnell sein.

Deterministisches Routing

Ein Routing-Algorithmus ist deterministisch, wenn die von einer Nachricht genommene Route ausschließlich von ihrer Quelle und ihrem Ziel bestimmt wird und nicht von anderem Verkehr im Netzwerk. Wenn ein Routing-Algorithmus nur kürzeste Pfade zum Ziel auswählt, ist er minimal, andernfalls nicht minimal.

Deadlock-Freiheit

Deadlock kann in verschiedenen Situationen auftreten. Wenn zwei Knoten versuchen, Daten aneinander zu senden, und jeder beginnt zu senden, bevor einer der beiden empfängt, kann ein "frontaler" Deadlock auftreten. Ein weiterer Fall eines Deadlocks tritt auf, wenn mehrere Nachrichten im Netzwerk um Ressourcen konkurrieren.

Die grundlegende Technik zum Nachweis, dass ein Netzwerk frei von Deadlocks ist, besteht darin, die Abhängigkeiten zu löschen, die zwischen Kanälen aufgrund von Nachrichten auftreten können, die sich durch die Netzwerke bewegen, und zu zeigen, dass das gesamte Kanalabhängigkeitsdiagramm keine Zyklen enthält. Daher gibt es keine Verkehrsmuster, die zu einem Deadlock führen können. Der übliche Weg, dies zu tun, besteht darin, die Kanalressourcen so zu nummerieren, dass alle Routen einer bestimmten zunehmenden oder abnehmenden Sequenz folgen, so dass keine Abhängigkeitszyklen entstehen.

Schalterdesign

Das Design eines Netzwerks hängt vom Design des Switches und davon ab, wie die Switches miteinander verdrahtet sind. Der Grad des Switches, seine internen Routing-Mechanismen und seine interne Pufferung entscheiden, welche Topologien unterstützt und welche Routing-Algorithmen implementiert werden können. Wie jede andere Hardwarekomponente eines Computersystems enthält ein Netzwerk-Switch Datenpfad, Steuerung und Speicher.

Häfen

Die Gesamtzahl der Pins entspricht der Gesamtzahl der Eingangs- und Ausgangsports multipliziert mit der Kanalbreite. Da der Umfang des Chips im Vergleich zum Bereich langsam wächst, sind die Schalter in der Regel stiftbegrenzt.

Interner Datenpfad

Der Datenpfad ist die Konnektivität zwischen jedem der Eingangsports und jedem Ausgangsport. Es wird allgemein als interne Querstange bezeichnet. Ein nicht blockierender Querbalken ist einer, bei dem jeder Eingangsport in jeder Permutation gleichzeitig mit einem bestimmten Ausgang verbunden werden kann.

Kanalpuffer

Die Organisation des Pufferspeichers innerhalb des Switches hat einen wichtigen Einfluss auf die Switch-Leistung. Herkömmliche Router und Switches verfügen in der Regel über große SRAM- oder DRAM-Puffer außerhalb der Switch-Struktur, während bei VLSI-Switches die Pufferung innerhalb des Switches erfolgt und aus demselben Siliziumbudget wie der Datenpfad und der Steuerabschnitt stammt. Mit zunehmender Chipgröße und -dichte steht mehr Pufferung zur Verfügung und der Netzwerkdesigner hat mehr Optionen. Dennoch ist die Pufferimmobilie die erste Wahl, und ihre Organisation ist wichtig.

Ablaufsteuerung

Wenn mehrere Datenflüsse im Netzwerk versuchen, dieselben gemeinsam genutzten Netzwerkressourcen gleichzeitig zu verwenden, müssen einige Maßnahmen ergriffen werden, um diese Flüsse zu steuern. Wenn wir keine Daten verlieren möchten, müssen einige der Flüsse blockiert werden, während andere fortfahren.

Das Problem der Flusskontrolle tritt in allen Netzwerken und auf vielen Ebenen auf. In parallelen Computernetzwerken ist dies jedoch qualitativ anders als in lokalen und Weitverkehrsnetzen. Bei parallelen Computern muss der Netzwerkverkehr ungefähr so ​​genau wie der Verkehr über einen Bus geliefert werden, und es gibt eine sehr große Anzahl paralleler Flüsse in sehr kleinem Zeitrahmen.