PatentDe  


Dokumentenidentifikation DE69732020T2 15.12.2005
EP-Veröffentlichungsnummer 0000843262
Titel Wiedereinordnung von Speicheranforderungen in einem Datenverarbeitungssystem
Anmelder Hyundai Electronics America Inc., San Jose, Calif., US
Erfinder Talbot, Gerry R., Concord, Massachusetts 01742-4915, US;
Hypher, Austen J., Newton, Massachusetts 02160-1706, US
Vertreter Sparing · Röhl · Henseler, 40237 Düsseldorf
DE-Aktenzeichen 69732020
Vertragsstaaten DE, GB
Sprache des Dokument EN
EP-Anmeldetag 11.11.1997
EP-Aktenzeichen 971196944
EP-Offenlegungsdatum 20.05.1998
EP date of grant 22.12.2004
Veröffentlichungstag im Patentblatt 15.12.2005
IPC-Hauptklasse G06F 13/16

Beschreibung[de]

Die vorliegende Erfindung betrifft ein Verfahren zum Umordnen mehrerer Speicherzugriffsanforderungen gemäß dem Oberbegriff von Anspruch 1 und ein Datenverarbeitungssystem gemäß dem Oberbegriff von Anspruch 8.

Somit betrifft die vorliegende Erfindung allgemein Datenverarbeitungssysteme mit Speicherteilsystemen und insbesondere die Steuerung von Anforderungen an Speicherteilsysteme, um die Bandbreite und die Gleichzeitigkeit zu maximieren, wodurch die Gesamtgeschwindigkeit des Speicherteilsystems und des Datenverarbeitungssystems erhöht wird.

Die Geschwindigkeit der Speicherteilsysteme kann in modernen Datenverarbeitungssystemen ein bedeutender begrenzender Faktor der Geschwindigkeit des Gesamtsystems sein. Der Speicherengpass ist vorhanden, da ein Speicherzugriff typisch wesentlich langsamer als die Geschwindigkeit ist, mit der Computerprozessoren und Datenbusse Speicherzugriffsanforderungen erzeugen und transportieren können. Da eine Leseanforderung angibt, dass ein anfordernder Prozessor möglicherweise auf Daten wartet, ist die niedrige Geschwindigkeit des Speicherzugriffs besonders zu spüren, wenn es im Gegensatz zu einer Schreibanforderung eine Leseanforderung gibt.

Der durch die niedrige Speichergeschwindigkeit verursachte Engpass wird noch ernster, während die Geschwindigkeit von Computerprozessoren mit einer schnelleren Rate als die Geschwindigkeit üblicher Speicherkomponenten steigt. Außerdem wird der Speicherengpass verschärft, während Computersystem- und Netzarchitekturen eingeführt werden, die mehrere Prozessoren enthalten, die ein Speicherteilsystem gemeinsam nutzen.

Ein herkömmlicher Zugang zur Milderung des Speicherengpasses ist die Verwendung des Daten-Caching, möglicherweise auf verschiedenen Ebenen innerhalb des Datenverarbeitungssystems. Zum Beispiel können Abschnitte der Daten in einem langsamen, preiswerten Plattenspeicherteilsystem in ein schnelleres System-RAM-Teilsystem (System-Schreib-Lese-Speicher-Teilsystem) kopiert oder "gecached" werden. Abschnitte von Daten im System-RAM können wiederum in ein RAM-Teilsystem eines Cache der "zweiten Ebene" gecached werden, das eine kleine Menge eines teuren, noch schnelleren RAM enthält. Außerdem können Teile der Daten in einen noch schnelleren Cache-Speicher der "ersten Ebene" gecached werden, der auf dem gleichen Chip wie ein Prozessor liegen kann. Das Daten-Caching ist eine leistungsfähige Technik, um die Zugriffe auf den langsameren Speicher zu minimieren. Allerdings muss an einem Punkt immer noch auf die verschiedenen Speicherebenen zugegriffen werden. Gleich, ob ein Caching verwendet wird oder nicht, werden somit weiter Techniken zum Beschleunigen des Speicherzugriffs benötigt.

Versuche, den Speicherzugriff zu beschleunigen, umfassen das Organisieren des Speichers in mehrere Bänke. Während in Übereinstimmung mit dieser Speicherarchitektur eine erste Speicherbank damit belegt ist, eine Anforderung für den Zugriff auf einen Speicherplatz in der ersten Bank zu bedienen, kann eine zweite, verfügbare Bank damit beginnen, die nächste Speicherzugriffsanforderung zu bedienen, falls die nächste Anforderung einen Speicherplatz in der zweiten Bank zum Ziel hat. Die Speicherplätze können unter den Bänken verschachtelt sein, so dass sich zusammenhängende Speicheradressen, auf die wahrscheinlich sukzessive zugegriffen wird, in verschiedenen Bänken befinden.

Ein Problem bei der herkömmlichen Verwendung von Speicherbänken ist, dass sukzessive Zugriffsanforderungen gelegentlich weiter Adressen in einer gemeinsamen Bank zum Ziel haben, selbst wenn die Adressen unter den Bänken verschachtelt sind. In dieser Situation muss ein herkömmliches Speicherteilsystem weiter darauf warten, dass die gemeinsame Bank verfügbar wird, bevor das Speicherteilsystem beginnen kann, die zweite und irgendwelche nachfolgenden Anforderungen zu bedienen. Ein solches erzwungenes Warten ist verschwenderisch, falls andernfalls damit begonnen werden hätte können, eine dritte Zugriffsanforderung zu bedienen, da die dritte Anforderung eine andere, verfügbare Speicherbank zum Ziel hat. Außerdem behandelt lediglich das Organisieren des Speichers in verschachtelte Bänke nicht die zusätzliche Dringlichkeit, die Leseanforderungen wie oben diskutiert gegenüber Schreibanforderungen haben.

US 5 421 788 betrifft das Management des Belegt-Zustands von Speicherbänken und das Beurteilen, ob Zugriffsanforderungen zulässig sind.

WO 9630838 beschreibt ein Verfahren und eine Vorrichtung zum Umordnen einer Lese- und Schreibanforderung in einem seitenbetriebsartgestützten Computersystem in Übereinstimmung mit einem Umordnungsschema. Dieses Schema ordnet die Anforderungen in der Weise um, dass alle Lese- und Schreibanforderungen, die den Zugriff auf eine momentane Seite erfordern, vor den Lese- und Schreibanforderungen ausgeführt werden, die den Zugriff auf eine andere Seite erfordern. Da die Seitenadresse nicht geändert zu werden braucht und die Seite bereits in einem elektronisch aktivierten Zustand ist, stellt dies einen schnellen Speicherzugriff sicher.

Im Gebiet wird ein Weg benötigt, um den Zugriff auf Speicherteilsysteme in der Weise zu steuern, dass die Bandbreite und die Gleichzeitigkeit maximiert werden, indem die Zeitdauer, die Speicheranforderungen darauf warten müssen, bedient zu werden, minimiert wird. Insbesondere wird ein Weg benötigt, der ermöglicht, dass ein Speicherteilsystem selbst dann beginnt, eine Anforderung für den Zugriff auf einen verfügbaren Speicherplatz zu bedienen, wenn eine vorausgehende Anforderung noch nicht bedient werden kann, da die Ziele der vorausgehenden Anforderung ein nicht verfügbarer Speicherplatz sind. Darüber hinaus wird ein Weg benötigt, der Leseanforderungen, die insbesondere in "Posted-Write"-Systemen, in denen die Prozessoren nicht darauf zu warten brauchen, dass ein Speicherschreibvorgang vollständig abgeschlossen ist, bevor sie zur nächsten Aufgabe übergehen, wichtiger als Schreibanforderungen sind, eine zusätzliche Priorität verleiht.

