Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
CACHE MEMORY FOR TWO-DIMENSIONAL DATA FIELDS
Document Type and Number:
WIPO Patent Application WO/1999/059069
Kind Code:
A1
Abstract:
The invention relates to a cache memory, especially for processing images. The special configuration of a memory field (CMEM), an allocation unit (MAP), a write queue (WQ), a read queue (RQ) and a data conflict recognition unit (HDET) enable a number of data items to be read out from the memory field simultaneously per cycle, in the form of line or column segments. The format of the screen windows that are read out can change from one cycle to another. With sufficient data locality, time-consuming reloading operations do not damage the data throughput since the access requests are pipelined.

Inventors:
HACHMANN ULRICH (DE)
Application Number:
PCT/DE1999/001190
Publication Date:
November 18, 1999
Filing Date:
April 20, 1999
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
SIEMENS AG (DE)
HACHMANN ULRICH (DE)
International Classes:
G06F5/10; G06F12/08; G06F12/0875; G06T1/60; (IPC1-7): G06F12/08
Foreign References:
US5642494A1997-06-24
US5742831A1998-04-21
US5602984A1997-02-11
US5428725A1995-06-27
Attorney, Agent or Firm:
VIERING, JENTSCHURA & PARTNER (Postfach 22 14 43 München, DE)
Download PDF:
Description:
Beschreibung Cache-Speicher für zweidimensionale Datenfelder.

Die Erfindung betrifft einen Cache-Speicher, der bei einer Verarbeitungseinheit eine höhere Taktfrequenz erlaubt als die maximal zulässige Taktfrequenz aufgrund der Eigenschaften von externen Speicherbausteinen und der Leiterplatte. Cache- Speicher in herkömmlichen Prozessorstrukturen, wie beispiels- weise im Motorola MC68040 erlauben in der Regel nur den Zu- griff auf ein einzelnes Datenwort pro Takt. Bei der zweidi- mensionalen Datenfeldern, wie z. B. Bildern, bedeutet dies, daß zum Auslesen eines Bildbereiches aus dem Cache-Speicher mehrere Takte notwendig sind, wenn in einem Datenwort die be- nötigten Pixel nicht zufällig nebeneinander liegen, und zwar auch dann, wenn alle Daten schon im Cache vorhanden sind.

Aus dem IEEE Journal of Solid State Circuit, Vol. 25, No. 3, June 1990, sind on-chip-Speicher mit mehreren Zeilenpuffern, die komplette Bildzeilen speichern, bekannt, wobei übereinan- derliegende Pixel aus übereinander angeordneten Zeilenpuffern ausgelesen werden und ausgelesene Pixel in den nächsten Zei- lenpuffer transferiert werden, damit sie sich beim nächsten Zugriff, welcher dann um eine Zeile versetzt stattfindet, an der richtigen Position befinden. Dies hat jedoch die Nachtei- le, daß die Bildbreite durch die Puffergröße begrenzt, die Art des Auslesens festgelegt und ein spaltenorientiertes Ver- arbeiten der Bilddaten nicht ohne Nachladen möglich ist.

Die der Erfindung zugrundeliegende Aufgabe besteht nun darin, einen Cache-Speicher anzugeben, der die obengenannten Nach- teile vermeidet.

Diese Aufgabe wird erfindungsgemäß durch die Merkmale des Pa- tentanspruchs 1 gelöst. Die weiteren Ansprüche betreffen be- vorzugte Ausgestaltungen des Cache-Speichers.

Im folgenden wird ein Ausführungsbeispiel der Erfindung an- hand der Zeichnungen näher erläutert. Dabei zeigt Figur 1 ein Blockschaltbild des gesamten Ausführungsbei- spiels, Figur 2 ein Detailschaltbild des Speicherfeldes von Figur 1, Figur 3 eine Darstellung zur Erläuterung des Bildablagefor- mats im externen Bildspeicher, Figur 4 eine Darstellung zur Erläuterung der Funktion der Zu- ordnungseinheit von Figur 1, Figur 5 eine Darstellung zur Erläuterung der Pipelineverar- beitung der Cache-Zugriffe, Figur 6 eine Darstellung zur Erläuterung der Datenkonflikter- kennungseinheit und Figur 7 ein Schaltbild einer vorteilhaften Datenerkennungs- einheit.

