DE10219621A1

DE10219621A1 - Schnelle Prioritätsbestimmungsschaltung mit rotierender Priorität

Info

Publication number: DE10219621A1
Application number: DE10219621A
Authority: DE
Inventors: Duane A Wiens; Robert F Krick
Original assignee: Hewlett Packard Co
Current assignee: Hewlett Packard Development Co LP
Priority date: 2001-05-10
Filing date: 2002-05-02
Publication date: 2002-11-21
Also published as: US6915396B2; US20020188821A1

Abstract

Die Erfindung beschreibt ein System für und ein Verfahren zum Erzeugen und Verwenden von Abhängigkeiten, um die Reihenfolge des Bedienens von Transaktionsanforderungen in einer Mehrfachschlangenumgebung zu bestimmen. Wenn mehr als eine ausstehende Transaktion denselben Speicherplatz betrifft, werden Abhängigkeiten eingerichtet, um die korrekte Sequenzierung der konkurrierenden Transaktionen sicherzustellen. Bei einem bevorzugten Ausführungsbeispiel ist die Abhängigkeit konfiguriert, um sicherzustellen, daß, während jede Anforderung eingebracht wird, weitere ausstehende Anfoderungen überprüft werden, um zu bestimmen, ob auf denselben Speicherplatz zugegriffen wird. Wenn der gleiche Speicherplatz betroffen ist, wird eine Abhängigkeit erzeugt, die sicherstellt, daß der jüngste Warteschlangeneintrag, der zum Zeitpunkt der Durchführung der Prüfung vorliegt, vor der vorliegenden, ausstehenden Anforderung geschieht.

Description

Der Gegenstand der vorliegenden Anmeldung ist verwandt zu dem in der eingereichten Anmeldung mit dem Titel SYSTEM UND VERFAHREN ZUR SPEICHERENTSCHEIDUNG UNTER VERWENDUNG VON MEHREREN WARTESCHLANGEN, deren Offenbarung hiermit durch Bezugnahme aufgenommen worden ist.

Die Erfindung bezieht sich im allgemeinen auf Computerspei chersysteme und spezieller auf eine Speichersteuerung in einem System, um eine Zugriffszeit auf Daten unter Verwen dung eines Speichers zu verbessern.

Der Wunsch nach einer Erhöhung der Geschwindigkeit, mit der der Computer Informationen verarbeitet, ist immer stärker geworden. Ein Schema zum Erhöhen der Verarbeitungsgeschwin digkeit umfaßt die Verbesserung einer Speicherzugriffszeit.

Eine übliche Art und Weise, mit der die Speicherzugriffs zeit verbessert werden soll, ist, einen Cache-Speichers zu sammen mit einem Hauptspeicher bereitzustellen. Ein Cache- Speicher ist typischerweise einem Prozessor zugeordnet und erfordert weniger Zugriffszeit als der Hauptspeicher. Kopi en von Daten aus Lese- und Schreibeaktionen aus dem Prozes sor werden im Cache zurückgehalten. Manche Cache-Systeme behalten vor kurzem vorgenommene Lese- und Schreibeaktionen ein, während andere komplexere Algorithmus aufweisen kön nen, um zu bestimmen, welche Daten im Cache-Speicher zu rückgehalten werden. Wenn ein Prozessor Daten anfordert, die derzeit im Cache resident sind, wird nur auf den Cache- Speicher zugegriffen. Da der Cache-Speicher eine geringere Zugriffszeit erfordert als der Hauptspeicher, wird die Ver arbeitungsgeschwindigkeit verbessert. Heutzutage können Speicherzugriffe vom Hauptspeicher sogar 250 Nanosekunden dauern, während ein Cache-Zugriff zwei oder drei Nanosekun den dauern kann.

Zusätzlich kann ein Cache-System verwendet werden, um die effektive Geschwindigkeit einer Datenschreibe-Aktion zu er höhen. Wenn ein Prozessor z. B. eine Speicherstelle schrei ben soll, kann der Prozessor eine Datenschreibe-Aktion aus schließlich an den Cache-Speicher ausführen. Der Cache- Speicher und eine zugeordnete Steuerlogik können dann die Daten an den Hauptspeicher schreiben, während der Prozessor mit anderen Aufgaben fortfährt.

Computersysteme können auch die Verwendung des Caches er weitern und eine Multiebenen-Hierarchie des Cache-Speichers verwenden, wobei sich ein relativ schneller, kostspieliger Speicher mit eingeschränkter Kapazität auf der höchsten Ebene der Hierarchie befindet und zu einem relativ langsa meren, kostengünstigeren Speicher mit einer höheren Kapazi tät auf der niedrigsten Ebene der Hierarchie übergegangen wird. Typischerweise umfaßt die Hierarchie einen kleinen, schnellen Speicher, der als Primär-Cache bezeichnet wird, der entweder physisch in eine prozessorintegrierte Schal tung integriert ist oder sich physisch nahe am Prozessor angebracht ist. Der Primär-Cache, der auf dem gleichen Chip wie die zentrale Verarbeitungseinheit (CPU) eingebaut ist, kann eine Frequenz (d. h. Zugriffszeit) gleich der Frequenz der CPU aufweisen. Es kann ein separater Anweisungs-Primär- Cache und ein Daten-Primär-Cache vorhanden sein. Primär- Caches maximieren typischerweise das Verhalten, während da bei Kapazität geopfert wird, um eine Datenlatenz zu mini mieren. Zusätzlich stellt der Primär-Cache typischerweise eine hohe Bandbreite bereit. Ein Sekundär-Cache oder ein Tertiär-Cache können ebenfalls verwendet werden und sind typischerweise weiter vom Prozessor entfernt. Diese Sekun där- und Tertiär-Caches liefern einen "Rückanschlag" (Back stop) für den Primär-Cache und weisen im allgemeinen eine größere Kapazität, eine höhere Latenz und eine geringere Bandbreite als der Primär-Cache auf. Wenn ein Prozessor ein Teil von einem Primär-Cache anfordert und das Teil im Pri mär-Cache vorhanden ist, resultiert daraus ein Cache- "Treffer". Während es, wenn ein Teil nicht vorhanden ist, einen Primär-Cache-"Fehlschlag" gibt. Im Falle eines Pri mär-Cache-Fehlschlags wird das angeforderte Teil von der nächsten Ebene des Cache-Speichers oder, wenn das angefor derte Teil nicht im Cache-Speicher enthalten ist, vom Hauptspeicher abgerufen.

Typischerweise sind alle Speicher in Worten organisiert (z. B. 32 Bits oder 64 Bits pro Wort). Der Mindestspeicher betrag, der zwischen einem Cache und einer nächstniedrigen Ebene der Speicherhierarchie übertragen werden kann, wird als eine Cache-Zeile oder manchmal als ein Block bezeich net. Eine Cache-Zeile umfaßt typischerweise mehrere Worte (z. B. 16 Worte pro Zeile). Ein Speicher kann auch in Sei ten (auch als Segmente bezeichnet), mit vielen Zeilen pro Seite aufgeteilt sein. Bei manchen Systemen kann die Sei tengröße variabel sein.

Caches sind unter Verwendung von drei Hauptarchitekturen konstruiert worden: direkt abgebildete, satzassoziative (satzadressierte) und vollassoziative (voll inhaltsadres sierte). Einzelheiten über die drei Cache-Typen sind in den nachstehenden Druckschriften des Stands der Technik be schrieben, deren Offenbarung hiermit durch Bezugnahme auf genommen worden ist: De Blasi, "Computer Architecture", ISBN 0-201-41603-4 (Addison-Wesley, 1990), S. 273-291; Sto ne, "High Performance Computer Architecture", ISBN 0-201- 51377-3 (Addison-Wesley, 2. Ausgabe 1990), S. 29-39; Tabak, "Advanced Microprocessors", ISBN 0-07-062807-6 (McGraw-Hill 1991), S. 244-248).

Beim direkten Abbilden, wenn eine Zeile angefordert wird, weist nur eine Zeile im Cache übereinstimmende Indexbits auf. Daher können die Daten unmittelbar abgerufen und auf einen Datenbus getrieben werden, bevor das System bestimmt, ob der Rest der Adresse übereinstimmt. Die Daten können oder können nicht gültig sein, jedoch im Normalfall, wo sie gültig sind, sind die Datenbits auf einem Bus verfügbar, bevor das System die Gültigkeit der Daten bestätigt.

Bei satzassoziativen Caches ist nicht bekannt, welche Zeile einer Adresse entspricht, bis die Indexadresse berechnet und die Etikettadresse gelesen und verglichen worden ist. Das heißt, bei satzassoziativen Caches wird das Ergebnis eines Etikettenvergleichs verwendet, um auszuwählen, welche Zeile von Datenbits in einem Satz von Zeilen dem Prozessor präsentiert wird.

Ein Cache soll angeblich vollassoziativ sein, wenn ein Ca che eine ganze Zeilenadresse zusammen mit den Daten spei chert und eine beliebige Zeile an einer beliebigen Stelle im Cache plaziert werden kann. Für einen großen Cache, bei dem eine beliebige Zeile an einer beliebigen Stelle pla ziert werden kann, ist jedoch eine umfangreiche Hardware erforderlich, um schnell zu bestimmen, ob und wo sich ein Eintrag im Cache befindet. Für große Caches umfaßt eine schnellere, platzsparende Alternative die Verwendung eines Teilsatzes einer Adresse (die als Index bezeichnet wird), um eine Zeilenposition im Cache zu benennen und anschlie ßend den verbleibenden Satz von höherwertigen Bits von je der physischen Adresse (die als Etikett bezeichnet wird) zusammen mit den Daten zu speichern. Bei einem Cache mit Indexierung kann ein Teil mit einer speziellen Adresse nur innerhalb eines Satzes von Cache-Zeilen, die durch den In dex bezeichnet sind, plaziert werden. Wenn der Cache so an geordnet ist, daß der Index für eine gegebene Adresse genau auf eine Zeile im Teilsatz abgebildet wird, gilt der Cache als direkt abgebildet. Wenn der Index auf mehr als eine Zeile im Teilsatz abgebildet wird, gilt der Cache als satz assoziativ. Die gesamte oder ein Teil einer Adresse werden einer Hash-Aktion unterzogen, um einen Satzindex zu lie fern, der den Adressenraum in Sätze partitioniert.

