(:requiretuid:)

Einführung in TGDI – Kapitel 3

Autoren: Anna Wenzelburger, Moritz Fischer, Patrick Meyn

Dieses Kapitel beginnt mit der Vorstellung von Latches und Flip-Flops, danach beschäftigen wir uns mit dem Entwurf synchroner Logik, Endlichen Zustandsautomaten, dem Zeitverhalten sequentieller Logik und schließlich wird Parallelität erklärt.

Einleitung

Ausgänge sequentieller Logik hängen ab von:

• aktuellen Eingabewerten
• vorherigen Eingabewerten

Sequentielle Schaltungen speichern einen internen Zustand.

Definitionen:

• ein Zustand ist eine interne Information, aus denen das weitere Schaltungsverhalten hergeleitet werden kann
• Latches und Flip-Flops sind Speicherelemente für jeweils einen 1 Bit Zustand
• Synchrone sequentielle Schaltungen bestehen aus kombinatorischer Logik gefolgt von Flip-Flops

Sequentielle Schaltungen

Sequentielle Schaltungen können Folgen von Ereignissen bearbeiten. Sie haben ein "Gedächtnis", das in der Regel nur eine Kurzzeitgedächtnis ist.

Sie benutzen Rückkopplungen von Logikausgängen zu Logikeingängen um Informationen zu speichern. Durch das Vorhandensein von Rückkopplungen sind sie keine kombinatorischen Schaltung mehr!

Zustandselemente

Bei Zustandselementen beeinflusst der Zustand einer Schaltung das zukünftige Verhalten

Speicherelemente speichern den Zustand. Solche Speicherelemente sind zum Beispiel:

• Bistablie Schaltungen
• SR Latches
• D Latches
• D Flip-Flops

Diese werden auch manchmal Zustandselemente genannt.

Bistabile Grundschaltung

Bistabile Grundschaltungen sind ein fundamentaler Baustein für andere Speicherelemente.

Diese haben:

1. zwei Ausgänge:
2. keine Eingänge

Analyse der bistabilen Grundschaltung

Es gibt zwei Möglichkeiten, welcher der beiden Ausgänge WAHR sein kann:

• und
• und

In beiden Fällen ist die Grundschaltung konsistent und stabil.

Eine bistabile Schaltung speichert 1 Zustandsbit in den Zustandsvariablen oder

Bisher gibt es keine Eingänge, um diesen Zustand zu beeinflussen. Dazu erweitern wir die Schaltung im Folgenden.

SR (Setzen/Rücksetzen) Latch

Die hier zu betrachtenden Fälle sind:

• , dann gilt

• , dann gilt

• , dann gilt (Hier wird der Wert gespeichert!)

• , dann gilt

Dies ist ein ungültiger Zustand, da

Schaltplansymbol für SR Latch

SR steht für Setzen/Rücksetzen(engl. set/reset). Das heißt, man kann die Werte setzen bzw. rücksetzen. Der ein Bit Zustand wird in der Variablen Q gespeichert.

Das Festlegen des gespeicherten Wertes geschieht über die Eingänge S und R.

• Set: Setze Ausgang auf 1, d.h.
• Reset: Zurücksetzen des Ausgangs auf 0, d.h.

Dabei gibt es einen illegalen Zustand, der zu vermeiden ist. Es darf niemals gelten: S = R = 1.

D Latch

D Latches haben zwei Eingänge: CLK und D. Dabei steuert:

• CLK: wann sich der Ausgang ändert (clock, Taktsignal)
• D (der Dateneingang): auf was sich der Eingang ändert

Die Funktionalität eines D Latches ist:

• Wenn CLK = 1, dann wird D an Q weitergereicht (das Latch ist transparent)
• Wenn CLK = 0, dann behält Q seinen vorherigen Wert (das Latch ist opak (undurchsichtig))

Der illegale Fall kann hier nicht mehr auftreten.

Interner Aufbau eines D Latches

D Flip-Flop

Ein D Flip-Flop hat zwei Eingänge: CLK und D. Das Flip-Flop liest den aktuellen Wert von D bei einer steigenden Flanke von CLK. Wenn CLK von 0 nach 1 steigt, so wird D weitergegeben an Q. Ansonsten behält Q seinen vorherigen Wert. Das heißt, dass Q sich nur ändert, wenn CLK eine steigende Flanke hat. Man sagt auch, dass ein Flip-Flop flankengesteuert (edge-triggered) ist.