Durch die spezielle Ausgestaltung des Speicherfeldes und der Zuordnungseinheit können aus dem Speicherfeld pro Takt z. B. mehrere Pixel gleichzeitig ausgelesen und in einem Prozessor- feld parallel verarbeitet werden. Das Format der ausgelesenen Bildfenster kann dabei-von----Takt zu Takt wechseln und z. B.

Bildbereiche aus zwei Zeilensegmenten mit 8 Pixeln bis zu Bildbereichen aus zwei Spaltenelementen mit 8 Pixeln aufwei- sen. Es sind also keine Puffer zur Aufnahme einer oder mehre- rer ganzer Bildzeilen erforderlich. Durch eine Schreibwarte- schlange, eine Lesewarteschlange und eine Datenkonflikterken- nungseinheit werden Datenkonflikte beim Lesen und Beschreiben des Speicherfeldes verhindert. Die zeitintensiven Nachla- deoperationen beeinträchtigen hier nicht den Datendurchsatz, da durch die Pipelineverarbeitung der Zugriffsanforderungen

zwar die Latenzzeit für die einzelnen Zugriffe nicht vermin- dert wird, jedoch der Durchsatz bei genügender Lokalität der Daten, das heißt hier z. B. einer der oben genannten Bild- breiche, nur wenige Zugriffe pro Bildbereich erfordert und so der Datentransferdurchsatz zum externen Speicher reduziert wird.

In Figur 1 ist ein Cache-Speicher zwischen einem externen Speicher XMEM und einer Verarbeitungseinheit P vereinfacht dargestellt, wobei die Verarbeitungseinheit in der Regel aus einem Prozessorfeld besteht. Der Cache-Speicher weist im we- sentlichen ein Speicherfeld CMEM sowie eine Cache-Steuerung auf, die aus einem Anforderungssignal REQ Schreibsteuersigna- le WC und Lesesteuersignale RC für das Speicherfeld CMEM und in entsprechender Weise auch für den externen Speicher und die Verarbeitungseinheit P bildet, wobei Eingangsdaten DI aus dem externen Speicher XMEM in das Speicherfeld eingelesen werden und Ausgangsdaten DO aus dem Speicherfeld in die Ver- arbeitungseinheit eingelesen werden. Die Cache-Steuerung weist im wesentlichen eine Zuordnungseinheit (Mapper) MAP, eine Schreibwarteschlange WQ, eine Lesewarteschlange RQ, eine Datenkonflikterkennungseinheit (hazard detection unit) HDET, eine Schreibsteuerung WCTRL und eine Lesesteuerung RCTRL auf.

Die Zuordnungseinheit MAP bildet Bereiche innerhalb eines zweidimensionalen Datenfeldes, z. B. eines Bildes, mit Hilfe von Beschreibungsdatensätzen SectionEntry auf Datenblöcke des Cache-Speichers flexibel ab und erzeugt so aus dem Anforde- rungssignal REQ Schreibkommandos W, die der Schreibwarte- schlange WQ zugeführt werden, und Lesekommandos R, die der Lesewarteschlange RQ zugeführt werden. Am Ausgang der Schreibwarteschlange WQ stehen verzögerte Schreibkommandos W an, die sowohl der Schreibsteuerung WCTRL als auch der Daten- konflikterkennungseinheit HDET zugeführt werden. Die Daten- konflikterkennungseinheit HDET bildet dabei in Abhängigkeit der verzögerten Schreibkommandos W und in Abhängigkeit von Adressen HS aller noch zu lesenden Cache-Speicherzellen, die vor einem Cache-Miss, also einer Leseanfrage deren zugehörige

Daten noch nicht bereits Speicherfeld CMEM geladen sind, an- gefordert wurden, ein Konfliktmeldesignal H, das die Schreibsteuerung WCTRL im Konfliktfall an der Abgabe von Schreibsteuersignalen WC hindert. Datenkonflikterkennungsein- heit HDET verhindert, daß Schreibanforderungen gestartet wer- den, bevor alle Treffer, also die Anfragen deren zugehörige Daten im Speicher CMEM bereits geladen sind, in der Lesewar- teschlage RQ verarbeitet sind. Die Lesesteuerung RCTRL erhält ein Synchronisiersignal SYNC von der Schreibsteuerung WCTRL und von der Lesewarteschlange RQ verzögerte Schreibkommandos R2 und bildet am Ausgang das Lesesignal RC. Das Synchroni- siersignal SYNC sorgt dafur, daß zu einer Anfrage ein zugehö- riges Lesesteuersignal RC erst dann erzeugt wird, wenn die benötigten Daten bereits vom externen Speicher XMEM in den Cache-Speicher CMEM übertragen wurden.