Bei allen drei Typen von Caches wird eine Eingangsadresse an eine Vergleichslogik angelegt. Typischerweise wird ein Teilsatz der Adresse, der als Etikettenbits bezeichnet wird, aus der Eingangsadresse extrahiert und mit den Eti kettenbits von jedem Cache-Eintrag verglichen. Wenn die Etikettenbits übereinstimmen, werden die entsprechenden Da ten aus dem Cache extrahiert.

Im allgemeinen liefern direktabgebildete Caches einen schnelleren Zugriff, jedoch beanspruchen sie die meiste Zeit zum Vergleichen der Etikettenbits. Vollassoziative Ca ches weisen eine größere Zugriffszeit auf, konsumieren je doch mehr Leistung und erfordern einen komplexeren Schal tungsaufbau.

Wenn mehrere Prozessoren mit ihren eigenen Caches in einem System enthalten sind, werden Cache-Kohärenzprotokolle ver wendet, um die Kohärenz zwischen und unter den Caches bei zubehalten. Es gibt zwei Klassen von Cache- Kohärenzprotokollen:

1. Verzeichnisbasierte: Die Informationen über einen Block des physischen Speichers werden an einem einzi gen gemeinsamen Platz erhalten. Diese Informationen umfassen normalerweise, welche/r Cache/s eine Kopie des Blocks aufweist/en und ob diese Kopie ausschließ lich für eine zukünftige Modifizierung markiert ist. Bei einem Zugriff auf einen speziellen Block wird zu erst das Verzeichnis abgefragt, um zu sehen, ob die Speicherdaten verfallen sind und die echten Daten (wenn überhaupt) in irgendeinem anderen Cache residie ren. Ist dies der Fall, dann wird der Cache, der den modifizierten Block enthält, dazu gebracht, seine Da ten an den Speicher zurückzusenden. Dann leitet der Speicher die Daten an den neuen Anfordernden (Reque ster), wobei das Verzeichnis mit dem neuen Platz die ses Blocks aktualisiert wird. Dieses Protokoll mini miert eine Interbusmodul-(oder Intercache-)Störung, leidet jedoch typischerweise an einer hohen Latenz und ist aufgrund der erforderlichen großen Verzeichnisgrö ße teuer zu bauen.
2. Schnüffeln: Jeder Cache, der eine Kopie der Daten aus einem Block des physischen Speichers aufweist, weist auch eine Kopie der Informationen über den Datenblock auf. Jeder Cache befindet sich typischerweise auf ei nem gemeinsamen Speicherbus, und alle Cache-Controller überwachen oder schnüffeln an dem Bus, um zu bestim men, ob sie eine Kopie des gemeinsamen Blocks aufwei sen oder nicht.

Schnüffel-Protokolle sind für eine Multiprozessor- Systemarchitektur sehr gut geeignet, die Caches und einen gemeinsamen Speicher verwendet, weil sie im Kontext der be reits bestehenden, physischen Verbindung arbeiten, die nor malerweise zwischen dem Bus und dem Speicher vorgesehen ist. Das Schnüffeln wird gegenüber den Verzeichnisprotokol len häufig bevorzugt, weil sich der Betrag an Kohärenzin formationen proportional zur Anzahl von Blöcken in einem Cache und nicht zur Anzahl von Blöcken im Hauptspeicher verhält.

Das Kohärenzproblem entsteht in einer Multiprozessorarchi tektur, wenn ein Prozessor einen exklusiven Zugriff haben muß, um einen Block des Speichers oder Objekts zu schrei ben, und/oder die neueste Kopie haben muß, wenn ein Objekt gelesen wird. Ein Schnüffel-Protokoll muß alle Caches, die das Objekt, das geschrieben werden soll, teilen, lokalisie ren. Die Konsequenzen einer Schreibe-Aktion an gemeinsame Daten umfassen entweder ein Invalidieren aller anderen Ko pien der Daten oder ein Aussenden der Schreibe-Aktion an alle der gemeinsamen Kopien. Aufgrund der Verwendung der Zurückschreibe-Caches müssen die Kohärenzprotokolle eben falls Prüfungen an allen Caches während der Speicherleseak tionen bewirken, um zu bestimmen, welcher Prozessor die ak tuellste Kopie der Informationen aufweist.

Daten bezüglich der Informationen, die zwischen den Prozes soren geteilt werden, werden den Statusbits hinzugefügt, die in einem Cache-Block bereitgestellt sind, um die Schnüffel-Protokolle zu implementieren. Diese Informationen werden beim Überwachen von Busaktivitäten verwendet. Bei einem Leseaktions-Fehlschlag überprüfen alle Caches, ob sie eine Kopie des angeforderten Blocks von Informationen haben und ergreifen die entsprechende Maßnahme, wie z. B. Zufüh ren der Informationen zum Cache, bei dem sich der Fehl schlag ereignete. In ähnlicher Weise überprüfen alle Caches bei einer Schreibe-Aktion, ob sie eine Kopie der Daten be sitzen und handeln dann, indem sie beispielsweise ihre Ko pie der Daten invalidieren oder ihre Kopie der Daten verän dern, um den jüngsten Wert zu reflektieren.

Die Schnüffel-Protokolle umfassen zwei Typen:
Schreiben-Invalidieren: Der Schreibprozessor bewirkt, daß alle Kopien in anderen Caches invalidiert werden, bevor er seine lokale Kopie verändert. Dem Prozessor steht dann frei, die Daten zu aktualisieren, bis zu dem Zeitpunkt, wo ein weiterer Prozessor nach den Daten fragt. Der Schreib prozessor gibt ein Invalidierungssignal über den Bus aus, und alle Caches prüfen, ob sie eine Kopie der Daten besit zen. Ist dies der Fall, müssen sie den Block, der die Daten enthält, invalidieren. Dieses Schema erlaubt mehrere Leser, jedoch nur einen einzigen Schreiber.

Schreiben-Aussenden: Der Schreibprozessor sendet die neuen Daten über den Bus aus und invalidiert nicht jeden Block, der geteilt wird. Alle Kopien werden dann mit dem neuen Wert aktualisiert. Dieses Schema sendet kontinuierlich Schreibe-Aktionen an gemeinsame Daten aus, während das Schreiben-Invalidieren-Schema, das vorstehend erörtert wur de, alle anderen Kopien löscht, so daß es nur eine lokale Kopie für die anschließenden Schreibe-Aktionen gibt. Die Schreiben-Aussenden-Protokolle ermöglichen normalerweise, daß Daten als gemeinsam (ausgesendet) etikettiert werden, oder die Daten können als privat (lokal) etikettiert wer den. Für weitere Informationen über die Kohärenz siehe J. Hennessy, D. Patterson, Computer Architecture: A Quantita tive Approach, Morgan Kaufmann Publishers, Inc., (1990), deren Offenbarung hiermit durch Bezugnahme aufgenommen wor den ist.

Bei einer Schnüffel-Kohärenz-Multiprozessor-Systemarchi tektur wird jede kohärente Transaktion auf dem Systembus zu jedem Cache-Teilsystem des Prozessors weitergeleitet, um eine Kohärenzprüfung auszuführen. Diese Überprüfung stört normalerweise die Pipeline des Prozessors, weil auf den Ca che nicht durch den Prozessor zugegriffen werden kann, wäh rend die Kohärenzprüfung stattfindet.

Bei einem traditionellen Einzelport-Cache ohne doppelte Ca che-Etiketten wird die Prozessor-Pipeline bei Cache- Zugriffsanweisungen blockiert, wenn der Cache-Controller damit beschäftigt ist, Cache-Kohärenzprüfungen für andere Prozessoren zu verarbeiten. Für jede Schnüffel-Aktion muß der Cache-Controller zuerst die Cache-Etiketten für die Schnüffel-Adresse prüfen und dann den Cache-Zustand modifi zieren, wenn sich ein Treffer ereignet hat. Das Zuteilen der Cache-Bandbreite für eine atomische (untrennbare) Eti ketten-Lese- und Schreibe-Aktion (für eine mögliche Modifi zierung) verriegelt den Cache von dem Prozessor länger als notwendig, wenn die Schnüffel-Aktion keine Etiketten- Schreibe-Aktion erfordert. Zum Beispiel sind 80 bis 90% der Cache-Abfragen Fehlschläge, d. h. eine Etiketten- Schreibeaktion ist nicht erforderlich. Bei einer Mehrebe nen-Cache-Hierarchie können viele dieser Fehlschläge gefil tert werden, wenn eine Inklusionseigenschaft beachtet wird. Eine Inklusionseigenschaft ermöglicht, daß Informationen auf der höchsten Ebene des Caches bezüglich der Inhalte der unteren Cache-Ebenen gespeichert werden.

Die Geschwindigkeit, mit der Computer Informationen für viele Anwendungen verarbeiten, kann durch Erweitern der Größe der Caches, speziell des Primär-Caches, erhöht wer den. Während die Größe des Primär-Caches zunimmt, werden die Hauptspeicherzugriffe verringert und die Gesamtverar beitungsgeschwindigkeit nimmt zu. In ähnlicher Weise, da die Größe des Sekundär-Caches zunimmt, werden die Haupt speicherzugriffe verringert und die Gesamtverarbeitungsge schwindigkeit erhöht, obwohl dies nicht so wirksam ist wie das Erweitern der Größe des Primär-Caches.

Typischerweise werden bei Computersystemen Primär-Caches, Sekundär-Caches und Tertiär-Caches unter Verwendung eines statischen Direktzugriffsspeichers (SRAM; SRAM = Static Random Access Memory) implementiert. Die Verwendung des SRAM ermöglicht eine verringerte Zugriffszeit, was die Ge schwindigkeit erhöht, mit der die Informationen verarbeitet werden können. Ein dynamischer Direktzugriffsspeicher (DRAM; DRAM = Dynamic Random Access Memory) wird typischer weise für den Hauptspeicher verwendet, da er weniger kost spielig ist, weniger Leistung erfordert und größere Spei cherdichten liefert.

