DE60130039T2

DE60130039T2 - Fifo-schaltungen mit geringer latenz für gemischte asynchrone und synchrone systeme

Info

Publication number: DE60130039T2
Application number: DE60130039T
Authority: DE
Inventors: Tiberiu New York CHELCEA; Steven M. Leonia NOWICK
Original assignee: Columbia University in the City of New York
Current assignee: Columbia University in the City of New York
Priority date: 2000-06-09
Filing date: 2001-06-08
Publication date: 2008-05-15
Anticipated expiration: 2021-06-09
Also published as: AU2001266808A1; KR100761430B1; WO2001095089A3; JP2011227919A; JP2004510216A; CA2412438A1; CN1478226A; EP1374032B1; DE60130039D1; KR20030066333A; ATE370448T1; WO2001095089A2; JP4849763B2; EP1374032A2; CN100429616C; JP5379826B2

Description

QUERVERWEIS AUF VERWANDTE ANMELDUNGEN
Diese Anmeldung beansprucht Priorität gegenüber der vorläufigen U.S. Patentanmeldung mit dem Titel "Low-Latency FIFO for Mixed-Clock Systems", Serial No. 60/210642, welche am 9. Juni 2000 eingereicht wurde, welche hierin in ihrer Gesamtheit durch Bezugnahme beinhaltet ist.
HINTERGRUND DER ERFINDUNG
GEBIET DER ERFINDUNG
Diese Erfindung betrifft FIFO-Schaltungen und insbesondere FIFO-Konstruktionen mit geringer Verzögerung, die eine Schnittstelle zwischen Subsystemen bilden, die mit unterschiedlichen Geschwindigkeiten arbeiten und die synchron oder asynchron sein können, und zwischen Subsystemen mit sehr langen Zwischenverbindungsverzögerungen.
STAND DER TECHNIK
Ein Trend in der VLSI läuft zunehmend auf ein "System auf einem Chip" hinaus, welches mehrere Taktbereiche enthält. Ein herausforderndes Problem besteht in der robusten Verknüpfung dieser Bereiche. Es gab bisher wenige hinreichende Lösungen, insbesondere solche, welche eine zuverlässige Kommunikation mit geringer Latenz bereitstellen.
Es gibt zwei fundamentale Herausforderungen bei der Konstruktion von Systemen auf einem Chip. Eine erste Herausforderung betrifft Systeme, die unter unterschiedlichen Zeittaktannahmen arbeiten. Diese Zeittaktannahmen beinhalten unterschiedliche Taktgeschwindigkeiten, sowie sowohl synchrone als auch asynchrone Umgebungen. Eine zweite Herausforderung betrifft Konstruktionen mit langen Verzögerungen in der Kommunikation zwischen Systemen.
Es wurde bereits eine Anzahl von FIFO-Schaltungen und Komponenten entwickelt, um die Zeittaktunterschiede zwischen den Subsystemen zu behandeln. Einige Konstruktionen sind auf die Beherrschung von Ein-Takt-Systemen beschränkt. Diese Konzepte wurden vorgeschlagen, um Taktversetzungen, Driften und Jitter (R. Kol et al., "Adaptive Synchronization for Multi-Synchronous System", IEEE International Conference an Computer Design (ICCD'89), pp. 188–189, October 1998; and M. Greenstreet, "Implementing a STARI Chip", Proceedings IEEE International Conference an Computer Design (ICCAD, 1999), pp. 38–45, 1995) zu behandeln. Um lange Zwischenverbindungsverzögerungen zu behandeln, wurden bereits "Latenz-unempfindliche Protokolle" vorgeschlagen (L. Carloni et al., "A Methodology for Correct-by-Construction Latency Insensitive Designs", ICCAD, 1999); deren Lösung jedoch auf nur einen einzigen Taktbereich beschränkt war.
Einige Konstruktionen wurden auch bereits zur Beherrschung gemischter Zeittaktbereiche vorgeschlagen. Eine Kategorie von Konstruktionskonzepten versucht, Datenelemente und/oder Steuersignale mit dem Empfänger zu synchronisieren, ohne mit dessen Takt in Beziehung zu treten. Insbesondere verknüpft Seizovic robust asynchrone mit synchronen Umgebungen, über ein "Synchronisations-FIFO". (J. Seizovic, "Pipeline Synchronization", Proceedings International Symposium an Advanced Research in Asynchronous Circuits and Systems, pp. 87–96, November 1994. Jedoch ist die Verzögerung dieser Konstruktion proportional zu der Anzahl von FIFO-Stufen, deren Implementation teuere Synchronisatoren beinhaltet. Ferner erfordert diese Konstruktion, dass der Sender Datenelemente mit einer konstanten Rate erzeugt.
Weitere Konstruktionen erzielen eine robuste Schnittstellenverbindung von Misch-Takt-Systemen, indem sie kurzzeitig den Empfängertakt modifizieren. Synchronisationsfehler werden vermieden, indem der lokale Takt des Empfängers ausgesetzt oder gedehnt wird. Jedes kommunizierende synchrone System ist von einer asynchronen Logik umgeben, welche für die Kommunikation mit den anderen Systemen und für die Anpassung der Takte verantwortlich ist. Dieses Konzept verändert die Takte der lokalen Systeme und kann Latenzprobleme bei deren Neustart induzieren.
Jerry Jex et al. U.S. Patent Nr. 5 598 113 beschreibt eine Mischtakt-FIFO-Schaltung. Jedoch weist die in '113 beschriebene FIFO-Schaltung einen deutlich größeren Flächenbedarf bei der Implementation der Synchronisation auf. Beispielsweise besitzt diese Konstruktion zwei Synchronisatoren für jede Zelle.
EP 0 645 696 (Tokyo Shibura Electric Co; Toshiba Micro Electronics) offenbart einen Halbleiterspeichervorrichtung unter Verwendung eines seriellen Zeigers.
ISCC 93 G3/Session 16/Static Memories/Paper FA 16-1, Fenstermaker et al.: "A Low Power Generator-Based FIFO..." offenbart ein FIFO mit seriellen Zeigern und einer Leerdetektion, durch Vergleichen der Zeiger.
EP 606 600 offenbart eine Voll/Leer-Anzeige in einer einzelnen FIFO-Zelle für eine Durchfallkontrolle.
Demzufolge besteht im Fachgebiet ein Bedarf nach einer FIFO-Schaltung mit geringer Latenz und hohem Durchsatz und die in gemischten synchronen/asynchronen Umgebungen betrieben werden kann.
ZUSAMMENFASSUNG DER ERFINDUNG
Eine Aufgabe der vorliegenden Erfindung besteht in der Bereitstellung einer FIFO-Schaltung mit geringer Latenz und hohem Durchsatz.
Eine weitere Aufgabe der Erfindung besteht in der Bereitstellung einer FIFO-Schaltung, die in gemischten synchronen/asynchronen Umgebungen nützlich ist.
Eine weitere Aufgabe der vorliegenden Erfindung besteht in der Bereitstellung einer FIFO-Schaltung, welche als eine Relaisstation in Verbindung mit langen Verzögerungen und gemischten synchronen/asynchronen Umgebungen verwendet werden kann.
Noch eine weitere Aufgabe der vorliegenden Erfindung besteht in der Bereitstellung von FIFO-Schaltungskomponenten, welche zur Verwendung in einem speziellen Betriebsprotokoll, d.h., synchron oder asynchron konfiguriert sind, und welche in Verbindung mit anderen Komponenten unabhängig von dem Betriebsprotokoll der anderen Komponenten eingesetzt werden können.
Diese und weitere Aufgaben der Erfindung, welche unter Bezugnahme auf die Offenbarung hierin ersichtlich werden, werden durch eine FIFO-Schaltung gelöst, welche eine Schnittstelle für die Übertragung von Datenelementen zwischen einem unter einem ersten Betriebsprotokoll arbeitenden Sendersubsystem und einem unter einem zweiten Betriebsprotokoll arbeitenden Empfängersubsystem bereitstellt.
Eine Geberschnittstelle ist dafür konfiguriert, gemäß dem ersten Betriebsprotokoll zu arbeiten und weist einen Geberdatenbus zum Übertragen eines Datenelementes aus dem Sendersubsystem und einen Geberdaten-Anforderungseingang zum Empfangen einer Geberanforderung von dem Sendersystem auf, um das Datenelement aus dem Geberdatenbus in eine Warteschlange einzugeben. Eine Nehmerschnittstelle ist dafür konfiguriert, gemäß dem zweiten Zeitbereich zu arbeiten und weist einen Nehmerdatenbus auf, um das Datenelement an das Empfängersubsystem zu übertragen und einen Nehmerdaten-Anforderungseingang, um eine Nehmeranforderung aus dem Empfängersubsystem zu empfangen, um das Datenelement aus der Warteschlange an den Nehmerdatenbus auszugeben.
Eine Anordnung von Zellen wird bereitgestellt. Jede Zelle besitzt ein Register, das dafür konfiguriert ist, das Datenelement aus dem Geberdatenbus zu empfangen, und das Datenelement an den Nehmerdatenbus zu übertragen, eine Zustandssteuerung, die eine Anzeige des Zustands der Zelle liefert, eine Geberkomponente, die dafür konfiguriert ist, gemäß dem ersten Betriebsprotokoll zu arbeiten, und eine Nehmerkomponente, die dafür konfiguriert ist, gemäß dem zweiten Betriebsprotokoll zu arbeiten.
Die Geberkomponente empfängt das erste Geber-Token (Sendeberechtigungszeichen) aus einer ersten benachbarten Zelle, speichert das aus dem Geberdatenbus empfangene Datenelement in dem Register auf der Basis der Geberanforderung, des Geber-Tokens und des Status der Zelle zwischen, und übergibt das Geber-Token an eine zweite benachbarte Zelle. Die Nehmerkomponente empfängt das Nehmer-Token von der ersten benachbarten Zelle, gibt das Datenelement aus dem Register von der Warteschlange an den Nehmerdatenbus auf der Basis der Nehmeranforderung, des Nehmer-Tokens und des Zustands der Zelle aus und gibt das Nehmer-Token an die zweite benachbarte Zelle weiter.
Gemäß der Erfindung werden die vorstehend beschriebenen Aufgaben gelöst und der Bedarf in dem Fachgebiet nach einer FIFO-Schaltung mit geringer Latenz und hohem Durchsatz und die für einen Betrieb in gemischten synchronen/asynchronen Umgebungen geeignet ist, vollständig erfüllt. Weitere Merkmale der Erfindung, deren Art und verschiedenen Vorteile werden aus den beigefügten Zeichnungen und der nachfolgenden detaillierten Beschreibung veranschaulichender Ausführungsformen ersichtlich.
KURZBESCHREIBUNG DER ZEICHNUNGEN
In den Zeichnungen ist:
1 eine schematische Ansicht einer synchronen Geberschnittstelle gemäß der Erfindung.
2 eine schematische Ansicht einer synchronen Nehmerschnittstelle gemäß der Erfindung.
3 eine schematische Ansicht einer asynchronen Geberschnittstelle gemäß der Erfindung.
4 eine schematische Ansicht einer asynchronen Nehmerschnittstelle gemäß der Erfindung.
5 eine schematische Blockdarstellung einer exemplarischen FIFO-Schaltung gemäß einer ersten Ausführungsform der Erfindung.
6 eine detailliertere schematische Blockdarstellung der in 5 dargestellten FIFO-Schaltung.
7 eine schematische Blockdarstellung einer exemplarischen FIFO-Schaltung gemäß einer zweiten Ausführungsform der Erfindung.
8 eine detailliertere schematische Blockdarstellung der in 7 dargestellten FIFO-Schaltung.
9 eine schematische Blockdarstellung einer exemplarischen FIFO-Schaltung gemäß einer dritten Ausführungsform der Erfindung.
10 eine detailliertere schematische Blockdarstellung der in 9 dargestellten FIFO-Schaltung.
11 ein Zeitdiagramm von in Verbindung mit einem synchronen Geberprotokoll angelegten exemplarischen Signalen gemäß der Erfindung.
12 ein Zeitdiagramm von in Verbindung mit einem synchronen Nehmerprotokoll angelegten exemplarischen Signalen gemäß der Erfindung.
13 ein Zeitdiagramm von in Verbindung mit einem asynchronen Geberprotokoll angelegten exemplarischen Signalen gemäß der Erfindung.
14 ein Zeitdiagramm von in Verbindung mit einem asynchronen Nehmerprotokoll angelegten exemplarischen Signalen gemäß der Erfindung.
15 eine vergrößerte schematische Blockdarstellung, welche einen Abschnitt der FIFO-Schaltung von 5 und 6 gemäß der Erfindung darstellt.
16 eine detailliertere schematische Blockdarstellung des Abschnittes der in 15 dargestellten FIFO-Schaltung gemäß der Erfindung.
17 eine schematische Blockdarstellung eines Voll-Detektors, der in 5 und 6 dargestellten FIFO-Schaltung gemäß der Erfindung.
18 eine schematische Blockdarstellung eines ersten Leer-Detektors, der in 5 und 6 dargestellten FIFO-Schaltung gemäß der Erfindung.
19 eine schematische Blockdarstellung eines zweiten Leer-Detektors, der in 5 und 6 dargestellten FIFO-Schaltung gemäß der Erfindung.
20 eine schematische Blockdarstellung eines anderen Abschnittes in 5 und 6 dargestellten FIFO-Schaltung gemäß der Erfindung.
21 eine schematische Blockdarstellung eines weiteren Abschnittes der in 5 und 6 dargestellten FIFO-Schaltung gemäß der Erfindung.
22 eine vergrößerte schematische Blockdarstellung, die einen Abschnitt der FIFO-Schaltung der 7 und 8 gemäß der Erfindung darstellt.
23 eine detailliertere schematische Blockdarstellung des in 22 dargestellten Abschnittes der FIFO-Schaltung gemäß der Erfindung.
24 eine Bündel-Modus-Spezifikation eines Abschnittes der in 23 dargestellten FIFO gemäß der Erfindung.
25(a) eine detailliertere schematische Blockdarstellung eines Abschnittes der in 23 dargestellten FIFO-Schaltung gemäß der Erfindung.
25(b) eine detailliertere schematische Blockdarstellung einer anderen Ausführungsform eines Abschnittes der in 23 dargestellten FIFO-Schaltung gemäß der Erfindung.
26 eine detailliertere schematische Blockdarstellung eines weiteren Abschnittes der in 23 dargestellten FIFO-Schaltung gemäß der Erfindung.
27 eine detailliertere schematische Blockdarstellung noch eines weiteren Abschnittes der in 23 dargestellten FIFO-Schaltung gemäß der Erfindung.
28 eine Petri-Netz-Spezifikation eines Abschnittes der in 23 dargestellten FIFO-Schaltung gemäß der Erfindung.
29 eine vergrößerte schematische Blockdarstellung, die einen Abschnitt der FIFO-Schaltung der 9 und 10 gemäß der Erfindung darstellt.
30 eine detailliertere schematische Blockdarstellung des Abschnittes der in 29 dargestellten FIFO-Schaltung gemäß der Erfindung.
31(a) eine detailliertere schematische Blockdarstellung eines Abschnittes der in 30 dargestellten FIFO-Schaltung gemäß der Erfindung.
31(b) eine detailliertere schematische Blockdarstellung einer anderen Ausführungsform eines Abschnittes der in 30 dargestellten FIFO-Schaltung gemäß der Erfindung.
32 eine Bündel-Modus-Spezifikation eines Abschnittes der in 30 dargestellten FIFO gemäß der Erfindung.
33 eine detailliertere schematische Blockdarstellung eines weiteren Abschnittes der in 30 dargestellten FIFO-Schaltung gemäß der Erfindung.
34 eine detailliertere schematische Blockdarstellung noch eines weiteren Abschnittes der in 30 dargestellten FIFO-Schaltung gemäß der Erfindung.
35 eine Petri-Netz-Spezifikation eines Abschnittes der in 30 dargestellten FIFO-Schaltung gemäß der Erfindung.
36 eine schematische Blockdarstellung eines herkömmlichen Systems.
37 eine schematische Blockdarstellung eines Relaisstationen enthaltenden herkömmlichen Systems.
38 eine schematische Blockdarstellung einer herkömmlichen Relaisstation.
39 eine schematische Blockdarstellung, die eine FIFO-Schaltungs-Relaisstation gemäß der Erfindung darstellt.
40 eine detailliertere schematische Blockdarstellung, die eine in 39 dargestellte FIFO-Schaltungs-Relaisstation gemäß der Erfindung darstellt.
41 eine detaillierte schematische Ansicht eines Abschnittes der in 40 dargestellten FIFO-Schaltungs-Relaisstation gemäß der Erfindung.
42 eine detaillierte schematische Ansicht eines anderen Abschnittes der in 40 dargestellten FIFO-Schaltungs-Relaisstation gemäß der Erfindung.
43 eine schematische Blockdarstellung, die ein anderes FIFO-Schaltungs-Relaisstationssystem gemäß der Erfindung darstellt.
44 eine detailliertere schematische Blockdarstellung, die das FIFO-Schaltungs-Relaisstationssystem von 43 gemäß der Erfindung darstellt.
45 eine detailliertere schematische Blockdarstellung, die eine in 44 dargestellte FIFO-Schaltungs-Relaisstation gemäß der Erfindung darstellt.
46 eine detaillierte schematische Ansicht eines Abschnittes der in 45 dargestellten FIFO-Schaltungs-Relaisstation gemäß der Erfindung.
47 eine schematische Blockdarstellung, die noch ein anderes FIFO-Schaltungs-Relaisstationsystem gemäß der Erfindung darstellt.
48 eine detailliertere schematische Blockdarstellung, die das FIFO-Schaltungs-Relaisstationssystem von 47 gemäß der Erfindung darstellt.
49 eine detailliertere schematische Blockdarstellung, die eine in 44 dargestellte FIFO-Schaltungs-Relaisstation gemäß der Erfindung darstellt.
50 eine detaillierte schematische Ansicht eines Abschnittes der in 49 dargestellten FIFO-Schaltungs-Relaisstation gemäß der Erfindung.
DETAILLIERTE BESCHREIBUNG DER EXEMPLARISCHEN AUSFÜHRUNGSFORMEN
Die FIFO-Schaltungen gemäß der Erfindung vermitteln zwischen zwei Subsystemen: einem Sendersubsystem, welches Datenelemente erzeugt und einem Empfängersubsystem, welches Datenelement verbraucht. Die FIFO-Schaltungen sind als ein Ringpuffer aus identischen Zellen implementiert, in welchem jede Zelle mit den zwei Subsystemen auf gemeinsamen Datenbussen kommuniziert. Das Eingabe- und Ausgabe-Verhalten einer Zelle wird durch den Fluss von zwei Token um den Ring diktiert: einem zum Eingeben von Daten in eine Warteschlange und einem zum Entnehmen von Daten aus einer Warteschlange. Die Datenelemente werden nicht um den Ring herum bewegt, sobald sie in eine Warteschlange eingegeben wurden, um somit die Möglichkeit für eine geringe Latenz bereitzustellen; sobald ein Datenelement in die Warteschlange eingegeben ist, ist es kurz darauf für eine Entnahme verfügbar.
Jede FIFO-Schaltung ist in modulare Komponenten, unterteilt, welche mit anderen modularen Komponenten in einer Reihe unterschiedlicher Systeme verwendet werden können, wie es nachstehend beschrieben wird. Ein Satz von Schnittstellen, oder Abschnitten der FIFO-Schaltung kann miteinander kombiniert werden, um vollständige FIFO-Schaltungen zu erhalten, welche die gewünschten Zeittaktannahmen sowohl an dem Ende de Senders als auch Empfängers erfüllen, wie es hierin nachstehend beschrieben wird. So wie hierin verwendet, soll "Zeitbereich" sich darauf beziehen, ob das Subsystem synchron oder asynchron ist.
Gemäß der Erfindung besitzt jede FIFO-Schaltung zwei Schnittstellen, oder Abschnitte der FIFO-Schaltung, welche dafür ausgelegt sind, mit der Umgebung zusammenzuarbeiten. Die erste, die Geberschnittstelle ist der Abschnitt der FIFO-Schaltung, welche mit dem Sendersubsystem kommuniziert. Eine synchrone Geberschnittstelle ist in 1 dargestellt und eine asynchrone Geberschnittstelle ist in 3 dargestellt. Die zweite, die Nehmerschnittstelle ist der Abschnitt der FIFO-Schaltung, welcher mit dem Empfängersystem kommuniziert. 2 stellt eine synchrone Nehmerschnittstelle dar, und 4 stellt eine asynchrone Nehmerschnittstelle dar. Eine FIFO-Schaltung, welche eine Schnittstelle zu der Umgebung unabhängig davon, ob die Sender- und Empfängersubsysteme synchron, synchron und asynchron oder asynchron bzw. synchron sind, kann aufgebaut werden, indem eine Geberschnittstelle und eine Nehmerschnittstelle zusammengefügt werden, welche korrekt den präsentierten Bedingungen entsprechen.
1-2 stellen zwei synchrone Schnittstellen gemäß der Erfindung dar. Die in 1 dargestellte synchrone Geberschnittstelle 10 wird von einem Sendertaktsignal 12 (CLK_put) gesteuert. Es gibt zwei Eingangssignale zu der synchronen Geberschnittstelle 10, ein Geberanforderungssignal 14 (req_put), welches Anforderungen durch den Sender überträgt, um Daten in eine Warteschlange einzugeben und in einen Senderdatenbus 16 (data_put), welcher der Bus für die Datenelemente ist. Das globale Voll-Signal 18 (full) wird aktiviert, wenn die FIFO-Schaltung voll ist, ansonsten deaktiviert.
2 stellt eine synchrone Nehmerschnittstelle 20 dar, welche von einem Empfängertaktsignal 22 (CLK_get) gesteuert wird. Ein einziges Steuereingangssignal aus dem Empfänger zum Entnehmen eines Datenelementes aus der Warteschlange ist ein Nehmeranforderungssignal 24 (req_get). Die Daten werden auf den Empfängerdatenbus 26 (data_get) gelegt. Ein globales Leersignal 28 (empty) wird nur dann aktiviert, wenn die FIFO-Schaltung leer ist. Das Datengültigkeitssignal 30 (valid_get) zeigt an, dass das Datenelement gültig ist.
Die in 3–4 dargestellten asynchronen Schnittstellen sind nicht mit einem Taktsignal synchronisiert. 3 stellt eine asynchrone Geberschnittstelle 40 dar, die zwei Eingangssignale besitzt, welche im Wesentlichen ähnlich zu den Eingangssignalen der syn chronen Geberschnittstelle 10 (1) sind. Ein erstes Geberanforderungssignal 44 (put_req) wird bereitgestellt, welches Anforderungen durch den Sender zum Entnehmen von Daten aus der Warteschlange überträgt und ein zweites, ein Senderdatenbussignal 46 (put_data) wird für die Ausgabe von Datenelementen bereitgestellt. Im Gegensatz zu der synchronen Geberschnittstelle 10 weist diese Schnittstelle kein globales Voll-Signal auf; stattdessen liefert die asynchrone Geberschnittstelle 40 ein Geberbestätigungssignal 45 (put_ack), wenn der Gebevorgang abgeschlossen ist.
Die in 4 dargestellt asynchrone Nehmerschnittstelle 50 weist ein Nehmeranforderungssignal 54 (get_req) und einen Ausgabedatenbus 58 (get_data) auf. Anders als bei dem synchronen Gegenstück hat diese Schnittstelle kein Gültigkeitssignal oder ein globales Leersignal. Die asynchrone Nehmerschnittstelle 50 erzeugt ein Nehmerbestätigungssignal 55 (get_ack), welches anzeigt, dass die Nehmeroperation abgeschlossen ist.
Die modularen Schnittstellen 10, 20, 40 und 50 der 1, 2, 3 und 4 können gemäß der Erfindung angeschlossen sein, um FIFO-Schaltungen zu erzeugen, welche Daten zwischen unterschiedlichen Umgebungen übertragen. Beispielsweise kann eine FIFO-Schaltung, welche eine Schnittstelle zwischen einem synchronen Sendersubsystem und einem synchronen Empfängersubsystem bildet, unter Verwendung der synchronen Geberschnittstelle 10 und der synchronen Nehmerschnittstelle 20 erzeugt werden, um eine FIFO-Schaltung auszubilden, welche hierin als eine "Synchron-Synchron"-FIFO-Schaltung bezeichnet wird, wie es unter Bezugnahme auf die FIFO-Schaltung 100 einer exemplarischen Ausführungsform beschrieben wird. In ähnlicher Weise würde eine FIFO-Schaltung, die eine Schnittstelle zwischen einem asynchronen Sendersubsystem und einem synchronen Empfängersubsystem erzeugt, eine asynchrone Geberschnittstelle 40 zusammen mit einer synchronen Geberschnittstelle 20 enthalten, was als eine "Asynchron-Synchron"-FIFO bezeichnet werden kann, und detaillierter in Bezug auf eine FIFO-Schaltung 200 einer exemplarischen Ausführungsform beschrieben wird. Ebenso kann, um eine Schnittstelle zwischen einem synchronen Sendersubsystem und einem asynchronen Empfängersubsystem zu erzeugen, welche als eine "Synchron-Asynchron"-FIFO bezeichnet werden kann, diese eine synchrone Geberschnittstelle 10 und eine asynchrone Nehmerschnittstelle 50 verwenden, wie es hierin unter Bezugnahme auf eine FIFO-Schaltung 300 einer exemplarischen Ausführungsform beschrieben wird.
Die FIFO-Schaltungen 100, 200 und 300 der 6, 8 bzw. 10 sind im Wesentlichen mit den hierin angegebenen Unterschieden ähnlich. Beispielsweise enthält jede FIFO-Schaltung 100, 200 und 300 eine Ringanordnung identischer Zellen, welche mit den Geber- und Nehmerschnittstellen auf gemeinsamen Datenbussen kommunizieren. Die Steuerlogik für jede Operation ist zwischen den Zellen verteilt und ermöglicht eine Gleichzeitigkeit zwischen den zwei Schnittstellen. Daten sind in der Anordnung der Zellen unbeweglich. Demzufolge wird ein Datenelement, sobald es in die Warteschlange eingegeben ist, nicht bewegt, und wird lediglich an dieser Stelle aus der Warteschlange entnommen.
Zu jedem Zeitpunkt befinden sich zwei Tokens in den FIFO-Schaltungen 100, 200 und 300, d.h., ein Geber-Token und ein Nehmer-Token. Das Eingabe- und Ausgabeverhalten der FIFO-Schaltungen 100, 200 und 300 wird durch diese Tokens gesteuert. Der Geber-Token wird dazu verwendet, um eine Warteschlangeneingabe der Datenelemente zu ermöglichen, und das Nehmer-Token wird dazu verwendet, um eine Entnahme der Datenelemente aus der Warteschlange zu ermöglichen. Eine Zelle mit dem Geber-Token kann als das "Ende" der Warteschlange betrachtet werden, und die Zelle mit dem Nehmer-Token kann als der "Kopf" der Warteschlange betrachtet werden. Im normalen Betrieb befindet sich das Geber-Token typischerweise vor dem Nehmer-Token. Sobald eine Zelle ein Token für eine Datenoperation verwendet hat, wird das Token an die nächste Zelle weitergegeben, nachdem die entsprechende Operation abgeschlossen ist. Die Token-Bewegung wird sowohl durch die Schnittstellenanforderungen als auch durch den Zustand der FIFO-Schaltung, d.h., leer oder voll, wie es nachstehend detaillierter beschrieben wird, gesteuert.
Es gibt mehrere Vorteile, die den Architekturen der FIFO-Schaltungen 100, 200 und 300 gemeinsam sind. Da keine Daten zwischen den Zellen von Eingang zu Ausgang weitergeleitet werden, haben die FIFO-Schaltungen das Potential für eine geringe Latenz. Demzufolge ist, sobald ein Datenelement in die Warteschlange eingegeben ist, dieses auch für die Entnahme aus der Warteschlange verfügbar. Zweitens bieten die FIFO-Schaltungen das Potential für geringen Leistungsverbrauch: Datenelemente sind immobil während sie sich in der FIFO-Schaltung befinden. Schließlich sind diese Architekturen sehr gut skalierbar; die Kapazität der FIFO-Schaltung und die Breite des Datenelementes können mit sehr wenigen Auslegungsmodifikationen verändert werden.
Die FIFO-Schaltung 100 gemäß einer ersten exemplarischen Ausführungsform ist in den 5 und 6 dargestellt. Die FIFO-Schaltung 100 kann verwendet werden, wenn das Sendersubsystem synchron und das Empfängersubsystem ebenfalls synchron ist. Demzufolge wird die modulare synchrone Geberschnittstelle 10 in Verbindung mit der modularen synchronen Nehmerschnittstelle 20 gemäß Darstellung in 5 verwendet. Das Sendersubsystem arbeitet mit dem Sendertaktsignal 12 (CLK_put) und das Empfängersubsystem arbeitet mit dem Empfängertaktsignal 22 (CLK_get).
Gemäß Darstellung in 6 ist die FIFO-Schaltung 100 mit einer Ringanordnung identischer Zellen 170a, 170b, 170c und 170d aufgebaut und kommuniziert mit den zwei externen Schnittstellen, d.h., der synchronen Geberschnittstelle 10 auf dem Senderdatenbus 16 (data_put) und der synchronen Nehmerschnittstelle 20 auf dem Empfängerdatenbus 26 (data_get).
Die synchronen Schnittstellen 10 und 20 haben zwei zusätzliche Arten von Komponenten: (1) Detektoren, welche den aktuellen Zustand der FIFO-Schaltung 100 ermitteln, d.h., leer oder voll, und (2) externe Steuerungen, welche bedingungsabhängig Anforderungen für Datenoperationen zu der Zellenanordnung weitergeben. Wie es im Fachgebiet bekannt ist, wird eine Datenoperation in einer synchronen Schnittstelle innerhalb eines Taktzyklusses abgeschlossen; daher benötigt die Umgebung kein explizites Bestätigungssignal. Wenn jedoch die FIFO-Schaltung 100 voll (oder leer) wird, kann es sein, dass die Umgebung an einer Kommunikation mit der Geber-(oder Nehmer)-Schnittstelle abgehalten werden muss. Die Detektoren und Steuerungen arbeiten in der FIFO-Schaltung 100, um die Ausnahmefälle zu detektieren und sperren die entsprechende Schnittstelle, wenn die Datenoperation nicht sicher durchzuführen ist. Gemäß Darstellung in 6 beobachten der Voll-Detektor 72 und Leer-Detektor 74 den Zustand aller Zellen 170a, 170b, 170c und 170d und berechnen den globalen Zustand der FIFO-Schaltung 100, d.h., voll oder leer. Das Ausgangssignal des Voll-Detektors 72 kann an die Geberschnittstelle 10 weitergeleitet werden, während das Ausgangssignal des Leer-Detektors 74 an die Nehmerschnittstelle 20 weitergeleitet werden kann. Die Gebersteuerung 176 und die Nehmersteuerung 178 filtern Datenoperationsanforderungen an die FIFO-Schaltung 100. Somit gibt die Gebersteuerung 176 üblicherweise Geberanforderungen aus dem Sendersubsystem weiter, sperrt aber diese, wenn die FIFO-Schaltung voll ist. In ähnlicher Weise gibt die Nehmersteuerung 178 Anforderungen aus dem Empfängersubsystem weiter, blockiert aber diese, wenn die FIFO-Schaltung 100 leer ist. Die Detektoren 72 und 74, die externen Steuerungen 176 und 178 und die Definitionen von "leer" und "voll" werden nachstehend detaillierter beschrieben.
Die FIFO-Schaltung 200 gemäß einer zweiten exemplarischen Ausführungsform ist in den 7 und 8 dargestellt. Die FIFO-Schaltung 200 kann verwendet werden, wenn das Sendersubsystem asynchron und das Empfängersubsystem synchron ist. Demzufolge wird die modulare asynchrone Geberschnittstelle 40 in Verbindung mit der modularen synchronen Nehmerschnittstelle 20 gemäß Darstellung in 7 verwendet. Das Sendersubsystem arbeitet asynchron, während das Empfängersubsystem mit dem Empfängertaktsignal 22 (CLK_get) arbeitet.
Gemäß Darstellung in 8 ist die FIFO-Schaltung 200 mit einer Ringanordnung identischer Zellen 270a, 270b, 270c und 270d aufgebaut und kommuniziert mit den zwei externen Schnittstellen, der asynchronen Geberschnittstelle 40 und der synchronen Nehmerschnittstelle 20 auf gemeinsamen Datenbussen: einem Senderdatenbus 46 (data_put) und einem Empfängerdatenbus 16 (get_data).
Die synchrone Nehmerschnittstelle 20 gemäß vorstehender Beschreibung unter Bezugnahme auf 6 enthält einen Leer-Detektor 74 und eine Nehmersteuerung 278. Die Nehmersteuerung 278 gibt typischerweise die Nehmeranforderungen aus dem Empfängersubsystem weiter, deaktiviert aber derartige Anforderungen, wenn die FIFO-Schaltung 200 leer ist. Im Gegensatz zu synchronen Schnittstellen enthalten asynchrone Schnittstellen, wie z.B. die asynchrone Schnittstelle 40, keine Voll- oder Leer-Detektoren oder externe Steuerungen. Da eine asynchrone Schnittstelle ohne ein Taktsignal arbeitet, muss sie keine Ausnahme wie z.B. "voll" oder "leer" schaffen, um temporär eine Datenoperation zu blockieren. Daher kann, wenn eine FIFO-Schaltung mit einer asynchronen Schnittstelle voll (oder leer) wird, die Geber-(oder Nehmer-)Bestätigung unbegrenzt aufrechterhalten werden, bis die Datenoperation sicher durchgeführt werden kann. In dem Falle der FIFO-Schaltung 200 wird das Geberbestätigungssignal 45 (put_ack) aufrechterhalten, wenn die FIFO-Schaltung 200 voll ist, und übertragen, wenn die Geberoperation sicher durchgeführt werden kann.
9 und 10 stellen die FIFO-Schaltung 300 gemäß einer dritten exemplarischen Ausführungsform dar. Die FIFO-Schaltung 300 kann verwendet werden, wenn das Sendersubsystem synchron und das Empfängersubsystem asynchron ist. Die synchrone Geberschnittstelle 10 wird in Verbindung mit der asynchronen Nehmerschnittstelle 50 gemäß Darstellung in 9 verwendet. Das Sendersubsystem arbeitet mit dem Sendertaktsignal 12 (CLK_put), während das Empfängersubsystem asynchron arbeitet.
Gemäß Darstellung in 10 enthält die FIFO-Schaltung 300 eine Ringanordnung identischer Zellen 370a, 370b, 370c und 370d und kommuniziert mit den zwei externen Schnittstellen, der synchronen Geberschnittstelle 10 und der asynchronen Nehmerschnittstelle 50 auf gemeinsamen Datenbussen: einem Senderdatenbus 16 (data_put) und einem Empfängerdatenbus 56 (get_data).
Die synchrone Geberschnittstelle 10 gemäß vorstehender Beschreibung unter Bezugnahme auf 6 enthält einen Voll-Detektor 72 und eine Gebersteuerung 376. Die FIFO-Schaltung 300 besitzt keinen Leer-Detektor; stattdessen wird das Nehmerbestätigungssignal 55 (get_ack) aufrechterhalten, wenn die FIFO-Schaltung 300 leer ist, und übertragen, wenn die Nehmeroperation sicher ausgeführt werden kann.
Das synchrone Geberprotokoll ist in 11 dargestellt und wird in Verbindung mit 1 diskutiert. Die synchrone Geberschnittstelle 10 startet eine Geberoperation, wenn sie ein Geberanforderungssignal 14 (put_req) und ein Datenelement auf dem Geberdatenbus 16 (data_put) unmittelbar nach der positiven Flanke des Sendertaktsignals 12 (CLK_put) empfängt. Das Datenelement wird unmittelbar nach der positiven Flanke des (nicht dargestellten) nächsten Taktzyklus in die Warteschlange eingegeben. Wenn die FIFO-Schaltung voll wird, wird dann das globale Voll-Signal 18 (full) vor dem nächsten Taktzyklus gemäß Darstellung in 11 aktiviert, und die synchrone Geberschnittstelle 10 an jeder weiteren Operation gehindert.
12 stellt das synchrone Nehmerprotokoll dar, welches in Verbindung mit der vorstehenden 2 diskutiert wird. Eine synchrone Nehmeroperation wird durch ein Nehmeranforderungssignal 24 (req_get) freigegeben, welches unmittelbar nach der positiven Flanke des Empfängertaktsignals 22 (CLK_get) aktiviert wird. Durch das Ende des Takt zyklusses wird ein Datenelement auf den Nehmerdatenbus 28 (data_get) zusammen mit seinem Gültigkeitssignal 30 (valid_get) platziert. Wenn die FIFO-Schaltung während dieses Taktzyklusses leer wird, wird dann das globale Leer-Signal 28 (empty) ebenfalls unmittelbar nach der positiven Flanke des nächsten Taktzyklusses aktiviert und die synchrone Nehmerschnittstelle 20 blockiert, bis die FIFO-Schaltung nicht-leer wird. Nach einer Nehmeranforderung 24 (req_get) können dann das Gültigkeitssignal 30 (valid_get) und das globale Leer-Signal 28 (empty) drei Ergebnisse anzeigen: (a) Ein Datenelement kann aus der Warteschlange ausgegeben sein, und mehrere verfügbare Datenelemente sein (d.h., valid_get = 1, empty = 0); (b) ein Datenelement kann aus der Warteschlange ausgegeben sein, und die FIFO-Schaltung wurde leer (d.h., valid_get = 1, empty = 1); oder (c) die FIFO-Schaltung ist leer und kein Datenelement ist aus der Schlange ausgegeben (valid_get = 0, empty = 1).
Die asynchronen Geber- und Nehmer-Protokolle sind in den 13 und 14 dargestellt. Da die asynchronen Schnittstellen keinen Takt besitzen, verwenden sie eine 4-Phasen-Bündeldaten-Kommunikationsart, wie sie im Fachgebiet bekannt ist. Weitere Details bezüglich Bündeldatenkommunikation sind in S. Furber, "Asynchronous Design", Proceedings of Submicron Electronics, pp. 461–492; I. Sutherland, "Micropipelines", Communications of the ACM, 32(6), pp. 720–738, June 1989, und H. van Gageldonk et al. "An Asynchronous Low-Power 805C51 Microcontroller", Proceedings International Symposium an Advanced Research in Asynchronous Circuits and Systems pp. 96–107, 1998, welche hierin in ihrer Gesamtheit durch Bezugnahme beinhaltet sind, beschrieben. Datenelemente müssen stabile Werte auf den Datenbussen haben, bevor eine Datenoperation angefordert wird.
Gemäß Darstellung in 13 startet der Sender eine Geberoperation, indem er ein Datenelement auf dem Senderdatenbus 46 (put_data) platziert und eine Anforderung an die FIFO-Schaltung ausgibt, dieses in die Warteschlange einzugeben, indem er das Geberanforderungssignal 44 (put_req) aktiviert. Der Abschluss der Warteschlangeneingabeoperation wird angezeigt, indem das Geberbestätigungssignal 45 (put_ack) aktiviert wird. Die zwei Steuerleitungen werden anschließend auf den Leerlaufzustand zurückgesetzt, zuerst die Geberanforderungen 44 (put_req) und dann die Geberbestätigung 45 (put_ack).
In ähnlicher Weise ist eine asynchrone Nehmeroperation in 14 dargestellt. Die Nehmeroperation wird durchgeführt, indem das Geberanforderungssignal 54 (get_req) aktiviert wird, und indem ein Datenelement aus der Warteschlange auf den Nehmerdatenbus 56 (get_data) ausgegeben wird. Nach dem Abschluss dieser Operation wird das Nehmerbestätigungssignal 55 (get_ack) aktiviert. Anschließend wird das Nehmeranforderungssignal 54 (get_req) deaktiviert und dann das Nehmerbestätigungssignal 55 (get_ack) ebenfalls deaktiviert.
Um FIFO-Schaltungen 100, 200 und 300 aufzubauen, welche korrekt mit synchronen und asynchronen Systemen arbeiten, besitzt jede Zelle eine Konfiguration, die aus vier unterschiedlichen, austauschbaren Komponententeilen besteht, die so ausgewählt sind, dass sie eine Schnittstelle mit der Sender- oder Empfängerumgebung bilden: (1) eine Geberkomponente, die die Geberoperation durchführt und dafür konfiguriert ist, mit der Senderumgebung zu arbeiten, d.h., synchron oder asynchron, (2) eine Nehmerkomponente, die die Nehmeroperation ausführt, und dafür konfiguriert ist, mit der Empfängerumgebung zu arbeiten, d.h., synchron oder asynchron, (3) eine Datengültigkeits-(DV)-Steuerung, welche eine Anzeige dafür liefert, ob die Zelle ein Datenelement aufweist, und welche dafür konfiguriert ist, sowohl mit den Sender- als auch Empfängerumgebungen zu arbeiten, und (4) ein Register, welches dafür konfiguriert ist, sowohl mit den Sender- als auch Empfängerumgebungen zu arbeiten. Demzufolge sind die Geberkomponenten in den Zellen 170a–d und 370a–d im Wesentlichen identisch, da sie dafür konfiguriert sind, mit einer synchronen Senderumgebung zu arbeiten. Die Nehmerkomponenten in den Zellen 170a–d und 270a–d dürften im Wesentlichen identisch sein, da sie dafür konfiguriert sind, mit einer synchronen Empfängerumgebung zu arbeiten. Die Geberkomponenten der Zellen 270a–d sind dafür konfiguriert, um mit einer asynchronen Senderumgebung zu arbeiten, und die Nehmerkomponenten der Zellen 370a–d sind dafür konfiguriert, um mit einer asynchronen Empfängerumgebung zu arbeiten.
Der Zweck der Datengültigkeitssteuerung besteht in der Anzeige, wenn die Zelle voll ist, und wenn sie leer ist, und wenn sie gültige Daten enthält. Das Register in jeder Zelle ist in zwei Teile unterteilt, einen, der zu der Geberkomponente gehört (der Schreibport) und einen, der zu der Nehmerkomponente (Leseport). Die Geberkomponente, die Nehmerkom ponente und die Datengültigkeitssteuerung und das Register sind miteinander verbunden, um eine komplette Zelle zu erhalten.
Die FIFO-Schaltung 100, welche in Verbindung mit einem synchronen Sender und einem synchronen Empfänger verwendet werden kann, wurde vorstehend zusammen mit einer Anordnung identischer Zellen 170a, 170b, 170c und 170d in Verbindung mit den 5 und 6 beschrieben. Eine exemplarische einzelne Zelle, wie z.B. die Zelle 170a der FIFO-Schaltung 100, ist in den 15 und 16 dargestellt. (Die nachstehende Beschreibung für die Zelle 170a trifft auch auf die Zellen 170b, 170c und 170d zu). Jede Zelle 170a besitzt vier Schnittstellen: (1) eine synchrone Geberschnittstelle 171, (2) eine synchrone Nehmerschnittstelle 172, (3) eine Schnittstelle 173 mit einer rechten Zelle in der Anordnung von Zellen, und (4) eine Schnittstelle 174 mit einer linken Zelle in der Anordnung der Zellen. Auf der synchronen Geberschnittstelle 171 empfängt die Zelle 170a Daten auf dem gemeinsamen Geberdatenbus 16 (data_put). Dieser wird zur Durchführung einer Geberoperation durch das Geberfreigabesignal 80 (en_put) freigegeben, welche das Ausgangssignal der Gebersteuerung 76 ist (siehe 6). Das Geberanforderungssignal 14 (req_put) zeigt eine Datengültigkeit (welche in dieser Ausführungsform immer aktiviert ist) an. Die Weitergabe des Geberanforderungssignals 14 (req_put) an die Zelle 170a wurde aus 6 vorstehend weggelassen, um eine Komplizierung der Figur zu vermeiden. Die Zelle 170a kommuniziert mit dem Voll-Detektor 72, mit dem Leer-Bit 182 (e_i), welches aktiviert ist, wenn die Zelle 170a leer ist. Der Zustand der exemplarischen Zelle 170a wird durch die Datengültigkeits-(DV)-Steuerung angezeigt, wie z.B. durch einen asynchronen SR-Zwischenspeicher 180. Auf der synchronen Nehmerschnittstelle 172 (15) gibt die Zelle 170a Daten auf den gemeinsamen Nehmerdatenbus 26 (data_get) zusammen mit ihrem Gültigkeitssignal 184 (valid_i) aus, welches in dieser Ausführungsform immer aktiviert ist. Gemäß Darstellung in 6 wird das Gültigkeitssignal 184 (valid_i) in der FIFO-Schaltung 100 nicht verwendet, wird aber in den nachstehend beschriebenen verschiedenen Ausführungsformen verwendet. Die synchrone Nehmerschnittstelle 172 wird durch das Nehmerfreigabesignal 186 (en_get) freigegeben, welche das Ausgangssignal der Nehmersteuerung 78 ist (siehe 6). Die Zelle 170a kommuniziert mit dem Leer-Detektor 74 mit dem Voll-Bit 188a (f_i), welches aktiviert ist, wenn die Zelle 170a voll ist. Auf der Schnittstelle 173 mit der rechten Zelle empfängt jede Zelle 170a–d Tokens auf einem Geber-Token-Eingang 190 (ptok_in) und empfängt das Nehmer-Token-Eingangssignal 192 (gtok_in) von der rechten Zelle. Auf der Schnittstelle 174 mit der linken Zelle gibt jede Zelle 170 die Tokens auf den Geber-Token-Ausgang 194 (ptok_out) und das Nehmer-Token-Ausgangssignal 196 (gtok_out) an die linke Zelle weiter.
Die Zelle 170a gemäß der ersten Ausführungsform ist auch in 16 dargestellt. Das Verhalten der Zelle 170a kann durch Verfolgen einer Geberoperation und dann einer Nehmeroperation durch die Zelle 170a hindurch dargestellt werden. Zu Beginn startet die Zelle 170a in einem Leerzustand (d.h., e_i = 1 und f_i = 0) und ohne irgendwelche Tokens. Die Zelle 170a wartet, um das Geber-Token auf dem Geber-Token-Eingang 190 (ptokn_in = 1) aus der rechten Zelle mit der positiven Flanke des Sendertaktsignals 12 (CLK_put) zu empfangen und wartet, bis der Sender ein gültiges Datenelement auf dem Geberdatenbus 16 (data_put) platziert. Ein gültiges Datenelement wird dann allen Zellen durch das Geberfreigabesignal 180 (en_put = 1) angezeigt, welches das Ausgangssignal der Gebersteuerung 176 ist (siehe 6).
Wenn gültige Daten vorliegen und die Zelle das Geber-Token (d.h., AND 181) erhalten hat, führt die Zelle 170a drei Aktionen aus: (1) sie gibt das Register 191 (REG) frei, um das Datenelement und auch das Geberanforderungssignal 14 (req_put) zwischenzuspeichern; (2) sie zeigt an, dass die Zelle 170a ein gültiges Datenelement besitzt (setzt asynchron f_i = 1); und (3) gibt das obere linke flankengetriggerte D-Flipflop ETDFF 193 (en_put = 1) frei, um das Geber-Token an die linke Zelle auf dem Geber-Token-Ausgang 194 ptok_out weiterzugeben. Mit der positiven Flanke des nächsten Taktzyklusses des Sendertaktsignals 12 (CLK_put), werden das Datenelement und das Gültigkeitsbit endgültig zwischengespeichert, und das Geber-Token an die linke Zelle weitergegeben.
Eine Entnahme von Daten aus der Warteschlange durch die Zelle 170a läuft in einer im Wesentlichen identischen Weise mit den hierin angegebenen Unterschieden ab. Die Zelle 170a wartet, um das Nehmer-Token an dem Nehmer-Token-Eingang 192 (gtok_in = 1) aus der rechten Zelle zu empfangen. Wenn dieses erfolgt, gibt die Zelle 170 die Weitergabe des Gültigkeitsbits 183 (v_i) frei, d.h., das zwischengespeicherte Geberanforderungssignal 14 (req_put), auf dem gültigen Bus 184 (valid_i). Wenn sowohl das Nehmer-Token an dem Nehmer-Token-Eingang 192 (gtok_in = 1) empfangen wird als auch der Empfänger ein Datenelementes mit dem Nehmerfreigabesignal 186 (en_get = 1) anfordert, wie es durch das AND-Gatter 181 implementiert ist, gibt die Zelle 170a asynchron das auf dem gemeinsamen Datenbus 26 (data_get) zu platzierende Datenelement frei und zeigt an, dass die Zelle 170 leer ist (setzt asynchron e_i = 1). Die Ankunft der aktivierten Nehmerfreigabe 186 (en_get) gibt das untere linke flankengetriggerte D-Flipflop ETDFF 195 frei, um das Nehmer-Token an das Nehmer-Token-Ausgang 196 (gtok_out) weiterzugeben. An dem Beginn des nächsten Taktzyklusses wird dann das Nehmer-Token an die linke Zelle weitergegeben.
Jede von den FIFO-Schaltungen 100, 200 und 300 kann wenigstens eine synchrone Schnittstelle enthalten. Daher müssen die FIFO-Schaltungsoperationen synchronisiert werden. Eine Mischtakt-FIFO-Schaltung weist einen sehr gleichzeitig ablaufenden Betrieb auf: Zu jedem Zeitpunkt kann der FIFO-Schaltungszustand, d.h., voll oder leer, entweder von der Geberschnittstelle 10 und/oder der Nehmerschnittstelle 20 modifiziert werden, wovon jede unter einem anderen Takt oder asynchron arbeitet. Gleichzeitig "liest" jede Schnittstelle den Zustand der Schnittstellenschaltung unter ihrem eigenen Takt. Das globale Vollsignal 18 (full) (6 und 10) wird durch die Geberschnittstelle gelesen, und das globale Leersignal 28 (empty) (6 und 8) wird durch die Nehmerschnittstelle gelesen. Daher wurden, um inkonsistente Leseoperationen zu verhindern, Synchronisatoren zu jedem von den zwei globalen Steuersignalen, dem Vollsignal 18 (full) und dem Leersignal 28 (empty) hinzugefügt. Jeder Synchronisator passt das entsprechende globale Signal an den entsprechenden Takt an. In der exemplarischen Ausführungsform wird ein Paar von Synchronisations-Zwischenspeichern verwendet; wobei jedoch für erhöhte Robustheit angemerkt wird, dass mehr als zwei Zwischenspeicher verwendet werden können. Gemäß Darstellung in den nachstehenden 17, 18 und 19 werden Synchronisatoren dem Ausgang des Voll-Detektors 72 und des Leer-Detektors 74 hinzugefügt, und von dem Sendertaktsignal 12 (CLK_put) bzw. dem Empfängertaktsignal 22 (CLK_get) gesteuert.
Die hierin beschriebenen Synchronisatoren fügen der Leseoperation des aktuellen Zustandes der FIFO-Schaltung zusätzliche Taktzyklen hinzu. Demzufolge können einfache Voll- und Leer-Detektoren, welche lediglich den unmittelbaren Zustand der FIFO-Schaltung anzeigen, zu einem Fehler, d.h., zu einem Überlauf oder Unterlauf führen. Beispielsweise wird, wenn die FIFO-Schaltung, welche ein Paar von zwei Synchronisierungszwischenspeichern verwendet, voll wird, die Senderschnittstelle zwei Taktzyklen später blockiert. In dem nächsten Taktzyklus könnte der Sender ein neues Datenelement ablegen wollen, was effektiv ein ungelesenes Datenelement überschreibt. Umgekehrt wird, wenn die FIFO-Schaltung leer wird, die Empfängerschnittstelle zwei Taktzyklen später blockiert, so dass in dem nächsten Taktzyklus der Empfänger eine leere Zelle lesen könnte.
Eine erfindungsgemäße Lösung besteht in der Modifikation des Definition und der Implementation des globalen Voll-Signals 18 (full) und des globalen Leersignals 28 (empty), um einen "imminenten" Voll- oder Leerzustand vorwegzunehmen, um die Schnittstellen rechtzeitig und nicht zu früh oder zu spät anzuhalten. Gemäß der Definition wird die FIFO-Schaltung als "voll" betrachtet, wenn weniger als eine vorbestimmte Anzahl von Zellen leer sind. (Die Definition von "leer" wird detaillierter nachstehend betrachtet). Gemäß der ersten exemplarischen Ausführungsform wird die FIFO-Schaltung als voll betrachtet, wenn entweder keine Zellen oder nur eine Zelle leer sind. Somit wird, wenn weniger als zwei leere Zellen vorhanden sind, die FIFO-Schaltung als voll erklärt, und das Sendersubsystem kann sicher ein endgültiges Datenelement ablegen und eine neue unbeantwortete Anforderung ausgeben, bevor es zwei Taktzyklen später blockiert. Die vorstehend unter Bezugnahme auf die 11–12 beschriebenen Protokolle bleiben unverändert. Die einzige Auswirkung kann die sein, dass manchmal die zwei Systeme eine FIFO-Schaltung mit n Plätzen als eine n-1 Plätzen sehen.
Der in 17 dargestellte Voll-Detektor 72 implementiert die vorstehend beschriebene Definition von "voll". Die FIFO-Schaltung 100 wird für voll erklärt, wenn weniger als eine vorbestimmte Anzahl von aufeinander folgenden Zellen leer sind. Gemäß Darstellung in 17 werden die Leer-Bits 182 (e_i) für aufeinander folgende Zellen bewertet, d.h., e_0 und e_1; e_1 und e_2; e_2 und e_3; und e_3 und e_0; und die FIFO-Schaltung 100 wird für voll erklärt, wenn keine von diesen aufeinander folgenden Paaren von Zellen leer vorgefunden wird. Ein Paar von Zwischenspeichern 171 und 173 wurden hinzugefügt, um das globale Vollsignal 18 (full) mit dem Sendertaktsignal 12 (CLK_put) zu synchronisieren.
Eine ähnliche Definition von "leer" trifft zu, wenn weniger als eine vorbestimmte Anzahl von Zellen in der FIFO-Schaltung 100 voll ist. In der exemplarischen Ausführungsform kann, wenn weniger als zwei Datenelemente vorhanden sind, die FIFO-Schaltung als leer erklärt werden. Unter diesen Umständen kann dann das Empfängersubsystem das letzte Datenelement entnehmen und eine neue unbeantwortete Anforderung ausgeben, bevor es zwei Taktzyklen später blockiert. Jedoch kann die frühe Detektion von leer, wie vorstehend beschrieben, eine Dauerblockierung der FIFO-Schaltung 100 bewirken. Ein Nachteil der "fast leer" (ne) Definition (null oder ein Datenelement(e) in der FIFO-Schaltung) besteht darin, dass die FIFO-Schaltung 100 für leer erklärt werden kann, aber trotzdem ein Datenelement enthält, aber der anfordernde Empfänger noch blockiert ist.
Eine alternative Definition von leer, wie sie allgemein bekannt ist, ist "tatsächlich leer" (oe), was eine Anzeige ist, ob sich irgendwelche Datenelemente in der Schaltung befinden. Da das "tatsächlich leer"-Signal (oe) typischerweise durch die Synchronisation verzögert ist, besteht ein Nachteil des "tatsächlich leer"-Signals darin, dass es zu einem Unterlauf führen kann.
Eine erfindungsgemäße Lösung besteht in der Verwendung eines bi-modalen Leer-Detektors 74 (dessen Komponenten in 18–19 gemäß nachstehender detaillierterer Beschreibung dargestellt sind). Der bi-modale Detektor ermittelt sowohl den "fast leeren" (ne) Zustand sowie den "tatsächlich leer" (oe) Zustand. Die zwei Leersignale werden dann mit dem Empfänger synchronisiert und in ein globales Leersignal 28 (empty) kombiniert. Jedoch hat die "fast leer"-Definition normalerweise Vorrang gegenüber der "tatsächlich leer"-(oe)-Definition.
Der bi-modale Leer-Detektor erklärt das globale Leersignal 28 (empty) zum Teil auf der Basis des Auftretens neuer Nehmeranforderungen aus dem Empfänger. Wenn keine neuen Nehmeranforderungen für wenigstens einen Taktzyklus vorhanden waren, geht das "tatsächlich leer"-Signal (oe) vor. Dieses wird wichtig, wenn sich nur ein Datenelement in der FIFO-Schaltung 100 befindet. Das "fast leer"-Signal (ne) zeigt an, dass die FIFO-Schaltung leer ist, und das "tatsächlich leer"-Signal (oe) zeigt an, dass die FIFO-Schaltung nicht leer ist. In diesem Zustand muss die Nehmerschnittstelle 20 das Datenelement aufnehmen, so dass das "tatsächlich leer"-Signal (oe) dazu verwendet wird, den FIFO-Zustand anzuzeigen, d.h., "Nicht leer". Jedoch muss, wenn die Geberschnittstelle gerade ein Datenelement entnommen hat, das "fast leer"-Signal (ne) verwendet werden, um den Zustand anzuzeigen, d.h., "leer", um zu verhindern, dass ein Unterlauf der FIFO-Schaltung auftritt, welche die Synchronisationsverzögerungen für das "tatsächlich leer"-Signal (oe) bewirken könnten.
Gemäß einem weiteren Szenario kann die FIFO-Schaltung für wenigstens einen Taktzyklus leer werden, d.h., das globale Leersignal 28 (empty) wird aktiviert. Während des nächsten Taktzyklusses geht das "tatsächlich leer"-Signal (oe) vor.
Gemäß der ersten exemplarischen Ausführungsform wird der bi-modale Leer-Detektor 74 mit zwei Detektoren, einem "fast leer"-Detektor 120 (18) und einem "tatsächlich leer"-Detektor 130 (19) implementiert. Die zwei Signale werden kombiniert, um das globale Leersignal 28 (empty) gemäß nachstehender Beschreibung unter Bezugnahme auf 19 zu erzeugen. Der in 18 dargestellte "fast leer"-Detektor 120 ist ähnlich dem vorstehend beschriebenen Voll-Detektor 72 und bewertet die Voll-Bits 188 (f_i) aufeinander folgender Zellenpaare, d.h., f_0 und f_1, f_1 und f_2, f_2 und f_3, und f_3 und f_0. Die FIFO-Schaltung 100 wird mit dem Signal 121 (empty_p) als leer erklärt, wenn keine zwei aufeinander folgenden Zellenpaare mit entsprechenden Datenelementen gefunden werden. Ein Paar von Zwischenspeichern 124 und 126 werden zum Synchronisieren des "fast leer"-Signals 122 (ne) mit dem Nehmertaktsignal 22 (CLK_get) verwendet.
Ein in 19 dargestellter "tatsächlich leer"-Detektor 130 ermittelt den "tatsächlichleer"-(oe)-Zustand der FIFO-Schaltung. Gemäß dieser Definition ist die FIFO-Schaltung 100 leer, wenn null Datenelemente vorhanden sind, wobei in diesem Falle das "tatsächlich leer"-Signal 132 (oe) aktiviert wird.
Somit bewertet der "tatsächlich leer"-Detektor 130 jedes Voll-Bit 88 (f_i), um zu ermitteln, ob irgendwelche Datenelemente vorhanden sind. Das "tatsächlich leer"-Signal 132 (oe) wird durch die Synchronisation verzögert, was zu einem Unterlauf führen kann. Um diesen Zustand zu verhindern, wird das "tatsächlich leer"-Signal 132 (oe) synchron auf den neutralen "FIFO-Schaltung leer"-Wert nach jeder Nehmeroperation gesetzt. Dieses wird implementiert, indem das Ausgangssignal 138, nachdem es durch den ersten Zwischenspeicher 134 getaktet wurde, mit dem Nehmerfreigabesignal 186 (en_get) vor dem zweiten Zwischenspeicher 136 ODER-verknüpft wird. Als eine Folge der Festlegung des "tatsächlich leer"-Signals nach jeder Nehmeroperation zeigt das "tatsächlich leer"-Signal (oe) nicht notwendigerweise an, dass keine Datenelemente in der FIFO-Schaltung sind. Insbesondere gibt, wenn mehr als nur ein Datenelement vorhanden ist und das Nehmerfreigabesignal 186 (en_get) aktiviert wird, der "tatsächlich leer"-Detektor 130 das "tatsächlich leer"-Signal 132 (oe) aus.
Das mögliche Dauerblockierungssystem wird erfindungsgemäß durch eine Kombination des "fast leer"-Signals 122 und des "tatsächlich leer"-Signals 132 gelöst. In den meisten Fällen erzeugen der "fast leer"-Detektor 120 und der "tatsächlich leer"-Detektor 130 dasselbe Ergebnis, d.h., das "fast leer"-Signal 122 (ne) und das "tatsächlich leer"-Signal 132 (oe) sind dasselbe. Wenn die FIFO-Schaltung 100 einige wenige Datenelemente enthält, und das Nehmerfreigabesignal 186 (en_get) nicht während des Intervalls aktiviert wird, wenn der Zwischenspeicher 134 getaktet wird und wenn der Zwischenspeicher 136 getaktet wird, zeigen sowohl das "tatsächlich leer"-Signal 132 (oe) als auch das "fast leer"-Signal 122 (ne) an, dass die FIFO-Schaltung 100 nicht leer ist, d.h., beide Signale sind deaktiviert. In ähnlicher Weise zeigen, wenn die FIFO-Schaltung 100 null Datenelemente enthält, sowohl das "tatsächlich leer"-Signal 132 (oe) als auch das "fast leer"-Signal 122 (ne) an, dass die FIFO-Schaltung leer ist, d.h., beide Signale sind aktiviert.
Eine andere Situation entsteht, wenn die FIFO-Schaltung 100 genau ein Datenelement enthält, d.h., das "fast leer"-Signal 122 anzeigt, dass die FIFO-Schaltung "leer" ist (ne = 1) und das "tatsächlich leer"-Signal 132 anzeigt, dass die FIFO-Schaltung "nicht leer" (oe = 0) bei fehlender Aktivierung des Nehmerfreigabesignals 186 (en_get) während des vorstehend erwähnten Intervalls ist. Dieser Zustand kann entstehen, nachdem die Nehmerschnittstelle die Entnahme des "nächsten bis letzten"-Datenelementes in der FIFO-Schaltung freigegeben hat. Der nächste Schritt hängt davon ab, ob eine weitere Nehmeranforderung vorliegt: (1) Wenn der aktuelle Taktzyklus hier eine weitere Nehmeranforderung ist, wird diese Anforderung erfüllt, und der "fast leer"-Detektor 120 erklärt die FIFO für leer (d.h., das "fast leer"-Signal (ne) wird aktiviert) und startet die Nehmerschnittstelle in dem nächsten Taktzyklus. (2) Wenn keine Anforderung vorliegt, dominiert dann der "tatsächlich leer"-Detektor 130 den nächsten Taktzyklus und erklärt die FIFO-Schaltung für nicht leer (d.h., das "tatsächlich leer"-Signal (oe) wird deaktiviert), was die Erfüllung der anschließenden Nehmeranforderung ermöglicht. Sobald das letzte Datenelement aus der Warteschlange entnommen ist, dominiert das "fast leer"-Signal (ne) wiederum und blockiert sofort die Nehmerschnittstelle. An diesem Punkt werden keine weiteren Nehmeran forderungen erfüllt, so dass das "fast leer"-Signal (ne) wieder verwendet wird, um den Zustand des FIFO 100 anzuzeigen.
Die Gebersteuerung 176 ist in 20 dargestellt. Die Gebersteuerung 176 gibt die Gebeoperation und die Bewegung des Geber-Tokens in der FIFO-Schaltung 100 frei und sperrt sie. Gemäß Darstellung in 20 werden diese Operationen nur freigegeben, wenn ein gültiges Datenelement auf data_put vorhanden ist, d.h., das Geberanforderungssignal 18 (req_put) aktiviert wurde und die FIFO-Schaltung nicht voll ist, d.h., das globale Vollsignal 18 (full) nicht aktiviert wurde. In dem vorstehend beschriebenen Szenario, in welchem die FIFO-Schaltung für wenigstens einen Zyklus leer wird, wird das Nehmerfreigabesignal 186 (en_get) unabhängig davon deaktiviert, ob Nehmeranforderungssignale 24 (req_get) durch den Empfänger erzeugt werden. In einem derartigen Falle wird das "tatsächlich leer"-Signal 18 (oe) nicht in dem nächsten Taktzyklus zurückgesetzt und kann dominieren. In diesem Falle wird sobald die FIFO-Schaltung leer ist, wenn ein einziges Datenelement in die Warteschlange durch die Geberschnittstelle eingegeben wird, das "tatsächlich leer"-Signal (oe) dominant bleiben, schließlich oe deaktiviert und das globale Leersignal 28 (empty) wieder deaktiviert, und die Nehmerschnittstelle 20 wird in der Lage sein, das Datenelement zu entnehmen, um somit eine Dauerblockierung zu verhindern.
Die in 21 dargestellte Nehmersteuerung 178 gibt die Nehmeroperation und die Bewegung des Nehmer-Tokens in der FIFO-Schaltung 100 frei und sperrt sie. Das Nehmerfreigabesignal 186 (en_get) wird nur aktiviert, wenn eine Anforderung aus dem Empfänger vorliegt, d.h., das Nehmeranforderungssignal 24 (req_get) aktiviert wird, und wenigstens einer von dem "fast leer"-Detektor 120 und dem "tatsächlich leer"-Detektor 130 anzeigt, dass die FIFO-Schaltung 100 nicht leer ist.
Jede von der FIFO-Schaltung 200 (7 und 8) gemäß der zweiten Ausführungsform und von der FIFO-Schaltung 300 (9 und 10) gemäß der dritten Ausführungsform besitzt eine asynchrone Schnittstelle und eine synchrone Schnittstelle. Wie vorstehend unter Bezugnahme auf die 7–8 beschrieben, besitzt die FIFO-Schaltung 200 eine asynchrone Geberschnittstelle und eine synchrone Nehmerschnittstelle, während die vorstehend unter Bezugnahme auf die 9–10 beschriebene FIFO-Schaltung 300 eine synchrone Geberschnittstelle und eine asynchrone Nehmerschnittstelle enthält. Daher verwendet jede FIFO- Schaltung 200 und 300 bestimmte synchrone Komponenten aus der vorstehend beschriebenen FIFO-Schaltung 100. Insbesondere wird die synchrone Geberschnittstelle 10 als die Geberschnittstelle in der FIFO-Schaltung 300 verwendet. In ähnlicher Weise wird die synchrone Nehmerschnittstelle 20 in der FIFO-Schaltung 100 auch in der FIFO-Schaltung 200 als die Nehmerschnittstelle verwendet.
Wie vorstehend beschrieben, weist jede Zelle vier unterschiedliche Teile auf: eine Geberkomponente, eine Nehmerkomponente, eine Datengültigkeits-(DV)-Steuerung und ein Register. Jede von den Zellen 270a–d und 370a–d verwendet eine Version einer Datengültigkeitssteuerung, d.h., eine Datengültigkeitssteuerung 280 bzw. eine Datengültigkeitssteuerung 380. In der vorstehenden Zelle 170a (16) war die Datengültigkeitssteuerung einfach (ein SR-Zwischenspeicher 180). Jedoch wird für die FIFO-Schaltungen 200 und 300, welche sowohl synchrone als auch asynchrone Komponenten haben, das Verhalten komplexer. Diese Konstruktionen ermöglichen mehr Gleichzeitigkeit zwischen den Schreiboperationen und den Leseoperationen bei derselben Zelle. Daher muss die Datengültigkeitssteuerung diese erhöhte Gleichzeitigkeit zulassen, wie es nachstehend beschrieben wird.
Die Schnittstellen der FIFO-Schaltung gemäß der zweiten Ausführungsform, d.h., die der Asynchron-Synchron-FIFO-Schaltung 200 wurden vorstehend unter Bezugnahme auf 7 beschrieben. Sie werden erhalten, indem die asynchrone Geberschnittstelle 40 ( 3) und die synchrone Nehmerschnittstelle 20 (2) verwendet werden. Das FIFO-Schaltungsprotokoll bezüglich dieser Schnittstellen wurde unter Bezugnahme auf die 12–13 beschrieben, und die Architektur der FIFO-Schaltung 200 wurde in den 7-8 dargestellt. Gemäß spezifischer Bezugnahme auf 8 verwendet die FIFO-Schaltung 200 eine Anzahl von Komponenten, welche vorstehend beschrieben wurden, d.h., Schnittstellenkomponenten, wie z.B. die Nehmersteuerung 278, den Leer-Detektor 74 und synchrone Zellenkomponenten. Die restlichen Komponenten in den Zellen 270a–d, d.h., die asynchrone Geberkomponente und die Datengültigkeitssteuerung werden hierin unter Bezugnahme auf die 22–23 beschrieben.
Der in 23 dargestellte synchrone Teil einer Zelle 270a ist identisch mit den entsprechenden Komponenten der Zelle 170a (16) in der FIFO-Schaltung 100 (6).
Der asynchrone Teil der Zelle 270a ist in unterschiedliche Blöcke unterteilt. Der Geberkomponententeil weist den "erhalte-Geber-Token"-Block 293 (OPT) und das C-Element 295 auf. Der "erhalte-Geber-Token"-Block 293 (OPT) erhält das entsprechende Geber-Token von der rechten Schnittstelle auf dem Geber-Token-Eingang 290 (wel). Er ist als eine Bündel-Modus-Maschine gemäß Darstellung in 24 implementiert. (Bündel-Modus-Maschinen werden detaillierter in T. Chelcea et al., "Low Latency Asynchronous FIFO's using Token Rings", IEEE ASYNCH'00 Symp., pp. 210–220, welches hierin durch Bezugnahme in seiner Gesamtheit beinhaltet ist, beschrieben. Gemäß Darstellung in der Bündel-Modus-Spezifikation 400 von 24 beobachtet der "erhalte-Geber-Token"-Block 293 die rechte Zelle und wartet auf eine Geberoperation. Eine vollständige Token-Übergabe wird durch die rechte Zelle angezeigt, welche zuerst das Geber-Token-Eingangssignal 290 (wel) bei dem Schritt 402 setzt, und dann das Geber-Token-Eingangssignal 290 (wel) bei dem Schritt 404 zurücksetzt. Nachdem diese Operation stattgefunden hat, befindet sich das Geber-Token in der aktuellen Zelle, d.h., das Geber-Token-Signal 297 (ptok ist gesetzt) (Schritt 404). Wenn das Geber-Token-Signal 297 (ptok) gesetzt ist, kann eine weitere Operation stattfinden. Sobald die Geberoperation startet, wird das Geber-Token-Signal 297 (ptok) zurückgesetzt und das Geber-Token-Ausgangssignal 294 (we) bei dem Schritt 406 gesetzt. Wenn die Geberoperation endet, wird das Geber-Token-Ausgangssignal 294 (we) zurückgesetzt, das Geber-Token an die nächste Zelle gesendet und der Zyklus findet wieder statt. Eine erste Ausführungsform des "erhalte-Geber-Token"-Blockes 293 (OPT) ist in 25(a) dargestellt. Eine zweite exemplarische Ausführungsform des "erhalte-Geber-Token"-Blockes 293' (OPT) ist in 25b dargestellt.
Die Geberoperation wird durch ein C-Element 295 gemäß Darstellung in 26 gesteuert. Wie es im Fachgebiet bekannt ist, hat das asymmetrische C-Element 295 sein Ausgangssignal auf 1, wenn alle seine Eingangssignale auf 1 liegen; das Ausgangssignal wird zu 0, wenn alle seine Eingangssignale zu 0 werden. In einem asymmetrischen C-Element partizipieren einige von den (mit "+" markierten) Eingangssignalen nur an dem Setzen des Ausgangssignals des Elementes auf 1; deren Werte sind für den anderen Ausgangssignalübergang irrelevant.
Das Verhalten der Zelle 270a (23) für eine asynchrone Geberoperation läuft wie folgt ab: Zu Beginn startet eine Zelle 270a in einem leeren Zustand (e_i = 1 und f_i = 0) und weder das Geber-Token noch das Nehmer-Token sind vorhanden. Nach ein paar Übergängen bezüglich des Geber-Token-Eingangssignals 190 (wel) befindet sich das Geber-Token in der Zelle (ptok = 1). Wenn die Umgebung eine Geberoperation in Hinblick auf das Geberanforderungssignal 44 (put_req = 1) anfordert, und die Zelle leer ist (e_i = 1), wird das Geber-Token-Ausgangssignal 294 (we) gesetzt. Dieses Ereignis bewirkt mehrere Operationen parallel: Der Zustand der Zelle wird durch die Datengültigkeitssteuerung 280 (DV_as) auf voll geändert (d.h., das Voll-Bit 288a (f_i) wird aktiviert); das Register 291 (REG) wird freigegeben, um Daten zwischenzuspeichern, und die Zelle 270a startet sowohl mit dem Senden des Geber-Tokens zu der linken Zelle als auch mit dem Rücksetzen von OPT (ptok = 0). Wenn das Geberanforderungssignal 44 (put_req) deaktiviert wird, wird auch das Geber-Token-Ausgangssignal 294 (we) deaktiviert. Dieses Ereignis schließt das Senden des Geber-Tokens an die linke Zelle ab. Nun ist die Zelle 270a für den Start einer weiteren Geberoperation vorbereitet, nachdem die Daten in dem Register 291 (REG) aus der Warteschlange entnommen sind.
Die synchrone Nebenoperation in der Zelle 270a startet, nachdem ein Datenelement in der Zelle vorhanden ist. Sobald das Voll-Bit 288a (f_i) gesetzt ist, berechnet der Leer-Detektor 74 (8) den Zustand der FIFO-Schaltung 200 als "nicht leer" und eine Nehmeranforderung 24 (req_get) wird auf dem Nehmerfreigabesignal 86 (en_get) weitergeleitet. Wenn die Zelle 270a das Nehmer-Token hat, werden dann die Inhalte des Registers 291 (REG) auf den Nehmerdatenbus 26 (data_get) ausgegeben; bei der nächsten positiven Flanke des Empfängertaktsignals 22 (CLK_get) wird das Nehmer-Token an die nächste Zelle weitergegeben. In derselben Zeit wird der Zustand der Zelle durch die Datengültigkeitssteuerung 280 (DV_as) auf "leer" verändert. Man beachte, dass wenn die Zelle das Nehmer-Token (gtok = 1) enthält, das Zellengültigkeits-Bit auf dem Gültigkeitsdatenbus 284 (valid_i) unabhängig von dem Signal der Nehmeranforderung 86 (en_get) weitergegeben wird. Das stellt sicher, dass das Signal auf dem Gültigkeitsbus 284 (valid_i) immer auf einen bestimmten Wert gesteuert wird.
Gemäß Darstellung in 27 zeigt die Datengültigkeitssteuerung 280 (DV_as) an, wenn die Zelle Datenelemente enthält; sie steuert damit die Geber- und Nehmer-Operationen. Sie akzeptiert als Eingangssignale das Geber-Token-Ausgangssignal 294 (we), welches signalisiert, dass eine Geberoperation stattfindet, und das Lesefreigabesignal 299 (re), welches signalisiert, dass eine Nehmeroperation stattfindet. Die Ausgangssignale der Gültigkeitssteuerung 280 (DV_as) sind das Leer-Bit 282a (e_i), das anzeigt, dass die Zelle 270a leer ist (nur intern in dieser Ausführungsform verwendet), und das Voll-Bit 288a (f_i), das anzeigt, dass die Zelle 270a voll ist, welches in dem Leer-Detektor in dieser Ausführungsform verwendet wird).
Das Protokoll für die Datengültigkeitssteuerung 280 (DV_as) ist als ein Petri-Netz 410 in 28 dargestellt. (Ein Petri-Netz ist eine allgemein bekannte grafische Darstellung, welche üblicherweise zur Beschreibung von gleichzeitigen Verhaltensweisen verwendet wird). Es besteht aus Übergängen, die durch markierte Ereignisse dargestellt werden, und Stellen, welche Token speichern, welche durch schwarze Punkte dargestellt sind. Ein Übergang feuert, wenn alle seine ankommenden Bögen Tokens aufweisen, welche dann auf all seinen abgehenden Bögen abgelegt werden. (Weitere Details bezüglich Petri-Netzen sind in Tadao Murata, "Petri Nets: Properties, Analysis and Applications", Proceedings of the IEEE, 77(4), April 1989; L.Y. Rosenblum and A.V. Yakolev, "Signal Graphs: From Self-Timed to Timed Ones", Proceedings of International Workshop in Timed Petri-Nets, Torino, Italy, pp. 199–207, July 1985; und Tam-Anh Chu, "On the Models for Designing VLSI Asynchronous Digital Circuits", Integration, the VLSI Journal, 4(2); 99–113, June 1986 diskutiert, welche hierin in ihrer Gesamtheit durch Bezugnahme beinhaltet sind). Sobald eine Geberoperation startet, setzt die Datengültigkeitssteuerung 280 (DV_as) sowohl das Leer-Bit 282a (e_i = 0) zurück und setzt das Voll-Bit 288a (f_i = 1), und erklärt damit Zelle für voll, was bei 412 eine Nehmeroperation freigibt. Nach einem Start einer Nehmeroperation (re+) bei 414 wird die Zelle als asynchron bei 415, in der Mitte des CLK-get-Taktzyklus als "nicht voll" (f_i = 0) erklärt. Wenn die Nehmeroperation endet (bei der nächsten positiven Flanke von CLK_get) bei 416, setzt die Datengültigkeitssteuerung 280 (DV_as) die Zelle 280a auf "leer" (e_i = 1) bei 417. Das Geber-Token-Ausgangssignal 294 (we) wird bei 418 zurückgesetzt, und das Verhalten kann wieder aufgenommen werden. Dieses asymmetrische Verhalten verzögert die Weitergabe des Geber-Tokens, um eine Datenkorruption durch eine Geberoperation zu verhindern, während noch eine Nehmeroperation stattfindet.
Die FIFO-Schaltung gemäß der dritten exemplarischen Ausführungsform, d.h., die Synchron-Asynchron-FIFO-Schaltung 300 (9 und 10) wird nun detaillierter hierin be schrieben. Die Schnittstellen der FIFO-Schaltung 300 wurden vorstehend unter Bezugnahme auf 9 beschrieben. Sie werden durch "Beifügen" einer synchronen Geberschnittstelle 10 (siehe 1) und einer asynchronen Nehmerschnittstelle 50 (siehe 4) erhalten. Das FIFO-Schaltungs-Protokoll bezüglich dieser Schnittstellen wurde unter Bezugnahme auf die 11 und 14 beschrieben, und die Architektur der FIFO-Schaltung 300 wurde in den 9–10 dargestellt. Gemäß Bezugnahme auf 10 verwendet die FIFO-Schaltung 300 eine Anzahl von Komponenten, welche vorstehend beschrieben wurden, d.h., Schnittstellenkomponenten, wie z.B. die Gebersteuerung 376, den Voll-Detektor 72 und asynchrone Zellenkomponenten. Die restlichen Komponenten in den Zellen 370a, z.B. die asynchrone Geberkomponente und die Datengültigkeitssteuerung (DV_as) werden hierin unter Bezugnahme auf die 29–30 beschrieben.
Die Schnittstellen der exemplarischen Zelle 370a sind in 29 dargestellt. (Alle Zellen 370a, 370b, 370c und 370d sind identisch). Die Zelle 370a kommuniziert mit vier Schnittstellen: (1) einer synchronen Geberschnittstelle 371, (2) einer asynchronen Nehmerschnittstelle 372, (3) einer Schnittstelle 373 mit der rechten (d.h., vorausgehenden) Zelle, um Tokens zu empfangen, und (4) einer Schnittstelle 374 mit der linken (d.h., der nächsten) Zelle zum Weitergeben der Tokens. Auf der synchronen Geberschnittstelle empfängt die Zelle 370a Daten auf dem gemeinsamen Geberdatenbus 16 (data_put). Sie wird zum Durchführen einer Geberoperation durch das Geberfreigabesignal 80 (en_put) freigegeben, welche das Ausgangssignal der Gebersteuerung 76 (siehe 10) ist. Das Geberanforderungssignal 14 (req_put) zeigt eine Datengültigkeit (welche in dieser Ausführungsform immer aktiviert ist) an. Die Zelle 370a kommuniziert mit dem Voll-Detektor 72 (10), mit dem Leer-Bit 82 (e_i), welches als hoch aktiviert wird, wenn die Zelle 370a leer ist. Die Geberoperation wird durch das Sendertaktsignal 12 (CLK_put) kontrolliert. Jede Zelle 370a–d kommuniziert mit der asynchronen Nehmerschnittstelle 372, um Daten auf dem Nehmerdatenbus 56 zu übertragen (get_data), empfängt die globale Anforderung für eine Nehmeroperation 54 (get_req), und jede Zelle 370a zeigt das Ende der Warteschlangenausgabeoperation auf 55 (get_ack) an. Da die asynchrone Nehmerschnittstelle 50 nur gültige Daten weitergibt (siehe 4), wird das gültige Bit in der asynchronen Nehmerschnittstelle der Zelle 370a nicht verwendet. Jede Zelle empfängt das Geber-Token auf dem Geber-Token-Eingang 90 (ptok_in) und das Nehmer-Token auf dem Nehmer-Token-Eingang 392 (rel); sie gibt die Tokens an den Geber-Token-Ausgang 94 (ptok_out) und das Nehmer-Token an den Nehmer-Token-Ausgang 396 (re) weiter.
Der synchrone Teil der Zelle 370a ist mit den entsprechenden Komponenten der Zelle 170 der FIFO-Schaltung 100 (siehe 16) identisch. Gemäß 30 wird der asynchrone Teil der Zelle 370a in verschiedene Blöcke zerlegt, z.B. den "erhalte Nehmer-Token"-Block 393 (OGT) und das asymmetrische C-Element 395. Der "erhalte Nehmer-Token"-Block 393 (OGT) erhält den entsprechenden Nehmer-Token von der rechten Schnittstelle auf dem Nehmer-Token-Eingang 392 (re 1). Der "erhalte Nehmer-Token"-Block 393 (OGT) ist als eine Bündel-Modus-Asynchronzustands-Maschine gemäß Darstellung in 31(a) implementiert. Eine weitere exemplarische Implementation des "erhalte Nehmer-Token"-Blockes 393' (OGT) ist in 31(b) dargestellt. Die Bündel-Modusspezifikation 420 ist in 32 dargestellt. Der "erhaltene Nehmer-Token"-Block 393 (OGT) und beobachtet die rechte Zelle und wartet auf eine Nehmeroperation. Die rechte Zelle zeigt eine vollständige Token-Weitergabe an, indem sie zuerst das Nehmer-Token-Eingangssignal 392 (rel) (30) bei dem Schritt 422 setzt bzw. 424 zurücksetzt. Sobald diese Operationen abgeschlossen sind, befindet sich das Nehmer-Token in der aktuellen Zelle, d.h., das Nehmer-Token-Signal 392 (gtok) ist gesetzt (Schritt 424 in 32). Das Nehmer-Token-Ausgangssignal 396 (re) (30) wird bei dem Schritt 426 (32) gemäß Steuerung durch das asymmetrische C-Element 395 (30) gesetzt. Es startet die Nehmeroperation, wenn die Zelle voll ist, wenn sie das Nehmer-Token besitzt und wenn der Empfänger ein Datenelement anfordert. Sobald die Ausgabe aus der Warteschlange abgeschlossen ist, wird die Kommunikation mit dem Empfänger beendet, indem die Anforderung und dann die Bestätigung zurückgesetzt wird. Das Nehmer-Token-Ausgangssignal 336 (re) wird zusammen mit dem Nehmer-Token-Signal 397 (gtok) bei 427 zurückgesetzt.
Die Zelle 370a führt eine Geberoperation in derselben Weise wie die Zelle 170a aus. Wenn die Zelle mit dem Geberfreigabesignal 80 (en_put) freigegeben ist, und das Geber-Token ptok_in = 1 hat, wird das Register 391 (REG) freigegeben, um Daten in die Warteschlange einzugeben, sowie die Geberanforderung 14 (req_put), welche als das Gültigkeits-Bit verwendet wird. Parallel erklärt die Datengültigkeitssteuerung 380 (DV_as) die Zelle 370 für voll. Bei dem Start des Taktzyklusses des Sendertakts 12 (CLK_put) werden Daten in das Register zwischengespeichert und das Nehmer-Token an die nächste Zelle weitergegeben.
Die Nehmeroperation wird wie folgt durchgeführt. Zu Beginn startet die Zelle 370a mit dem Nehmer-Token (gtok = 0). Der "erhalte Nehmer-Token"-Block 393 (OGT) wartet auf einen Aufwärts- und Abwärtsübergang auf dem Nehmer-Token-Eingang 392 (rel); sobald diese auftreten, befindet sich das Nehmer-Token in der Zelle (gtok = 1), und das Ausgangssignal des Registers 391 (REG) wird auf dem Nehmerdatenbus 56 (get_data) ausgegeben. Das zwischengespeicherte Gültigkeits-Bit wird durch die asynchrone Nehmerschnittstelle nicht verwendet. Die Zelle 370a wartet auf das Empfängersubsystem (oder die Umgebung), um ein Datenelement so anzufordern, dass das Nehmeranforderungssignal 54 aktiviert wird (get_req = 1). Wenn dieses erfolgt, bestätigt die Zelle 370a dieses nur, wenn die Zelle ein Datenelement enthält, d.h., ein Voll-Bit 388a wird aktiviert (f_i = 1). Wenn die drei Bedingungen erfüllt sind (d.h., gtok = 1, get_req = 1, und f_i = 1), wird das Nehmer-Token-Ausgang 396 (re) gesetzt; dieses Ereignis bestätigt die Datenoperation für die Umgebung, startet den "erhalte Nehmer-Token"-Block 393 (OGT), startet das Rücksetzen des Zellenzustands in der Datengültigkeitssteuerung 380 (DV_as), und startet das Senden des Nehmer-Tokens an die nächste Zelle. Der Operationszyklus an der Nehmerschnittstelle wird abgeschlossen, indem das Nehmeranforderungssignal 54 (get_req) deaktiviert wird, was die Deaktivierung des Nehmer-Token-Ausgangssignals 396 (re) und den Abschluss aller mit der positiven Flanke des Nehmer-Token-Ausgangssignals 396 (re) gestarteten Operationen bewirkt.
Die Datengültigkeitssteuerung 380 (DV_as) zeigt an, wenn die Zelle full oder leer ist, und ist in 34 dargestellt. Das Protokoll für die Datengültigkeitssteuerung 380 (DV_as) ist als ein Petri-Netz 430 in 35 dargestellt. In einem normalen Leerzustand wird das Leer-Bit 382a aktiviert (e_i = 1), und das Voll-Bit 388 deaktiviert (f_i = 0). Wenn eine Geberoperation startet, setzt dann die Gültigkeitssteuerung 380 (DV_as) gleichzeitig das Leer-Bit 382 (e_i) bei dem Schritt 431 und setzt das Voll-Bit 388 (f_i) bei dem Schritt 432 (d.h., der Zustand der Zelle 370a wird "voll"), wobei dieses eine Nehmeroperation freigibt. Das Ende der Geberoperation, d.h., die Deaktivierung eines Schreibfreigabesignals 394 (we) (Schritt 433) kann gleichzeitig mit einer Nehmeroperation durchgeführt werden. Eine Nehmeroperation wird durch ein paar Übergänge auf dem Nehmer-Token-Ausgangssignal 396 (re) (Schritte 434 und 435) signalisiert, nachdem ein fallender Übergang auf re auftritt, der Zustand der Zelle sich auf "leer" (e_i = 1 und f_i = 0) bei den Schritten 436 und 437 ändert, und die Normaloperation kann wieder beginnen.
Einige hierin beschriebene zusätzliche Ausführungsformen sind im Wesentlichen zu den vorstehend beschriebenen FIFO-Schaltungen 100, 200 und 300 ähnlich, wurden jedoch modifiziert, um als eine Relaisstation zwischen einem Sender und einem Empfänger zu arbeiten. Gemäß Darstellung in 36 kann ein System 450 zwei Subsysteme, wie z.B. ein Sendersubsystem 452 und ein Empfängersubsystem 454 enthalten, welche über sehr lange Leitungen 456 und 458 verbunden sind. Bei dieser Konfiguration kann ein zwischen dem Subsystem 452 und Subsystem 454 wanderndes Signal mehrere Taktzyklen zum Wandern benötigen, und es können zusätzliche Verzögerungen eingeführt werden. Gemäß Darstellung in 37 führt ein modifiziertes System 460 Relaisstationen 462a, 462b, 462c, 462d ein, um die zusätzlichen Verbindungsverzögerungen zwischen dem Subsystem 464 und dem Subsystem 466 zu milder, wovon beide unter demselben Takt arbeiten müssen. Die Einfügung von Relaisstationen 462a, 462b, 462c und 462d teilt die langen Leitungen in Segmente 468 und 470 auf, welche jeweils weniger als einer Verzögerung eines Taktzyklusses entsprechen. Die Kette von Relaisstationen arbeitet in einer ähnlichen Weise wie FIFO-Schaltungen, indem Pakete von einem System zum anderen gesendet werden.
Die Implementation einer Eintakt-Relaisstation, wie z.B. die Relaisstation 462b, wie im Fachgebiet bekannt, ist in 38 gegeben. Normalerweise werden die Pakete aus der linken Relaisstation an die rechte Relaisstation weitergegeben. In 37 werden Pakete typischerweise von der Relaisstation 462a an die Relaisstation 462b weitergegeben. Die rechte Relaisstation, d.h., die Relaisstation 462b besitzt auch die Fähigkeit, einen Gegendruck auf den Datenstrom auszuüben, indem die Relaisstationen nach links, d.h., die Relaisstation 462a angehalten wird. Gemäß Darstellung in 38 ist eine exemplarische Relaisstation 462b zwischen der Relaisstation 462a und der Relaisstation 462c (siehe 37) angeordnet. Gemäß 38 besitzt die Relaisstation 462b zwei Register, ein Hauptregister 472 (MR), das im Normalbetrieb eingesetzt wird und ein Hilfsregister 474 (AR), das zum Speichern eines Extrapaketes verwendet wird, wenn sie angehalten wird. Im Gegensatz zu der Mischtaktzyklus-FIFO-Schaltung 100 enthält die Relaisstation weder Voll- und Leer-Signale noch Geberanforderungen und Nehmeranforderungen. Stattdessen werden im nor malen Betrieb Daten bei jedem Taktzyklus weitergegeben. Da die Datenweitergabe üblicherweise kontinuierlich ist, werden sowohl gültige als auch ungültige Daten übertragen, wobei ungültige Daten immer dann übertragen werden, wenn keine gültigen Daten in der Warteschlange eingegeben sind. Somit wird ein Gültigkeitsbit sowohl an die Geber- als auch Nehmerdatenbusse angefügt, um dadurch ein Datenpaket auf jeder Schnittstelle auszubilden.
Gemäß den 37–38 arbeitet die Relaisstation 462b (welche im Wesentlichen identisch mit den Relaisstationen 462a, 462c und 462d ist) wie folgt. Im normalen Betrieb wird zu Beginn jedes Taktzyklusses das mit dem Paketeingangssignal 468 (packetIn) von der linken Relaisstation 462a empfangene Datenpaket in das Hauptregister 472 (MR) kopiert und dann als einem Paketausgangssignal 470 (packetOut)) an die rechte Relaisstation 462c weitergeleitet. Ein Paket besteht aus einem Datenelement auf einem Datenbus und einem Gültigkeitsbit, welches die Gültigkeit der Daten in dem Paket anzeigt. Wenn das Empfängersystem 466 den Empfang von Daten anhalten möchte, aktiviert es stopIn in 476. Mit der nächsten Taktflanke aktiviert die Relaisstation 462b stopOut 478 und speichert das nächste Paket in dem Hilfsregister 474 (AR) zwischen. An diesem Punkt blockiert die Zelle. Wenn die Blockierung der Relaisstation 462b aufgegeben wird, sendet sie zuerst das Paket aus dem Hauptregister 472 (MR) an die rechte Relaisstation 462c und anschließend das eine aus dem Hilfsregister 474 (AR).
Gemäß 39 arbeitet die FIFO-Schaltung 500 als eine Mischtakt-Relaisstation. Die FIFO-Schaltung 500 ist im Wesentlichen mit der (in den 5 und 6 dargestellten) FIFO-Schaltung 100 mit den hierin angegebenen Unterschieden identisch. Die Schnittstelle der FIFO-Schaltung 500 mit der Relaisstation ist in 39 dargestellt. Die FIFO-Schaltung 500 ist in der Kette von Relaisstationen wie die in 37 dargestellte angeordnet und bildet eine Schnittstelle zwischen einer linken Relaisstationskette, wie z.B. der, welche die Relaisstationen 462a und 462b enthält, und einer rechten Relaisstationskette, wie z.B. der, die die Relaisstationen 462c und 462d enthält. Anders als das in 37 dargestellte System 460, welches nur mit einem einzigen Takt arbeitet, kann jede Relaisstationskette unter einem unterschiedlichen Takt arbeiten, d.h., die Relaisstationskette 462a/462b arbeitet unter einem ersten Taktbereich 502 und die Relaisstationskette 462c, 462d arbeitet unter einem zweiten Taktbereich 504.
Im Gegensatz zu der vorstehend beschriebenen FIFO-Schaltung 100 gibt die FIFO-Schaltung 500 immer gültige Datenelemente von der linken Geberschnittstelle 506 an die rechte Nehmerschnittstelle 508 weiter. In dem Protokoll für die FIFO-Schaltung 500 gibt es keine aktiven Anforderungen an jede Schnittstelle. Stattdessen sind die Nehmerschnittstelle 508 und die Geberschnittstelle 506 dafür konfiguriert, aktiv den kontinuierlichen Fluss von Datenelementen zu beenden oder zu unterbrechen. Die Nehmerschnittstelle 508 entnimmt Datenelemente aus der Warteschlange aus der FIFO-Schaltung 500 mit einem Paketausgangssignal 470 (packetOut)) für jeden Taktzyklus des Empfängertaktes 22 (CLK_get). Um den Fluss anzuhalten, aktiviert die Relaisstation 462c stopIn 476. In ähnlicher Weise gibt die FIFO-Schaltung 500 immer Datenelemente in die Warteschlange aus der Geberschnittstelle 506 bei einem Paketeingabesignal 468 (packetIn) ein. Somit wird anders als bei der FIFO-Schaltung 100 das Geberanforderungssignal 514 (req_put) nur zum Anzeigen der Datengültigkeit verwendet, und wird als ein Teil des Paketeingabesignals 468 (packetIn) statt als ein Steuersignal verwendet. Wenn sie voll wird, stoppt die FIFO-Schaltung 500 die Geberschnittstelle 506 durch Aktivieren von stopOut 512, welches das globale Vollsignal 18 (full) ist. Somit kann anders als das Eintakt-Relaisstationssystem 460, die Mischtakt-FIFO-Schaltungs-Relaisstation 500 auf der Geberschnittstelle 506 blockiert werden und aktiviert stopOut 478, selbst wenn kein stopIn 476 in der Nehmerschnittstelle 508 aktiviert wurde.
Die FIFO-Schaltung 500 ist ähnlich der FIFO-Schaltung 100 mit mehreren hierin angegebenen Modifikationen. Gemäß 40 ist der Voll-Detektor 72 im Wesentlichen wie vorstehend unter Bezugnahme auf die 17–19 implementiert, um die Anzahl der Leer-Bits 582a, 582b, 582c und 582d (e_i) in jeder von den Zellen 570a, 570b, 570c und 570d zu bestimmen. Der bi-modale Leer-Detektor 74 (siehe 18–19) der FIFO-Schaltung 100 ist unnötig, da die FIFO-Schaltungs-Relaisstation normalerweise Daten bei jedem Taktzyklus überträgt, sodass keine Dauerblockierung auftreten kann. Stattdessen ist der Leer-Detektor 574 im Wesentlichen mit dem "fast leer"-Detektor 120, der in der vorstehenden 18 dargestellt ist, identisch. Die Gebersteuerung 176 und die Nehmersteuerung 178 der FIFO-Schaltung 100, welche vorstehend unter Bezugnahme auf die 20–21 beschrieben wurden, sind in der FIFO-Schaltung 500 modifiziert. In der FIFO-Schaltung 100 gibt die Gebersteuerung 176 die Warteschlangeneingabe gültiger Datenelemente frei, wenn sie das Geberanforderungssignal 14 (req_put) empfängt. Die Gebersteuerung 576 der FIFO-Schaltung 500 erlaubt einfach das Durchleiten von gültigen Datenelementen. Die Gebersteuerung 576 gibt kontinuierlich Datenelemente in die Warteschlange ein, bis die FIFO-Schaltung 500 voll wird. Somit ist die Gebersteuerung 576 in der exemplarischen Ausführungsform als ein Inverter des globalen Vollsignals 18 (full) (siehe 41) implementiert. Im Gegensatz zu der Nehmersteuerung 178 der FIFO-Schaltung 100, in welcher die Entnahme aus der Warteschlange auf Bedarf erfolgte, gibt die Steuerung 578 eine kontinuierliche Entnahme der Datenelemente frei. Gemäß Darstellung in 42 wird die Entnahme aus der Warteschlange nur unterbrochen, wenn die FIFO-Schaltung 500 leer wird (das "fast leer"-Signal 122 (ne) wird wie vorstehend beschrieben, aktiviert) oder die Geberschnittstelle signalisiert, dass sie keine Datenelemente mehr annehmen kann, indem sie stopIn 476 aktiviert). Da sowohl gültige als auch ungültige Daten weitergegeben werden können, verwendet die Nehmersteuerung 678 auch das Gültigkeitsbit 584 (valid_i), um das Gültigkeitssignal 30 (valid_get) zu berechnen.
Gemäß den 43, 44, 45, 47, 48 und 49 sind die FIFO-Schaltungen 600 und 700 zwei zusätzliche Ausführungsformen, die als Relaisstationen arbeiten, welche dafür konfiguriert sind, mit gemischten asynchronen-synchronen bzw. synchronen-asynchronen Schnittstellen zu arbeiten. Die FIFO-Schaltungen 600 und 700 befassen sich mit zwei kritischen Konstruktionsherausforderungen: Der Fähigkeit einer Schnittstellenerzeugung zwischen gemischten asynchronen/synchronen Umgebungen und mit langen Zwischenverzögerungen.
Die Grundarchitektur einer Kommunikation zwischen einem asynchronen Sender 490 und einem synchronen Empfänger 466 mit Relaisstationen ist in 43 dargestellt. Der asynchrone Bereich sendet Datenpakete (möglicherweise über eine Kette asynchroner Relaisstationen (ARS) 494a und 494a, die hierin detaillierter diskutiert werden) an die FIFO-Schaltung 600. Die Pakete werden dann an den synchronen Bereich übertragen, und durch die Kette synchroner Relaisstationen 462a und 462b an den Empfänger 466 gesendet.
Im Prinzip kann die Kommunikation an der asynchronen Schnittstelle beliebig robust gemacht werden, sodass keine Relaisstationen an den Ausgängen der asynchronen Bereiche benötigt werden. In der Praxis müssen jedoch Richtigkeits- und Leistungsprobleme in den FIFO-Konstruktionen beachtet werden. Zwei übliche asynchrone Datencodierungsarten sind im Fachgebiet bekannt: Doppel-Schienen und Einzel-Schienen-Bündeldaten. (Einzelschienen-Bündeldaten sind detaillierter in S. Furber, Asynchronous Design", Proc. of Submicron Electronics, pp. 461–492, 1997, welche hierin durch Bezugnahme in Gesamtheit beinhaltet ist, beschrieben.) Die Doppelschienenart, welche sowohl den Wert als auch die Gültigkeit jedes Daten-Bits auf einem Paar von Leitungen codiert, ist beliebig robust in Bezug auf Leitungsverzögerungen (hat jedoch einen erheblichen Überbau) und erfordert keine Kette von ARS's. Die Einzelschienen-Bündeldatenart hat Zeitannahmen zwischen den Daten selbst und den Steuerleitungen, sodass eine Kette von ARS's erwünscht sein kann, um die Leitungslängen zwischen den Stufen auf kurze Stücke zu begrenzen. Ferner können wegen des Problems der Leistung, selbst wenn keine ARS's erforderlich sind, diese erwünscht sein, um den Durchsatz zu erhöhen. Eine Kette von ARS's kann direkt implementiert werden, indem eine asynchrone FIFO-Schaltung implementiert wird, welche üblicherweise als eine Mikropipeline bekannt ist (weitere Details über Mikropipelines sind in I. Sutherland; "Micropipelines", Communications of the ACM, 32(6). Pp. 720–738, 1989 und M. Singh et al. "MOUSETRAP: Ultra High-Sped Transition-Signalling Asynchronous Pipelines", ACM RAU-00 Workshop, 2000 beschrieben, welche beide hierin durch Bezugnahme in ihrer Gesamtheit beinhaltet sind).
Anders als die synchronen Datenpakete erfordern die asynchronen Datenpakete kein Gültigkeits-Bit. Stattdessen wird das Vorhandensein von gültigen Datenpaketen auf Steueranforderungsleitungen signalisiert und ein ARS kann unbegrenzt zwischen Empfangsdatenpaketen warten. Daher implementiert eine Standardmikropipeline das gewünschte ARS-Verhalten.
Die FIFO-Schaltung 600, welche in den 44 und 45 dargestellt ist, arbeitet zwischen einem asynchronen Bereich 602 und einem synchronen Bereich 604. Die asynchrone Schnittstelle 640 ist identisch und unterstützt dasselbe Kommunikationsprotokoll wie die asynchrone Schnittstelle 40 in der vorstehend beschriebenen FIFO-Schaltung 200. Diese Schnittstelle entspricht genau den Mikropipeline-Schnittstellen. In ähnlicher Weise ist die synchrone Schnittstelle 620 identisch und unterstützt dasselbe Kommunikationsprotokoll wie die entsprechende synchrone Nehmerschnittstelle 508 in der FIFO-Schaltung 500. Gemäß 45 ist die FIFO-Schaltung 600 auf Aufbauebene identisch mit der in 8 darge stellten FIFO-Schaltung 200. Zellen 670a, 670b, 670c und 670d sind im Wesentlichen identisch mit Zellen 270a, 270b, 270c und 270d. Die Nehmersteuerung 678 unterscheidet sich von der Nehmersteuerung 278 (welche im Wesentlichen identisch mit der Nehmersteuerung 178 ist), wie es nachstehend beschrieben wird. Der Leer-Detektor 674 ist im Wesentlichen identisch mit dem Leer-Detektor 574 in der FIFO-Schaltung 500 und entspricht dem in der vorstehend in 18 dargestellten "fast leer"-Detektor 120.
Die FIFO-Schaltung 600 arbeitet wie folgt. Wenn ein Datenelement an seiner asynchronen Schnittstelle 640 vorhanden ist, gibt es die FIFO-Schaltung 600 in die Warteschlange ein. Auf der synchronen Schnittstelle 620 gibt die FIFO-Schaltung 600 ein Datenelement bei jedem Taktzyklus aus, sofern sie nicht leer ist oder durch die rechte Relaisstation angehalten wird. Somit ist im Gegensatz zur FIFO-Schaltung 500 ein Datenpaket nur ungültig, wenn die FIFO-Schaltung 600 blockiert ist. Die Nehmerschnittstelle 620 ist blockiert, wenn die FIFO-Schaltung 600 leer oder von rechts aus angehalten ist. Da jedoch die FIFO-Schaltung 600 keine ungültigen Datenpakete in die Warteschlange eingibt, empfängt die rechte Schnittstelle nur gültige Datenpakete, falls die FIFO-Schaltung 600 nicht blockiert ist.
Die Implementation der Nehmersteuerung 678 ist in 46 dargestellt. Die Nehmersteuerung 678 gibt eine Nehmeroperation (en_get = 1) frei, wenn sie nicht von der rechten Seite aus angehalten wird (stopIn = 0), und wenn die Relaisstation nicht leer ist (ne = 0). Diese arbeitet in derselben Weise wie die Nehmersteuerung 178 der FIFO-Schaltung 100. Das nach rechts gesendete Paket ist ungültig, wenn entweder die Relaisstation angehalten ist oder diese leer ist. Daher sind alle von der asynchronen Schnittstelle empfangenen Pakete gültig, und somit besteht kein Bedarf für ein bestimmtes Gültigkeits-Bit, da stattdessen das Nehmerfreigabesignal 686 (en_get) als das Gültigkeitssignal 30 (valid_get) verwendet wird.
Die Grundarchitektur einer Kommunikation zwischen einem synchronen Sender 464 und einem asynchronen Empfänger 492 mit Relaisstationen ist in 47 dargestellt. Der synchrone Bereich sendet Datenpakete über eine Kette von synchronen Relaisstationen 462a und 462b an die FIFO-Schaltung 800. Die Pakete werden dann an den asynchronen Empfänger 292, bevorzugt über die Kette der ARS 494a und 494b in dem asynchronen Bereich übertragen.
Die Schnittstellen der FIFO-Schaltung 700 sind in 48 dargestellt. Die asynchrone Schnittstelle 750 ist im Wesentlichen mit der asynchronen Schnittstelle 50 der in 9 dargestellten FIFO-Schaltung 500 identisch und unterstützt dasselbe Kommunikationsprotokoll. In ähnlicher Weise ist die in 48 dargestellte synchrone Schnittstelle 710 im Wesentlichen mit der synchronen Schnittstelle 10 der FIFO-Schaltung 300 identisch und unterstützt dasselbe Kommunikationsprotokoll. Die Zellen 770a, 770b, 770c und 770d der in 49 dargestellten FIFO-Schaltung 700 sind im Wesentlichen mit den Zellen 370a, 370b, 370c und 370d der in 10 dargestellten FIFO-Schaltung identisch. Der einzige wesentliche Unterschied zwischen der FIFO-Schaltung 700 und der FIFO-Schaltung 300 ist die Nehmersteuerung jeder FIFO-Schaltung.
Während des Normalbetriebs überträgt die FIFO-Schaltung 700 Datenpakete von der synchronen Schnittstelle an die asynchrone. Die asynchronen Relaisstationen auf der rechten Seite geben ein Datenpaket in die Warteschlange ein, sobald die FIFO-Schaltung 700 Daten liefert. Jedoch wirkt auf der synchronen Schnittstelle die FIFO-Schaltung 700 als ein Filter, da alle asynchronen Datenpakete gültig sein müssen. Das Gültigkeits-Bit 14 (valid_put) der ankommenden synchronen Pakete wird für deren Filterung verwendet. Insbesondere wird, wenn das Paket gültig ist, die FIFO-Schaltung 700 dafür konfiguriert, diese in die Warteschlange einzugeben; andererseits wird sie dafür konfiguriert, dieses zu verwerfen. Die FIFO-Schaltung 700 gibt nur gültige Datenpakete in die Warteschlange ein und blockiert die Geberschnittstelle, wenn die FIFO-Schaltung 700 voll ist. Die FIFO-Schaltung 500 gemäß vorstehender Beschreibung gibt alle empfangenen Datenpakete ein und blockiert, wenn keine weiteren vollen Zellen mehr vorhanden sind. Im Gegensatz dazu blockiert die FIFO-Schaltung 700 unter den nachstehenden Bedingungen: (1) wenn die FIFO-Schaltung voll ist und/oder (2) ein ungültiges Datenpaket empfangen wird.
Die exemplarische Implementation der Gebersteuerung 776 ist in 50 angegeben. Die Gebersteuerung 776 gibt eine Geberoperation (en_put = 1) nur frei, wenn die Relaisstation nicht voll ist (full = 0) und das ankommende Datenpaket gültig ist (valid_put = 1). Die Implementation der Gebersteuerung 776 ist ähnlich der Gebersteuerung 176, aber die Rolle des expliziten Geberanforderungssignals (wie z.B. req_put) wird von einem impliziten Gültigkeits-Bit 14 (valid_put) übernommen, welches jedes Datenpaket begleitet.
Beispiel
Um die Leistung der verschiedenen FIFO-Schaltungskonstruktionen zu bewerten, wurde jede exemplarische FIFO-Schaltung 100, 200, 300, 500, 600 und 700 simuliert. Jede FIFO-Schaltung wurde sowohl unter Verwendung kommerzieller als auch akademischer Werkzeuge simuliert. Die Konstruktionen wurden sowohl unter Verwendung von Bibliotheks- als auch kundenspezifischen Schaltkreisen aufgebaut und wurden unter Verwendung von Cadence HSPICE simuliert. Die Bündel-Modussteuerungen wurden unter Verwendung von Minimalist (Minimalist wird detaillierter in R. Fuhrer et al., MINIMALIST: An Environment for Synthesis, Verification and Testability of Burst Mode Asychronouos Maschines", CUCS-020-99, 1990 beschrieben, welches hierin in seiner Gesamtheit beinhaltet ist) und die Petri-Netzsteuerungen wurden unter Verwendung von Petrify synthetisiert (Petrify wird detaillierter in J. Cortadella et al., "Petrify: A Tool for Manipulating Concurrent Specifications and Synthesis of Asynchronous Controllers", IEICE Transactions an Information and Systems, Vol. E80-D, Number 3, pp. 315–325, March 1997, welches hierin in seiner Gesamtheit beinhaltet ist beschrieben). Die FIFO-Schaltungskonstruktionen wurden in einer 0,6 μ HP CMOS-Technologie bei 3,3 V und 300 K simuliert.
Die nachstehenden sind einige von den speziellen Überlegungen bei der Modellierung von globalen Steuer- und Datenbussen: Die Steuerbusse put_req/en_put und get_req/en_get wurden mit entsprechender Pufferung versehen. Die Bestätigungssignale put_ack und get_ack sind als ein Baum von OR-Gattern aufgebaut, welche die einzelnen Bestätigungen in eine einzige globale vereinen. Bei der Modellierung von get_data und data_get wurde jedes Bit in dem Bus mittels Tri-state-Puffern betrieben. Sowohl die durch die Umgebung beigetragene Last als auch die durch die langen Leitungen innerhalb der FIFO-Schaltung wurden modelliert. Das Modell machte die Annahme, dass die Umgebung zu der Last mit zwei Invertern (die etwa einem Zwischenspeicher entsprechen) beiträgt, und dass jede Leitung mit einer Kapazität von zwei Invertern pro Zelle (etwa 2n Inverter pro Leitung) beiträgt.
Zwei Messungen wurden für jede Konstruktion simuliert: Latenz und Durchsatz. Latenz ist die Verzögerung von der Eingabe von Daten an der Geberschnittstelle bis zu deren Vorhandensein an dem Ausgang der Nehmerschnittstelle in einer leeren FIFO-Schaltung. Durchsatz ist als die umgekehrte Zykluszeit für eine Geber- oder Nehmeroperation definiert. Der Durchsatz und die Latenz wurden für unterschiedliche FIFO-Schaltungsumfänge und Datenelementbreiten berechnet. Der FIFO-Schaltungsumfang wurde auf 4, 8 oder 16 Zellen festgelegt. Für jede dieser FIFO-Schaltungen wurde die Datenelementbreite entweder auf 8 oder 18 Bit festgelegt.

Die Ergebnisse für den maximalen Durchsatz sind in den Tabellen 1 und 2 angegeben. Für synchrone Schnittstellen ist der Durchsatz als maximale Taktfrequenz ausgedrückt, mit welcher die Schnittstelle getaktet werden kann. Da die asynchronen Schnittstellen keinen Takt besitzen, ist der Durchsatz in MegaOps/s (der Anzahl von Datenoperationen, die eine Schnittstelle in einer Sekunde durchführen kann) angegeben.

	4-Plätze		8-Plätze		16-Plätze
Ausführungsform	Geber	Nehmer	Geber	Nehmer	Geber	Nehmer
Schaltung 100	565	549	544	523	505	484
Schaltung 200	421	549	379	523	357	484
Schaltung 300	565	454	544	392	505	360
Schaltung 500	580	539	550	517	509	475
Schaltung 600	421	539	379	517	357	475
Schaltung 700	580	454	550	392	509	360

TABELLE 1

	4-Plätze		8-Plätze		16-Plätze
Ausführungsform	Geber	Nehmer	Geber	Nehmer	Geber	Nehmer
Schaltung 100	505	492	488	471	460	439
Schaltung 200	386	492	351	471	332	439
Schaltung 300	505	417	488	362	460	335
Schaltung 500	521	478	498	459	467	430
Schaltung 600	386	478	351	459	332	430
Schaltung 700	521	417	498	392	467	360

TABELLE 2

Die Durchsatzergebnisse sind konsistent mit den FIFO-Schaltungskonstruktionen. Die synchronen Nehmerschnittstellen sind aufgrund der Komplexität des Leer-Detektors 74 langsamer aus die synchronen Geberschnittstellen. Ferner sind auch synchrone Geberschnittstellen von Relaisstationen etwas schneller als ihre FIFO-Schaltungsgegenstücke aufgrund der Vereinfachung des Geber-Detektors in den ersteren. Auf der synchronen Seite sind die Nehmerschnittstellen tendenziell schneller als die Geber hauptsächlich deswegen, weil die Ausgabe der Register früh auf dem Datenbus freigegeben wird.

Latenzen (ns) durch leere FIFO-Schaltungen sind nur für Konstruktionen mit 8 Bit Datenelementen (Tabelle 3) dargestellt.

	4-Plätze		8-Plätze		16-Plätze
Ausführungsform	Min.	Max.	Min.	Max.	Min.	Max.
Schaltung 100	5,43	6,34	5,79	6,64	6,14	7,17
Schaltung 200	5,53	6,45	6,13	7,17	6,47	7,51
Schaltung 300	1,95		2,18		2,44
Schaltung 500	5,48	6,41	6,05	7,02	6,23	7,28
Schaltung 600	5,61	6,35	6,18	7,13	5,57	7,62
Schaltung 700	1,86		2,23		2,43

TABELLE 3

Der experimentelle Aufbau für Latenz ist wie folgt: in einer leeren FIFO-Schaltung fordert die Nehmerschnittstelle ein Datenelement an. Zu einem beliebigen Zeitpunkt später legt die Geberschnittstelle ein Datenelement an. Die Latenz wird als die verstrichene Zeit zwischen dem Moment berechnet, wenn der Geberdatenbus gültige Daten besitzt, bis zu dem Moment, wenn die Geberschnittstelle das Datenelement erhält und dieses verwenden kann.
Die Latenz für eine FIFO-Schaltung mit einem synchronen Empfänger ist nicht eindeutig definiert. Die Latenz variiert mit dem Moment, wenn die Datenelemente sicher in eine Zelle eingegeben sind. Wenn das Datenelement in die Warteschlange durch die Geberschnittstelle unmittelbar nach der positiven Flanke von CLK_get eingegeben wird, ist die Latenz erhöht (Spalte Max. in der Tabelle). Wenn das Datenelement unmittelbar in die Warteschlange eingegeben wird, bevor der Leer-Detektor mit der Berechnung startet, ist dann die Latenz verringert (Spalte Min). Der asynchrone Empfänger ist jedoch in der Lage, das Datenelement unmittelbar nach dessen Eingabe in die Warteschlange zu erfassen; daher ist die Latenz eindeutig definiert. Interessanter ist, dass, da der asynchrone Empfänger keine Synchronisation benötigt, die Latenz für eine Kommunikation zu einem asynchronen Bereich wesentlich schneller gemacht werden kann.
Die Durchsatz- und Latenzergebnisse sind für eine Bus-basierende Konstruktion ziemlich gut. Wie erwartet, nehmen sowohl der Durchsatz als die Latenz ab, wenn der FIFO-Schaltungsumfang oder die Datenelementbreite zunimmt. Der Durchsatz ist tendenziell für synchrone Schnittstellen höher als für asynchrone. Die Latenz durch eine leere FIFO-Schaltung ist kleiner, wenn der Empfänger asynchron ist.

Claims

FIFO-Schaltung (100; 200; 300; 500; 600; 700), welche eine Schnittstelle zur Übertragung von Datenelementen zwischen einem unter einem ersten Zeitbereich arbeitenden Sendersubsystem und einem unter einem zweiten Zeitbereich arbeitenden Empfängersubsystem bereitstellt, wobei der erste Zeitbereich und der zweite Zeitbereich unterschiedlich sind, und wenigstens einer von den Zeitbereichen abhängig von einem Taktsignal arbeitet, wobei die FIFO-Schaltung aufweist: eine Geberschnittstelle (10; 40), die dafür konfiguriert ist, gemäß dem ersten Zeitbereich zu arbeiten, umfassend einen Geberdatenbus (16; 46), um ein Datenelement aus dem Sendersubsystem zu übertragen, und einen Geberdaten-Anforderungseingang (14; 44) um eine Geberanforderung aus dem Sendersubsystem zu empfangen, um das Datenelement aus dem Geberdatenbus (14, 46) in eine Warteschlange einzugeben; eine Nehmerschnittstelle (20; 50), die dafür konfiguriert ist, gemäß dem zweiten Zeitbereich zu arbeiten, umfassend einen Nehmerdatenbus (26; 56), um das Datenelement an das Empfängersubsystem zu übertragen, und einem Nehmerdatenanforderungseingang (24; 54), um eine Nehmeranforderung aus dem Sendersubsystem zu empfangen, um das Datenelement aus der Warteschlange an den Nehmerdatenbus (26; 56) auszugeben; und eine Anordnung von Zellen (170; 270; 370; 570; 670; 770), wobei jede Zelle aufweist: ein Register (191; 291; 391), das dafür konfiguriert ist; das Datenelement von dem Geberdatenbus (16; 46) zu empfangen und das Datenelement an den Nehmerdatenbus (26; 56) zu senden; eine Zustandsteuerung, die dafür konfiguriert ist, eine Anzeige des vollen oder leeren Zustands der Zelle zu liefern; eine Nehmerkomponente, die dafür konfiguriert ist, gemäß dem ersten Zeitbereich zu arbeiten, um ein erstes Geber-Token (Sendeberechtigungszeichen) von einer ersten benachbarten Zelle zu empfangen, das von dem Geberdatenbus (16; 46) empfangene Datenelement in dem Register (191; 291; 391) auf der Basis der Geberanforderung, des Geber-Tokens und des Zustands der Zelle zu speichern, und das Geber-Token an eine zweite benachbarte Zelle zu übergeben; und eine Nehmerkomponente, die dafür konfiguriert ist, gemäß dem zweiten Zeitbereich zu arbeiten, um das Nehmer-Token aus der ersten benachbarten Zelle zu empfangen, um das Datenelement aus dem Warteschlangenregister (191; 291; 391) an den Nehmerdatenbus (26; 56) auf der Basis der Nehmeranforderung, des Nehmer-Tokens und des Zustands der Zelle auszugeben, und das Nehmer-Token an die zweite benachbarte Zelle zu übergeben.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 1, wobei die Nehmerschnittstelle (10) synchron ist und von einem ersten Taktsignal (12) gesteuert ist, und die Nehmerschnittstelle (10) ferner aufweist: einen Voll-Detektor, welcher ein globales Voll-Signal (18) synchronisiert mit dem ersten Taktsignal (12) erzeugt, welches ein positives Signal ist, wenn weniger als eine vorbestimmte Anzahl von aufeinander folgenden Zellen in der Anordnung der Zellen (170; 270; 370; 570; 670; 770) in einem leeren Zustand sind; und eine Gebersteuerung (176; 376; 576; 776), die dafür konfiguriert ist, die Geberanforderung (14) an die Geberkomponente jeder Zelle in der Anordnung von Zellen (170; 270; 370; 570; 670; 770) zu liefern, wenn das globale Voll-Signal (18) nicht positiv ist.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 2, wobei die Geberkomponente jeder Zelle in der Anordnung von Zellen (170; 270; 370; 570; 670; 770) ferner aufweist: einen synchronen Zwischenspeicher, der von der Geberanforderung dafür freigegeben wird, das Geber-Token an die zweite benachbarte Zelle zu übergeben; eine Schaltung, die dafür konfiguriert ist, der Zustandsteuerung zu signalisieren, eine Anzeige zu erzeugen, die einen Leer-Zustand der Zelle in Reaktion auf die Geberanforderung und das Geber-Token negativ macht.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 2, wobei das Register (191; 291; 391) durch die Geberanforderung (14) dafür freigegeben wird, das Datenelement zu empfangen.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 2, wobei die Nehmerschnittstelle (20) synchron ist und von einem zweiten Taktsignal (22) synchronisiert ist, und die Nehmerschnittstelle (20) ferner aufweist: einen ersten Leer-Detektor (120), welcher ein erstes globales Leer-Signal (122) synchron mit dem zweiten Taktsignal (22) erzeugt, welches positiv wird, wenn weniger als eine vorbestimmte Anzahl aufeinander folgender Zellen der Anordnung von Zellen (170; 270; 370; 570; 670; 770) sich in einem vollem Zustand befinden; einen zweiten Leer-Detektor (130), welcher ein zweites globales Leer-Signal (132) erzeugt und welcher aufweist: eine Schaltung, welche ein erstes Zwischensignal erzeugt, das positiv ist, wenn keine von den Zellen in der Anordnung von Zellen (170; 270; 370; 570; 670; 770) sich in dem vollen Zustand befindet; einen ersten und zweiten Zwischenspeicher (134; 136), welche das erste Zwischensignal mit den zweiten Taktsignal (22) synchronisieren; und ein Kombinationselement, welches ein zweites Zwischensignal mit dem ersten Zwischensignal zwischen dem ersten Zwischenspeicher (134) und dem zweiten Zwischenspeicher (136) synchronisiert, wobei das zweite globale Leer-Signal (132) das erste Zwischensignal ist, wenn das zweite Zwischensignal negativ ist, und das zweite globale Leer-Signal (132) das zweite Zwischensignal ist, wenn das zweite Zwischensignal positiv ist; und eine Nehmersteuerung (178; 278; 578; 678), die dafür konfiguriert ist, die Nehmeranforderung (24) an die Nehmerkomponente in jeder Zelle in der Anordnung von Zellen (170; 270; 370; 570; 670; 770) zu liefern, wenn eines von dem ersten globalen Leer-Signal (122) und dem zweiten globalen Leer-Signal (132) negativ ist.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 5, wobei die Nehmerkomponente jeder Zelle in der Anordnung von Zellen (170; 270; 370; 570; 670; 770) ferner aufweist: einen synchronen Zwischenspeicher, der von der Nehmeranforderung (24) dafür freigegeben wird, das Nehmer-Token an die zweite benachbarte Zelle zu übergeben; und eine Schaltung, die dafür konfiguriert ist, der Zustandssteuerung zu signalisieren, eine Anzeige zu erzeugen, die einen Voll-Zustand der Zelle in Reaktion auf die Geberanforderung und das Geber-Token negativ macht.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 5, wobei das Register (191; 291; 391) durch die Nehmer-Anforderung (24) und das Nehmer-Token dafür freigegeben wird, das Datenelement an den Nehmerdatenbus (26) zu übertragen.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 2, wobei die Nehmerschnittstelle (50) asynchron ist, und die Nehmerkomponente jeder Zelle in der Anordnung von Zellen (170; 270; 370; 570; 670; 770) eine Nehmer-Token-Übergabeschaltung aufweist, die dafür konfiguriert ist, das Nehmer-Token in der entsprechenden Zelle in der Anordnung von Zellen (170; 270; 370; 570; 670; 770) in Reaktion auf ein Signal aus der ersten benachbarten Zelle, das eine Ausgabe des Da tenelementes aus dem Warteschlangenregister (191; 291; 391) der ersten benachbarten Zelle an den Nehmerdatenbus (56) anzeigt, zu empfangen.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 8, wobei das Register (191; 291; 391) durch das Nehmer-Token dafür freigegeben wird, das Datenelement aus der Warteschlange an den Nehmer-Datenbus (56) auszugeben.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 9, wobei die Nehmerschnittstelle (50) ferner ein Nehmer-Bestätigungssignal (55) aufweist, und die Nehmerkomponente ferner eine Nehmer-Steuerschaltung aufweist, die durch das Nehmer-Token, die Nehmeranforderung und den vollen Zustand der Zelle dafür freigegeben wird, der Zustandssteuerung zu signalisieren, den Zustand der Zelle (170; 270; 370; 570; 670; 770) zurückzusetzen, um das Nehmer-Bestätigungssignal positiv zu machen.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 10, wobei die Nehmer-Steuerschaltung durch Negierung der Nehmeranforderung, für die Übergabe des Nehmer-Tokens an die zweite benachbarte Zelle, gesperrt wird.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 1, wobei die Geberschnittstelle (40) asynchron ist, und die Geberkomponente jeder Zelle in der Anordnung von Zellen (170; 270; 370; 570; 670; 770) eine Geber-Token-Übergabeschaltung aufweist, die dafür konfiguriert ist, das Geber-Token in der entsprechenden Zelle in der Anordnung von Zellen (170; 270; 370; 570; 670; 770) in Reaktion auf ein Signal aus der ersten benachbarten Zelle, das eine Zwischenspeicherung des Datenelementes von dem Geberdatenbaus (46) in dem Register (191; 291; 391) der ersten benachbarten Zelle anzeigt, zu empfangen.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 12, wobei die Geberschnittstelle (40) ferner ein Geberbestätigungssignal (45) erzeugt und die Geberkomponente ferner eine Geber-Steuerschaltung aufweist, die durch das Geber-Token, die Geberanforderung, und den Leer-Zustand der Zelle dafür freigegeben wird, das Register (191; 291; 391) freizugeben, das Datenelement von dem Geberdatenbus (46) zu empfangen und der Zustandsteuerung zu signalisieren, eine Anzeige für die Rücksetzung des Zustandes der Zelle zu erzeugen und das Geber-Bestätigungssignal positiv zu machen.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 12, wobei die Geber-Steuerschaltung durch Negierung der Geberanforderung für die Weitergabe des Geber-Tokens an die zweite benachbarte Zelle gesperrt wird.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 12, wobei der zweite Zeitbereich synchron ist und von einem zweiten Taktsignal (22) gesteuert wird, und die Nehmerschnittstelle (20) ferner aufweist: einen ersten Leer-Detektor (120), welcher ein erstes globales Leer-Signal (122) synchronisiert mit dem zweiten Taktsignal (22) erzeugt, welches positiv wird, wenn weniger als eine vorbestimmte Zahl aufeinander folgender Zellen in der Anordnung der Zellen (170; 270; 370; 570; 670; 770) sich in dem vollen Zustand befindet; einen zweiten Leer-Detektor (130), welcher ein zweites globales Leer-Signal (132) erzeugt, und welcher aufweist: eine Schaltung, welche ein erstes Zwischensignal erzeugt, das positiv wird, wenn sich keine von den Zellen in der Anordnung der Zellen (170; 270; 370; 570; 670; 770) in dem vollen Zustand befindet; einen ersten und zweiten Zwischenspeicher (134; 136), welche das erste Zwischensignal mit dem zweiten Zwischensignal (22) synchronisieren; und ein Kombinationselement, welches das zweite Zwischensignal mit dem ersten Zwischensignal zwischen dem ersten Zwischenspeicher (134) und dem zweiten Zwischenspeicher (136) kombiniert, wobei das zweite globale Leer-Signal (132) das erste Zwischensignal ist, wenn das zweite Zwischensignal negativ ist, und das zweite globale Leer-Signal (132) das zweite Zwischensignal ist, wenn das zweite Zwischensignal positiv ist; und eine Nehmersteuerung (178; 278; 578; 678), die dafür konfiguriert ist, die Nehmeranforderung (24) an die Nehmerkomponente in jeder Zelle in der Anordnung der Zellen (170; 270; 370; 570; 670; 770) zu liefern, wenn eines von dem ersten globalen Leer-Signal (122) und dem zweiten globalen Leer-Signal (132) negativ ist.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 15, wobei die Nehmerkomponente in jeder Zelle in der Anordnung von Zellen (170; 270; 370; 570; 670; 770) ferner aufweist: einen synchronen Zwischenspeicher, der von der Nehmeranforderung (24) dafür freigegeben wird, das Nehmer-Token an die zweite benachbarte Zelle zu übergeben; und eine Schaltung, die dafür konfiguriert ist, der Zustandsteuerung zu signalisieren, eine Anzeige des Leerzustands der Zelle in Reaktion auf die Nehmeranforderung und das Nehmer-Token zu erzeugen.
FIFO-Schaltung (100; 200; 300; 500; 600; 700) nach Anspruch 16, wobei das Register (191; 291; 391) durch die Nehmeranforderung (24) und das Nehmer-Token dafür freigegeben wird, das Datenelement an den Nehmer-Datenbus (26) zu übertragen.