In Figur 2 ist beispielhaft ein Speicherfeld CMEM mit den zu- gehörigen Datenpfaden dargestellt. Das Speicherfeld CMEM ent- hält Speicherzellen Z mit jeweils 8 Bits, die zwei getrennte Leseports RD1 und RD2 zum Auslesen und einen Schreibport WR zum Beschreiben der Zelle Z aufweisen. Ein Leseport versorgt vertikale Leseleitungen VL und der andere Leseport horizonta- le Leseleitungen HL bzw. HL'. Die vertikalen Leseleitungen sind über einen Kreuzschienenverteiler (Crossbar-Switch) den Ausgängen für die Ausgangsdaten DO frei zuordenbar. Das Spei- cherfeld ist in zwei getrennte Blöcke BO und Bl aufgeteilt, wobei die horizontalen Leseleitungen HL im Block BO von den horizontalen Leseleitungen--HL'im Block B1 getrennt sind. In jedem Block sind diagonal verteilte Schalter zwischen den vertikalen Leseleitungen VL und den horizontalen Leseleitun- gen HL bzw. HL'derart vorgesehen, daß die horizontalen Lese- leitungen über die vertikalen Leseleitungen mit dem Kreuz- schienenverteiler verbindbar sind, der über eine Vielzahl von Schaltern S verfügt. Dies ermöglicht hier das parallele Aus- lesen von mehreren Pixeln einer Bildzeile oder einer Zweizei- lenmatrix über die vertikalen Leseleitungen aber auch das

Auslesen von Spaltensegmenten oder Matrizen mit zwei Spalten über die horizontalen und vertikalen Leseleitungen.

Durch Figur 3 wird deutlich, wie beispielsweise ein Bild im externen Speicher XMEM abgelegt ist. Die ersten 32 Byte der ersten Zeile eines Bildes liegen z. B. im ersten Datenwort das durch eine Bildbasisadresse adressiert wird. Ein Daten- wort, das durch die nächsthöhere Adresse bestimmt wird, er- hält die in der Bildzeile rechts anschließenden 32 Byte usw.

Am Zeilenende wird an den Anfang der nächsten Zeile gesprun- gen. Wenn die Zeilenlänge ungleich einem Vielfachen von 32 Bytes ist, wird die Zeile mit unbenutzten Bytes bis zu einem Vielfachen von 32 Bytes aufgefüllt, so daß jede Bildzeile im externen Speicher an einer 32-Byte-Wortgrenze beginnt. Damit wird das Bild in vertikale Streifen von 32 Byte Breite unter- teilt. Figur 3 zeigt einige mögliche Verarbeitungsoperanden PO1... P03, wobei der Verarbeitungsoperand PO1 vollständig in einem Speicherwort, der Verarbeitungsoperand P02 auf zwei Speicherwörter verteilt oder aber bei spaltenförmiger Anord- nung der Verarbeitungsoperator P03 in mehreren Speicherworten enthalten ist. Das oben erwähnte Speicherfeld mit zwei ge- trennten Blöcken BO und Bl ist gerade für den Verarbeitungs- operanden P02 von besonderem Vorteil. Für den Verarbeitungs- operanden P03 wäre ohne den Cache-Speicher die Anzahl der Zu- griffe gleich der Anzahl der benötigten Pixel, wobei die Speicher-Busbreite nur minimal genutzt würde.

Die Anforderung REQ enthält eine Position, zum Beispiel die x, y-Koordinaten, ein Format, zum Beispiel Zeile, Spalte oder Matrix, und eine Bildnummer eines angeforderten Bildbereichs.