Interner Aufbau eines D Flip-Flops

Ein D Flip-Flop besteht aus zwei Latches, die in Serie geschaltet sind (L1 und L2). Diese werden gesteuert durch komplementäre Taktsignale.

• Wenn CLK = 0

• Wenn CLK = 1

Bei steigender Flanke von CLK (also einem Wechsel von 0 -> 1) wird D an Q weitergegeben.

Vergleich von einem D Latch mit einem D Flip-Flop

Das Diagramm zeigt das Zeitverhalten der beiden Schaltelemente. Es wird deutlich, dass ein D Latch einen Wechsel von D übernimmt, solange CLK = 1 ist. Im Gegensatz dazu übernimmt das D Flip-Flop nur bei einer steigenden Taktflanke von CLK den Wert von D.

Register

Flip-Flops mit Taktfreigabesignal (clock enable)

Flip-Flops mit Taktfreigabesignal haben drei Eingänge: CLK, D und EN. Der Freigabeeingang (EN, enable) steuert, wann neue Daten (D) gespeichert werden.

• EN = 1

• EN = 0

Zurücksetzbare Flip-Flops

Zurücksetzbare Flip-Flops haben drei Eingänge: CLK, D und Reset.

• Reset = 1

• Reset = 0

Dabei gibt es zwei Arten von Resets:

• synchroner Reset: Das Rücksetzen geschieht zur steigender Taktflanke, wenn Reset = 1
• asynchroner Reset: Das Rücksetzen geschieht sofort bei Reset = 1

Setzbare Flip-Flops

Setzbare Flip-Flops haben die Eingänge CLK, D und Set

• Set = 1

• Set = 0

Sequentielle Logik

Bei sequentieller Logik hängt der Ausgang von dem aktuellen und dem vorherigen Werten ab. Außerdem hat sequentielle Logik ein "Gedächtnis". Sequentielle Schaltungen sind alle nicht-kombinatorischen Schaltungen.

Diese merkwürdige Schaltung hat keine Eingänge und 3 Ausgänge (die Knoten X, Y und Z). Diese instabile Schaltung oszilliert . Dabei hängt die Periode von der Inverterverzögerung ab. Diese variiert mit dem Herstellungsprozess, der Temperatur usw. Diese Schaltung hat einen Zyklus: Der Ausgang ist rückgekoppelt auf den Eingang.

Entwurf synchroner sequentieller Logik

Bei synchroner sequentieller Logik wird die Rückkopplung durch Einfügen von Registern aufgebrochen. Diese Register halten den Zustand der Schaltung. Dabei ändert sich der Zustand nur zur Taktflanke . Die Schaltung wird also mit der Taktflanke synchronisiert.

Regeln für den Aufbau von synchronen sequentiellen Schaltungen:

• Jedes Schaltungselemt ist entweder ein Register oder eine kombinatorische Schaltung
• Mindestens ein Schaltungselement ist ein Register
• Alle Register werden durch das gleiche Taktsignal gesteuert
• Jeder Zyklus enthält mindestens ein Register

Zwei weit verbreitete synchrone sequentielle Schaltungen sind:

• Endliche Zustandsautomaten (Finite State Machines, FSMs)
• Pipelines (manchmal Fließbandverarbeitung genannt)

Endliche Zustandsautomaten (FSM)

FSM bestehen aus:

• Zustandsregister

• Kombinatorische Logik

Der nächste Zustand hängt vom aktuellen Zustand und den Eingangswerten ab.

Die Ausgangswerte werden üblicherweise auf eine von zwei Arten bestimmt:

• Moore FSM: Ausgänge hängen nur vom aktuellen Zustand ab
• Mealy FSM: Ausgänge hängen vom aktuellen Zustand und den Eingangwerten ab

Beispiel für einen endlichen Zustandsautomaten

Wir betrachten hier das Beispiel einer Ampelsteuerung. Die Ampelsteuerung hat zwei Induktionsschleifen: . Diese sind TRUE wenn Autos detektiert werden. Außerdem steuert sie zwei Ampeln:

