wissenschaftliche Spielerei oder echte Alternative · 2005-05-13 · 12 A. Steininger / TU Wien Die...

A. Steininger / TU Wien1

Asynchrone Designmethoden

wissenschaftliche Spielerei oder echte Alternative ?

Huffman CircuitsDelay ModelsBounded Delay Methoden

Bundled Data & Micropipelines

Delay Insensitive MethodenTransition SignalingNull Convention LogicCode Alternation Logic

Überblick

Ein kurzes Resumee ...Boole‘sche Logik beschreibt das Input/ Output-Mappingzeitfrei. Es wird also von kontinuierlich gültigenEingängen ausgegangen

Skew verursacht aber inkonsistente Eingänge und daher ungültige Zwischenzustände

11110011110100011110101001000000

Idee: Vermeiden von SkewWenn wir stets nur je einSignal (Bit) ändern, dannkann sich auch der Skewnicht auswirken

Daten sind jederzeitkonsistent

Beispiel für Glitches

AMLKZYXW1110

1111 100

0000101111

statisch !

∆ = 4

∆ = 3

∆ = 6

∆ = 2

Huffman Circuits

„Glitchfreie“ Auslegung der Logik Einfügen redundanter Zusatzterme in derNormalform-DarstellungProbleme:

nicht alle Glitches sind vermeidbarRestriktionen für Inputs erforderlichZusatzterme = redundante Logik

F = (X ∧ ¬Y ∧ ¬Z) ∨(¬W ∧ Z) ∨ (W ∧ Y)

1 11 11 1 1 1

00 01 11 10

1 11 1 1

00 01 11 1000

(¬W ∧ Z)F = (X ∧ ¬Y ∧ ¬Z) ∨(¬W ∧ Z) ∨ (W ∧ Y)

Optimierung im KV-Diagramm

(W ∧ Y)∨ (Y ∧ Z) ∨ (¬W ∧ X ∧ ¬Y)∨ (W ∧ X ∧ ¬Z)

Restriktionen für Inputs

Fundamental Mode („Grey-Codierung“)es ändert sich immer nur ein Input-Bit

Delay in der Rückkopplung nötigZustandscodierung schwierigfür Datenpfadelemente ungeeignet

Burst ModeInputs dürfen sich gruppenweise ändern

Burst-Mode erfordert lokalen Takt

DelayElements

Combinationallogic

Outputs

NextState

CurrentState

Inputs Z1

Delay in der Rückkopplung

Probleme bei Huffman Circuits

Delay im Feedbackimpliziert Timing-Annahmen („Bounded Delay“)verlangsamt Funktion erheblich

Kompliziertes Designbei Zustandscodierung & Datenpfadelementendurch lokalen Takt im Burst-Modewegen redundanter Terme Test ?

Keine Strukturierung

keine brauchbare Gesamtlösung

Es darf nur mit konsistenten, eingeschwungenen Zuständen operiert werden

? Wie unterscheidet man konsistente Zustände von Übergangszuständen oder Glitches ?

Zeitbedingungen für Konsistenzsynchrones Designasynchrone „bounded delay“ Verfahren (Timer)

Hinzufügen von „Meta-Information“asynchrone „delay-insensitive“ Verfahren (Codierung)

Grundproblem beim Design

Die wichtigsten Delay ModelsSynchroner Fall

begrenzte Delays, a priori bekannt (min, max)

fundamental (bounded delay)Grenze für (absolute) Delays für Gatter & Leitungen angenommen

scalable-delay-insensitiveGrenze für relative Abweichung zwischen Delaysangenommen

quasi-delay-insensitiveeinzige Annahme: alle Zweige einer „Gabel“ haben gleichen Delay

delay insensitivekeine Restriktionen für Delays (nur „endlich“)

Bounded Delay Methoden

Philosophie: Wir suchen weiterhin eineLösung im Zeitbereich, allerdings wollenwir kein globales Steuersignal sondernlokale Lösungen

Erspart Probleme mit TaktverteilungErlaubt detailliertere Optimierungen

Dazu sind Annahmen / Kenntnisse überdas Zeitverhalten nötig

Synchron versus Asynchron

Synchrones Designein globales Steuersignal

(ohne Feedback !)globale Timinganalyse

Asynchrones Designviele lokale Handshakes (= Feedback)lokale Timinganalysen

comb comb

Was benötigen wir?

HandshakeTransportmedium für Handshake-Information

SpeicherHalten der Ausgängevgl. Pipelineregister

Completion detectionSteuerung von req & ack

