Florian Kurpicz
Presentation at SPIRE 2019

SACABench: Benchmarking Suffix Array Construction

Today, I presented our results on benchmarking suffix array construction algorithms at SPIRE 2019. The results were created by 11 students (Johannes Bahne, Nico Bertram, Marvin Böcker, Jonas Bode, Hermann Foot, Florian Grieskamp, Marvin Löbel, Oliver Magiera, Rosa Pink, David Piper, and Christopher Poeplau) that were supervised by Prof. Dr. Johannes Fischer and me.

The slides are available as handout and heavily animated, and you can find the paper here (DOI).

Slides in Handout Mode

Slide image spire_2019_slides_handout-1.jpg
Slide image spire_2019_slides_handout-2.jpg
Slide image spire_2019_slides_handout-3.jpg
Slide image spire_2019_slides_handout-4.jpg
Slide image spire_2019_slides_handout-5.jpg
Slide image spire_2019_slides_handout-6.jpg
Slide image spire_2019_slides_handout-7.jpg
Slide image spire_2019_slides_handout-8.jpg
Slide image spire_2019_slides_handout-9.jpg

Abstract

We present a practical comparison of suffix array construction algorithms on modern hardware. The benchmark is conducted using our new benchmark framework SACABench, which allows for an easy deployment of publicly available implementations, simple plotting of the results, and straight forward support to include new construction algorithms. We use the framework to develop a construction algorithm running on the GPU that is competitive with the fastest parallel algorithm in our test environment.