Code meiner Bachelorarbeit zum hybriden Konstruiren von Wavelet Trees. Die Konstruktion geschieht mithilfe einer Domain Decomposition. Dafür wird MPI und openMP verwendet. Basiert auf https://github.com/pdinklag/distwt/ und https://github.com/kurpicz/pwm/.
Für die Theoretischen Grundlagen siehe Constructing the Wavelet Tree and Wavelet Matrix in Distributed Memory [Dinklage et al., ALENEX 2020] und Simple, Fast and Lightweight Parallel Wavelet Tree Construction[Kurpicz et al.]
Das Projekt ist ein CMake Projekt, welches einfach mit
mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
make
gebaut werden kann. Dabei werden zwei Programme gebaut, welche unter build/src/ gefunden werden können. Einmal hpwt_ppc, welches den Parallel Prefix Counting Algorithmus zur lokalen Konstruktion verwendet. Desweiteren wird das hpwt_pps Programm gebaut, welches einen Parallel Prefix Sorting Algorithmus zur lokalen Konstruktion verwendet. Das hpwt_ppc Programm war in allen Test schneller und sollte immer verwendet werden.
Neben MPI und openMP wird noch tlx benötigt, welches manuell zuerst installiert werden muss.
- Als minimales Argument wird die Eingabedatei erwartet, für welche der Wavelet Tree berechnet werden soll.
- Soll der berechnet Baum auch gespeichert werden, kann
-o /path/to/fileals Argument genutzt werden. - Des Weiteren ist es möglich nur einen Präfix der Eingabe zu verwenden, dieser kann mit
-p 1Giangegeben werden, um z.B. nur das erste Gibibyte der Eingabe zu verwenden. - Mit
-w 1kann angegeben werden wie viele Bytes pro Eingabezeichen verwendet werden sollen. Valide Größen sind1, 2, 4, 5. - Sollte der finale Wavelet Tree überprüft werden, ob dieser korrekt konstruiert wurde, kann das Programm mit
-vgestartet werden. Dabei ist es notwendig den Wavelet Tree vorher zu Speichern, also das Programm mit-ozu starten. - Des Weiteren kann mit
-r Xfestgelegt werden, in wievielen Byte Blöcken die Eingabe gelesen werden soll. WobeiXeine valide Größe wie1Giist.