Typischerweise schränkten Computersysteme des Stands der Technik auch auf die Anzahl von ausstehenden Transaktionen an den Cache zu einem bestimmten Zeitpunkt ein. Wenn mehr als eine Transaktion durch einen Cache empfangen werden sollte, verarbeitete der Cache die Anforderungen seriell. Wenn z. B. zwei Transaktionen durch einen Cache empfangen werden sollten, wurde die erste Transaktionsanforderung zu erst verarbeitet, wobei die zweite Transaktion zurückgehal ten wurde, bis die erste Transaktion beendet war. Sobald die erste Transaktion vollendet war, verarbeitete der Cache die zweite Transaktionsanforderung.

Es existieren zahlreiche Protokolle, die die Cache-Kohärenz über mehrere Caches und den Hauptspeicher beibehalten. Ein solches Protokoll ist MESI ([Modified, Exclusive, Shared, Invalid] = Modifiziert, Exklusiv, Geteilt, Ungültig). Das MESI-Protokoll ist bei M. Papamarcos und J. Patel, "A Low Overhead Coherent Solution for Multiprocessors with Private Cache Memories", im Sitzungsprotokoll des 11. International Symposium on Computer Architecture, IEEE, New York (1984), S. 348-354, ausführlich beschrieben, und seine Offenbarung wird hiermit hierin durch Bezugnahme aufgenommen. Nach dem MESI-Protokoll wird eine Cache-Zeile gemäß ihrer Verwendung kategorisiert. Eine modifizierte Cache-Zeile zeigt an, daß die spezielle Zeile durch den Cache, der der momentane Be sitzer der Zeile ist, beschrieben worden ist. Eine exklusi ve Cache-Zeile zeigt an, daß ein Cache die exklusive Eigen tümerschaft der Cache-Zeile aufweist, was dem Cachecontrol ler ermöglicht, die Cache-Zeile zu modifizieren. Eine ge meinsame Cache-Zeile zeigt an, daß ein oder mehrere Caches die Eigentümerschaft der Zeile aufweisen. Eine gemeinsame Cache-Zeile gilt als Nur-Lese-Zeile, und jede Vorrichtung unter dem Cache kann die Zeile lesen, darf jedoch nicht an den Cache schreiben. Eine Cache-Zeile ohne Eigentümer iden tifiziert eine Cache-Zeile, deren Daten nicht gültig sein können, da der Cache die Cache-Zeile nicht mehr besitzt.

Es ist die Aufgabe der vorliegenden Erfindung, ein Verfah ren und eine Vorrichtung zum Bereitstellen eines geordneten Zugriffs auf einen Speicher zu schaffen.

Diese Aufgabe wird durch ein Verfahren gemäß Anspruch 1 und eine Vorrichtung gemäß Anspruch 10 gelöst.

Die Erfindung beschreibt ein System und ein Verfahren zum Erzeugen und Verwenden von Abhängigkeiten, um die Reihen folge des Bedienens von Transaktionsanforderungen in einer Mehrfach-Warteschlangenumgebung zu bestimmen. Wenn mehr als eine ausstehende Transaktion den gleichen Speicherplatz be trifft, werden die Abhängigkeiten festgelegt, um die kor rekte Sequenzierung der konkurrierenden Transaktionen si cherzustellen. Bei einem bevorzugten Ausführungsbeispiel ist die Abhängigkeit konfiguriert, um sicherzustellen, daß, während jede Anforderung verarbeitet wird, andere ausste hende Anforderungen überprüft werden, um zu bestimmen, ob derselbe Speicherplatz betroffen ist. Wenn derselbe Spei cherplatz betroffen ist, wird eine Abhängigkeit geschaffen, die sicherstellt, daß der jüngste Warteschlangeneintrag, der zu dem Zeitpunkt der Prüfung ansteht, vor der anstehen den ausstehenden Anforderung geschieht.

Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend Bezug nehmend auf die beiliegenden Zeichnungen näher erläutert. Es zeigen:

Fig. 1 eine Sekundär-Cachestruktur, die zwei Warte schlangen, eine Lesewarteschlange und eine Schreibwarteschlange umfaßt;

Fig. 2 ein zweidimensionales Array, das den satzassozia tiven Cache, der im DRAM enthalten ist, dar stellt;

Fig. 3 eine Sekundär-Cachestruktur, die eine Lesewarte schlange, eine Schreibwarteschlange, eine Kohä renzwarteschlange und eine Räumungswarteschlange umfaßt, die jeweils verwendet werden, um Cache- Zeilen aus dem DRAM zu lesen;

Fig. 4 die Struktur der Adressen für die verschiedenen Warteschlangen von Fig. 3;

Fig. 5 die Struktur der Adressen, wenn die Transaktionen in der Kohärenzwarteschlange und der Lesewarte schlange anstehen;

Fig. 6 die Struktur der Adressen, wenn die Transaktionen in der Lesewarteschlange, der Räumungswarte schlange und der Schreibwarteschlange anstehen;

Fig. 7A die Struktur der Adressen, wenn die Transaktionen in der Lesewarteschlange und der Schreibwarte schlange anstehen und derselbe Speicherabschnitt des DRAMs betroffen ist;

Fig. 7B ein Beispiel einer Abhängigkeitsauswahl, wenn mehrere Adreßabhängigkeiten existieren;

Fig. 7C ein Beispiel der Umbruchbeschaffenheit der Warte schlangen;

Fig. 8 eine Tabelle, die die Abhängigkeiten zwischen den verschiedenen Warteschlangen darstellt;

Fig. 9 ein Diagramm eines Verfahrens, um eine Abhängig keit zwischen einer Leseoperation und einer Schreiboperation konkret darzustellen;

Fig. 10 ein schematisches Diagramm eines logischen Schal tungsaufbaus, der die Löschmaske von Fig. 9 im plementiert;

Fig. 11 ein Diagramm eines Beispiels eines Ausführungs beispiels der vorliegenden Erfindung;

Fig. 12A und 12B schematische Diagramme von logischen Schaltungen, die die Zählermaske von Fig. 11 für Bit[0] bzw. Bit[4] implementieren;

Fig. 13 ein schematisches Diagramm einer logischen Schal tung, die zum Erzeugen der Zählermaske von Fig. 11 verwendet wird; und

Fig. 14 ein Flußdiagramm, das die Erzeugung einer Abhän gigkeit darstellt.

Im allgemeinen umfaßt eine Speicherhierarchie verschiedene Komponenten, die mit verschiedenen Geschwindigkeiten arbei ten. Diese Geschwindigkeiten können sich von der Geschwin digkeit der zentralen Verarbeitungseinheit (CPU) unter scheiden. Typischerweise nimmt die Geschwindigkeit der Kom ponente ab, während die Entfernung von der CPU zunimmt. Diese Geschwindigkeits-Versätze können durch Warteschlan genbildung, oder Speichern, der verzögerten Operationen ge löst werden. Zum Beispiel wird ein statischer Direkt zugriffsspeicher (SRAM) bei Cache-Operationen verwendet, und die Technik des dynamischen Direktzugriffsspeichers (DRAM) ist im allgemeinen nicht für Caches verwendet wor den, weil sie, bezüglich der Zugriffszeit, relativ zum Hauptspeicher einen geringen Nutzen bietet. Die DRAM- Technik ist jedoch pro Bit Speicher näherungsweise viermal weniger teuer als der SRAM und ermöglicht aufgrund seiner höheren Dichte, daß ein viel größerer Cache für einen be stimmten Bereich implementiert wird. Wenn eine nutzbare Fläche "auf dem Gehäuse" von Bedeutung ist, erlangt der Dichtevorteil des DRAMs gegenüber dem SRAM ebenfalls Bedeu tung.

Während die Größe des SRAM-implementierten Primär-Caches zunimmt, nimmt die Größe des Speichers, der für den Sekun där- oder Tertiär-Cache erforderlich ist, ebenfalls zu. Ty pischerweise, wenn eine Cache-Hierarchie implementiert wird, wird die Größe des Speichers auf jeder nachfolgenden Ebene um einen Faktor von vier oder acht erhöht. Daher ist für einen Primär-Cache von einem Megabyte ein Sekundär- Cache von vier bis acht Megabyte wünschenswert. Da die Grö ße des Sekundär-Caches zunähme, würde die Verwendung des SRAMs aufgrund seiner eingeschränkten Dichte untragbar wer den. Durch Verwendung der DRAM-Technologie sind Sekundär- Caches von 32 Megabyte oder mehr möglich. Während die Zeit für einen Zugriff auf Informationen, die im DRAM-Sekundär- Cache gespeichert sind, zunimmt, wird die Gesamtbeeinträch tigung durch die geringe Primär-Cache-Fehlschlagsrate, die dem größeren Primär-Cache zugeordnet ist, versetzt. In an deren Worten könnte der Sekundär-Cache eine längere Latenz umfassen, während die Größe des Primär-Caches zunimmt.

Um die Latenz, die dem Sekundär-Cache zugeordnet ist, wei ter zu verringern, kann der DRAM-Speicher konzipiert sein, um eine schnellere Zugriffszeit aufzuweisen. Diese schnel lere Zugriffszeit wird durch die Verwendung kleinerer DRAM- Chips als im Hauptspeicher erreicht, wodurch die Anzahl von Pins, die zum Übertragen von Daten zu und aus dem DRAM ver wendet werden, erhöht wird und die Frequenz, bei der der DRAM-Chip arbeitet, erhöht wird. Die DRAM-Chips können kon figuriert sein, um zu ermöglichen, daß eine Cache-Zeile in der Größenordnung von 15 Nanosekunden übertragen wird.