comb comb

Bundled Data: Prinzip

Sender (REQ):"Daten gültig und dürfenverwendet werden„

Empfänger: (ACK)"Daten verarbeitet,dürfen entfernt werden"

DatenSender Emp-fänger

„explizites Handshaking“

Beispiel: Centronix-Protokoll

[Centronix Spec zu ETRAX100LX, „Fastbyte Mode“]

„REQ“

„ACK“

Bundled Data: Problem

Wie bestimmt man die Zeitpunkte „Daten gültig“ und „Daten verarbeitet“ ?

(=> Timing der Steuersignale )Lösungen:

Steuerpfad muss langsamer sein als Datenpfad:bounded Delay model (absolut)scalable delay insensitive (relativ)

kann nie delay-insensitive sein !Current Sensing

Codierung der Steuersignale

Information wird nicht über den Zustand eines Signals

dargestellt, sondern über Signalflanken („Events“)

Es gibt keine statischen DatenFlanke liefert implizit den Zeitpunkt der Gültigkeit mit, unabhängig vom Delay (!)

Zur logischen Verknüpfung Event-Logic

Implementierungsvarianten

Two-Phase HandshakeFlanke auf REQ, danach Flanke auf ACK

optimale Nutzung der Bandbreite des KanalsHW-Implementierung oft aufwendig

Four-Phase HandshakeAkt. Flanke auf REQ, dann akt. Flanke auf ACK,danach durch passive Flanken zum Ausgangszust.

Verschwendung von BandbreiteHW-Implementierung viel einfacher

Event Logic

ODER-Verknüpfung für Events:„Flanke Y“ = „Flanke A“ ODER „Flanke B“

XOR-Gate

UND-Verknüpfung für Events:„Flanke Y“ = Flanke A“ UND „Flanke B“

Muller-C-Gate

IF a = = bTHEN y = aELSE hold y

„FIFO-für Steuersignale“

AOUTRIN

Elastische Pipeline

Micropipeline mit Datenpfad

Bundled Data: Bilanz

Steuersignale kennzeichnen Gültigkeit der Daten, Übergabe mittels asynchronem HandshakeMit Event-Logik lässt sich eine „elastische“Pipeline für Steuersignale aufbauen

Probleme bleibenTiming/Routing der SteuersignaleFeststellung der Gültigkeit der Daten

Timing der Steuersignale

bisher:ein Steuersignal (REQ) beschreibt die Gültigkeit der gesamten Daten („bundled data“)dies impliziert die Forderung, dass REQ längere Laufzeit hat als die Daten (=> Delay-Elemente)ein solches Design ist nie Delay-insensitive

besser:jede Datenleitung beschreibt ihre Gültigkeit selbst

Gültigkeit der Daten

Feststellung der Gültigkeit / Konsistenzder Daten erfolgt mittels Delay/Timer

Mit einfachen Delay-Elementen erzielt man wie im synchronen System keine konzeptionell saubere Lösung(worst-case,…)Delay-Faults sind extrem kritisch.

Die Zeit als Maß aller Dinge ?

TreppenhauslichtAnwesenheit auf der Treppe

MikrowelleTemperatur/Garzustand der Speise

3-Minuten-EiKonsistenz des Dotters

AmpelAnzahl wartender Autos

IntervallschalterSicht durch die verregnete Scheibe

Konsistenz aus Zeitbedingung?

Taktperiode (synchrones Design)Delay (bounded Delay)

… sind ein indirektes und daher aus konzeptioneller Sicht problematisches/ungeeignetes Maß für die Gültigkeit und Konsistenz der Daten

Können wir Datenkonsistenz nicht direkt feststellen??

Es darf nur mit konsistenten, eingeschwungenen Zuständen operiert werden

? Wie unterscheidet man konsistente Zustände von Übergangszuständen oder Glitches ?

Zeitbedingungen für Konsistenzsynchrones Designasynchrone „bounded delay“ Verfahren (Timer)

Hinzufügen von „Meta-Information“asynchrone „delay-insensitive“ Verfahren (Codierung)

Grundproblem beim Design

Wie codiere ich „ungültig“ ?

Transition Signaling für die Daten selbstHI und LO nur als „Events“ darstellbarje eine Leitung für HI und LOEvent auf einer Leitung setzt entspr. Zustand

„Mehrwertige“ statische Logikim Pegelbereich nicht etabliertDarstellung eines Bits auf 2 digitalenLeitungen erlaubt 4 Zustände

Transition Signaling - BeispielA0

