基于滑動(dòng)窗的Needleman-Wunsch 算法硬件加速方案設(shè)計(jì)與實(shí)現(xiàn)

肖俊杰

（上海交通大學(xué)電子信息與電氣工程學(xué)院，上海200240）

0 引言

生物序列比對是生物信息學(xué)和計(jì)算生物學(xué)的基本問題之一，它旨在找出一個(gè)未知序列與已知序列在結(jié)構(gòu)和功能上是否相關(guān)，這對于疾病的早期防治和藥物工程至關(guān)重要[1]。Needleman-Wunsch 算法[2]是一種廣泛使用的序列比對算法，用于全局比對兩個(gè)序列之間的相似性。這一算法基于動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)，可以求得比對的最優(yōu)解，但其時(shí)間復(fù)雜度與序列長度的乘積成正比，考慮到生物序列數(shù)據(jù)庫的巨大規(guī)模和其指數(shù)增長率，需要更快的計(jì)算技術(shù)來應(yīng)對這一問題。

高算力的并行結(jié)構(gòu)為解決這一問題提供了機(jī)會(huì)，但是Needleman-Wunsch 算法內(nèi)部數(shù)據(jù)之間存在依賴性，需要各計(jì)算節(jié)點(diǎn)之間相互通信?，F(xiàn)有計(jì)算方法大多基于波前進(jìn)位（wave-front）[3]這一并行方式進(jìn)行優(yōu)化刪減[4-6]，但其訪存特征不規(guī)則，難以實(shí)現(xiàn)高效的訪存調(diào)度，有限的存儲(chǔ)資源和過多的片外存儲(chǔ)器訪問導(dǎo)致并行效率下降成為了硬件優(yōu)化的主要阻礙。因此本文提出了一種基于滑動(dòng)窗的解決方案，采用了通用化的并行策略，簡化了對Needleman-Wunsch 算法進(jìn)行并行的難度；并提出一種延時(shí)串連的脈動(dòng)陣列（systolic array）[7]結(jié)構(gòu)，減少了對存儲(chǔ)的訪問。為與不同加速方案下的計(jì)算和存儲(chǔ)特征相匹配，本文基于粗粒度可重構(gòu)陣列（CGRA）[8]對改進(jìn)前后的方案進(jìn)行了比較，并與通用計(jì)算架構(gòu)下的解決方案對比，量化本文方案在執(zhí)行時(shí)間和執(zhí)行效率方面的優(yōu)勢。

1 Needleman-Wunsch算法

Needleman- Wunsch 算法的目標(biāo)是在序列X=x1x2…xi…xM（序列長度為M）和序列Y=y1y2…yj…yN（序列長度為N）之間尋找最佳的全局匹配結(jié)果。該算法建立了一個(gè)(M+1) ×(N+1) 的分?jǐn)?shù)矩陣F，其中矩陣的元素F(i,j)表示X的子序列x1x2…xi和Y的子序列y1y2…yj比對的得分，分值越高表示兩條序列的相似性越大。矩陣的最后一個(gè)元素F(M,N)為序列X和序列Y的最優(yōu)比對得分，最優(yōu)比對結(jié)果通過回溯得出。該算法分為初始化、填充和回溯三個(gè)步驟，如圖1 給出的兩條示例序列所示。

分?jǐn)?shù)矩陣的第一行和第一列被初始化，其余元素的值由其左元素、上元素和對角線元素的值確定，其填充規(guī)則如下：

上述式子表明了位置(xi,yi)的3 種更新方式：通過（xi-1,yj）的垂直方向，此時(shí)序列X需要插入空位，罰分為-d；通過（xi,yj-1）的水平方向，此時(shí)序列Y需要插入空位，罰分為-d；通過（xi-1,yi-1）的對角方向，此時(shí)序列匹配成功，得分為s（xi,yi）。

圖1 Needleman-Wunsch算法執(zhí)行步驟

回溯過程從F(M,N)開始，如圖1 所示，以箭頭標(biāo)記的方向追溯路徑來源，通過箭頭的方向確定是否需要在序列中插入空位，獲得具有最優(yōu)解特性的匹配結(jié)果。