Endlicher Automat: Außenansicht (black blox)

Dieser endliche Automat hat 4 Eingänge: CLK, Reset, und zwei Ausgänge:

Zustandsübergangsdiagramm der FSM

Bei einem Moore FSM werden die Ausgangswerte den Zuständen zugeordnet. Die Zustände werden als Kreise dargestellt und die Übergänge als Pfeile.

Zustandsübergangstabelle

Die Zustandübergangstabelle kann man relativ leicht ablesen:

Wir betrachten als aktuellen Zustand, den Zustand S0. Dieser hat als Eingang nur und ist unabhängig von . kann dabei die Werte 0 und 1 annehmen. Jenachdem ist der nächste Zustand ein anderer. Wenn so ist der nächste Zustand S1. Ansonsten bleibt er S0. So betrachtet man jeden Zustand und kann damit die letzte Spalte ausfüllen.

Zustandsübergangstabelle mit binärkodierten Zuständen

Hier kodieren wir die Zustände binär. Damit kann man dann die boole'sche Funktion bestimmen, die diesen Automaten beschreibt.

FSM Ausgangstabelle

FSM Schaltplan: Zustandsregister

FSM Schaltplan: Zustandsübergangslogik

FSM Schaltplan: Ausgangslogik

FSM Zeitverhalten: Timing-Diagramm

Zustandskodierung in endlichen Automaten

Die Zustandskodierung kann binär erfolgen. Zum Beispiel für vier Zustände: 00, 01, 10, 11.

Es ist auch möglich einen 1-aus-N Code (One-hot encoding) zu verwenden. Dieser funktioniert folgendermaßen:

• Ein Zustandsbit pro Zustand
• Zu jedem Zeitpunkt ist genau ein Zustandsbit gesetzt
• z.B. für vier Zustände 0001, 0010, 0100, 1000
• Benötigt zwar mehr Flip-Flops
• ... aber die Zustandübergangs- und Ausgangslogiken sind häufig kleiner und schneller.

Vergleich von Moore- und Mealy-Automaten

Wir betrachten die Unterschiede an Hand einer Erkennung der Bitfolge 1101 auf einem Lochstreifen.

Zustandsübergangsdiagramme

Moore-Automate: Zustandsübergangstabelle

Moore-Automat: Ausgangstabelle

Mealy-Automat: Zustandsübergangstabelle

Moore-Automat: Schaltplan

Mealy-Automat: Schaltplan

Moore- und Mealy-Automaten: Zeitverhalten

Zerlegen von Zustandsautomaten

Das Aufteilen komplexer FSMs in einfachere interagierende FSMs wird auch manchmal Dekomposition genannt. Ein Beispiel ist eine um einen Modus für Festumzüge erweiterte Ampelsteuerung. Dabei bekommt der FSM zwei weitere Eingänge: F und R. Und es gilt:

• F = 1 aktiviert Festumzugsmodus: Die Ampeln für den Bibliotheksweg bleiben grün
• R = 1 deaktiviert den Festumzugsmodus

FSM mit Festumzugsmodus

Zustandsübergangsdiagramm für unzerlegte FSM

Zustandsübergangsdiagramm für zerlegte FSM

Entwurfsverfahren für endliche Automaten

Hier eine Schritt für Schritt Anleitung, wie man endliche Automaten entwirft:

• Definiere die Ein- und Ausgänge
• Zeichne ein Zustandsdiagramm
• Stelle eine Zustandsübergangstabelle auf
• Kodiere die Zustände (binär, one-hot, ...)
• Für Moore-Automaten gilt dabei:

• Für Mealy-Automaten gilt:

Für beide Automatentypen gilt dann:

• Stelle Boole'sche Gleichungen für Zustandsübergangs- und Ausgangslogiken auf
• Entwerfe einen Schaltplan aus Gattern und Registern

Zeitverhalten von sequentiellen Schaltungen

Bei sequentiellen Schaltungen übernimmt das Flip-Flop die Daten von D zur steigenden Taktflanke. Dabei darf D sich nicht ändern, wenn es übernommen (sampled) wird. Man sagt auch, D muss stabil sein. Ähnlich wie bei einer Fotographie darf keine Bewegung zum Auslösezeitpunkt stattfinden, sonst das Ergebnis unscharf wird. D darf sich also nicht zur Taktflanke ändern, da dies zu Metastabilität führen kann.

