SPLATT: Effiziente und parallele spärliche Tensor-Matrix-Multiplikation

Mehrdimensionale Arrays oder Tensoren finden sich zunehmend in Bereichen wie der Signalverarbeitung und Empfehlungssystemen. Reale Tensoren können enorm groß und oft sehr spärlich sein. Es besteht Bedarf an effizienten, leistungsstarken Werkzeugen, die in der Lage sind, die massiven spärlichen Tensoren von heute und morgen zu verarbeiten. Dieses Papier stellt SPLATT vor, eine C-Bibliothek mit Shared-Memory-Parallelsystemen für dreidimensionale Tensoren. SPLATT enthält algorithmische Verbesserungen im Vergleich zu konkurrierenden, hochmodernen Werkzeugen für die spärliche Tensorfaktorierung. SPLATT hat ein schnelles, paralleles Verfahren zur Multiplikation eines Matrizen-Tensors durch ein Khatri-Rao-Produkt, welches ein Schlüssel-Kernel in Methoden der Tensorfaktorierung ist. SPLATT verwendet eine neuartige Datenstruktur, die die Sparsamkeitsmuster von Tensoren ausnutzt. Diese Datenstruktur hat einen kleinen Speicherbedarf ähnlich den konkurrierenden Methoden und ermöglicht die in unserer Arbeit vorgestellten rechnerischen Verbesserungen. Wir präsentieren auch eine Methode zur Auffindung von cachefreundlichen Neuordnungen und deren Nutzung mit einer neuartigen Form der Cache-Tiling. Soweit wir wissen, ist dies die erste Arbeit, die Neuordnungen und Cache-Tiling in diesem Kontext untersucht. SPLATT vermittelt im Vergleich zu unserer Basislinie eine durchschnittliche Beschleunigung von fast 30x bei der Verwendung von 16 Threads und erreicht über 80x Beschleunigung auf NELL-2.