Book/Report

FZJ-2018-02726

http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png Entwicklung der Grundlagen einer Theorie paralleler partitionierter Algorithmen unter besonderer Berücksichtigung partitionierter Netzwerkalgorithmen

Vogell, T. (Corresponding author)FZJ*

1986
Kernforschungsanlage Jülich, Verlag Jülich

Please use a persistent id in citations: http://hdl.handle.net/2128/18383

Report No.: Juel-2108

Abstract: Im Rahmen der Theorie paralleler Algorithmen sind eine Vielzahl von Algorithmen zur Lösung von Problemen der Größe n für theoretische Prozessor-anzahlfunktionen p(n) entwickelt worden. Zusammenstellungen einiger wesentlicher paralleler Algorithmen aus den Bereichen der Linearen Algebra, der Graphen- und Sortieralgorithmen finden sich beispielsweise in [10], [21], [2} und [11]. Die Annahme eines unbeschränkten Parallelismus ermöglicht es, sehr schnelle Algorithmen zu entwickeln, jedoch um den Preis einer großen Prozessoranzahl, die häufig keine praktische Relevanz besitzt. Dieser theoretischen Behandlung paralleler Algorithmen stehen die Restriktionen gegenüber, die sich aus der vorhandenen Technologie ergeben. Hierzu gehören vor allem die Beschränkung der Prozessoranzahl sowie dieOrganisation des Datenaustausches zwischen den Prozessoren. Ein Ziel ist die Abbildung der theoretisch entwickelten Algorithmen auf die real verfügbaren Parallelrechner, so daß ein möglichst geringer Zeitverlust erfolgt. Um dies zu ermöglichen, ist es sinnvoll, die wesentlichen technologischen Restriktionen in die Theorie paralleler Algorithmen zu integrieren. Unser Ausgangspunkt ist die Beschränkung der Prozessoranzahl. Parallele Algorithmen für eine fest vorgegebene Prozessorzahl p können aus den theoretischen Algorithmen für p(n) Prozessoren gewonnen werden, indem die Algorithmen "partitioniert " werden. Der Begriff der Partitionierung wird in der Literatur nicht einheitlich verwendet. In Bezug auf Algorithmen werden zwei verschiedene Methoden damit bezeichnet. In [18] werden parallele Algorithmen partitioniert, um sie optimal auf systolische Felder beschränkter Größe abzubilden. Konkret wird in diesem Fall der Indexraum des Algorithmus in Teilräume zerlegt, die dann den einzelnen Prozessoren zugeordnet werden. Dies entspricht einer Partitionierung der Menge der vom Algorithmus auszuführenden Operationen.Die in [14] beschriebenen partitionierten Algorithmen dienen dem Zweck, Chips, die zur Berechnung elementarer Matrix-Operationen für kleine Blockmatrizen entwickelt worden sind, einzusetzen. Obwohl die Arbeit [18] [...]

---

Contributing Institute(s):

1. Publikationen vor 2000 (PRE-2000)

Research Program(s):

1. 899 - ohne Topic (POF3-899) (POF3-899)

---

Database coverage:

---