Um es genauer auszudrücken: D darf sich nicht in einem gewissen Zeitfenster um die Taktflanke herum ändern.

Zeitanforderungen an Eingangssignale

• Setup-Zeit:

• Hold-Zeit:

• Abtastzeit:

• 

Zeitanforderungen an Ausgangssignale

Die Laufzeitverzögerung (propagation delay) ist das Zeitintervall nach der Taktflanke, nach dem Q garantiert stabil ist. Q ändert sich danach also nicht mehr.

Die Kontaminationsverzögerung (contamination delay) ist das Zeitintervall nach der Taktflanke, nach dem Q beginnen könnte, sich zu ändern

Dynamische Entwurfsdisziplin

Die Eingänge in einer synchronen Schaltung müssen in der ganzen Abtastzeit stabil sein. Genauer gesagt, sie müssen stabil sein, mindestens

• ... ab vor der Taktflanke
• ... bis nach der Taktflanke

Die Verzögerung zwischen Registern hat einen Maximal- und Minimalwert. Dabei ist sie abhängig von der Verzögerung der kombinatorischen Schaltelemente.

Anforderung an Setup-Zeit

Das Einhalten der Setup-Zeit hängt von der Maximal-Verzögerung von Register R1 durch kombinatorische Logik ab. Dabei muss der Eingang zu dem Register mindestens ab vor der Taktflanke stabil sein.

Anforderungen an Hold-Zeit

Das Einhalten der Hold-Zeit hängt von der minimalen Verzögerung von Register R1 durch die kombinatorische Logik ab. Dabei muss der Eingang an Register R2 mindestens bis nach der Taktflanke stabil sein.

Analyse des Zeitverhaltens

Beheben der verletzten Hold-Zeitanforderung

Taktverschiebung (clock skew)

Der Takt kommt nicht bei allen Registern zur gleichen Zeit an. Das liegt an unterschiedlichen Verdrahtungswegen auf dem Chip oder Logik in den Taktsignalen (gated clock, vermeiden!). Dabei ist die Verschiebung (oder Versatz, skew) die Differenz der Ankunftszeit zwischen zwei Registern.

Überprüfe dabei, ob auch bei maximalem Versatz die dynamische Entwurfsdisziplin noch eingehalten wird.

Setup-Zeitanforderungen mit Taktverschiebung

In diesem Beispiel ist CLK2 früher altiv als CLK 1.

Hold-Zeitanforderungen mit Taktverschiebung

In diesem anderen Fall gilt: CLK2 könnte später als CLK1 aktiviert werden.

Verletzung der dynamischen Entwurfsdisziplin

Asynchrone Eingänge können die dynamische Disziplin verletzen. Ein Beispiel dafür sind Benutzereingaben.

Metastabilität

Jedes bistabile Element hat zwei stabile Zustände und einen metastabilen dazwischen. Ein Flip-Flop-Ausgang hat zwei stabile Zustände (0 und 1) und einen metastabilen Zustand. Falls das Flip-Flop den metastabilen Zustand annimmt, kann es dort für unbetimmte Zeit verbleiben.

Interner Aufbau eines Flip-Flop

Ein Flip-Flop hat intern Rückkopplungen. Falls Q zwischen 1 und 0 liegt:

• ... wird es von den kreuzgekoppelten Gattern irgendwann auf 1 oder 0 getrieben
• Je nachdem, an welchem Spannungspegel es näher lag

• Ein Signal wird als metastabil bezeichnet, wenn es noch nicht zu 1 oder 0 aufgelöst wurde.

Zeitdauer der Metastabilität

Wenn der Flip-Flop EIngang D zu einem zufälligen Zeitpunkt innerhalb der Abtastzeit wechselt, wird der Ausgang Q nach einer zufälligen Zeit t_res zu 0 oder 1 aufgelöst (resolved).

Für die Wahrscheinlichkeit, dass der Ausgang Q nach einer Wartezeit t noch metastabil ist, gilt:

: Zeit um Ausgang sicher nach 1 oder 0 aufzulösen
: Eigenschaft der Schaltung
: Taktperiode

Intuitiv interpretieren wir diese Formel folgendermaßen:

