Benchmarking Popular SVD libraries and Optimizing and Autotuning RSVD Targeting the Real-Time Applications

Abstract

Parallelle datamaskiner og GPUer tilbyr nå en tidligere utilgjenglig beregningskraft som kan utnyttes for sanntidsapplikasjoner. En slik sanntidsapplikasjon er DAS (Distributed Acoustic Sensing). DAS er spesielt interessant fordi det kan brukes for mange formål, inkludert jordskjelvovervåking og for å finne lekkasjer i undervannsrør. En av de mest tidkrevende delene av signalanalysene knyttet med DAS er SVD-en som brukes til å filtrere ut uønsket støy fra DAS-dataene. Den er spesielt god til å filtrere ut ortogonal signalstøy som genereres av interrogatorsystemer.

I denne oppgaven benchmarker vi ytelsen til populære kodebiblioteker med SVDløsere funnet i Eigen, MKL, PLASMA og MAGMA. Vi implementerer, benchmarker og autotuner også RSVD-en siden den tilbyr en effektiv måte å generere første rang-r-tilnærminger av SVD mens den potensielt forbedrer beregningstid betydelig.

Resultatene våre viser at bruk av PLASMA kan forbedre ytelsen for SVD betydelig over Eigen og MKL på CPU for en 30000x30000 matrise henholdsvis med 11x og 3,8x. Å legge til en GPU i systemet og bruk av MAGMA kan gi en speedup på 40x og 13,8x over Eigen og MKL for samme dimensjoner. I tillegg gir vår RSVD implementering for MAGMA-biblioteket en total speedup på 1067x over mp4096/Eigen RSVD for en 20 000 x 20 000 matrise hvor vi tilnærmer halvparten av singulærverdiene. Dette er betydelig tregere enn Normal Eigen SVD, noe som betyr at bruk av denne RSVD implementering begrenser i stor grad størrelsene på matrisene du kan jobbe med i virkelig-tids beregninger.

Merk at selv en realistisk sammenligning sammen med den beste implementasjonen fra Eigen-bibliotekene sammenlignet med vår beste RSVD-implementering gir fortsatt 127x speedup på grunn av raskere SVD-løsning og nivå 3 GEMMoperasjon- sjoner på GPU mens de har en 9% lavere forskjell i Frobenius-normen enn Eigen RSVD. Dette er for referansen som simulerer den første r = n/8 singulærverdiene for en 20000x20000 matrise. I tillegg er flere forslag til fremtidig arbeid inkludert.

Parallel computers and GPUs now offer unprecedented computational power that can be harnessed for real-time applications. One such application is DAS (Distributed Acoustic Sensing). DAS is especially interesting since it can be used for many applications, including earthquake monitoring, and tracking issues with underwater pipelines. However, due there are several challenges when aiming to use DAS for real-time applications. One of the most time-consuming parts of the signal analyses associated with DAS is the SVD, which is especially good at filtering out orthogonal signal noise that is generated by interrogator systems.

In this thesis, we benchmark the performance of popular implementations of the SVD found in the popular Eigen, MKL, PLASMA, and MAGMA libraries. We also implement, benchmark, and autotune the RSVD (Randomized SVD) since it offers an efficient way of generating the first rank-r approximations of the SVD while potentially significantly improving computational time.Our results show that using PLASMA can significantly improve the performance of the SVD over Eigen and MKL on CPU for a 30000x30000 matrix by 11x and 3.8x, respectively. Adding a GPU and using MAGMA can give a speedup of 40x and 13.8x over Eigen and MKL for the same dimensions. In addition, using our RSVD implementations for the MAGMA library gives a total speedup of 1067x over the mp4096/Eigen RSVD for a 20000 x 20000 matrix where we approximate half the singular values. This is significantly slower than the Normal SVD, which means that using this RSVD implementation greatly limits the sizes of the matrices you can work with for realtime computing.

Note that even a realistic benchmark that provides the best possible implementation from the Eigen libraries compared to our best RSVD implementation still gives a 127x speedup due to faster SVD solving and level 3 GEMM operations on the GPU while having a 9% lower difference in Frobenius norm to the original. This is for the benchmark simulating the first r = n/8 singular values for a 20000x20000 matrix. In addition, several suggestions for future work are included.