Forschungsbericht 2018 - Max-Planck-Institut für Informatik

Eindämmen von Metastabilität oder: Die Kunst, zwischen zwei gleichen Heuballen zu wählen

Autoren
Lenzen, Christoph.; Wiederhake, Ben
Abteilungen
Theorie verteilter und eingebetteter Systeme / D1 – Algorithmen und Komplexität
Zusammenfassung
Im Gegensatz zu Buridans Esel verhungern Pferde nicht, wenn man sie zwischen zwei exakt gleiche Heuballen stellt. Aber was passiert, wenn das Pferd nicht sieht, ob rechts und/oder links Heuballen sind, und wir auch nicht? Oder wenn wir nicht sehen, auf welche Seite das Pferd geht? Können wir nun zuverlässig entscheiden, ob das Pferd verhungert? Interessanterweise werden die Antworten auf diese Fragen relevant, wenn in digitalen Schaltkreisen Metastabilität auftritt. Dieser Artikel erklärt diese Begriffe, den Zusammenhang und warum es von Bedeutung ist, zu wissen, ob das Pferd verhungert.

Würde bitte jemand dieses arme Pferd füttern?

original
Abb. 1: Unentschlossenes Pferd, namens "Der Denker"

Dies ist ein Pferd mit einem existenziellen Problem: Es muss sich zwischen dem rechten und linken Heuballen entscheiden. Unser Problem ist anders gelagert: Wir müssen ermitteln, ob das Pferd verhungern wird. Offensichtlich ist die Antwort hier „nein“, da das Pferd Futter hat.

Machen wir die Aufgabe etwas schwerer. Zu jeder Seite des Pferdes kann es einen Heuballen geben oder auch nicht, und wir stellen Sichtschirme zwischen den Heuballen und dem Pferd auf. Unser armes Pferd ist schon so hungrig, dass es nicht mehr die Kraft hat, auf mehr als einer Seite nach Heu zu suchen. Was passiert nun? Wenn wir nicht auf beiden Seiten Heu haben (in diesem Fall wäre das Pferd sicher gerettet) oder wenn auf keiner der beiden Seiten Heu zu finden ist (wir sollten etwas unternehmen), können wir nicht wissen, ob sich das Pferd richtig entscheidet. Also  berücksichtigen wir auch, in welche Richtung das Pferd geht. Somit fragen wir:

  1. Geht das Pferd nach rechts und gibt es dort auch Heu?
  2. Geht das Pferd nach links und gibt es dort auch Heu?
  3. Haben wir eine der beiden vorherigen Fragen mit „ja“ beantwortet?

    Das genau leistet ein Multiplexer-Schaltkreis. Er ist ein grundlegender Baustein in digitalen Schaltkreisen, der  einen von zwei Werten auswählt  und an darauf folgende Bausteine weitergibt. Er erhält zwei Eingaben, zwischen denen gewählt wird (die Heuballen) und eine dritte „Auswahleingabe“ (wohin das Pferd geht), die bestimmt, welche Eingabe weitergeleitet wird. Wenn die Auswahleingabe also „rechts“ angibt, gibt der Multiplexer „ja“ weiter, falls die rechte Eingabe ebenso „ja“ ist und „nein“ andernfalls; wenn die Auswahleingabe „links“ angibt, gibt er „ja“ weiter, wenn die linke Eingabe „ja“ ist und „nein“ andernfalls.

    Dies ist das Hardwaregegenstück einer absolut kritischen Struktur in jedem Computerprogramm: Wenn die Auswahleingabe “rechts” angibt (bzw. je nach Benennung “wahr” oder “1”), verwende im Folgenden einen Wert, wenn sie “links” (oder “falsch” oder “0”) angibt, dagegen einen anderen. Es handelt sich also um ein Kommando wie „wenn x wahr ist, wähle a, andernfalls b“. Dementsprechend ist ein Multiplexer ein absolutes Muss in Schaltkreisen, die komplexere Berechnungen durchführen.

"Vielleicht" und warum es gefährlich ist

Bei Schaltkreisen treten aber häufig größere Probleme auf als bei Programmen.  Manchmal sind Eingaben nicht eindeutig „ja“ oder „nein“ („rechts“ oder „links“, „1“ oder „0“), sondern „vielleicht“. Das passiert, wenn die Spannung an einer Eingabe eines Schaltkreises irgendwo in der Mitte zwischen dem liegt, was als „ja“, und dem, was als „nein“ aufgefasst wird.

Doch zurück zu unserem hungrigen Pferd. „Vielleicht“ bedeutet in diesem Fall, dass es auch Sichtschirme zwischen uns und einem Heuballen oder dem hungrigen Pferd geben kann. Zum Beispiel könnten wir uns nicht sicher sein, ob ein Heuballen auf der linken Seite ist, wohingegen wir aber wissen, dass das Pferd nach rechts geht, wo ein Heuballen liegt. Somit lautet die Antwort „ja“. Wenn das Pferd nach links geht, gibt es allerdings keine Möglichkeit für uns, sicher zu sein, ob das Pferd Futter finden wird. In diesem Fall müssen wir mit „vielleicht“ antworten.