Y = A or B

A=0 A=1

B=1B=0

Y1 Y=1 Y=1

Transition Signaling – GrenzenDelay insensitive circuits können nur unter folgenden Einschränkungen entworfen werdenBuffer, Inverter, Wires und C-Elements sind die einzig zulässigen single-output GatesAND, OR, XOR, etc. sind daher nicht zulässigMulti-Output Gates (intern bounded delay) günstig

Scott Hauck, „Asynchronous Design Methodologies – An Overview“Proceedings of the IEEE, vol 83, no 1, pp 69-93, Jan. 1995

Wie codiere ich „ungültig“ ?

Transition Signaling für die Daten selbstHI und LO nur als „Events“ darstellbarje eine Leitung für HI und LOEvent auf einer Leitung setzt entspr. Zustand

„Mehrwertige“ statische Logikim Pegelbereich nicht etabliertDarstellung eines Bits auf 2 digitalenLeitungen erlaubt 4 Zustände

Mehrwertige Logik

Die in der NULL-Convention Logic ver-wendete 3-wertige Logik umfasst dieZustände:

True (T) False (F) NULL (N)Das ermöglicht es, gemeinsam mit denNutzdaten auch Steuerinformation zuübermitteln.

„implizites Handshaking“

Logische Funktionen für NCL

NNNNNFFFNFTTNFTAND

NNNNNFTFNTTTNFTOR

NNTFFT

Completeness of Input–CriteriaDer Ausgang bleibt immer solange auf NULL, bisauch der letzte Eingang gültig (= ungleich NULL) ist.In einer mit NULL initialisierten Schaltung läuft eine „wavefront“ mit gültigen Werten von den Eingängen zu den AusgängenDie Synchronisation läuft selbständig und völlig unabhängig von Verzögerungen abDieses Prinzip lässt sich ohne weitere Maßnahmen vom einzelnen Gatter auf ein komplettes System erweitern.

Completen. of Input – Beispiel

AMLKZYXWNNNN

11N0 01N

0NN0NN

NNNNNNNNN0

N1N011N0

010010

∆ = 4

∆ = 3

∆ = 6

∆ = 2

Bereitschaft für neue Daten...

...besteht erst, wenn auch der letzteInput wieder NULL ist.Der Output geht aber mit dem erstenNULL-Input wieder auf NULLEs sollen aber immer abwechselnd DATA-wellen und NULL-Wellen durch die Schaltung laufen Wie erkennen wir die „completeness of input“ für die NULL-Wellen ??

Completen of NULL – Problem

AMLKZYXW1110

1111 NN0

NN0NN0

0N0010111N

111N111N

100100

Waren die anderen Ein-gänge wirklich konstant oder nur langsamer ??

∆ = 4

∆ = 3

∆ = 6

∆ = 2

Rückkopplung vom Ausgang

„Feedback-Gate“mit Hysterese-Verhalten

TTTTTTNFFFFFFFFNFFNFTNNNNNFTNFTNFTNFTNFTNFTNFTNFTN

FTNFTNFTNTFN

Timing!!

Completen. of NULL – Lösung

AMLKZYXW1110

NN1N NN0

N10N10

010010111N

1N1NNN1N

NNNNNN

∆ = 4

∆ = 3

∆ = 6

∆ = 2

Datenkonsistenz in NCLDurch das Alternieren von NULL- und DATA-Wellen ist jede konsistente DATA-Welle durchzwei NULL Wellen ( = vorne und hinten)eingerahmt.

FALSENULLt

Konsistent DATAKonsistent NULLA

Codierung des Alphabets

im Pegelbereich nicht etabliertDarstellung eines Bits auf 2 Leitungen:

grundsätzl. beliebig(1 aus n , 2-rail, etc.) kosteneffizient sind 2 SignalleitungenBeispiel: 2-rail-coding

verboten11FALSE01TRUE10NULL00BedeutungX1X0

Signal X

Bedingungen an die Codierung

Vertauschbarkeit der Reihenfolgebeim Übergang von einem gültigen Codewort auf das nächste darf kein Zwischenzustand ein gültiges Codewort darstellen

Ist noch eine Flanke ausständig ?

Garantiertes Auftreten eines EventsBeim Übergang von einem Codewort auf das nächste muss zumindest eine Flanke auftreten

Neues oder altes Codewort ?

Vertauschbarkeit der Reihenfolgebeim Übergang von einem gültigen Codewort auf das nächste darf kein Zwischenzustand ein gültiges Codewort darstellenNCL: Nur 1 Bit Änderung von N auf T / F