Die vorliegende Erfindung schafft ein Verfahren und eine Vorrichtung zum Erhöhen der Geschwindigkeit von Speicherteilsystemen durch Steuern der Reihenfolge, in der Speicherzugriffsanforderungen für die Bedienung geschedult werden.

Gemäß einer Ausführungsform der Erfindung wird ein Verfahren zum Umordnen mehrerer Speicherzugriffsanforderungen gemäß Anspruch 1 geschaffen.

Gemäß einer weiteren Ausführungsform der Erfindung enthält der Schritt des Auswählens einer Anforderung für den Zugriff auf den Speicher die Schritte des Feststellens, ob unter den mehreren Anforderungen eine Leseanforderung für den Zugriff auf einen verfügbaren Speicherplatz vorliegt, und wenn das der Fall ist, des Auswählens einer Leseanforderung für den Zugriff auf einen verfügbaren Speicherplatz; und wenn das nicht der Fall ist, des Auswählens einer Nichtleseanforderung für den Zugriff auf einen verfügbaren Speicherplatz.

Ein weiteres Verständnis des Wesens und der Vorteile der vorliegenden Erfindung kann anhand der verbleibenden Abschnitte der Beschreibung und der Zeichnungen realisiert werden.

1 ist ein Blockschaltplan eines Computersystems, in dem die vorliegende Erfindung verkörpert sein kann.

2A ist ein höherer Blockschaltplan, der eine Mehrprozessorausführungsform der vorliegenden Erfindung zeigt.

2B ist ein höherer Blockschaltplan, der eine Mehrprozessorausführungsform der vorliegenden Erfindung zeigt, die zwei parallel geschaltete Speicherbusse enthält.

3A ist ein schematisches Diagramm, das die Reihenfolge der angeforderten Speicheroperationen gemäß dem Stand der Technik veranschaulicht, die mit angeforderten Leseoperationen gezeigt sind.

3B ist ein schematisches Diagramm, das umfassend die Reihenfolge der angeforderten Speicheroperationen in der vorliegenden Erfindung veranschaulicht, die mit angeforderten Leseoperationen gezeigt sind.

4 ist ein Blockschaltplan einer Ausführungsform der vorliegenden Erfindung.

5 ist ein Ablaufplan, der das Anforderungs-Scheduling in Ausführungsformen der vorliegenden Erfindung veranschaulicht.

6 ist ein Ablaufplan, der das Anforderungs-Scheduling in Ausführungsformen der vorliegenden Erfindung veranschaulicht, die das Lesen bevorzugen.

7 Ist ein Blockstromlaufplan, der eine Ausführungsform der vorliegenden Erfindung veranschaulicht.

8A und 8B sind Ablaufpläne, die das Anforderungs-Scheduling in dem Lese/Schreib-Scheduler aus 7 veranschaulichen.

9A, 9B und 9C sind Ablaufpläne, die die Lese/Schreib-Präferenzerzeugung in dem Präferenzgenerator aus 7 veranschaulichen.

Die vorliegende Erfindung ist auf das Steuern der Reihenfolge gerichtet, in der die angeforderten Speicheroperationen in einem Datenverarbeitungssystem geschedult werden.

1 ist ein vereinfachter Blockschaltplan eines Computersystems 101, in dem die vorliegende Erfindung verkörpert sein kann. Die auf dieser hohen Ebene veranschaulichte Computersystemkonfiguration ist Standard, so dass 1 als "Stand der Technik" bezeichnet ist. Allerdings ist ein Computersystem wie etwa das System 101, falls es die vorliegende Erfindung für das Management des Zugriffs auf den Speicher enthält, nicht Stand der Technik. In Übereinstimmung mit der bekannten Praxis enthält das Computersystem 101 einen oder mehrere Prozessoren 103, die über ein Busteilsystem 111 mit einer Anzahl von Peripherievorrichtungen kommunizieren. Diese Peripherievorrichtungen enthalten typisch Speicherteilsysteme wie etwa ein Schreib-Lese-Speicher-Teilsystem (RAM-Teilsystem) 107 und ein Plattenspeicherteilsystem 109, Eingabeeinrichtungen wie etwa eine Tastatur 104 oder eine Maus 105 und Ausgabeeinrichtungen wie etwa eine Anzeige 102. Weitere typische Peripherievorrichtungen, die nicht gezeigt sind, umfassen Drucker, Magnetbandspeicher-Teilsysteme, ferner vernetzte Server-Speicherteilsysteme usw.

Im vorliegenden Kontext wird der Begriff "Busteilsystem" allgemein in der Weise verwendet, dass er irgendeinen Mechanismus enthält, der ermöglicht, dass die verschiedenen Komponenten des Systems 101 bei Bedarf miteinander kommunizieren. Obgleich das Busteilsystem 111 schematisch als ein einziger Bus gezeigt ist, enthält ein typisches Computersystem z. B. eine Anzahl von "Bussen" wie etwa einen Lokalbus, einen oder mehrere Erweiterungsbusse, serielle Anschlüsse, parallele Anschlüsse, Netzverbindungen usw. Im Allgemeinen brauchen die Komponenten des Computersystems 101 nicht am gleichen physikalischen Ort zu sein.

1 ist nur für einen Typ eines Datenverarbeitungssystems repräsentativ, das die vorliegende Erfindung verkörpert. Für den Durchschnittsfachmann auf dem Gebiet ist leicht sichtbar, dass für die Verkörperung der vorliegenden Erfindung viele Computersystemtypen und -konfigurationen geeignet sind.

2A ist ein Blockschaltplan, der eine Mehrprozessorausführungsform 201 der vorliegenden Erfindung zeigt. Das Datenverarbeitungssystem 201 enthält eine Anzahl von Prozessoren P1–P4, die jeweils mit 203, 204, 205 und 206 bezeichnet sind. Die Prozessoren sind mit einem Speicherbus 215 gekoppelt. Der Speicherbus 215 ist über eine Anforderungsumordnungseinheit 214 mit einem Speicherteilsystem 216 gekoppelt.

Die Prozessoren P1–P4 erzeugen auf dem Speicherbus 215 Anforderungen für das Speicherteilsystem 216. Die Anforderungsumordnungseinheit 214 nimmt die Anforderungen von dem Speicherbus 215 an und schedult die Anforderungen, wie unten beschrieben wird, gemäß den Techniken der vorliegenden Erfindung. In einigen Ausführungsformen ist der Speicherbus 215 ein Intel-P6-Bus; ist die Anzahl der Prozessoren vier oder weniger; und sind die Prozessoren Intel-Pentium-Pro-kompatible Prozessoren.