Die Zuordnungseinheit MAP (Mapper) überprüft, ob alle ange- forderten Pixel schon im Cache-Speicherfeld gespeichert sind und berechnet die physikalischen Adressen für den externen Speicher XMEM und das Cache-Speicherfeld CMEM. Die Zuordnung von Bildzeilen und Cache-Zeilen erfolgt hier beispielsweise einfach-assoziativ bzw. direct-mapped, das heißt, daß die

niederwertigsten Bit der Bildzeilennummer mit der Adresse der zugehörigen Cache-Zeile identisch sind.

Die in Figur 4 beispielhaft angegebene Zuordnungseinheit MAP weist voneinander getrennte Datenbereiche, sogenannte Be- reichseinträge (section entries) auf, die über einen Be- schreibungsteil SD (section description) verfügen, der die Merkmale des Bildes enthält und über die Anforderung REQ in- itialisierbar ist. Darüber hinaus enthält ein jeweiliger Be- reichseintrag zwei Blockeinträge BEO und BEl für zwei Cache- Speicherblöcke CS1 und CS2 im Cache-Speicherfeld CMEM. Ein solcher Blockeintrag enthält eine Startspalte mBC und eine Startreihe mBR eines Bildfensters W1 im Gesamtbild IM, eine Startreihe CBR im Cache-Block und die Anzahl CR der Zeilen des jeweiligen Cache-Bereiches sowie eine Merkzelle RF (resi- dent flag) die angibt, ob der Cache-Block überhaupt gültige Zeilen enthält. Damit mehrere Prozessoren der Verarbeitungs- einheit P gleichzeitig den Cache-Speicher benutzen können, werden gegebenenfalls mehrere solche Bereichseinträge vorge- sehen. Hiermit ist es möglich, mehrere Bildobjekte gleichzei- tig im Cache-Speicher zu verwalten.

Wenn externe Speicherbausteine verwendet werden, die sich nur mit Zwei-Wort-Bursts effizient auslesen lassen oder bei An- wendungen, bei denen eine große Fensterweite nützlich ist, können in einem Cache-Block auch mehrere Cache-Blockbereiche mehreren Bildstreifen zugeordnet werden, wobei beispielsweise alle ungeradzahligen Bildstreifen einem Cache-Blockbereich CS1 und alle geradzahligen Bildstreifen einem Cache- Blockbereich CS2 zugeordnet werden.

Für den Fall, daß ein angeforderter und gespeicherter Bereich keinen Überlapp aufweist, wird ein Schreibkommando für den kompletten angeforderten Bereich in die Schreibwarteschlange WQ und ein Lesekommando in die Lesewarteschlange RQ überge- ben. Daten die zuvor im betroffenen Cache-Block gespeichert waren, werden für die nachfolgenden Anforderungen ungültig.

In der Zuordnungseinheit wird hierbei kein Wartezustand (wait state) erzeugt.

Falls zwischen dem angeforderten und gespeicherten Bereich ein Überlapp besteht, werden ein oder zwei Schreibkommandos mit dem noch nicht gespeicherten Bildbereich in die Schreib- warteschlange WQ und ein Lesekommando in die Lesewarteschlan- ge RQ übergeben. Soweit beim Nachladen keine bisher gültigen Zeilen überschrieben werden, bleiben die im betroffen Cache- Block enthaltenen Daten gültig und werden für die Anforderung benutzt. Zwei Schreibkommandos sind notwendig, wenn von dem angeforderten Bildbereich oben und unten Bildzeilen fehlen.

In diesem Fall generiert die Zuordnungseinheit einen Wartezu- stand, sonst nicht.

Für den letzten Fall, daß der angeforderte Bereich komplett im gespeicherten Bereich enthalten ist, ist kein Schreibkom- mando notwendig. Das Lesekommando wird in die Lesewarte- schlange RQ übergeben. Die Daten im betroffenen Cache-Block bleiben gültig und werden benutzt.

Ein Schreibkommando startet, nachdem es die Schreibwarte- schlange WQ durchlaufen hat, das Nachladen eines Bildberei- ches aus dem externen Speicher in das Cache-Speicherfeld CMEM. Der mit einem Kommando angeforderte Bildbereich umfaßt einen Ausschnitt mit einer oder zweier Bildspalten und einer oder mehreren Zeilen.

