• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    Beider LU-Zerlegung einer Matrix, die aus Blöcken zusammengesetzt ist, werdendie zu aktualisierenden Blöckeder Matrix in vertikaler Richtung in jedem SMP-Knoten geteilt, der über einNetzwerk angeschlossen ist, und jeder der geteilten Blöcke wirdjedem Knoten zugeteilt. Dieser Prozess wird wiederholt auf später zu aktualisierendeneue Blöckeangewendet, und die neu geteilten Blöcke werden auch zyklisch jedemKnoten zugeteilt. Jeder Knoten aktualisiert zugeteilte geteilteBlöckein der ursprünglichenReihenfolge von Blöcken.Da sich durch sequentielles Aktualisieren von Blöcken das Ausmaß an verarbeitetenBlöckenjedes Knotens auf gleiche Weise erhöht, kann eine Belastung gleichmäßig verteiltwerden.
    公开号:DE102004015599A1
    申请号:DE200410015599
    申请日:2004-03-30
    公开日:2004-10-28
    发明作者:Makoto Kawasaki Nakanishi
    申请人:Fujitsu Ltd；
    IPC主号:G06F9-38
    专利说明:
    [0001] Dievorliegende Erfindung betrifft eine Matrizenverarbeitungsvorrichtungund ein Verfahren in einem Parallelrechner vom SMP-(symmetrischesMultiprozessorsystem)-knotenverteiltenSpeichertyp.
    [0002] Beider Lösungvon gleichzeitigen linearen Gleichungen, die für einen Parallelrechner entwickelt sind,in welchem Vektorprozessoren durch Kreuzschienen verbunden sind,wird jeder Block, der einer LU-Zerlegung zu unterziehen ist, jedemProzessorelement zyklisch zugeteilt, um eine LU-Zerlegung auszuführen. Ineinem Vektorprozessor ist selbst dann, wenn die Breite eines Blocksreduziert ist, die Effizienz der teuren Berechnung eines Aktualisierungsteilsunter Verwendung eines Matrizenprodukts sehr hoch. Daher berechnetin Bezug auf eine Matrix als die zyklische Zuteilung eines Blocksmit einer Breite von etwa 12 zuerst eine CPU sequentiell Blöcke mittelseiner LU-Zerlegung, und dann wird das Ergebnis in eine Vielzahlvon Teilen aufgeteilt. Jeder Teil wird zu jedem Prozessor transferiertund wird unter Verwendung eines Matrizenprodukts aktualisiert.
    [0003] 1 zeigt den Grundalgorithmusfür eine LU-Zerlegungeines Superskalar-Parallelrechners.
    [0004] EineLU-Zerlegung wird unter Verwendung eines Verfahrens, das durch Blockiereneines Gauss'schenEliminationsverfahrens erhalten wird, auf ein Feld A angewendet.Das Feld A wird durch eine Blockbreite d zerlegt.
    [0005] Imk-ten Prozess wird ein Aktualisierungsteil A(k) wiefolgt aktualisiert: A(k) = A(k) – L2(k) × U2(k) (1)
    [0006] Im(k + 1)-ten Prozess wird A(k) durch die Breited zerlegt, und eine Matrix, die um d kleiner ist, wird unter Verwendungderselben Gleichung aktualisiert.
    [0007] L2(k) und U2(k) müssen gemäß der folgenden Gleichungberechnet werden.
    [0008] ImFall eines Aktualisierens unter Verwendung der Gleichung (1) wirdA(k) wie folgt zerlegt A -(k) = (L1(k)T, L2(k)T)TU1(k) undwird wie folgt aktualisiert: U2(k) =L1(k)-1U2(k)
    [0009] Dieoben angegebene Block-LU-Zerlegung ist im Patentdokument 1 offenbart.
    [0010] Darüber hinausoffenbaren die Patentdokumente 2, 3, 4 und 5 als Technologien zumBerechnen einer Matrix durch einen Parallelrechner ein Verfahrenzum Speichern der Koeffizientenmatrix einer gleichzeitigen linearenGleichung in einer externen Speichervorrichtung, ein Verfahren für einenVektorcomputer, ein Verfahren zum gleichzeitigen Eliminieren vonMehrfach-Pivot-Ketten bzw. ein Verfahren zum Ausführen einerLU-Zerlegung nach einem erneuten Anordnen der Reihenfolge jedesElements einer Reservematrix, um eine Randblock-Diagonalmatrix herzustellen. Patentdokument1: offengelegtes japanisches Patent Nr. 2002-163246 Patentdokument2: offengelegtes japanisches Patent Nr. 9-179851 Patentdokument3: offengelegtes japanisches Patent Nr. 11-66041 Patentdokument4: offengelegtes japanisches Patent Nr. 5-20349 Patentdokument5: offengelegtes japanisches Patent Nr. 3-229363
    [0011] Wenndie oben angegebene LU-Zerlegung für einen Superskalar-Parallelrechner durchein Parallelrechnersystem ausgeführtwird, bei welchem ein Knoten einfach derart bezeichnet ist, dasser ein SMP ist, treten die folgenden Probleme auf: Zum effizientenBerechnen eines Matrizenprodukts in einem SMP-Knoten muss die Blockbreite,die in einem Vektorrechner auf 12 eingestellt ist, auf etwa 1.000erhöhtwerden. (1) In diesem Fall wird dann, wenneine Matrix unter der Annahme verarbeitet wird, dass ein SMP-Knotenjedem Prozessor fürjeden Block zyklisch zugeteilt wird, das Ausmaß an Aktualisierungsberechnungunter Verwendung eines Matrizenprodukts unter Prozessoren oft ungleich,und eine Parallelitätseffizienzverschlechtert sich merklich. (2) Wenn die LU-Zerlegung eines Blocks mit einer Breite vonetwa 1.000 in einem Knoten nur in einem Knoten berechnet wird, tretenandere Knoten in einen Leerzustand ein. In diesem Fall verschlechtertsich deshalb, weil diese Leerzeit sich proportional zur Breite erhöht, eineParallelitätseffizienzmerklich. (3) Wenn die Anzahl von CPUs, die einen SMP-Knoten bilden, erhöht wird,scheint sich beim herkömmlichenVerfahren das Ausmaß an Transferrelativ zu erhöhen,obwohl es etwa 0,5n2 × 1,5 Elemente ist (in diesemFall sind Elemente Matrixelemente), da sich eine Transferrate bzw. Übertragungsratemit einem Erhöhenan Berechnungskapazitätrelativ verschlechtert. Daher verschlechtert sich die Effizienzsehr. Die in (1) bis (3) von oben verursachte Verschlechterung ziehteine Leistungsverschlechterung von etwa 20 bis 25% als Ganzes nachsich.
    [0012] Esist eine Aufgabe der vorliegenden Erfindung, eine Vorrichtung undein Verfahren zu schaffen, um zu ermöglichen, dass ein Parallelrechner vomSMP-knotenverteilten Speichertyp Matrizen mit hoher Geschwindigkeitverarbeitet.
    [0013] DasMatrizenverarbeitungsverfahren der vorliegenden Erfindung ist ineinem Parallelrechnersystem angenommen, in welchem eine Vielzahlvon Prozessoren und eine Vielzahl von Knoten einschließlich einesSpeichers überein Netzwerk verbunden sind. Das Verfahren weist folgendes auf:einen ersten Zuteilungsschritt zum Verteilen und Zuteilen einerKombination von Bündelnvon Spaltenblöckeneines Teils einer Matrix, zyklisch zugeteilt, zu jedem Knoten, umdie Kombination von Bündelnvon Spaltenblöckenzu verarbeiten, einen Trennungsschritt zum Trennen eines diagonalenBlocks und eines Spaltenblocks unterhalb des diagonalen Blocks derKombination von Bündelnvon Spaltenblöcken vonden anderen Blöcken,einen zweiten Zuteilungsschritt zum redundanten Zuteilen des diagonalen Blockszu jedem Knoten und auch zum Zuteilen von einem Block, der durcheindimensionales Aufteilen des Spaltenblocks in jedem der Vielzahlder Knoten erhalten wird, währendparallel kommuniziert wird, einen LU-Zerlegungsschritt zum parallelen Ausführen derLU-Zerlegung des diagonalen Blocks und des zugeteilten Blocks injedem Knoten, währendmit jedem Knoten kommuniziert wird, und einen Aktualisierungsschrittzum Aktualisieren der anderen Blöcke derMatrix unter Verwendung des LU-zerlegten Blocks.
    [0014] Gemäß der vorliegendenErfindung kann deshalb, weil eine Berechnungsbelastung auf Knoten verteiltwerden kann und das Ausmaß anParallelverarbeitung verbessert werden kann, eine MatrizenverarbeitunghöhererGeschwindigkeit realisiert werden. Da eine Berechnung und ein Datentransferparallel durchgeführtwerden, kann die Verarbeitungsfähigkeiteines Computers ungeachtet seiner Datentransferrate verbessert werden.
    [0015] Esfolgt eine kurze Beschreibung der Zeichnungen.
    [0016] 1 zeigt den Grundalgorithmusfür die LU-Zerlegungeines Superskalar-Parallelrechners;
    [0017] 2A und 2B zeigen die allgemeine Grundkonfigurationeines Parallelrechner vom SMP-knotenverteilten Speichertyp, diedas bevorzugte Ausführungsbeispielder vorliegenden Erfindung annimmt;
    [0018] 3 ist ein Ablaufdiagramm,das den gesamten Prozess gemäß dem bevorzugtenAusführungsbeispielder vorliegenden Erfindung zeigt;
    [0019] 4 zeigt das allgemeine Konzeptdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung;
    [0020] 5 zeigt einen Zustand, inwelchem Blöckemit einer relativ geringen Breite zyklisch zugeteilt werden (Nr.1);
    [0021] 6 zeigt einen Zustand, inwelchem Blöckemit einer relativ geringen Breite zyklisch zugeteilt werden (Nr.2);
    [0022] 7 zeigt den Aktualisierungsprozessder Blöcke,die zugeteilt sind, wie es in den 5 und 6 gezeigt ist;
    [0023] 8A und 8B zeigen eine rekursive LU-Zerlegungsprozedur;
    [0024] 9 zeigt die Aktualisierungdes Unterblocks, der ein anderer als ein diagonaler Block ist;
    [0025] 10 zeigt den Aktualisierungsprozesseines Zeilenblocks (Nr. 1);
    [0026] 11 zeigt den Aktualisierungsprozesseines Zeilenblocks (Nr. 2);
    [0027] 12 zeigt den Aktualisierungsprozesseines Zeilenblocks (Nr. 3);
    [0028] 13 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 1);
    [0029] 14 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 2);
    [0030] 15 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 3);
    [0031] 16 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 4);
    [0032] 17 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 5);
    [0033] 18 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 6);
    [0034] 19 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 7);
    [0035] 20 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 8);
    [0036] 21 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 9);
    [0037] 22 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 10);
    [0038] 23 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 11);
    [0039] 24 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 12);
    [0040] 25 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 13); und
    [0041] 26 ist ein Ablaufdiagrammdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung (Nr. 14).
    [0042] Esfolgt eine Beschreibung der bevorzugten Ausführungsbeispiele.
    [0043] Diebevorzugten Ausführungsbeispieleder vorliegenden Erfindung schlagen ein Verfahren zum Verarbeiteneines Teils vor, bei welchem eine Belastung selbst dann vollständig ausgeglichenist, wenn eine Blockbreite erhöhtist, und welches durch eine CPU parallel zwischen Knoten sequentiellberechnet wird.
    [0044] Die 2A und 2B zeigen die allgemeine Grundkonfigurationeines Parallelrechners vom SMP-knotenverteilten Speichertyp, derdas bevorzugte Ausführungsbeispielder vorliegenden Erfindung annimmt.
    [0045] Wiees in 2A gezeigt ist,sind Knoten 1 bis N an ein Kreuzschienennetz angeschlossen und können miteinanderkommunizieren. Wie es in 2B gezeigtist, könnendeshalb, weil in jedem Knoten Speichermodule 11-1 bis 11-n undPaare von Prozessoren 13-1 bis 13-m und Caches 12-1 bis 12-m miteinanderverbunden sind, sie miteinander kommunizieren. Eine Datenkommunikations-Hardware(DTU) 14 ist an das in 2A gezeigteKreuzschienennetz angeschlossen und kann mit einem anderen Knotenkommunizieren.
    [0046] Zuerstwerden Spaltenblöckejeweils mit einer vergleichsweise geringen Breite zyklisch einem Knotenzugeteilt. Eine Kombination von Bündeln von Blöcken injedem Knoten wird als eine Matrix angesehen. In diesem Fall kanneine Matrix derart angesehen werden, dass sie in einem Zustand ist,in welchem eine Matrix zweidimensional und gleichmäßig aufgeteiltist, und die aufgeteilten Blöckewerden verteilt und einer Vielzahl von Knoten zugeteilt. Dieser Zustandwird unter Verwendung eines parallelen Transfers bzw. einer parallelen Übertragungdynamisch zu einer eindimensionalen und gleichmäßig aufgeteilten Anordnungmodifiziert. In diesem Fall bedeutet ein eindimensionales und zweidimensionalesAufteilen einer Matrix ein Aufteilen von ihr in vertikaler bzw.horizontaler Richtung, wenn die Matrix ein Rechteck oder ein Quadratist. In diesem Fall wird ein quadratischer Teil am oberen Ende vonallen Knoten gemeinsam genutzt.
    [0047] DieseModifikation einer verteilten Zuteilung ermöglicht die Verwendung einesparallelen Transfers unter Verwendung des Kreuzschienennetzes, unddas Ausmaß einesTransfers erniedrigt sich auf ein solches, das durch Teilen vonihm durch die Anzahl von Knoten erhalten wird. Dann wird diese LU-Zerlegungvon Blöckenin der eindimensional und gleichmäßig aufgeteilten Anordnungin allen Knoten durch eine Zwischenknotenkommunikation parallel ausgeführt. Indiesem Fall wird zum Verbessern einer Parallelverarbeitungseffizienzund auch zum Verbessern der Leistungsfähigkeit des SMP eine Reflexions-LU-Zerlegungdurch weiteres Zerlegen der Blöckeausgeführt.
    [0048] Wenndiese LU-Zerlegung von Blöckenbeendet ist, hat jeder Knoten Information über einen diagonalen Blockteilund Information übereinen eindimensional und gleichmäßig aufgeteiltenTeil. Daher wird unter Verwendung von beiden Segmenten von Informationein Zeilenblockteil aktualisiert, und andere Teile ausschließlich deroberen linken Ecke, bei welcher sich eine Spalte und eine Zeileschneiden, werden unter Verwendung des Zeilenblockteils und einesgespeicherten Spaltenblockteils aktualisiert. Dann wird zur Zeiteiner Aktualisierung diese Information zu seinem benachbarten Knotentransferiert, und ein darauf folgendes Aktualisieren wird vorbereitet.Dieser Transfer kann gleichzeitig mit einer Berechnung durchgeführt werden.Durch Wiederholen dieser Operationen können alle zu aktualisierenden Teileaktualisiert werden.
    [0049] 3 ist ein Ablaufdiagramm,das den gesamten Prozess gemäß dem bevorzugtenAusführungsbeispielder vorliegenden Erfindung zeigt.
    [0050] Zuerstwird in einem Schritt S10 bestimmt, ob es das letzte Bündel ist.Wenn die Bestimmung im Schritt S10 ja ist, geht der Prozess weiterzu einem Schritt S15. Wenn die Bestimmung im Schritt S10 nein ist,wird in einem Schritt S11 die Anordnung bzw. der Aufbau unter Verwendungeines parallelen Transfers in die Anordnung bzw. den Aufbau einer Kombinationvon Bündelnvon Blöcken,die zu verarbeiten sind, umgewandelt. In diesem Fall muss der diagonaleBlock von allen Knoten gemeinsam genutzt werden. In einem SchrittS12 wird eine LU-Zerlegung auf die eindimensional aufgeteilten undzugeteilten Blöckeangewendet. In diesem Fall werden beide Blöcke mit derselben Breite wieder Größe einesCaches und Blöckemit einer Breite, die kleiner als sie ist, getrennt und reflektivverarbeitet. In einem Schritt S13 wird der Aufbau, der durch eindimensionalesAufteilen des LU-zerlegtenBlocks erhalten wird, unter Verwendung eines parallelen Transferszu demjenigen wiederhergestellt, der durch zweidimensionales Aufteilendes ursprünglichenBlocks erhalten wird. An dieser Stelle werden diagonale Blöcke undkleine Blöcke,die durch eindimensionales Teilen der übrigen Blöcke durch die Anzahl von Knotenerhalten werden, jedem Knoten zugeteilt. In einem Schritt S14 wirdein Bündelvon Blöckenin der Zeilenrichtung in jedem Knoten unter Verwendung des von allenKnoten gemeinsam genutzten aktualisierten diagonalen Blocks aktualisiert.In diesem Fall werden fürein darauf folgendes Aktualisieren benötigte Spaltenblöcke gleichzeitigmit einer Berechnung zu ihren benachbarten Knoten transferiert.Im Schritt S15 wird das letzte Bündelvon Blöckenredundant jedem Knoten zugeteilt, ohne dass es geteilt wird, undeine LU-Zerlegung wird darauf angewendet, indem dieselbe Berechnungausgeführtwird. Ein Teil entsprechend jedem Knoten wird zurückkopiert.Dann endet der Prozess.
    [0051] 4 zeigt das allgemeine Konzeptdes bevorzugten Ausführungsbeispielsder vorliegenden Erfindung.
    [0052] Wiees in 4 gezeigt ist,wird beispielsweise eine Matrix gleichmäßig in vier aufgeteilt und wirdzu jedem Knoten verteilt und angeordnet. Spaltenblöcke werdenjedem Knoten zugeteilt und werden zyklisch verarbeitet. In diesemFall wird eine Kombination aus Bündelnvon Blöckenals ein Block angesehen. Dieser Block wird, außer einem diagonalen Blockteil,eindimensional aufgeteilt und wird unter Verwendung einer Kommunikationerneut jedem Knoten zugeteilt.
    [0053] Die 5 und 6 zeigen einen Zustand, in welchem Blöcke miteiner vergleichsweise geringen Breite zyklisch zugeteilt werden.
    [0054] Wiees in den 5 und 6 gezeigt ist, wird ein Teildes Spaltenblocks einer Matrix weiter in kleinere Spaltenblöcke aufgeteilt,und die geteilten Spalten werden jedem Knoten zugeteilt (in diesemFall ist die Anzahl von Knoten vier). Eine solche Zuteilungsmodifikationbedeutet, einen zweidimensional aufgeteilten Block in einen eindimensionalaufgeteilten Block umzuwandeln (diagonale Blöcke werden gemeinsam genutztund gespeichert). Diese Umwandlung kann unter Verwendung des parallelenTransfers des Kreuzschienennetzes durchgeführt werden.
    [0055] Dieskann durch paralleles Transferieren von jeder Gruppe von diagonalangeordneten Blöcken (11, 22, 33, 44),(12, 23, 34, 41), (13, 24, 31, 42)und (14, 21, 32, 43) zu jedemKnoten (Transferieren von ihnen von einem zweidimensional geteiltenProzessor zu einem eindimensional geteilten Prozessor) realisiertwerden, wenn eine Kombination von Bündeln von Blöcken wieein Gitter bzw. Netz virtuell geteilt wird. In diesem Fall wirddurch Übertrageneines diagonalen Blockteils mit einer großen Größe, die ausreichend ist, umvon allen Knoten miteinander gemeinsam genutzt zu werden, das Transferausmaß zu einemsolchen reduziert, das durch sein Teilen durch die Anzahl von Prozessorenerhalten wird.
    [0056] Dannwird eine LU-Zerlegung auf die Spaltenblöcke angewendet, deren Verteilung/Zuteilung durchgleichmäßiges Zuteilendes geteilten diagonalen und der übrigen Blöcke zu jedem Knoten so modifiziertist, währendeine Zwischenknotenkommunikation durchgeführt und eine Zwischenknotensynchronisierunggebildet wird. Eine LU-Zerlegung in jedem Knoten wird durch Durchführen einerTeilprozess-Parallelverarbeitung ausgeführt.
    [0057] DieseLU-Zerlegung durch eine Teilprozess-Parallelverarbeitung wird durch einerekursive Prozedur mit einer Doppelstruktur ausgeführt, umsie im Cache effizient auszuführen.Insbesondere wird eine primärerekursive Prozedur auf Blöckemit einer Breite bis zu einem spezifischen Wert angewendet. Blöcke miteiner geringeren Breite als dem Wert würden durch Kombinieren einesdiagonalen Teils und eines Teils, der durch gleichmäßiges Teilendes übrigenTeils durch die Anzahl von Teilprozessen für den Zweck einer Teilprozess-Parallelverarbeitungerhalten wird, und durch Kopieren von ihnen zu einem kontinuierlichenArbeitsbereich verarbeitet. Somit werden Daten im Cache effektivverwendet.
    [0058] Dader von allen Knoten gemeinsam genutzte diagonale Blockteil zwischenden Knoten redundant berechnet wird, verschlechtert sich die Parallelverarbeitungseffizienzeiner Zwischenknoten-LU-Zerlegung. Die Zusatzverarbeitung, die dann auftritt,wenn Blöckein jedem Knoten unter Verwendung eines Teilprozesses parallel berechnetwerden, kann durch Ausführeneiner LU-Zerlegung durch eine doppelte rekursive Prozedur reduziertwerden.
    [0059] 7 zeigt den Aktualisierungsprozessder Blöcke,die zugeteilt sind, wie es in den 5 und 6 gezeigt ist.
    [0060] Derin 7 gezeigte äußerste linkeBlock wird durch redundantes Zuteilen von diagonalen Blöcken zujedem Knoten und auch durch Zuteilen von Blöcken, die durch eindimensionalesund gleichmäßiges Teilen der übrigen Blöcke zu einem Arbeitsbereicherhalten. Dies ist der Zustand eines spezifischen Knotens. Eineprimärerekursive Prozedur wird auf Blöckemit der minimalen Breite angewendet.
    [0061] Nachdemdie LU-Zerlegung des minimalen Blocks beendet ist, werden Zeilenblöcke undein Aktualisierungsteil durch gleichmäßiges Teilen des zu aktualisierendenBereichs parallel aktualisiert.
    [0062] DieLU-Zerlegung des minimalen Blockteils wird weiterhin wie folgt ausgeführt, indemder diagonale Blockteil eines Blocks mit der minimalen Breite zudem lokalen Bereich (mit etwa der Größe eines Caches) von jedemTeilprozess kopiert wird und indem auch der übrige Teil durch gleichmäßiges Teilen vonihm kopiert wird.
    [0063] EineLU-Zerlegung wird weiterhin durch eine rekursive Prozedur unterVerwendung dieses Bereichs ausgeführt. Ein Pivot(-Element) wirdbestimmt, und Information zum Umwandeln der relativen Position desPivot-Elements in die relative Position in einem Knoten und einePosition in der gesamten Matrix wird in jedem Teilprozess gespeichert,um Zeilen zu ersetzen.
    [0064] Wenndas Pivot-Element innerhalb des diagonalen Teils des lokalen Bereichseines Teilprozesses angeordnet ist, können sie in jedem Teilprozess unabhängig ersetztwerden.
    [0065] Wennes außerhalbdes diagonalen Blocks angeordnet ist, variiert der Prozess von Blöcken in Abhängigkeitvon der Position.
    [0066] 5.Wenn das Pivot-Element innerhalb des diagonalen Blocks angeordnetist, der redundant zugeteilt wird, wenn Blöcke aufgeteilt und Knoten zugeteilt werden.
    [0067] Indiesem Fall gibt es keine Notwendigkeit für eine Zwischenknotenkommunikation,und Blöcke können injedem Knoten unabhängigverarbeitet werden.
    [0068] 6.Wenn das Pivot-Element außerhalbdes diagonalen Blocks angeordnet ist, wenn Blöcke aufgeteilt und Knoten zugeteiltwerden.
    [0069] Indiesem Fall wird bestimmt, zu welchem Knoten das maximale Pivot-Elementgehört,indem überden maximalen Wert des Pivot-Elements zwischen Teilprozessen kommuniziertwird, d.h. den maximalen Wert im Knoten, und zwar mit allen Knoten. Nacheinem Bestimmen von ihm, werden Zeilen in einem Knoten mit dem maximalenPivot-Element ersetzt. Dann werden die ersetzten Zeilen (Pivot-Zeile) zuden anderen Knoten gerichtet.
    [0070] Derfolgende Pivot-Prozess wird durchgeführt.
    [0071] Einenach einer LU-Zerlegung durch eine rekursive Prozedur mit einerDoppelstruktur durch eine sekundäreTeilprozess-Parallelverarbeitungdoppelt ausgeführtLU-Zerlegung kann parallel zu einer LU-Zerlegung im lokalen Bereichjedes Teilprozesses ausgeführtwerden, währendder oben angegebene Pivot-Ersatz durchgeführt wird.
    [0072] DieVorgeschichte eines Pivot-Ersatzes wird redundant im gemeinsamenSpeicher jedes Knotens gespeichert.
    [0073] Die 8A und 8B zeigen die Prozedur der rekursivenLU-Zerlegung.
    [0074] DieProzedur der rekursiven LU-Zerlegung ist wie folgt.
    [0075] Eswird auf das in 8B gezeigteLayout Bezug genommen. Wenn die LU-Zerlegung des in 8B gezeigten diagonalen Blockteils beendetist, aktualisiert sich U unter Verwendung von L1 wie folgt: U ← L1'U und C ← L × U
    [0076] Dierekursive Prozedur ist ein Verfahren zum Teilen eines Bereichs,auf welchen eine LU-Zerlegung angewendet ist, in eine erstere Hälfte undeine letztere Hälfteund zum rekursiven Anwenden einer LU-Zerlegung auf sie, wobei dieaufgeteilten Bereiche als die Ziele einer LU-Zerlegung angesehenwerden. Wenn eine Blockbreite kleiner als ein spezifischer minimalerWert ist, wird die herkömmliche LU-Zerlegung auf Blöcke miteiner solchen Breite angewendet.
    [0077] Die 8A zeigt einen Zustand,in welchem ein Bereich durch eine dicke Linie in zwei geteilt ist unddie linke Seite im Verlauf einer LU-Zerlegung weiterhin in zweiaufgeteilt wird. Die durch eine dicke Linie geteilte linke Seiteentspricht dem in 8B gezeigtenLayout. Wenn die LU-Zerlegung des Teils C dieses Layouts beendetist, ist auch die LU-Zerlegung der durch die dicke Zeile aufgeteiltenlinken Seite beendet.
    [0078] DerTeil C auf der rechten Seite wird durch Anwenden des in 8B gezeigten Layouts aufden gesamten Block basierend auf dieser Information über dielinke Seite aktualisiert. Nachdem das Aktualisieren beendet ist,wird eine LU-Zerlegung durch gleiches Anwenden des in 8B gezeigten Layouts aufdie rechte Seite ausgeführt.
    [0079] Nacheinem parallelen Ausführeneiner LU-Zerlegung in einen Zustand, in welchem Blöcke Knotenunter Verwendung einer Zwischenknotenkommunikation und einer Teilprozess-Parallelverarbeitungneu zugeteilt sind, werden die diagonalen Blöcke, die in jedem Knoten gemeinsamangeordnet sind, und ein Teil, der durch gleichmäßiges Teilen des übrigen Teilserhalten wird, zurückgelassen,wobei jeder den resultierenden Wert einer LU-Zerlegung hat.
    [0080] Zuerstwerden Zeilen unter Verwendung von Information über die Ersatz-Vorgeschichtedes Pivot-Elements in jedem Knoten und Information über einendiagonalen Block ersetzt. Dann wird ein Zeilenblockteil aktualisiert.Dann wird ein Aktualisierungsteil unter Verwendung eines Spaltenblockteils,der durch Aufteilen des übrigenTeils eines Blocks und eines aktualisierten Zeilenblockteils erhaltenwird, aktualisiert. Ein geteilter Spaltenblockteil, der gleichzeitigmit dieser Berechnung zur Aktualisierung verwendet wird, wird zuseinem benachbarten Knoten in jedem Knoten transferiert.
    [0081] DieserTransfer wird durchgeführt,um Information, die fürein darauf folgendes Aktualisieren nötig ist, gleichzeitig mit derBerechnung zum Vorbereiten füreine darauf folgende Berechnung zu senden, und durch Ausführen diesesTransfers gleichzeitig mit einer Berechnung kann die Berechnungeffizient fortgeführtwerden.
    [0082] ZumDurchführender effektiven Aktualisierung eines Teil-Matrizenprodukts selbst dann, wenn dieAnzahl von Teilprozessen groß ist,wird eine Matrix auf eine solche Weise geteilt, dass der Aktualisierungsbereicheines Matrizenproduktes, der in jedem Teilprozess zu berechnen ist,einem Quadrat nahe kommt. Der Aktualisierungsbereich, der die Leitung einerAktualisierung in jedem Knoten übernimmt,ist ein Quadrat. Die Aktualisierung dieses Bereichs wird von jedemKnoten gemeinsam genutzt, um zu verhindern, dass eine Leistungsverschlechterungauftritt.
    [0083] Zudiesem Zweck wird der Aktualisierungsbereich auf eine solche Weisegeteilt, dass er einem Quadrat so nahe wie möglich wird. Somit kann der zweidimensionalgeteilte Block des Aktualisierungsteils groß gemacht werden, und die Bezugnahmeauf einen Teil, auf den im Verlauf der Berechnung eines Matrizenproduktswiederholt Bezug genommen wird, kann in einem Cache gespeichertwerden und kann vergleichsweise effektiv verwendet werden.
    [0084] Zudiesem Zweck wird eine parallele Berechnung ausgeführt, nachdemjede gemeinsame Nutzung eines Teilprozesses beim Aktualisieren eines Matrizenproduktsin der folgenden Prozedur bestimmt ist. 5.Die Quadratwurzel der Gesamtanzahl #THRD von Teilprozessen wirdberechnet. 6. Wenn dieser Wert keine ganze Zahl ist, wird der Wert biszu nrow gerundet. 7. Die Anzahl einer zweidimensionalen Teilung wird als nrowbezeichnet. 8. Wenn die Anzahl einer eindimensionalen Teilung als ncol angenommenwird, wird die minimale ganze Zahl, die die folgenden Bedingungenerfüllt,gefunden. ncol × nrow ≥ #THRD 9. wenn(ncol·nrow==#thrd)dann Ausführen einerparallelen Aktualisierung in jedem Teilprozess durch Teilen einerMatrix in ncol·nrowdurch eindimensionales und gleichmäßiges Teilen von ihr durchncol und auch durch zweidimensionales und gleichmäßiges Teilenvon ihr durch nrow, und sonst Aktualisieren von #THRD Teilenparallel durch Teilen der Matrix in ncol·nrow durch eindimensionalesund gleichmäßiges Teilenvon ihr und auch durch zweidimensionales und gleichmäßiges Teilenvon ihr durch nrow auf eine solche Weise wie (1,1), (1,2), (1,3),...(2,1), (2,2), (2,3),.... Dann wird allgemein das übrige zueinem Rechteck mit einer langen horizontalen Seite gemacht. Dannwiederum Ausführeneines parallelen Prozesses durch zweidimensionales und gleichmäßiges Teilendes Rechtecks und Teilen eines Aktualisierungsteils auf eine solcheWeise, dass eine Belastung von allen Teilprozessen gemeinsam gleichmäßig genutztwerden kann, und Ende von wenn.
    [0085] 9 zeigt die Aktualisierungvon Unterblöcken,die andere als ein diagonaler Teil sind.
    [0086] DasErgebnis einer LU-Zerlegung wird in jedem Knoten in einem verteiltenund zugeteilten Zustand gespeichert. Jeder Knoten speichert Blöcke mit einervergleichsweise geringen Breite in einem Zustand, in welchem eineLU-Zerlegung auf eine Matrix angewendet worden ist.
    [0087] EineVorwärtssubstitutionund eine Rückwärtssubstitutionwerden auf diesen kleinen Block angewendet, welcher zu seinem benachbartenKnoten, zu welchem ein nachfolgender Block gehört, transferiert und verarbeitetwird. In diesem Fall wird ein Teil, dessen Lösung aktualisiert worden ist,transferiert.
    [0088] Beieiner tatsächlichenVorwärtssubstitution undRückwärtssubstitutionwird eine parallele Aktualisierung durch eindimensionales und gleichmäßiges Teileneines Rechteckteils ausschließlicheines langen diagonalen Blockteils ausgeführt.
    [0089] Zuerstlöst einTeilprozess die folgende Gleichung: LD × BD = BD
    [0090] DurchVerwenden dieser Information aktualisieren alle Teilprozesse B parallelwie folgt: Bi = Bi – Li × BD
    [0091] Eindurch diese Aktualisierung modifizierter Teil von einem Zyklus wirdzu seinem benachbarten Knoten transferiert.
    [0092] Nachdemeine Vorwärtssubstitutionbeendet ist, wird eine Rückwärtssubstitutionauf solche Weise ausgeführt,dass der Prozedur genau umgekehrt gefolgt wird, in welcher eineVerarbeitung bislang zu einem Knoten transferiert worden ist.
    [0093] Tatsächlich wirdein in jedem Knoten der ursprünglichenMatrix angeordneter Teil zyklisch verarbeitet. Dies entspricht einemErsetzen von Spaltenblöckenund einem Umwandeln der Matrix in eine andere Matrix. Dies ist deshalbso, weil im Verlauf einer LU-Zerlegung ein Pivot-Element aus irgendeiner Spalteeines nicht zerlegten Teils extrahiert werden kann. Es entsprichteinem Lösenfür y durchUmwandeln von APP–1x = b durch y = P–1x.In diesem Fall kann durch erneutes Anordnen des gelösten y xberechnet werden.
    [0094] Die 10 bis 12 zeigen den Aktualisierungsprozessvon Zeilenblöcken.
    [0095] Nachdemdie Berechnung von Spaltenblöckenbeendet ist, wird die Anordnung des aktuell berechneten Teils wiederzu dem ursprünglichenhergestellt, der durch zweidimensionales Teilen der Matrix erhaltenist. In diesem Fall werden Daten in der zweidimensional geteiltenForm in jedem Knoten gespeichert. Nachdem Zeilen basierend auf Information über dasErsetzen von Zeilen ersetzt sind, werden Zeilenblöcke aktualisiert.
    [0096] DieAktualisierung wird sequentiell durchgeführt, indem ein Spaltenblockteil,der in jedem Knoten existiert, zu seinem benachbarten Knoten entlangeines Rings gleichzeitig mit einer Berechnung übertragen wird. Dies kann durchVorsehen eines weiteren Puffers realisiert werden. Obwohl in diesemBereich jeder Knoten einen diagonalen Block redundant speichert,wird dieser auch zusammen mit dem Spaltenblockteil transferiert.Das Ausmaß anDaten von Teilen, die andere als ein diagonaler Block sind, istgroß, undsie werden gleichzeitig mit einer Berechnung transferiert. Jedochkann die Transferzeit nicht erkannt werden.
    [0097] Gemäß 11 werden Daten von einem PufferA zu einem Puffer B transferiert. Zu einer darauf folgenden Zeitgabewerden Daten entlang eines Knotenrings vom Puffer B zum Puffer A übertragen bzw.gesendet. Somit werden Daten durch Umschalten des Puffers übertragen.Weiterhin wird in 12 nachder Aktualisierung derselbe Prozess wiederholt auf einen Block angewendet,der durch Reduzieren der Größe einerquadratischen Matrix ausschließlich vonSpalten- und Zeilenblöckenerhalten ist.
    [0098] Die 13 bis 26 sind Ablaufdiagramme, die den Prozessdes bevorzugten Ausführungsbeispiels dervorliegenden Erfindung zeigen.
    [0099] Die 13 und 14 sind die Ablaufdiagramme eines UnterprogrammspLU. Dieses Unterprogramm ist ein Aufrufprogramm und es führt Prozesse durchein Aufrufen nach einem Erzeugen von einem Prozess in jedem Knotenparallel aus.
    [0100] Zuerstwird eine LU-Zerlegung durch Bestimmen der Einheitenanzahl von Blöcken iblksunit,der Anzahl von Knoten numnord und der Größe n eines zu lösenden Problemsibklsunit × numnord × m (m: dieEinheitenzahl von Blöckenvon jedem Knoten) ausgeführt.Das Unterprogramm empfängteinen gemeinsamen Speicherbereich A(k, n/numnord) (k ≥ n), in welchemeine Koeffizientenmatrix A zweidimensional und gleichmäßig geteiltund jedem Knoten zugeteilt wird, und eine ip(n) speichernde Ersatz-Vorgeschichteals Argumente. In einem Schritt S20 wird eine Prozessanzahl (1-Anzahlvon Knoten) in nonord eingestellt, und wird die Anzahl von Knoten(Gesamtanzahl von Prozessen) in numnord eingestellt. In einem SchrittS21 werden Teilprozesse in jedem Knoten erzeugt. Dann werden eineTeilprozessanzahl (1-Anzahl von Teilprozessen) und die Gesamtanzahlvon Teilprozessen jeweils in nothrd und numthrd eingestellt. Ineinem Schritt S22 werden die eingestellte Breite eines Blocks iblksmacro= iblksunit × numnordund die Anzahl einer Wiederholungsschleife = n(iblksunit × numthrd) – 1 berechnet.Weiterhin werden i = 1 und lenbufmax = (n – iblksmacro)/numnord + iblksmacroeingestellt.
    [0101] Ineinem Schritt S23 werden Arbeitsbereiche für wLu1(lenbufmax, iblksmacro),wLu2(lenbufmax,iblksmacro), bufs(lenbufmax, iblksunit), bufd(lenbufmax,iblksunit) gesichert. Jedes Mal, wenn das Unterprogramm ausgeführt wird,wird nur der nötigeTeil dieses Bereichs durch Berechnen der tatsächlichen Länge lenbuf verwendet.
    [0102] Ineinem Schritt S24 wird bestimmt, ob i ≥ Schleife gilt. Wenn die Bestimmungim Schritt S24 ja ist, geht der Prozess weiter zu einem SchrittS37. Wenn die Bestimmung im Schritt S24 nein ist, wird in einemSchritt S25 eine Grenzsynchronisierung unter Knoten gebildet. Dannwird in einem Schritt S26 lenblks = (n – 1 × iblksmacro)/numnord + iblksmacroberechnet. In einem Schritt S27 wird ein Unterprogramm ctob aufgerufen,und die Anordnung in jedem Knoten wird durch Kombinieren des i-tendiagonalen Blocks mit einer Breite iblksunit in jedem Knoten mit einemBlock mit einer Breite iblksmacro, der durch eindimensionales undgleichmäßiges Teilendes zu verarbeitenden Blocks erhalten wird, modifiziert. In einemSchritt S28 wird eine Grenzsynchronisierung unter Knoten gebildet.In einem Schritt S29 wird ein Unterprogramm interlu aufgerufen,in einem Feld wlul gespeichert und wird eine LU-Zerlegung auf denverteilten und erneut zugeteilten Block angewendet. Information über denErsatz von Zeilen wird in ip(is:ie) als is = (i – 1)·iblksmacro + 1, ie = i·iblksmacrogespeichert.
    [0103] Ineinem Schritt S30 wird eine Grenzsynchronisierung unter Knoten gebildet.In einem Schritt S31 wird ein Unterprogramm btoc aufgerufen und wirdein erneut zugeteilter Block, auf welchen eine LU-Zerlegung angewendetworden ist, zur ursprünglichenSpeicherstelle jedes Knotens zurückgebracht. Ineinem Schritt S32 wird eine Grenzsynchronisierung unter Knoten gebildet.In einem Schritt S33 wird ein Unterprogramm exrw aufgerufen undwerden der Ersatz von Zeilen und die Aktualisierung von Zeilenblöcken ausgeführt. Ineinem Schritt S34 wird eine Grenzsynchronisierung unter Knoten gebildet.Im Schritt S35 wird ein Unterprogramm mmcbt aufgerufen und wirdder erneut zugeteilte Block, auf welchen eine LU-Zerlegung angewendetworden ist, unter Verwendung des Matrizenprodukts eines Spaltenblockteils(in wlul gespeichert) und eines Zeilenblockteils aktualisiert. DerSpaltenblockteil wird zwischen Prozessoren entlang dem Ring gleichzeitigmit einer Berechnung transferiert und wird während eines Vorbereitens für eine nachfolgendeAktualisierung aktualisiert. In einem Schritt S36 wird i = i + 1ausgeführt undder Prozess springt zurückzum Schritt S24.
    [0104] Ineinem Schritt S37 wird eine Grenzsynchronisierung gebildet, undin einem Schritt S38 werden die erzeugten Teilprozesse gelöscht. Ineinem Schritt S39 wird ein Unterprogramm fblu aufgerufen und wirdeine Aktualisierung durchgeführt,während dieLU-Zerlegung des letzten Blocks ausgeführt wird. In einem SchrittS40 wird eine Grenzsynchronisierung gebildet, und der Prozess endet.
    [0105] Die 15 und 16 sind die Ablaufdiagramme eines Unterprogrammsctob.
    [0106] Ineinem Schritt S45 empfängtein Unterprogramm ctob A(k,n/numnord), wlul(lenblks,iblksmacro),bufs(lenblks,iblksunit) und bufd(lenblks,iblksunit) als Argumente,und die Anordnung eines Blocks, der durch Addieren eines Blocks,der durch Teilen eines Teils unter dem diagonalen Blockmatrixteileines Bündelsvon numnord der i-tenBlöckemit einer Breite iblksunit in jedem Knoten durch numnord erhalten wird,zu dem diagonalen Block erhalten ist, wird durch diejenige des verteiltenund jedem Knoten zugeteilten Blocks unter Verwendung eines Transfers ersetzt.
    [0107] Ineinem Schritt S46 werden nbase = (i – 1)·iblksmacro (i: Anzahl vonWiederholungen einer Aufruf quellen-Hauptschleife), ibs = nbase+ 1, ibe = nbase, iblksmacro, len = (n – ibe)/numnord, nbase2d = (i – 1)·iblksunitund ibs2d = nbase2d + 1, ibe2d=ibs2d+iblksunit ausgeführt. Indiesem Fall ist die Anzahl von übertragenenDaten lensend = (len + iblksmacro)·iblksunit. In einem SchrittS47 wird iy = 1 zugeordnet und in einem Schritt S48 wird bestimmt, obiy > numnord gilt.Wenn die Bestimmung im Schritt S48 ja ist, geht der Prozess ausdem Unterprogramm hinaus. Wenn die Bestimmung im Schritt S48 neinist, werden in einem Schritt S49 ein Sendeteil und ein Empfangsteilbestimmt. Insbesondere werden idst = mod(nornord – 1 + iy – 1, numnord)+ 1 (Sendezielort-Knotennummer)und isrs = mod(nonnord – 1+ numnord – iy+ 1, numnord) + 1 (Sendequellen-Knotennummer) ausgeführt. Ineinem Schritt S50 werden der diagonale Blockteil mit einer Breiteiblksunit, der jedem Knoten zugeteilt ist, und ein Block, der erhaltenwird durch eindimensionales Teilen seines Blocks, der unter ihmangeordnet ist, durch numnord und der dann gespeichert wird, wenner erneut zugeteilt wird (Transfer-Zielortteil, der in der ansteigenden Reihenfolgeder Anzahl von Knoten angeordnet ist), im unteren Teil des Puffersgespeichert. Insbesondere werden bufd(1:iblksmacro,l:iblksunit) ← A(ibs:ibe, ibs2d:ibe2d),icps – ibe+ (idst – 1)+ len + 1, icpe = isps = isps + len – 1 und bufd(iblksmacro + 1:len+ iblksmacro, 1:iblksunit) ← A(icps:icpe,ibs2d:ibe2d) ausgeführt.Das berechnete Ergebnis wird parallel zu jedem Teilprozess durcheindimensionales Teilen von ihm in die Anzahl von Teilprozessenkopiert.
    [0108] Ineinem Schritt S51 wird das Senden/Empfangen des berechneten Ergebnisseszwischen allen Knoten durchgeführt.Insbesondere sendet jeder Knoten die Inhalte von bufd zu dem idst-tenKnoten und empfängtder idst-te Knoten sie in bufs. In einem Schritt S52 wartet jederKnoten auf das Beenden des Sendens/Empfangens. In einem SchrittS53 bildet jeder Knoten eine Grenzsynchronisierung und in einem SchrittS54 speichert jeder Knoten die von dem isrs-ten Knoten empfangenenDaten in der entsprechenden Position von wlu1. Insbesondere führt jeder Knotenicp2ds = (isrs – 1)·iblksunit+ 1, icp2de = icp2ds; iblksunit – 1 und wlu1(1:len + iblkacro, icp2ds:icp2de) ← bufs(1:len+ iblksunit, 1:iblksunit) aus. Insbesondere führt jeder Knoten ein paralleles Kopierenin jedem Teilprozess durch eindimensionales Teilen der Daten durchdie Anzahl von Teilprozessen aus. In einem Schritt S55 wird iy =iy + 1 zugeordnet, und der Prozess springt zurück zum Schritt S48.
    [0109] Die 17 und 18 sind die Ablaufdiagramm eines UnterprogrammsinterLU.
    [0110] Ineinem Schritt S60 werden A(k, n/numnord), wlu1(lenblks, iblksmacro)und wlumicro(ncash) als Argumente empfangen. In diesem Fall istdie Größe von wlumicro(ncash)dieselbe wie diejenige eines L2-Caches (Cache auf einer Ebene 2) undwird wlumicro(ncache) in jedem Teilprozess gesichert. Ein diagonalerBlock mit einer Breite iblksmacro, der einer LU-Zerlegung zu unterziehen ist, und einervon Blöcken,die durch eindimensionales Teilen eines Blocks erhalten werden,der unter ihm angeordnet ist, werden in einem Bereich wlu1 in jedem Knotengespeichert. Sowohl eine Pivot-Suche als auch das Ersetzen von Zeilenwerden parallel zu der LU-Zerlegung unter Verwendung eines Zwischenknotentransfersausgeführt.Dieses Unterprogramm wird rekursiv aufgerufen. Wenn das Aufrufentiefer eindringt, wird die Blockbreite bei einer LU-Zerlegung kleiner.Wenn dieser Block in jedem Teilprozess parallel einer LU-Zerlegungunterzogen wird, wird ein weiteres Unterprogramm zum parallelenAusführen derLU-Zerlegung injedem Teilprozess aufgerufen, wenn die durch jeden Teilprozess berechneteBlockbreite gleich oder kleiner als die Größe des Caches wird.
    [0111] Beider parallelen Teilprozess-Verarbeitung eines vergleichsweise kleinenBlocks wird dieser diagonale Matrixteil durch jeden Teilprozessgemeinsam genutzt, und der Block wird so kopiert und verarbeitet,dass er in einem Bereich wlumicro verarbeitet werden kann, der kleinerals die Größe des Caches jedesTeilprozesses ist, indem ein eindimensionales und gleichmäßiges Teileneines Teils durchgeführt wird,der unter dem diagonalen Block angeordnet ist. istmicro stellt dieführendePosition eines kleinen Blocks dar, und sie wird anfänglich auf1 eingestellt. widthmicro stellt die Breite eines kleinen Blocksdar, und sie wird zuerst auf die Breite des gesamten Blocks eingestellt.iblksmicromax stellt den maximalen Wert eines kleinen Blocks darund reduziert die Blockbreite dann, wenn die Blockbreite größer alser ist (beispielsweise auf 80 Spalten). nothrd und numthrd stellenjeweils eine Teilprozessnummer und die Anzahl von Teilprozessendar und sie werden in einem eindimensionalen Feld ip(n) gespeichert,das von jedem Knoten gemeinsam als Ersatzinformation genutzt wird.
    [0112] Ineinem Schritt S61 wird bestimmt, ob nwidthmicro ≤ iblksmicromax gilt. Wenn dieBestimmung im Schritt S61 ja ist, wird in einem Schritt S62 durchAusführenvon iblksmicro=nwidthmicro bezüglicheines diagonalen Blocks in einem Bereich jedes Knotens, wo die Belastunggemeinsam genutzt wird und eines Teils wlu(istmicro:lenmacro, istmicro:iblksmicro+ iblksmicro – 1)von wlu(lenmacro, iblksmacro), in welchem ein geteilter Block gespeichertist, ein diagonaler Teil wlu (istmicro:istmicro + iblksmicro – 1, istmicro:istmicro;iblksmicro – 1) alsdiagonaler Block bestimmt. Durch Ausführen von irest = istmicro +iblksmicro wird ein durch eindimensionales und gleichmäßiges Teilenvon wlu(irest:lenmacro, itmicro:istmicro + iblksmicro – 1) erhaltenerTeil mit dem diagonalen Block kombiniert, und die Kombination wirdzu dem Bereich wlumicro jedes Teilprozesses kopiert. Insbesonderewird lenblksmicro = lenmicro + iblksmicro durch Ausführen vonlenmicro = (lenmacro – irest+ numthred)/numthrd und durch Kopieren von wlumicro (lenmicro +iblksmicro, iblksmicro) erhalten. Dann wird in einem Schritt S63ein Unterprogramm Lumicro aufgerufen. Dann ist wlumicro (linmicro;iblksmicro,iblksmicro) gegeben. In einem Schritt S64 wird der diagonale Teildes Teils, der aufgeteilt und wlumicro zugeteilt ist, von wlumicrovon einem Teilprozess zur ursprünglichenStelle von wlu zurückgebracht,und der andere Teil des Teils, der aufgeteilt und wlumicro zugeteiltist, wird von wlumicro von jedem Teilprozess zur ursprünglichenStelle von wlu zurückgebracht.Dann geht der Prozess aus dem Unterprogramm hinaus.
    [0113] Wenndie Bestimmung im Schritt S61 nein ist, wird in einem Schritt S65bestimmt, ob nwidthmicro ≥ 3·iblksmicromaxoder nwidthmicro ≤ 2·iblksmicromaxgilt. Wenn die Bestimmung im Schritt S65 ja ist, werden in einemSchritt S66 nwidthmicro2 = nwidthmicro/2, istmicro2 = istmicro +nwidthmicro2 und nwidthmicro3 = nwidthmicro – niwidthmicro2 ausgeführt undgeht der Prozess zu einem Schritt S68. Wenn die Bestimmung im SchrittS65 nein ist, werden in einem Schritt S67 nwidthmicro2 = nwidthmicro/3,istmicro2 = istmicro + nwidthmicro2 und nwidthmicro3 = nwidthmicro – nwidthmicro2ausgeführtund geht der Prozess zu dem Schritt S68. Im Schritt S68 ruft istmicrodas Unterprogramm durch Geben von nwidthmicro2 als nwidthmicro2zu dem Unterprogramm interLU als nwidthmicro auf.
    [0114] Ineinem Schritt S69 wird ein Teil wlu(istmicro:istmacro + nwidthmicro – 1) aktualisiert. Esist ausreichend, diesen in einem Teilprozess zu aktualisieren. Indiesem Fall wird der Teil wlu(istmicro:istmacro + nwidthmicro – 1) durchMultiplizieren der inversen Matrix der unteren Dreiecksmatrix von wlu(istmicro:istmacro+ nwidthmicro2 – 1, istmicro:istmacro+ nwidthmicro2 – 1)von links mit ihm aktualisiert. In einem Schritt S70 wird wlu(istmicro2:lenmacro,istmicro2:istmicro2 + nwidthmicro3 – 1) aktualisiert durch Subtrahierenvon wlu(istmicro2:lenmacro, istmicro:istmicro2 – 1) × 1lu(istmicro:istmacro+ nwidthmicro2 – 1, istmacro+ nwidthmicro2:istmacro + nwidthmicro – 1) von ihm. In diesem Fallwird eine parallele Berechnung durch eindimensionales und gleichmäßiges Teilenvon ihm durch die Anzahl von Teilprozessen ausgeführt. Ineinem Schritt S71 wird das Unterprogramm interLU durch Zuteilenvon istmicro2 und nwidthmicro3 jeweils als istmicro und nwidthmicro aufgerufen,und das Unterprogramm endet.
    [0115] Die 19 und 20 sind die Ablaufdiagramme eines UnterprogrammsLUmicro.
    [0116] Ineinem Schritt S75 werden A(k,n/numnord), wlul(lenblks,iblksmacro)und wlumicro(leniblksmicro, iblksmicro) als Argumente empfangen. Indiesem Fall wird wlumicro in jedem Teilprozess gesichert, dessenGröße dieselbewie diejenige eines L2-Caches ist. In diese Routine bzw. diesemProgramm wird die LU-Zerlegung eines in wlumicro gespeicherten Teilsausgeführt.ist stellt die führende Positioneines einer LU-Zerlegung zu unterziehenden Blocks dar und ist anfänglich 1.nwidth stellt eine Blockbreite dar und ist anfänglich die gesamte Blockbreite.iblksmax stellt die maximale Anzahl von Blöcken (etwa 8) dar, und einBlock wird niemals in mehr als diese Anzahl geteilt. wlumicro wirdjedem Teilprozess als Argument zugeteilt.
    [0117] Ineinem Schritt S76 wird bestimmt, ob nwidth ≤ iblksmax gilt. Wenn die Bestimmungim Schritt S76 nein ist, geht der Prozess weiter zu einem SchrittS88. Wenn die Bestimmung im Schritt S76 ja ist, wird in einem SchrittS77 i = ist ausgeführtund wird in einem Schritt S78 bestimmt, ob i < istnwidth gilt. Wenn die Bestimmungim Schritt S78 nein ist, geht der Prozess aus dem Unterprogrammhinaus. Wenn die Bestimmung im Schritt S78 ja ist, wird in einemSchritt S79 das i-te Element mit dem maximalen absoluten Wert injedem Teilprozess erfasst und in einem gemeinsamen Speicherbereichin der Reihenfolge von Teilprozessnummern gespeichert. In einem SchrittS80 wird das maximale Pivot-Element im Knoten aus den Elementenerfasst. Dann wird das maximale Pivot-Element in allen Knoten injedem Knoten durch Kommunizieren auf solche Weise bestimmt, dassjeder Knoten jede Gruppe dieses Elements hat, seine Knotennummerund seine Position und das maximale Pivot-Element in alle Knoten in jedem Knotenbestimmt wird. Dieses maximale Pilot-Element wird in jedem Knotendurch dasselbe Verfahren bestimmt.
    [0118] Ineinem Schritt S81 wird bestimmt, ob diese Pivot-Position in einemdiagonalen Block in jedem Knoten ist. Wenn die Bestimmung im SchrittS81 nein ist, geht der Prozess weiter zu einem Schritt S85. Wenndie Bestimmung im Schritt S81 ja ist, wird in einem Schritt S82bestimmt, ob die Position des maximalen Pivot-Elements in einemdiagonalen Block ist, der durch jeden Teilprozess gemeinsam genutztwird. Wenn die Bestimmung im Schritt S82 ja ist, werden in einemSchritt S83 Pivot-Elemente in jedem Teilprozess unabhängig ersetzt,da dies ein Ersatz im diagonalen Block ist, der in allen Knotengespeichert ist, und derjenige in dem diagonalen Block, der vonallen Teilprozessen gemeinsam genutzt wird. Die ersetzten Positionenwerden in einem Feld ip gespeichert und der Prozess geht weiterzu einem Schritt S86. Wenn die Bestimmung im Schritt S82 nein ist,wird das Pivot-Element in einem solchen diagonalen Block durch dasmaximale Pivot-Element in jedem Knoten unabhängig ersetzt. In diesem Fallwird eine zu ersetzende Pivot-Zeile im gemeinsamen Bereich gespeichertund durch den diagonalen Blockteil jedes Teilprozesses ersetzt.Die ersetzte Position wird in einem Feld ip gespeichert und derProzess geht weiter zum Schritt S86.
    [0119] Ineinem Schritt S85 wird ein zu ersetzender Zeilenvektor von einemKnoten mit dem maximalen Pivot-Element durch eine Zwischenknotenkommunikationkopiert. Dann wird die Pivot-Zeileersetzt. Im Schritt S86 wird die Zeile aktualisiert und in einem SchrittS87 werden die Aktualisierungsteile der i-ten Spalte und Zeile aktualisiert. Dannwird i = i + 1 ausgeführtund springt der Prozess zurückzum Schritt S78.
    [0120] Ineinem Schritt S88 wird bestimmt, ob nwidth ≥ 3·iblksmax oder nwidth ≤ 2·iblksmaxgilt. Wenn die Bestimmung im Schritt S88 ja ist, werden in einemSchritt S89 nwidth = nwidth/2 und ist2 = ist + nwidth2 ausgeführt undgeht der Prozess weiter zu einem Schritt S91. Wenn die Bestimmungim Schritt S88 nein ist, werden in einem Schritt S90 nwidth2 = nwidth/3,ist2 = ist + nwidth2 und nwidth3=nwidth-nwidth2 ausgeführt undgeht der Prozess weiter zu einem Schritt S91. Im Schritt S91 wirddas Unterprogramm LUmicro durch Zuteilen von ist und nwidth2 jeweilsals ist und nwidth zu dem Unterprogramm als Argument aufgerufen.In einem Schritt S92 wird ein Teil wlumicro(istmicro:istmacro + nwidth2 –1,istmicro+ nwidth2:istmicro + nwidthmicro – 1) aktualisiert. In diesemFall wird wlumicro(istmicro:istmacro:nwidth2 –1,istmicro + nwidth2:istmicro – nwidthmictro – 1) durchMultiplizieren der inversen Matrix der unteren Dreiecksmatrix vonwlumicro(istmicro:istmacro + nwidthmicro2 – 1, istmicro:istmacro + nwidth2 – 1) vonlinks mit ihm aktualisiert. In einem Schritt S93 wird wlumicro(istmicro2:lenmacro, istmicro2:istmicro2+ nwidthmicro3 – 1)durch Subtrahieren von wlumicro(istmicro2:lenmacro, istmicro:istmicro2 – 1) + wlumicro(istmicro:istmacro+ nwidth2 – 1,ist + nwidth2:ist + nwidthmicro – 1) von ihm aktualisiert.In diesem Fall wird in einem Schritt S94 das Unterprogramm interLUdurch Zuteilen von ist2 und nwidth3 jeweils als ist und nwidth aufgerufen undgeht der Prozess aus dem Unterprogramm hinaus.
    [0121] 21 ist das Ablaufdiagrammeines Unterprogramms btoc.
    [0122] Ineinem Schritt S100 werden A(k, n/numnord), wlul(lenblks, iblksmacro),bufs(lenblks, iblksunit), bufd(lenblks, iblksunit) als Argumenteempfangen, und die Anordnung eines Blocks, der durch Addieren einesBlocks, der durch Teilen eines Teils unter dem diagonalen Blockmatrixteiliblksmacro × iblksmacroeines Bündelsvon numnord der Breite von i-ten Blöcken iblksunit in jedem Knotendurch numnord erhalten wird, zum diagonalen Block erhalten wird,wird durch diejenige des Blocks ersetzt, der verteilt und jedemKnoten zugeteilt ist, und zwar unter Verwendung eines Transfers.
    [0123] Ineinem Schritt S101 werden nbase = (i – 1)·iblksmacro (i = Anzahl vonWiederholungen eines Aufrufens einer Quellen-Hauptschleife), ibs = nbase + 1, ibe= nbase + iblksmacro, len = (n – ibe)/numnord,nbase2d = (i – 1)+ iblksunit, ibs2d = nbase2d + 1 und ibe2d = ibs2d + iblksunit ausgeführt, unddie Anzahl von Sendedaten ist lensend = (len + iblksmacro)·iblksunit.
    [0124] Ineinem Schritt S102 wird iy = 1 ausgeführt und in einem Schritt S103wird bestimmt, ob iy > numnordgilt. Wenn die Bestimmung im Schritt S03 ja ist, geht der Prozessaus dem Unterprogramm hinaus. Wenn die Bestimmung im Schritt S103nein ist, werden in einem Schritt S104 ein Sendeteil und ein Empfangsteilbestimmt. Insbesondere werden idst = mod(nonord –1 + iy – 1, numnord) + 1, isrs = mod(nonord – 1 + y – 1, numnord)+ 1, isrs = mod(nonord – 1numnord – iy + 1,numnord) + 1 ausgeführt.In einem Schritt S105 wird das berechnete Ergebnis von wlu1 zu einemPuffer transferiert und wird dort gespeichert, um übertragenbzw. gesendet zu werden, um die Anordnung von Blöcken zu der ursprünglichen wiederherzustellen.Ein entsprechender Teil wird zu dem idst-ten Knoten übertragen.Insbesondere werden icp2ds = (idst – 1)·iblksunit + 1, ic2de = icp2ds+ iblksunit – 1,bufd(1:len + iblksunit, 1:iblksunit) ← wlul(1:len + iblksmacro,icp2ds:icp2de)ausgeführt. Dasberechnete Ergebnis wird eindimensional durch die Anzahl von Teilprozessengeteilt und wird parallel zu jedem Knoten kopiert.
    [0125] Ineinem Schritt S106 wird das berechnete Ergebnis in allen Knotengesendet/empfangen. Die Inhalte von bufd werden zu dem idst-tenKnoten gesendet und werden in bufs empfangen. In einem Schritt S107wartet der Prozess auf die Beendigung des Sendens/Empfangens undin einem Schritt S108 wird eine Grenzsynchronisierung gebildet.In einem Schritt S109 werden der diagonale Blockteil mit der Breiteiblksunit, der jedem Knoten zugeteilt ist, und der Teil, der durchden Teil ersetzt ist, der durch eindimensionales Teilen eines Blocks,der unter ihm angeordnet ist, durch numnord erhalten wird (Teil,der in der Reihe der Anzahl von Transfer-Zielortknoten angeordnet ist) in ihrenursprünglichenPositionen gespeichert.
    [0126] A(ibs:ibe,ibs2d:ibe2d) ← bufs(1:iblksmacro,1:iblksunit),icps = ibe + (isrs – 1)·len +1, icpe = isps + len – 1,A(icps·icpe,ibs2d.ibe2d) ← bufs(iblksmacro+ 1:iblksmacro, 1:iblk smacro, 1:iblksunit) werden ausgeführt. Dasberechnete Ergebnis wird eindimensional durch die Anzahl von Teilprozessengeteilt und wird fürjede Spalte in jedem Teilprozess kopiert.
    [0127] Ineinem Schritt S110 wird iy = iy + 1 ausgeführt, und der Prozess springtzurückzum Schritt S103.
    [0128] 22 ist das Ablaufdiagrammeines Unterprogramms exrw.
    [0129] DiesesUnterprogramm wird zum Aktualisieren des Ersatzes von Zeilen undder Aktualisierung von Zeilenblöckenverwendet.
    [0130] Ineinem Schritt S115 werden A(k,n/numnord) und wlul(lenblks,iblksmacro)als Argumente empfangen. Der einer LU-Zerlegung unterzogene diagonaleTeil wird in wlul(l:iblksmacro,l:iblksmacro) gespeichert und wirdvon allen Knoten gemeinsam genutzt. nbdiag = (i – 1)·iblksmacro wird ausgeführt. i stelltdie Anzahl von Wiederholungen der Hauptschleife eines aufrufendenQuellen-Unterprogramms pLU dar. Information über einen Pivot-Ersatz wirdin ip(nbdiag + 1:nbdiag + iblksmacro) gespeichert.
    [0131] Ineinem Schritt S116 werden nbase = i·iblksunit (i: die Anzahlvon Wiederholungen der Hauptschleife eines aufrufenden Quellen Quellen-UnterprogrammspLU), irows = nbase + 1, irowe = n/numnord, len = irowe – irows+ 1)/numthrd, is = nbase + (nothird – 1)·len + 1 und ie = min(irowe,is+ len – 1)ausgeführt.In einem Schritt S117 wird ix = is ausgeführt.
    [0132] Ineinem Schritt S118 wird bestimmt, ob is ≤ ie gilt. Wenn die Bestimmungim Schritt S118 nein ist, geht der Prozess weiter zu einem SchrittS125. Wenn die Bestimmung im Schritt S118 ja ist, werden in einemSchritt S119 nbdiag = (i – 1)·iblksmacround j = nbdiag + 1 ausgeführt,und in einem Schritt S120 wird bestimmt, ob j ≤ nbdiag + iblksmacro gilt. Wenndie Bestimmung im Schritt S120 nein ist, geht der Prozess weiterzu einem Schritt S124. Wenn die Bestimmung im Schritt S120 ja ist,wird in einem Schritt S121 bestimmt, ob ip(j) > j gilt. Wenn die Bestimmung im SchrittS121 nein ist, geht der Prozess weiter zu einem Schritt S123. Wenndie Bestimmung im Schritt S121 ja ist, wird in einem Schritt S122A(j,ix) durch A(ip(j),ix) ersetzt, und der Prozess geht weiter zueinem Schritt S123. Im Schritt S123 wird j = j + 1 zugeordnet, undder Prozess springt zurückzum Schritt S120.
    [0133] Ineinem Schritt S124 wird ix = ix + 1 ausgeführt, und der Prozess springtzurückzum Schritt S118.
    [0134] Ineinem Schritt S125 wird eine Grenzsynchronisierung (alle Knoten,alle Teilprozesse) gebildet. In einem Schritt S126 wird A(nbdiag+ lnbdiag + iblksmaco,is:ie) ← TRL(wlul(i:iblksmacro,1.iblksmacro)) × A(nbdiag+ 1:nbdiag + iblksmacro,is:ie) in allen Knoten und in allen Teilprozessenaktualisiert. In diesem Fall stellt TRL(B) den unteren Dreiecksmatrixteileiner Matrix B dar. In einem Schritt S127 wird eine Grenzsynchronisierung(alle Knoten, alle Teilprozesse) gebildet und der Prozess geht ausdem Unterprogramm hinaus.
    [0135] Die 23 und 24 sind die Ablaufdiagramm eines Unterprogrammsmmcbt.
    [0136] Ineinem Schritt S310 werden A(k,n/numnord), wlul(lenblks, iblksmacro),wlu2(lenblks, blksmacro) als Argumente empfangen. Das Ergebnis einerLU-Zerlegung eines Blocks mit einer Breite iblksmacro, der ein Blockist, der durch eindimensionales Teilen von sowohl einem diagonalenBlock als auch einem Block, der unter ihm angeordnet ist, durch numnorderhalten wird, wird in wlu1 gespeichert. Es wird in seiner aufgeteiltenReihenfolge entsprechend seiner Knotennummer erneut Knoten zugeteilt.Dies wird aktualisiert, währenddies entlang dem Ring von Knoten transferiert wird (gleichzeitigesTransferieren mit einer Berechnung) und ein Matrizenprodukt berechnetwird. Da es keinen Einfluss auf die Leistung gibt, wird auch eindiagonaler Blockteil, der nicht direkt für die Berechnung verwendetwird, übertragen, während eineBerechnung ausgeführtwird.
    [0137] Ineinem Schritt S131 werden nbase = (i – 1)·iblksmacro (i: die Anzahlvon Wiederholungen der Hauptschleife eines aufrufenden Quellen-UnterprogrammspLU), ibs = nbase + 1, ibe = nbase + iblksmacro, len = (n – ibe)/numnord,nbase2d(i –1)·iblksunit,ibs2d = nbase2d + 1, ibe2d = ibs2d + iblksunit, n2d = n/numnordund lensend=len:iblksmacro ausgeführt, und die Anzahl von Sendedatenist nwlen=lensend*iblksmacro.
    [0138] Ineinem Schritt S132 werden iy = 1 (Einstellen eines Anfangswerts),idst = mod(nonord,numnord) + 1 (Nummer des übertragenden Zielortknotens(benachbarter Knoten)) isrs = mod(nonnord – 1 + numnord – 1,numnord)+ 1 (Nummer des übertragendenQuellenknotens) und ibp = idst ausgeführt.
    [0139] Ineinem Schritt S133 wird bestimmt, ob iy > numnord gilt. Wenn die Bestimmung imSchritt S133 ja ist, geht der Prozess aus dem Unterprogramm hinaus.Wenn die Bestimmung im Schritt S133 nein ist, wird in einem SchrittS134 bestimmt, ob iy = 1 gilt. Wenn die Bestimmung im Schritt S134ja ist, geht der Prozess weiter zu einem Schritt S136. Wenn dieBestimmung im Schritt S134 nein ist, wartet der Prozess in einemSchritt S135 auf die Beendigung des Sendens/Empfangens. Im SchrittS136 wird bestimmt, ob iy = numnord (die letzte ungerade Zahl) gilt.Wenn die Bestimmung im Schritt S136 ja ist, geht der Prozess weiterzu einem Schritt S38. Wenn die Bestimmung im Schritt S136 nein ist,wird in einem Schritt S137 das Senden/Empfangen des berechnetenErgebnisses durchgeführt.Die Inhalte von wlu1 (einschließlich einesdiagonalen Blocks) werden zu seinem benachbarten Knoten (Knotennummeridst) gesendet, und zu wlu2 gesendete Daten (ab der Knotennummer isrs)werden gespeichert. In diesem Fall ist die Sende/Empfangs-Datenlänge nwlen.
    [0140] Ineinem Schritt S138 wird die Position einer Aktualisierung unterVerwendung von in wlu1 gespeicherten Daten berechnet. ibp = mod(ibp – 1 + numnord – 1,numnord)+ 1 und ncptr = nbe + (ibp –1)·len +1 (eindimensionale Startposition) werden ausgeführt. In einem Schritt S139wird ein Unterprogramm zum Berechnen eines Matrizenprodukts aufgerufen. Zudieser Zeit wird wlu1 gegeben. In einem Schritt S140 wird bestimmt,ob iy=numnord (der letzte Prozess ist beendet) gilt. Wenn die Bestimmungim Schritt S140 ja ist, geht der Prozess aus dem Unterprogramm hinaus.Wenn die Bestimmung im Schritt S140 nein ist, wartet der Prozessin einem Schritt S141 auf die Beendigung des gleichzeitig mit derBerechnung einer Matrizenproduktoperation durchgeführten Sendens/Empfangens.In einem Schritt S142 wird bestimmt, ob iy = numnod – 1 (dieletzte gerade Zahl) gilt. Wenn die Bestimmung im Schritt S142 ja ist,geht der Prozess weiter zu einem Schritt S144. Wenn die Bestimmungim Schritt S142 nein ist, wird in einem Schritt S143 das Senden/Empfangendurchgeführt.Insbesondere werden die Inhalte von wlu1 (einschließlich desdiagonalen Blocks) zu seinem benachbarten Knoten (Knotennummer idst)gesendet. Die zu wlu1 (von der Knotennummer isrs) gesendeten Datenwerden gespeichert. Die Sende/Empfangs-Datenlänge ist nwlen.
    [0141] ImSchritt S144 wird die Position einer Aktualisierung unter Verwendungvon in wlu2 gespeicherten Daten berechnet. Insbesondere werden ibp= mo(ibp – 1+ numnord – 1,numnord)+ 1 und ncptr = nbe + (ibp – 1)·len +1 (eindimensionale Startposition) ausgeführt.
    [0142] Ineinem Schritt S145 wird ein Unterprogramm pmm zum Berechnen einesMatrizenprodukts aufgerufen. Zu dieser Zeit ist wlu2 gegeben. Ineinem Schritt S145 wird 2 addiert und wird iy – iy + 2 zugeordnet. Dann springtder Prozess zurückzum Schritt S133.
    [0143] 25 ist das Ablaufdiagrammdes Unterprogramms pmm.
    [0144] Ineinem Schritt S150 wird A(k, n/numnord), und wlu1(lenblks, iblksmacro)oder wlu2 (lenblks, iblksmacro) in wlux (lenblks, iblksmacro) empfangen. Einquadratischer Bereich wird unter Verwendung einer eindimensionalenStartposition ncptr aktualisiert, die durch eine aufrufende Quellegegeben ist. is2d = i·blksunit+ 1, ie2d = n/numnord, len = ie2d – is2d + 1, isld = ncptr, ield= nptr + len – 1(i: die Anzahl von Wiederholungen eines Unterprogramms pLU), a(isld:ield, is2d:ie2d)= A(isld:ield, is2d:ie2d) –wlu(iblksmacro+ 1:iblksmacro + len, 1·iblksmacro) × A(isld-iblksmacro:isld – 1, isld,is2d:ie2d) (Gleichung 1) werden ausgeführt.
    [0145] Ineinem Schritt S151 wird die Wurzel der Anzahl von Teilprozessenzum Verarbeiten von Blöckenparallel berechnet und aufgerundet. numroot=int(sgrt(numthrd)) wirdausgeführt.Wenn sgrt(numthrd)-numroot nicht Null ist, wird numroot = numroot+ 1 ausgeführt.In diesem Fall bedeutet int, den Bruchteil einer Zahl fallen zulassen und bedeutet sqrt eine Wurzel. In einem Schritt S152 werden m1=numroot,m2 = numroot und mx = m1 ausgeführt. Ineinem Schritt S153 werden m1 = mx, mx = mx – 1 und mm = mx × m2 ausgeführt. Ineinem Schritt S154 wird bestimmt, ob mm < numthrd gilt. Wenn die Bestimmungim Schritt S154 nein ist, springt der Prozess zurück zum SchrittS153. Wenn die Bestimmung im Schritt S154 ja ist, wird in einemSchritt S155 ein zu aktualisierender Bereich eindimensional undgleichmäßig durchml geteilt. Dann wird er zweidimensional durch m2 geteilt. Dannwerden m1xm2 von Rechtecken erzeugt. numthrd von ihnen werden zujedem Teilprozess zugeteilt, und der entsprechende Teil der Gleichung1 wird parallel berechnet. Die Teilprozesse werden zweidimensionalund sequentiell auf eine solche Art wie (1, 1), (1, 2),..., (1,m2), (2, 1),... zugeteilt.
    [0146] Ineinem Schritt S156 wird bestimmt, ob m1·m2 – numthrd > 0 gilt. Wenn die Bestimmung im SchrittS156 ja ist, geht der Prozess weiter zu einem Schritt S158. Wenndie Bestimmung im Schritt S156 nein ist, werden m1·m2 – numthrdab dem rechten Ende der letzten Zeile des letzten Rechtecks nicht aktualisiert gelassen.Dann wird in einem Schritt S157 dieses m1·m2 –numthrd in ein Rechteck kombiniertund wird zweidimensional durch die Anzahl von Teilprozessen numthrdgeteilt. Dann werden entsprechende Teile der Gleichung 1 parallelberechnet. Dann wird in einem Schritt S158 eine Grenzsynchronisierung(zwischen Teilprozessen) gebildet, und der Prozess geht aus demUnterprogramm hinaus.
    [0147] 26 ist das Ablaufdiagrammeines Unterprogramms fblu.
    [0148] Ineinem Schritt S160 werden A(k, n/numnord), wlul(iblksmacro, iblksmacro),bufs(iblksmacro, iblksunit) und bufd(iblksmacro, iblksunit) alsArgumente empfangen, und ein nicht zugeteilter Teil wird zu jedemKnoten gesendet, so dass ein Bündelvon numnord der letzten Blöckemit der Breite iblksunit von jedem Knoten von allen Knoten gemeinsamgenutzt werden kann. Nachdem iblksmacro × iblksmacro von Blöcken vonallen Knoten gemeinsam genutzt sind, wird eine LU-Zerlegung aufdieselbe Matrix in jedem Knoten angewendet. Nachdem die LU-Zerlegungbeendet ist, wird ein jedem Knoten zugeteilter Teil zu jedem Knotenzurückkopiert.
    [0149] Ineinem Schritt S161 werden nbase = n – iblksmacro, ibs = nbase +1, ibe = n, len = iblksmacro, nbase2d = (i – 1)·iblksunit, ibs2d = n/numnord – iblksunit+ 1 und ibe2d = n/numnord ausgeführt.Die Anzahl von Sendedaten ist lensend = iblksmacro·iblksunitund iy = 1 wird zugeordnet.
    [0150] Ineinem Schritt S162 wird das berechnete Ergebnis zum Puffer kopiert.Insbesondere wird bufd(1:iblksmcro, 1:iblksunit) ← A(ibs:ibe, ibs2d:ibe2d)ausgeführt.In einem Schritt S163 wird bestimmt, ob iy > numnord gilt. Wenn die Bestimmung imSchritt S163 ja ist, geht der Prozess weiter zu einem Schritt S170.Wenn die Bestimmung im Schritt S163 nein ist, werden in einem SchrittS164 ein Sendeteil und ein Empfangsteil bestimmt. Insbesondere werdenidst = mod(nonord – 1+ iy – 1),numnord)+ 1, isrs = mod(nonord – 1+ numnord – iy+ 1), numnord) + 1 ausgeführt.In einem Schritt S165 wird das Senden/Empfangen des berechnetenErgebnisses in allen Knoten durchgeführt. Die Inhalte von bufd werdenzu dem idst-ten Knoten gesendet. In einem Schritt S166 werden dieDaten in bufs empfangen, und der Prozess wartet auf die Beendigungdes Sendens/Empfangens. In einem Schritt S167 wird eine Grenzsynchronisierunggebildet, und in einem Schritt S168 werden vom isrs-ten Knoten gesendeteDaten in der entsprechenden Position von wlul gespeichert. Icp2ds= (isrs –1)·iblksunit+ 1, icp2de = icp2ds + iblksunit – 1, wlu(1:iblksmacro, icp2ds:icp2de) ← bufs(1:iblksunit,1:iblksunit) werden ausgeführt.In einem Schritt S169 wird iy = iy + 1 ausgeführt, und der Prozess springtzurückzum Schritt S163.
    [0151] Ineinem Schritt S170 wird eine Grenzsynchronisierung gebildet, undin einem Schritt S171 wird die LU-Zerlegung von iblksmacro × iblksmacro parallelin jedem Knoten ausgeführt.Information über einenZeilenersatz wird in ip gespeichert. Wenn die LU-Zerlegung beendetist, wird das berechnete Ergebnis für den relevanten Knoten zumletzten Block zurückkopiert.Insbesondere werden is=(nonord-1)·iblksunit+1, ie = is + iblksunit – 1, A(ibs:ibe, ibs2d.ibe2d) ← wlul(1:iblksmacro,is:ie) ausgeführt, undder Prozess geht aus dem Unterprogramm hinaus.
    [0152] Blöcke können dynamischund eindimensional geteilt und verarbeitet werden und können unter Verwendungder Information nach einer Zerlegung von jedem Knoten aktualisiertwerden. Ein Transfer kann gleichzeitig mit einer Berechnung durchgeführt werden.Daher kann die Belastung eines Aktualisierungsteils vollständig gleichmäßig aufKnoten aufgeteilt werden, und das Ausmaß an Transfer kann zu einemsolchen reduziert werden, das durch Teilen von ihm durch die Anzahlvon Knoten erhalten wird.
    [0153] Gemäß dem herkömmlichenVerfahren wird das Gleichgewicht der Belastung dann gestört, wenn sichdie Breite eines Blocks erhöht.Jedoch wird gemäß der vorliegendenErfindung deshalb, weil die Belastung gleichmäßig verteilt wird, eine Parallelverarbeitungseffizienzum etwa 10% verbessert. Die Reduzierung bezüglich des Ausmaßes an Transferträgt auchzu der um etwa 3%-igen Verbesserung bezüglich einer Parallelverarbeitungseffizienzbei. Daher kann selbst dann, wenn eine Transfergeschwindigkeit denVergleich mit der Rechenleistung eines SMP-Knotens niedrig ist,weniger Einfluss auf eine Parallelverarbeitungseffizienz erwartetwerden.
    [0154] DurchBerechnen der LU-Zerlegung von Blöcken auf parallele Weise kannnicht nur die Verschlechterung einer parallelen Effizienz aufgrunddes Erhöhensin einem Teil, der nicht parallel verarbeitet werden kann, wennsich die Breite eines Blocks erhöht,kompensiert werden, sondern kann auch eine parallele Effizienz umetwa 10% verbessert werden. Durch Verwenden eines rekursiven Programms,das auf Mikroblöckeabzielt, könnendiagonale Blöcke auchdurch die parallele Operation von SMPs parallel verarbeitet werden.Daher kann die Leistung eines SMP verbessert werden.
    权利要求:
    Claims (7)
    [1] Programm zum Ermöglichen, dass ein Computerein Matrizenverarbeitungsverfahren eines Parallelrechners realisiert,wobei eine Vielzahl von Prozessoren und eine Vielzahl von Knoteneinschließlicheines Speichers überein Netzwerk verbunden sind, wobei das Verfahren die folgenden Schritteaufweist: Verteilen und Zuteilen einer Kombination von Bündeln vonZeilenblöckeneiner Matrix, die zyklisch zugeteilt sind, zu jedem Knoten, um dieKombination der Bündelzu verarbeiten; Trennen einer Kombination von Bündeln vonBlöcken ineinen diagonalen Block, einen Spaltenblock unter dem diagonalenBlock und andere Blöcke; redundantesZuteilen des diagonalen Blocks zu jedem Knoten und auch Zuteilenvon einem von Blöcken,der durch eindimensionales Teilen des Spaltenblocks erhalten ist,zu jedem der Vielzahl von Knoten, während parallel kommuniziertwird; Anwenden einer LU-Zerlegung auf sowohl den diagonalenBlock als auch den zugeteilten Block parallel in jedem Knoten, während zwischenKnoten kommuniziert wird; und Aktualisieren der anderen Blöcke derMatrix unter Verwendung des einer LU-Zerlegung unterzogenen Blocks.
    [2] Programm nach Anspruch 1, wobei die LU-Zerlegungdurch jeden Prozessor jedes Knotens in einer rekursiven Prozedurparallel ausgeführtwird.
    [3] Programm nach Anspruch 1, wobei im Aktualisierungsschritt,währendein Zeilenblock berechnet wird, jeder Knoten Daten, die zu einem berechneten Blockgehörenund zum Aktualisieren anderer Blöcke benötigt werden,parallel zu der Berechnung zu anderen Knoten transferiert.
    [4] Programm nach Anspruch 1, wobei der Parallelrechnerein Parallelrechner vom SMP-knotenverteiltenSpeichertyp ist, in welchem jeder Knoten ein SMP (symmetrischerMultiprozessor) ist.
    [5] Matrizenverarbeitungsvorrichtung eines Parallelrechners,wobei eine Vielzahl von Prozessoren und eine Vielzahl von Knoteneinschließlicheines Speichers überein Netzwerk verbunden sind, welche Vorrichtung folgendes aufweist: eineerste Zuteilungseinrichtung zum Verteilen und Zuteilen einer Kombinationvon Bündelnvon Zeilenblöckeneiner Matrix, die zyklisch zugeteilt sind, zu jedem Knoten, um dieKombination der Bündelzu verarbeiten; eine Trenneinrichtung zum Trennen einer Kombinationvon Bündelnvon Blöckenin einen diagonalen Block, einen Spaltenblock unter dem diagonalen Blockund andere Blöcke; einezweite Zuteilungseinrichtung zum redundanten Zuteilen des diagonalenBlocks zu jedem Knoten und auch zum Zuteilen von einem von Blöcken, derdurch eindimensionales Teilen des Spaltenblocks erhalten ist, zujedem der Vielzahl von Knoten, währendparallel kommuniziert wird; eine LU-Zerlegungseinrichtung zumAnwenden einer LU-Zerlegungauf sowohl den diagonalen Block als auch den zugeteilten Block parallelin jedem Knoten, währendzwischen Knoten kommuniziert wird; und eine Aktualisierungseinrichtungzum Aktualisieren der anderen Blöckeder Matrix unter Verwendung des einer LU-Zerlegung unterzogenen Blocks.
    [6] Matrizenverarbeitungsverfahren eines Parallelrechners,wobei eine Vielzahl von Prozessoren und eine Vielzahl von Knoteneinschließlicheines Speichers überein Netzwerk verbunden sind, welches Verfahren die folgenden Schritteaufweist: Verteilen und Zuteilen einer Kombination von Bündeln vonZeilenblöckeneiner Matrix, die zyklisch zugeteilt sind, zu jedem Knoten, um dieKombination von Bündelnvon Blöckenzu verarbeiten; Trennen einer Kombination von Bündeln vonBlöcken ineinen diagonalen Block, einen Spaltenblock unter dem diagonalenBlock und andere Blöcke; redundantesZuteilen eines diagonalen Blocks zu jedem Knoten und auch Zuteilenvon einem von Blöcken,der durch eindimensionales Teilen des Spaltenblocks erhalten ist,zu jedem der Vielzahl von Knoten, während parallel kommuniziertwird; Anwenden einer LU-Zerlegung auf sowohl den diagonalenBlock als auch den zugeteilten Block parallel in jedem Knoten, während zwischenKnoten kommuniziert wird; und Aktualisieren der anderen Blöcke derMatrix unter Verwendung des eine LU-Zerlegung unterzogenen Blocks.
    [7] Computerlesbares Speichermedium, auf welchem einProgramm aufgezeichnet ist, um einem Computer zu ermöglichen,ein Matrizenverarbeitungsverfahren eines Parallelrechners zu realisieren, wobeieine Vielzahl von Prozessoren und eine Vielzahl von Knoten einschließlich einesSpeichers über einNetzwerk verbunden sind, wobei das Verfahren die folgenden Schritteaufweist: Verteilen und Zuteilen einer Kombination von Bündeln vonZeilenblöckeneiner Matrix, die zyklisch zugeteilt sind, zu jedem Knoten, um dieKombination der Bündelzu verarbeiten; Trennen einer Kombination von Bündeln vonBlöcken ineinen diagonalen Block, einen Spaltenblock unter dem diagonalenBlock und andere Blöcke; redundantesZuteilen des diagonalen Blocks zu jedem Knoten und auch Zuteilenvon einem von Blöcken,der durch eindimensionales Teilen des Spaltenblocks erhalten ist,zu jedem der Vielzahl von Knoten, während parallel kommuniziertwird; Anwenden einer LU-Zerlegung auf sowohl den diagonalenBlock als auch den zugeteilten Block in jedem Knoten, während zwischenKnoten parallel kommuniziert wird; und Aktualisieren der anderenBlöckeder Matrix unter Verwendung des einer LU-Zerlegung unterzogenen Blocks.
    类似技术:
    公开号 | 公开日 | 专利标题
    US10019294B2|2018-07-10|Method of achieving intra-machine workload balance for distributed graph-processing systems
    US5081575A|1992-01-14|Highly parallel computer architecture employing crossbar switch with selectable pipeline delay
    KR100740081B1|2007-07-18|재구성 가능한 연산 장치
    JP5131830B2|2013-01-30|ローカル・レジスタを有する処理要素のアレイ
    US20150304245A1|2015-10-22|Crossbar switch and recursive scheduling
    KR100570137B1|2006-04-12|패킷 흐름을 네트워크 처리 수단에 순서적이고 동적으로분배하는 방법 및 시스템
    JP5514041B2|2014-06-04|識別子割当て方法及びプログラム
    US5521591A|1996-05-28|Switching networks with expansive and/or dispersive logical clusters for message routing
    JP2011505617A|2011-02-24|データ・ストレージ方法、管理サーバ、ストレージ設備及びシステム
    Szymanski1995|"Hypermeshes": Optical Intercomnnection Network for Parallel Computing
    EP2710470B1|2016-12-21|Erweiterbare zentralisierte dynamische ressourcenverteilung in einem geclusterten datengitter
    JP4781089B2|2011-09-28|タスク割り当て方法およびタスク割り当て装置
    CN100364279C|2008-01-23|结构化p2p系统的分布式负载均衡方法
    DE60208252T2|2006-09-07|Vorrichtung für ein Mehrrechnersystem mit einer mehrstufigen Verbindungsanordnung
    US5561768A|1996-10-01|System and method for partitioning a massively parallel computer system
    DE69434421T2|2006-04-27|Mehrdimenzionales verbindungs- und leitwegnetzwerk für einen mpp rechner
    US7644142B2|2010-01-05|Methods and apparatus to perform process placement for distributed applications
    DE112011103497T5|2013-08-14|Informationsverarbeitungssystem, Informationsverarbeitungsvorrichtung, Lastausgleichsverfahren, Planungsverfahren für die Datenbankbereitstellung und Programm zum Durchführen der Verbindungsverteilung für den Lastausgleich in einer verteilten Datenbank
    US7693421B2|2010-04-06|Optical packet buffering device and method
    JPH08320797A|1996-12-03|プログラム制御システム
    EP1696336B1|2009-09-23|Vorrichtung und Verfahren zur Einstellung eines Routingpfades zwischen Routern auf einem Chip
    DE112006000282T5|2008-03-06|Synchronization of data packets for multipoint connections in a multi-level switching system
    EP0398543A1|1990-11-22|Gleichlaufende Mehrstufennetzwerk-Kontrollmethode
    TW201108668A|2011-03-01|Buffered crossbar switch system
    US8819272B2|2014-08-26|Multiprocessor communication networks
    同族专利:
    公开号 | 公开日
    JP2004302928A|2004-10-28|
    JP3983193B2|2007-09-26|
    US20040193841A1|2004-09-30|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    2004-10-28| OP8| Request for examination as to paragraph 44 patent law|
    2011-01-20| 8139| Disposal/non-payment of the annual fee|
    优先权:
    申请号 | 申请日 | 专利标题
    [返回顶部]