• ist die Wahrscheinlichkeit, dass ein Eingang zu einem ungünstigen Zeitpunkt, also innerhalb der Abtastzeit, schaltet. Diese sinkt mit wachsender Taktperiode .
• Die Zeitkonstante gibt an, wie schnell sich das Flip-Flop aus dem metastabilen Zustand wegbewegen kann. Sie hängt von der Verzögerung durch die kreuzgekoppelten Gatter ab.

Grob gesagt heißt das: Wenn man nur lange genug wartet, wird der Ausgang sicher zu 0 oder 1 aufgelöst.

Synchronisierer (synchronizer)

Asynchrone Eingänge (D) lassen sich praktisch nicht ganz vermeiden:

• Benutzerschnittstellen
• Systeme mit mehreren interagierenden Taktsignalen

Ziel eines Synchronisierers ist es daher die Wahrscheinlichkeit für einen metastabilen Zustand zu reduzieren und mit hoher Wahrscheinlichkeit gültige Werte an Q zu liefern. Dennoch kann Metastabilität aber nie völlig ausgeschlossen werden.

Der interne Aufbau eines Synchronisierers besteht aus einer Reihenschaltung von Flip-Flops.

Wir nehmen nun an, dass der Eingang während derAbtastzeit von Flip-Flop F1 wechselt.

Die Synchronisation gelingt, wenn Signal D2 innerhalb von (T_c - t_setup) zu 0 oder 1 aufgelöst wird.

Für die Wahrscheinlichkeit des Scheiterns der Synchronisation gilt für jede Änderung des Eingangs D:

Daraus können wir nun eine Formel für die Mittlere Betriebsdauer zwischen Ausfällen (mean time between failures, MTBF) herleiten.
Bei einer Änderung des Eingangssignals einmal pro Sekunde ist die Ausfallwahrscheinlichkeit des Synchronisierers pro Sekunde P(Scheitern). Bei einer Änderung des Eingangssignals N-mal pro Sekunde gilt für die Ausfallwahrscheinlichkeit des Synchronisierers pro Sekunde:

Im Durchschnitt scheitert die Synchronisation also alle 1/[P(Scheitern)/s] Sekunden. Dies bezeichnen wir als Mittlere Betriebsdauer zwischen Ausfällen (MTBF).

Beispielrechnung

Annahmen:

Rechnung:

Parallelität

Wir unterscheiden zwei Arten von Parallelität:

• Räumliche Parallelität: Vervielfachte Hardware bearbeitet mehrere Aufgaben gleichzeitig
• Zeitliche Parallelität: Die Aufgabe wird in mehrere Unteraufgaben aufgeteilt. Diese werden parallel ausgeführt. Ein Beispiel dafür ist das Fließbandprinzip bei der Autofertigung. Es gibt nur eine Station für einen Arbeitsschritt, aber alle unterschiedlichen Arbeitsschritte für mehrere Autos werden parallel ausgeführt. Zeitliche Parallelität wird auch Pipelining genannt.

Definitionen:

• Datensatz: Vektor aus Eingabewerten, die zu einem Vektor aus Ausgabewerten bearbeitet werden
• Latenz: Zeit von der Eingabe eines Datensatzes bis zur Ausgabe der zugehörigen Ergebnisse
• Durchsatz: Die Anzahl von Datensätzen die pro Zeiteinheit bearbeitet werden können

Man verwendet Parallelität, um den Durchsatz zu erhöhen.

Um das Konzept der Parallelität zu verdeutlichen, wollen wir sie hier am Beispiel "Plätzchen backen" anwenden.

Wir beginnen naiv und backen Plätzchen zuerst seriell. Wir nehmen an, dass genügend Teig da ist. Zum bestücken eines Blechs mit Teig benötigen wir 5 Minuten. Die Backzeit beträgt 15 Minuten. Wir bereiten ein Blech nach dem anderen vor und backen es. Somit ergibt sich:

Die Latenz beschreibt also die Zeit, die ein Blech braucht, um den "Produktionsprozess" vollständig zu durchwandern.
Der Durchsatz gibt an wie viele Plätzchen wir in einer gewissen Zeit produzieren können.