Needleman-Wunsch 的填充階段本質(zhì)上是二維動(dòng)態(tài)規(guī)劃數(shù)組的建立階段，其時(shí)間和空間復(fù)雜度均為O(M×N)，是整個(gè)算法計(jì)算、訪存最密集的部分。又由于動(dòng)態(tài)規(guī)劃的特點(diǎn)，需要各個(gè)節(jié)點(diǎn)之間相互通信，這一特性增大了Needleman-Wunsch 算法并行化的難度，使其只能以對角線條帶（diagonal strip manner）的形式進(jìn)行內(nèi)存訪問，這種不規(guī)則的訪問方式破壞了數(shù)據(jù)的空間局域性。目前的加速平臺(tái)通常采用一級或多級高速緩存（cache）來提升訪存的性能，但cache 的容量有限，單純增大并行度并不能顯著提升系統(tǒng)的性能，反而可能降低系統(tǒng)的存儲(chǔ)帶寬和增大緩存缺失率。采用合適的并行計(jì)算方法提高計(jì)算和訪存的效率成為了加速Needleman-Wunsch 算法的關(guān)鍵。

2 加速方案設(shè)計(jì)

2.1 并行特征提取

依據(jù)公式（1），Needleman-Wunsch 算法在執(zhí)行比對任務(wù)時(shí)內(nèi)部的數(shù)據(jù)存在依賴關(guān)系，即元素F(i,j)的計(jì)算依賴于相鄰三個(gè)元素：F(i,j-1)、F(i-1,j)和F(i-1,j-1)，只有這三個(gè)元素計(jì)算完成后才開始計(jì)算F(i,j)。因此通常的串行方式是按照矩陣的行或者列逐層進(jìn)行運(yùn)算，如圖2（a）所示。這種方法在一個(gè)時(shí)間步內(nèi)只能處理矩陣的一個(gè)元素，計(jì)算效率低，而且下一個(gè)節(jié)點(diǎn)的計(jì)算操作數(shù)來自前一節(jié)點(diǎn)的計(jì)算結(jié)果，不能簡單地對矩陣不同位置的元素進(jìn)行并行展開。

圖2 分?jǐn)?shù)矩陣填充步驟的實(shí)現(xiàn)和優(yōu)化

但不難發(fā)現(xiàn)當(dāng)矩陣某一元素F(i,j)的計(jì)算完成后，其右方的元素F(i,j+1)和下方的元素F(i+1,j)就可以開始計(jì)算，即位于矩陣同一條反對角線上的元素不存在數(shù)據(jù)相關(guān)，從矩陣左上角的第一個(gè)元素開始沿著對角線方向通過波前進(jìn)位的方式進(jìn)行并行處理，就能夠在一個(gè)時(shí)間步內(nèi)同時(shí)處理同一條反對角線的元素，如圖2（b）所示。針對波前進(jìn)位的優(yōu)化主要是通過不同的分塊策略實(shí)現(xiàn)計(jì)算和訪存之間的平衡，如圖3 所示，但對角線元素?cái)?shù)量不一使得計(jì)算和訪存依舊是不規(guī)則的，并行效率不高。

圖3 分?jǐn)?shù)矩陣的分塊

圖4 滑動(dòng)窗數(shù)據(jù)流圖

2.2 并行策略改進(jìn)

本文利用串聯(lián)延時(shí)脈動(dòng)陣列結(jié)構(gòu)對上述策略進(jìn)行了改進(jìn)，提出了一種滑動(dòng)窗式的并行加速方法，不僅考慮了單個(gè)應(yīng)用的特性，還提取出算法的公共特征，得到的計(jì)算結(jié)構(gòu)更易于擴(kuò)展。如圖2（c）所示，硬件在每一個(gè)時(shí)間步內(nèi)只需要處理單個(gè)滑動(dòng)窗內(nèi)的元素，每個(gè)滑動(dòng)窗遵循相同的計(jì)算規(guī)則，并且以邊界填充（padding）的形式避免邊界條件的判斷并保證計(jì)算規(guī)則的統(tǒng)一。計(jì)算規(guī)則確保了每個(gè)滑動(dòng)窗內(nèi)部計(jì)算的并行性，滑動(dòng)窗的大小可以依據(jù)片上存儲(chǔ)器的容量和計(jì)算單元的數(shù)量確定。這一方法的好處是滑動(dòng)窗的計(jì)算規(guī)則保證了單個(gè)滑動(dòng)窗內(nèi)的數(shù)據(jù)不存在相關(guān)性，硬件只需要對單個(gè)滑動(dòng)窗的計(jì)算進(jìn)行并行加速。并且邊界填充可以在算法的初始化階段完成，簡化了邊界條件的判斷，提高了資源的利用效率。

