Verlag des Forschungszentrums Jülich
JUEL-4211
Hofmann, Michael
Paralleles Sortieren am Beispiel der schnellen Multipolmethode
76 S., 2006
Paralleles Sortieren am Beispiel der schnellen
Multipolmethode
Die schnelle Multipolmethode (FMM) ist eine linear skalierende Methode zur Berech-nung
langreichweitiger Wechselwirkungen. Im Rahmen einer parallelen Implementierung
der FMM (am Zentralinstitut für Angewandte Mathematik des Forschungszentrums
Jülich), werden linear skalierende parallele Sortierverfahren benötigt. Durch die Verwen-dung
der FMM, beispielsweise als Unterprogramm in Molekulardynamiksimulationen,
ergeben sich weitere Anforderungen. Diese betreffen unter anderem Einschränkungen
bei der Verwendung von zusätzlichem Hauptspeicher, die Handhabung der Eingabeda-ten
und die Bereitstellung der Ausgabedaten. Im Verlauf der Arbeit wird gezeigt, wie sich
sequentielle und parallele Sortierverfahren mit Laufzeitkomplexität O(n) und Speicher-komplexität
O(1) realisieren lassen. Zum Abschluss wird das Konzept einer Programm-bibliothek
vorgestellt, welche die implementierten Sortierverfahren beinhaltet. Damit ist
es möglich, die verwendeten Verfahren einfach an Erfordernisse anderer Anwendungen
anzupassen und unabhängig von der FMM einzusetzen.
Parallel sorting within an implementation of the Fast
Multipole Method
The fast multipole method (FMM) evaluates Coulomb interactions with linearly sca-ling
computational complexity. A parallel implementation of the FMM (developed at
the Central Institute for Applied Mathematics at the Research Centre Jülich) requires
linearly scaling methods for parallel sorting. Additional requirements arise due to the
usage of the FMM, for example as part of molecular dynamics simulations. They con-cern
the restricted use of memory, the handling of the input data and the preparation
of the output data. It is shown, how to achieve sequential and parallel sorting with time
O(n) and space O(1) complexity. Finally a library for sorting methods is introduced, to
provide flexible and easy to use parallel sorting for applications besides the FMM too.
Neuerscheinungen
Schriften des Forschungszentrums Jülich
Ihre Ansprechperson
Heike Lexis
+49 2461 61-5367
zb-publikation@fz-juelich.de