基於流處理的生物序列資料庫搜索多層次加速方法

2023-06-05 10:32:31

專利名稱：基於流處理的生物序列資料庫搜索多層次加速方法
技術領域：
本發明主要涉及生命科學和信息科學中海量生物學信息的檢索與比較方法，尤其指 如何對生物序列資料庫搜索進行多層次加速迫方法。
背景技術：
近年來，隨著各物種基因組計劃的陸續開展與深入，產生了海量的生物學序列數據， 這些數據主要包括DNA (脫氧核糖核酸)、脂A (核糖核酸)序列數據和蛋白質序列數據等。 例如，國際三大核酸資料庫GenBank/EMBL/DDBJ中的數據量大約每15個月就會翻一番， 且數據增長的速度還在不斷加快，根據摩爾定律可知，生物數據量增長速度正在或即將 超過計算機處理能力的增長速度，因此按照這種增長趨勢，搜索、處理這些數據將會花 費更長的時間(在計算機處理能力相對固定的情況下)，並需要更高的計算機處理能力(在 任務時間開銷相對固定的情況下)。生物序列數據的搜索與比較也面臨著如此巨大的挑 戰。
給定一條生物序列(以下稱為査詢序列)，到現有的生物序列資料庫中去搜索與之足 夠相似的一條或多條搜索結果序列(以下稱為庫序列)，這已經成為當前生物與醫藥領域 分子生物學應用研究中常規性的操作任務。例如，分子水平的進化發育分析研究、新蛋 白質的結構與功能預測等應用都離不開這種基於相似性的資料庫搜索。因此研究與開發 快速高效的生物序列資料庫搜索的方法和工具對於生物醫藥等領域的應用具有重要的實 用價值。
生物序列資料庫搜索的過程可以概括為三個關鍵步驟(1) 分解搜庫任務逐一取出資料庫中的所有庫序列，並與查詢序列組合成對，各自執行一次"成對序列比對"子任務。這個環節相當於將資料庫搜索分解 成多個成對序列比對子任務。(2) 成對序列比對的過程以兩條生物序列為輸入，對其進行比較計算，得到一 個用以刻畫這兩條序列相似程度的一個數值，稱為相似性比對得分值。(3) 綜合搜索結果將資料庫中的每一條庫序列依照"成對序列的比對"獲得的 相似性比對得分值從高到低降序排列，挑出一條(根據應用的需要，有時可
能是數條)得分值最高的庫序列作為搜索結果輸出。其中前兩步("分解搜庫任務"與"成對序列比對")是搜索過程中的兩個核心環節， 第三步"綜合搜索結果"則是對前兩步的簡單排序、分析與輸出。生物序列資料庫的搜索與其他常規性的資料庫搜索的主要差異體現在"成對序列的 比對"的環節。 一方面，生物序列之間的相似性主要是根據它們在進化歷史上是否具有 共同祖先(稱為同源性)來進行度量，而生物進化過程普遍存在的突變性就決定了生物 序列的比較不可能是"非此即彼"的精確化方式(就像經典的字符串匹配那樣)；另一方 面，由於生物序列測序中的誤差以及特定實驗目標的需要等因素的存在，參與比較的序 列往往都是不完整的"片段"，這也需要生物序列比較方法中要進行特殊處理。在成對序 列的比對方面，Smith和Waterman於1981年提出一種利用動態規划算法計算兩條序列的 最優局部相似性比對得分值的方法(稱為Smith-Waterman方法)，這是迄今所知最早的 計算兩條序列相似性比對得分值的方法，1982年Gotoh在簡化了原始的空位罰分函數形 式(由一般函數簡化為線性函數)的基礎上，對Sraith-Waterman的方法進行了改進；1993 年Green又針對計算機存儲特點對該方法的程序實現進行了優化。用以評估生物序列資料庫搜索方法優劣的基本性能指標主要有(1)準確性，主要 是追求更高的敏感性、特異性以及更低的假陽性率、假陰性率；(2)搜索速度，主要考 察能否在可接受的、更短的時間內完成相同數據規模的搜索。準確性的提高主要依靠成 對序列的比對方法的創新與改進，經過來自不同學科研究人員多年來的努力，目前已經 形成了比較成熟的成對序列比對方法，獲得了可滿足應用需求的準確性。當前制約生物 序列數據搜索與比較的主要瓶頸是搜索速度的日益落後於數據量的增長速度，如前文所 述，國際三大核酸資料庫的數據量大約每15個月就會翻一番，計算機軟硬體的更新速度 越來越跟不上數據量的增長速度，從而也越來越無法滿足應用的需求。為了解決搜索速度落後於數據量增長速度的矛盾，全世界的科研人員進行了不懈的 努力，發展了各種各樣的新方法，這些方法可以歸為三類(1)犧牲準確性以加快搜索 速度的近似尋優方法，(2)用專門的計算硬體實現搜索核心算法，(3)藉助各種並行處 理策略加快搜索速度的並行處理類方法。1.[近似尋優類方法]最初的生物序列資料庫搜索方法中的成對序列比對環節主要使用經典的 Smith-Waterman算法，它是一種動態規劃的尋優算法，在常規的計算設備實現 Sraith-Waterman算法非常耗時，於是人們在此基礎上發展出了大量近似尋優算法(又稱 啟發式方法)，例如FASTA (Pearson and Lipman, 1988)和BLAST (Altschul et al., 1990; Altschul et al. ， 1997)等，與通用計算機上實現的最優Smith-Waterman串行方法相比， 這些方法在最好情形下可將計算機運行時間縮減40倍左右，不過這樣高的速度是以犧牲 搜索結果的敏感性為代價的。由於損失了不少的敏感性，有些本來可以檢測到的遠緣序 列在使用近似尋優算法進行數據搜索時就無法搜索到了。2. [專用硬體實現法]為了追求生物序列資料庫搜索中"速度快、敏感性高"的目標，人們也發展出了不 少加速Smith-Waterman比對的方法。其中， 一部分解決方案是採用專用的硬體實現並行 處理能力(Hughey， 1996)，例如Paracel的GeneMatcher， Compugen的Bioccelerator 以及TimeLogic的DeCypher等等，這些機器設備可以達到每秒處理2億個矩陣單元的高 速度。另有一些硬體實現的Smith-Waterman算法已經申請了專利，例如專利號分別為 5553272， 5632041， 5706498, 5964860和6112288的美國專利，等等。這類方法的主要 缺陷是，專用的機器硬體設備造價昂貴，只有少數機構才有實力採購使用，而非一般用 戶所能用得上。3. [並行處理類方法]這類方法是利用"單指令多數據"(SIMD， Single-Instruction Multiple-Data)技 術來實現Smith-Waterman算法的並行處理能力。 一個SIMD計算機可以針對不同的數據 並行地同時執行某個相同的運算(算術運算、邏輯運算等)，如果並行的粒度變小，這種 並行可以在指令、寄存器中進行。現代的微處理器通過增加一些特殊的寄存器和指令， 使得實現這種SIMD變得更加容易了。例如，1997年Intel公司推出了奔騰多媒體擴展 (Pentium MMX)微處理器，從而將SIMD技術引入了具有業界標準的、使用最廣泛的通用 微處理器系統結構中來。之後，奔騰2處理器依然繼承了這種技術，奔騰3則進一步將 其擴展為"流單指令多數據擴展"(SSE， Intel, 1999)， 2000年Intel在奔騰4中將其 擴展為SSE2(Intel， 2000)。此外，為了保持跟Intel處理器的兼容性，AMD系列的處理 器同樣也支持MMX/SSE/SSE2等指令集。大量研究與實踐證明，使用SIMD並行技術可以 有效加速Smith-Waterman算法。在Smith與Waterman提出他們的成對序列比對算法後，先後有一系列研究者對該算 法進行了改進與完善。1982年Gotoh在"仿射型空位罰分函數"的情形下給出了 Smith-Waterman算法的一種實現，並將運行時間減少到與兩條序列長度之積成正比的量 級，即時間複雜度為O(rrm)，其中m和n分別是兩條序列的長度。1993年Green編制了名
為SWAT的電腦程式，他在其中對Gotoh的方法進行了一些優化，取得了運行時間縮短 50%的優化效果。後來Pearson在其SSEARCH程序中也採用了這些優化。通常認為， Smith-Waterman-Gotoh-Green方法是迄今為止所知的成對序列比對算法的最優串行版本 實現。之後，Smith-Waterman算法已經被實現和應用到多種不同的SIMD計算機中* 1993年Sturrock與Collins為MasPar系列的並行計算機上實現了 Smi th-Waterman算法，並將程序命名為MPsrch 。他們在具有4096個CPU的MasPar MP-1型計算機上取得了每秒計算1.3億個矩陣單元的速度性能，在具有16384 個CPU的MasPar MP-2型計算機上取得了每秒計算15億個矩陣單元的速度性能。* 1993年Brutlag等在MasPar型機器上實現了一個名為BLAZE的Smith-Waterman 算法。
1997年Wozniak提出一種在Sun UltraSPARC微處理器上使用VIS (Visual Instruction Set)技術實現Smith-Waterman算法的方法，該方法在167 MHz的 UltraSPARC處理器上取得了每秒計算1800萬個矩陣單元的性能。據 Wozniak(1997)聲稱，新方法較在同樣機器上實現的整數精度的傳統算法速度提 高2倍左右。* Taylor於1998年使用應X技術實現Smith-Waterman算法，在Intel奔騰3 500MHz 處理器上取得了每秒計算660萬個矩陣單元的性能。* 2000年，Sturrock和Collins在Alpha處理器上利用SIMD技術實現了 Smith-Waterman算法，不過他們方法的細節並未公布。間接文獻表明，他們取 得了每秒計算5300萬個矩陣單元的速度性能(不清楚他們所用的處理器類型及 參數)。* 2000年Barton等人採用謝X技術對他們自己的SCANPS程序中的Smith-Waterman 進行加速，並聲稱在Intel奔騰3 650MHz的處理器上達到了每秒計算7100萬個 矩陣單元的速度。他們的方法只有一個摘要(以牆報形式發表)，細節並未公布。跟近似尋優類方法和專用硬體實現法相比，SIMD並行策略可以在不降低搜索準確性 的前提下，以較低的成本加快了生物序列資料庫的搜索速度，因而得到了更為廣泛的應 用。然而，這種策略過於強調計算設備的通用性，無法充分利用更好的硬體設備及其性 能優化技術，限制了發揮更佳加速性能的潛力。綜合上述三種生物序列資料庫搜索的加速方法，不難發現它們仍存在著一些不足之 處。首先，三種加速方法具有各自的特點與適用範圍近似尋優方法對計算平臺沒有特 點要求，適應面寬，缺點是加速過程中犧牲掉了搜索的準確性；專用硬體實現法加速效 果最佳，但高昂的機器設備費用嚴重限制了其適用性；SIMD並行處理方法結合了前兩種 方法的優點，準確性沒有降低，成本較小，通用性好，但加速效果沒有達到最佳。其次， 所有這三種加速方法都是圍繞生物序列資料庫搜索中的"成對序列的比對"這一環節展 開的(重點是對傳統Smith-Waterman算法的改進或硬體實現)，但目前制約生物序列數 據庫搜索速度的決定性因素是資料庫規模增長過快，因此若能加速生物序列資料庫搜索 中的另一環節"分解搜庫任務"(例如，將資料庫序列與查詢序列的比對操作分布到多個 處理器結點上並發執行)，則可望達到對搜索速度更加顯著的改進效果，這是上述三類方 法中普遍缺乏關注的地方。第三，近年來隨著流計算概念的產生和流處理器晶片的出現， 流處理技術在許多應用領域(特別數字信息處理領域)得到了大量的應用；生物序列比 對處理過程中，生物序列數據具有典型的流特性，比較適合於在流處理器進行處理完成； 同時，由於流處理器主要是靠集成大量廉價的計算單元而實現功能的，因而具有計算速 度快、成本低廉的優點。當前的上述三類技術均還未採用這種流處理技術，專利與文獻 中也未見有使用流處理器實現生物序列資料庫搜索的相關報導。發明內容本發明要解決的技術問題在於在保證不降低搜索準確性、同時兼顧較低成本的前 提下，加快生物序列資料庫搜索速度，使其在生物序列數據量急劇增長的背景下仍能夠 滿足生物醫藥領域應用的日常需求。為了解決上述技術問題，本發明提出的技術方案為使用配置有流處理器的計算機 集群系統，通過對生物序列資料庫搜索過程中的"分解搜庫任務"與"成對序列比對" 這兩個核心環節進行資源分配與任務劃分，實現集群節點層、流級計算層、流內核指令 層三個層次的多級並行提速的目標。具體技術方案為-1.構建由多臺個人計算機組成的集群系統，每臺計算機都是集群系統的節點，各節 點有著各自獨立的存儲系統，節點之間的通信採用消息傳遞的方式。節點依次編號為 0,1，2，...，np-l。這裡 為集群系統中節點的總數目(實際系統中， 的取值為2的整數次冪等)。為了便於後續處理，指定編號為o的那個節點機器為主控節點機器，它主要負責與用戶交互，完成輸入輸出及對搜索結果的中間處理。每個節點除了自身的主處理器外，還配置一個流處理器為該節點的協處理器；流處理器主要由存儲部件、計算部件
和控制部件組成，其中計算部件是流處理器的主體，它包含有P個硬體計算簇單元，在實 施計算時，p個硬體計算簇可利用SIMD方式同時處理流向量中的p個數據，達到並行處理的加速效果。實際系統中P是流處理器中硬體計算簇單元的數目，它由具體的流處理器型 號與配置所決定。2. 主控節點機器將資料庫序列分布存儲到集群系統中各個節點機器。在創建資料庫 和增量更新數據時，將生物序列資料庫中的序列數據平均分布到集群系統中不同節點的 存儲器中，以便進行生物序列的資料庫搜索時的任務分布與並行處理。由於生物序列數 據庫更新的頻度遠遠低於資料庫搜索的頻度，因此本步驟的操作雖然費時，但執行頻度 不高，因而對資料庫搜索速度的影響較小。具體方法為2.1主控節點機器對資料庫序列按照序列長度進行降序排列，形成一個序列列表 seq[O]， seq[l], ...， seq[/V-1]，其中iV是生物序列資料庫中序列的總數目。2.2主控節點機器將序列列表中的每條序列分發到集群系統中的各個節點中去，分 發規則如下將seq[i]這條序列分發到編號為i'的節點的局部存儲器中，？的計算方法為 若i0 < ，貝lj取 :' = i0; 若i0 2，貝U取i' = 2np — 1 — i0 。式中，i0 = i mod (2rap)' i = 0,l;...:iV-l。這種序列分發方法的好處是不論從序列條數還是從存儲容量上衡 量，集群系統中各節點的局部資料庫存儲量都是均衡的。3. 主控節點機器對査詢序列進行填充與重排。當查詢序列提交給集群系統中主控節 點機器後，主控節點機器對査詢序列進行填充補齊及重排，以減少並行計算過程中的數 據依賴，並達到多節點並行計算的負載平衡。具體步驟包括3.1主控節點機器對查詢序列進行數據填充與補齊如果查詢序列s'的長度V是2p的 整倍數，則跳至步驟3. 2，否則在查詢序列的尾部追加2p - n' mod (2p)個"空元素"NUL， 以便於後續任務分配時保持負載平衡。填充補齊後的查詢序列記作.s"，其長度用n表示。3.2主控節點機器對查詢序列進行重排將填充補齊後的查詢序列 s〃 =《《...'.<—丄重新組合為s = ,s0， . ., —丄'其中& =《ra。d A.).K+Li/A-」，Z = 0， 1, . . . ，77, — 1。這裡K = p或2p，兩種取值分別代表不同的數值精度和並行粒度，/(值的具體確定方法見步驟5. 1. 2. 1及5.1. 2. 7。4. 主控節點機器將査詢序列分發到集群系統中的各個節點機器。主控節點機器將上 述填充與重排後的查詢序列分發給計算機集群系統中的所有節點，每個節點機器將該查 詢序列及存放於本地存儲器中的資料庫序列一併讀入本地內存。5. 各個節點機器並行執行搜索任務。每個節點機器負責完成查詢序列在本地資料庫序列中的搜索任務，搜索的結果是一條比對得分值最高的結果序列及其比對得分值。這 個過程由各個節點機器分布並發完成，它們之間不需要相互通信。每個節點機器上的搜 索過程為5.1使用流處理器、結合流處理器體系結構及Smith-Waterman比對算法的特點，基 於SIMD並行策略快速計算出査詢序列與節點本地資料庫中每條序列的比對得分值。本步 驟完成後，每條庫序列與査詢序列比對得到一個比對得分值，共獲得iV'個比對得分值， 其中W'是本地資料庫中序列的數目。每條庫序列與査詢序列之間的成對序列比對得分值 的計算過程為5.1.1確定成對序列比對過程中的參數，方法是*參與比對的兩條序列中， 一條是查詢序列(即步驟3中填充與重排後的查詢序 列)，用符號s表示，其長度記為rz;另一條是資料庫序列，用符號i表示，其長度 記為爪。* S表示成對序列比對Smith-Waterman算法中的匹配打分矩陣，對於核酸序列數 據而言，默認使用"替換-置換打分矩陣"，對於蛋白質序列數據而言，默認使用 Blosum 50打分矩陣，用戶也可根據應用問題的需求指定包含Blosum 62及PAM 系列在內的其它打分矩陣。* .9和h表徵成對序列比對過程中出現空位時的仿射罰分模型參數，即對於長度為fc 的空位區(即包含連續fc個空位的區域)，其罰分值為.g十(fc-l)J，這兩個參 數默認取值為.9 = 14， /i = 2，也可由用戶根據應用問題的需要指定其它取值。5.1.2利用流處理器計算查詢序列s與庫序列糹的局部相似性得分值。計算採用 Smith-Waterman的原理，但針對流處理器須進行SIMD並行化處理，為此構造五個輔助流 向量vH[O..n _ 1], vE[O..n — 1] ， vM[O..n — 1]' vF[O..p — 1]和vH'[O..p — 1]。傳統的 Smith-Waterman方法實現時需要使用一個n x m階矩陣的存儲空間，本步驟中只使用 0(3n,+ 2^)的存儲空間，計算過程中只保留原始矩陣中的一列數據，有效節約了存儲空間。 具體計算過程如下5. 1. 2. 1 取K = 2p，所有參與計算的數據均使用UHALF類型，這種數據類型的精 度為半字長(16位無符號整數)，所能表示的數值範圍為0 65535。在這種情形下，盡 管計算精度較低(與^ = 的情形相比)，但步驟5. 1.2.5中的流內核計算中一條指令可 同時得到2p個計算結果，具有較高的並發度和較快的計算速度。5. 1. 2. 2初始化流向量vH與vE:為流向量vH[O..n — l]和vE[O..n - l]賦以全0的初
值；流向量vF[O..p-l]的初值可任意設置，通常也置為全0。置庫序列位置標誌j'為0， 置局部相似性比對得分值V為0。5. 1. 2. 3計算流向量vM的值針對庫序列的第j個位置，通過查詢匹配打分矩陣S 設置^^/[
流向量的新值。其中，若s，:為"空字符"NUL，則取vM[7:]為0值；否則， vM卜:]取為.s與t,在打分表中對應的打分值S(s"y。這裡，.s,表示査詢序列的第i個字符，~ 表示庫序列的第j'個字符，？: = 0，l,...，n—l。5. 1. 2. 4 設置流向量vH'的值將流向量vH的尾部p個元素複製給vH'[O..p - lj,同 時將vH'的元素依次向右移動一個位置，空出的最左端元素vH'[O]置為0值。5. 1. 2. 5 在流內核級完成相似性比對得分值的計算以vH, vE，vM，vH'四個流向量 為輸入，通過多輪迭代過程計算得到最終的相似性比對得分值V。計算需要迭代的輪次 數跟査詢序列的內容及庫序列第j個位置的字符都有關，最壞情形下需要迭代71-p+l 輪，最好情形下只需要迭代1輪；若迭代較少的輪次即能產生最終的相似性比對得分值， 增加額外的計算輪次計算結果不變。為此，將第一輪迭代計算與後續輪次的迭代區分開 來，第一輪迭代計算稱為"粗計算過程"，後續輪次的計算稱為"精計算過程"。這兩個 過程都是採用SIMD策略由流處理器的p個硬體計算簇並行完成(p由流處理器的型號與硬 件配置決定，見步驟l)。"粗計算過程"以vH，vE，vM,vH'四個流向量為輸入，利用動態 規劃原理計算，輸出vH, vE和vF三個流向量及當前的局部相似性得分值V的更新值；"精 計算過程"以vH, vE和vF三個流向量為輸入，利用動態規劃原理進行多輪迭代計算，每 輪計算都對vH， vE和vF三個流向量的取值進行更新，並根據當前計算結果設置一個"繼 續迭代標誌位"，用以確定是否需要繼續執行下一輪的迭代過程；若繼續迭代標誌位為1， 則重新執行新一輪的迭代計算；若繼續迭代標誌位為0，則表示計算過程完成，轉至步驟 5.1.2.6。A粗計算過程中每個硬體計算簇執行如下步驟。 Al初始化從vH'流向量中讀取一個數據/f，置F的值為O。 A2迭代步持續執行下述步驟，直到vE向量中的數據被讀取完畢為止。 A2. 1讀取流數據從流向量vM中讀取一個數據M，從流向量vE中讀取一個數據E。 A2.2更新相似性比對得分值V:若/7 + M〉V，則更新相似性比對得分值為 V —+ M。A2.3更新H值並寫回流向量vH:取H —max{ff+ M，￡,F,0}，並用所得的/f值更 新流向量vH中最近一次讀取的舊數據。
A2.4更新E值並寫回流向量vE:取￡ —max{E —/7,，^一.9}，並用得到的E值更新 流向量vE中最近一次讀取的舊數據。A2. 5更新F值取F — max{F -i/ — .9}。A2.6迭代條件判定若流向量中所有數據均被讀取並寫回，則結束迭代，否則，先 從流向量vH中讀取一個數據//，再重新執行A2.廣A2. 6的迭代過程。A3 寫回流向量vF:所有p個硬體計算簇將本地計算的F值"向右傳遞"，同時將接 收到的(來自左側鄰居的)F值寫回到流向量vF中。所謂"向右傳遞"，是指編號為z的 硬體計算簇將本地計算得到的F值傳遞給編號為i + 1的硬體計算簇 (7: = 0,l:2,...,p — 2)，編號為p-l的硬體計算簇的F值捨棄，編號為0的硬體計算簇的 F值更新為0。數據傳遞是通過消息發送機制完成的。A4 匯總所有硬體計算簇上獲得的最佳比對得分值每個硬體計算簇在上述迭代結 束後都獲得一個本地的局部相似性比對得分值V，通過在p個硬體計算簇之間進行數據通 訊，選出P個比對得分值中的最大值，作為流內核計算中粗計算過程的執行結果。A5 設置"繼續迭代標誌位"若至少有一個硬體計算簇上本地計算結果滿足 P > vH問—.9且P 〉 0，則設置"繼續迭代標誌位"為1，否則置為0。"繼續迭代標誌位" 也作為流內核計算中粗計算過程的執行結果返回。B精計算過程中每輪迭代計算所執行的步驟如下Bl初始化從流向量vF中讀取一個數據F。B2迭代步迭代執行下述步驟，直到流向量vE中的數據被讀取完畢為止。B2. 1更新流向量vH:從流向量vH中讀取一個數據/f,若/f <F，則取// —F，並 將K值寫回流向量vH剛才讀取數據的位置；否則忽略本步驟。B2.2更新流向量vE:從流向量vE中讀取一個數據醜，取醜-max(// —仏醜—W， 並將￡值寫回流向量vE剛才讀取數據的位置。B2. 3更新P值取F — F — /i。B2.4迭代條件判定若流向量vE中所有數據均被讀取並寫回，則結束迭代，否則， 重新執行B2. 1 B2. 4的迭代過程。B3 寫回流向量vF:所有p個硬體計算簇將本地計算的F值"向右傳遞"，同時將接 收到的屍值寫回到流向量vF中。詳細過程參見步驟A3。B4 設置"繼續迭代標誌位"若至少有一個硬體計算簇上本地計算結果滿足 F 〉- 2g且F 〉 0,則設置"繼續迭代標誌位"為1，否則置為0。5.1.2.6 令j'增加l，若j <m (m= W是庫序歹i」做長度，見步驟5. 1. 1的說明)， 則重複執行步驟5. 1.2. 3~5. 1.2.6;否則表明庫序列i與査詢序列.s的比對完成，其相似性 比對得分值為V，轉至步驟5. 1.2.7。5. 1. 2. 7 判定是否需要提高計算精度。對K = 2p (見步驟5. 1. 2. 1中的設置)時 計算得到的相似性比對得分值進行上溢檢査，若未發生上溢即V - 65536，則比對得分的 計算結果是正確的，無需修正；若發生上溢即乂 = 65536，則取^ = ^將所有數據改用 精度更高的UINT類型(32位無符號整數，所能表示的數值範圍為0 4 294 967 295)， 重新執行步驟5. 1. 2. 2~5. 1. 2. 7計算局部比對的相似性得分值。在K = p的情形下，儘管 提高了計算精度，但步驟5. 1. 2. 5中的流內核級計算中一條指令同時只能得到p個計算結 果，並發度較K-2p時減半，計算所需時間延長。5. 2從iV'個成對序列比對的得分值中挑出具有最高比對得分值的庫序列作為當前節 點機器返回的搜索結果序列，同時返回其比對得分值。6. 主控節點機器收集各節點機器上並行搜索任務的結果並匯總輸出每個節點機 器完成各自的搜索子任務後，將返回結果發送給主控節點機器，主控節點機器將返回的 這 條結果序列按其比對得分值大小排序，挑選得分值最高的那條序列作為最終搜索結 果並輸出。在本發明生物序列資料庫搜索的整個流程裡，包含了三個層次的並行加速與優化-一是搜索任務在集群的 個節點機器之間並行執行(稱為集群節點層次的加速)，二是每 個節點機器將兩條序列的比對計算任務分配到本地流處理器的P個硬體計算簇中並行進 行(稱為流級層次的加速)，三是每個硬體計算簇中單條指令最多可以同時操作2個UHALF數據類型(稱為核級層次的加速)。其中，集群節點層次的並行加速主要針對傳統生物序 列資料庫搜索中的"分解搜庫任務"這一環節，而流級層次和核級層次的加速優化主要 針對"成對序列的比對"這一環節，體現在流內核計算的"粗計算過程"和"精計算過 程"中，它們均採用與Smith-Waterman算法一樣的動態規劃原理，將計算過程並發到流 處理器的p個硬體計算簇中(即每個硬體計算簇同時執行了 一條流處理器發出的流指令， 每條流指令操作了P個運算過程)。在這兩個流內核計算過程中，每條內核指令操作的均 為32位字長的數據，因此在步驟5. 1.2. 1中(即取K-2p，數據類型採用16位的UHALF 類型)，每條內核指令又可以同時操作2個UHALF類型的數據。這樣，在一條流指令周期 內，有P個硬體計算簇在並發執行，每個硬體計算簇同時執行2個數據的運算，每個流指 令周期共計有2p個運算。但當這種計算精度無法滿足要求而改為執行步驟5. 1. 2. 7時(即
K-P，數據類型為32位的UINT類型)，每個硬體計算簇在一條流指令周期內只能執行 l個運算，每個流指令周期內共計只有p個運算，運行速度將減慢。 與現有技術相比，採用本發明可達到以下技術效果1. 本發明基於核級層次、流級層次以及集群節點層次這三層並行策略、在配置有流 處理器的計算機集群系統上實現了生物序列資料庫搜索的加速，在生物序列資料庫搜索 過程中，充分挖掘了集群節點之間、節點中流處理器的硬體計算簇之間、流內核的指令 操作數之間三個層次的並行潛力，使得搜索與計算速度得以加快。通過在單個節點機器主處理器為Intel Pentium 4 CPU 3.0GHz、協處理器(即流處理器)為主頻500MHz的集 群系統上對本發明的方法進行測試，結果表明，在由8個節點組成的集群系統中，可以 達到每秒計算3.05億個矩陣單元的速度；在由16個節點組成的集群系統中，可以達到 每秒計算5. 60億個矩陣單元的速度，搜索速度遠遠超過了現有 的並行處理類搜索方 法。其中，每秒計算的矩陣單元數是國際上衡量生物序列資料庫搜索速度的標準度量標 準，其計算公式為查詢序列長度X資料庫所有序列的總長度+搜索所用的掛鍾時間。2. 本發明採用具有流處理器的計算機集群系統，流處理器作為普通計算機的協處理 器，具有成本低、計算部件密集、性價比高的優點，克服了傳統專用硬體造價高、普及 率低的缺。3. 本發明通過數據分解策略、將大型生物序列資料庫的搜索任務分解成多個規模較 小的搜索子任務，並分布到集群系統的各個節點機器上並發執行。 一方面增加了搜索任 務的並發度，提高了整體搜索的速度；另一方面，資料庫搜索期間需要將資料庫全部讀 入內存進行處理，多個節點協同工作時，所能搜索的資料庫容量的上限值得到提高(是 所有節點內存容量之和)，從而拓寬了生物序列資料庫搜索的適用範圍(原本只能搜索最大規模為c的資料庫，現在可以搜索最大規模為c ^p的資料庫)。4. 本發明在利用流處理器計算成對序列比對的相似性比對得分值時，採取了多項加 速措施(1)對査詢序列進行了填充與重排，與傳統的Smith-Waterman算法實現相比， 這種數據劃分與數據組織策略能夠有效減少局部相似性比對得分值計算過程的數據依賴 關係，便於進行並行任務的劃分，最大程度地降低並行任務執行期間的通訊開銷，加快 了計算速度。(2)將計算比對得分的過程轉化為對少數幾個流向量數據的操作，利用流 處理器的體系結構特點，基於SIMD並行策略將計算任務分布到多個硬體計算簇上，實現 了並發執行的加速效果。(3)借鑑Green(1993)對Smith-Waterman算法的優化方案，對 計算比對得分值的流處理過程分解成"粗計算"和"精計算"兩個流內核計算過程，當
粗計算過程能返回正確的比對得分值時，就可以省去精計算過程的計算過程，這樣可以 節約計算時間。Green的統計數據表明，在通常的蛋白質序列搜索中，約有73%的成對序 列比對任務在計算比對得分值時只需一輪迭代(即相當於本發明中只執行一次"粗計算" 過程)。5.本發明在流處理器上實現"粗計算"與"精計算"時，採用了自適應動態調整數 據精度的方案，先用"低精度、高並行度"模式進行計算，僅當低精度下的計算結果發 生上溢時，才進一步切換至"高精度、低並行度"模式下重新計算。實際上，只要兩條 序列的比對得分值小於65535,低精度模式就不產生上溢，從而無需高精度模式的執行。 在實踐應用中，用戶提交的査詢序列多是短序列(如長度不超過1000)，其資料庫搜索與 比對的最高比對得分值都不會超出這一上限。這種獨特的處理方式充分開發了流內核層 次中的並行潛力，為搜索過程的加速提供了貢獻。綜上所述，本發明依照"成本性能兼顧、軟體硬體結合"的原則，藉助於帶有流處 理器的計算機集群系統，採用"分解搜庫任務"與"成對序列比對"兩個環節綜合加速 的策略，在流處理器實現了 "成對序列的比對"方法；對生物序列資料庫"分解搜庫任 務"進行了並行處理；在流處理器的核級層次、流級層次以及集群處理器層次進行了三 層加速優化，以較小的成本實現了生物序列資料庫搜索的明顯加速。


