DE3854035T2

DE3854035T2 - Nichtperiodisches Abbildungsverfahren zum verbesserten Zweierpotenzzugriff für ineinandergreifende Einrichtungen.

Info

Publication number: DE3854035T2
Application number: DE3854035T
Authority: DE
Inventors: Kevin Patrik Mcauliffe; Evelyn Au Melton; Vern Alan Norton; Gregory Francis Pfister; Scott Philip Wakefield
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1987-10-29
Filing date: 1988-09-15
Publication date: 1996-02-29
Anticipated expiration: 2008-09-16
Also published as: EP0313788A2; EP0313788A3; DE3854035D1; EP0313788B1; JPH065512B2; JPH01116850A; US5111389A

Description

Die Europäische Patentanmeldung EP-A-0-313 787 (E. Melton et al.), die am gleichen Tage eingereicht wurde wie die vorliegende Anmeldung, betitelt "A hardware mechanism for the dynamic customization of permutation using bit-matrix multiplication" offenbart einen Permutationsmechanismus, der die Speicher- oder Gerätbandbreite nach Kundenwunsch vergrößert durch erhöhte Flexibilität einer Bitmatrix Multiplikations- Permutationsfunktion in Hardware für eine spezifische Operationsumgebung, ohne Veränderungen der physikalischen Hardware vorauszusetzen.
Der Typ der Bitmatrix Multiplikations-Permutationsfunktion ist der gleiche, wie er im allgemeinen in der vorliegenden Erfindung offenbart wird. Zusätzlich wird auch die Entwicklung anderer Matrizen nach Kundenwunsch beschrieben. Die Hardware dieser Anwendung läßt es zu, daß die verschiedenen Matrizen leicht in das Matrix-Speichermedium übertragen werden, wobei der sich ergebende Permutationsmechanismus für eine bestimmte Anwendung nach Kundenwunsch ausgelegt ist, sei es, daß sich der Kundenwunsch auf das Datenzugriffsverhalten der Anwendung oder auf sonstige kritische Operationsforderungen bezieht.
Die Europäische Patentanmeldung 85 113 174.8 mit dem Titel "Dynamically allocated local/global storage system" offenbart ein hochparalleles Verarbeitungssystem mit einem großen, verschachtelten, gemeinsam benutzten Speichersystem , in dem die einzelnen Speichermodule auf die verschiedenen Prozessoren verteilt sind. Ein Verkoppelungsnetzwerk ist vorgesehen zusammen mit einem geeigneten Speicherverwaltungsmittel, so daß jeder Prozessor leicht auf jedes Modul im System Zugriff hat. Ferner laßt die Systemarchitektur den gleichzeitigen Zugriff auf alle Module zu, vorausgesetzt natürlich, daß es keinen Konflikt gibt, so wie wenn z.B. mehr als ein Prozessor auf ein bestimmtes Speichermodul zugreifen will. Das derzeitige Speichertransformationsverfahren, das so ausgelegt ist, daß solche Konflikte vermieden oder minimiert werden, wäre beim Speicherverwaltungsgerät eines solchen Speichersystems besonders nützlich.
Die vorliegende Erfindung betrifft im allgemeinen das Gebiet der multiplen Systemelementverwaltung in einem elektronischen Datenverarbeitungssystem. Im einzelnen betrifft es die wirksame Anwendung aller solcher Systemelemente in jedem Augenblick während der Datenverarbeitung. Genauer gesagt betrifft es eine Eins-zu-Eins-Abbildung logischer Adressen auf physikalische Adressen in z.B. einem großen gemeinsam benutzten, verschachtelten Speichersystem in einer hochparallelen Verarbeitungsumgebung.
In vielen modernen Hochleistungsrechnersystemen wird eine vergrößerte Bandbreite für Speicher- und E/A-Geräte erreicht durch die Anwendung multipler, verschachtelter Geräte. Verschachtelung ist ein Weg, um viele Zugriffe ungefähr zur gleichen Zeit zuzulassen. Betrachten wir n = 2d Geräte D&sub0;,D&sub2;, ..., Dn-1. Durch Anwendung der Verschachtelung werden die Inhalte der Adresse m in Dq gespeichert, wobei q = mod(m,n) ist. Durch Verschachtelung auf diese Weise können bis zu n Bezugnahmen gleichzeitig befriedigt werden, insbesondere wenn sich diese Bezugnahmen auf nacheinanderfolgende Speicheradressen beziehen. Das ist besonders vorteilhaft in hochparallelen, gemeinsam benutzten Speichersystemen, wenn viele Prozessoren gleichzeitig auf nacheinanderfolgende Adressen arbeiten.
In dieser Situation kommt es zu Problemen, wenn die Adressen nicht nacheinanderfolgen, sondern mit einem Schritt t vorkommen, so daß t und n einen gemeinsamen Faktor haben, d.i., GGT(t,n) > 1. Betrachten wir z.B. die Adressenfolge mit Schritt kn (wobei k ≥ 1, und k &epsi;I) gegeben durch a, a + kn, a + 2kn, a + 3kn, ..., a + (n - 1)kn, für eine beliebige Anfangsadresse a. Wenn die obige Verschachtelung benutzt wird, werden alle diese Bezugnahmen an das gleiche Gerät Dmod(a,n) adressiert. Solche Schrittzugriffe kommen häufig vor bei Anwenderprogrammen, z.B. bei Zugriffen auf Reihen oder Spalten in Matrizen. Diese Leistungsbeeinträchtigung, die aus solchen schrittweisen Zugriffen entsteht, wird noch verstärkt, wenn eine sehr große Anzahl Prozessoren vorhanden ist, und kann bei solcher Hardware zu einer größeren Vereinzelbarkeit führen.
In der nachfolgenden Diskussion wird auf Veröffentlichungen auf dem Stand der Technik auf herkömmliche Weise durch Erwähnung in eckigen Klammern [ ] Bezug genommen. Eine Liste dieser Veröffentlichungen wird nach diesem Abschnitt angegeben.
Das Problem der Nichteinheitlichkeit des Speicherzugriffs ist bei hochparallelen Systemen ein ernstes Problem, weil solche "Heißstellen" im Speicher zu einer "Baumblockade" [1] führen können: Netzwerk- sowie Speicherüberlappungen können die Leistung des Gesamtsystems auf eine Höhe reduzieren, die von dem sich überlappenden Gerät bestimmt wird. Solche Systeme sind besonders empfindlich gegen Zweierpotenzschritt- Zugriffsüberlappungen, weil diese Bezugnahmen üblicherweise unter den Geräten verschachtelt sind und in Feldern in Binärdarstellung ihrer physikalischen Adressen durch das Verbindungsnetz geführt werden.
In einem SIMD-Parallelsystem, wie z.B. ILLIAC IV [2], können Speicherzugriffskonflikte bewirken, daß alle Prozessoren auf den letzten Speicherzugriff der Paralleloperation warten. Aus diesem Grund wurde viel Arbeit in Entwürfe gesteckt, die die Überlappung, die mit dem schrittweisen Zugriff verbunden ist, eliminieren oder reduzieren.
Speicherorganisationen, die einen konfliktfreien Zugriff für jede Reihe, Spalte, Vorwärts- und Rückwärtsdiagonale einer Anwendungsmatrix-Anordnung vorsehen, wurden für ILLIAC IV [2], STAAAN [3] und BSP [4] Rechner untersucht. In den meisten dieser Abhandlungen wird auf Matrizen in einer deterministischen, für eine synchronisierte SIMD-Maschine konfliktfreien Weise zugegriffen.
In [2] schlagen Budnik und Kuck, und in [4] Lawrie und Vora Hardware- und Softwarelösungen vor, die eine Primzahl an Speichermodulen voraussetzen. In [6] schlägt Lawrie ein System mit M Speichermodulen vor, bei dem M = 2N, wobei N die Anzahl der Verarbeitungsknoten ist. Alle diese Lösungen sollen bewirken, daß M und der Schrittzugriff relativ prim sind. Batcher [3] und Frailong, Jalby und Lenfant [7] benutzen Bitversatzdarstellungen, die EXKLUSIV-ODER-Operationen an Indizes einer Matrixanordnung ausführen, um sie auf individuelle Speichereinheiten abzubilden. Wijshoff und Leeuwen in [8], und Shapiro in [9], untersuchen die mathematischen und theoretischen Grenzen für solche Bitversatzdarstellungen.
Von Lawrie [6] wurden ferner Ausrichtnetzwerke untersucht, um auf der Grundlage von Stones [10] Umordnungsaustauschoperation eine alternative Lösung für das Herstellen teuerer N x M Koordinatenschalter für den Zugriff und das Abspeichern ordentlich ausgerichteter Daten zu finden. Andere, wie z.B. Lenfant [11], entwarfen Steuermustermatrizen für ein Schaltverbindungsnetzwerk, das die dynamische Datenpermutation zuläßt.
Alle diese Pläne sind mit größeren Nachteilen behaftet. Da sie in erster Linie für besondere Zwecke entworfen wurden und eine eingebaute Abhängigkeit von den Matrizengrößen und der Anzahl der Speichermodule haben, sind sie für allgemeine Rechnerumgebungen nicht brauchbar, die die unterschiedlichsten Vorgaben berücksichtigen müssen. Zusätzlich erfordern einige dieser Entwürfe teuere und komplizierte Adressier- und Ausrichthardware für Modulo-Operationen und Ganzzahldivisionen. Schließlich können auch Löcher im Adressierraum, die durch diese Verfahren erzeugt werden, zu allzu geringer Inanspruchnahme von Speicherraum führen.

