1、生物信息處理專用計算機研究與開發(fā)（曙光（曙光4000H）驗收報告）驗收報告徐志偉中國科學院計算技術(shù)研究所中國科學院北京基因組研究所l 課題研究背景課題研究背景l(fā) 課題執(zhí)行情況評價課題執(zhí)行情況評價 l 取得的成果的水平和作用取得的成果的水平和作用l 研究隊伍的建設(shè)和人才培養(yǎng)研究隊伍的建設(shè)和人才培養(yǎng) l 組織管理工作組織管理工作l 下一步工作設(shè)想下一步工作設(shè)想 主要內(nèi)容主要內(nèi)容研究背景研究背景l(fā) 人類基因組計劃引爆生物信息的大發(fā)展l 計算成為了生物學家的重要研究工具 蛋白質(zhì)結(jié)構(gòu)的預測 序列聯(lián)配和序列拼接 l 用于生物信息學的計算計系統(tǒng)不斷升級 普通的臺式機 工作站、服務(wù)器 高性能的對稱多處理器系統(tǒng)

2、 大規(guī)模并行計算機系統(tǒng)生物數(shù)據(jù)庫的增長趨勢及挑戰(zhàn)生物數(shù)據(jù)庫的增長趨勢及挑戰(zhàn) l 到2004年底GenBank中的DNA序列總量已超過445億堿基對 l 相對增長量和絕對增長量都很大摩爾定律l 龐大的基因數(shù)據(jù)庫為更加準確地進行生物信息的分析提供了可能l 算法的計算復雜度高l 對計算能力提出了挑戰(zhàn)解決方案之一：解決方案之一：研制更復雜的通用巨型計算機系統(tǒng)研制更復雜的通用巨型計算機系統(tǒng)BlueGene/L：l 65536顆700MHz主頻的PowerPC440l 360TFlopsl 未來的1年之內(nèi)規(guī)模再增加一倍 l 分子動力學通用系統(tǒng)的優(yōu)缺點通用系統(tǒng)的優(yōu)缺點l 利用通用型巨型機的優(yōu)點 計算機用途廣

3、泛 程序移植方便l 利用通用型巨型機的缺點 費用高l 通用型巨型機的價格非常昂貴l 維護費用高（電力、制冷、場地、管理等） 效率低 性能提高的速度難以跟上生物信息處理的需要 生物信息處理算法受計算機內(nèi)硬件資源制約生物信息學中算法的特點生物信息學中算法的特點 l 生物信息學中還有很多算法（如各種基因組研究的算法）具有數(shù)據(jù)量較大、算法相對簡單、并行度較高、運算類型單一、重復性較強的特點，許多計算過程都可以歸類于字符串的查找和比對等簡單操作。通常對字符進行操作只需要816位數(shù)據(jù)寬度，計算類型多為各種簡單的邏輯運算和算術(shù)運算，無需浮點計算，但需要進行大量的判斷和轉(zhuǎn)移。l 目前通用處理器的設(shè)計通常都采用

4、32位或64位字長，集成有數(shù)個復雜的浮點計算單元，為了提高指令級并行一般都采用超標量技術(shù)，而為了提高系統(tǒng)的工作頻率，幾乎所有的通用處理器都采用了深度流水線技術(shù)。這些特點使得通用處理器在進行字符串操作時往往是英雄無用武之地，有些技術(shù)如深度流水線甚至會對計算帶來負面影響，因為一旦發(fā)生轉(zhuǎn)移預測失敗，就需要清空流水線，因而會浪費很多時鐘周期。因此，用現(xiàn)有的大規(guī)模并行機或超級服務(wù)器等通用系統(tǒng)解決這些問題，既浪費系統(tǒng)的資源，使用維護也比較復雜，有些問題甚至無法在限定的時間內(nèi)完成。解決方案之二：解決方案之二：研制專用的計算機系統(tǒng)研制專用的計算機系統(tǒng)TimeLogic：l All bacterial prot

5、eins (4,242 proteins sequences) were compared against 192 E. coli genomes (775 million symbols in 6- frames). l DeCypherBLAST systems with 1 and 2 Engines complete the seach in 32 and 16 minutes respectively. l The DeCypher systems were installed in a 2 CPU Dell server. l An 8-CPU cluster requires o