圖l是本發明的總流程圖。圖2是本發明中資料庫序列的分布存儲流程示意圖。圖3是本發明中査詢序列的填充對齊與重排流程示意圖。圖4是本發明中每個集群節點機器計算兩條序列的比對得分值流程圖。圖5是本發明中流內核計算的"粗計算過程"流程圖。圖6是本發明中流內核計算的"精計算過程"流程圖。具體實施方案圖l是本發明的總流程圖，主要包括以下六個步驟，其中第1 2步是集群系統的建 立和資料庫序列的預處理，只需在系統建立之初及資料庫有更新時執行一次，在以後每 一次具體的搜索資料庫任務中，僅需執行第3 6步即可。1.構建帶流處理器的集群系統。該集群系統由多臺個人計算機組成，每臺計算機都 是集群系統的節點，各節點有著各自獨立的存儲系統，節點之間的通信採用消息傳遞的
方式。節點依次編號為0，1,2，...， -1。這裡 為集群系統中節點的總數目(實際系統 中， 的取值為2的整數次冪等)。為了便於後續處理，指定編號為O的那個節點機器為 主控節點機器，它主要負責與用戶交互，完成輸入輸出及對搜索結果的中間處理。每個 節點除了自身的主處理器外，還配置一個流處理器為該節點的協處理器；流處理器主要 由存儲部件、計算部件和控制部件組成，其中計算部件是流處理器的主體，它包含有p個 硬體計算簇單元，在實施計算時，P個硬體計算簇可利用SIMD方式同時處理流向量中的p 個數據，達到並行處理的加速效果。實際系統中p是流處理器中硬體計算簇單元的數目， 它是由具體的流處理器型號所決定的。2主控節點機器將資料庫序列分布存儲到各個節點機器。將待搜索的生物序列數據 庫分解成容量幾乎相等的 份，並分布存儲到集群系統中的 個節點機器中去，具體分 解的方法見圖2的說明。本步驟需要在進行搜索之前完成，而且每當資料庫的序列有變 更(如增加、刪除、修改)時就執行一次本步驟。3主控節點機器對查詢序列進行填充與重排。首先對查詢序列進行尾部填充空元素 的操作，使填充後的查詢序列長度是2p的整倍數(？ = 8是集群系統中每個節點機器中流 處理器上的硬體計算簇的數目)，然後再對該序列進行元素的重排。查詢序列的填充與重 排過程詳見圖3的說明。本步驟的任務只在集群系統中的總控節點(編號為0的節點) 機器上執行。4主控節點機器將查詢序列分布存儲到各個節點機器。由總控節點機器負責將上述 填充與重排後的查詢序列分發給集群系統中的每個節點機器。5並行執行資料庫搜索任務。通過上述對資料庫序列和查詢序列的分布存儲，集群 系統中的每個節點機器本地存放著一個生物序列數據的子集(子資料庫)和一條查詢序 列，各節點各自獨立、並行地執行查詢序列對本地子資料庫的搜索任務，搜索完成後， 每個節點機器返回當前節點本地子資料庫中比對得分值最高的一條序列(連同比對得分 值本身)。搜索的詳細過程見圖4的說明。6主控節點機器收集並匯總資料庫搜索的結果。由主控節點負責收集所有節點機器 的搜索結果，共得到 條子搜索結果序列，選出其中比對得分值最高的那一條序列(連 同比對得分值)，作為整個資料庫搜索任務的最終輸出結果。圖2是本發明第二步中對生物序列資料庫的數據分解與分布存儲流程示意圖，主要 過程為1對原始的生物序列資料庫中的所有序列依長度從大到小到排列，並依次編號為
0,l，2,...,iV —1，其中7V是資料庫中序列的總數目(圖2中/V-19)。2將每條序列的編號按圖中的箭頭方向順次排列成陣列，每行rip個編號(np是集群 系統中節點機器的數目，圖2中 =4)，第l行從左向右排列編號，第2行從右向左排 列編號，其餘行依次類推(即奇數行從左向右排列編號，偶數行從右向左排列編號，最 後一行可能出現排不滿的情況)；排列完成後，將第l列中的編號所對應的庫序列分配給 0號節點，將第2列中編號所對應的庫序列分配給1號節點，依此類推，將最右邊一列中 編號所對應的庫序列分配給 - l號節點。如果用i'表示編號為i的序列所分配的節點編號 (i = 0，l:...，iV —1)，則上述過程可以用數學公式簡潔表示為'若io < ，則取7:' = 7:0; 否貝U (即'i'o上np)，取i'= 2np — 1 — i0。式中，i0 = "uod (2 )。圖3是本發明第三步中査詢序列的填充對齊與重排流程示意圖，具體過程為 1原始査詢序列的數據填充與補齊。在查詢序列的尾部填充空元素NUL，使填充後的 查詢序列長度是2p的整倍數(p = 8是集群系統中每個節點機器中流處理器上的硬體計算 簇的數目)。在此過程中，要遵循"填充空元素的個數要儘可能少"的原則，即如果查 詢序列的長度W是2p的整倍數，則不填充；否則在查詢序列的尾部追加2p - rx' mod (2p)個 空元素。在示意圖3中，原始序列長度rV二69， 2p=16，在末尾填充11個空元素，從 而使填充後的序列長度為n = 80。2查詢序列的重排。為了適應於流內核計算的需求，需要將填充後的查詢序列重新 組織，這個過程包括兩步首先將長度為n的查詢序列順次劃分成K個相同大小的數據塊， 每個塊大小為n/K，如圖3所示，將這些數據塊從上到下排列成一個陣列，每個數據塊 佔一行；其次，將形成的陣列進行轉置，然後順次從上到下逐行(每行中的數據從左向右依次)讀出，形成重排後的查詢序列。若,=.^，.5'1',...,《—i表示填充補齊後的查詢序 列，S^SQ，&，...， —i表示重排後的序列，則上述重排過程可用數學公式表示為 & =《m。dK)K+Ll/AT其中 : = 0， 1, 2,... ，rz — 1。上述重排過程中用到的參數K = p或2p， 其中p為每個流處理器上硬體計算簇的數目，/(的兩種取值分別代表了不同的數值精度和 並行粒度當K-2p時，採用較低精度的UHALF類型數據進行計算，硬體計算簇中的每 條指令可同時計算兩個結果，並行度較大；反之當K-P時，採用較高精度的UINT類型 數據進行計算，硬體計算簇中的每條指令只能計算一個結果，並行度較小。圖4是本發明第五步中每個集群節點機器執行序列比對任務的流程圖，主要過程為: 1輸入查詢序列s，這裡的查詢序列是經過填充對齊與重排後的序列(如圖3)，用 = H表示查詢s的長度。 2每個節點機器從本地資料庫中取一條未參與過比對的序列"記其長度為爪=|,|。3首先取K-2p，所有參與計算的數據取為16位的UHALF類型。4初始化置局部相似性比對得分值卩=0，置流向量vH
和vE[O..r ,-lj為全0值。置庫序列糹的當前列標誌j-O。5設置流向量vM的值針對庫序列的第j個位置，通過查詢匹配打分矩陣設置vM[O..rx-l]流向量的新值。其中，若.s,:為"空字符"NUL，則取vM[7;]-0;否則，取vMW-S(s，:,i,)，即.、與~在打分表中對應的打分值。這裡，A表示查詢序列的第i個字符，^表示庫序列的第j個字符，i = 0,1，... ，rx - 1。6設置流向量vH'的值將流向量vH的尾部p個元素複製給vH'[a.p —l]，同時將vH'的元素依次向右移動一個位置，空出的最左端元素vH'問置為0值。7 "粗計算"以vH，vE，vM,vH'四個流向量為輸入，利用動態規劃原理對vH， vE和vF三個流向量及當前的局部相似性比對得分值V進行更新，並返回"繼續迭代標誌位，，loop—more。8根據"繼續迭代標誌位"loopjnore的取值進行流程分支執行若loop_more = 1, 則轉第9步；否則轉至第10步。9 "精計算"以vH, vE和vF三個流向量為輸入，是利用動態規劃原理對vH, vE和 vF三個流向量進行修改與更新，並返回"繼續迭代標誌位"loop—more。執行完畢後轉第 8步根據loopjnore的取值進行流程分支。10更新庫序列的當前列標誌位j — j' + 1，若j < m = |t|，則轉第5步繼續處理庫序 列的下一列；否則轉第ll步。11判定精度是否滿足要求若K-2p且比對得分值l/發生上溢，則轉第12步重新 使用更高的精度進行計算；否則已經完成當前s和^的比對得分值計算，轉第13步。12重新取^=仏所有參與計算的數據取為32位的UINT類型。然後轉第4步完成 更高精度的計算過程。13保存參與本次比對的庫序列f及其比對得分值V。14若所有庫序列均已參與過序列比對，則當前節點對所有的庫序列按照比對得分值 的大小排序，輸出比對得分最高的那條庫序列連同其得分值；否則轉第2步對剩餘的庫 序列進行比對計算。圖5和圖6分別是本發明中"粗計算"與"精計算"兩個流內核計算過程的流程圖， 其中，符號》表示數據從流向量中"流出"(即讀取)到普通變量中去，符號《表示將普 通變量中的數據"流入"(即回寫)到流向量中去。在粗計算過程中，輸入vH，vE，vM,vH'四個流向量，藉助if,E,F等普通變量完成對 vH, vE和vF三個流向量的計算與更新，並輸出局部比對得分值V和繼續迭代標誌位 lo叩jnore。具體實現過程如下，其中第1 8步是在多個硬體計算簇上獨立、並發執行 的1初始化vH'》//，置F-0。2讀取流數據vM》M， vE》E。3更新比對得分值V:置V —maX{K，// + Af}，其中max表示取最大值運算。 4更新孖值並回寫取// —max{// + M,￡;,F;0}，並回寫vH《//。 5更新E值並回寫取五—max(E-/i,if— .9}，並回寫vE《醜。 6更新P值取F — max(F — / ,，// — .9}。7迭代條件判定若流向量vE中所有數據均被讀取並寫回，則結束迭代並轉第8步；否則，先從流向量vH中讀取一個數據// (vH》/Z)，轉第2步重新迭代。8寫回流向量vF:所有p個硬體計算簇通過消息發送機制將本地計算的F值"向右傳 遞"，同時將接收到的(來自左側鄰居的)P值寫回到流向量vF中。所謂"向右傳遞"， 是指編號為i的硬體計算簇將本地計算得到的^值傳遞給編號為z + l的硬體計算簇 (7: = 0,1:2，...，P —2)，編號為p —l的硬體計算簇的屍值捨棄，編號為0的硬體計算簇的 F值更新為0。9匯總所有硬體計算簇上獲得的最佳比對得分值每個硬體計算簇在上述迭代結束 後都獲得一個本地的局部比對得分值V，通過在p個硬體計算簇之間進行數據通訊，選出 p個比對得分中的最大值，作為輸出結果。10設置"繼續迭代標誌位"loop—more:若至少有一個硬體計算簇上本地計算結果 滿足F 〉 vH問—/7且F 〉 0，則設置loop—more為1，否則置為0。在精計算過程中，輸入vH，vE,vF三個流向量，藉助仏醜，F等普通變量完成對vH，vE 和vF三個流向量的計算與更新，並輸出繼續迭代標誌位loop—more。具體實現過程如下， 其中第i 8步是在p個硬體計算簇上獨立、並發執行的-1初始化vF》F。2更新H值並回寫vH》//，取// —max(7/,i^，並回寫vH《//。3更新醜值並回寫vE》醜，取E — max(醜—.9}，並回寫vE《￡。4更新F值取F — F-Zi。
5迭代條件判定若流向量vE中所有數據均被讀取並寫回，則轉第6步結束迭代； 否則，轉第2步重新迭代。6寫回流向量VF:所有p個硬體計算簇通過消息發送機制將本地計算的F值"向右傳遞"，同時將接收到的(來自左側鄰居的)F值寫回到流向量vF中。所謂"向右傳遞"， 是指編號為i的硬體計算簇將本地計算得到的F值傳遞給編號為i + l的硬體計算簇 G: = 0,l,2，...，p — 2)，編號為p-l的硬體計算簇的F值捨棄，編號為0的硬體計算簇的 P值更新為0。7設置"繼續迭代標誌位"lcx)p_m0re:若至少有一個硬體計算簇上本地計算結果滿 足F 〉 i — 2.9且P > 0，則設置loop—more為1，否則置為0。
權利要求
1.一種基於流處理的生物序列資料庫搜索多層次加速方法，其特徵在於使用配置有流處理器的計算機集群系統，對生物序列資料庫搜索過程中的「分解搜庫任務」與「成對序列比對」這兩個核心環節進行資源分配與任務劃分，實現集群節點層、流級計算層、流內核指令層三個層次的多級並行提速，具體方法是第一步，構建由多臺個人計算機組成的集群系統，每臺計算機都是集群系統的節點，各節點有著各自獨立的存儲系統，節點之間的通信採用消息傳遞的方式；節點依次編號為0，1，2，…，np-1，np為集群系統中節點的總數目，指定編號為0的那個節點機器為主控節點機器，它負責與用戶交互，完成輸入輸出及對搜索結果的中間處理；每個節點除了自身的主處理器外，還配置一個流處理器為該節點的協處理器；流處理器中的計算部件包含有p個硬體計算簇單元，p個硬體計算簇利用SIMD方式同時處理流向量中的p個數據；p是流處理器中硬體計算簇單元的數目，它由具體的流處理器型號與配置所決定；第二步，主控節點機器將資料庫序列分布存儲到集群系統中各個節點機器，即在創建資料庫和增量更新數據時，將生物序列資料庫中的序列數據平均分布到集群系統中不同節點的存儲器中；第三步，主控節點機器對查詢序列進行填充及重排；第四步，主控節點機器將查詢序列分發到集群系統中的各個節點機器，即主控節點機器將填充與重排後的查詢序列分發給計算機集群系統中的所有節點，每個節點機器將該查詢序列及存放於本地存儲器中的資料庫序列一併讀入本地內存；第五步，各個節點機器並行執行搜索任務，每個節點機器負責完成查詢序列在本地資料庫序列中的搜索任務，搜索的結果是一條比對得分值最高的結果序列及其比對得分值；第六步，主控節點機器收集各節點機器上並行搜索任務的結果並匯總輸出每個節點機器完成各自的搜索子任務後，將返回結果發送給主控節點機器，主控節點機器將返回的這np條結果序列按其比對得分值大小排序，挑選得分值最高的那條序列作為最終搜索結果並輸出。
2. 如權利要求1所述的基於流處理的生物序列資料庫搜索多層次加速方法，其特徵 在於主控節點機器對資料庫序列進行分布存儲的方法是2.1主控節點機器對資料庫序列按照序列長度進行降序排列，形成一個序列列表 seq[O]， seq[l]， ...， seq[iV-l]，其中iV是生物序列資料庫中序列的總數目；2.2主控節點機器將序列列表中的每條序列分發到集群系統中的各個節點中去，分 發規則是將seq[z]這條序列分發到編號為i'的節點的局部存儲器中，i'的計算方法是 若io〈'"p，則取7:'-io;若^蘭 ，則取i'= 2n,, — 1 - i0，式中，i0 = i mod (2np)， : = 0,l，...，iV — 1。
3.如權利要求1所述的基於流處理的生物序列資料庫搜索多層次加速方法，其特徵 在於主控節點機器對查詢序列進行填充及重排的方法是3. 1主控節點機器對査詢序列進行數據填充與補齊如果查詢序列s'的長度M'是2p的 整倍數，則跳至步驟3. 2，否則在查詢序列的尾部追加2p - n' mod (2p)個"空元素"NUL， 填充補齊後的查詢序列記作s〃，其長度用n表示；3.2主控節點機器對査詢序列進行重排將填充補齊後的查詢序列 ,=,《…，重新組合為s = s。:... ， n '其中s！=《m。d w.k+wj ，i = 0,1，...，", 一 1, Ki或2p。
4. 如權利要求l所述的基於流處理的生物序列資料庫搜索多層次加速方法，其特徵在於各節點機器執行搜索任務的過程是4.1使用流處理器、結合流處理器體系結構及Smith-Waterman比對算法的特點，基 於SIMD並行策略計算出査詢序列與節點本地資料庫中每條序列的比對得分值，獲得iV'個 比對得分值，其中iV'是本地資料庫中序列的數目；每條庫序列與査詢序列之間的成對序 列比對得分值的計算過程為-4.1.1確定成對序列比對過程中的參數，方法是*參與比對的兩條序列中， 一條是査詢序列，用符號s表示，其長度記為n;另一條是資料庫序列，用符號糹表示，其長度記為m; * S表示成對序列比對Smith-Waterman算法中的匹配打分矩陣，對於核酸序列數據而言，默認使用"替換-置換打分矩陣"，對於蛋白質序列數據而言，默認使用Blosum 50打分矩陣，根據應用問題的需求還可指定包含Blosum 62及P細系列在內的其它打分矩陣； .9和/i表徵成對序列比對過程中出現空位時的仿射罰分模型參數，即對於長度為A;的空位區，其罰分值為g + (A: —1)^,這兩個參數默認取值為9 = 14，/1 = 2; 4. 1. 2構造五個輔助流向量vH[O..n — l]， vE[O..n - 1], vM[O..", 一 1], vF[O..p — l]和 vH'[O..p-l]，利用流處理器計算查詢序列s與庫序列糹的局部相似性得分，計算過程如下: 4.1.2.1取K二2p，所有參與計算的數據均使用UHALF類型，這種數據類型的精 度為半字長即16位無符號整數，所能表示的數值範圍為0 65535; 4. 1. 2. 2 初始化流向量vH與vE:為流向量vH[O..n — lj和vE[O..n — l]賦以全0的初 值；置流向量vF[O..p-l]的初值為全0;置庫序列位置標誌j為0，置局部相似性比對得分值V為0;4.1. 2. 3計算流向量vM的值針對庫序列的第j'個位置，通過查詢匹配打分矩陣S , 設置vM[O..n —l]流向量的新值，其中，若.s,為"空字符"NUL，則取vM[i]為0值；否則， vM[i]取為^與^在打分表中對應的打分值S(s,，G)， .s,表示查詢序列的第z個字符，^表示庫序列的第j個字符，7: = 0，1:...:77,— 1;4. 1. 2. 4設置流向量vH'的值將流向量vH的尾部p個元素複製給vH'[O..p - l]，同 時將vH'的元素依次向右移動一個位置，空出的最左端元素vH'[O]置為0值；4.1.2.5 在流內核級完成相似性比對得分值的計算以vH，vE,vM，vH'四個流向量 為輸入，通過多輪迭代過程計算得到最終的相似性比對得分值V，第一輪迭代計算稱為"粗計算過程"，後續輪次的計算稱為"精計算過程"，這兩個過程都是採用SIMD策略由 流處理器的P個硬體計算簇並行完成；"粗計算過程"以vH，vE，vM，vH'四個流向量為輸 入，利用動態規劃原理計算，輸出vH， vE和vF三個流向量及當前的局部相似性得分值V 的更新值；"精計算過程"以vH， vE和vF三個流向量為輸入，利用動態規劃原理進行多 輪迭代計算，每輪計算都對vH， vE和vF三個流向量的取值進行更新，並根據當前計算結 果設置一個"繼續迭代標誌位"，若繼續迭代標誌位為l，則重新執行新一輪的迭代計算； 若繼續迭代標誌位為0，則表示計算過程完成，轉至步驟4.1.2.6;4.1.2.6 令j增加1，若j'〈'm, m = W是庫序列f,的長度，則重複執行步驟 4. 1. 2. 3~4. 1. 2. 6;否則表明庫序列t與查詢序列s的比對完成，其相似性比對得分值為V， 轉至步驟4.1. 2. 7;4. 1. 2. 7 判定是否需要提高計算精度，對K = 2p時計算得到的相似性比對得分值 進行上溢檢査，若未發生上溢即V ^ 65536，則比對得分的計算結果是正確的，無需修正； 若發生上溢即乂 = 65536，則取K^p，將所有數據改用精度更高的UINT類型，重新執行 步驟4. 1. 2. 2 4. 1. 2. 7計算局部比對的相似性得分值；4. 2從iV'個成對序列比對的得分值中挑出具有最高比對得分值的庫序列作為當前節 點機器返回的搜索結果序列，同時返回其比對得分值。
5. 如權利要求4所述的基於流處理的生物序列資料庫搜索多層次加速方法，其特徵在於所述粗計算過程中每個硬體計算簇執行如下步驟Al初始化從vH'流向量中讀取一個數據i/，置F的值為0; A2 迭代步持續執行下述步驟，直到vE向量中的數據被讀取完畢為止；A2.1讀取流數據從流向量vM中讀取一個數據M，從流向量vE中讀取一個數據E;A2. 2更新比對得分值V:若H + M > V，則更新比對得分為V — /f + M;A2.3更新/f值並寫回流向量vH:取// —max(/Z + M，JE;,F，0L並用所得的/f值更 新流向量vH中最近一次讀取的舊數據；A2.4更新E值並寫回流向量vE:取￡ —111肌{五一、7/-.9}，並用得到的E值更新 流向量vE中最近一次讀取的舊數據；A2. 5更新F值取F — max(F - 、 —A2.6迭代條件判定若流向量中所有數據均被讀取並寫回，則結束迭代，否則，先 從流向量vH中讀取一個數據if ，再重新執行A2.廣A2. 6的迭代過程；A3 寫回流向量vF:所有p個硬體計算簇將本地計算的P值"向右傳遞"，同時將 接收到的來自左側鄰居的F值寫回到流向量vF中，"向右傳遞"是指編號為i的硬體計算 簇將本地計算得到的F值傳遞給編號為i + l的硬體計算簇( : = 0,1: 2，... ，;> - 2)，編號為 P - 1的硬體計算簇的F值捨棄，編號為0的硬體計算簇的F值更新為0，數據傳遞通過消 息發送機制完成；A4 匯總所有硬體計算簇上獲得的最佳比對得分值每個硬體計算簇在上述迭代結 束後都獲得一個本地的局部相似性比對得分值V，通過在p個硬體計算簇之間進行數據通 訊，選出p個比對得分值中的最大值，作為流內核計算中粗計算過程的執行結果；A5 設置"繼續迭代標誌位"若至少有一個硬體計算簇上本地計算結果滿足 F 〉 vH問一 .g且F 〉 0，則設置"繼續迭代標誌位"為1，否則置為0，"繼續迭代標誌 位"也作為流內核計算中粗計算過程的執行結果返回。
6.如權利要求4所述的基於流處理的生物序列資料庫搜索多層次加速方法，其特徵 在於所述精計算過程中每輪迭代計算所執行的步驟如下Bl 初始化從流向量VF中讀取一個數據P;B2 迭代步迭代執行下述步驟，直到流向量VE中的數據被讀取完畢為止；B2.1更新流向量vH:從流向量vH中讀取一個數據//，若H〈F，則取// —F，並將i/值寫回流向量vH剛才讀取數據的位置；否則忽略本步驟；B2.2更新流向量vE:從流向量vE中讀取一個數據j5，取E二max(^ —仏E-W，並將E值寫回流向量VE剛才讀取數據的位置； B2. 3更新F值取F — F — /1; B2.4迭代條件判定若流向量vE中所有數據均被讀取並寫回，則結束迭代，否則， 重新執行B2.廣B2. 4的迭代過程；B3 寫回流向量vF:所有p個硬體計算簇將本地計算的F值"向右傳遞"，同時將接 收到的F值寫回到流向量vF中；B4 設置"繼續迭代標誌位"若至少有一個硬體計算簇上本地計算結果滿足 P 〉 // _ 2.9且屍〉0，則設置"繼續迭代標誌位"為1，否則置為0。
全文摘要
本發明公開了一種基於流處理的生物序列資料庫搜索多層次加速方法，目的是在保證搜索準確性、較低成本的前提下，加快生物序列資料庫搜索速度。技術方案是先構建由多臺個人計算機組成的集群系統，指定一個主控節點機器；主控節點機器將資料庫序列分布存儲到集群系統中各個節點機器，對查詢序列進行填充及重排，且將查詢序列分發到集群系統中的各個節點機器；各節點機器並行執行搜索任務，負責完成查詢序列在本地資料庫序列中的搜索任務；主控節點機器收集各節點機器上並行搜索任務的結果並匯總輸出。採用本發明使得搜索任務在集群的np個節點機器之間並行執行，每個節點機器將兩條序列的比對計算任務分配到p個硬體計算簇中並行進行，實現了集群節點層、流級計算層、流內核指令層三個層次的多級並行提速的目標。
文檔編號G06F17/30GK101158952SQ20071003619
公開日2008年4月9日 申請日期2007年11月22日 優先權日2007年11月22日
發明者彭宇行, 徐傳福, 王勇獻, 王意潔, 王正華, 董蘊源, 車永剛, 邢座程 申請人:中國人民解放軍國防科學技術大學