Sowohl die erweiterte Größe des Sekundär-Caches und seine längere Latenzzeit (im Vergleich zum Primär-Cache) erfor dern eine Methodik, um mehrere unerfüllte Anforderungen für Daten aus dem Sekundär-Cache zu bewältigen. Die Anforderun gen können sogar alle zwei Nanosekunden empfangen werden, und wenn 15 Nanosekunden für eine Anforderung benötigt wer den, um bedient zu werden, können mehrere zusätzliche An forderungen empfangen werden. Obgleich die Systeme des Stands der Technik zahlreiche Anforderungen an den SRAM- Sekundär-Cache sequentiell gehandhabt haben, erfordert die Verwendung von größeren DRAM-Sekundär-Cache-Strukturen ei nen solideren Lösungsansatz.

Fig. 1 zeigt eine Sekundär-Cachestruktur 100, die zwei War teschlangen, eine Lese-Warteschlange (ReadQ) 101 und eine Schreibe-Warteschlange (WriteQ) 102, umfaßt. Für den Zweck der vorliegenden Darstellung kann ReadQ 101 acht Adressen 103 und zwei Datenzeilen 104 halten, während WriteQ 102 acht Adressen 105 und acht Datenzeilen 106 halten kann. Ei ne Adresse 103 und eine Adresse 105 sind gepufferte Kopien der Adresse der Cache-Zeile, die im DRAM 113 gespeichert wird, nicht die Cache-Zeile an sich. Wenn eine Leseanforde rung durch den Sekundär-Cache empfangen wird, wird diese durch die Etiketten-Pipeline 107 verarbeitet, die den Platz der Cache-Zeile im DRAM 113 bestimmt. Die Leseanforderung wird an einem der Adreßplätze gespeichert, und während die Lese-Aktion stattfindet, können zusätzliche Leseanforderun gen durch ReadQ 101 empfangen werden. Gleichzeitig können Schreibanforderungen empfangen werden, die durch die Eti ketten-Pipeline 107 verarbeitet und durch WriteQ 102 ge speichert werden. Die Speicherung von mehreren Anforderun gen ermöglicht den Caches, als nichtblockierende Caches zu arbeiten, die dem System ermöglichen, weiterhin mit einer oder mehreren unerfüllten, anstehenden Transaktionen zu ar beiten. Eine Speicherentscheidungsvorrichtung oder eine Speicherzugriffs-Ordnungsvorrichtung, die nachstehend be schrieben wird, wird verwendet, um die Sequenz von mehreren anstehenden Anforderungen zu bestimmen.

Die Etiketten-Pipeline 107 und der Etiketten-RAM 108 werden verwendet, um zu bestimmen, ob die angeforderte Cache-Zeile im Sekundär-Cache resident ist. Die Etiketten-Pipeline 107 ist ebenfalls wirksam, um für eine neue Cache-Zeile, die in den Sekundär-Cache geschrieben werden soll, Platz zu ma chen. Wenn die Cache-Zeile im Sekundär-Cache resident ist, wird die Anforderung durch die Etiketten-Pipeline 107 an die ReadQ 101 gesendet, die dann auf die Anforderung hin agiert. Die ReadQ 101 liefert dann die Cache-Zeile zur CPU. Wenn die Cache-Zeile nicht resident ist, wird die Anforde rung durch die Etiketten-Pipeline 107 an den Hauptspeicher über einen Multiplexer 109 gesendet. Die Cache-Zeilen, die vom Hauptspeicher zurückkehren, gelangen durch den Busrück gabepuffer 110 und werden über den Multiplexer 111 zum Pro zessor 112 gesendet. Diese Cache-Zeilen, die vom Hauptspei cher zurückkehren, können ebenfalls im Sekundär-Cache ge speichert werden, um die Zugriffszeit für anschließende Ab fragen der gleichen Cache-Zeile zu verringern. Die Etiket ten-Pipeline 107 und der Etiketten-RAM 108 behandeln Opera tionen aus der CPU atomisch und sequentiell. Dies verdeckt das Warteschlangenverhalten, das zum Liefern der Daten not wendig ist.

Die WriteQ 102 ist für das Schreiben von neuen Cache-Zeilen in den DRAM des Sekundär-Caches verantwortlich. Diese Ca che-Zeilen werden vom Prozessor oder dem Hauptspeicher er halten. Der Prozessor kann die Cache-Zeile zurück zum Se kundär-Cache senden, wenn er die Informationen, die in der Cache-Zeile enthalten sind, aktualisiert hat, oder die Ca che-Zeile kann zum Sekundär-Cache gesendet werden, um die Daten aus dem Primär-Cache zu entfernen. Die Cache-Zeilen, die aus dem Primär-Cache kommen, befinden sich typischer weise im modifizierten oder "schmutzigen" Zustand. Das Speichern der modifizierten Cache-Zeile im Sekundär-Cache und nicht im Hauptspeicher ermöglicht eine schnellere, an schließende Wiedergewinnung der Cache-Zeile. Die Cache- Zeilen, die aus dem Hauptspeicher kommen, gelangen durch den Busrückgabepuffer 110 zur WriteQ 102 und werden im DRAM 113 gespeichert.

Die Größe des DRAMs 113 beträgt bei einem bevorzugten Aus führungsbeispiel 32 Megabyte. Der DRAM 113 kann daher 262.144 Cache-Zeilen speichern, wenn die Größe von jeder Cache-Zeile 128 Byte beträgt. Bei einem bevorzugten Ausfüh rungsbeispiel verwendet der DRAM 113 einen satzassoziativen Vier-Wege-Cache, der 65.536 Reihen enthält. Der satzasso ziative Vier-Wege- (0, 1, 2, 3) Cache ermöglicht daher die Speicherung von 262.144 Cache-Zeilen. Der satzassoziative Cache kann als ein zweidimensionales Array dargestellt wer den.

Ein Fachmann mit Durchschnittsqualifikation würde verste hen, daß, obwohl die vorliegende Beschreibung einen einzel nen Prozessor, der eine Cache-Zeile anfordert, erörtert, die Erfindung auf eine Anzahl von Prozessoren, die den Sekundär-Cache teilen, gleichermaßen anwendbar wäre.

Fig. 2 zeigt ein zweidimensionales Array, das den satzasso ziativen Cache, der im DRAM 113 enthalten ist, darstellt. Das zweidimensionale Array enthält 65.536 Indizes oder Rei hen und vier Wege (0, 1, 2, 3). Wenn eine Cache-Zeile an den Sekundär-Cache gesendet wird, legt die Etiketten- Pipeline 107 eine Funktion an die Adresse an, um zu bestim men, wo im DRAM 113 die Cache-Zeile gespeichert werden soll. Die Funktion bestimmt zuerst, in welchem Index die Cache-Zeile gespeichert werden könnte. Sechzehn Bit der Ca che-Zeilenadresse werden verwendet, um den Index zu bestim men. Anschließend wird der Cache-Zeilenweg unter Verwendung der nächsten zwei Bits der Funktion bestimmt. Zum Beispiel würde eine Cache-Zeile mit dem Ausgangssignal der Funktion auf der Adresse 000000000000000110 im Index 1 (0000000000000001) und Weg 2 (10) gespeichert werden. Die Cache-Zeile würde im Platz 201 der Fig. 2 gespeichert wer den. Vierundvierzig Bit werden im Hauptspeicher verwendet, um einzelne Bytes zu adressieren, wo die oberen zweiund dreißig Bits verwendet werden, um die Cache-Zeilen zu dif ferenzieren. Da nur achtzehn Bit der Cache-Zeilenadresse verwendet werden, um zu bestimmen, wo im DRAM 113 die Ca che-Zeile gespeichert wird, kann mehr als eine Cache-Zeile im gleichen Abschnitt des DRAMs 113 gespeichert werden, je doch vorzugsweise nicht gleichzeitig.

Der Etiketten-RAM 108 (Fig. 1) enthält ebenfalls 65.536 Reihen (Indizes) und vier Spalten (Wege) und wird verwen det, um die Position einer Cache-Zeile im DRAM 113 zu be stimmen. Wenn vom Primär-Cache eine Anforderung empfangen wird, berechnet die Etiketten-Pipeline 107 einen Index, der für den Zugriff auf den Etiketten-RAM 108 verwendet wird. Bei einem bevorzugten Ausführungsbeispiel werden 44 Bits (0 bis 43) verwendet, um den Hauptspeicher zu adressieren, wo bei 0 das höchstwertige Bit und 43 das niederwertigste Bit ist. Da die Cache-Zeilen 128 Byte enthalten, werden die un teren sieben Bits (37 bis 43) nicht verwendet und können fallengelassen werden. Sechzehn der verbleibenden Bits (21 bis 36) werden durch die Etiketten-Pipeline 107 verwendet, um den Index für sowohl den Etiketten-RAM 108 als auch den DRAM 113 zu berechnen. Die verbleibenden Bits, die Bits 0 bis 20, die als das "Etikett" bezeichnet werden, werden im entsprechenden Abschnitt des Etiketten-RAMs 108 gespei chert. Die im Etiketten-RAM 108 gespeicherten Bits sowie die Position, wo die Bits gespeichert sind, werden durch die Etiketten-Pipeline 107 verwendet, um zu bestimmen, ob die gewünschte Cache-Zeile im Sekundär-Cache vorhanden ist. Bei diesem Ausführungsbeispiel wird jeder der vier Wege überprüft, um zu bestimmen, ob die Cache-Zeile im Sekundär- Cache vorhanden ist.

Fig. 3 ist eine Sekundär-Cache-Struktur, die die ReadQ 101, die WriteQ 102, die Kohärenz-Warteschlange (CohQ) 301 und die Räumungswarteschlange (EvictQ) 302 umfaßt. Die ReadQ 101, die CohQ 301 und die EvictQ 302 werden jeweils verwen det, um Cache-Zeilen aus dem DRAM zu lesen. In Fig. 3 wird die ReadQ 101 verwendet, um die Cache-Zeile aus dem DRAM zu lesen und die Cache-Zeile zum Prozessor zurückzusenden. Ei ne Kopie der Cache-Zeile kann im Sekundär-Cache zurück gehalten werden.

