Network on Chip

Network on Chip (NoC) beschreibt zunächst die Adaption von Netzwerken auf einen Chip. Es wird also bei einem NoC nicht Wert auf den Prozessortyp an sich gelegt, sondern auf die Struktur und Logik, wie die Prozessoren (IP-Cores) verbunden sind. Die ersten Many-Core-Chips wurden schon mit einem NoC gefertigt und der Trend geht ganz klar in Richtung NoC.

Warum?

Nun, warum ist das so? Warum weg von Bussystemen und Point-to-Point-Verbindungen? Der Grund liegt eigentlich auf der Hand: Ein Bussystem ist ein extremer Flaschenhals, sobald viele (sagen wir mal über 60) Cores miteinander kommunizieren wollen. Bei Point-to-Point-Verbindungen übersteigen schlicht die Kosten den Nutzen. Es ist, wenn man so will, der nächste Schritt ein Netzwerk als Verbindung zu verwenden, da hier die Kosten, Schnelligkeit und Skalierbarkeit ganz klar hervorstechen. Jedoch gibt es auch bei NoCs Unterschiede, auf die ich nun eingehen möchte.

Topologien

Eine Topologie beschreibt die Struktur eines Netzes. Dabei kann die Struktur sehr unterschiedlich ausfallen. Für NoCs wird meistens eine Mesh-Struktur verwendet.



Eine Abwandlung davon ist eine Torus-Sturktur, hier werden die Enden eines Meshes miteinander verbunden, sodass es kein Ende gibt.



Weitere, die eigentlich nicht bei NoCs vorkommen:

Stern



Butterfly




Mesh (hier 3D)



CCC (Cube Connected Cycles, 3D)



Es können natürlich auch 3D-Topologien auf einen 2D-Chip abgebildet werden, jedoch gehen dadurch einige Vorteile verloren, da z.B. ein Link über den kompletten Chip gezogen werden muss. Da sich bei großer Knotenzahl auch verschiedene Nachteile einschleichen (z.B. bei Stern würde der zentrale Knoten extreme Last tragen müssen) sind eben Meshes die momentan bevorzugte Topologie bei NoCs.

Aufbau Knoten

Wie sehen nun solche Knoten aus? In der Regel haben bei Mesh die Knoten jeweils 5 Input- und Output-Ports (außer natürlich die äußeren Kantenknoten): North, West, East, South und Center (zum IP-Core). Hier merkt man, dass der Knoten prinzipiell ein Router ist und der Core "nur" eine mögliche Richtung zu routen. Zwischen Core und Router ist dann meist noch etwas wie ein Network-Interface. Dort werden dann die Befehle vom Core in Pakete gepackt und an den Router weiter gereicht. Natürlich kann man das auch per Hardware und/oder Software direkt am Core regeln.
Der Router ist vom Routing-Algorithmus abhängig, jedoch sind die Komponenten im allgemeinen ähnlich: Zum einen jeweils die Ports und zum anderen eine zentrale Einheit, die die Routing-Entscheidungen trifft. An den Ports kann jeweils ein Speicher, bzw. Buffer existieren - jedoch könnten hier ein mehrere Buffer angebracht werden (Stichwort: Virtual Channels). So wird pro Zyklus vom Inport-Speicher die Nachricht zum Outport-Speicher geschrieben (falls keine zwei Nachrichten zum selben Ausgang wollen).

Switching

Swiching bezeichnet hier die Art, wie Pakete (genauer gesagt: Flits) weitergereicht werden; dazu wird die Routing-Entscheidung schon vorausgesetzt. Flits ist die "Einheit" an Bits, die in einem Zyklus übertragen werden kann. Pakete können verschiedene Größen haben, je nach Protokoll. Die Verbindung zwischen den verschiedenen Knoten lässt allerdings z.B. nur 32 Bit zu. Somit ist es notwendig die Pakete in (hier 32 Bit große) Flits aufzubrechen. Nun gibt es eben verschiedene Möglichkeiten diese Flits zu übertragen. Man kann bei der Übertragung warten, bis der andere Knoten genug Platz hat um das komplette Paket zwischen zu speichern und es dann flit-weise übertragen. Das ist nicht gewünscht, da man dadurch genug Buffer-Speicher zur Verfügung stellen muss, damit man für jeden Input-Port die komplette Nachricht zwischen speichern kann. Eine gängige Methode ist das Wormhole-Switching. Hier kann man sich das Paket als einen Flit-Wurm vorstellen, der einen Kopf (head) und einen Schwanz (tail) hat. Es wird beim Head-Flit ein Kanal zwischen den beiden Knoten geöffnet, der sich erst mit dem Tail-Flit wieder schließt (auch hier Stichwort: Virtual Channels). Somit kann das Head-Flit schon einige Knoten weiter sein, als das Tail-Flit. Allgemeines zu diesem Thema findet man unter dem Stichwort "flow control".

