A non-blocking fault-tolerant asynchronous networks-on-chip router

Abstract

Die Gesamtleistung der heutigen komplexen Systems-on-Chip (SoCs) wird entscheidend durch die Leistungsfähigkeit der Networks-on-Chip (NoCs) bestimmt. Die zunehmende Verkleinerung der Halbleiter-Strukturgrößen ermöglicht hier zwar immer höhere Taktraten, stellt jedoch gleichzeitig das übliche global synchrone Paradigma vor wachsende Herausforderungen. Hierzu zählt die Verteilung des Taktsignals über den gesamten Chip ebenso wie die Beherrschung der signifikanten Variationen der Signallaufzeiten. Im Gegensatz dazu basieren asynchrone Schaltungen auf Handshakes, womit sie Probleme mit dem Takt elegant vermeiden. Gleichzeitig erlauben sie einen effizienten Umgang mit Prozessvariationen und sogar dynamisch auftretenden Veränderungen von Laufzeitparametern. Das Interesse an asynchronen Schaltungen nimmt daher stark zu, und auch wir konzentrieren uns in dieser Arbeit auf asynchrone NoCs. Ein entscheidender Vorteil von NoCs gegenüber traditionellen Busstrukturen ist ihre Fähigkeit, über verschiedene Pfade parallel Nachrichten zu übertragen. Das Blockieren eines Pfades ist in diesem Kontext unerwünscht, da es mit gravierenden Leistungseinbußen und dem Verlust der Echtzeitfähigkeit verbunden ist. Demgemäß beschäftigt sich die Literatur auch ausführlich mit nicht-blockierendem Verhalten, allerdings nicht immer in korrekter Weise. So konnten wir zeigen, dass einige existierende Lösungen einen sicheren Datenaustausch nicht immer garantieren können. Ein Ergebnis unserer Arbeit ist daher ein Framework, welches notwendige Bedingungen zur Konstruktion eines nicht-blockierenden NoCs definiert. Wir zeigen die Korrektheit unseres Frameworks anhand des Entwurfes eines neuen NoC Protokolls, welches nicht nur alle funktionalen Anforderungen erfüllt, sondern auch den Leistungsverbrauch auf langen Verbindungen reduziert und die Anforderungen an die Bandbreite lockert. Eine weitere Folge der Miniaturisierung ist eine erhöhte Anfälligkeit von Chips gegenüber transienten Fehlern. Ursache dafür sind kleinere Transistor-Geometrien sowie niedrigere Spannungspegel, was zu geringeren kritischen Ladungen führt. Dem entsprechend wächst auch die Bedeutung von Fehlertoleranz. Asynchrone NoCs enthalten allerdings einige Komponenten, für welche die konventionelle Fehlertoleranzmethode der Replikation nicht bzw. nicht effizient eingesetzt werden kann. Ein Beispiel hierfür sind Arbiter, die auf nicht deterministische Weise den Zugriff auf geteilte Ressourcen regeln. Das zweite wesentliche Ergebnis dieser Arbeit ist daher der systematische Schutz einiger dieser Komponenten, insbesondere eines Arbiters, vor transienten Fehlern. Außerdem präsentieren wir das Design eines vollständigen fehlertoleranten Routers, welcher zudem einen hochperformantenArbiter enthält. Zur Evaluierung unseres Designs verwenden wir funktionale Verifikation anhand von teilautomatisierten post-layout Simulationen, gepaart mit formaler Verifikation mittels Model Checking.

It is well understood that the throughput of Networks-on-Chip (NoCs) is decisive for the performance of today's complex Systems-on-Chip (SoCs). On the one hand, proceeding miniaturization has allowed these systems to operate at ever increasing clock rates, on the other hand, however, the globally synchronous designs face certain challenges that are difficult to overcome for recent technology nodes. This includes the distribution of clocks across a complete chip, and robustness against delay variations. The handshake based style of control flow in asynchronous communication style naturally eliminates the need for a global clock, and at the same time provides an inherent ability to adapt to uncertainties and even dynamic changes of timing parameters. Because of these reasons, they are receiving increasing attention in the embedded systems community, and for the same reason we will also concentrate on asynchronous NoCs in this work. A crucial advantage of NoCs over traditional bus structures is the ability to perform several independent message transfers in parallel, namely along different routes. In this situation blocking of a link is highly undesired, as it severely degrades performance and real time capabilities of a NoC. A very important property of a NoC is therefore non-blocking behavior. The latter is widely addressed in literature, but unfortunately not always correctly understood and presented. We will show that a few existing solutions do not guarantee a safe data exchange between two communicating entities. One contribution of our work, therefore, is to present a framework that precisely elaborates the minimum requirements of building a nonblocking NoC.We also demonstrate the correctness of our framework by proposing a novel solution that not just satisfies all the functional requirements, but reduces the power consumption on long interconnects, and relaxes the bandwidth requirements. Another undesired consequence of the miniaturization process is the higher susceptibility of VLSI circuits to transient faults, which is due to the smaller geometries and lower supply voltages which in turn reduce the critical charge. Fault tolerance is therefore predicted to become a crucial property in context with future technologies. As far as asynchronous NoCs are concerned, they comprise several such circuits that cannot be made fault-tolerant by using conventional replication techniques. One such circuit is an arbiter that allows resource sharing in a nondeterministic manner. Therefore the second major contribution of this work is to systematically harden a few of those circuits, including an arbiter cell. Other than these, we also present the design of a complete fault-tolerant asynchronous router, which in addition promises high speed resource sharing capability. Our evaluation is partially supported with formal verification using model checking, and partially using post layout functional verification based on Modelsim scripts.