Primitive Elemente der linearen Algebra für die Geometrieverarbeitung: Wirklich erschwingliche Höchstleistung
Geometrische Daten stehen im Mittelpunkt von Schlüsselanwendungen, die vom künstlerischen Design bis zur wissenschaftlichen Datenverarbeitung, von den Nanowissenschaften bis zum Geo-Engineering reichen. Die Fähigkeit, mit solchen Daten effizient numerische Berechnungen durchzuführen, ist der Schlüssel zu einer Leistungssteigerung, die all diesen Bereichen zugute käme. Hochleistungsberechnungen waren für geraume Zeit auf den Einsatz von Supercomputern beschränkt, aber da sich die Computerlandschaft drastisch in Richtung allgegenwärtige Parallelität verändert, sind billigere Mehrkernprozessoren und leistungsstarke Grafikhardware mit Tausenden von Kernen (GPUs) für die breite Öffentlichkeit zugänglich geworden. Leider bleibt die Rechenleistung dieser leistungsstarken Einheiten weitgehend ungenutzt, insbesondere im Umgang mit geometrischen Daten. Leistungssteigerungen beschränken sich oft auf beschämend parallele Aufgaben oder erfordern einen speziellen plattformspezifischen Entwicklungsaufwand für jeden einzelnen Algorithmus. Unsere Forschung zielt darauf ab, die Geometrieverarbeitung von Grund auf intuitiv und plattformunabhängig zu gestalten.
Die wohl gebräuchlichsten geometrischen Darstellungen sind Netze. Ihre Fähigkeit, beliebige Freiformflächen zu erfassen, hat sie längst zu einer vielseitigen, fachübergreifenden Repräsentation gemacht. Der direkte Zugriff auf Konnektivitätsinformationen und Traversal erfordert seit langem umfangreiche verknüpfte Listendatenstrukturen, die bei Varianten wie winged-edge oder half-edge bekannt sind. Auf moderner Hochleistungs-Computerhardware ist die gängige Beschreibung durch diesen Typ Zwischenstrukturen nicht mehr geeignet, da der zum einen der Speicherzugriff ineffizient erfolgt und, noch wichtiger, die Speicherkapazität z.B. von Grafikkarten an ihre Grenzen stößt. Daher ist es dringend erforderlich, das Problem der Netzverkettung grundlegend zu überdenken.
Aus unserer Sicht liegt der Schlüssel zur Bereitstellung einer einfachen Schnittstelle in der Wahl des richtigen Abstraktionsgrades. Unser Ziel ist es, einer Mehrheit von Praktizierenden und Neueinsteigern eine Darstellung zu bieten, die ihnen vertraut ist und es ihnen ermöglicht, sie auf intuitive Weise zu manipulieren. Unsere algorithmische Formulierung konzentriert sich auf Objekte wie Matrizen, Vektoren und Permutationen und wirkt durch Operationen wie Multiplikation von dünnbesetzten Matrizen mit Vektoren oder anderen Matrizen sowie Kartierungen. Diese Darstellung durch lineare Algebra dient mehreren Zwecken:
- Kompaktheit und Lesbarkeit. Algorithmen sind kompakt und leichtverständlich. Der Verzicht auf Zwischendatenstrukturen reduziert das Aufblähen vom Programmcode und vergrößert die Zugänglichkeit.
- Wiederverwendbarkeit. Die gleichen Verfahren, die auch für die numerische Optimierung verwendet werden, können auch für die Netzverarbeitung eingesetzt werden.
- Leistung. Datenzugriffsmuster können die Leistung des Cache und des Speichers stark beeinträchtigen. Array-basierte Algorithmen zeigen Datenzugriffsmuster auf und lassen sich leicht optimieren.
Die Darstellung beliebiger unstrukturierter Gitter als dünnbesetzte Matrizen, auch bekannt als Mesh-Matrix, senkt nicht nur den Speicherbedarf, sondern verschlankt auch den Großteil der Datenbewegungen vom globalen Speicher zu den Recheneinheiten. Durch diese Darstellung wird Hochleistungsberechnung mittels linearer Algebra-Kernel ermöglicht. Die Kompaktheit und Effektivität dieser Darstellung ermöglicht die Kodierung komplexer Operationen in einfachem, menschenlesbarem und leistungsfähigem Code. Ein typisches Beispiel ist in Abbildung 1 dargestellt.
Abbildung 1: Ein Netz (links) und sein Dual (rechts). Mit Hilfe der Mesh-Matrix-Darstellung kann das Dualgitter einfach aus dem Produkt der transponierten binären Form der Gittermatrix mit sich selbst gewonnen werden.
Unsere Strategie für den Einsatz in allen Anwendungen konzentriert sich auf mehrere Aspekte:
Direkte Anpassung: Viele bestehende Algorithmen sind so einfach, dass sie fast wörtlich in die Sprache der linearen Algebra übersetzt werden können. In dieser Hinsicht sind die Leistungssteigerungen unmittelbar und die Lernkurve ist sehr flach.
Algorithmische Neuinterpretation: Aufwändigere Algorithmen, die erhebliche Änderungen der Konnektivität mit sich bringen, können nicht direkt übersetzt werden. Um Steigerungen der Rechenleistung zu erzielen, ist eine Neuformulierung bestehender Algorithmen innerhalb der linearen Algebra notwendig.
Typische Beispiele aus unserer Forschung sind Unterteilungsoberflächen, die in der Modellierung weit verbreitet sind und sich zu einem unverzichtbaren Produktionsmittel in der Spielfilmindustrie entwickelt haben. Unser Ansatz ist weitaus besser als OpenSubdiv, das in Industrie wie Wissenschaft weitgehend als State-of-the-Art angesehen wird.
Neue Abstraktion: Viele existierende algorithmische Lösungen stammen aus den Anfängen der elektronischen Datenverarbeitung, in denen die damalige Hardware die Art erfolgreicher Algorithmen bestimmte. Infolgedessen wird der serielle Charakter einer ursprünglichen algorithmischen Abstraktion selten in Frage gestellt. Bemühungen um Leistungssteigerung innerhalb dieses Rahmens sind meist wenig erfolgreich, hier ist eine Re-Abstraktion des Problems vonnöten. Ein typisches Beispiel ist die Erzeugung von Voronoi-Diagrammen (VD) auf Oberflächen und deren Varianten wie z.B. zentroide Voronoi-Parkettierungen (CVT), wie man sie mit dem Lloyd's-Algorithmus erhält. Unsere Lösung abstrahiert die Probleme als natürliche Teilung, die sich als Lösung eines zeitabhängigen Satzes von partiellen Differentialgleichungen ergibt; diese beschreiben die sich gleichzeitig entwickelnden Fronten auf einer Oberfläche wie in Abbildung 2 dargestellt. Auf diese Weise können große komplexe geometrische Modelle effizient auf Grafikhardware verarbeitet werden, was zu bisher unerreichbaren Ergebnissen führt, siehe Abbildung 3. Ein weiteres Beispiel ist die Matrixanordnung in der Finite-Elemente-Analyse (FEA). Diese Operation ist grundlegend für die Sammlung elementarer Beiträge innerhalb der globalen Systemmatrix. Unsere Re-Abstraktion des Problems ermöglicht es, das (???) Montageproblem als eine Multiplikation zweier dünn besetzter Matrizen zu formulieren. Auf diese Weise erschließen wir direkt die leistungsstarken Möglichkeiten der linearen Algebra und erzielen erhebliche Leistungssteigerungen.
Abbildung 2: Veranschaulichung des Wachstums natürlicher Parkettierungen (ein alternatives numerisches Modell zu Voronoi-Diagrammen auf Oberflächen) auf dem Earhart-Fluganzug (10Mio Facettennetz, mit freundlicher Genehmigung der Smithsonian Instituts): Initialisierung mit 10.000 zufälligen Wachstumskeimen; deren entsprechende Zellen sind in verschiedenen Farben visualisiert.