Routing

Beim Routing muss man versuchen drei Dinge zu beachten: Vermeidung Deadlock, Vemeidung Livelock und möglichst optimaler Weg. Warum "möglichst" optimaler Weg? Es kann bei Auslastung passieren, dass ein Paket auf seinen optimalen Weg beharrt und dabei erst andere Pakete Vorrang haben. So muss das Paket warten. Nun kann es sinnvoller sein, einen nicht optimalen Weg zum Ziel zu gehen und dennoch schneller dort zu sein - eben wegen dieser möglichen Blockade.
Ein Livelock kann bei nicht-minimalen Routing-Algorithmen vorkommen, falls also das Paket nicht seinen optimalen Weg geht. Dieses Paket wird zwar weitergesendet, jedoch kommt es dabei seinen Ziel nicht näher. Eine Vermeidung ist durch einen Hop-Count (Anzahl der Sprünge von Knoten zu Knoten) recht einfach zu realisieren.
Ein Deadlock kann entstehen, falls Pakete sich gegenseitg blockieren. Dabei sind dann durch den Algorithmus alle Turns (Richtungswechsel) erlaubt und ein Paket könnten im Netzwerk einen Kreis gehen (Stichwort: turn model). Eine Vermeidung kann man durch eine Einschränkung der Turns erreichen, oder auch durch garantierte Freigabe der Ressourcen pro Zyklus. Deadlock-Bild:



Als kleine Beispiele möchte ich zwei Routing-Algorithmen vorstellen - einen deterministischen und einen nicht deterministischen:

Das XY-Routing ist einer der simpelsten deterministischen Routing-Algorithmen. Es werden die Pakete zuerst in X-Richtung zum Ziel geroutet und dann in Y-Richtung. Somit existieren "nur" 4 von 8 möglichen Turns und ein Deadlock ist ausgeschlossen. Jedoch werden bei diesem Algorithmus vor allem die äußeren Knoten stark frequentiert, wodurch meist "Staus" bei Volllast entstehen. Unnötig - vor allem wenn man sich vor Augen hält, dass es bei einem Mesh-Netzwerk meist mehrere optimale Wege zum Ziel existieren.

Das Deflection-Routing (oder: deflective routing) ist ein nicht deterministischer "Algorithmus" (eher ein Prinzip) - sprich: es ist nicht vorhersagbar welchen Weg das Paket nehmen wird. Bei diesem Algorithmus werden in einem Zyklus alle Flits (Packete=Flits, da kein fester Weg existiert) geroutet, egal ob optimaler Weg oder nicht optimaler. Somit ist pro Port nur noch ein Speicher für ein Flit notwendig (Kosten-, Platz- und Energieersparnis). Unter der Prämisse, dass das Flit sofort geroutet wird, muss priorisiert werden: Welches Flit darf seinen optimalen Weg gehen, falls mehrere diesen Weg gehen wollen? Dies geschieht meist über den Hop-Count. Wer schon länger im Netzwerk ist, darf optimal gehen. Dabei zu beachten ist auch wieder die Struktur des Netzes: Meistens gibt es zwei günstige Wege für ein Flit (X- und Y-Richtung). So könnte man noch teil-priosieren, was jedoch stark auf die konkrete Implementierung ankommt. Da nun alle Inport-Flits einen höheren Hop-Count haben, als das Core-Flit, kann der Core bei voller Last eventuell keine Flits senden (außer ein Flit ist für den Core bestimmt, dadurch wird ein Output-Port "frei").

Natürlich gibt es noch weitere Algorithmen und weitere Möglichkeiten ein NoC zu entwerfen. Einen wirklichen "sanften" Einstieg in das Thema habe ich nicht gefunden, jedoch kann ich "Principles and practices of interconnection networks" empfehlen. Man kann auch mal mit einem der zahllosen NoC-Simulatoren spielen und sich in deren Quellcode einlesen (z.B. Nirgam, Soclib, etc.).