Ein Lesekommando bewirkt, nachdem benötigte Daten in den Cache nachgeladen wurden und eine Freigabe von der nachge- schalteten Verarbeitungseinheit P erfolgt ist, die Ausgabe der angeforderten Daten DO im passenden Format.

Eine Schwierigkeit ergibt sich beim Nachladen des Cache- Speichers durch ein Pipelining bzw. durch die Warteschlangen WQ und RQ. Nach Abarbeitung von mehreren Zugriffen ergibt sich zwangsläufig, daß alle Cache-Einträge mit Daten be-

schrieben wurden und für neue Zugriffe alte Daten überschrie- ben werden müssen. Hierbei ist sicherzustellen, daß keine Da- ten überschrieben werden, die benötigt werden, um noch in der Pipeline befindliche Aktionen zu bedienen. In Figur 5 wird verdeutlicht, daß dies ohne eine geeignete Steuerung zu einem Datenverlust führen könnte. Wird beispielsweise die Anforde- rung 3 von der Cache-Steuerung als Treffer (Hit) erkannt und in eine Warteschlange eingegliedert, da die benötigten Daten im Cache-Eintrag N vorhanden sind. Der nächste Zugriff 4 er- fordert ein Nachladen von Daten, die-beispielsweise bedingt durch die Leseadresse-ungünstigerweise die Daten in Eintrag N überschreiben. Da nach Anforderung des Zugriffs 4 das Lade- port frei wäre, könnte gleich mit dem Nachladen 4'begonnen werden. Die Daten im Eintrag N werden jedoch noch gebraucht, um Zugriff 3 zu bedienen. Das Nachladen für Zugriff 4 muß auf einen späteren Zeitpunkt 4''verschoben werden, da die Kom- mandos 0... 3 vorher noch aus der Warteschlange ausgelesen werden müssen. Nach der Latenzzeit der Warteschlange kann auch zum Zeitpunkt 4'''das Kommando 4 aus der Warteschlange ausgelesen werden.

In Figur 6 ist zur Erläuterung der Wirkungsweise der Daten- konflikterkennungseinheit HDET ein Blockschaltbild mit der Zuordnungseinheit MAP, der Schreibwarteschlange WQ, der Lese- warteschlange RQ mit einem ersten Teil RQ1 und einem zweiten Teil RQ2, der Schreibsteuerung WC und der Lesesteuerung RC dargestellt. Die Zuordnungseinheit MAP bestimmt die Schreib- und Leseaktionen, die auf. Anforderung REQ folgen müssen. Das Nachladen aus den externen Speicher XMEM in das Speicherfeld CMEM dauert viel länger als die Ausgabe, da für das Speichern mehrere langsame Speichertakte und für die Verarbeitung nur ein schneller Verarbeitungstakt nötig ist und außerdem sich das Nachladen aus dem externen Speicher mit einer großen La- tenzzeit von beispielsweise 10 Speichertakten behaftet. Da viele Leseanforderungen ohne Nachladen auskommen sollen, ist es vorteilhaft, mehrere Anforderungen in einer Pipeline zu verarbeiten. Die Zuordnungeinheit MAP gibt Schreibkommandos W

und Lesekommandos R gleichzeitig aus, wenn zu einer Anforde- rung REQ ein Nachladen notwendig ist. Bevor also das Lesekom- mando R, für welches Daten nachzuladen sind, zu einem Ausga- bezyklus verarbeitet wird, muß es solange verzögert werden, bis die Daten im Cache-Speicherfeld CMEM verfügbar sind. Da die Ausgabe vorteilhafterweise in der gleichen Reihenfolge erfolgen sollten wie sie angefordert werden, müssen sie eine Lesewarteschlange RQ (Queue) durchlaufen.

Auch die Schreibkommandos W sind vorteilhafterweise in der Schreibwarteschlange WQ zwischengespeichert, wenn schon eine Nachladeoperation bearbeitet, da sonst zwei aufeinanderfol- gende Anforderungen, die ein Nachladen erfordern, die Pipe- line unweigerlich zum Stillstand bringen würden. Bereits ei- nige Speicherplätze in der Schreibwarteschlange ermöglichen eine wesentlich bessere Auslastung der Nachladebandbreite.