6、ver 1 week to complete the task (216 hrs). l Results: For this search, DeCypher delivers the performance of 400-800 CPUs. 專用計算機系統(tǒng)的優(yōu)缺點專用計算機系統(tǒng)的優(yōu)缺點l 利用專用硬件加速方案的優(yōu)點 計算速度快、計算效率高 使用費用低l機器成本l維護費用低廉（功耗低、體積?。﹍ 利用專用硬件加速方案的缺點 程序移植困難l 可重構(gòu)計算將方便算法的硬件實現(xiàn)過程幾種算法的計算速度和數(shù)據(jù)質(zhì)量比較幾種算法的計算速度和數(shù)據(jù)質(zhì)量比較 序列聯(lián)配算法的加速方法序列聯(lián)配算法的加速方法l 啟發(fā)式算

7、法 FASTA BLAST 這兩種方法會損失敏感度l 并行計算方法 把數(shù)據(jù)庫分布在多個節(jié)點 使用MPI通訊l 硬件加速計算方法硬件加速的典型工作硬件加速的典型工作 l R. J. Lipton和D. P. Lopresti在1985年觀察到并指出，可以利用動態(tài)規(guī)劃算法中隱含的并行性將其映射到一個脈動陣列結(jié)構(gòu)中，并且可以通過恰當?shù)卦O(shè)置編輯操作的分值以有效地簡化每個PE的設(shè)計。l 在此基礎(chǔ)上，他們于1987年實現(xiàn)了P-NAC（Princeton Nucleic Acid Comparator）系統(tǒng)l 91年加州理工的BISP(Biological Information Signal Proces

8、sor)l 9193年布朗大學的B-SYS(Brown Systolic Array)和Splash l 9799年UCSC（Univ. of Cal. at Santa Cruz）開發(fā)了Kestrel l 96年法國IRISA在BISP基礎(chǔ)上改進實現(xiàn)了SAMBAl TimeLogic公司DeCypher系列產(chǎn)品l Paracel公司的GeneMacherII、BlastMachine （Closed）l 2002年Xilinx JBits Smith-Watermanl 2003年香港中文大學Pilchard序列聯(lián)配算法的加速方法總結(jié)序列聯(lián)配算法的加速方法總結(jié)l 除了啟發(fā)式算法，主要還有以下

9、一些方法用于對各種序列聯(lián)配算法進行加速： l 采用超級計算機進行并行計算：最具彈性，如加速比相對較小、性價比較低、使用維護比較復雜等。l 采用專用的的VLSI：對某個算法性能最高，典型的系統(tǒng)如P-NAC、BioScan、BISP、SAMBA等，但研制費用高、周期長、靈活性較差。l 采用可編程的處理器陣列：這種做法希望能夠兼顧靈活性、專用性和加速性，典型的系統(tǒng)有B-SYS、Kestrel等，但對控制的要求較高，雖然可編程，但由于運算精度、運算類型、運算速度等多方面的因素使這種系統(tǒng)并沒有得到大規(guī)模的應(yīng)用。l 采用可重構(gòu)硬件：設(shè)計修改相對比較方便，例如早期的Splash和Splash-2，近期的Pi

10、lchard、以及Decypher等系統(tǒng)。尤其是在近年來，隨著微電子技術(shù)的進步，這種方法的優(yōu)點日見突出傳統(tǒng)加速方法的局限性傳統(tǒng)加速方法的局限性l 大部分的工作都集中于如何實現(xiàn)更多的計算單元以及如何提高峰值的處理速度等方面l 許多設(shè)計因為結(jié)構(gòu)的問題限制序列的長度不能超過陣列的長度l 許多設(shè)計要求主機系統(tǒng)保證序列能夠及時地進入脈動陣列，對主機操作系統(tǒng)的實時性也提出了較高的要求。l 大部分加速卡和主機系統(tǒng)的總線接口帶寬相對較低，這也影響了他們在其他類型的算法中的應(yīng)用 這些問題影響了加速卡在實際系統(tǒng)中的應(yīng)用華大基因中心和計算所的合作華大基因中心和計算所的合作 l 計算所研制的曙光2000和曙光3000

