Space-Filling Curves for Efficient Algorithms in Scientific Computing
Author:
Bader, Michael Georg
Year:
2008
Document type:
Habilitation
Institution:
Fakultät für Informatik
Language:
en
Subject group:
DAT Datenverarbeitung, Informatik
Abstract:
Raumfüllende Kurven sind stetige, surjektive Abbildungen eines Intervalls in eine mehrdimensionale Teilmenge positiven Rauminhalts. Aus ihrer zumeist rekursiven Konstruktion resultieren starke Lokalitätseigenschaften, die in dieser Arbeit speziell zum Entwurf inhärent speichereffizienter Algorithmen ausgenutzt wurden. Schwerpunkte waren die Entwicklung Cache-effizienter Algorithmen für Matrixoperationen sowie deren Implementierung auf Parallelrechnern mit gemeinsamem oder verteiltem Speicher sowie die Entwicklung eines auf Sierpinski-Kurven basierenden Ansatzes zur numerischen Simulation auf dynamisch adaptiven Diskretisierungsgittern. Beide Ansätze reduzieren die Abhängigkeit der erzielbaren Rechenleistung von der Performance von Speicher- und Kommunikationshardware. Für moderne Rechnerarchitekturen ist dies von grundlegender Bedeutung, da der langsame Zugriff auf lokalen wie auch auf entfernten Speicher zunehmend die erzielbare Leistung limitiert. «
Raumfüllende Kurven sind stetige, surjektive Abbildungen eines Intervalls in eine mehrdimensionale Teilmenge positiven Rauminhalts. Aus ihrer zumeist rekursiven Konstruktion resultieren starke Lokalitätseigenschaften, die in dieser Arbeit speziell zum Entwurf inhärent speichereffizienter Algorithmen ausgenutzt wurden. Schwerpunkte waren die Entwicklung Cache-effizienter Algorithmen für Matrixoperationen sowie deren Implementierung auf Parallelrechnern mit gemeinsamem oder verteiltem Speicher sow... »