2B ist ein Blockschaltplan, der eine Mehrprozessorausführungsform der vorliegenden Erfindung zeigt, die zwei parallel geschaltete Speicherbusse enthält. Das Datenverarbeitungssystem 202 enthält eine Anzahl von Prozessoren P1–P8, die jeweils mit 223, 224, ... und 230 bezeichnet sind. Die Prozessoren P1–P4 sind mit einem ersten Speicherbus 211 gekoppelt. Die Prozessoren P5–P8 sind mit einem zweiten Speicherbus 212 gekoppelt. Die zwei Speicherbusse 211 und 212 sind durch eine Steuereinheit/einen Kreuzschienenschalter 213, der das Schalten zwischen den zwei Bussen und einem dritten Bus 215 ausführt, parallel geschaltet. Der dritte Bus 215 ist über eine Anforderungsumordnungseinheit 214 mit einem Speicherteilsystem 216 gekoppelt. Die Busse 211, 212 und 215 können als zu einem Busteilsystem gehörend betrachtet werden.

Die Steuereinheit/der Kreuzschienenschalter 213 führt Kohärenzprüfungs- und Lenkungsanweisungen aus, die erforderlich sind, um Operationen von einem der Busse 211 und 212 zum anderen widerzuspiegeln. Die Prozessoren P1–P4 erzeugen auf dem ersten Speicherbus 211 Anforderungen für das Speicherteilsystem 216. Die Prozessoren P5–P8 erzeugen auf dem zweiten Speicherbus 212 Anforderungen für das Speicherteilsystem 216. Die Steuereinheit/der Kreuzschienenschalter 213 lenkt Speicheranforderungen von den zwei Speicherbussen 211 und 212 zu dem dritten Bus 215. Die Anforderungsumordnungseinheit 214 empfängt Anforderungen von dem dritten Bus 215 und schedult die Anforderungen gemäß den Techniken der vorliegenden Erfindung, wie sie unten beschrieben werden. In einigen Ausführungsformen sind die Speicherbusse 211 und 212 jeweils Intel-P6-Busse; ist die Anzahl der Prozessoren, die mit jedem Speicherbus gekoppelt sind, vier oder weniger und sind die Prozessoren Intel-Pentium-Prokompatible Prozessoren.

3A ist ein schematisches Diagramm, das das Ordnen der angeforderten Speicheroperationen gemäß dem Stand der Technik veranschaulicht, wie es im Hintergrundabschnitt diskutiert worden ist. Lediglich zur Einfachheit der Veranschaulichung sind alle gezeigten angeforderten Operationen Leseoperationen. In 3A werden mehrere angeforderte Speicheroperationen 303, die jeweils eine Zielspeicheradresse enthalten, durch einen Abschnitt 301 eines Datenverarbeitungssystems an ein Speicherteilsystem 216 übergeben. Die Anforderungen/Speicheradressen haben die Reihenfolge A110, A104, A99, A50, A2 und A1 und sind jeweils mit 305, 306, ... und 310 bezeichnet.

Das Speicherteilsystem 216 beginnt, jede anforderte Operation der Reihe nach auszuführen. Falls die Zielspeicheradresse einer angeforderten Operation verfügbar ist, beginnt das Speicherteilsystem 216, die angeforderte Operation auszuführen. Falls das nicht der Fall ist, wartet das Speicherteilsystem darauf, dass die Zielspeicheradresse verfügbar wird. In Situationen wie etwa den im Hintergrundabschnitt beschriebenen, in denen ansonsten damit begonnen werden hätte können, eine nachfolgend angeforderten Operation zu bedienen, die eine verfügbare Adresse zum Ziel hat, kann dieses Warten verschwenderisch sein.

Die durch die angeforderten Operationen 303 angeforderten Daten werden in einer Reihenfolge 312, die der Reihenfolge der angeforderten Operationen 303 entspricht, zurückgegeben 322. In diesem Beispiel ist die Reihenfolge 312 der Daten D110, D104, D99, D50, D2 und D1, wobei sie jeweils mit 315, 316, ... und 320 bezeichnet sind.

3B ist ein schematisches Diagramm, das umfassend das Umordnen der angeforderten Speicheroperationen in der vorliegenden Erfindung veranschaulicht. Lediglich zur Vereinfachung der Veranschaulichung sind alle gezeigten angeforderten Operationen Leseoperationen. In 3B sind mehrere angeforderte Operationen 303, die jeweils eine Zielspeicheradresse enthalten, durch einen Abschnitt 301 eines Datenverarbeitungssystems dargestellt.

Die Anforderungen/Speicheradressen 303 haben eine Anfangsreihenfolge A110, A104, A99, A50, A2 und A1 und sind jeweils mit 305, 306, ... und 310 bezeichnet. Diese angeforderten Operationen werden in Übereinstimmung mit einer neuen Reihenfolge 311 zur nachfolgenden Ausführung an ein Speicherteilsystem 216 übergeben 323. Das Umordnen wird gemäß unten diskutierten Techniken ausgeführt, um das Warten in dem Speicherteilsystem 216, das dadurch veranlasst wird, dass Zieladressen nicht verfügbar sind, zu minimieren. In diesem Beispiel wird die Reihenfolge der Anforderungen/Adressen zu einer Reihenfolge A99, A110, A1, A104, A2 und A50 optimiert 311.

Die Daten werden in der optimierten Reihenfolge D99, D110, D1, D104, D2 und D50 aus dem Speicherteilsystem 216 gelesen 324. Daraufhin werden diese Daten in einer Reihenfolge 312 D110, D104, D99, D50, D2 und D1, wobei sie jeweils mit 315, 316, ... 320 bezeichnet sind, umgeordnet 313. Die umgeordnete Datenreihenfolge entspricht der Anfangsanforderungsreihenfolge. Die umgeordneten Daten werden zurückgegeben 322. Da die Daten in Übereinstimmung mit der Anfangsanforderungsreihenfolge zurückgegeben werden 322, brauchen Entitäten, z. B. nicht gezeigte Prozessoren, die Speicheroperationen anfordern, die Reihenfolge, in der die angeforderten Operationen durch das Speicherteilsystem 216 tatsächlich ausgeführt wurden, nicht zu kennen.

In 3B wurden zur Erleichterung der Veranschaulichung lediglich angeforderte Leseoperationen gezeigt. Im Allgemeinen können die angeforderten Operationen auch Schreiboperationen sein. Die Daten für Schreibvorgänge müssen zusammen mit den Schreib-Anforderungen/Adressen selbst umgeordnet werden.

Im Allgemeinen sollten Maßnahmen ergriffen werden, um die Situation zu verhindern, dass ein angeforderter Schreibvorgang, auf den ein angeforderter Lesevorgang zu derselben Adresse folgt, umgeordnet wird, so dass der Lesevorgang vor dem Schreibvorgang ausgeführt wird. Eine solche Umordnung sollte vermieten werden, da sie veranlassen würde, dass der Lesevorgang falsche Daten zurückgibt. Ein Weg, um die falsche Umordnung zu verhindern, ist, den Abschnitt 301 des Systems keine Schreibanforderungen ausgeben zu lassen, auf die Leseanforderungen folgen, bis abgeleitet werden kann, dass die Schreibanforderung bereits geschedult worden ist. Ein weiterer Weg ist zuzulassen, dass der Abschnitt 301 des Systems ohne Beschränkung Anforderungen ausgibt, und daraufhin die Situation während des Umordnungsprozesses selbst aktiv verhindert. Beim letzteren Weg brauchen Entitäten, z. B. nicht gezeigte Prozessoren, die die Speicheroperationen anfordern, überhaupt nicht zu wissen, dass eine Umordnung stattfindet.