11、系統(tǒng)安裝在華大中心l 華大利用曙光3000系統(tǒng)上完成了水稻基因組框架圖繪制工作，這一工作以封面文章的形式發(fā)表在2002年4月的Science雜志上l 近期華大正在進行超級雜交水稻基因組分析等工作 l 在進一步的工作中，我們發(fā)現(xiàn)現(xiàn)有的高性能計算能力仍然不能滿足高速增長的需求： 水稻基因組完全圖的繪制工作，需要對1000萬個短片段進行拼接，如果使用現(xiàn)有的拼接算法，如Phrap、CAP3、GAP4，無論是內(nèi)存還是計算速度都無法滿足需求； 序列比對：現(xiàn)在的Blast只適合于長度為幾兆的片段之間的比對，而且該算法的敏感度不夠好，而現(xiàn)在感興趣的是對兩個長達數(shù)百兆的基因組之間的比對，這已遠遠超出了現(xiàn)有的計算

12、能力。課題執(zhí)行情況評價本課題總體目標要求： l 最終目標：研制一套生物信息學專用系統(tǒng)，以相對較低的硬件成本達到4萬億次系統(tǒng)的處理能力，以實現(xiàn)專用、高效、經(jīng)濟的目的。l 面向生物信息處理 處理基因數(shù)據(jù)、功能基因組分析、蛋白功能分析 研究基因聯(lián)配、蛋白質(zhì)折疊等算法的硬件實現(xiàn)技術(shù) 從算法、體系結(jié)構(gòu)、芯片設(shè)計、存儲系統(tǒng)設(shè)計、快速數(shù)據(jù)傳遞等幾方面，研究專用數(shù)據(jù)處理硬件系統(tǒng)的設(shè)計技術(shù)l 2-3項發(fā)明專利l 10篇左右有影響的高質(zhì)量學術(shù)論文課題組完成如下工作：l 生物專用機（曙光4000H一臺）；l 申請發(fā)明專利3項，軟件登記1項。達到課題任務(wù)書規(guī)定的23項專利技術(shù)；l 發(fā)表SCI、EI收錄學術(shù)論文11篇。

13、完成了課題任務(wù)書規(guī)定的高質(zhì)量學術(shù)論文10篇要求。l 開展應(yīng)用試算，完成基因組水平的水稻雜交優(yōu)勢研究；完成黑猩猩人類基因組比較計算；完成mRNA預測計算。相關(guān)研究成果將在Science等刊物上發(fā)表。取得的成果的水平和作用取得的主要成果 (1)l 研制曙光研制曙光4000H生物信息處理專用計算機生物信息處理專用計算機 采用“通用體系結(jié)構(gòu)+專用硬件加速部件”相結(jié)合的方法來實現(xiàn)的技術(shù)方案 從算法、體系結(jié)構(gòu)、芯片設(shè)計、存儲系統(tǒng)設(shè)計、快速數(shù)據(jù)傳遞等幾方面研究關(guān)鍵技術(shù)，充分利用現(xiàn)有的曙光超級服務(wù)器成熟的Cluster技術(shù) 采用高密度化、微型化的技術(shù)路線，解決了數(shù)據(jù)密集型問題 開展了動態(tài)規(guī)劃算法細粒度并行計算

14、研究，使之適合硬件的大規(guī)模并行處理，并成功研制專用硬件加速部件4000H網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖 計算 節(jié)點 機箱 (包含 8 片 刀片) 計算 節(jié)點 機箱 (包含 8 片 刀片) 計算 節(jié)點 機箱 (包含 8 片 刀片) 計算 節(jié)點 機箱 (包含 8 片 刀片) 服務(wù)節(jié)點 雙 XEON 8GB RAM 438GB HD 雙千兆互聯(lián) 計算 節(jié)點 機箱 (包含 8 片 刀片) 2 套 5 個千兆交換機 萬兆級連堆疊 服務(wù)節(jié)點 雙 XEON 8GB RAM 438GB HD 服務(wù)節(jié)點 雙 XEON 8GB RAM 438GB HD 服務(wù)節(jié)點 雙 XEON 8GB RAM 438GB HD 服務(wù)

