Detailansicht
Space-filling curves for improved cache-locality in shared memory environments
Martin Albin Perdacher
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Dr.-Studium der technischen Wissenschaften (DissG: Informatik)
Betreuer*innen
Claudia Plant ,
Christian Böhm
DOI
10.25365/thesis.69593
URN
urn:nbn:at:at-ubw:1-16304.22837.346769-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Heutige Mikroprozessoren bestehen aus mehreren Kernen, von denen jeder mehr\-ere Additionen, Multiplikationen oder andere Operationen gleichzeitig in einem Taktzyklus ausführen kann. In Shared Memory Architekturen müssen zumindest zwei Arten von Parallelität angewendet werden, um die maximale Leistung des Algorithmus auszunutzen: MIMD (Multiple Instruction Multiple Data), bei dem jeder Kern gleichzeitig verschiedene Operationen an verschiedenen Typen von Eingangsdatenströmen ausführt, und SIMD (Single Instruction Multiple Data), bei dem innerhalb eines Kerns dieselbe Operation an verschiedenen Daten gleichzeitig ausgeführt wird. Zusätzlich bieten moderne Mikroprozessoren eine reichhaltige Speicherhierarchie mit verschiedenen Ebenen der Caches für jedes der Register. Einige dieser Speicher (wie Hauptspeicher, L3-Cache) sind groß, aber langsam und werden von allen Kernen gemeinsam genutzt. Andere (Register, Cache-Zeilen, L1-Cache) sind schnell und ausschließlich einem einzigen, aber kleinen Kern zugeordnet. Nur wenn die Datenzugriffe eine hohe Lokalität haben, können übermäßige Datentransfer zwischen den Elementen der Speicherhierarchie vermieden werden. Algorithmen in der linearen Algebra werden oft durch drei oder mehreren verschachtelte Schleifen definiert. In dieser Arbeit schlagen wir vor, solche Schleifen in einer Reihenfolge zu durchlaufen, die durch eine raumfüllende Kurve, wie z.B. die Hilbert- oder die Morton-Ordnung definiert ist. Die in dieser Arbeit verwendeten Low-Level-Kernel basieren auf Advanced Vector Extensions (AVX), die die Ausnutzung auf mehreren Ebenen der Parallelität in gemeinsam genutzten Speicherumgebungen ermöglichen. Wir wenden unsere raumfüllenden Kurven in verschiedenen Algorithmen an, die von linearer Algebra (Matrix-Multiplikation, Cholesky-Zerlegung, LU-Faktorisierung) oder Clustering (K-means) bis hin zu Datenbankabfragen (d.h. Similarity Join) reichen.
Abstract
(Englisch)
Today's microprocessors consist of multiple cores each of which can perform multiple additions, multiplications, or other operations simultaneously in one clock cycle. In shared memory environments at least two types of parallelism must be applied to exploit the maximum performance of the algorithm: MIMD (Multiple Instruction Multiple Data) where each core simultaneously perform different operations on different types of input data streams and SIMD (Single Instruction Multiple Data) where within a core, the same operation is executed at once on various data. Additionally, modern microprocessors offer a rich memory hierarchy, including various levels of cache and registers. Some of these memories (like main memory, L3 cache) are big but slow and shared among all cores. Others (registers, cache lines, L1 cache) are fast and exclusively assigned to a single core but small. Only if data access has a high locality, we can avoid excessive data transfers between the different levels of the memory hierarchy. Algorithms in linear algebra are often defined by three or more nested loops. In this thesis, we propose to traverse such loops in an order defined by a space-filling curve, such as the Hilbert or the Morton-order curve. The low-level kernels used in this work are based on Advanced Vector Extensions (AVX), which allow the exploitation of several levels of parallelism in shared memory environments. We apply our space-filling curves in several algorithms ranging from linear algebra (matrix-multiplication, Cholesky decomposition, LU factorization) or clustering (K-means) as well as in database queries (i.e., similarity join).
Schlagwörter
Schlagwörter
(Englisch)
Space-Filling curves Memory Hierarchy Hilbert Curve Morton-order
Schlagwörter
(Deutsch)
Raumfüllende Kurven Speicherhierarchie Hilbert Kurve Morton Ordnung
Autor*innen
Martin Albin Perdacher
Haupttitel (Englisch)
Space-filling curves for improved cache-locality in shared memory environments
Publikationsjahr
2020
Umfangsangabe
xix, 176 Seiten : Illustrationen, Diagramme
Sprache
Englisch
Beurteiler*innen
Nikolaus Augsten ,
Sascha Hunold
AC Nummer
AC16136879
Utheses ID
58087
Studienkennzahl
UA | 786 | 880 | |