[發明專利]基于CPU+GPU異構的高并發序列比對計算加速方法

有效

• 申請號: 202210046617.1
• 申請日: 2022-01-17
• 公開（公告）號: CN114064551B
• 公開（公告）日: 2022-05-17
• 發明（設計）人: 張巍;林超寧;張崇
• 申請（專利權）人: 廣州嘉檢醫學檢測有限公司
• 主分類號: G06F15/16
• 分類號: G06F15/16;G06F9/48
• 代理公司: 廣州君策達知識產權代理事務所(普通合伙) 44749
• 代理人: 陳宏升

本發明公開了基于CPU+GPU異構的高并發序列比對計算加速方法，包含以下步驟：BWA?MEM算法代碼重構；CPU上任務并發處理：完成序列集的劃分，第一次形成多個并發任務；運行代碼重構后的BWA?MEM算法，完成GPU上數據并發處理；GPU上任務并發處理：對于序列數據對比過程中產生的種子集和鏈，將相同或相鄰的長度、位置、數量的種子集劃分為同一數據塊，鏈做同樣處理，由此完成種子集與鏈的劃分，第二次形成多個并發任務。本發明通過設計任務并行+數據并行的方式，讓BWA?MEM算法的特征與GPU加速設備的特征緊密結合，充分利用GPU強大的并發運算能力，為序列比對算法提供優異的性能，對比高并發處理效率較高。

技術領域

本發明涉及生物序列比對領域，特別涉及基于CPU+GPU異構的高并發序列比對計算加速方法。

背景技術

生物序列比對是計算機領域經典的文本比對問題在生物領域的應用。隨著不斷涌現的新型分子生物學技術的發展 ,隨之而來的比如基因變異、RNA表達、蛋白質和基因相互作用等分子生物學研究需要研究人員采用高通量的方法去解釋。這對高性能計算提出了新的挑戰。高通量測序時代的挑戰不再是數據的產生，而是數據存儲，處理和分析。第三代測序技術的發展將進一步加快測序速度，同時產生較長的測序片段，對序列比對技術的發展提出了更高的要求。與此同時，計算機硬件平臺也在近幾年飛速發展, 不斷推陳出新，新的多核平臺和眾核平臺不斷出現，眾核處理器加速設備如GPU使高性能計算機的性能快速提高，GPU異構平臺正成為構建高性能計算機的重要方式。這也使得計算機體系結構變得越來越復雜，給計算程序的優化帶來了新的難題。

同時，在生物序列比對領域中，采用CPU+GPU異構平臺的方式對算法進行加速時一個常見的處理方式。

比如，文獻《基于GPGPU的生物序列快速比對》（第一作者馬海晨，發表于期刊《計算機工程》第38卷第4期，2012年2月），是在CPU-GPU 異構平臺下，提出一種高效的生物序列比對方案。該方案利用GPU的并行處理能力，通過對讀延遲、寫延遲、重組函數及數據傳輸進行優化，在OpenCL 框架下重構Smith- Waterman 算法，加快生物序列比對速度。即該文獻主要是對SW算法（即Smith- Waterman 算法）進行優化。

再比如，工程碩士論文《生物序列分析算法的CPU_GPU異構并行優化關鍵技術研究》（作者萬文，國防科學技術大學研究生院，2012年3月），其核心思想同樣是基于CPU和GPU構建的異構系統，主要是對SW算法（即Smith-Waterman算法）進行優化。

上述技術方案，都是對某個具體算法（例如SW算法、FM-index算法）進行優化或者改進，這些技術方案均是聚焦于算法本身，利用GPU的特性，來解決數據并行的問題，通過對所采用具體算法的改進，來達到生物序列比對速度提升的目的，其缺點在于：在進行生物序列比對時，要先找到一段比較精確的匹配子段作為seed，對于不同的reads，其包含的SMEM長度、位置、數量都有很大的不同；當在GPU平臺用采用每個線程處理一個reads的任務劃分方式時，這會造成不同線程之間嚴重的不同步，包含較短SMEM的reads需要等待包含較長SMEM的reads查找完畢, 而對于包含較短SMEM的reads，其包含的SMEM的個數又更多，這樣包含較長SMEM的reads又反過來需要等待包含較短SMEM的reads，這種互相等待的情況導致計算資源利用率極低，加速效果非常有限。上述技術方案聚焦于數據并行的問題（進一步加大數據并行的能力），并不能克服所述缺點。

同樣，由于BWA-MEM的這種與輸入數據高度相關的seeding方式，每個reads包含的seed數量、長度都會有很大不同，這又會影響下一個模塊中根據seed生成chain的過程，導致生成chain的模塊的不同線程同步性很差，進一步限制了加速效果。由于算法的運行特征與輸入數據高度相關，這些方法無法同時適合不同特征的輸入數據。 GPU平臺對于同一warp內指令一致性的要求使BWA-MEM算法的加速效果受到了嚴重限制。因此，對于原有的BWA-MEM算法同樣不能解決上述問題。

發明內容