Die CohQ 301 wird verwendet, um den DRAM zu lesen und die Daten an einen anderen Prozessor über den externen Spei cherbus zu senden. Die CohQ 301 wird verwendet, um ein Schnüffeln von einem anderen Prozessor zu erfüllen. Das Schnüffeln nimmt die Cache-Zeile aus dem Sekundär-Cache und gibt die Cache-Zeile an einen zweiten Prozessor ansprechend auf das Schnüffeln frei. Die CohQ 301 ähnelt einer Fern- Lesewarteschlange von einem zweiten Prozessor.

Die EvictQ 302 löscht eine Cache-Zeile aus dem DRAM. Abhän gig vom Status der Cache-Zeile kann die EvictQ 302 die Da ten (für gemeinsame oder private Leerdaten) aussortieren, oder die EvictQ 302 sendet eine verschmutzte, private Ca che-Zeile zum Hauptspeicher oder einem anfragenden Prozes sor zurück. In beiden Fällen macht die EvictQ 302 im Sekun där-Cache Platz für nachfolgende Daten. Typischerweise spült die EvictQ 302 die älteste Cache-Zeile aus dem Sekun där-Cache. Während die Cache-Zeile aus dem Speicher gespült wird, werden die Etiketten-Pipeline 107 und der Etiketten- RAM 108 aktualisiert, um die gespeicherten Informationsda ten zu reflektieren.

Das System von Fig. 3 umfaßt drei separate, spezialisierte Lesewarteschlangen in Form der ReadQ 101, CohQ 301 und EvictQ 302, weil das Gesamtverhalten des Systems direkt an die Zeit gebunden ist, die erforderlich ist, um die Lese- Aktionen von einem Prozessor zu bedienen. Sowohl die ReadQ 101 als auch die CohQ 301 können, wenn die Lese-Aktionen nicht umgehend ausgeführt werden, bewirken, daß ein Prozes sor seine Gesamtbetriebsgeschwindigkeit verringert. Die EvictQ 302 wird verwendet, um alte Cache-Zeilen, die nicht mehr benötigt werden, zurück zum Hauptspeicher zu schieben, um die Speicherung von zusätzlichen Cache-Zeilen zu ermög lichen. Indem jeder der Lese-Aktionen eine separate Warte schlange gewidmet wird, wird das Gesamtsystemverhalten ver bessert.

Die CohQ 301 von Fig. 3 kann zwei Adressen und zwei Daten leitungen beinhalten, während die EvictQ 302 vier Adressen und vier Datenleitungen beinhalten kann. Die Anzahl von Adressen und die Anzahl von Datenleitungen sind vom Verhal ten, das von der Sekundär-Cache-Struktur gewünscht ist, ab hängig. Während die Anzahl von Adressen und die Anzahl von Datenleitungen, die gespeichert sind, erhöht wird, erhöht sich das Gesamtverhalten des Systems.

Die Warteschlangenarchitektur, die in Fig. 3 gezeigt ist, ermöglicht der eingehenden Transaktionsrate, vorübergehend die Rate zu übertreffen, mit der die eingehenden Transak tionen verarbeitet werden können. In anderen Worten können zu einem bestimmten Zeitpunkt mehrere Anforderungen ausste hen. Diese ausstehenden Anforderungen werden in den Adreß warteschlangen von ReadQ 101, CohQ 301, EvictQ 302 und Wri teQ 102 gespeichert. Die separaten, unterscheidbaren Warte schlangen werden für die verschiedenen Transaktionen ver wendet, um kritischeren Transaktionen eine höhere Priorität einzuräumen. Wenn mehrere ausstehende Anforderungen inner halb einer bestimmten Warteschlange vorhanden sind, werden sie in der Reihenfolge, in der sie empfangen wurden, be dient. Die ausstehenden Anforderungen innerhalb einer be stimmten Warteschlange können jedoch nicht sequentiell be dient werden, da die Abhängigkeiten zwischen den Warte schlangen eine ausstehende Transaktion in einer weiteren Warteschlange erfordern können, um gegenüber der Bedienung der nächsten ausstehenden Anforderungen in der vorhandenen Warteschlange Priorität zu erlangen. Die Abhängigkeiten werden in einer Abhängigkeitslogik gesammelt.

Fig. 4 zeigt die Struktur der Adressen für die verschiede nen Warteschlangen von Fig. 3. Die in den Adressen der ver schiedenen Warteschlangen gespeicherten Adressen sind im Hinblick auf den DRAM 113 und nicht auf die Cache-Zeilen- Adresse aus dem Hauptspeicher. Wie in Fig. 2 beschrieben ist, wird eine Speicheradresse im DRAM 113 durch einen In dex und einen Weg identifiziert, wobei der Index von 0 bis 65.536 und der Weg von 0 bis 3 variiert. Für den Zweck von Fig. 4 bis 7 wird die Speicheradresse des DRAMs 113 durch geordnete Paare der Form (x, y) identifiziert, wobei x den Indexwert und y den Wegewert darstellt. Zum Beispiel würde (5, 3) eine Cache-Zeile darstellen, die bei einem Indexwert von 5 und einem Weg 3 gespeichert ist. Wie zuvor erörtert wurde, werden mehrere ausstehende Anforderungen, die in ei ner spezifischen Warteschlange vorhanden sind, in der Rei henfolge verarbeitet, in der sie empfangen wurden. Wenn ei ne Lese-Aktion für (10, 1) zuerst empfangen werden würde, der eine Lese-Aktion für (11, 2) folgte, der eine Lese- Aktion für (3, 0) folgte, und jede dieser Anforderungen ausstehend wäre, würde die ReadQ-Adresse 103 erscheinen, wie in Fig. 4 dargestellt ist. Ohne die Transaktionen, die in den anderen Warteschlangen anstehen, würde die Lese- Aktion 401 zuerst bedient werden, die Lese-Aktion 402 als nächstes bedient werden und schließlich die Lese-Aktion 403 als letztes verarbeitet werden.

Fig. 5 zeigt die Struktur der Adressen, wenn die Transak tionen in der CohQ und der ReadQ anstehen. Die Bezeichnung "T" zeigt die Zeitsequenz an, mit der die Anforderungen durch die Etiketten-Pipeline 107 empfangen und verarbeitet wurden. In Fig. 5 wurde zum Zeitpunkt T1 eine Lese-Aktion (10, 1) empfangen, der eine Kohärenz (5, 1) zum Zeitpunkt T2 folgte, der eine Lese-Aktion (11, 2) zum Zeitpunkt T3 folgte, dem eine Kohärenz (7, 2) zum Zeitpunkt T4 folgte, der eine Lese-Aktion (3, 0) zum Zeitpunkt T5 folgte. Vor zugsweise erlangt eine ausstehende Kohärenzanforderung ge genüber einer ausstehenden Anforderung in einer beliebigen der anderen drei Warteschlangen (ReadQ, EvictQ oder WriteQ) Priorität. Wenn jede der Transaktionen, die in Fig. 5 iden tifiziert sind, ausstünde und nicht begonnen hätte, würde die Kohärenz (5, 1) 501 vor der Lese-Aktion (10, 1) 502 zu erst bedient werden, selbst wenn die Lese-Aktion (10, 1) 502 zuerst empfangen wurde. Zusätzlich, da die ausstehenden Transaktionen in der Kohärenzwarteschlange gegenüber den ausstehenden Transaktionen in den anderen Warteschlangen Priorität besitzen, würden ausstehende Kohärenztransaktio nen (7, 2) 503 ebenfalls vor der Lese-Aktion (10, 1) 502 bedient werden. Sobald jede der ausstehenden Kohärenztrans aktionen bedient wurde, würden die drei ausstehenden Lese anforderungen der Reihe nach ausgeführt werden.

Fig. 6 zeigt die Struktur der Adressen, wenn die Transak tionen in der ReadQ, EvictQ und WriteQ anstehen. In Fig. 6 wurde zum Zeitpunkt T1 eine Lese-Aktion (10, 1) empfangen, der eine Räum-Aktion (13, 0) zum Zeitpunkt T2 folgte, der eine Schreib-Aktion (5, 1) zum Zeitpunkt T3 folgte, der ei ne Schreib-Aktion (7, 2) zum Zeitpunkt T4 folgte, der eine Schreib-Aktion (8, 0) zum Zeitpunkt T5 folge, der eine Le se-Aktion (11, 2) zum Zeitpunkt T6 folgte.

Vorzugsweise erlangt, abgesehen von einer Aktion auf dem identischen Abschnitt des DRAMs 113, eine Lese-Aktion ge genüber einer Schreib-Aktion Priorität. Wenn jede der Transaktionen, die in Fig. 6 identifiziert sind, ausstehend wäre, würde die Lese-Aktion (10, 1) zuerst auftreten, ge folgt von der Lese-Aktion (11, 2). Da die Räum-Aktion ein spezifischer Typ von Lese-Aktion ist, träte die Räum-Aktion (13, 0) an dritter Stelle auf, der die drei Schreibanforde rungen der Reihe nach folgten.

