Bonelli, A. (2006). SPIRAL/DMP: A generator for optimized parallel signal transforms [Dissertation, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-18892
Die diskrete Fourier-Transformation (DFT) stellt eines der bedeutendsten mathematischen Werkzeuge in den Naturwissenschaften und der Technik dar. Sie ist aus einem überaus breiten Spektrum von Anwendungen, wie z.B. der Lösung partieller Differentialgleichungen der Physik, nicht wegzudenken. Andere Anwendungsgebiete findet man z.B. in der Geophysik, in den verschiedensten Formen der digitalen Signalverarbeitung, wie etwa der digitalen Bildverarbeitung, oder nicht zuletzt bei der Proteinfaltung in der Molekularbiologie.<br />Lange wurde vermutet, dass die Komplexität der DFT bei O(N 2) läge. 1965 veröffentlichten Cooley und Tukey einen Algorithmus, der als die schnelle Fourier-Transformation (fast Fourier transform, FFT) bekannt wurde. Dieser Algorithmus vermindert die Komplexität der DFT von O(N 2) auf O(N log N). Die Leistung von Algorithmen für einen Prozessor wird im Allgemeinen an der Anzahl der vom Prozessor ausgeführten Arbeitsschritte pro Zeiteinheit gemessen. Bei Programmen für parallele Rechnerarchitekturen geht auch die Zeit, die für den Datenaustausch zwischen den Prozessoren benötigt wird, maßgeblich in die Leistungsbewertung ein. Dabei hängt das Verhältnis zwischen der Rechen- und der Kommunikations-Leistung sehr stark vom verwendeten Computersystem ab.<br />Die vorliegende Arbeit stellt SPIRAL/DMP vor, ein Software-System zum automatischen Generieren und Optimieren von Algorithmen und Codes für die effiziente Ausführung der DFT auf Parallelrechnern. SPIRAL/DMP wurde als Erweiterung des Programm-Generierungs- und Optimierungs-Systems SPIRAL implementiert. Basis dieses Systems ist die Darstellung von DFT-Algorithmen in der problem-spezifischen Sprache SPL. SPIRAL wurde mit Hilfe eines Markierungs- und Formel-Manipulations-Systems erweitert, um parallele Algorithmen darstellen, herleiten und optimieren zu können.<br />SPIRAL/DMP hat die besondere Eigenschaft, skalierende DFT-Algorithmen generieren zu können, die in der Lage sind, eine automatische Datenumverteilung auf die optimale Anzahl an Prozessoren durchzuführen, um den Kommunikationsaufwand so weit wie möglich zu senken. Eine Besonderheit des neu entwickelten Verfahrens liegt darin, dass die Umverteilung der Daten während der, für die Berechnung der DFT unvermeidlichen Kommunikation durchgeführt wird, und dadurch keine zusätzlichen Kommunikationsschritte notwendig sind. SPIRALs Suchmechanismus findet heraus, welche der möglichen Algorithmen und deren Implementierungen auf einer gegebenen Plattform die besten Leistungswerte erzielen. Auf diese Weise wird plattformoptimierter DFT-Code automatisch erzeugt. Experimente mit den von SPIRAL/DMP generierten MPI-Programmen ergaben mit den skalierenden DFT-Algorithmen eine Leistungssteigerung von bis zu 30%.<br />
de
The discrete Fourier transform (DFT) is one of the principal algorithmic tools in the field of scientific computing. DFT methods can be used to solve various problems in science and engineering. For example, the DFT is an essential tool in digital signal processing.<br />Moreover, DFT methods are heavily used for the numerical solution of partial differential in mathematical physics, like the ones arising in computational fluid dynamics. Other applications of DFT methods occur in geophysical research, vibration analysis, speech recognition and synthesis, protein folding etc.<br />The order of complexity of the DFT was long thought to be O(N 2), as the DFT requires the evaluation of a special matrix-vector product. In 1965 Cooley and Tukey published an algorithm, the fast Fourier transform (FFT), which reduced the DFT's computational complexity to O(N log N).<br />Since then numerous studies have been published on how to implement the FFT on advanced computer systems efficiently.<br />The performance of numerical algorithms for single processors is usually characterized by the number of processor cycles per time unit, measured during its execution. The performance of parallel programs is influenced by an additional factor, i.e., the time needed for data communication.<br />The major difficulty in developing efficient code for parallel systems is the machine dependent ratio of processor and network performance.<br />This work introduces SPIRAL/DMP, a formal framework for automatically generating performance optimized implementations of the DFT for distributed memory computers. SPIRAL/DMP is an extension of the program generation and optimization system SPIRAL. DFT algorithms are represented as mathematical formulas in SPIRAL's internal language SPL.<br />Using a tagging mechanism and formula rewriting, SPIRAL has been extended to automatically generate parallelized formulas.<br />SPIRAL/DMP has been used to generate rescaling DFT algorithms, which redistribute the data in intermediate steps to the optimal number of processors to reduce communication overhead. It is a novel feature of the methods implemented in SPIRAL/DMP that redistribution steps are merged with communication steps to avoid additional communication overhead. Among the multitude of possible algorithm variants, SPIRAL's search mechanism determines the fastest one for a given platform, hence effectively generates hardware adapted code without human intervention. Experiments with DFT MPI programs generated by SPIRAL/DMP demonstrate that the new methods enable performance gains of up to 30%.