4 ist ein Funktionsblockschaltplan eines Datenverarbeitungssystems 401 gemäß der vorliegenden Erfindung. Ein Abschnitt 301 des Systems gibt Speicherzugriffsanforderungen 303 und "W"-Daten 403, die bestimmten der Anforderungen 303 zugeordnet sind, aus. Die "W"-Daten sind Daten, die einer angeforderten Speicheroperation bzw. angeforderten Speicheroperationen zugeordnet sind, die an einen Speicherplatz bzw. an Speicherplätze zu schreibende Daten enthalten. Die Anforderungen 303 und die "W"-Daten 403 können z. B. von einem (nicht gezeigten) Busteilsystem in dem Abschnitt 301 des Datenverarbeitungssystems ausgegeben werden, wobei das Busteilsystem dem Busteilsystem 111 aus 1 entspricht.

Eine Adressenumordnungs-Teileinheit 311 innerhalb einer Anforderungsumordnungseinheit 214 empfängt die Anforderungen 303 und speichert sie vorübergehend in einem Puffer. In Ausführungsformen der Erfindung empfängt die Adressenumordnungs-Teileinheit 311 die Anforderungen 303 über einen optionalen Kollisionsdetektor 404. Die Anforderungen 303 können beim Eintritt in die Adressenumordnungs-Teileinheit 311 eine Anfangsreihenfolge besitzen. Die Adressenumordnungs-Teileinheit 311 übergibt die Anforderungen gemäß unten diskutierten Techniken in einer neuen Reihenfolge 408 der Anforderungen an ein Speicherteilsystem 216.

Eine erste Datenumordnungs-Teileinheit 406 innerhalb der Anforderungsumordnungseinheit 214 empfängt die "W"-Daten 403. Die erste Datenumordnungs-Teileinheit 406 übergibt die "W"-Daten in einer neuen Reihenfolge 410 der "W"-Daten in Übereinstimmung mit der Anordnung von der Adressenumordnungs-Teileinheit 311 an das Speicherteilsystem 216. Die neue Reihenfolge 410 der "W"-Daten 403 entspricht der neuen Reihenfolge 408 der Anforderungen 303.

Das Speicherteilsystem 216 erfüllt die Anforderungen und gibt irgendwelche resultierenden "R"-Daten 412 an die Anforderungsumordnungseinheit 214 zurück. Die "R"-Daten sind Daten, die sich aus einer angeforderten Speicheroperation bzw. aus angeforderten Speicheroperationen ergeben, einschließlich Daten, die vom Zielspeicherplatz bzw. von Zielspeicherplätzen gelesen werden.

Eine zweite Datenumordnungs-Teileinheit 313 empfängt innerhalb der Anforderungsumordnungseinheit 214 die "R"-Daten und gibt sie an den Abschnitt 301 des Datenverarbeitungssystems zurück 414. Falls die Anforderungen 303 eine Anfangsreihenfolge besaßen, stellt die zweite Datenumordnungs-Teileinheit 313 für die "R"-Daten 412 die Reihenfolge wieder her, bevor sie die "R"-Daten zurückgibt 414, wobei die wiederhergestellte Reihenfolge der Anfangsreihenfolge der Anforderungen 303 entspricht. In Ausführungsformen der vorliegenden Erfindung sind die zweite Datenumordnungs-Teileinheit 313 und die erste Datenumordnungs-Teileinheit 406 in einer einzigen Einheit implementiert, die in der Weise gekoppelt ist, dass sie eine Anweisung von der Adressenumordnungs-Teileinheit 311 empfängt.

Ausführungsformen der Erfindung aus 4 arbeiten typisch in einer andauernden dynamischen Laufzeitweise. Die Anforderungsumordnungseinheit 214 nimmt dynamisch neue Anforderungen und entsprechende "W"-Daten an. Die Anforderungsumordnungseinheit 214 übergibt in Übereinstimmung mit einer optimalen neuen Reihenfolge 408 für Anforderungen und 410 für entsprechende "W"-Daten dynamisch Anforderungen und entsprechende "W"-Daten an das Speicherteilsystem 216. Die Anforderungsumordnungseinheit 214 empfängt dynamisch Daten von dem Speicherteilsystem 216, ordnet sie um und gibt "R"-Daten zurück.

Der Kollisionsdetektor 404 einiger Ausführungsformen der vorliegenden Erfindung implementiert ein Verfahren, das sicherstellt, dass Lesevorgänge von einer Adresse erst geschehen, wenn irgendwelche früheren Schreibvorgänge zu dieser Adresse abgeschlossen worden sind. Dadurch, dass dies sichergestellt wird, verhindert der Kollisionsdetektor 404, dass das Umordnen der Anforderungen das oben diskutierte Problem des vorzeitigen und fehlerhaften Lesens von einer Adresse verursacht. Der Kollisionsdetektor 404 arbeitet wie im nächsten Absatz beschrieben, um von vornherein zu verhindern, dass Anforderungssequenzen, die das oben diskutierte Problem verursachen können, in die Adressenumordnungs-Teileinheit 311 eintreten. Weitere Möglichkeiten, um das Problem des vorzeitigen Lesens zu verhindern, sind anhand der Lehren hierin sichtbar. In Ausführungsformen der Erfindung, die den Kollisionsdetektor 404 nicht besitzen, könnte z. B. die Adressenumordnungs-Teileinheit 311 selbst die Anforderungssequenzen überwachen und verhindern, dass die Reihenfolge einer Schreibanforderung, auf die eine Leseanforderung zu derselben Adresse folgt, umgekehrt wird.

In dem Kollisionsdetektor 404 werden die Zieladressen ankommender Leseanforderungen mit den Adressen aller in der Adressenumordnungs-Teileinheit 311 wartender Schreibanforderungen abgeglichen. Falls eine Leseanforderung mit einer der Schreibanforderungsadressen zusammenfällt, wird diese Leseanforderung blockiert, um zu verhindern, dass sie in die Adressenumordnungs-Teileinheit 311 eintritt. Wenn die zusammenfallende Schreibanforderung schließlich die Adressenumordnungs-Teileinheit 311 auf dem Weg zu dem Speicherteilsystem 216 verlässt, verschwindet die "Kollision", wobei zugelassen wird, dass die Leseanforderung in die Adressenumordnungs-Teileinheit 311 eintritt.

Beim Eintritt in die Anforderungsumordnungseinheit 214 können die Anforderungen Standardprioritäten haben, die eine Anfangsreihenfolge der Anforderungen definieren. Die vorliegende Erfindung weist den Anforderungen durch Festsetzen einer neuen Reihenfolge der Anforderungen neue Prioritäten zu. Jenen Anforderungen, die momentan verfügbare Adressen zum Ziel haben, wird eine hohe Priorität zugewiesen.

Die Standardanforderungsprioritäten können durch beliebige Kriterien oder durch heuristische Vorschriften festgestellt werden. In einer Ausführungsform der Erfindung werden ältere Anforderungen als solche mit höherer Priorität als neuere Anforderungen definiert. Das Alter einer Anforderung kann z. B. durch die Zeit, zu der die Anforderung ausgegeben wurde, durch die Zeit, zu der die Anforderung empfangen wurde, oder durch einen der Anforderung zugeordneten Zeitstempel festgestellt werden. In einer weiteren Ausführungsform der Erfindung wird die Standardpriorität durch ein der Anforderung zugeordnetes Prioritätsfeld festgestellt. Außerdem kann die Standardpriorität durch die Identität der Entität, zum Beispiel des Prozessors, der die Anforderung ursprünglich erzeugt hat, beeinflusst sein.

