Communication analysis for Network-on-Chip
Final Report Abstract
Durch den steten Fortschritt in der Mikroelektronik ist es möglich, immer mehr Transistoren auf einem einzelnen Chip unterzubringen. Dies führt zu starken Änderungen im System-on-Chip (SoC) Entwurf. Designer von eingebetteten Systemen können immer mehr Komponenten wie z.B. Standard Prozessoren, DSPs, Mikrocontroller, RAM und applikationsspezifische Hardware auf einem System-on-Chip (SoC) integrieren. Die Integration von immer mehr Komponenten auf einem einzelnen Chip wird durch verschiedene Probleme begleitet, die es zu lösen gilt. So nimmt die Skalierbarkeit der Verbindungsstruktur eines System-on-Chip mit der Anzahl der integrierten Komponenten stark ab, da die bislang weit verbreiteten busbasierten Verbindungsstrukturen zwischen den einzelnen Komponenten zunehmend zu einem Flaschenhals werden. Zusätzlich werden durch die immer kleiner werdende Strukturbreite in der CMOS Technologie, welche durch die Miniaturisierung bedingt ist, die Transistoren immer anfälliger für externe Störquellen wie prozess- und zeitabhängige Variabilitäten, aber auch für elektromagnetische Effekte. Diese Probleme und die steigende Komplexität müssen durch neue Ansätze im System-on-Chip Design beherrschbar gemacht werden. Network-on-Chip-Architekturen (NoC) stellen einen viel versprechenden Ansatz dar, um die Probleme, die bei System-on-Chips durch die steigende Anzahl an Komponenten auftreten, beherrschbar zu machen. Bei Network-on-Chips werden globale Leitungen und Busse auf dem Chip durch paketvermittelte Netzwerke ersetzt. Die Vorteile von NoCs sind die gute Skalierbarkeit sowie die Verringerung der elektromagnetischen Effekte durch die regulären Verbindungsnetzwerke. Network-on-Chips können unterschiedliche Topologien wie z.B. Mesh, Torus und Hyperkubus als Verbindungsstruktur realisieren. In Network-on-Chips werden die Daten mittels Paketvermittlung weitergeleitet. Die Kommunikation zwischen den Komponenten des Network-on-Chip wird maßgeblich durch das verwendete Routingverfahren, die Topologie des Network-on-Chip sowie die Platzierung der Komponenten im Network-on-Chip beeinflusst. Durch die paketvermittelte Kommunikation in Network-on-Chips kann es zu Konflikten zwischen Kommunikationen, die den gleichen Pfad zur Kommunikation verwenden, kommen. Durch solche Konflikte der paketvermittelten Kommunikation ist die zeitliche Vorhersagbarkeit in Network-on-Chips eingeschränkt. Jedoch können Kommunikationen in einem Network-on-Chip, im Gegensatz zu Kommunikationen in einem System-on-Chip, auf unterschiedlichen Pfaden geroutet werden, so dass Konflikte beim Zugriff auf das Kommunikationsmedium verringert bzw. verhindert werden können. Hierdurch kann eine eingeschränkte zeitliche Vorhersagbarkeit in Network-on-Chips erreicht werden. Wird ein statisches Routingverfahren verwendet so können in einigen Fällen Worst-Case-Abschätzungen verwendet werden, um Echtzeitanforderungen zu überprüfen. Wird ein adaptives (dynamisches) Routingverfahren verwendet, so ist es schwer, wenn nicht sogar unmöglich, Aussagen Zusammenfassung 5 DFG-Forschungsprojekt „Communication Analysis for Network-on-Chip” über das zeitliche Verhalten des Network-on-Chip zu treffen. Dies liegt in der dynamischen Wegewahl der adaptiven Routingverfahren begründet. Um es dennoch Aussagen über das zeitliche Verhalten eines Network-on-Chip treffen zu können, wurden in diesem Projekt neue Analysemethoden erforscht, die es ermöglichen, die zeitlichen Abhängigkeiten von Inter-Prozess-Kommunikationen einer verteilten eingebetteten Anwendung in einem Network-on-Chip zu bestimmen. Dabei steht insbesondere die Analyse der Wartezeiten in blockierenden Kommunikationsendpunkten im Vordergrund, um potentielle Konflikte zwischen parallel ausführbaren Datentransfers statisch bestimmen zu können. Basierend auf den potentiellen Konflikten zwischen Kommunikationen, können die Prozesse einer eingebetteten Applikation auf die einzelnen Verarbeitungseinheiten eines Network-on-Chip applikationsspezifisch abgebildet werden. Des Weiteren kann ein statisches Routing berechnet werden, welches die potentiell konfliktbehafteten Kommunikationen auf konfliktfreien Pfaden im Network-on-Chip routet, so dass sich die Kommunikationslatenz verringert und deterministische Aussagen über das Zeitverhalten getroffen werden können. Im Gegensatz zu bisherigen Ansätzen, berücksichtigt das in diesem Projekt entwickelte Verfahren auch die Applikation, welche auf dem Network-on-Chip ausgeführt werden soll und kombiniert statische mit dynamischen Routing-Verfahren. Hierdurch ist es möglich, zeitliche Vorhersagen über den Network-on-Chip zu machen und harte Echtzeitbedingungen zu garantieren. Da eingebettete Systeme häufig in Umgebungen eingesetzt werden, in welchen sie externen Umwelteinflüssen wie z.B. Strahlung oder hohen Temperaturschwankungen ausgesetzt sind, können Fehler während der Kommunikation auftreten. Beispielsweise können Verbindungen oder Switches gestört werden oder vollständig ausfallen. Des Weiteren können solche Einflüsse zu Fehlern in den vermittelten Paketen oder zum Verlust von einzelnen Paketen führen. Um mit diesen Fehlern umgehen zu können, muss ein Routingverfahren fehlertolerant sein und dynamisch auf den Ausfall von Verbindungen und/oder Komponenten des Network-on-Chip reagieren. So kann bei einem Ausfall ein alternativer Pfad für die Vermittlung der Daten bestimmt wird. Da es dynamische Routingverfahren nur eingeschränkt ermöglichen, Aussagen über Echtzeitbedingungen zu treffen, bietet gerade die in diesem Projekt entwickelte Kombination aus statischen, applikationsspezifischem und dynamischen Routingverfahren eine wichtige Voraussetzung zur Lösung dieses Problems. Hierzu müssen die entwickelten Analysemethoden sowie das entwickelte statische konfliktfreie Routingverfahren um fehlertolerantes Verhalten erweitert werden. Dies lässt sich realisieren, indem Alternativpfade, die ebenfalls die Echtzeitbedingungen einhalten, berechnet werden und fest einzuhaltende Timing-Budgets an die dynamische Routing-Phase weitergereicht werden. Diese alternativen Pfade können im 6 Zusammenfassung Forschungsprojekt „Communication Analysis for Network-on-Chip” Fall eines aufgetretenen Fehlers verwendet werden, um das Datenpaket auf einem fehlerfreien Pfad zu routen und anhand der Timing-Budgets dynamisch die Einhaltung der Echtzeitbedingungen zu prüfen. Basierend auf den im Projekt entstandenen Analysen zur Abschätzung des Leistungsverbrauchs einzelner Tasks, kann durch Deployment der einzelnen Tasks auf Verarbeitungseinheiten einer Network-on-Chip-Architektur mittels weiterer Analyseschritte eine Temperaturverteilung auf dem Chip bestimmt werden. Diese Temperaturverteilung kann darüber hinaus als Grundlage für die Bewertung der Zuverlässigkeit eines Network-on-Chip verwendet werden. Durch die Migration einzelner Tasks auf andere Verarbeitungseinheiten der Network-on-Chip-Architektur könnte somit die Zuverlässigkeit einzelner Links, Switches und des gesamten Network-on-Chip konstruktiv erhöht werden.