Wie in Figur 5 dargestellt können beim Nachladen von Daten in das Cache-Speicherfeld CMEM Datenkonflikte (Hazards) auftre- ten. Diese treten dann auf, wenn eine Nachladeoperation ge- startet werden soll, die gültige Daten im Cache-Speicherfeld überschreiben würde, die noch für zuvor in der Zuordnungsein- heit bereits erzeugte aber noch nicht ausgegebene Lesekomman- dos gebraucht werden. Die Lesekommandos sind zu diesem Zeit- punkt in der ersten Lesewartenschlange RQ gespeichert. Um so einen Datenkonflikt zu erkennen, ist nur der Inhalt des er- sten Teils RQ1 der Lesewarteschlange RQ bei einer Nachla- deoperation abzusuchen-. Am---Kopf K der Schreibwarteschlange WQ steht ein Nachladekommando, welches ein Datum in die Cache- Adresse A übertragen soll. Die Zelle 11 des erten Teils RQ1 der Lesewarteschlange RQ enthält hier beispielsweise das hierzu korrespondierende Lesekommando, das heißt die beiden Einträge stammen aus der gleichen Anforderung und wurden gleichzeitig von der Zuordnungseinheit MAP in die Schreibwar- teschlange WQ und in den ersten Teil RQ1 der Lesewarteschlan- ge eingetragen. Folglich enthält die Zelle 11 der Lesewarte- schlange ein Kommando, das aus der Cache-Adresse A liest. Die

Zelle 5 des zweiten Teils RQ2 der Lesewarteschlange enthält ebenfalls einen Lesezugriff auf Adresse A und steht im Kon- flikt mit der anstehenden Nachladeoperation, weil die zugehö- rige Anforderung vor der Anforderung die das Kommando in der Zelle 11 initiierte, angelegt wurde und somit ein älteres Da- tum in der Cache-Adresse A erwartet. Um ein fehlerhaftes Ver- halten zu vermeiden muß also der zweite Teil RQ2 der Lesewar- teschlange RQ bis zur Zelle 5 abgearbeitet werden, ehe die Nachladeoperation gestartet werden darf. Lesekommandos auf Plätzen mit Nummern größer oder gleich 11, die aus Cache- Adresse A lesen werden, dürfen bei der Suche nicht berück- sichtigt werden, da diese Operationen schon das nachzuladende Datum erwarten. Für die Suchfunktion die das vorzeitige Nach- laden verhindert, muß somit die Lesewarteschlange RQ in zwei Teile RQ1 und RQ2 gespalten werden. Die Zuordnungseinheit übergibt die Kommandos zunächst in den ersten Teil RQ1 den sie durchlaufen, bis die korrespondierenden Schreibkommandos als Auftrag in die Schreibsteuerung WCTRL übergeben werden.

Bei Start der Nachladeoperation werden die Lesekommandos an den zweiten Teil RQ2 der Lesewarteschlange übertragen. Die Konfliktsuche beschränkt sich auf den zweiten Teil RQ2 der Lesewarteschlange.

Zu beachten ist, daß dann, wenn eine Nachladeoperation ge- startet wird und das korrespondierende Lesekommando zum zwei- ten Teil RQ2 überwechselt, die nächste Nachladeoperation erst gestartet werden kann, wenn das hierzu korrespondierende Le- sekommando am Kopf KRQ1 des-ersten Teils RQ1 der Lesewarte- schlange steht, weil alle vorhergehenden Kommandos, die nicht mit einer Nachladeoperation verbunden sind, für die Kon- fliktsuche in dem zweiten Teil RQ2 der Lesewarteschlange ste- hen müssen. Im Fall von Figur 6 bedeutet das, daß nach dem Start der Nachladeoperation für Zelle 11, die Konfliktsuche bezüglich des Nachladens für Zelle 16 frühestens ausgeführt werden darf, wenn alle Lesekommandos der Nummern 15 und klei- ner sich im zweiten Teil RQ2 befinden. Dies kann dann einige zusätzliche Wartezyklen und damit einen Performance-verlust