In Ausführungsformen der vorliegenden Erfindung ist die Anforderungsumordnungseinheit 214 in Software implementiert, die in einem Prozessor auszuführen ist. In Ausführungsformen der vorliegenden Erfindung ist die Software in einem Computerprogrammprodukt gespeichert, das ein computerlesbares Speichermedium enthält. Computerlesbare Speichermedien umfassen Nur-Lese-Speicher (ROM), programmierbare Nur-Lese-Speicher (PROM), eine CD-ROM, eine Festplatte usw. In Ausführungsformen der vorliegenden Erfindung ist die Anforderungsumordnungseinheit 214 durch Software konfigurierbar.

5 ist ein Ablaufplan, der die Anforderungsordnung in der Adressenumordnungs-Teileinheit 311 gemäß Ausführungsformen der vorliegenden Erfindung veranschaulicht. 5 wird unter weiterer Bezugnahme auf 4 diskutiert. In den Ausführungsformen gemäß 5 stellt die Adressenumordnungs-Teileinheit 311 in Schritt 502 fest, ob eine Anforderung der in der Umordnungs-Teileinheit 311 gepufferten Anforderungen eine verfügbare Adresse zum Ziel hat. Wenn das der Fall ist 503, schedult die Umordnungs-Teileinheit 311 in Schritt 504 eine solche Anforderung in der neuen Reihenfolge 408 und veranlasst sie, dass die Datenumordnungs-Teileinheit 406 irgendwelche entsprechenden "W"-Daten dementsprechend schedult 410. In Schritt 504 wird die geschedulte Anforderung aus der Adressenumordnungs-Teileinheit 311 entfernt. In einer bevorzugten Ausführungsform der Erfindung schedult die Adressenumordnungs-Teileinheit in Schritt 504 eine Anforderung, die unter den Anforderungen, die verfügbare Adressen zum Ziel haben, die höchste Priorität besitzt.

Das Scheduling einer Anforderung bedeutet, dass die Anforderung in eine Warteschlange von Anforderungen zur Lieferung an das Speicherteilsystem 216 eingereiht wird. In einer bevorzugten Ausführungsform der Erfindung ist die Länge der Warteschlange null, wobei Anforderungen an das Speicherteilsystem 216 übergeben werden, sobald sie geschedult werden.

In Ausführungsformen der Erfindung enthält das Speicherteilsystem Speicherbänke, wobei eine Speicheradresse verfügbar ist, wenn die Bank verfügbar ist, in der sie vorliegt. In Ausführungsformen der Erfindung enthält das Speicherteilsystem Speicherbänke mit verschachtelten Adressen, wobei eine Speicheradresse verfügbar ist, wenn die Bank verfügbar ist, in der sie vorliegt. Die vorliegende Erfindung ist besonders geeignet, um die Zugriffe auf Speicherteilsysteme zu steuern, die Speicherbänke enthalten. Außerdem ist die vorliegende Erfindung besonders geeignet, um die Zugriffe auf Speicherteilsysteme zu steuern, die Speicherbänke mit verschachtelten Adressen enthalten. Außerdem ist die vorliegende Erfindung besonders geeignet, um die Zugriffe auf die Speicherteilsysteme zu steuern, die Halbleiterspeicherteilsysteme oder Speicherteilsysteme mit ähnlicher oder höherer Geschwindigkeit sind.

6A ist ein Ablaufplan, der das Anforderungs-Scheduling in Ausführungsformen der vorliegenden Erfindung veranschaulicht, die Leseanforderungen gegenüber Schreibanforderungen bevorzugen. Wie im Hintergrundabschnitt diskutiert worden ist, ist es besonders wichtig, Leseanforderungen so schnell wie möglich zu behandeln, da eine Leseanforderung angibt, dass ein anfordernder Prozessor möglicherweise auf Daten wartet. Somit ist eine Leseanforderung eine kritischere Anforderung als andere Operationen, z. B. eine Schreiboperation. 6A wird mit weiterem Bezug auf 4 diskutiert.

In den Ausführungen gemäß 6A stellt die Adressenumordnungs-Teileinheit 311 in Schritt 610 zuerst fest, ob eine Leseanforderung der in der Umordnungs-Teileinheit 311 gepufferten Anforderungen eine verfügbare Adresse zum Ziel hat. Wenn das der Fall ist 611, schedult die Adressenumordnungs-Teileinheit 311 in Schritt 612 diese Leseanforderung in der neuen Reihenfolge 408. In einer bevorzugten Ausführungsform der Erfindung schedult die Adressenumordnungs-Teileinheit in Schritt 612 eine Anforderung, die die höchste Standardpriorität unter den Leseanforderungen besitzt, die verfügbare Adressen zum Ziel haben. In Schritt 612 wird die geschedulte Leseanforderung aus der Umordnungs-Teileinheit 311 entfernt.

Falls in Schritt 610 festgestellt wird, dass keine Leseanforderung in der Umordnungs-Teileinheit 311 eine verfügbare Adresse zum Ziel hat 613, stellt die Umordnungs-Teileinheit 311 in Schritt 614 fest, ob eine Schreibanforderung der Anforderungen in der Umordnungs-Teileinheit 311 eine verfügbare Adresse zum Ziel hat. Wenn das der Fall ist 616, schedult die Adressenumordnungs-Teileinheit 311 in Schritt 618 diese Schreibanforderung in der neuen Reihenfolge 408 und veranlasst, dass die Datenumordnungs-Teileinheit 406 irgendwelche entsprechenden "W"-Daten dementsprechend schedult 410. In einer bevorzugten Ausführungsform der Erfindung schedult die Adressenumordnungs-Teileinheit in Schritt 618 eine Anforderung, die die höchste Standardpriorität unter den Schreibanforderungen besitzt, die verfügbare Adressen zum Ziel haben. In Schritt 618 wird die geschedulte Schreibanforderung aus der Umordnungs-Teileinheit 311 entfernt.

In vielen Speicherteilsystemen kann eine Schreibanforderung wegen der potentiellen Buskonkurrenz in dem Speicherteilsystem zwischen den in das Speicherteilsystem eintretenden Schreibdaten und den in dem Speicherteilsystem vorliegenden Lesedaten nicht sofort geschedult werden, nachdem eine Leseanforderung geschedult worden ist. Wenn die vorliegende Erfindung zum Steuern des Zugriffs auf diese Speicherteilsysteme verwendet wird, sollte diese mögliche Konkurrenz berücksichtigt werden. Ein Weg, um eine mögliche Konkurrenz zu verhindern, besteht darin, den Schritt 614 zu ändern, so dass nicht nur gefragt wird, ob eine Schreibanforderung vorliegt, die eine verfügbare Adresse zum Ziel hat, sondern auch, ob der Schreib-Datenweg leer ist. Zum Beispiel kann festgestellt werden, dass der Schreibdatenweg leer ist, wenn die zuvor geschedulte Anforderung keine Leseanforderung war oder wenn zwischen der Ausführungszeit der zuvor geschedulten Anforderung und der der besagten Schreibanforderung ein ausreichendes Zeitintervall sichergestellt worden ist. Die Schreibanforderung wird nur dann in Schritt 618 geschedult, wenn eine Schreibanforderung vorliegt und der Schreibweg leer ist 616.