LITERATURHINWEISE

[1] Pfister, G.F., Norton, V.A. "Hot Spot Contention and Combining in Multistage Interconnection Networks", IEEE Trans on Comp, C-34, Nr. 10, Okt. 1985, S. 943-948.
[2] Budnik, P., Kuck, D.J., "The Organization and Use of Parallel Memories", IEEE Trans on Computers, Dez. 1971, S. 1566-1569.
[3] Batcher, K.E., "The Multidimensional Access Memory in STARAN", IEEE Trans on Comp, Feb. 1977, S. 174-177.
[4] Lawrie, D.H., und Vora, C.R., "The Prime Memory System for Array Access", IEEE Trans on Comp, C-31, Nr. 5, Mai 1982, S. 435-442.
[5] Kuck, D.J., "ILLIAC IV Software and Application Programming", IEEE Trans on Comp, Bd. C-17, Aug. 1968, S. 758-770.
[6] Lawrie, D.H., "Access and Alignment of Data in an Array Processor", IEEE Trans on Comp, Bd. C-24, Nr. 12, Dez. 1975, S. 1145-1150.
[7] Frailong, J.M., Lenfant, J., "XOR-Schemes: A Flexible Data Organization in Parallel Memories", Proceedings, Internat Conf on Parallel Processing, Aug. 1985, S. 276-283.
[8] Wijshoff, H.A., Leeuwen, J., "The Structure of Periodic Storage Schemes for Parallel Memories", IEEE Trans on Comp, Bd. C-34, Nr. 6, Juni 1985, S. 501-505.
[9] Shapiro, H.D., "Theoretical Limitations on the Efficient Use of Parallel Memories", IEEE Trans on Comp, Bd. C-27, Nr. 5, Mai 1978, S. 421-428.
[10] Stone, H.S., "Parallel Processing with the Perfect Shuffle", IEEE Trans Comp, Bd. C-20, Feb. 1971, S. 153-161.
[11] Lenfant, J., "Parallel Permutations of Data: A Benes Network Control Algorithm for Frequently Used Permutations", IEEE Trans Comp, Bd. C-27, Nr. 7, Juli 1978, S. 637-647.
[12] Pfister, G.F., Brantley, W.C., George, D.A., Harvey S.L., Kleinfelder, W.J., McAuliffe, K.P., Melton, E.A., Norton, V.A. und Weiss, J., "The IBM Research Parallel Processor Prototype (RP3) : Introduction and Architecture", Proceedings, Internat Conf on Parallel Processing, 1985, S. 764-771.
[13] Brooks, E.D., "Performance of the Butterfly Processor- Memory Interconnection in a Vector Environment", Proceedings, Internat Conf on Parallel Processing, 1985, S. 21-25.
[14] Mandelbrot, B.B., "The Fractal Geometry of Nature", W.H. Freeman and Company, N.Y. 1983.
Zusätzlich zu den oben angezogenen Veröffentlichungen stellt das folgende eine Diskussion des zusätzlichen Kenntnisstandes dar, der den Erfindern bekannt ist und für die vorliegende Erfindung als relevant angesehen wird, jedoch gegenüber der vorliegenden Erfindung nicht vorveröffentlicht ist.
US Patent 4,484,262 von Sullivan et al. offenbart einen Speicherverwalter in der Form eines Zufallszahlengenerators, um Adressen zu "zerhacken", die an alle ihm zugeordneten Speichermodule geschickt werden. Dieser Speicherverwalter kann entweder als eine Zentralprozedur oder als eine Prozedurhierarchie implementiert werden. Im letzteren Fall muß, wenn die Prozedur im System verteilt wird, eine Art Koordination möglich sein, damit verhindert wird, daß unterschiedliche logische Adressen sich in die gleiche physikalische Adresse auflösen. Es erfordert eine beträchtliche Menge Hardware und zusätzlichen Platzbedarf (der letztere in der Form von durch ihren Netzwerk-Speicherverwalter vergrößerten Paketen), die in einem Rechnersystem implementiert werden müssen. Es ist eine sehr teuere Lösung zum Vergrößern der Speicherbandbreite für hochparallele Systeme. Wenn man die Systemkonfiguration und die Anzahl der Quellen und Speichereinheiten für ein hochparalleles Rechnersystem umändert, würde die im vorliegenden Patent vorgeschlagene Hardware einen vollkommenen Umbau erfordern, um wieder maßgerecht zu werden.
Der zugrundeliegende Adressentransformationsmechanismus der vorliegenden Erfindung ist so ausgelegt, daß er eine Permutation von Adressen für parallele Geräte vorsieht. Die Charakteristik einer solchen Matrix garantiert, daß unterschiedliche logische Adressen sich nicht in die gleiche physikalische Adresse auflösen. Zusätzlich ist die vorliegende Erfindung spezifisch dafür ausgelegt, daß Zugriffe in Zweierpotenzschritten gemacht werden, wo Daten sonst unter Verwendung sonstiger Verfahren der Tabelleneintragsuche oder Zufallszahlauflösung in Untergruppen der gesamten verfügbaren Speichermodule gruppiert werden.
In einem Artikel von R.N. Langmaid mit dem Titel " Versatile Programmable Logic Array", erschienen im IBM Technical Disclosure Bulletin, Bd. 25, Nr. 8, Januar 1983, S. 4445- 4449, ist eine logische Anordnung oder Matrix offenbart, die, wie angegeben, zur Tabelleneintragsuche benutzt werden kann einem Parallelverarbeitungsrechnersystem mit einer großen, gemeinsam benutzten, verschachtelten Speicherorganisation eingesetzt werden könnte.
Eine Anzahl weiterer Literaturstellen sind den Erfindern bekannt, können jedoch nur als Hintergrundinformationen angesehen werden. Die Mehrzahl von ihnen offenbart virtuelle Speichersysteme unter Verwendung von Tabelleneintragsuche in ihrer Adressenumsetzfunktion. Diese angezogenen US-Patentnummern sind nachstehend aufgelistet:
3,691,531 4,433,389
4,157,587 4,484,272
4,167,782 4,550,367
4,249,242 4,587,610
4,395,757 4,588,985
Die nachstehenden Literaturstellen offenbaren im allgemeinen eine Art Multiplikations- oder Logikmatrix, aber keine von ihnen offenbart oder regt eine Bitmatrix-Multiplikation oder die Anwendung derselben auf Speicherabbildungsverfahren an.
1. IBM Technical Disclosure Bulletin, Matyas et al., Bd. 24, Nr. 5, Oktober 1981, S. 2335-2336, mit dem Titel "Electronic Signature for Use with Data Encryption Standard".
2. IBM Technical Disclosure Bulletin, Lubold et al., Bd. 28, Nr. 2, Juli 1985, S. 603-604, mit dem Titel "Matrix Digital Signature for Use with the Data Encryption Algorithm".
3. IBM Technical Disclosure Bulletin, Anglin et al., Bd. 16, Nr. 7, Dezember 1973, S. 2223-2234, mit dem Titel "Information Retrieval Technique".
4. IBM Technical Disclosure Bulletin, Matyas et al., Bd. 24, Nr. 5, Oktober 1981, S. 2232-2234, mit dem Titel "Electronic Signature for Data Encryption Standard".
Hauptaufgabe der vorliegenden Erfindung ist die Bereitstellung eines aperiodischen Speicherabbildungsverfahrens zur Verbesserung der Bandbreite in Zweierpotenzschritt-Zugriffen auf verschachtelte, gemeinsam genutzte Speicher hochparalleler Verarbeitungssysteme.
Eine weitere Aufgabe der Erfindung ist die Bereitstellung eines solchen Verfahrens mit Nutzbarkeit in jedem beliebigen Rechnersystem mit einer großen Anzahl verschachtelter Geräte für wahlfreien Zugriff. Eine Vielzahl solcher gleichzeitig ansprechbarer Server beinhalten E/A-Geräte wie große DASD- Systeme, Speichermodule mit wahlfreiem Zugriff eines hochparallelen SIMD oder MIMD-Verarbeitungssystems, und natürlich sind alle hierarchischen Primär- und/oder Sekundärspeichersysteme mit wahlfreiem Zugriff hier anwendbar.
Eine weitere Aufgabe der Erfindung ist die Bereitstellung eines solchen Verfahrens, in dem eine jedem Speicherverwaltungssystem vorgestellte logische Adresse permutiert wird zu einer physikalischen Adresse mit dem globalen Effekt, daß die Anwendung individueller Speichermodule über das System jederzeit hochoptimiert wird, und insbesondere für logische Adressen, auf die in Zweierpotenzschritten zugegriffen wird.
Noch eine weitere Aufgabe der vorliegenden Erfindung ist die Bereitstellung eines solchen Verfahrens, in dem die Permutation eine Bitmatrix-Multiplikation einer logischen Adresse mit einer gegebenen Matrix beinhaltet, um eine einzigartige physikalische Adresse zu erzeugen.
Eine weitere Aufgabe der Erfindung ist die Bereitstellung eines solchen Verfahrens, in dem die im Permutationsverfahren benutzte Matrix die Merkmale aufweist, daß alle quadratischen Untermatrizen, aus denen die Matrix besteht, die entweder am oberen oder am rechten Rand der Matrix anliegen, invertierbar oder nichtsingulär sind.
Eine weitere Aufgabe der vorliegenden Erfindung ist die Bereitstellung eines solchen Verfahrens mit einer besonderen Anwendbarkeit in einem hochparallelen Verarbeitungssystem mit einem gemeinsam genutzten, verschachtelten Speicher.
Eine weitere Aufgabe der Erfindung ist die Bereitstellung eines solchen Verfahrens, in dem das hochparallele Verarbeitungssystem ferner dadurch gekennzeichnet ist, daß ebenso viele Frozessoren vorhanden sind wie verschachtelte Speichermodule, und in dem die Anzahl derselben eine Zweierpotenz ist.
Die Aufgaben der vorliegenden Erfindung werden im allgemeinen gelöst durch ein Verfahren zum Abbilden logischer Adressen auf physikalische Geräte einschließlich einer Familie von Adressenpermutationsmethoden oder -verfahren zur Verminderung der Überlappung, die schrittweisen Zugriffen auf verschachtelte Geräte zugeordnet sind. Diese Methoden ermöglichen gleichmäßige Zugriffe für jeden Zweierpotenzschritt, verursachen aber keine Überlappungsprobleme für andere schrittweisen Zugriffe. Sie gründen sich auf Transformationen, die über das Boolesche Feld GF(2) linear sind.
Das Verfahren ist anwendbar auf Primär- und/oder Sekundärspeichersysteme in SIMD- oder MIMD-Maschinen und kann Speicher-Heißpunktprobleme eliminieren, die beim Schrittzugriffsmuster einer Anwendung auftreten. Das hier beschriebene Verfahren läßt sich leicht in Hardware oder Software implementieren, und ein Verfahren zum Einbau solcher Transformationen in eine Speicherabbildungseinheit eines hochparallelen Verarbeitungssystems wird beschrieben. Während die vorliegende Erfindung weitgehend in großen, verschachtelten Speichersystemen mit wahlfreiem Zugriff Anwendung findet, läßt es sich auch bei großen E/A-Systemen einsetzen, wie Direktspeichergeräte, die einen schnellen Datenabruf für Anwendungen in einer Datenbank erfordern.
In den Zeichnungen,
Fig. 1 zeigt einen Signalflußplan eines hochparallelen Verarbeitungssystems mit einem gemeinsamen Speicher. Jedem Prozessor ist ein Modul zugeordnet, auf das über ein vielstufiges Verbindungsnetzwerk von allen anderen Prozessoren zugegriffen werden kann;
Fig. 2 zeigt einen Signalflußplan einer Adressentransformationseinheit, die die Grundsätze der vorliegenden Erfindung implementiert, die im System der Fig. 1 zur Anwendung kommen können;
Fig. 3 zeigt einen Signalflußplan einer geeigneten Hardware zur Ausführung der erfindungsgemäßen Bitmatrix-Multiplikation, wobei physikalische Speicheradressen unter Benutzung des Permutationsverfahrens der vorliegenden Erfindung aus einer anfänglichen, logischen Adresse abgeleitet werden;
Fig. 4 zeigt einen Signalflußplan eines Blocks zur Berechnung des Skalarprodukts gemäß Fig. 3;
Fig. 5 zeigt einen Signalflußplan eines Netzwerks mit invertierter Basislinie, wie sie als mehrstufiges Verbindungsnetzwerk im Parallelverarbeitungssystem mit einem gemeinsamen Speicher der Fig. 1 eingesetzt werden kann, wobei die Anwendung desselben eindeutig die Vorteile der vorliegenden Erfindung zeigt;
Fig. 6 ist ein Graph, der die drei verschiedenen Methoden der Verschachtelung zeigt: Die Matrix-Multiplikationsmethode gemäß der vorliegenden Erfindung, eine einfache Verschachtelung ohne Tabelleneintragsuche, und eine reine Zufallsfunktion. Der Graph ist aufgetragen mit einem Schritt von log&sub2; in der x-Achse und der Maximalzahl von Kollisionen (d.i. maximale Gesamtzugriffszahl für jedes Speichermodul) in der y-Achse. Die im gezeigten Experiment benutzten Schrittzugriffe sind in verschiedenen Zweierpotenzen erfolgt;
Fig. 7 ist ein Graph, der die einfache Verschachtelungsmethode und die gleiche reine Zufallsfunktion wie Fig. 6 vergleicht. Der Graph ist aufgetragen mit den Schritten in der x-Achse, und mit der Maximalzahl Kollisionen (d.i. Maximum der totalen Zugriffe auf jedes Speichermodul) in der y-Achse. Die in diesem Versuch benutzten Schrittzugriffe gehen von 1 bis 100; und
Fig 8 ist ein Graph, der die erfindungsgemäße Matrixmultiplikationsmethode und die gleiche reine Zufallsfunktion wie in Fig. 6 vergleicht. Der Graph ist aufgetragen mit dem Schritt in der x-Achse und der Maximumanzahl Kollisionen (d.i. Maximum der Gesamtzugriffe auf jedes Speichermodul) in der y- Achse. Die in diesem Versuch benutzten Schrittzugriffe gehen von 1 bis 100.
Das hier vorgeschlagene Verfahren überwindet viele der Nachteile des Speicherverwaltungssystems auf dem Stand der Technik, das bekannte Tabelleneintragssuchtechniken anwendet, um eine verbesserte Adressenverteilung zu erreichen, besonders in großen verschachtelten Systemen, in denen man Zugriffe in Zweierpotenzschritten häufig antrifft. Die vorliegende Methode permutiert einen Adressenraum durch Anwendung einer Booleschen (oder binären) Matrixmultiplikation. Es wird eindeutig gezeigt, daß Matrizen so gewählt werden können, daß sie Überlappungen beim Zweierpotenzschritt- Zugriff in Systemen eliminieren, bei denen die Anzahl der Geräte eine Zweierpotenz ist. Eine solche Speicherabbildung kann z.B. benutzt werden, um die dem Speicherzugriff in parallelen, schnellen, Wurzel-zwei Fouriertransformationen zugeordneten Überlappungen auszuschließen. Obwohl diese Technik im besonderen zum Eliminieren von Netzwerk- und Speicherüberlappungsproblemen für alle Zugriffe in Zweierpotenzschritten dient, ruft sie keine übermäßigen Überlappungsprobleme für alle sonstigen Zugriffe in Nicht- Zweierpotenzschritten hervor.
Der Leistungsgewinn ist am größten bei synchronen Systemen, wie z.B. SIND-Maschinen, wo das Verfahren alle Überlappungen bei Zweierpotenzschrittzugriffen auf Reihen- und Spalten eliminieren kann, die eine ernstliche Engstelle wären. Bei asynchronen MIMD-Systemen oder bei E/A-Zugriffen mag die Verbesserung weniger dramatisch sein, ist aber ausreichend zum Eliminieren einer Leistungsverschlechterung aufgrund des schrittweisen Zugriffs.
Die beschriebene Methode läßt sich wirksam in Hardware implementieren und ist geeignet zum Einschluß in die Speicherabbildungs- oder Adressierungs-Hardware der einzelnen Prozessoren in ein paralleles System. Diese Hardware ist in der RP3 Konstruktion [12] aufgenommen, wie in einem späteren Abschnitt noch beschrieben wird. Es ist vorteilhaft, eine solche Hardware als Systemfunktion des Seitenumsetzmechanismus in die Konstruktion der Verarbeitungselemente für eine Mehrfachprozessorumgebung aufzunehmen.
Als erstes soll die allgemeine Methode zum Erreichen eines verbesserten Zugriffs in Zweierpotenzschritten beschrieben werden. Eine algebraische Bedingung wird abgeleitet und wird als hinreichend zum Eliminieren der Konflikte beim Zugriff in Zweierpotenzschritten auf den Speicher bewiesen. Eine Variante dieser Bedingung wird als hinreichend zum Eliminieren auch von Netzwerkkonflikten bewiesen. Verfahren werden angegeben für die Konstruktion von Bit-Matrizen, die den angegebenen Bedingungen genügen. Ergebnisse einer Leistungsanalyse werden für eine solche Matrix dargestellt, die die Zugriffskonflikte zeigen, die den verschiedenen Schritten zugeordnet sind. Schließlich wird gezeigt, wie diese Methode als Teil des Hardware-Adressenverschiebungsmechanismus entweder in Hardware oder in Software in großen, gemeinsamen, verschachtelten Speichersystemen wie z.B. in dem oben angezogenen experimentellen System RP3 implementiert werden kann.
Eine Boolesche r x s Matrix ist eine rechteckige Anordnung von Binärbits, die in r Reihen und s Spalten aufgetragen sind. Solche Matrizen beschreiben lineare Abbildungen aus dem Vektorraum Fs von Bit-s-tupeln auf den Raum Fr von Bit-r- tupeln. Das sind Vektorräume über dem Feld F = GF(2) aus zwei Elementen,{0,1}. Hier ist anzumerken, daß die Addition und Multiplikation in diesem Feld entsprechend die logischen (Booleschen) Operationen "EXKLUSIV-ODER" und "UND" sind.
Die lineare Transformation einer Multiplikation einer Booleschen Matrix M = (mij) mal einem Booleschen s x 1 Vektor V wird genau so ausgeführt, wie man Ganzzahl-Matrizen multipliziert: Das i-te Element des Produkts MV ist das "Punkt"- Produkt der i-ten Reihe von M mit dem Vektor V. Dieses Punktprodukt ist die Summe (EXKLUSIV-ODER) der s Bits, die durch Multiplizieren (UNDEN) jedes Eintrags mij mit vj erhalten werden.
Die hier beschriebene Methode benutzt die Boolesche Matrixmultiplikation, um eine Permutation auf einen Adressenraum anzuwenden. Wenn die Matrix M eine quadratische invertierbare s x s Matrix ist, definiert die Multiplikation mit M eine Permutation an Bit-s-tupeln. Durch Betrachten der s-Bit Adressen als s-Vektoren definieren wir somit eine Permutationsabbildung auf einen Raum aus 2s Adressen.
Für den größten Teil dieser Diskussion werden diese Adressen als Speicheradressen betrachtet, und die Matrixmultiplikation wird für eine Abbildung logischer Adressen auf physikalische Adressen angewandt. Diese gleiche Methode gilt jedoch auch für das Adressieren verschiedener anderer physikalischer Geräte wie z.B. Direktzugriffs-Speichermedien oder Hochgeschwindigkeits-Plattenantriebe mit wahlfreiem Zugriff.
Zwecks größerer Deutlichkeit wird ein System mit 2d physikalischen Geräte angenommen. Die physikalischen Adressen in diesem System bestehen aus s Bits (wobei d < s ist) . Die ersten d Bits identifizieren die Gerätnummer und die letzten s - d Bits identifizieren die verschiedenen Adressen innerhalb eines Geräts. Eine logische Adresse wird als ein s x 1 Vektor definiert. Das niedrigstwertige Bit einer Adresse ist das letzte ("Boden") Element in der Bit-Kette, und das höchstwertige Bit ist das erste ("Kopf") Element in der Bit- Kette.
Jetzt sollen die algebraischen Vorgaben beschrieben werden, die die Wirkung einer Matrix auf einen gegebenen Zweierpotenzschritt hat. Der konfliktfreie Zugriff mit einem Schritt 2t wird für einige Ganzzahlen t ≥ 0 über die 2d physikalischen Geräte gewünscht. Optimal sollten aufeinanderfolgende Verweise auf unterschiedliche Geräte gemacht werden, wobei keine Gerät zweimal angesprochen werden darf, bis alle der 2d Geräte jeweils einmal angesprochen wurden. Das bedeutet, daß die 2d Adressen 0, 2t, 2 x 2t, 3 x 2t, ... , (2d-1) x 2t jeweils auf unterschiedliche physikalische Geräte abgebildet werden müssen.
Die oben beschriebene Adressenfolge bildet einen linearen Teilraum S des Adressenraums, wenn der logische Adressenraum als Boolescher Vektorraum FS über dem Feld F aufgefaßt wird.
Damit dieser Raum gleichmäßig über die physikalischen Speichergeräte verteilt abgebildet werden kann, werden die ersten d Reihen der Matrix M betrachtet, weil diese Reihen das einer logischen Adresse zugeordnete physikalische Gerät bestimmen. M' sei die d x m Matrix, die aus den ersten d Reihen von M besteht.
Die Abbildung des Teilraums S auf physikalische Geräte wird bestimmt durch die d x d Untermatrix von M', bestehend aus d nebeneinanderliegenden Spalten von M', Spalten s - t - d + 1, s - t - d + 2, ..., s - t, für einen Schritt 2t. Wenn diese Untermatrix einen maximalen Rang (Rang = d) aufweist, dann läßt sich der Teilraum S auf 2d unterschiedliche Geräte abbilden. Sonst wird S auf einen kleineren Teilraum Fd abgebildet, der auf 2k Speichermodule für k ≤ d - 1 abgebildet wird.
Wenn verschiedene Zweierpotenzschritte 2t, t = 0, 1, 2 ..., betrachtet werden, muß die folgende Bedingung einen solchen Schrittzugriff als einheitlichen Zugriff auf die 2d Geräte bewirken:
* (A) Alle d x d Untermatrizen, die aus d aufeinanderfolgenden Spalten M' bestehen, sind nichtsingulär, wobei eine Matrix als nichtsingulär definiert wird, dann und nur dann wenn ihre Determinante nicht Null ist oder die Matrix invertierbar ist.
Eine Matrix ist als nichtsingulär definiert, dann und nur dann wenn ihre Determinante nicht Null ist oder die Matrix invertierbar ist.
Hier wird angemerkt, daß Bedingung (A) aus der tYberlegung abgeleitet wurde, daß die 2d aufeinanderfolgenden Zweierpotenzschritt-Zugriffe gerade mit der Adresse 0 beginnen. Sie bedeutet keinen gleichmäßigen Zugriff von anderen Anfangsadressen aus. Wenn jedoch die 2d Zugriffe von einer anderen Adresse a aus anfangen, ist die Auswirkung fast genauso gut: Die 2d Zugriffe werden keine Geräte mehr als zweimal ansprechen. Hier ist zu bemerken, daß die Abbildung M konfliktfrei ist, nicht nur auf S, sondern auch auf jede Nebenmenge a S von S. Wenn ein Schrittzugriff bei a ≠ 0 beginnt, dann wird er höchstens 2 solche Nebenmengen schneiden, nämlich a S und (a + 2t+d) S, wobei die logische bitweise EXKLUSIV-ODER-Operation bedeutet.
Als Beispiel für eine Matrix, die die Bedingung (A) erfüllt, siehe Tabelle 1. TABELLE I Eine 4 x 8 Matrix, die der Bedingung (A) genügt.
Die obige Bedingung (A) impliziert eine eingeschränkte Speicherüberlappung unter einem Zweierpotenzschritt-Zugriff. In vielen parallelen Systemen kann auch eine Überlappung zwischen Prozessoren und Speicher gefunden werden. Betrachten wir z.B. das invertierte Basislinien-Netzwerk, das in Fig. 5 abgebildet ist. Damit ein Prozessor ein Speichermodul ansprechen kann, muß er eine Meldung durch das Netzwerk an das bestimmte Modul schicken. Auch wenn zwei Meldungen zu zwei unterschiedlichen Bestimmungsorten unterwegs sind, können sie auf dem Weg zu ihren Bestimmungsorten in einem Schalter "kollidieren". Auch solche Konflikte lassen sich durch die geeignete Wahl einer Adressentransformationsmatrix eliminieren oder reduzieren.
Ein invertiertes Basislinien-Netzwerk, wie in Fig. 5 dargestellt, wird benutzt, um zu zeigen, wie eine geeignete Matrix gewählt werden kann; andere Netzwerke mögen ähnlich ausgewählte Matrizen benutzen. Merken wir an, daß der einzige Weg von einem Prozessor zum Speicher gegeben ist durch einen Satz binärer Wahlmöglichkeiten, die unterwegs an den verschiedenen Schaltern getroffen werden müssen. Ferner hängen die für diesen Weg zu benutzenden Bits ausschließlich vom Bestimmungsspeichermodul ab, nicht vom aussendenden Prozessor, auch wenn die Leitwegpfade unterschiedlich sein können.
Wenn im Netzwerk Zweierpotenzschritt-Zugriffskonflikte eliminiert werden sollen, genügt es, sicherzustellen, daß auf die verschiedenen Leitwege zum Speicher gleichmäßig zugegriffen werden kann. Zu diesem Zweck werden die verschiedenen Speichermodule gemäß dem Leitweg, durch den auf sie zugegriffen wird, numeriert: Das erste (höchstwertige) Bit ist das Leitwegbit für die erste Netzwerkstufe; das zweite Bit ist das Leitwegbit für die zweite Stufe, usw. Daraus ergibt sich die Speichernumerierung gemäß Fig. 5. Gemäß dem benutzten physikalischen Adressierungsplan sind das auch die höchstwertigen Bits der physikalischen Adressen der Speicherorte.
Nehmen wir jetzt an, daß die Bedingung (A) erfüllt ist, nicht nur für jede 2d quadratische Untermatrix von M', sondern auch für Untermatrizen der Größe 2j für alle j ≤ d. Mit anderen Worten,
* (B) Jede quadratische Untermatrix von M', die oben an M' angrenzt, ist nichtsingulär.
Diese Bedingung (B) impliziert dann, daß jeder Zweierpotenzschritt-Zugriff, anfangend von einer beliebigen Adresse a, so daß S Λ a = 0, einen gleichmäßigen Zugriff zu jedem beliebigen Teilraum des physikalischen Adressenraumes gibt, der durch die ersten j Bits der Adresse definiert wird, wobei Λ die logische, bitweise UND-Operation ist. Ein Beispiel einer Matrix, die der Bedingung (B) genügt, ist in Tabelle 2 gegeben. TABELLE 2 Eine 9 x 29 Matrix, die der Bedingung (B) genügt.
Mit Hilfe dieser Tatsache wird gezeigt, daß, wenn alle Prozessoren gleichzeitig auf hintereinanderliegende Elemente mit dem gleichen Schritt zugreifen (Prozessor Nr. i greift auf Datum i x 21 zu), dann gibt es keinen Konflikt im Netzwerk oder beim Speicher.
Weiterhin wird angenommen, daß von einem invertierten Basisliniennetzwerk mit d Stufen von Zwei-zu-Zwei-Schaltern auf 2d Speichermodule zugegriffen wird.
Betrachten wir einen beliebigen Schalter in der ersten Stufe des Netzwerks. Die Ausgänge aus diesem Schalter werden vom höchstwertigen Bit der Adresse angesprochen. Weil die Bedingung (A) für die erste Reihe der Matrix erfüllt ist, ist daraus zu schließen, daß die zwei Bezugspunkte in diesem Schalter, die an die Datenfelder i x 2¹ und (i + 1)2¹ adressiert sind, sich notwendigerweise in diesem Bit unterscheiden müssen.
Nehmen wir auf ähnliche Weise an, daß auf Stufe k des Netzwerkes 2d Meldungen gleichzeitig an den Eingängen der verschiedenen Schalter ankommen. Betrachten wir jetzt die ersten 2k Schalter dieser Stufe. Weil auf Reihe k (bei k ≤ d) der Matrix die Bedingung (B) anwendbar ist, sieht man, daß die 2k an dieser Reihe ankommenden Bezugspunkte notwendigerweise ohne Überlappung an unterschiedliche Ausgänge geführt werden müssen. Ein ähnliches Argument gilt für die nachfolgende Gruppen von 2k Schalter in der Reihe k. Daraus darf geschlossen werden, daß die gesamten 2d Bezugspunkte konfliktfrei durch das Netzwerk laufen.
Auch wenn der schrittweise Zugriff zum Netzwerk nicht perfekt synchronisiert ist (wie in der obigen Beweisführung angenommen war), gibt es doch wesentliche Vorteile bei diesem Verfahren. Es wurde beobachtet [13], daß leichte Synchronisationsfehler im Schritt-eins-Vektorzugriff durch die Überlappungsverzögerungen in solchen Netzwerken ausgeglichen werden. Es ist anzunehmen, daß ein ähnlicher Vorteil auch beim Zweierpotenzschritt-Zugriff auftritt, wenn eine Matrixspeicherabbildung benutzt wird, die der Bedingung (B) genügt.
Die oben beschriebenen Kriterien (A) und (B) zum Bestimmen geeigneter Boolescher Matrizen sind sehr wichtig, weil sie die charakteristischen Merkmale solcher Matrizen liefern. Jetzt soll ein allgemeines Verfahren zum Aufbau aller Matrizen, die der Bedingung (B) genügen, beschrieben werden.
Theorem: Gegeben sei eine Matrix mit d Reihen und s Spalten, dann existiert eine Matrix M, die der Bedingung (B) genügt. Wenn man nämlich eine freie Wahl Unterdiagonalbits {mij i > j} zuläßt, gibt es eine eindeutige Boolesche Matrix M, die diese Unterdiagonalelemente aufweist und (B) erfüllt.
Beweis: Um Matrizen zu erhalten, die (B) erfüllen, führe man einen induktiven Beweis an den Reihen der Matrix durch. Sobald die ersten k Reihen, 1 ≤ k ≤ s - 1 so ausgewählt wurden, daß sie (B) erfüllen, kann jede beliebige Auswahl der übrigen s - k Reihen, die zu einer invertierbaren Matrix M führen, benutzt werden.
Die Anwendung der Bedingung (B) auf die erste Reihe impliziert, daß jedes Element in dieser Reihe 1 sein muß, da die Elemente eben dieser Reihe genau die 1 x 1 Untermatrizen sein müssen.
Nehmen wir jetzt an, daß die ersten k - 1 Reihen ausgewählt wurden, und daß alle (k - 1) x (k - 1) quadratischen Untermatrizen, die von nebeneinanderliegenden Spalten der sich ergebenden (k - 1) x s Matrix gebildet werden, invertierbar sind. Wählen wir beliebige k - 1 Werte (0 oder 1) für die ersten k - 1 Einträge in Reihe k. Dann gibt es einen Wert (entweder 0 oder 1) für das Element mkk, so daß die sich ergebende k x k Eckpunkt-Untermatrix nichtsingulär ist. Um das zu beweisen, erweitern wir die Determinante D für diese Untermatrix entlang ihrer untersten Reihe. Daraus entsteht wie folgt:
D = mk1Dk1 + mk2Dk2 + ... + mkkDkk
wobei im obigen Ausdruck Dij den Kofaktor des Elements mij darstellt.
Hier ist anzumerken, daß durch induktive Hypothese die Determinante Dkk nicht Null und daher 1 ist. Es ist jetzt möglich mkk zu wählen. Wenn die ersten k - 1 Terme sich zu Null addieren, ist mkk mit 1 gewählt; ansonsten wird mkk mit Null gewählt. In beiden Fällen kann die quadratische Eckpunkt- Untermatrix so gewählt werden, daß sie nichtsingulär ist.
Entlang der Reihe k fortschreitend kann das gleiche Argument angewandt werden, indem man immer mkl, l > k, wählt, so daß die quadratische Untermatrix mit mkl in ihrer rechten unteren Ecke invertierbar ist. Das schließt den Beweis ab.
Das obige Argument ergibt die Konstruktion aller Matrizen M, die der Bedingung (B) genügen. Für jede Reihe k der Matrix M ist es möglich, die ersten k - 1 Bits zu wählen, und die restlichen Einträge in dieser Reihe sind bestimmt. Es gibt genau 2(d-1)d/2 Matrizen M von d Reihen, die (B) erfüllen.
Eine dieser Matrizen, die ein symmetrisches Muster aufweisen, ist in Tabelle 2 gezeigt. Hier sieht man, wie die 1en in dieser Matrix ein rekursives Muster sich wiederholender Dreiecke bilden; diese fraktale Konstruktion ist bekannt als "Sierpinski-Dichtung" [14]. Im Nachhinein läßt sich ein leichteres Verfahren zum Generieren dieser Matrix erkennen: Jedes Element ist das EXKLUSIV-ODER seiner Nachbarn rechts und oben. Diese Bit-Anordnung ist das binäre Äquivalent zum Pascalschen Dreieck.
Im allgemeinen lassen sich die Matrizen M errechnen aus einer quadratischen s x s Matrix, in der alle Elemente der obersten oder der untersten Reihe 1en sind (Einheitsreihen) und in der alle Elemente der rechten oder der linken Spalte 1en sind. Der Rest der quadratischen Matrix ist dann so konfiguriert, daß alle Elemente jeweils die Ergebnisse einer EXKLUSIV-ODER- Operation der zwei nächstliegenden Elemente sind, die am nächsten an der Einheitsspalte bzw. Einheitsreihe liegen.
Wenn die Bedingungen (A) und (B) erfüllt sind, ist ein konfliktfreier Zugriff garantiert, wenn auf den Speicher im Zweierpotenzschritt zugegriffen wird. Auch andere Schritte sind wichtig und es wäre erwünscht, die gleiche Konflikteliminierung auch für solche andere Schritte zu haben. Es ist aber nicht möglich, alle Schrittzugriffskonflikte zu eliminieren. Wenn dieses System auf allgemeine Rechnersysteme angewandt werden soll, ist es bedeutsam, daß kein Schrittzugriff einen Speicher-Heißpunkt erzeugt, oder daß wenigstens Speicherüberlappungsprobleme aus Schrittzugriffen extrem selten auftreten.
Um mit diesem Problem fertig zu werden, werden einige Maßnahmen definiert, um zu sehen, wie gut eine gegebene Permutation mit verschiedenen Schrittzugriffen fertig wird. Es sei M eine d x s Matrix-Abbildung eines s-Bit-Adressenraums FS, und nehmen wir an, das System habe d Geräte. Somit ist M eine Abbildung aus dem Satz FS auf den Satz {0,1,2,...,d-1}. Es seien t und a Ganzzahlen, wobei t als Schritt definiert ist, und a sei die Anfangsadresse des Schritts.
Betrachten wir die Adressen im Schritt, nämlich den Schritt A, bestehend aus a, a + t, a + 2t, ..., a + (d-1)t. Ci ist definiert als Teilmenge von V, abgebildet durch M auf die Geräte i. D.h.,
Ci = {x&epsi; V M(x) = i}
Die Ungleichmäßigkeit von M gegenüber (a,t) ist definiert als die Anzahl der Elemente im größten aller Ci.
Das zeigt, wie oft im häufigste Fall auf ein beliebiges Gerät während eines Schrittzugriffs auf die d Adressen a, a + t, a + 2t, ..., a + (d-1)t zugegriffen wird. Im geringsten Fall, bei einem konfliktfreien Zugriff, ist die Ungleichförmigkeit 1; im häufigsten Fall ist sie d. Für einen beliebigen Zweierpotenzschritt-Zugriff, unter Verwendung einer Permutation, die der Bedingung (A) genügt, ist die Ungleichförmigkeit entweder 1 oder 2.
Die Ungleichförmigkeit dieser Funktionen wurde für unterschiedliche Anfangsadressen a und Schritte t gemessen, unter der Annahme eines Systems mit 512 Speichermodulen, und unter Verwendung der 9 x 29 Matrix gemäß Definition in Tabelle 2. In einem solchen System, wenn die Zufallsverteilungsfunktion benutzt wird, um die Gerätenummern zu generieren, ist die Ungleichmäßigkeit etwa 5,16, ein Wert, der in die Graphen der Fig. 6, 7 und 8 zu Vergleichszwecken aufgenommen wurde. Auch die "einfache" Verschachtelung wurde eingeschlossen zwecks Darstellung der Unzulänglichkeit einer solchen Speicherorganisation. Die der Anfangsadresse a zugeordnete Ungleichförmigkeit Mai,t und Schritt t wurden für jeden Schritt berechnet unter Verwendung von 10.000 unterschiedlichen, zufallsgenerierter Anfangsadressen ai. Der Durchschnitt der Mai,t über alle i ist gegen den Schritt t aufgetragen.
Um die Effektivität dieser Technik zu zeigen, wurden alle Zweierpotenzschritt-Zugriffe von 2&sup0; bis 2¹&sup0; gemessen. Wie erwartet, sind alle A2i kleiner oder gleich 2. Der Graph in Fig. 6 zeigt die Bit-Matrix-Multiplikationsmethode im Vergleich zum reinen Verschachteln und mit Zufallsgenerierung der Gerätenummern.
Ähnliche Beispiele wurden für Schritte zwischen 1 und 100 gesammelt. Die Graphen in Fig. 8 und Fig. 7 geben einen Vergleich des allgemeinen Verhaltens der Bit-Matrix-Multiplikationsmethode mit "einfachem" Verschachteln. Das Verhalten der Methode zeigt, daß sie für die meisten Nichtzweierpotenzschritte "näher" an einer Zufallsfunktion als an der "einfachen" Verschachtelung liegt.
Die oben beschriebenen Testergebnisse unter Einsatz der vorliegenden Erfindung zum Reduzieren potentieller Konflikte betreffend den Schritt und dergl., wurden erzielt mit einer Software-Simulierung des beschriebenen Abbildungsverfahrens. Es muß hier darauf hingewiesen werden, daß eine solche Software-Implementierung sowohl praktisch als auch machbar ist. Jedoch ist es in einem großen Speichersystem, wo der allgemeine Zeitaufwand für den Zugriff auf den Speicher kritisch ist, für den Fachmann offensichtlich, daß eine Hardware-Ausführungsform in der Lage ist, mit einer beträchtlich größeren Geschwindigkeit zu arbeiten. Dementsprechend ist nachfolgend eine detaillierte Beschreibung einer bevorzugten Hardware-Ausführungsform der Erfindung gegeben, zusammen mit einer kurzen Diskussion über bestimmte Merkmale der Erfindung, die auf einzigartige Weise zu einer möglichen Konstruktion einer Adressenpermutationseinheit beiträgt, die die Merkmale der vorliegenden Erfindung beinhaltet, wobei der Bit-Matrix-Multiplikator, der für die Adressenabbildung eingesetzt ist, eine Mindestanzahl Geräte und Schaltungshöhen aufweist, die beide signifikant zur Geschwindigkeit der Operation beitragen.
Gegeben sei eine Boolesche Matrix M und ein logischer Adressenvektor V, dann ist die logische Tiefe der Booleschen Bitmatrix-Multiplikation logarithmisch in der Anzahl der Spalten s der Matrix. Alle Elemente im Produktvektor können parallel verarbeitet werden. Jedes Element des Produktvektors ist das EXKLUSIV-ODER derjenigen Elemente von V, für die das entsprechende Element von M gleich 1 ist. Das kann von der Hardware berechnet werden durch zunächst Berechnen des UND jedes Elements von V mit dem entsprechenden Element von M, dann Kombinieren der s Ergebnisse in einem Binärbaum von EXKLUSIV-ODER-Operationen. Das Ergebnis ist in der Tat die Parität der bitweisen UND zwischen der Reihe in M und dem Vektor V.
Wegen der Geradeausnatur der Funktionen, die von der Hardware-Implementierung der vorliegenden Erfindung gefordert wird, ist es möglich, die Boolesche Matrixmultiplikation als Teil der Adressenumsetzungs-Hardware innerhalb der individuellen Verarbeitungselemente des großen parallelen Verarbeitungssystems zu implementieren. Die Wahl bzw. Konstruktion dieser Matrix kann ein Attribut einer Seite oder eines Segments des virtuellen Speichers sein. Im Suchparellelen Verarbeitungssystem (RP3) [12], das oben schon angezogen wurde, wird der gesamte verschachtelte Speicher so ausgelegt, daß er als Vorgabe eine solche Transformation durchmacht.
Die Konstruktion einer geeigneten Hardwareimplementierung mit den obigen Merkmalen ist in den Figuren dargestellt. Diese Ausführungsform ist streng für eine Adressentransformation und im einzelnen zur Lösung der Probleme ausgelegt, die im Normal falle einhergehen mit dem Zweierpotenzschritt-Zugriff in einem solchen System. Wie bereits gesagt, ist ein Hardwaresystem mit einer mehr allgemeinen Fähigkeit zum Ausnutzen des Konzepts der Adressen- oder sonstigen Datenpermutation über die Bitmatrix-Multiplikation in der bereits angezogenen Europäischen Patentanmeldung EP-A-0 313 787 (E. Melton et al.) dargelegt.
Fig. 1 enthält ein funktionelles Blockschaltbild eines hochparallelen gemeinsam genutzten Speichersystems auf hoher Ebene wie z.B. der oben bereits angezogene RP3 [12]. Das System beinhaltet eine Vielzahl (bis zu 512) Verarbeitungsspeicherelemente 10, die über ein Netzwerk 18 miteinander verkoppelt sind. Jedes verarbeitende Verarbeitungsspeicherelement (PME) ist als im wesentlichen identisch vorstellbar und beinhaltet einen Mikroprozessor 12, eine Adressentransformationseinheit 14, eine Netzwerkschnittstelle 16, und eine Speichereinheit 22. Der Mikroprozessor 12 arbeitet ganz normal und greift erforderlichenfalls auf den Systemspeicher zu, um Befehle und/oder Daten abzurufen. Die Adressentransformationseinheit 14 wandelt logische Adressen aus dem Prozessor in physikalische Adressen und Speicher um. Die Netzwerkschnittstelle 16 bestimmt, ob eine besondere physikalische Adresse im örtlichen Speicher 22 resident ist oder aus einem anderen Speicherelement 22 des allgemeinen gemeinsamen Speichersystem, das in einem anderen PME resident ist, abgerufen werden muß. Der Zugriff auf eine andere Speichereinheit 22 in einem anderen PME würde über das Netzwerk 18 erfolgen. Wie man sich erinnert, ist der RP3 ein enggekoppeltes Multiprozessorsystem, auf dessen Speicher gemeinsam zugegriffen wird und der für alle Prozessoren zugänglich ist. Ferner liegt im RP3, zusätzlich zum gemeinsamen Zugriff, jede der Speichereinheiten 22 örtlich anliegend an einen bestimmten Prozessor.
Die Einzelheiten der vorliegenden Erfindung residieren in der Adressentransformationseinheit 14. Ein Signalflußplan mit Datenfluß für diese Einheit sind in Fig. 2 dargestellt. Wie in der Figur gezeigt, wird eine virtuelle 29-Bit-Adresse (0,28) auf eine Eingangsleitung 30 zur Segment/Seiten- Tabellenumsetzeinheit 32 gelegt. Wie in einem solchen virtueilen Adressierungssystem bekannt ist, wird die virtuelle Adresse über eine Seiten- und Segment-Nachschlagtabelle in der Einheit 32 in eine echte Adresse umgesetzt, wie in jedem herkömmlichen virtuellen Speichersystem. Daraus entsteht eine echte Adresse auf der Leitung 34, in der die Bits 9 bis 28 eine Verschiebung, und die Bits 0 bis 8, in welchem Segment und auf welcher Seite die angeforderte echte Adresse resident ist, angeben. Es sind die Bits 0 bis 8, die zur Adressenumwandlungsoperation durch die Matrixmultiplikationseinheit 34 passieren müssen. Man erinnert sich hier natürlich daran, daß obwohl die Bits 9 bis 28 den Verschiebeteil der physikalischen Adresse ausmachen, die auf Leitung 36 steht, diese Bits auch als Teil des Eingangs an die Matrixmultiplikationseinheit 34 gegeben werden müssen. Die Bits 0 bis 8 müssen von der Matrixmultiplikationseinheit in eine Knotenzahl permutiert werden, die, anders gesagt, festlegt, in welchem Speicher des allgemeinen Systems die entsprechende Adresse residiert. Wieder wird angenommen, daß das System 512 unterschiedliche PME und zugeordnete gesonderte Speichereinheiten 22 enthält. Dementsprechend sind 9 Bits (0,8) erforderlich, um eine solche Knotenadresse zu spezifizieren. Die wahre benutzte Bitzahl zum Bestimmen der Knotenadresse und die Anzahl der Verschiebungsbits hängt ab vom Verschachtelungsbetrag, der für eine bestimmte Systemkonfiguration spezifiziert ist. Wenn also ein bestimmtes System nur z.B. 256 PMEs enthielte, dann wären nur 8 Bits erforderlich, um die Knotennummer zu spezifizieren, und dementsprechend würden nur 8 Bits von der Matrixmultiplikationseinheit 34 produziert werden. Diese spezifischen Verschachtelungsbeträge würden auf der Leitung 36 in der Figur stehen und würden (nicht spezifisch dargestellt) kontrollieren, wie viele Bits eines permutierten Ausgangs produziert würden. Die wahre Permutationsmatrix wird als abgespeichert und/oder verfügbar für die Matrixmultiplikationseinheit 34 angenommen, die einfach ein ROM innerhalb der Matrixmultiplikationseinheit sein könnte.
Nehmen wir jetzt an, daß vom System 9 die Bits der permutierten Adresse produziert werden müssen; hier versteht man, daß die gesamte 29 Bit lange echte Adresse der Reihe nach (9 Mal) mit den ersten neun der 29-Bit Reihen der Permutationsmatrix multipliziert würde, und so eine 9-Bit- Knotenadresse auf Leitung 38 produzieren würde. Diese 9-Bit- Knotennummer oder Adresse würde kombiniert mit den Bits 9 bis 28 auf Leitung 40, um die 29-Bit lange physikalische Adresse auf Leitung 42 zu produzieren. Fig. 3 zeigt eine mögliche Hardware-Implementierung einer Matrixmultiplikationseinheit, die in der Lage wäre, die permutierte Adresse zu erzeugen, die von der hier offenbarten Methode gefordert wird.
Die 29 Bits der echten Adresse S und die 29 Bits aus jeder entsprechenden Reihe der Matrix A sind in Tabelle 2 gezeigt und bilden die Eingänge zu dieser funktionellen Skalarprodukteinheit. Die echte Adresse S wird in Register 50 gespeichert und die neun 29-Bit-Reihen (A&sub0; ... A&sub8;) werden über die zwei Leitungen 54 und 56, die in der Figur dargestellt sind, an die Skalarproduktblöcke 52 gegeben. Es wird hier natürlich begreiflich, daß unter der Annahme, daß eine 9-Bit Permutation vorgenommen werden muß, neun 29-Bit-Eingangsleitungen wie 54 und 56 jeweils einen 29-Bit-Eingang auf 9 der Skalarproduktblöcke 52 legen würde. Wie oben beschrieben, produziert jeder der Skalarproduktblöcke ein entsprechendes Bit der endgültigen Knotennummer, die auf der Leitung 58 erscheinen. Wie man in der Figur bemerkt, werden, wie schon früher unter Bezugnahme auf die Fig. 2 beschrieben ist, die Bits S&sub9; "bis" S&sub2;&sub8; der echten Adresse über die Leitungen 62 direkt in unveränderter Form ins Ausgangsregister 60 zu den Bitspeicherorten S'&sub9; bis S'&sub2;&sub8; gegeben.
Alle 29 echten Adressenbits S&sub0; bis S&sub2;&sub8; müssen auch, wie dargestellt, über die Leitung 64 an jeden Eingang der Skalarproduktblöcke 52 gegeben werden. Jeder Skalarproduktblock 52 erhält zusätzlich 29 Bits der echten Adresse und auch eine 29-Bit-Reihe von der Matrix. Somit führt jeder Skalarproduktblock 52 die geforderte Matrixmultiplikation durch und erzeugt ein einziges Ausgangsbit (S'x).
Fig. 4 enthält ein detailliertes logisches Blockschaltbild, wie ein Skalarproduktblock 52 gemäß Fig. 3 ausgeführt werden könnte. Die Figur illustriert spezifisch die Schaltung zum Generieren des höchstwertigen Bits S'&sub0;, ausgehend von den Eingängen:
1. 29 Bit der echten Adresse S(0,28), die dem Block über die Leitung 70 zugehen, und
2. 29 Bit der Reihe 0 der Matrix A, die dem Block über die Leitung 72 zugehen.
Die Adressen- und Reihenbits werden an 29 und die Schaltung 74 geliefert, in der die Bits S&sub0; und A&sub0; an das obere UND- Gatter geführt werden, und die Bits S&sub2;&sub8; und A&sub2;&sub8; werden an das untere UND-Gatter geführt. Alle 29 Ausgänge, die an den Leitungen 76 auftreten, bilden die Eingänge zu einem Modulo-2 Summierer 78, der diese 29 Eingänge über eine logische Modulo-2 Additionsfunktion zu einem einzigen Ausgangs-Bit kombiniert. Das könnte durch einen 'EXKLUSIV-ODER'-Baum geschehen, wie dem Fachmann geläufig ist. Es ist natürlich klar, daß die Skalarproduktfunktion durch eine ganze Anzahl verschiedener logischer Schaltungskonfigurationen erzeugt werden kann. Eine solche unterschiedliche Konfiguration wird in der einschlägigen Europäischen Patentanmeldung EP-A-0 313 787 (E. Melton et al.) benutzt.
Das schließt die Beschreibung der offenbarten, bevorzugten Hardware-Ausführungsform ab, die in der Lage ist, das allgemeine Bit-Matrix-Multiplikations-Permutationsverfahren der vorliegenden Erfindung durchzuführen. Weitere Konfigurationen können von Fachleuten leicht entworfen werden.
Fig. 5 zeigt ein Netzwerk mit invertierter Basislinie, das für den Typ der Verkoppelungsnetzwerke, die in einem solchen parallelen Speichersystem mit gemeinsamen Zugriff typisch ist. Die Konfiguration dieses Netzwerks ermöglicht eine konfliktfreie Datenführung für alle Zweierpotenzschritt- Zugriffe dann und nur dann wenn solche Adressen gemäß der vorliegenden Erfindung vor der Leiterwegsuche permutiert werden. Dieses System ist nicht Teil der vorliegenden Erfindung und wird nur für Illustrationszwecke gezeigt. Wie dem Fachmann ersichtlich ist, handelt es sich um ein mehrstufiges, zweiseitiges Blockierungs-Netzwerk. Kurz gesagt, der Betrieb desselben ist wie folgt: Die Schalter in den drei Spalten, gekennzeichnet A, B und C, verbinden jeweils jeden der beiden Eingänge mit einem bestimmten Ausgang in Abhängigkeit von der Einstellung des Adressen-Teilfeldes. In diesem Fall wird der obere Ausgang eines jeden Schalters aktiviert, wenn das Feld 0 ist, und der untere Ausgang wird aktiviert, wenn die Adresse oder das Teilfeld eine 1 ist. Die Spalte mit den Binärzahlen an der linken Seite stellen die Quell- oder Anwenderadressen dar, und die Spalten mit den drei Binärzahlen auf der rechte Seite stellen die Ziel- oder Serveradressen dar. Hier sieht man, daß eine gleiche Zahl, die in der gleichen Reihe beider Spalten erscheint, anzeigt, daß die Quelle gleichzeitig auch die Bestimmung oder der Server ist. Wenn also in der Figur die Quelle 000 ihren eigenen Speicher ansprechen will, sieht sie eine Bestimmungsadresse 000 vor. Wie man sieht, führt das dazu, daß in allen drei Spalten die Schalter jeweils auf die oberen Ausgänge eingestellt werden, weil die Bestimmungsadresse 000 an die Schaltersteuermatrix gegeben wird. Wieder unter Bezugnahme auf die Figur wird bemerkt, daß die kleinen Teilfelder a, b und c in der Figur die besonderen Teilfelder bezeichnen, die die Schalterspalten A, B und C steuern. Wenn also gewünscht wird, die Quelle 011 mit dem Ziel 111 zu verbinden, mußt die Quelle 011 eine Adresse 111 angeben, was die unteren Ausgänge der drei Schalter 90, 92 und 94 aktiviert, die diese Verbindung herstellen.
Als zweites Beispiel nehmen wir an, es solle die Quelle 001 mit dem Ziel 110 verbunden werden; in diesem Fall würde von der Quelle 001 die Adresse d.i. der Matrixschalterbefehl 110 an die Schaltersteuermatrix für das Netzwerk gegeben werden, was die unteren Ausgänge der Schalterblöcke 96 und 92, und den oberen Ausgang des Blocks 94 aktivieren würde, wodurch der gewünschte Leiterweg hergestellt würde. Somit läßt sich von dem System jede gewünschte Verbindung zwischen Quelle und Ziel herstellen. Wie bereits gesagt, wird natürlich eine Schalterüberlappung d.i. der Durchgang von zwei Anforderungen durch den gleichen Schalter zur gleichen Zeit nur durch Anwendung des hier beschriebenen Adressenpermutationsverfahren erleichtert.
Jetzt, nach Abschluß der Beschreibung des hier dargelegten Verfahrens zur Verbesserung der Zweierpotenzschritt-Zugriffe auf physikalische Geräte kann man zu bestimmten Schlußfolgerungen kommen. Das Verfahren ist von besonderem Wert beim Vermeiden von E/A-Heißstellen, die sich ergeben würden, wenn viele Prozessoren auf Daten an Adressen zugreifen wollten, die um Zweierpotenzschritte voneinander getrennt sind. Auch Netzwerküberlappungen lassen sich vermeiden durch eine geeignet Auswahl der Abbildungsfunktion. Es wurde zum Beispiel gezeigt, daß sich alle Überlappungen in einem Netzwerk mit invertierter Basislinie für alle Zweierpotenzschritt-Zugriffe vermeiden lassen. Das Verfahren eliminiert nicht vollständig Überlappungen bei Zugriffen mit anderen Schritten, aber eine solche Überlappung ist vergleichbar mit der Überlappung, die bei Zufallszahlen- Speicherzugriffen auftritt.
Ein signifikanter Vorteil dieses Verfahrens liegt in der Tatsache, daß es sich mit einer kleinen Anzahl EXKLUSIV-ODER- Gatter leicht implementieren läßt. Daher ist das Verfahren geeignet für die Anwendung in speicheradressierender Hardware in Parallelrechnern für allgemeine Zwecke. Aufgrund der vollständigen Eliminierung von Konflikten bei Zweierpotenzschritt-Zugriffen ist dieses Verfahren auch geeignet zum Einsatz in Rechnern für besondere Zwecke und für SIMD- Maschinen, die auf einen konfliktfreien Zugriff auf Parallelspeicher in Zweierpotenzabständen angewiesen sind.
Die gezeigten Anwendungsbeispiele der hier beschriebenen Erfindung zeigen nur eine begrenzte Anzahl von Anwendungsmöglichkeiten für das Verfahren. Man kann annehmen, daß die Anwendung der vorliegenden Erfindung zu verbesserten Zugriffsmethoden für eine ganze Reihe von Netzwerk-Topologien führen wird und für E/A-Systemkonstruktionen nützlich ist.
Zwar wurde hier die Implementierung des Verfahrens in Hardware-Ausführung als bevorzugte Ausführungsart offenbart, es muß jedoch darauf hingewiesen werden, daß sich die Erfindung, wie oben gesagt, auch leicht als Softwarelösung ausführen läßt. Zusammenfassend muß gesagt werden, daß die vorliegende Erfindung in dem neuheitlichen Verfahren zum Ausführen der Adressenpermutation liegt, die das Bit-Matrix-Multiplikationsverfahren beinhaltet, und nicht auf ihrer bestimmten Implementierungsform beruht.
Der Wert und die Einfachheit des Verfahrens zeigen eindeutig, daß die hier offenbarte Bit-Matrix-Multiplikation in Speicherabbildungshardware für Prozessoren in Hochparallelsystemen eingesetzt werden sollte.

Claims

1. Adressenpermutationsverfahren zum Abbilden einer ersten Speicheradresse auf eine zweite Speicheradresse in einem Rechnersystem mit einer Anzahl Speichergeräte (22) unter Eliminierung der Zweierpotenzschritt-Zugriffsüberlappung zwischen den Speichergeräten (22) für Schritte von 2t mit Ganzzahlen t > = 0,

in dem die erste und die zweite Speicheradresse s Bits enthalten und

die Anzahl der Speichergeräte (22) ein Zweierpotenzwert 2d mit d < s ist,

wobei das Adressenpermutationsverfahren den Schritt der Durchführung einer Bit-Matrix-Multiplikation der ersten Speicheradresse mit aufeinanderfolgenden Reihen einer d x d Untermatrix einer Familie von Adressen-Permutation- Untermatrizen umfaßt,

wobei sich die Untermatrizen und die Abbildungen der Resultierenden auf Transformationen gründen, die über das Boolesche Feld GF(2) linear sind, und

wobei die d x d Untermatrix bestimmt wird von einer d x s Matrix M', in der die d Reihen die der ersten Speicheradresse zugeordnete physikalische Geräte bestimmen,

wobei die d x d Untermatrix nichtsingulär ist und d nebeneinanderliegende Spalten von M', d.i. Spalten s - t - d + 1 bis s - t für einen Schritt 2t umfaßt.

2. Adressenpermutationsverfahren gemäß Anspruch 1, in dem jede j x j Untermatrix von M' mit j < = d, die an den oberen Rand von M' anstößt, nichtsingulär ist.

3. Adressenpermutationsverfahren gemäß Anspruch 1 oder 2, in dem

die Matrix M' aus einer s x s Matrix M abgeleitet wird, in der jedes Element in der obersten oder in der untersten Reihe der Matrix M 1 ist, und

jedes Element in der am weitesten rechts oder am weitesten links liegenden Spalte 1 ist,

und in dem die anderen Elemente der Matrix M durch eine EXKLUSIV-ODER-Operation der zwei der Einheitsspalte und -reihe zunächst liegenden anliegenden Elemente gebildet werden.

4. Speicherverwaltungsmittel mit einer Vielzahl von Speicherelementen (10), die über ein Netzwerk (18) zusammengeschaltet sind,

wobei diese Speicherelemente (10) Speichermittel (22) und eine Adressentransformationseinheit (14) zum Transformieren der logischen Adressen in physikalische Adressen enthalten,

dadurch gekennzeichnet, daß

die Adressentransformationseinheit (14) eine Matrix- Multiplikationseinheit (34) enthält, die im Betrieb die Adressen-Permutationsmethode gemäß einem der Ansprüche 1 bis 3 durchführt.

5. Speicherverwaltungsmittel gemäß Anspruch 4, ferner dadurch gekennzeichnet, daß

die Adressen-Transformationseinheit (14) ferner eine segment/Seiten-Umsetzeinheit (32) enthält, die als Eingang eine virtuelle Adresse aufnimmt und eine echte Adresse ausgibt,

wobei diese echte Adresse eine Knotennummer und eine Verschiebung beinhaltet,

wobei die Knotennummer und die Verschiebung an die Matrix- Multiplikationseinheit (34) weitergegeben werden und durch die Adressen-Permutationsmethode eines der Ansprüche 1 bis 3 bearbeitet werden, um eine permutierte Knotennummer zu erzeugen,

und wobei am Ausgang der Adressen-Transformationseinheit (14) die permutierte Knotennummer und die Verschiebung verkettet werden, um eine permutierte echte Adresse zu erzeugen.

6. Speicherverwaltungsmittel gemäß Anspruch 4 oder 5, ferner dadurch gekennzeichnet, daß

die Matrix-Multiplikationseinheit wenigstens eine Skalarprodukt-Einheit (52) aufweist,

ein erster Eingang jeder der wenigsten einen Skalarprodukt-Einheiten (52) mit einem Speicherelement verbunden ist, in dem eine Reihe der Matrix M' abgespeichert ist, und

ein zweiter Eingang jeder der wenigsten einen Skalarprodukt-Einheiten (52) mit einem Speicherelement (50) verbunden ist, in dem die echte Adresse abgespeichert ist,

wobei jede der wenigsten einen Skalarprodukt-Einheiten (52) den ersten und den zweiten Eingang bit-multipliziert, um den Wert eines Bits der permutierten Knotennummer zu erzeugen.

7. Rechnersystem mit einer Vielzahl von Prozessoren und einer Vielzahl von Speicherelementen (10), das im Betrieb die Adressen-Permutationsmethode der Ansprüche 1 bis 3 anwendet, um Konflikte beim Zugriff auf die Vielzahl der Speicherelemente (10) zu reduzieren.