bedeuten, wenn das Nachladen für Kommando 11 sehr schnell fertig ist und die Lesesteuerung RCTRL für ein Kommando in Zelle 16 bereits bereit wäre, während sich im ersten Teil der Lesewarteschlange noch Kommandos mit Zellennummern kleiner oder gleich 15 befinden. Dies passiert zum Beispiel dann, wenn die beiden Teile RQ1 und RQ2 in zwei getrennten Spei- chern realisiert werden und nur ein Kommando pro Takt von dem ersten Teil zum zweiten Teil wechseln kann.

Dieser Nachteil kann beispielsweise dadurch umgangen werden, daß beide Teile RQ1 und RQ2 sich in einem Speicher befinden und das Weiterrücken der Kommando innerhalb der Wartenschlan- ge RQ1 anstatt durch Datentransport durch Inkrementieren von Schreib-und Lese-Pointern erfolgt. Hiermit kann der logische Übergang eines ganzen Satzes von Kommandos in einem Takt er- folgen. Bei dieser Realisierungsart ist es vorteilhaft, neben einem Anfangszeiger (Headpointer) und einem Endezeiger (Tail- pointer) auch einen Mittenzeiger vorzusehen, der die Trennung zwischen dem ersten Teil RQ1 und dem zweiten Teil RQ2 mar- kiert.

Für jedes Laden einer Cache-Zeile ist zu prufen, ob in diesem Warteschlangenbereich ein Kommando vorhanden ist, das aus der gleichen Zeile liest. Diese Überprüfung kann besonders ein- fach mit einer in Figur 7 gezeigten Anordnung realisiert wer- den. RQ1 und RQ2 werden hierbei durch ein Speicherfeld HMEM implementiert, dessen Spaltenzahl der Anzahl der Einträge von RQ1 und RQ2 und dessen Zeilenzahl der Anzahl der Cachezeilen entspricht. Beim Eintragen eines Lesekommandos in RQ1 wird ein Datenwort in die durch den Schreibzeiger bestimmten Spal- te geschrieben. Jedes Bit dieses Wortes spiegelt den Lesesta- tus der korrespondierenden Cachezeile wieder, wobei hier z.

B. eine 1 Lesen und eine 0 nicht Lesen bedeuten. Da durch ein Kommando mehrere Cachezeilen gelesen werden können, können mehrere Bits einer Spalte hierbei gesetzt werden. Somit re- präsentiert eine Zeile des Speicherfeldes HMEM den Status ei-

ner Cachezeile für die komplette Lesewarteschlange RQ1 und RQ2.

Bevor eine Cachezeile überschrieben wird, wird eine Zeile aus dem Speicherfeld HMEM ausgelesen. Jedes ausgelesene Bit wird jeweils mit einem Auswahl-Bit aus einem Auswahlsignal RQ2SEL in einem jeweiligen UND-Gatter A1... An verknüpft und über ein ODER-Gatter OR zu dem Konflikt-Signal H zusammengefaßt.

Die Auswahlbits markieren durch 1-Pegel an den passenden Po- sitionen die Spalten, welche zu dem Lesewarteschlangenbereich RQ2 gehören.

Die Schreibsteuerung WCTRL setzt die Schreibkommandos WC in passende Ansteuerzyklen für das Cache-Speicherfeld und den externen Speicher um. Das Schreibkommando WC kann das Nachla- den von mehreren Cache-Zeilen bewirken. Das Nachladen jeder Cache-Zeile erfordert eine enge Zusammenarbeit mit der Daten- konflikterkennungseinheit HDET. Das Umsetzen eines Kommandos dauert in der Regel mehrere Taktzyklen.

Die Lesesteuerung RCTRL setzt die Lesekommandos aus der Lese- warteschlange RQ in Steuersignale für das Cache-Speicherfeld um. Der Durchsatz hierbei beträgt in der Regel ein Kommando und eine Ausgabe pro Takt. Wenn ein Lesebefehl mit einer Nachladeoperation verbunden ist, werden gegebenenfalls Warte- zyklen eingeführt, bis die Nachladeoperation vollzogen ist.

Da mit jeder Ausgabe mehrere Pixel ausgelesen werden, gibt es eine Vielzahl von Formaten für die die Darstellung der Pixel am Cache-Ausgang DO. Außer der Aktivierung der passenden Cache-Zeilen hat also die Lesesteuerung die Aufgabe, die pas- senden Schaltpunkte S des Kreuzschienenverteilers anzusteu- ern.