In Speicherteilsystemen, wie sie im vorangehenden Absatz beschrieben worden sind, geht während Busübergaben oder schnellen Übergängen von der Behandlung einer Leseanforderung zur Behandlung einer Schreibanforderung Zeit verloren. Um die Menge der verlorenen Zeit zu verringern, enthalten Ausführungsformen der vorliegenden Erfindung nach dem Schritt 618 den optionalen Burst-Schreibschritt 620, um Busübergaben zu minimieren. Der Burst-Schreibschritt 620 implementiert das Verhalten, dass, wenn in Schritt 618 eine Schreibanforderung geschedult wird, in Schritt 620 ein Burst von Schreibanforderungen nacheinander geschedult wird. In diesem Sinn sind Schreibanforderungen eine "burstfähige" Operation, da sie Nutzen daraus ziehen, sie miteinander zu gruppieren.

6B ist ein Ablaufplan, der den Burst-Schreibschritt aus 6A veranschaulicht. 6B ist zum größten Teil selbsterklärend. Wie zu sehen ist, werden die Schreibanforderungen an verfügbare Adressen in Schritt 622 geschedult, bis entweder 624 keine weiteren Schreibanforderungen vorliegen, die verfügbare Adressen zum Ziel haben, oder 626 eine vorgegebene Anzahl X von Schreibanforderungen in dem momentanen Burst geschedult worden sind und eine Leseanforderung vorliegt, die eine verfügbare Adresse zum Ziel hat. In einer Ausführungsform der vorliegenden Erfindung wird die Anzahl X anhand von Systemanforderungen eingestellt. In einer bevorzugten Ausführungsform der vorliegenden Erfindung ist die Anzahl X programmierbar. Zum Beispiel könnte der Wert von X durch ein Softwareprogramm, durch DIP-Schalter oder dergleichen in einem Register gespeichert werden. In einer Ausführungsform der Erfindung mit acht Intel-Pentium-Pro-Prozessoren, wie sie in 2B gezeigt ist, ist festgestellt worden, dass ein Wert von vier für X gut funktioniert.

7 ist ein Blockstromlaufplan, der eine Ausführungsform 701 der vorliegenden Erfindung veranschaulicht, die Anforderungen an ein verschachteltes Mehrbank-Speichersystem steuert. In 7 sendet ein Bus 111 Speicheranforderungen an das Eingangsende 705 eines Schiebepuffers, das Anforderungspuffer 703 genannt wird.

Der Anforderungspuffer 703 besitzt eine Anzahl von Elementen wie etwa ein Element 705, die jeweils eine Anforderung speichern können. In einer Acht-Pentium-Pro-Prozessor-Ausführungsform der vorliegenden Erfindung ist festgestellt worden, dass ein Puffer mit acht Elementen geeignet ist. Innerhalb eines Elements wird eine Anforderung als ein "Typ" 707, eine "ID" 709 und eine "Bank" 711 gespeichert. Ein Anforderungstyp 707 kann die Werte "Lesen" oder "Schreiben" annehmen. Eine Anforderungs-ID 709 spezifiziert die Zieladresse der Anforderung. In einer Ausführungsform der Erfindung ist eine Anforderungs-ID nicht selbst eine Adresse, sondern ein Index, d. h. ein Zeiger, auf einen (nicht gezeigten) Adressenpuffer, der Adressen hält. Eine Anforderungsbank 711 ist die Speicherbank, zu der die Zieladresse gehört. Außerdem enthält jedes Element ein "Gültig"-Bit 713, das besagt, ob dieses Element momentan eine Anforderung enthält.

Der Anforderungspuffer 703 ist in der Weise gekoppelt, dass er von einer Speichersteuereinheit 715 Informationen empfängt, die angeben, welche Speicherbänke momentan für Lesevorgänge 717 oder für Schreibvorgänge 719 verfügbar sind. Der Anforderungspuffer stellt anhand der Informationen darüber, welche Bänke verfügbar sind, fest, welche der Anforderungen verfügbare Adressen zum Ziel haben. Der Anforderungspuffer 703 übergibt 721 alle Leseanforderungen, die verfügbare Adressen zum Ziel haben, an einen Lese-MUX 723. Der Anforderungspuffer 703 übergibt 725 alle Schreibanforderungen, die verfügbare Adressen zum Ziel haben, an einen Schreib-MUX 727.

Der Lese-MUX 723 übergibt die älteste Leseanforderung 729 der Leseanforderungen 721 mit verfügbarem Ziel an einen Lese/Schreib-Scheduler 731. Außerdem erzeugt der Lese-MUX 723 einen "Lesen-verfügbar"-Merker 735, der das Vorliegen der ältesten Leseanforderung 729 mit verfügbarem Ziel angibt. Der Lese/Schreib-Scheduler 731 und ein Präferenzgenerator 737 empfangen den "Lesen-verfügbar"-Merker 735.

Der Schreib-MUX 727 übergibt die älteste Schreibanforderung 733 der Schreibanforderungen 725 mit verfügbarem Ziel an den Lese/Schreib-Scheduler 731. Außerdem erzeugt der Schreib-MUX 727 einen "Schreiben-verfügbar"-Merker, der das Vorliegen der ältesten Schreibanforderung 733 mit verfügbarem Ziel angibt. Der Lese/Schreib-Scheduler 731 und der Präferenzgenerator 737 empfangen den "Schreiben-verfügbar"-Merker 739.

Der Lese/Schreib-Scheduler 731 und der Präferenzgenerator 737 implementieren zusammen die Umordnungsvorschriften der Ausführungsform 701. Auf einer hohen Ebene sind die Umordnungsvorschriften der Ausführungsform 701 wie oben in Verbindung mit den 6 und 6B beschrieben.

Wie unten beschrieben wird, stellt der Präferenzgenerator 737 eine momentane Präferenz 741 für Leseanforderungen oder eine momentane Präferenz 743 für Schreibanforderungen fest. Wie unten beschrieben wird, schedult 745 der Lese/Schreib-Scheduler 731 teilweise anhand der momentanen Präferenz entweder die älteste Leseanforderung 729 mit verfügbarem Ziel oder die älteste Schreibanforderung 733 mit verfügbarem Ziel. Wenn eine Anforderung geschedult worden ist 745, nimmt die Speichersteuereinheit 715 die Anforderung an, wobei der Präferenzgenerator 737 und eine Schiebesteuereinheit 751 davon in Kenntnis gesetzt werden, ob gerade eine Leseanforderung 747 oder eine Schreibanforderung 749 geschedult worden ist.