Wir elaborieren nun unseren Produktionsprozess und wenden das Konzept der räumlichen Parallelität an.
Wir nehmen an, dass wir, anstatt alleine zu backen, nun zwei Bäcker(Ben & Alyssa) haben, beide mit eigenem Ofen.

Die Latenz bleibt unverändert, aber unser Durchsatz verbessert sich deutlich.

Eine weitere Möglichkeit zur Steigerung der Plätzchenproduktion ist die zeitliche Parallelität. Die Teilaufgabe "Blech bestücken" können wir für das nächste Blech durchführen, während das vorherige im Ofen ist.

Die Latenz bleibt wieder gleich und unser Durchsatz ist:

Zeitliche und räumliche Parallelität können auch miteinander kombiniert werden. Wenn wir zwei Öfen haben und das nächste Blech bestücken, während das alte gebacken wird, können wir sogar auf einen Durchsatz von 8 Blechen/h kommen.

Pipelining

Kehren wir nun zurück zu elektronischen Schaltungen. Auch hier können wir das Konzept der zeitlichen Parallelität anwenden. Wir nennen dies Pipelining. Betrachen wir zunächst eine Schaltung ohne Pipelining.

• Kritischer Pfad durch Elemente 2, 3, 4: 9 ns
• t_setup = 0,2 ns und t_pcq = 0,3 ns T_c = 9 + 0,2 + 0,3 = 9,5 ns
• Latenz = 9,5 ns; Durchsatz = 1 / 9,5 ns = 105 MHz

Durch Pipelining können wir nun den Durchsatz dieser Schaltung erhöhen. Wir teilen, durch das Einfügen von Registern, die kombinatorische Logik in zwei Teile. Somit erhalten wir eine Schaltung mit zweistufiger Pipeline.

• Stufe 1: 3 + 2 + 0,2 + 0,3 = 5,5 ns
• Stufe 2: 4 + 0,2 + 0,3 = 4,5 ns
• T_c = 2 Takte = 11 ns
• Durchsatz = 1 / 5,5 ns = 182 MHz

Nun müssen wir nicht mehr warten bis ein Datum die ganze kombinatorische Logik durchwandert hat, sondern können bereits, wenn es in Element 4 angekommen ist, die Elemente der Stufe 1 für das nächte Datum verwenden. Der Durchsatz steigt deutlich. Die Latenz hat sich aber auch etwas erhöht. Wir fügen eine weitere Stufe ein und erhalten eine dreistufige Pipeline.

• T_c = 4,5 ns
• Latenz = 3 Takte = 13,5 ns
• Durchsatz = 1 / 4,5 ns = 222 MHz

Das Einfügen von Pipelinestufen hat Auswirkungen auf Durchsatz und Latenz. Mehr Pipelinestufen bedeutet:

• Höherer Durchsatz (mehr Ergebnisse pro Zeiteinheit)
• aber auch höhere Latenz (länger warten auf das erste Ergebnis)

Pipelining lohnt sich nur, wenn viele Datensätze bearbeitet werden müssen.

Pipelining lässt sich jedoch nicht immer anwenden. Oftmals führen Abhängigkeiten der Teilaufgaben zu Problemen. In unserem Keksbeispiel wollen wir vielleicht erstmal schauen wie ein Blech geworden ist, bevor wir das nächste bestücken.

Selbsttest

1 Ein D Latch übernimmt den neuen wert...? Sobald er angelegt wirdBei CLK = 0Bei CLK = 1Bei steigender TaktflankeBei fallender TaktflankeBei D = 1

2 Ein D Flip-Flop übernimmt den neuen wert...? Sobald er angelegt wirdBei CLK = 0Bei CLK = 1Bei steigender TaktflankeBei fallender TaktflankeBei D = 1

3 Jede Schaltung, die ein Register enthält, ist eine synchrone sequentielle Schaltun. RichtigFalsch

4 Beim Mealy Automaten hängen die Ausgänge nur vom aktuellen Zustand ab. RichtigFalsch

5 Zeitliche Parallelität ...? verringert lediglich die Zeit die der erste Datensatz für das vollständige Durchlaufen der Pipeline benötigterhöht die Menge an Daten, die in einem gegebenen Zeitraum bearbeitet werden können.Verbessert Durchsatz und Latenz

(:antwortchecker:)