Publication

Finding every occurrence of a DNA pattern (exact matching) is a core step in genome analysis, and often one of its slowest. This work presents a multi-GPU solution based on the Knuth-Morris-Pratt (KMP) algorithm that searches for many patterns at once and exploits multi-buffering to make the most of the hardware.
It runs up to 5.83x faster than a state-of-the-art genome analysis tool and, on an AMD MI210 GPU, up to 1.59x faster than the best FPGA solution reported in the literature.
Authors: Beatrice Branchini, Pierluigi Negro, Ian Di Dio Lavore, Marco Domenico Santambrogio
Published in: IEEE International Symposium on Circuits and Systems (ISCAS), 2025