Die Schiebesteuereinheit 751 ist in der Weise gekoppelt, dass sie den Inhalt des Anforderungspuffers 703 kennt. Nachdem eine Anforderung geschedult worden ist, entfernt die Schiebesteuereinheit 751 diese Anforderung aus dem Anforderungspuffer 703. Hierfür führt die Schiebesteuereinheit 751 zwei Funktionen aus. Zunächst leitet die Schiebesteuereinheit 751 durch Identifizieren der ältesten Anforderung mit verfügbarem Ziel, die an den Typ der gerade geschedulten Anforderung (d. h. an den Lesetyp 747 oder an den Schreibtyp 749) angepasst worden ist, ab, welche Anforderungen diejenige war, die gerade geschedult worden ist. Zweitens weist die Schiebesteuereinheit 751 den Anforderungspuffer 703 an, alle Anforderungen, die um ein Element älter als die gerade geschedulte Anforderung sind, von dem Eingabeende 705 (d. h. von dem neueren Ende) des Anforderungspuffers 703 weg zu verschieben.

Wie oben erwähnt wurde, ist der Anforderungspuffer 703 als ein Schieberegister mit einem jüngeren Ende 705 und einem entgegengesetzten älteren Ende 706 konstruiert. Das Alter des Eintritts der Anforderungen in den Puffer 703 steigt von dem jüngeren Ende 705 zu dem älteren Ende 706 notwendig an. Der Ablauf innerhalb des Anforderungspuffers 703 wird unter Verwendung der folgernden Vorschriften für jedes Element X des Puffers gesteuert, die gleichzeitig auf alte Elemente angewendet werden. Die Wirkung dieser Vorschriften ist, dass der Anforderungspuffer 703 seinen Inhalt verschiebt, um nicht belegte Elemente zu füllen, wodurch die Verfügbarkeit jüngerer Elemente zum Füllen an dem jüngeren Eingangsende 705 maximiert wird.

Vorschrift 1: Falls das Element X oder ein älteres Element nicht verwendet wird, wird der Inhalt des Elements X durch den Inhalt des benachbarten jüngeren Elements ersetzt.

Vorschrift 2: Falls geschedult wird, dass das Element X oder ein älteres Element in das Speichersystem geht, wird der Inhalt des Elements X durch den Inhalt des benachbarten jüngeren Elements ersetzt.

Vorschrift 3: Falls die Bedingungen sowohl der Vorschrift 1 als auch der Vorschrift 2 falsch sind, bleibt der Inhalt des Elements X ungeändert.

Da die Ausführungsform 701 so entworfen ist, dass sie mit einem in 7 nicht gezeigten Kollisionsdetektor 404 arbeitet, nimmt die Ausführungsform 701 an, dass auf keine aktive Schreibanforderung zu einer Adresse eine aktive Leseanforderung zu derselben Adresse folgt. Durch Hinzufügen einer Kollisionsfeststellungslogik zu dem Anforderungspuffer 703 kann die Ausführungsform 701 geändert werden, so dass sie die Annahme nicht macht.

8A ist ein Ablaufplan, der das Anforderungs-Scheduling in dem Lese/Schreib-Scheduler 731 aus 7 ausgehend von einer momentanen Präferenz für Lesevorgänge 741 veranschaulicht. In 8A wird eine älteste Leseanforderung geschedult 801, falls sie eine verfügbare Adresse 803 zum Ziel hat. Andernfalls 805 wird eine älteste Schreibanforderung geschedult 807, die eine verfügbare Adresse 809 zum Ziel hat, falls ausreichend Zeit vergangen ist 811, seit die vorausgehende Schreibanforderung geschedult worden ist, damit der Schreibweg leer ist.

8B ist ein Ablaufplan, der das Anforderungs-Scheduling in dem Lese/Schreib-Scheduler 731 aus 7 ausgehend von einer momentanen Präferenz für Schreibvorgänge 743 veranschaulicht. In 8B wird eine älteste Schreibanforderung geschedult 821, falls sie eine verfügbare Adresse 823 zum Ziel hat. Andernfalls 825 wird eine älteste Leseanforderung geschedult 827, die eine verfügbare Adresse 829 zum Ziel hat.

Die 9A, 9B und 9C sind Ablaufpläne, die die Lese/Schreib-Präferenzerzeugung in dem Präferenzgenerator 737 aus 7 veranschaulichen. Wie aus 9A zu sehen ist, wird eine momentane Präferenz für Lesevorgänge 741 genau dann in eine Präferenz für Schreibvorgänge geändert 907, 913, wenn keine Leseanforderung mit verfügbarem Ziel vorliegt 905, aber eine Schreibanforderung mit verfügbarem Ziel vorliegt 909. Bei Bedarf 910, 912 wartet 915 der Präferenzgenerator, bevor er eine momentane Präferenz für Schreibvorgänge festsetzt 913. Das Warten soll einen leeren Schreibweg sicherstellen, indem ausreichend Zeit verstreichen gelassen wird 911, nachdem eine vorangehende Leseanforderung geschedult worden ist. Während des Wartens ist weder eine Präferenz für Schreibvorgänge noch eine Präferenz für Lesevorgänge aktiviert – d. h., die Präferenz ist unbestimmt.

Wie aus 9C zu sehen ist, bleibt eine momentane Präferenz für Schreibvorgänge 743, nachdem sie aktiviert worden ist, aktiviert 917, bis entweder keine Schreibanforderung mit verfügbarem Ziel vorliegt 919 oder eine vorgegebene Anzahl X von Schreibvorgängen sukzessive geschrieben worden ist 921. In einer Acht-Pentium-Pro-Ausführungsform der vorliegenden Erfindung ist festgestellt worden, dass ein Wert von vier für X gut funktioniert.

Obgleich das Obige eine vollständige Beschreibung spezifischer Ausführungsformen der Erfindung ist, können verschiedene Änderungen, alternative Konstruktionen und Entsprechungen verwendet werden.