15、節(jié)點 雙 XEON 8GB RAM 438GB HD 雙千兆互聯(lián) 控制臺 生物專用機的通用體系結(jié)構(gòu)生物專用機的通用體系結(jié)構(gòu) l該系統(tǒng)具有通用的Cluster結(jié)構(gòu)l5個服務(wù)節(jié)點l40個計算節(jié)點組成，l節(jié)點類型：雙Xeon SMP系統(tǒng)l節(jié)點數(shù)量：45個lCPU數(shù)量：90個l系統(tǒng)總內(nèi)存容量：130GBl系統(tǒng)總存儲容量：2TBl系統(tǒng)互連網(wǎng)絡(luò)：雙千兆以太網(wǎng)l通用部分峰值浮點計算能力：5040億次取得的主要成果 (2)基于FPGA的算法可重構(gòu)硬件加速卡基于基于FPGA的算法可重構(gòu)加速卡的算法可重構(gòu)加速卡l FPGA容量已高達數(shù)百萬門，管腳1000條，頻率可高達100200MHzl 可以將成百上千個比較簡單

16、的PE設(shè)計到一片F(xiàn)PGA中，這些PE可以構(gòu)成一維或二維的脈動陣列，以脈動的方式工作。l 由于每個PE在一個時鐘周期內(nèi)能夠完成的工作往往相當于幾十條通用CPU的指令，因此其主頻通常只有100MHz左右，但相對于通用CPU仍能得到上百倍甚至數(shù)千倍的加速比。l FPGA與ASIC相比有很多優(yōu)點： FPGA是可重構(gòu)的，也就是說當算法發(fā)生變化時，可以非常方便地對其邏輯進行重新構(gòu)造，重構(gòu)一次只有幾十ms； FPGA的開發(fā)周期相對比較短，沒有ASIC設(shè)計過程中的版圖設(shè)計等非常耗時的后端設(shè)計過程。序列聯(lián)配問題的定義與分類序列聯(lián)配問題的定義與分類l 序列的聯(lián)配(Alignment）定義如下：將兩個或多個符號序列

17、按字母比較，并盡可能確切地反映它們之間的相似或相異，這一過程稱為序列的聯(lián)配。l 主要的生物序列的分析和計算任務(wù)： 序列相似性的比較 多序列的聯(lián)配 兩條序列聯(lián)配的主要問題兩條序列聯(lián)配的主要問題l 全局聯(lián)配（Global Alignment）：輸入兩個具有相同長度的序列S和T，輸出兩個序列之間的最大相似度差異并找出最佳的排列。l 局部聯(lián)配（Local Alignment）：輸入兩個序列S和T，兩者的長度可能不同，輸出S的一個子序列和T的一個子序列的最大相似度（最小差異），并找出具有最大相似度的兩個子序列編輯距離及加速思想l 編輯距離能夠在很大程度上測量出兩條序列的相似性 l 需要使用動態(tài)規(guī)劃算法對

18、矩陣相似度進行計算，但并不需要輸出矩陣的每個點的分值，只需要最終的矩陣的右下角的分值，這個值也就表示了這兩條序列之間的編輯距離 l 編輯距離的計算過程和全局聯(lián)配Smith-Waterman算法的計算過程是等價的，主要區(qū)別 編輯距離的計算是一個求最小值的過程， 全局聯(lián)配S-W算法是一個求最大值的過程。l 硬件加速的技術(shù)思想： 利用加速卡對數(shù)據(jù)庫中的序列進行快速的過濾或篩選， 再用主機對少數(shù)篩選出來的結(jié)果進行更進一步的分析，包括完整得分矩陣的計算和路徑的回溯等 編輯距離的計算方法l 前提條件為：(0,0)0;( ,0)(1,0)( , ),1;(0, )(0,1)( , ),1;VV iV iS

19、iinVjVjT jjm l 遞推關(guān)系為：11( , )min11,11V(i, j)(Si,Tj);V i jV(i, j) (Si, );injmV(j,i)( ,Tj); 算法到邏輯的簡單映射的問題l 每個PE中將有5個加法器、6個比較器、1個二選一以及多級組合邏輯電路，l PE的數(shù)據(jù)寬度也將隨著PE的個數(shù)而增加，例如，當N512時，PE的數(shù)據(jù)寬度至少應(yīng)該等于10l 每個PE至少將消耗約120個LEl 如果采用Altera Stratix系列的EP1S30 FPGA，只能實現(xiàn)約256個PE。l 這樣的設(shè)計方法將很難提高PE的工作頻率，其工作頻率通常只能達到5060MHz。l 因此，必須研

20、究高效的算法硬件實現(xiàn)方法編輯距離算法處理單元PE編輯距離算法脈動陣列編輯距離算法核心邏輯電路編輯距離算法核心邏輯電路 Matrix-PCI型加速卡型加速卡Matrix-PCI型加速卡型加速卡編輯距離算法在加速卡的性能測試編輯距離算法在加速卡的性能測試編輯距離算法編輯距離算法在加速卡上的測試結(jié)果分析在加速卡上的測試結(jié)果分析 l Xeon 2.8GHz CPU進行得分矩陣的計算時，每完成1個分值的計算需要約45個匯編指令，同時可以統(tǒng)計出該CPU的平均CPI0.6，所以每個循環(huán)將消耗約27個CPU周期，則該CPU的計算能力折合為103.7MCUPS。l 而加速卡的每個PE完成該計算過程則只需要1個周

21、期，工作在133.33MHz的3072個PE陣列的峰值計算能力為409.6GCUPS，所以理論上的加速比最高可以達到3950倍。l 實際測試最高加速比3800倍 ClustalW多序列聯(lián)配算法多序列聯(lián)配算法lClustalW是目前使用最廣泛的多序列聯(lián)配程序。它是一種漸進的聯(lián)配方法，計算過程主要包括以下三個步驟：1. 使用動態(tài)規(guī)劃算法計算所有兩兩序列最優(yōu)聯(lián)配的分值，基于最優(yōu)聯(lián)配得到序列的兩兩之間的相似度，根據(jù)相似度再進一步構(gòu)造距離矩陣。2. 從距離矩陣出發(fā)，采用NJ計算產(chǎn)生系統(tǒng)進化指導樹（Guide Tree），對關(guān)系密切的序列進行加權(quán)。3. 從引導樹的葉節(jié)點出發(fā)，遍歷整個樹直到根節(jié)點，逐步得到

22、最終的多序列聯(lián)配結(jié)果。l該程序的第一個步驟需要對所有的序列進行兩兩聯(lián)配，如果序列的數(shù)量為n，序列的長度為l，則這一步過程的計算時間復雜度為O(n2l2)，這也是整個程序中最耗時的部分，為加速計算提供了可能。 多序列聯(lián)配整體加速比多序列聯(lián)配整體加速比測試測試 多序列聯(lián)配程序串行部分比例多序列聯(lián)配程序串行部分比例 多序列聯(lián)配整體加速比多序列聯(lián)配整體加速比測試結(jié)論測試結(jié)論l 從圖中可以看出，在一定范圍內(nèi)，多序列聯(lián)配整體加速比與序列數(shù)量基本上成正比關(guān)系，即序列的數(shù)量越多，整體上得到的加速比越大。l 加速比的增長應(yīng)該有一個極限，但由于多序列聯(lián)配的時間非常之長，我們在測試過程中沒有測到增長曲線的拐點。l

23、實際上，序列的數(shù)量越多，ClustalW中的串行部分即不可加速部分所占的百分比越低，隨著序列數(shù)量的增長，程序中串行部分的比例迅速降低，但隨著序列數(shù)量的進一步增長，程序中串行部分的比例逐步趨于極限，這也暗示了加速比的增長也將趨于極限。 局部最優(yōu)序列聯(lián)配局部最優(yōu)序列聯(lián)配l 局部聯(lián)配在某些生物信息學中的應(yīng)用可能要比全局聯(lián)配更有實際的意義。在蛋白質(zhì)序列的比較中，由于親緣關(guān)系較遠的蛋白質(zhì)序列可能只有一些相互獨立的相同片段，所以對其進行局部相似性分析更為重要也更為合理。l 另一方面，前面介紹的編輯距離算法中較少地考慮到序列的生物學意義，但實際上，在生物序列聯(lián)配過程中，某些字符的匹配可能比另外一些字符的匹配

24、更為重要，而不是僅僅考慮兩個字符是否相同。因此，生物學家在統(tǒng)計分析的基礎(chǔ)上建立了一套專門的替換矩陣(substitution matrices)用于聯(lián)配的計算序列局部聯(lián)配算法PE設(shè)計l 數(shù)據(jù)寬度為20位 l 序列的長度為32Kl 由硬件邏輯控制加減法器的下溢問題 l Max電路由比較器和二選一電路兩級電路來實現(xiàn) l 關(guān)鍵路徑：從F-in、E-out和H-out到H-out上包括了1級減法器、1級寄存器、3級比較器和3級二選一，共計8級電路，這條關(guān)鍵路徑的延遲依賴于FPGA器件的特性 局部聯(lián)配算法局部聯(lián)配算法PE在在FPGA中的實現(xiàn)中的實現(xiàn) l LUT部分用于實現(xiàn)(Si,Ti)功能項，即查找替換

25、矩陣。 這個模塊共有10位輸入和4位輸出，如果使用普通的組合邏輯來實現(xiàn)需要消耗很多邏輯資源。 用RAM來實現(xiàn)該LUT：10位輸入和4位輸出的LUT可以等價于一個有10位地址線的4位寬度的ROM，該ROM可以使用Altera FPGA中的M4K RAM配置來實現(xiàn)，ROM中的數(shù)據(jù)可在FPGA上電時有Flash加載進去。 使用ROM來替代LUT，不僅節(jié)省了FPGA中的邏輯資源，而且對該ROM的訪問可以在1個周期內(nèi)完成，也能夠提高系統(tǒng)的工作速度。 l PE中的其它邏輯，將消耗約270個LE，其中約有190個LE中使用了寄存器，其他LE則只使用了查找表。 l Stratix 1S30共有一共有32470

26、個LE，除了接口邏輯和其他控制邏輯，還可以實現(xiàn)約80個PE。 l 上述的關(guān)鍵路徑中的從輸入到加減法中間結(jié)果一級需要約5ns，剩下的路徑需要約13ns，通過優(yōu)化，PE陣列的最高工作頻率可以達到80MHz，其峰值計算能力為6.4GCUPS。 局部聯(lián)配算法在加速卡的性能測試局部聯(lián)配算法在加速卡的性能測試40kbp（4kbp、20kbp、40kbp、60kbp、80kbp）（時間單位，秒）序列長度PCI_LSWXeon2.8GHz加速比40.0279.170340.14 200.13245.679 347.45 400.12691.332 349.66 600.394137.861 349.48 80

27、0.525184.302 351.79 取得的主要成果 (3)l 提出了提出了STE-Blast核心算法及其并行算法核心算法及其并行算法 Blast是使用最廣泛的序列相似性搜索工具，采用啟發(fā)式算法，其計算復雜性從S-W算法的O(n2)降為O(n)；Mega-Blast優(yōu)化了NCBI-BLAST算法，對查詢序列進行批處理，同時在進行序列聯(lián)配過程中采用了貪婪算法，其速度又有了大幅提高。但由于引入了批處理，使得內(nèi)存消耗更大。 我們從體系結(jié)構(gòu)的觀點出發(fā)，結(jié)合系統(tǒng)軟件和操作系統(tǒng)的特點，提出了一種較好的可擴展的算法，通過對庫造表，并將計算和輸出重疊并行進行，隱藏I/O開銷，不改變處理精度，大幅降低了內(nèi)存開

28、銷，成倍提高了計算速度；完善了STE-BLAST并行版本研究。 STE-Blast與與MegaBlast運行時間測試對比運行時間測試對比 203010920411559001031802236962548595401M/1M10M/100K10M/1M1M/10M1M/100M10M/10M并行化的并行化的STE-Blast和和MegaBlast運行時間對比測試運行時間對比測試 取得的主要成果 (4)l RNA二級結(jié)構(gòu)的硬件實現(xiàn)探索研究二級結(jié)構(gòu)的硬件實現(xiàn)探索研究 RNA二級結(jié)構(gòu)預測采用Vienna Package的算法，需要完成邊長為N2的最小自由能三角矩陣的計算，而后可以尋找全局最小能量并進

29、行路徑回溯找到最佳折疊結(jié)構(gòu)。確定由硬件完成矩陣計算，回溯則由軟件完成。 PCI-X接口可以給系統(tǒng)提供一個高效的數(shù)據(jù)傳輸通道，由PCI接口主機可以和卡上DDR RAM進行數(shù)據(jù)交換，將經(jīng)過軟件預處理的矩陣下載到DDR RAM中，計算完成后矩陣數(shù)據(jù)通過PCI口輸入到主機中完成后續(xù)的路徑回溯等工作。 能量矩陣的計算大致可以劃分為VM項（計算多環(huán)結(jié)構(gòu)的能量）與VBI項的計算（計算內(nèi)環(huán)結(jié)構(gòu)的能量）。由于VM與VBI計算所需要的數(shù)據(jù)以及計算特點有很大的差別，因此在設(shè)計中決定采取不同的硬件來完成。VM項的計算量為1/6N3，計算涉及大量的數(shù)據(jù)IO，因此在設(shè)計中如何壓縮數(shù)據(jù)IO量是最為關(guān)鍵的問題。 由于其中數(shù)據(jù)

30、依賴過于復雜，導致邏輯控制十分復雜，有關(guān)研究工作仍在進行中。 取得的主要成果 (5)l 蛋白質(zhì)空間結(jié)構(gòu)特征是蛋白質(zhì)功能分析、蛋白質(zhì)相互作用、進化樹構(gòu)建和藥物設(shè)計等研究的基礎(chǔ)，我們綜合運用圖論、機器學習及數(shù)理統(tǒng)計方面理論，構(gòu)建蛋白結(jié)構(gòu)模板庫，并基于該模板庫，提出了一種新的同源建模預測算法，可以更精確地預測出更多的蛋白質(zhì)空間結(jié)構(gòu)。相關(guān)研究成果將在Genome Research上發(fā)表。 取得的主要成果 (6)l 系統(tǒng)生物學主要多個基因如何通過相互作用，共同完成復雜的生理功能的。我們發(fā)揮計算所在算法方面多年積累的優(yōu)勢，使用圖論、矩陣論等工具，和生物物理所、北京基因組研究所合作，在基因調(diào)控網(wǎng)絡(luò)分析方面，

31、提出了相互作用網(wǎng)絡(luò)的譜分析方法,相關(guān)文章已經(jīng)發(fā)表在NAR。取得的主要成果 (7)l 我們主要使用統(tǒng)計理論工具，和生物物理所、北京基因組研究所合作，在蛋白質(zhì)質(zhì)譜數(shù)據(jù)分析方面，提出了基于Extreme Value Distribution的區(qū)分match和mismatch方法?，F(xiàn)在正在和PG公司合作，研究洗衣粉中蛋白酶的鑒定。取得的主要成果 (8)l STE-BLAST應(yīng)用。以數(shù)據(jù)量達到440MB的雜交水稻PA64的原始Reads和已有的336MB水稻基因組的比較，從而加速了PA64的組裝工作。同時從比對的結(jié)果中發(fā)現(xiàn)了一些有差異性的區(qū)域，這些差異區(qū)域?qū)τ谘芯侩s交水稻的優(yōu)勢工作具有重要的意義。l I

