一種基於CPU+MIC異構平臺的SIFT並行算法的製作方法

2023-06-03 02:21:16 2

本發明異構平臺的SIFT並行算法的實現技術，尤其涉及一種基於CPU+MIC平臺異構計算的並行加速的處理方法。
背景技術：
：：SIFT算法是用來預測當胺基酸變化是否會影響蛋白質的功能的工具，應用於在自然界中突變或者是在實驗室的人工誘導變異。SIFT首先通過blast來查找同源序列，然後使用PSI_BLAST選擇相近的相關序列，最後計算胺基酸的轉換是否影響蛋白質的功能，具體流程，如圖1所示。可以看出SIFT算法是由PSIBLAST算法以及其他後續處理算法組成。PSIBLAST是SIFT算法的核心算法，是基於局部序列比對的資料庫相似性搜索工具，一種啟發式搜索算法，其核心在於:seeding和extending。流程如下所示：1.建立查詢字串的列表(makelookuptable)a)按照字長為W(蛋白一般為3)劃分查詢序列，構建W字長的字串列表，b)尋找所有與字串匹配比對分值大於閾值T的鄰居字串(根據打分矩陣)，將它們也加入查詢字串列表中去2.在資料庫中搜索增強點(Seeding階段)：在資料庫中搜索，與查詢字串列表中的字串精確匹配的形成一個hit增強點，作為下一步的種子；3.擴展種子(Extending階段)：對於種子，根據打分矩陣沿左右兩個方向延伸直到分值低於一個閾值S，得到的結果稱為HSP；4.根據得分矩陣的進行回溯，得出比對結果序列。基本blast算法是不考慮空位插入的，但在生物進化過程中鹼基的插入或缺失突變是普遍存在的，因此比對結果中常會出現一些無空位但不連續的區域，若將這些高分分值片段對通過一些相似性較低且有空位的片段連接起來，就能形成一些更長或更有實際意義的比對，因此改進的BLAST算法允許空位的出現，在多個HSP中，找一個最好的得分最高的片段對(MSP)，以此基礎運行動態規劃將一片段向序列的兩段延伸，最終產生一個積分較高的最佳比對結果，且有可能空位產生。改進算法(含空位)流程：（1）採取two-hits階段，即距離小於A而得分大於T的兩個相鄰hits串聯起來形成種子進入下一步；（2）兩步擴展：首先對種子進行不含空位擴展，形成HSP(最初版本的BLAST)，之後進行含空位的擴展。PSI-BLAST(PositionSpecificIterativeBLAST)，位點特異的迭代blast搜索，主要針對蛋白序列，主要搜索與感興趣蛋白遠源相關的蛋白。第一次blast搜索後，結果中最相似的序列重新構建PSSM(位點特異打分矩陣)，然後根據此矩陣進行第二次blast搜素，再調整矩陣，搜索，調整矩陣，如此迭代。與blastp程序相比，提高了搜索的靈敏度。（傳統的BLAST對打分矩陣依賴大，HSP的計分值都依賴固定的計分矩陣，建立的PSSM使不能被搜索到的遠緣蛋白被比對上），PSIBLAST流程圖如圖2所示。計算速度對於高性能計算尤為重要，高性能計算將朝多核、眾核發展，採用異構並行提升應用計算速度，目前CPU+MIC是非常成熟的異構協同計算模式，適合高度並行計算的應用或算法，如生物信息學、計算流體力學應用、FFT計算等，但由於MIC協處理器在編程效率、細粒度並行算法設計、大規模並行性能上都存在巨大挑戰。隨著IntelKNL(KnightLightsLanding)的正式發布，CPU+MIC將是高性能計算一個不錯的選擇，利用KNL的眾核、兼容傳統CPU平臺二進位程序的等其他技術特點，特別適合併行度高的算法，採用此架構能在提升應用性能的同時大大提高編程效率，MIC能與CPU完美結合解決更多的應用性能瓶頸，但對於某些向量化程度不高、內存密集型應用其性能也面臨著挑戰，將極大滿足不同應用的計算性能需求。技術實現要素：本發明要解決的技術問題是針對SIFT算法的特性及並行處理的思想，利用CPU+MIC異構平臺的優點，尤其是Intel新一代KNL協處理器的特性，以實現整個算法效率大幅提升，並解決傳統CPU計算方法以及系統應用的性能低下、生產效率低等問題。為解決上述技術問題，為此，本發明針對CPU+MIC異構平臺提供一種基於CPU+MIC異構平臺的SIFT並行算法，它具有算法效率大幅提升，並解決傳統CPU計算方法以及系統應用的性能低下、生產效率低等問題的優點。本發明提供了一種實現針對CPU+MIC異構平臺、及SIFT算法的並行處理思想；並聯合MPI進行並行計算進行蛋白質序列比對並行處理的集群系統，該系統分為硬體系統和PSIBLAST算法軟體系統，其中硬體系統包括：一個主處理器平臺的系統和多個協處理器平臺加速平臺，其中主處理器採用純CPU晶片計算，協作加速平臺才用基於Intel的MIC技術的KNL平臺加速處理；專用OPA高速網絡，用於連接MIC集群中每個節點，每個節點可以互相實現高速通信，硬體體系結構圖如圖3所示。為了實現上述目的，本發明採用如下技術方案。一種基於CPU+MIC異構平臺的SIFT並行算法，對SIFT算法中核心模塊進行MIC上的加速，利用消息傳遞機制系統，對當前多序列進行分割，形成多條單蛋白質序列，對每條蛋白質序列進行並行加速處理、在資料庫中進行序列比對，挖掘其並行度。基於CPU+MIC異構平臺的SIFT並行算法，具體包括：第一步，初始化各參數，包括查詢長度、打分矩陣、閾值T、比對序列資料庫、迭代次數、顯著性分析的期望值、比對長度等，對序列比對模塊PSIBLAST並行計算，第二步，對蛋白質多序列數據按照生物信息學的標準進行分割處理。第三步，利用MPI消息傳遞機制進行多條蛋白質數據序列的分發，分發至MIC集群進行加速運算。第四步，比對結果輸出對齊統計、根據種子中位選擇蛋白質序列、序列排序、生成預測信息、數據合併處理。PSIBLAST並行算法首先將整個序列群體分解成若干個子群,然後針對各個子群,同時並行進行子群內部的序列比對算法的運算,由於各個子群中蛋白質序列數據是相互獨立而不相關的,所以能夠很好地進行並行計算。另外,各個子群中序列的數據不相關,進行序列比對時,非常合適並行計算。由此可見,可以將各個子群分配利用多處理器節點或者多線程的方式進行遺傳算子並行操作,提高整個PSIBLAST算法的運行效率，實現計算規模的擴展，滿足高性能應用的要求。本發明使用在蛋白質序列資料庫分割並行算法的模型基礎上,提出了基於查詢序列分割算法,查找序列分割算法採用生物信息蛋白質分割技術,對蛋白質多查詢序列數據進行有效合理分割。查詢序列分割算法的輸入是單文本中多條待進行序列比對的蛋白質查詢序列,輸出結果是序列比對的數據集，基於MPI的PSIBLAST算法流程。為了更好地加速SIFT算法，本發明算法分為三部分結構:(1)對SIFT算法中核心的序列比對算法模塊PSIBLAST進行MIC平臺的加速，並利用向量化、多線程的方式達到一個理想的加速效果;(2)SIFT算法中的其他流程利用CPU平臺的高頻率特點進行CPU的計算，並很好地與PSIBLAST算法進行異構協同加速。(3)對多蛋白質序列數據進行有效分割，並行處理計算運行SIFT算法，進一步挖掘SIFT算法的並行度，為了提高並行挖掘的效率，根據數據流的特點,基於MPI的並行計算模式，提高算法效率。本發明的有益效果：本發明實現整個算法效率大幅提升，並解決傳統CPU計算方法以及系統應用的性能低下、生產效率低等問題。附圖說明圖1.SIFT算法流程示意圖。圖2.PSIBLAST算法流程示意圖。圖3.CPU+MIC異構平臺系統。圖4.CPU+MIC異構平臺SIFT並行算法示意圖。具體實施方式下面結合附圖與實施例對本發明作進一步說明。如圖3、圖4所示，一種基於CPU+MIC異構平臺的SIFT並行算法，為進行異構加速計算，將p53數據發送至MIC平臺加速運行，為進行多蛋白質序列數據序列比並行比對，對蛋白質序列數據文本進行分割，並利用消息傳遞機制負載均衡地發送至MIC集群進行算法加速，並將加速運行完後的結果進行分析綜合，以下是實施的具體步驟。第一步：初始化各參數，包括查詢長度、打分矩陣、閾值T、比對序列資料庫、迭代次數、顯著性分析的期望值、比對長度等，由於對其中的序列比對模塊PSIBLAST採用並行算法，因此還需要設置線程數。第二步：由於需要對多序列蛋白質數據進行SIFT算法的流程，因此首先要對蛋白質多序列數據按照生物信息學的標準進行分割處理。第三步：利用MPI消息傳遞機制進行多條蛋白質數據序列的分發，分發至MIC集群進行加速運算。MPI偽碼如下:MPI_init{MPI_COMM_SIZE(n);MPI_COMM_RANK(CurRank);if(CurRank=0)//主節點,初始化查詢序列和分發計算任務{MPI_Scatterv(sequence[]);……MPI_Gatherv(result[]);}else//CurRank不是0,是從節點,接收主節點任務，進行序列數據比對{PSIBLAST……}MPl_finalize;}第四步：比對結果輸出對齊統計、根據種子中位選擇蛋白質序列、序列排序、生成預測信息、數據合併處理。由於SIFT算法其他步驟如耗時較短，流程簡單，在CPU段利用CPU的高頻率即可快速運行處理。上述雖然結合附圖對本發明的具體實施方式進行了描述，但並非對本發明保護範圍的限制，所屬領域技術人員應該明白，在本發明的技術方案的基礎上，本領域技術人員不需要付出創造性勞動即可做出的各種修改或變形仍在本發明的保護範圍以內。當前第1頁1&nbsp2&nbsp3&nbsp當前第1頁1&nbsp2&nbsp3&nbsp