Anspruch[de]
  1. Verfahren zum Umordnen mehrerer Speicherzugriffsanforderungen (303), die in einer bestimmten Reihenfolge in einem Datenverarbeitungssystem (101, 201, 202, 401) empfangen werden, wobei das Verfahren die folgenden Schritte umfasst:

    Annehmen mehrerer Anforderungen (303),

    Halten der mehreren Anforderungen (303) in einem Anforderungspuffer (103),

    Auswählen einer Anforderung zum Zugreifen auf einen Speicherplatz aus den mehreren Anforderungen entsprechend einem Auswahlschema, wobei die ausgewählte Anforderung nicht die nächste in der Reihenfolge ist, und

    Scheduling der ausgewählten Anforderung,

    gekennzeichnet durch

    Feststellen (502) der Nichtverfügbarkeit des Speicherplatzes aufgrund eines Speicherzugriffs oder der Verfügbarkeit des Speicherplatzes für einen Speicherzugriff und

    Auswählen (504) der Anforderung entsprechend dem Auswahlschema, falls die Verfügbarkeit des Speicherplatzes festgestellt wird (503).
  2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass der Schritt des Auswählens einer Anforderung einen Schritt des Auswählens (801) einer ältesten Anforderung der mehreren Anforderungen (303), die einen Zugriff auf einen verfügbaren Speicherplatz (803) anfordert, umfasst.
  3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass der Schritt des Auswählens einer Anforderung die folgenden Schritte umfasst:

    Feststellen (610), ob unter den mehreren Anforderungen (303) eine Leseanforderung zum Zugreifen auf einen verfügbaren Speicherplatz vorliegt,

    Auswählen (612) einer Leseanforderung für den Zugriff auf einen verfügbaren Speicherplatz, falls im Feststellungsschritt festgestellt wird, dass eine solche Leseanforderung vorhanden ist (611), und

    Auswählen (618) einer Nichtleseanforderung für den Zugriff auf einen verfügbaren Speicherplatz, falls im Feststellungsschritt (610) festgestellt wird, dass eine Leseanforderung für den Zugriff auf einen verfügbaren Platz nicht vorhanden ist (613).
  4. Verfahren nach Anspruch 3, gekennzeichnet durch:

    Feststellen (616), ob die ausgewählte Anforderung eine Schreibanforderung ist, und,

    nach dem Schritt des Scheduling der ausgewählten Anforderung, sukzessives Scheduling (620) wenigstens einer Schreibanforderung aus den mehreren Anforderungen, falls für die ausgewählte Anforderung festgestellt wird, dass sie eine Schreibanforderung ist.
  5. Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass wenigstens eine der mehreren Anforderungen (303) einen Rücksprungwert erzeugt, wobei das Verfahren ferner die folgenden Schritte umfasst:

    Sammeln von Rücksprungwerten von Anforderungen der mehreren Anforderungen, und

    Umordnen der gesammelten Rücksprungwerte in Übereinstimmung mit einer ursprünglichen Reihenfolge der mehreren Anforderungen.
  6. Verfahren nach einem der Ansprüche 1 bis 5, gekennzeichnet durch einen Schritt des Erfassens, ob die mehreren Anforderungen eine Leseanforderung und eine Schreibanforderung für denselben Speicherplatz enthalten.
  7. Verfahren nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, dass jeder Speicherplatz einer von mehreren Speicherbänken zugeordnet ist und der Schritt des Auswählens einer Anforderung die folgenden Schritte umfasst:

    Identifizieren eines Speicherplatzes, für den von einer der mehreren Anforderungen (303) ein Zugriff angefordert wird,

    Identifizieren einer der mehreren Speicherbänke, der der identifizierte Speicherplatz entspricht, und

    Feststellen, ob die identifizierte Speicherbank verfügbar ist.
  8. Datenverarbeitungssystem (101, 201, 202, 401), mit:

    einem Anforderungspuffer (703), der mehrere Speicherzugriffsanforderungen (303), die er in einer bestimmten Reihenfolge empfangen hat, hält, und

    einer Anforderungsumordnungseinheit (214), die eine Speicherzugriffsanforderung zum Zugreifen auf einen Speicherplatz unter den mehreren Speicherzugriffsanforderungen (303) in Übereinstimmung mit einem Auswahlschema auswählt, wobei die ausgewählte Anforderung nicht die nächste in der Reihenfolge ist,

    gekennzeichnet durch

    eine Verfügbarkeitsfeststellungseinrichtung, die die durch einen Speicherzugriff bedingte Nichtverfügbarkeit eines Speicherplatzes, für den wenigstens einige der mehreren Speicherzugriffsanforderungen (303) einen Zugriff begehren, oder die Verfügbarkeit des Speicherplatzes für einen Speicherzugriff feststellt,

    und dadurch, dass die Anforderungsumordnungseinheit (214) so entworfen ist, dass sie einen verfügbaren Speicherplatz in Reaktion auf die Verfügbarkeitsfeststellungseinrichtung auswählt (504).
  9. System nach Anspruch 8, dadurch gekennzeichnet, dass die Anforderungsumordnungseinheit (214) so beschaffen ist, dass sie eine älteste Anforderung der mehreren Anforderungen (303), die einen Zugriff auf einen verfügbaren Speicherplatz (803) anfordert, auswählt (801).
  10. System nach Anspruch 8 oder 9, dadurch gekennzeichnet, dass die Anforderungsumordnungseinheit (214) umfasst:

    eine Leseanforderungs-Identifizierungseinrichtung, die in Reaktion auf die Verfügbarkeitsfeststellungseinrichtung eine Leseanforderung für den Zugriff auf einen verfügbaren Speicherplatz identifiziert, falls eine solche Leseanforderung vorhanden ist,

    eine Nichtleseanforderungs-Identifizierungseinrichtung, die in Reaktion auf die Verfügbarkeitsfeststellungseinrichtung eine Nichtleseanforderung für den Zugriff auf einen verfügbaren Speicherplatz identifiziert, falls eine solche Nichtleseanforderung vorhanden ist, und

    eine Steuereinheit, die die identifizierte Leseanforderung auswählt (612), falls sie vorhanden ist (611), und andernfalls (613) die identifizierte Nichtleseanforderung auswählt (618).
  11. System nach Anspruch 10, dadurch gekennzeichnet, dass:

    die Steuereinheit so beschaffen ist, dass sie, falls die ausgewählte Anforderung eine Schreibanforderung ist, sukzessive wenigstens eine weitere Nichtleseanforderung für den Zugriff auf einen verfügbaren Speicherplatz aus den mehreren Anforderungen (303) auswählt (620), wobei die wenigstens eine Nichtleseanforderung dadurch einen Burst definiert.
  12. System nach einem der Ansprüche 8 bis 11, dadurch gekennzeichnet, dass wenigstens eine der mehreren Anforderungen (303) einen Rücksprungwert erzeugt, wobei das System ferner umfasst:

    eine Datenumordnungseinheit, die Rücksprungwerte der mehreren Anforderungen sammelt und die gesammelten Rücksprungwerte entsprechend einer ursprünglichen Reihenfolge der mehreren Anforderungen umordnet.
  13. System nach einem der Ansprüche 8 bis 12, dadurch gekennzeichnet, dass der Anforderungspuffer (703) so beschaffen ist, dass er in die mehreren Anforderungen neue Speicherzugriffsanforderungen (303) dynamisch aufnimmt.
  14. System nach einem der Ansprüche 8 bis 13, gekennzeichnet durch einen Kollisionsdetektor (404), der erfasst, wenn die neue Anforderung einen Zugriff auf denselben Speicherplatz anfordert, für den ein Zugriff durch eine Schreibanforderung in den mehreren Anforderungen (303) angefordert wird.
  15. System nach einem der Ansprüche 8 bis 14, dadurch gekennzeichnet, dass einige der mehreren Anforderungen (303) von Daten begleitet werden, wobei das System ferner umfasst:

    eine Datenumordnungseinheit (406), die in Reaktion auf die Anforderungsumordnungseinheit (214) beliebige Daten auswählt, die die ausgewählte Speicherzugriffsanforderung begleiten, wobei die ausgewählte Anforderung und begleitende Daten von einer Speichersteuereinheit empfangen werden müssen.
  16. System nach einem der Ansprüche 8 bis 15, dadurch gekennzeichnet, dass:

    jeder Speicherplatz einer von mehreren Speicherbänken zugeordnet ist, und

    die Verfügbarkeitsfeststellungseinrichtung mit einer Speichersteuereinheit gekoppelt ist, die angibt, ob eine Speicherbank verfügbar ist.
  17. System nach einem der Ansprüche 8 bis 16, gekennzeichnet durch:

    wenigstens einen Prozessor (103, 203206, 223230), der Programme ausführt und wenigstens einige der mehreren Speicherzugriffsanforderungen (303) ausgibt,

    ein Speichersystem, das Speicherplätze enthält, und

    eine Speichersteuereinheit, die die ausgewählte Speicherzugriffsanforderung für die Ausführung durch das Speichersystem empfängt.
Es folgen 11 Blatt Zeichnungen






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com