Fig. 7A zeigt die Struktur der Adressen, wenn die Transak tionen in der ReadQ und der WriteQ anstehen und derselbe Speicherabschnitt des DRAMs 113 betroffen ist. In Fig. 7A wurde zum Zeitpunkt T1 eine Lese-Aktion (5, 0) empfangen, der eine Schreib-Aktion (6, 1) zum Zeitpunkt T2 folgte, der eine Schreib-Aktion (9, 0) zum Zeitpunkt T3 folgte, der ei ne Lese-Aktion (7, 1) zum Zeitpunkt T4 folgte, der eine Schreib-Aktion (10, 0) zum Zeitpunkt T5 folgte, der eine Lese-Aktion (9, 0) zum Zeitpunkt T6 folgte, der eine Lese- Aktion (11, 2) zum Zeitpunkt T7 folgte, der eine Lese- Aktion (15, 0) zum Zeitpunkt T8 folgte. Wie im Hinblick auf Fig. 5 beschrieben ist, geschehen Lese-Aktionen vorzugswei se vor Schreib-Aktionen, solange kein Konflikt besteht, d. h. solange die Operationen nicht in dieselbe Speicherstelle des DRAMs 113 involvieren. Wenn jedoch dieselbe Speicher stelle des DRAMs 113 betroffen ist, muß die Operation, die an dieser Speicherstelle zuerst angefordert wurde, gesche hen, bevor die Operation, die als zweites angefordert wur de, an dieser Speicherstelle ausgeführt wird. In anderen Worten muß, im Hinblick auf Fig. 7A, die Schreib-Aktion (9, 0), die zum Zeitpunkt T3 geschah, geschehen, bevor die Le se-Aktion (9, 0), die zum Zeitpunkt T5 geschah, stattfin det. Diese Sequenzierung wird durch Überprüfen möglicher Abhängigkeiten erreicht, wenn eine Transaktion angefordert wird, und, wenn eine Abhängigkeit identifiziert wird, wo durch sichergestellt wird, daß die abhängige Transaktion vor der Transaktion erreicht wird, die die Abhängigkeit be wirkte.

Zum Zeitpunkt T1, als die Lese-Aktion (5, 0) empfangen wur de, gab es keine ausstehenden Transaktionen in keiner der Warteschlangen, so daß keine Abhängigkeit identifiziert wurde. Zum Zeitpunkt T2, als die Schreib-Aktion (6, 1) emp fangen wurde, gab es keine weiteren Transaktionen, die den Speicherplatz (6, 1) des DRAMs 113 betrafen, so daß daher keine Abhängigkeiten identifiziert wurden. In ähnlicher Weise wurde zum Zeitpunkt T3, als die Schreib-Aktion (9, 0) empfangen wurde, jede ausstehende Transaktion überprüft und es wurden keine Abhängigkeiten identifiziert, weil keine ausstehende Transaktion den Speicherplatz (9, 0) des DRAM 113 betraf. Zum Zeitpunkt T4 wurde die Lese-Aktion (7, 1) empfangen, und es wurde erneut keine Abhängigkeit identifi ziert. Zum Zeitpunkt T5 wird die Schreib-Aktion (10, 0) an gefordert, die erneut mit keiner der ausstehenden Transak tionen in Konflikt steht. Zum Zeitpunkt T6, wenn jedoch die Anforderung von der Etiketten-Pipeline 107 nach Abhängig keiten überprüft wird, wird die Schreib-Aktion (9, 0) iden tifiziert und eine Abhängigkeit wird eingerichtet, die er fordern wird, daß der jüngste Eintrag in die WriteQ, die die Abhängigkeit involviert, beendet werden muß, bevor die Lese-Aktion (9, 0) bedient wird. Bei diesem Beispiel wird die Lese-Aktion (5, 0) zuerst bedient, der eine Lese-Aktion (7, 1) folgt, der eine Schreib-Aktion (6, 1) folgt, der ei ne Schreib-Aktion (9, 0) folgt, der eine Schreib-Aktion (10, 0) folgt, der eine Lese-Aktion (9, 0) folgt, der eine Lese-Aktion (11, 2) folgt, der eine Lese-Aktion (15, 0) folgt. Durch Bedienen der Schreib-Aktion (9, 0) vor der Le se-Aktion (9, 0) stellt das System sicher, daß die letzte Cache-Zeile für (9, 0) durch die Lese-(9, 0)-Transaktion empfangen wird.

Fig. 7B zeigt ein Beispiel der Abhängigkeitsauswahl, wenn mehrere Adreßabhängigkeiten existieren. Bei diesem Beispiel wird davon ausgegangen, daß die Transaktionen T1, T2, T3, T4 und T5 in der ReadQ anstehen, wenn zum Zeitpunkt T6 eine Schreib-Aktion von (10, 0) in die WriteQ eingebracht wird. Wenn die (10, 0) Schreib-Aktion 701 in den WriteQ-Schlitz 101 eingebracht wird, wird seine Adresse mit allen gültigen Einträgen in die ReadQ verglichen. Die Schlitze 3 702 und 5 703 stimmen beide überein, so daß die Abhängigkeiten dahin gehend existieren, daß der ReadQ-Schlitz 3 702 vor dem Wri teQ-Schlitz 1 701 ausgeführt werden muß und der ReadQ- Schlitz 5 703 vor dem WriteQ-Schlitz 1 701 ausgeführt wer den muß. Das System muß diese beiden Abhängigkeiten jedoch nicht verfolgen. Es ist ausreichend, nur die Abhängigkeit bezüglich der "jüngsten" Lese-Aktion, die in die Abhängig keit involviert ist, aufzuzeichnen, da innerhalb der ReadQ eine implizite Priorität besteht, stets die älteste Trans aktion zuerst zu verarbeiten. Der ReadQ-Schlitz 3 702 muß vor dem ReadQ-Schlitz 5 703 ausgeführt werden. Wenn der WriteQ-Schlitz 1 701 nur eine Abhängigkeit bezüglich des ReadQ-Schlitzs 5 703 aufzeichnet, wird daher die Abhängig keit vom ReadQ-Schlitz 3 702 implizit erfüllt.

Fig. 7C zeigt ein Beispiel, das konzipiert ist, um die ro tierende oder Umbruchbeschaffenheit der Q-Strukturen her vorzuheben und zu zeigen, wie die Abhängigkeitsprüfung beeinträchtigt wird. Für dieses Beispiel geht man davon aus, daß die Transaktionen zu den Zeitpunkten T1, T2, T3, T4, T5, T6, T7 und T8 alle zusammen Lese-Aktionen waren und jeweils in den ReadQ-Schlitzen 1 bis 8 gehalten wurden. Dann werden die Transaktionen, die in den ReadQ-Schlitzen 1 bis 4 zurückgehalten wurden, beendet und aus der ReadQ ent fernt. Die nächste Lese-Transaktion wird in den ReadQ- Schlitz 1 704 plaziert, die als (14, 0) T9 gezeigt ist. Es ist zu beachten, daß die Transaktion T9 im Schlitz 1 immer noch "jünger" ist als die Transaktionen in den Schlitzen 5 bis 8. Zusätzliche Leseanforderungen T10 und T11 werden dann in die ReadQ-Schlitze 2 und 3 gesetzt. Der Schlitz, wo eine neue Transaktion plaziert ist, wird durch den ReadQ- Einbringungszeiger gesteuert. Dabei handelt es sich um ei nen rotierenden Zeiger in dem Sinne, daß nach dem Einbrin gen einer Transaktion in den Schlitz 8 sich der Zeiger her umwickelt und auf den Schlitz 1 für die nächste Einbringung zeigt. Infolgedessen hängt die Priorität oder das "Alter" einer Transaktion sowohl von ihrer Schlitzanzahl als auch vom Wert des ReadQ-Einbringungszeigers ab.

Unter Fortsetzung des Beispiels kommt eine Schreib-Aktion an (10, 0) 705 zum Zeitpunkt T12 an. Wenn die Schreib- Aktion (10, 2) T12 in den WriteQ-Schlitz 1 705 eingegeben wird, wird seine Adresse mit der Adresse der ReadQ-Einträge verglichen, um Abhängigkeiten herauszufinden. In diesem Fall weisen der Schlitz 3 706 und der Schlitz 5 707 Adreß übereinstimmungen auf, so daß eine Abhängigkeit zwischen dem ReadQ-Schlitz 3 706 und dem WriteQ-Schlitz 1 705 be steht und eine Abhängigkeit zwischen dem ReadQ-Schlitz 5 707 und dem WriteQ-Schlitz 1 705 existiert. Man beachte, daß dies gleichen Abhängigkeiten sind, die in Fig. 7B exi stierten, jedoch ist nun der Eintrag in den Schlitz 3 706 der jüngste aufgrund der rotierenden Eigenart der ReadQ. Daher markiert sich der Eintrag in den WriteQ-Schlitz 1 705 selbst als vom ReadQ-Schlitz 3 706 abhängig. Die Abhängig keit vom ReadQ-Schlitz 5 707 wird durch die Tatsache, daß die ReadQ ihren Schlitz 5 707 vor dem Schlitz 3 706 ausfüh ren muß, implizit gehandhabt. Ein Fachmann mit Durch schnittsqualifikation würde verstehen, daß die Erfindung andere Kombinationen von Adreßschlitzen und Numerierungs schemata umfaßt.