32、CT-ClustalW應(yīng)用。該數(shù)據(jù)為1129 個基因家族，每個家族含有從哺乳類動物人、黑猩猩、小鼠、大鼠，到雞、果蠅，直到酵母、植物等多個物種，包含了目前已測序的真核生物范圍。這樣的計算對于揭示真核生物的進化關(guān)系具有重要的意義。l ICT-FindRNA應(yīng)用。開發(fā)用于從內(nèi)含子發(fā)現(xiàn)microRNA；并對80Mbp，共45萬條基因序列的內(nèi)含子中，尋找microRNA。miRNA參與著生物體中很多基本生命過程的調(diào)控，在生命活動中起著非常重要的作用。創(chuàng)新點、主要意義與影響在硬件加速方面的創(chuàng)新在硬件加速方面的創(chuàng)新l 成功研制了全局動態(tài)規(guī)劃加速卡PCI_GSW。包含3072個處理單元，主頻達到133.3M

33、Hz，一塊卡的性能就達到409.6GCUPS。和通用CPU（Xeon 2.8GHz）相比，對于全局動態(tài)規(guī)劃專用算法，性能加速3600倍以上。在此基礎(chǔ)上，進一步研制了局部動態(tài)規(guī)劃加速卡，包含80個處理單元，主頻達到80MHz，性能6.4GCUPS。l 在Blast內(nèi)核算法改進和并行化方面。我們從體系結(jié)構(gòu)的觀點出發(fā)，結(jié)合系統(tǒng)軟件和操作系統(tǒng)的特點，提出了一種較好的可擴展的算法，通過對庫造表，并將計算和輸出重疊并行進行，隱藏I/O開銷，不改變處理精度，大幅降低了內(nèi)存開銷，成倍提高了計算速度。目前該算法是所有的BLAST性能最優(yōu)的。在高性能計算方面的創(chuàng)新在高性能計算方面的創(chuàng)新l 在Blast內(nèi)核算法改進