Das ist alles schön und gut, aber unser Multiplexer hat einen kritischen Schwachpunkt. Was passiert, wenn auf beiden Seiten Heuballen liegen, wir aber nicht wissen, wohin das Pferd geht, also unsere Auswahleingabe „unbekannt“ (d. h. „vielleicht“) ist? Es ist offensichtlich, dass das Pferd Futter hat, also muss die Antwort „ja“ sein. Wir erleben aber eine unangenehme Überraschung mit unserem Multiplexer:

  1. Geht das Pferd nach rechts und gibt es dort auch Heu? Vielleicht.
  2. Geht das Pferd nach links und gibt es dort auch Heu? Vielleicht.
  3. Haben wir eine der beiden vorherigen Fragen mit „ja“ beantwortet? Vielleicht.

Unser Multiplexer liefert ein falsches Ergebnis. In diesem einfachen Beispiel gibt es eine simple Korrektur durch Stellen einer zusätzlichen Frage:

  1. Geht das Pferd nach rechts und gibt es dort auch Heu? Vielleicht.
  2. Geht das Pferd nach links und gibt es dort auch Heu? Vielleicht.
  3. Liegt sowohl links als auch rechts ein Heuballen? Ja.
  4. Haben wir eine der drei vorherigen Fragen mit „ja“ beantwortet? Ja.

Somit können wir folgern, dass das Pferd etwas zu fressen finden wird, auch ohne die Entscheidung des Pferds zu kennen.

Von unschlüssigen Pferden zurück zu Elektronik

Diese Fragen sind gezielt so formuliert, dass sie durch einen Schaltkreis beantwortet werden können. In sämtlichen Fällen waren alle bis auf die letzte Frage von der Form „A oder B“, während die letzte Frage entweder die Form „A oder B“ oder „A oder B oder C“ hatte. Das entspricht genau dem, was die kleinsten Bausteine von Schaltkreisen, genannt UND- und ODER-Gatter, tun. Der Schaltkreis, der dem verbesserten Satz von Multiplexerfragen entspricht, wird als metastabilitätseindämmend bezeichnet, weil er stets die genaueste Antwort liefert, die möglich ist: Er gibt niemals „vielleicht“ aus, d. h. er hat niemals eine metastabile Ausgabe, wenn sich ein „ja“ oder „nein“ aus der Eingabe ableiten lässt.

 Der Multiplexer ist ein kleines Beispiel, in dem die Eindämmung von Metastabilität wichtig ist. Man kann ähnliche Fragen zu komplizierteren Aufgaben stellen. Konkrete Ergebnisse  im Spotlight:

  1. Wir beschreiben einen kleinen Schaltkreis, der Zeitmessungen vornimmt (eine analoge Größe) und digitale Werte ausgibt [1]. Wenn die Eingabe sich genau an der Grenze zwischen zwei Ausgaben  befindet, entsteht hier Metastabilität. Das besondere dabei ist, dass die Ausgaben, trotz Metastabilität sofort verwendet werden können, ohne dadurch Fehler zu verursachen.
  2. Ein Sortierschaltkreis, der solche Ausgaben verwenden kann und trotz Metastabilität korrekt sortiert [2]. Unser Schaltkreis ist nur marginal größer als ein kleinstmöglicher Schaltkreis ohne diese Eigenschaft!
  3. Eine generische Methode, für unkritische Berechnungen ohne vorheriges Warten „draufloszurechnen“ und eine geringe Fehlerwahrscheinlichkeit, während kritische Berechnungen immer noch sicher (aber etwas später) durchgeführt werden [3].

Existieren metastabilitätseindämmende Schaltkreise für bestimmte Aufgaben? Wenn ja, wie viel größer als reguläre Schaltkreise für die gleiche Aufgabe sind sie? Wann und in welchem Umfang ist die Eindämmung von Metastabilität sinnvoll? Mit diesen und ähnlichen Fragen beschäftigen wir uns in unserer Forschungsgruppe, um bessere Schaltkreise und letztendlich bessere Computer zu entwickeln.

1.
Fuegger, M., Kinali, A., Lenzen, C., Polzer
Symposium on Asynchronous Circuits and Systems (ASYNC), May 2017
2.
Tarawneh, G., Fuegger, M., Lenzen, C.
., Symposium on Asynchronous Circuits and Systems (ASYNC), May 2017
3.
Bund, J., Lenzen, C., Medina, M.
Design, Automation and Test in Europe (DATE), March 2018

Zur Redakteursansicht