Fig. 8 ist eine Tabelle, die die Abhängigkeitslogikpriori täten zwischen den verschiedenen Warteschlangen darstellt. Eine Spalte 801 identifiziert eine Warteschlange, die die erste ausstehende Anforderung empfängt. Eine Reihe 802 identifiziert die Warteschlange, die die zweite ausstehende Anforderung für eine Operation oder Transaktion auf der gleichen Speicheradresse empfängt. Der Inhalt der Tabelle zeigt die resultierenden Abhängigkeiten an. Diagonale Zel len 803, 804, 805 und 806 beschreiben zwei ausstehende Transaktionen in der gleichen Warteschlange. Wie zuvor be schrieben wurde, wenn zwei ausstehende Anforderungen in der gleichen Warteschlange enthalten sind, werden die angefor derten Transaktionen in der Reihenfolge, in der sie empfan gen werden, ausgeführt. Die Zellen 807, 808, 809, 810, 811 und 812 sind Situationen, in denen eine erste anstehende Transaktion eine Lese-Aktion und eine zweite anstehende Transaktion eine Schreib-Aktion involviert. Da die Lese- Aktionen nicht destruktiv sind, sind diese Zellen als Gleichgültige (DC; DC = don't care) etikettiert, d. h. die Transaktionen können in einer beliebigen Reihenfolge durch geführt werden. Wie jedoch zuvor beschrieben wurde, wird eine ausstehende Transaktion in einer Kohärenzwarteschlange immer zuerst durch eine Priorität bedient, und daher ist keine Abhängigkeit notwendig.

Wie in Fig. 8 dargestellt ist, beschreibt die Zelle 813 die Abhängigkeit, die erforderlich ist, wenn eine Schreib- Aktion an einen spezifischen Speicherplatz des DRAMs 113 vor einer Lese-Aktion an denselben Speicherplatz des DRAMs 113 auftritt. In diesem Fall sollte die Schreib-Aktion vor der Lese-Aktion geschehen. Die Abhängigkeit wird gehand habt, indem sichergestellt wird, daß die jüngste, überein stimmende, ausstehende Transaktion in der Schreibwarte schlange (als die Leseanforderung empfangen wurde) vor der Bedienung eines ausstehenden Eintrags in die Lesewarte schlange bedient wird. Weitere Abhängigkeitsalgorithmen können in ähnlicher Weise implementiert werden.

Die Zelle 814 von Fig. 8 zeigt die umgekehrte Situation. Darin wird eine übereinstimmende Transaktion zum Lesen ei ner speziellen Speicheradresse des DRAMs 113 vor einer aus stehenden Transaktion zum Schreiben an die Speicheradresse desselben spezifischen DRAMs 113 empfangen. In diesem Fall wird eine Abhängigkeit eingerichtet, die sicherstellt, daß die Lese-Aktion vor der Schreib-Aktion geschieht. Vorzugs weise wird die Abhängigkeit gehandhabt, indem sicherge stellt wird, daß die jüngste, übereinstimmende, ausstehende Transaktion in der Lesewarteschlange (als die Schreibanfor derung empfangen wurde) vor dem Bedienen des ausstehenden Eintrags in die Schreibwarteschlange bedient wird.

Eine Zelle 815 von Fig. 8 beschreibt die Abhängigkeit, die erforderlich ist, wenn eine Schreib-Aktion an einen spezi fischen Speicherplatz des DRAMs 113 vor einer Kohärenzan forderung an denselben spezifischen Speicherplatz des DRAMs 113 geschieht. In diesem Fall sollte die Schreib-Aktion vor der Kohärenz geschehen. Vorzugsweise wird die Abhängigkeit gehandhabt, indem sichergestellt wird, daß die jüngste, übereinstimmende, ausstehende Transaktion in der Schreib warteschlange (als die Kohärenzanforderung empfangen wurde) vor der Bedienung des ausstehenden Eintrags in die Kohä renzwarteschlange bedient wird.

Eine Zelle 816 von Fig. 8 zeigt die umgekehrte Situation. In der Zelle 816 wird eine ausstehende Kohärenztransaktion für eine spezifische Speicheradresse des DRAMs 113 vor ei ner ausstehenden Transaktion zum Schreiben derselben spezi fischen Speicheradresse des DRAMs 113 empfangen. In diesem Fall stellt die Priorität, die sicherstellt, daß die Kohä renztransaktion vor der Schreibtransaktion geschieht, die richtige Sequenzierung der Transaktionen sicher.

Eine Zelle 817 von Fig. 8 beschreibt die Abhängigkeit, die erforderlich ist, wenn eine Schreib-Aktion an einen spezi fischen Speicherplatz des DRAMs 113 vor einer EvictQ- Anforderung an den gleichen spezifischen Speicherplatz des DRAMs 113 geschieht. In diesem Fall sollte die Schreib- Aktion vor der Räum-Aktion geschehen. Vorzugsweise wird die Abhängigkeit gehandhabt, indem sichergestellt wird, daß die jüngste, übereinstimmende, ausstehende Transaktion in der Schreibwarteschlange (als die Räumungsanforderung empfangen wurde) vor dem Bedienen des ausstehenden Eintrags in die Räumungswarteschlange bedient wird.

Eine Zelle 818 von Fig. 8 zeigt die umgekehrte Situation. In der Zelle 818 wird eine ausstehende Räumungstransaktion für eine spezifische Speicheradresse des DRAMs 113 vor ei ner ausstehenden Transaktion zum Schreiben derselben spezi fischen Speicheradresse des DRAMs 113 empfangen. In diesem Fall sollte die Räumungstransaktion vor der Schreibtransak tion geschehen, um sicherzustellen, daß die Cache-Zeile, die sich momentan am Platz des DRAMs 113 befindet, nicht durch die Schreibtransaktion überschrieben wird. Die Abhän gigkeit wird gehandhabt, indem sichergestellt wird, daß die jüngste, übereinstimmende, ausstehende Transaktionen in der Räumungswarteschlange (als die Schreibwarteschlange empfan gen wurde) vor dem Bedienen des ausstehenden Eintrags auf die Schreibwarteschlange bedient wird.

Der Bedarf an einer Abhängigkeit zwischen einer Operation, die für einen spezifischen Speicherplatz zuerst angefordert wurde, und einer zweiten angeforderten Operation auf dem selben Speicherplatz ist ausführlich beschrieben worden. Zum Zwecke der vorliegenden Darstellung kann der komplette Satz von Abhängigkeiten erzeugt werden, indem die Adresse einer eingehenden Transaktion mit der Adresse von jeder gültigen Transaktion, die in der Warteschlange wartet, ver glichen wird. Jede Adreßübereinstimmung wird durch eine Eins oder ein anderes passendes Flag (bzw. Anzeigeelement) dargestellt. Die Übereinstimmungsbits werden dann miteinan der verkettet, wobei mit dem Übereinstimmungsbit von Schlitz 8 begonnen und mit dem Übereinstimmungsbit von Schlitz 1 aufgehört wird. Für das Beispiel in Fig. 7C, wo der Schlitz 3 und der Schlitz 5 Übereinstimmungen aufwei sen, erzeugt dies eine ursprüngliche Übereinstimmungsbit- Zeichenfolge von 00010100.

Fig. 9 zeigt die Schritte, die erforderlich sind, um das höchstwertige oder jüngste Übereinstimmungsbit zu finden. Die ursprünglichen Übereinstimmungsbits oder ein ursprüng licher Übereinstimmungsvektor werden erzeugt, indem eine Adresse einer eingehenden Transaktion mit der Adresse von jeder anstehenden Transaktion verglichen wird. Der Q-Einbringungszeiger ist 3, was uns bedeutet, daß der jüngste ReadQ-Eintrag der Schlitz 3 ist, der nächstjüngste der Schlitz 2 ist, und dann die Schlitze 1, 8, 7, 6, 5 und 4 folgen. Um die ursprünglichen Übereinstimmungsbits zu nor malisieren, so daß sie in einer Reihenfolge vom jüngsten bis zum ältesten geordnet sind, müssen wir eine rechte Dre hung um den Betrag des Q-Einbringungszeigers vornehmen. An schließend wird die Löschmaske 903 angewendet, die aus Nul len für jedes Bit besteht, wobei beim Bit Null begonnen wird bis einschließlich dem ersten übereinstimmenden Bit, und anschließend aus Einsen für jedes verbleibende Bit be steht.

Fig. 10 ist ein schematisches Diagramm einer logischen Schaltung, die konfiguriert ist, um die Löschmaske 903 zu erzeugen. Es werden nach rechts verschobene Bits 902 durch die Schaltung in einer Reihenfolge empfangen, wo RS[0] das erste Bit des nach rechts verschobenen Bits 902 ist. Bei diesem Beispiel ist das Bit[0] des nach rechts verschobenen Bits 0, und das erste Bit der Löschmaske ist 0 (CM[0]) 1002. Sowohl das Bit[0] als auch das Bit[1] der nach rechts verschobenen Bits 902 sind an den Eingängen des ODER- Gatters 1003 vorhanden, die, wenn sie kombiniert werden, eine Eins für das Bit[2] des Löschmaskenbits 903 erzeugen. In ähnlicher Weise wird jedes nachfolgende Bit der Lösch maske 903 erzeugt. Es wird darauf hingewiesen, daß, obwohl die Erzeugung der Löschmaske gezeigt ist, wenn diese in ei ner Hardware implementiert ist, statt dessen Software- und Firmwareimplementierungen verwendet werden können.

Sobald die Löschmaske 903 erzeugt ist, werden ihre Bits in vertiert und durch eine UND-Funktion mit den nach rechts verschobenen Bits 902 kombiniert, um eine angewandte Maske 904 zu erzeugen. Das Ergebnis der Berechnung der Löschmaske 903 und die UND-Verknüpfung des Inversen der Löschmaske 903 mit den nach rechts verschobenen Bits 902 ist, alle Er scheinungen von "1" in den nach rechts verschobenen Bits mit Ausnahme der ersten Erscheinung zu eliminieren. Die an gewandte Maske 904 wird dann umgekehrt verschoben (um den gleichen Betrag nach links verschoben, um den die ursprüng lichen nach rechts verschobenen Bits 902 nach rechts ver schoben wurden), um die Antwort zu bestimmen. Die Antwort zeigt an, von welchem Bit oder welchem Eintrag in die War teschlange die aktuelle Warteschlange abhängt. In anderen Worten, welcher Warteschlangeneintrag ausgeführt werden muß, bevor diese Anforderung beendet werden darf.

Fig. 11 zeigt ein bevorzugtes Verfahren zum Bestimmen der Abhängigkeit. Fig. 11 beginnt mit den gleichen ursprüngli chen Übereinstimmungsbits und dem Zählerwert wie in Fig. 9. Doppelte Übereinstimmungsbits 1101, die auch als ein erwei terter Übereinstimmungsvektor bezeichnet werden, werden durch Doppeln der ursprünglichen acht Bits und Verketten derselben erzeugt, um eine 16-Bit-Zeichenfolge 0010 1000 0010 1000 zu bilden.

Fig. 12A und 12B zeigen Verfahren zum Erzeugen von Werten der Zählermaske 1102. Die Zählermaske 1102 wird anhand des Zählerwerts unter Verwendung einer Kombinationslogik er zeugt. Wie in Tabelle 1 gezeigt ist, wird für jeden Zähler wert eine unterschiedliche Zählermaske erzeugt. Die Verwen dung einer 8-Eintrags-Warteschlange mit zugeordneten CAMs erfordert acht unterschiedliche Zählerwerte.

Tabelle 1

Die Zählermaskenwerte, die in Tabelle 1 identifiziert sind, zeigen die Werte für die ersten acht Bits der Zählermaske 1102. Die verbleibenden acht Bits sind das Inverse der er sten acht Bits. In anderen Worten sind die äußerst rechten acht Bits gleich einer invertierten Kopie der äußerst lin ken acht Bits.

Die markierten Übereinstimmungsbits 1103 werden durch UND- Verknüpfung der doppelten Übereinstimmungsbits 1101 und der Zählermaske 1102 bestimmt. Wie in Fig. 11 gezeigt ist, ent halten nur die Bits 4 und 10 in sowohl den doppelten Über einstimmungsbits 1101 als auch der Zählermaske 1102 eine "1".

Fig. 13 zeigt eine bevorzugte Implementierung zum Erzeugen der Löschmaske 1104. Das Bit[0] 1301 der Löschmaske 903 ist Null. Bei diesem Beispiel wird das Bit[0] der maskierten Bits 1103 am Bezugszeichen 1302 eingegeben, was dazu führt, daß das Bit[1] der Löschmaske 1104 ebenfalls Null ist. Die nachfolgenden Bits der Löschmaske 903 verbleiben bei Null, bis ein Bit der maskierten Übereinstimmungsbits 1103 gleich eins ist. Sobald dies geschieht, ist das entsprechende Bit der Löschmaske gleich eins. Bei einem bevorzugten Ausfüh rungsbeispiel müssen die Bits der Löschmaske 1104, die ver bleiben, nachdem die Bits in der Zählermaske 1102 von 1 zu 0 übergegangen sind, nicht bestimmt werden.

Die angelegte Maske 1105 wird bestimmt, indem die Bits, die in der Löschmaske 1104 enthalten sind, invertiert werden und das Ergebnis mit den maskierten Übereinstimmungsbits 1103 UND-verknüpft wurde. Sobald dies ausgeführt worden ist, werden die zweiten acht Bits mit den ersten acht Bits ODER-verknüpft.

Fig. 14 zeigt ein Flußdiagramm, das die Schritte, die der Identifizierung der Abhängigkeit von Fig. 11 zugeordnet sind, beschrieb. Bei Schritt 1401 werden die ursprünglichen Übereinstimmungsbits empfangen und verwendet, um den dop pelten Übereinstimmungswert zu erzeugen. Bei Schritt 1402 wird der Zählerwert verwendet, um die Zählermaske zu erzeu gen. Die Zählermaske kann im voraus als eine Funktion der verschiedenen möglichen Zählerwerte erzeugt werden. Bei Schritt 1403 werden die maskierten Übereinstimmungsbits 1103 durch UND-Verknüpfung der doppelten Übereinstimmungs bits 1101 mit der Zählermaske 1102 erzeugt. Bei Schritt 1404 wird die Löschmaske 1104 gemäß Fig. 13 erzeugt. Bei Schritt 1405 wird die angelegte Maske 1105 durch Invertie ren der Löschmaske 1104 und UND-Verknüpfen der resultieren den Werte mit den maskierten Übereinstimmungsbits 1103 er zeugt. Die Abhängigkeit wird dann im Schritt 1406 durch ODER-Verknüpfen der ersten achts Bits in unserem Beispiel mit dem zweiten Satz von acht Bits, bestimmt.

Claims

1. Verfahren zum Liefern eines geordneten Zugriffs auf einen Speicher, das folgende Schritte aufweist:
Vergleichen einer Adresse einer eingehenden Transakti on mit der Adresse von jeder anstehenden Transaktion, um einen ursprünglichen Übereinstimmungsvektor zu erzeugen, der die Sequenzierungsanforderungen zwischen der eingehenden Transaktion und den anstehenden Trans aktionen anzeigt, wobei der ursprüngliche Übereinstim mungsvektor ein Bit umfaßt, das einem Ergebnis von je dem Vergleich entspricht;
Bilden eines Bildes des ursprünglichen Übereinstim mungsvektors und Verketten des Bildes des ursprüngli chen Übereinstimmungsvektors mit dem ursprünglichen Übereinstimmungsvektor, um einen erweiterten Überein stimmungsvektor zu bilden;
Empfangen eines Werts, der das relative Alter der an stehenden Transaktion anzeigt;
Erzeugen (1402) einer Zählermaske (1102) aus dem Wert;
Erzeugen (1403) von maskierten Übereinstimmungsbits (1103) mit einer Logikoperation auf dem doppelten Übereinstimmungsvektor und der Zählermaske;
Identifizieren von einem der maskierten Übereinstim mungsbits basierend auf einem vorbestimmten Kriterium;
Einstellen der Verbleibenden der Übereinstimmungsbits auf einen ersten vorbestimmten Logikwert, um eine an gelegte Maske (1105) zu liefern; und
logisches Kombinieren (1406) eines ersten Segments der angelegten Maske (1105) mit einem zweiten Segment der angelegten Maske, um höchstens eine der anstehenden Transaktionen zu identifizieren, die vor dem Ermögli chen, daß die eingehende Transaktion verarbeitet wird, beendet werden muß.

2. Verfahren gemäß Anspruch 1, bei dem die Adresse der anstehenden Transaktion und die Adresse der eingehen den Transaktion Abschnitte von jeweiligen Speicher adressen aufweisen.

3. Verfahren gemäß Anspruch 1 oder 2, bei dem das Bild ein Duplikat des ursprünglichen Übereinstimmungsvek tors ist.

4. Verfahren gemäß einem der Ansprüche 1 bis 3, bei dem der Wert ein Zählerwert ist, der eine Position einer rotierenden Warteschlange anzeigt.

5. Verfahren gemäß einem der Ansprüche 1 bis 4, bei dem die Zählermaske (1102) unter Verwendung einer Nach schlagstruktur erzeugt wird.

6. Verfahren gemäß einem der Ansprüche 1 bis 5, bei dem die Zählermaske (1102) unter Verwendung einer Deco dierlogik erzeugt wird.

7. Verfahren gemäß einem der Ansprüche 1 bis 6, bei dem die Logikoperation eine logische UND-Operation ist.

8. Verfahren gemäß einem der Ansprüche 1 bis 7, bei dem das vorbestimmte Kriterium ein Abtasten der maskierten Übereinstimmungsbits (1103) in eine vorbestimmte Rich tung umfaßt, um ein erstes Auftreten eines ersten Bits mit einem zweiten vorbestimmten Logikwert entgegenge setzt zum ersten vorbestimmten Logikwert zu identifi zieren.

9. Verfahren gemäß einem der Ansprüche 1 bis 8, bei dem der Speicher entweder eine Registerdatei, ein Cache, ein Hauptspeicher, ein Bandlaufwerk oder ein Platten speicher ist.

10. Speicherzugriffs-Ordnungsvorrichtung, die folgende Merkmale aufweist:
einen Komparator, der eine Adresse einer eingehenden Transaktion mit der Adresse von jeder anstehenden Transaktion vergleicht und einen ursprünglichen Übereinstimmungsvektor erzeugt, der Sequenzierungsanforderungen zwischen der eingehenden Transaktion und den anstehenden Transaktionen anzeigt, wobei der ursprüngliche Übereinstimmungsvektor ein Bit umfaßt, das einem Ergebnis von jedem Vergleich entspricht;
einen erweiterten Übereinstimmungsvektor, der durch Verketten eines Bildes des ursprünglichen Übereinstim mungsvektors mit dem ursprünglichen Übereinstimmungs vektor gebildet ist;
einen Wert, der das relative Alter der anstehenden Transaktion anzeigt;
eine Zählermaske (1102), die aus dem Wert erzeugt wird;
maskierte Übereinstimmungsbits (1103), die mit einer Logikoperation bezüglich des doppelten Übereinstim mungsvektors und der Zählermaske erzeugt werden;
ein vorbestimmtes Kriterium, das zum Identifizieren von einem der maskierten Übereinstimmungsbits verwen det wird;
eine angelegte Maske (1105), die durch Einstellen der Verbleibenden der Übereinstimmungsbits auf einen er sten vorbestimmten Logikwert gebildet wird; und
eine Identifizierung von höchstens einer der anstehen den Transaktionen, die beendet werden muß, bevor der eingehenden Transaktion ermöglicht wird, verarbeitet zu werden, die durch logisches Kombinieren eines er sten Segments der angelegten Maske mit einem zweiten Segment der angelegten Maske identifiziert wurde.

11. Vorrichtung gemäß Anspruch 10, bei der die Adresse der anstehenden Transaktion und die Adresse der eingehen den Transaktion Abschnitte von jeweiligen Speicher adressen aufweisen.

12. Vorrichtung gemäß Anspruch 10 oder 11, bei der das Bild ein Duplikat des ursprünglichen Übereinstimmungs vektors ist.

13. Vorrichtung gemäß einem der Ansprüche 10 bis 12, bei der der Wert ein Zählerwert ist, der eine Position ei ner rotierenden Warteschlange anzeigt.

14. Vorrichtung gemäß einem der Ansprüche 10 bis 13, bei der die Zählermaske (1102) unter Verwendung einer Nachschlagstruktur erzeugt wird.

15. Vorrichtung gemäß einem der Ansprüche 10 bis 14, bei der die Zählermaske (1102) unter Verwendung einer De codierlogik erzeugt wird.

16. Vorrichtung gemäß einem der Ansprüche 10 bis 15, bei der die Logikoperation eine logische UND-Operation ist.

17. Vorrichtung gemäß einem der Ansprüche 10 bis 16, bei der das vorbestimmte Kriterium ein Abtasten der mas kierten Übereinstimmungsbits (1103) in eine vorbe stimmte Richtung umfaßt, um ein erstes Auftreten eines ersten Bits mit einem zweiten vorbestimmten Logikwert entgegengesetzt zum ersten vorbestimmten Logikwert zu identifizieren.

18. Vorrichtung gemäß einem der Ansprüche 10 bis 17, bei der der Speicher entweder eine Registerdatei, ein Ca che, ein Hauptspeicher, ein Bandlaufwerk oder ein Plattenspeicher ist.