34、和并行化方面。我們從體系結(jié)構(gòu)的觀點出發(fā)，結(jié)合系統(tǒng)軟件和操作系統(tǒng)的特點，提出了一種較好的可擴展的算法，通過對庫造表，并將計算和輸出重疊并行進行，隱藏I/O開銷，不改變處理精度，大幅降低了內(nèi)存開銷，成倍提高了計算速度。目前該算法是所有的BLAST性能最優(yōu)的算法方面的創(chuàng)新點算法方面的創(chuàng)新點l 提出了一種新的同源建模預測算法，可以更精確地預測出更多的蛋白質(zhì)空間結(jié)構(gòu)。l 在蛋白質(zhì)質(zhì)譜數(shù)據(jù)分析方面，提出了Extreme Value Distribution的區(qū)分match和mismatch方法。l 在基因調(diào)控網(wǎng)絡(luò)分析方面，提出了相互作用網(wǎng)絡(luò)的譜分析方法,相關(guān)文章已經(jīng)發(fā)表在NAR。社會和經(jīng)濟效益（1）l 曙

35、光4000H項目已經(jīng)通過有關(guān)部門的資產(chǎn)評估，其技術(shù)價值高達以2400萬元l 天津曙光計算機產(chǎn)業(yè)基地公司：天津曙光計算機產(chǎn)業(yè)基地公司：該項目注冊資金6,000萬元人民幣，中科院計算所投資2,400.00萬元（曙光4000H技術(shù)成果），天津新技術(shù)產(chǎn)業(yè)園區(qū)管理委員會投資1,200萬元，北京市曙光計算機公司投資2,400萬元。社會和經(jīng)濟效益（2）l促進了我國生命科學研究。為廣大基因組學、蛋白質(zhì)組學、醫(yī)藥科學、生物信息學等研究工作者提供一個先進、易用的科研工具，同時，增強我國在生物科學等基礎(chǔ)學科研究領(lǐng)域的實力，在基因組研究方面占據(jù)國際領(lǐng)先地位。l促進可重構(gòu)計算這一新學科的發(fā)展?？芍貥?gòu)計算近年來受到高度重