以圖2（c）為例，假定滑動(dòng)窗大小為4×4，滑動(dòng)窗在單個(gè)時(shí)間步內(nèi)可同時(shí)計(jì)算3 個(gè)元素的值，在分?jǐn)?shù)矩陣的邊界處（圖中的t=0 和t=7）額外填充了2 列元素，使得滑動(dòng)窗可以使用相同的規(guī)則進(jìn)行計(jì)算。滑動(dòng)窗首先進(jìn)行橫向滑動(dòng)，在計(jì)算得到當(dāng)前位置的結(jié)果之后向右滑，并將之前的結(jié)果作為新位置下的輸入，按照此方式處理分?jǐn)?shù)矩陣的0 至3 行后向下滑，以相同的規(guī)律處理矩陣的3 至7 行。滑動(dòng)窗的滑動(dòng)過程很容易通過脈動(dòng)陣列結(jié)構(gòu)實(shí)現(xiàn)，脈動(dòng)陣列結(jié)構(gòu)可以在消耗較小的內(nèi)存帶寬的情況下實(shí)現(xiàn)較高的運(yùn)算吞吐率。而且這種計(jì)算方式容易擴(kuò)展，能夠用于不同規(guī)模的輸入。

這一方法得到的數(shù)據(jù)流圖如圖4 所示，在硬件概念上使用計(jì)算處理單元（Processing Element，PE）對滑動(dòng)窗內(nèi)的元素實(shí)現(xiàn)并行計(jì)算。因?yàn)槟骋淮斡?jì)算得到的結(jié)果會(huì)在接下來兩次計(jì)算中使用，所以計(jì)算得分的PE會(huì)將結(jié)果直接或經(jīng)過延時(shí)后轉(zhuǎn)發(fā)給另一個(gè)PE，實(shí)現(xiàn)局部的數(shù)據(jù)復(fù)用，PE 陣列只有在分?jǐn)?shù)矩陣的上邊界和左邊界處才需要從存儲(chǔ)器中讀取操作數(shù)，其余時(shí)間可以從計(jì)算得分結(jié)果的PE 處獲取。單純采用對角線展開的方式處理3 個(gè)元素需要進(jìn)行7 次讀操作，相比之下采用滑動(dòng)窗實(shí)現(xiàn)只需要2 次讀操作，極大地減少了帶寬需求。同時(shí)，在計(jì)算得到矩陣元素分值的同時(shí)也可以知道該矩陣元素是由哪個(gè)方向的元素得到的，因此回溯方向的保存可以和分值的計(jì)算同時(shí)進(jìn)行。此外由于滑動(dòng)窗是按照矩陣的行、列方向滑動(dòng)的，在降低了訪存次數(shù)的同時(shí)也降低了對角線條帶式訪問帶來的緩存缺失問題。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)平臺(tái)

本實(shí)驗(yàn)中，我們采用了粗粒度可重構(gòu)陣列（CGRA）結(jié)構(gòu)來實(shí)現(xiàn)滑動(dòng)窗的結(jié)構(gòu)。粗粒度可重構(gòu)陣列兼具靈活度和高性能，能夠與不同的訪存和計(jì)算結(jié)構(gòu)相適配，從而對不同的算法提供廣泛而靈活的支持。本文基于C++搭建了一個(gè)包含典型CGRA 結(jié)構(gòu)的系統(tǒng)級模擬器，用以模擬可重構(gòu)陣列的執(zhí)行過程，模擬器包含周期精確的陣列模型和的內(nèi)存模型[9]，該CGRA 系統(tǒng)結(jié)構(gòu)如圖5 所示。

圖5 粗粒度可重構(gòu)陣列系統(tǒng)結(jié)構(gòu)

其中，粗粒度可重構(gòu)陣列負(fù)責(zé)處理核心計(jì)算，主處理器對系統(tǒng)進(jìn)行控制，對目標(biāo)應(yīng)用進(jìn)行編譯生成帶有配置信息的數(shù)據(jù)流圖（Data Flow Graph，DFG），任務(wù)控制器對數(shù)據(jù)流圖進(jìn)行解析，隨后向PE 組成的PE 陣列發(fā)送配置信息，PE 陣列依據(jù)配置完成任務(wù)的執(zhí)行。本地存儲(chǔ)器和主存儲(chǔ)器構(gòu)成存儲(chǔ)器層次結(jié)構(gòu)，實(shí)現(xiàn)高效的數(shù)據(jù)存儲(chǔ)和訪問功能，本地存儲(chǔ)器采用16KB 的一級cache。