Garantiertes Auftreten eines EventsBeim Übergang von einem Codewort auf das nächste muss zumindest eine Flanke auftretenNCL: Rückkehr zu NULL vorgeschrieben (!)

Gatter in NCL

NULL Convention Logic: Bilanz

NCL ist eine elegante, durchgängige,delay-insensitive Design-Methode(Direkte) Completion detection ist möglichStrukturierung ist möglich durch RegisterHW-Aufwand: zwei Leitungen je BitEffizienz: Die NULL-Wellen halbieren denproduktiven DurchsatzPatentiert und industriell verwendet

Code Alternation Logic

Grundidee: Anstelle der unproduktiven NULL-Wellen produktive Daten in anderer Codierung („Phase“) übertragen:

konsistent Phase Φ0konsistent Phase Φ1

FALSENULL

NCLCAL

Zustandscodierung in CAL

(1,0)(0,1)Φ1(1,1)(0,0)Φ0HILO

Zustand

Darstellung eines Signals auf 2 Leitungen (a,b) („two-rail coding“)

Vertauschbarkeit der Reihenfolgebeim Übergang von einem gültigen Codewort auf das nächste darf kein Zwischenzustand ein gültiges Codewort darstellenBei jedem Übergang ändert sich genau ein Bit

Garantiertes Auftreten eines EventsBeim Übergang von einem Codewort auf das nächste muss zumindest eine Flanke auftretenBei jedem Übergang ändert sich genau ein Bit

Gatter in CAL

Wahrheitstabelle CAL-AND

HL**HLL**L**hlh**lllHLhlY

L, H, l, h für E1, E2 und Y laut CAL Tabelle* … Halten des letzten gültigen Wertes an Y

Completion Detection in CALEin konsistentes Datenwort in CAL ist vonDatenworten in anderer Phase eingerahmt.

Completion Detection in CALEin konsistentes Datenwort in CAL ist vonDatenworten in anderer Phase eingerahmt.Zur Feststellung der Konsistenz muss für jedesBit die Phase ermittelt werden. Dies kann beiCAL sehr einfach durch ein XOR erfolgen.

(1,0)(0,1)Φ1(1,1)(0,0)Φ0HILO

a = ba ≠ b

Completion Detection in CALEin konsistentes Datenwort in CAL ist vonDatenworten in anderer Phase eingerahmt.Zur Feststellung der Konsistenz muss für jedesBit die Phase ermittelt werden. Dies kann beiCAL sehr einfach durch ein XOR erfolgen.Bits mit gleicher Phase gehören zum gleichenDatenwortDiese Konsistenzprüfung ist direkt undkonzeptionell sauber.

Code Alternation Logic: Bilanz

CAL ist eine elegante, durchgängige,delay-insensitive Design-Methode(Direkte) Completion detection ist möglichStrukturierung ist möglich durch RegisterHW-Aufwand: zwei Leitungen je BitEffizienz: Im Vergleich zu NCL doppelter produktiver DurchsatzPatentiert

Zusammenfassung (1)

Asynchrones Design verwendet lokalenHandshake (Feedback) anstelle einesglobalen TaktesDie Bundled-Data Methode

verwendet Steuersignale (expliziter Handshake)ist sehr effizient, leitet die Konsistenz aus einer Zeitbedingung abist bestenfalls scalable delay insensitive

Zusammenfassung (2)

MicropipelinesSind eine effiziente Methode zur Strukturierung asynchroner Designsbieten eine elastische Pipeline für Steuersignalebieten per se keine Completion Detection

Transition Signaling für Datenist konzeptionell geeignet für delay insensitivebietet nur eingeschränkte Funktionalitätist extrem schwierig zu designen

Zusammenfassung (3)

Null Convention Logic (NCL)verwendet dreiwertige Logikbenötigt daher zwei Leitungen je Signalist konzeptionell elegantBeruht auf einem Alternieren von DATA-Wellen und NULL-Wellenist daher nur beschränkt effizient

Zusamenfassung (4)

Code Alternation Logic (CAL)verwendet je zwei unterschiedliche Codierungen für HI und LObenötigt daher 2 Leitungen je Signalberuht auf einem Alternieren der Phasenist geeignet für delay insensitiveist doppelt so effizient wie NCL

Die Methode Zukunft ?Asynchrones Design bietet große Vorteile, aber