36、視，是高性能計算的重要分支。傳統(tǒng)的高性能計算在很多傳統(tǒng)行業(yè)，比如石油、氣象、天文等領(lǐng)域都發(fā)揮了重要作用，而面向生命科學提出的挑戰(zhàn)，可重構(gòu)計算也越來越顯示出其巨大的威力，同時也提出了很多新的課題。在本課題執(zhí)行過程中，課題組陸續(xù)獲得三項相關(guān)領(lǐng)域國家自然科學基金項目支持，可重構(gòu)計算學科成長起來。l促進我國在生物信息產(chǎn)業(yè)的發(fā)展。生物信息學產(chǎn)生的技術(shù)、應(yīng)用、算法、軟件和數(shù)據(jù)庫，比如疾病相關(guān)基因、分子標記輔助育種技術(shù)、藥物篩選技術(shù)等，都具有重要的經(jīng)濟價值，最終都將產(chǎn)品化，創(chuàng)造直接的經(jīng)濟效益。最終完成的生物信息處理專用計算機和軟件包將占領(lǐng)國內(nèi)市場，并力求在國際市場占有一席之地。l促進多領(lǐng)域的交流，培養(yǎng)一批跨領(lǐng)域的優(yōu)秀人才。生物信息學是一門新興的交叉學科，它位于信息學、物理學、數(shù)學和生物學的交叉點上，因此多領(lǐng)域的聯(lián)合和交流是促進這個領(lǐng)