PE 陣列包含有8×8 規(guī)模的64 個(gè)PE，每個(gè)PE 可依據(jù)配置字配置成不同的功能，32 個(gè)存儲(chǔ)處理單元（Load Store Element，LS）分布在PE 的外圍負(fù)責(zé)管理訪存請求。每個(gè)PE 可以與同行同列的PE 或LS 互連，這種互連方式支持同行和同列的PE 之間相互轉(zhuǎn)發(fā)數(shù)據(jù)，從而實(shí)現(xiàn)脈動(dòng)陣列，大量PE 組成的陣列帶來了高并行性，并且PE 計(jì)算的結(jié)果不需要存回存儲(chǔ)器，可以直接轉(zhuǎn)發(fā)給下一PE 進(jìn)行處理，提高了計(jì)算效率。

3.2 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證改進(jìn)后的方案在CGRA 上實(shí)現(xiàn)的效率，本文對上一節(jié)的三種填充實(shí)現(xiàn)策略進(jìn)行了映射，分別是串行、波前進(jìn)位和滑動(dòng)窗式，堿基序列長度均為256，最終得到的實(shí)驗(yàn)結(jié)果的如表1 所示。表中的PE 數(shù)量表示執(zhí)行應(yīng)用所需要的PE 總數(shù)，表明硬件的資源消耗情況；PE 利用率表示PE 執(zhí)行有效計(jì)算的時(shí)間占執(zhí)行時(shí)間的比率，表明硬件的執(zhí)行效率。

其中方案1 不進(jìn)行并行、分塊等任何優(yōu)化，作為對比的基準(zhǔn)，方案1 中的許多PE 被用于循環(huán)控制和邊界判斷，因此利用率不高。方案2 將矩陣分成8×8 大小的塊，采用對角線條帶的并行方式，單個(gè)塊最多可同時(shí)計(jì)算8 個(gè)對角線元素，增大了計(jì)算的并行度。但是大并行度也導(dǎo)致了更高的緩存缺失率（cache miss rate），多個(gè)請求相互爭搶cache 也導(dǎo)致了訪存沖突（cache conflict），不規(guī)則的對角線計(jì)算也使得部分PE 閑置，PE利用率反而有所降低，方案2 相比方案1 最終獲得了3.5 倍的加速比。方案3 選擇的滑動(dòng)窗大小為9×9，最多可同時(shí)計(jì)算8 個(gè)對角線元素；由于計(jì)算更規(guī)則，在相同并行度下減少了用于邊界判斷的PE 數(shù)量；方案3 相比方案1 的加速比提升到了7.5 倍，而且由于方案3 采用脈動(dòng)陣列實(shí)現(xiàn)，降低了訪存次數(shù)，很大程度上減少了由于緩存訪存缺失和訪存沖突引起的流水線停頓，相比方案2 獲得了2.3 倍的性能提升。

表1 不同映射方式執(zhí)行時(shí)間對比

表2 不同架構(gòu)執(zhí)行時(shí)間對比

表2 給出了本文方案與CPU 和GPU 對比的結(jié)果，以驗(yàn)證本文的上述方案相對通用加速平臺(tái)的性能提升。其中CPU 測試平臺(tái)采用Intel Core i7-4770 處理器，16GB DDR3 內(nèi)存，以執(zhí)行時(shí)間作為性能標(biāo)準(zhǔn)，本文提出的方案獲得了4.5 倍的加速比。GPU 平臺(tái)采用NVIDIA GeForce GTX 1080，并使用Rodinia[10]中的加速方案。由于Needleman-Wunsch 算法需要計(jì)算節(jié)點(diǎn)之間相互通信，GPU 不同線程之間需要頻繁同步，因此整體的并行效率不高，本文方案在使用更少計(jì)算資源情況下依然獲得了15.3%的性能提升，執(zhí)行效率更高。

4 結(jié)語

本文提出了一種基于滑動(dòng)窗的解決方案來加速Needleman-Wunsch 算法，并基于CGRA 對該方案進(jìn)行了驗(yàn)證。相比傳統(tǒng)波前進(jìn)位的并行方式，該方案提取了算法的公共計(jì)算特征，簡化了算法在硬件上的實(shí)現(xiàn)難度，使得更多的硬件資源可以用于核心計(jì)算；采用串連延時(shí)脈動(dòng)陣列結(jié)構(gòu)降低了訪存次數(shù)，減少了由于訪存延時(shí)帶來的流水線停頓，與改進(jìn)前相比獲得了的2.3倍加速比，相對CPU 獲得了4.5 倍的加速比，相對GPU，在使用計(jì)算資源更少的情況下仍然獲得了15.3%的性能提升。值得一提的是，本文提出的方案核心是對二維動(dòng)態(tài)規(guī)劃矩陣的建立過程進(jìn)行硬件優(yōu)化，這種優(yōu)化方法易于拓展到其他具有二維動(dòng)態(tài)規(guī)劃特性的算法上。