DP-HLS: A High-Level Synthesis Framework for Accelerating Dynamic Programming Algorithms in Bioinformatics

Dynamic programming (DP) is a widely used algorithmic paradigm, particularly in bioinformatics, finding applications in a wide spectrum of tasks, including read assembly, homology search, gene annotation, basecalling, and phylogenetic inference. Due to its computationally intensive nature, many ASIC- and FPGA-based accelerators have been proposed in recent years to accelerate specific tasks. However, DP algorithms in bioinformatics can vary considerably, and most existing solutions are customized for a single application, representing just one design point within the broader DP space. These implementations typically rely on low-level hardware description languages (HDLs), often requiring months of manual implementation effort. This paper introduces DP-HLS, a novel framework based on High-Level Synthesis (HLS) that simplifies and accelerates the development of a vast set of bioinformatically relevant 2-D DP algorithms in hardware. DP-HLS achieves this by introducing a new abstraction layer that decouples the front-end specification from predefined HLS-based back-end optimizations, enabling users to efficiently develop new 2-D DP kernels in C++ and deploy them on FPGAs without needing any expertise in hardware design or HLS. In our experience, DP-HLS significantly reduced the development time of new kernels (months to days) and produced designs with comparable resource utilization to open-source hand-coded HDL-based implementations and performance within$\mathbf{7. 7 - 1 6. 8 \%}$margin. DP-HLS is compatible with AWS®EC2 F1 FPGA instances. To showcase its versatility, we implemented 15 diverse 2-D DP kernels using the DP-HLS framework, achieving$1.38-41 \times$improved cost-efficiency over state-of-the-art GPU and CPU baselines and providing the first open-source FPGA implementation for several of them. The DP-HLS codebase is available freely under the MIT license at https://github.com/TurakhiaLab/DP-HLS.