具內容感知平舖技術之雙向波前比對演算法與其硬體加速器

Abstract

隨著基因檢測技術的進步，基因序列比對的長度經常達到10Kbp以上，甚至可達100Kbp。傳統動態規劃演算法在時間與空間複雜度為O(mn)，使得比對長度增加時資源需求急遽上升，難以負荷現今的運算需求。本研究基於高記憶體效率的雙向波前比對演算法，將其結合本論文提出的內容感知平鋪技術，設計並實現一款硬體加速器。本加速器主要包含兩個階段：序列比對與序列回溯。 本研究提出的平鋪技術將長序列切分為512×512大小的區塊，並採用內容感知方式將區塊銜接，大幅降低硬體資源需求。實驗結果顯示，即使在基因序列錯誤率高達30%的高變異區域，平鋪準確率仍可達99.9%，且本平舖技術最高能夠減少78%的記憶體用量。而在每個512×512 的區塊內，我們用128個運算元件實現了256倍平行化的雙向波前比對演算法，並透過動態平行指派運算元件，並行處理演算法切分出的各子區域，以提升運算效能。序列回溯階段則採用雙向路徑回溯策略，進一步加速回溯過程。 本研究的主要貢獻在於提出一種適用於波前比對演算法的內容感知平鋪技術，並成功在現場可程式化邏輯閘陣列（FPGA）與特定應用積體電路（ASIC）上實現長讀序列比對硬體加速器。該平台輸入參考基因序列與待比對序列後，能高效輸出相對應的比對結果。與雙向波前比對演算法運行於AMD Ryzen 9 7950X(32緒CPU)上相比，FPGA與ASIC 實作分別可實現最高324倍與1181倍的效能加速；與其他硬體加速器相比，本研究的ASIC版本加速器使用最小的面積取得最快的運算速度。

With the advancement of genome sequencing technologies, the length of sequence alignment has increased significantly, often exceeding 10 kbp and even reaching 100 kbp. Traditional dynamic programming algorithms, with a time and space complexity of O(mn), impose exponentially increasing resource demands as the equence length grows, making them unsuitable for modern computing needs. In this work, we present a hardware accelerator based on the memory-efficient Bidirectional Wavefront Alignment (BiWFA) algorithm, enhanced with a content-aware tiling technique to further extend its capability to handle longer genomic sequences. The accelerator consists of two major stages: sequence alignment and traceback. The proposed tiling technique partitions long sequences into tiles of 512bp × 512bp each and connects them using a content-aware scheme, substantially reducing hardware resource consumption. Experimental results show that even in high-variant regions with sequence error rates as high as 30%, the tiling accuracy remains 99.9%. This tiling technique effectively reduces memory footprint by up to 78% .Within each 512×512 tile, we implement a 256-way parallel BiWFA using 128 processing elements (PE) and dynamically allocate PEs to concurrently process sub-regions within the tile, significantly improving performance. The traceback stage adopts a bidirectional traceback strategy to further accelerate the process. The primary contribution of this work lies in the content-aware tiling technique tailored for wavefront-based alignment algorithms, along with the implementation of a long-read sequence alignment accelerator on both FPGA and ASIC platforms. Given a reference and a query sequence as input, the accelerator efficiently outputs the corresponding alignment results. Compared to a software BiWFA implementation running on a 32-thread AMD Ryzen 9 7950X CPU, our FPGA and ASIC implementations achieve up to 324× and 1181× speedups, respectively. Compared with the other hardware accelerators, the ASIC implementation proposed in this work achieves the highest processing speed while occupying the smallest silicon area.