keine Vereinfachungen wie im synchronen Falldie Design-Methoden sind weniger ausgereiftdie bestehenden Design-Tools sind ungeeignetdie bestehende Technologie ist schlecht geeignetes gibt wenig Erfahrung (Robustheit, Test)Ingenieure sind in synchronem Design ausgebildet

Evolution statt Revolution:

GALS-Architekturen (Globally Asynchronous / Locally Synchronous): Räumlich kleine synchrone Funktionsblöcke kommunizieren asynchron

wissenschaftliche Spielerei oder echte Alternative · 2005-05-13 · 12 A. Steininger / TU Wien Die...

Documents

Chirurgische Therapie (synchroner) kolorektaler ... · Hierbei muss für jeden Patienten individuell ein Konzept erstellt werden, das die Resektion des Primarius, die Resektion der

Lieblings-Apps der Deutschen: Facebook führt klar Rangliste der Downloads in Millionen 2015 Quelle: Priori Data Hinweis: Aufgrund von Vorinstallationen

Infos, Tipps und Inspirationen aus einer Hand - PRIORI …priori-reisen.de/wp-content/uploads/2014/10/Reisehandbuch_PRIORI.V... · Wie viel kostet…? Ohatrinona…? Odschin (Sehr)

A priori Tests (Kontraste) Nicht-parametrischer Vergleich ... · IOW-Statistikseminar: 4. Veranstaltung Carola Wagner & Anja Eggert Statistische Methoden in den Umweltwissenschaften

Strukturgleichungsmodell. Einleitung: Was sind Strukturgleichungsmodelle? mit ihnen werden anhand empirischer Daten a priori formulierte Kausalhypothesen

Satter Datendurchsatz auf dem Chip - exemark.com · pischer synchroner Arbiter ist z.B. ein Zustandsautomat, ... struktur erreicht. ... Anforderungen ergeben

Schaltungen mit Delays - RWTH Aachen University

Regelung dynamischer Systeme mit stochastischer ... · design of controllers for input delay systems with stochastically varying time delays. Static and Static and adaptive control

Klausur - Philipps-Universität Marburgloogen/Lehre/ws07/TechInf1/06Klausur.pdf · Ein synchroner Modulo-7-Zähler soll als Moore-Automat realisiert werden. a) Stellen Sie den Zustandsgraphen

Überblick Wiederholung Ergänzungen Wahrheitsbegriff - analytisch / synthetisch - a priori / a posteriori Wissensideal, Gegenstandsverständnis, Aufgabenverständnis

Thomas Herrmann Kommunikation und Kooperation mit Groupware 2000 24.02.2000 1 Synchroner Austausch von Text am Beispiel Internet Relay Chat -Konferenzartige

e g n n n Modellen - uni-magdeburg.de · 2 Bayes-Methode bei vollständiger a-priori-Information Dadie hiervorgestellteMethodezur empirischenBayes-Schätzungaufder Bayes—Schätzungbei

ZUR ISOLIERUNG, ZWANGSVERHEIRATUNG UND … · definition angewiesen. Nur ein Kulturverständnis, das nicht a priori an den globalen Kapital-zentren orientiert ist, sondern ambiguitätstolerant

Probabilistic Estimation of Unobserved Process Events · analysts detect delays and react to deviations from the expected or guaranteed performance of a process instance. To enable

Kapitel 3: KlassifikationKapitel 3: Klassifikation · Bayes als bedingte Wahrscheinlichkeiten formuliert A-Priori-Wahrscheinlichkeiten modellieren Faktenwissen über dieWahrscheinlichkeiten

Konzert - Ashra - The Official Website · Mick Glossop (Produzent u.a. von John Lee Hooker, Zappa, Van Morrison) für Virgin Records gemixt: „I had been using rhythmic tape delays

Bayessche Statistik - jeti.uni-freiburg.dejeti.uni-freiburg.de/studenten_seminar/stud_sem07/BayesRef2.pdf · Einleitung Wahl der a priori Verteilung Bezug zur Maximum Likelihood Methode

Informations- visualisierung€¦ · Präsentation Zu präsentierenden Fakten sind a priori festgelegt. Visualisierungsprozess besteht aus Auswahl geeigneter Präsentationstechniken

New X-Code - Dauphin · 2018. 12. 13. · X-Code SX Syncro-Motion X® ö Seitliche, schnelle Feineinstellung des Rückenlehnengegen - drucks mit wenigen Umdrehungen ö Synchroner

Thomas Herrmann Kommunikation und Kooperation mit Groupware 11.4.2000 1 2) Unterstützung synchroner Kommunikation 2.1) Aufbau und Modifizierung von Audio-