摘　要： 介紹了一種基于PCI總線和多片并行FPGA的高速計算平臺,。FPGA+PCI板卡利用普通PC機作為CPU,，通過PCI總線互聯(lián)，實現(xiàn)了一個并行高速的通用數(shù)字運算平臺,。利用VHDL語言編寫各種算法,，可用于加解密算法實現(xiàn)和高速數(shù)字信號處理等領(lǐng)域，而速度相當于數(shù)臺PC機并行運算,。
　　關(guān)鍵詞： 并行計算 現(xiàn)場可編程門陣列 MD5

　　當前對于各種加密算法,，除了有針對性的破解算法,，最基本的思想就是窮舉密鑰進行匹配，通常稱為暴力破解算法,。由于暴力破解算法包含密鑰個數(shù)較多,，遍歷的時間超過實際可接受的范圍。如果計算速度提高到足夠快,，這種遍歷的算法因結(jié)構(gòu)設(shè)計簡便而具有實際應用的前景,。
　　PCI 總線(外設(shè)互聯(lián)總線)與傳統(tǒng)的總線標準——ISA總線(工業(yè)標準結(jié)構(gòu)總線)相比, 具有更高的傳輸率(132MBps)、支持32位處理器及DMA和即插即用等優(yōu)點,用于取代ISA總線而成為目前臺式計算機的事實I/O總線標準,，在普通PC機和工控機上有著廣泛的應用,。PCI總線為滿足在插卡和系統(tǒng)存儲器中高速傳輸數(shù)據(jù)的要求提供了很好的途徑。
　　PCI總線是一種獨立于處理器的局部總線,，因此通過PCI總線插入擴展板,，利用并提升普通PC機和工控機對大規(guī)模數(shù)字信號處理的運算能力和速度是一項非常具有實用意義的工作。
　　隨著數(shù)字技術(shù)日益廣泛的應用,，以現(xiàn)場可編程門陣列(FPGA)為代表的ASIC器件得到了迅速普及和發(fā)展,，器件集成度和速度都在高速增長。FPGA既具有門陣列的高邏輯密度和高可靠性,，又具有可編程邏輯器件的用戶可編程特性,，可以減少系統(tǒng)設(shè)計和維護的風險，降低產(chǎn)品成本,，縮短設(shè)計周期,。FPGA與通用CPU相比又具有如下顯著優(yōu)點：
　　(1) FPGA一般均帶有多個加法器和移位器，特別適合多步驟算法中相同運算的并行處理,。通用CPU只能提供有限的多級流水線作業(yè),。
　　(2) 一塊FPGA中可以集成數(shù)個算法并行運算。通用CPU一般只能對一個算法串行處理,。
　　(3) 基于FPGA設(shè)計的板卡功耗小,、體積小、成本低,，特別適合板卡間的并聯(lián),。
　　本文介紹的基于PCI總線的FPGA計算平臺的系統(tǒng)實現(xiàn)：通過在PC機上插入擴展PCI卡，對算法進行針對并行運算的設(shè)計,，提升普通PC機對大計算量數(shù)字信號的處理速度,。本設(shè)計采用5片F(xiàn)PGA 芯片及相關(guān)周邊芯片設(shè)計實現(xiàn)這一并行高速計算平臺，并在該平臺上完成了DES和MD5等算法的加密和解密,。文中通過基于MD5算法設(shè)計的加密方案(仿Yahoo郵箱的密碼校驗)進行暴力破解,，驗證了本系統(tǒng)的可行性以及速度快、性價比高等顯著優(yōu)點,。
1 系統(tǒng)結(jié)構(gòu)
　　系統(tǒng)利用普通PC機或工控機進行控制,、數(shù)據(jù)流下載和結(jié)果采集,，大計算量的數(shù)字運算利用IP-CORE技術(shù)并行地在FPGA中進行,。將數(shù)字信號處理的算法設(shè)計為一個單元模塊,，并根據(jù)芯片的結(jié)構(gòu)對布局和布線進行優(yōu)化，該單元模塊重復利用的技術(shù)被稱為IP-CORE技術(shù),。在本系統(tǒng)中利用IP-CORE的可重復利用性,，通過仲裁邏輯調(diào)度數(shù)據(jù)的分配，從而實現(xiàn)算法的并行處理,。
1.1 硬件結(jié)構(gòu)
　　系統(tǒng)中采用5片ALTERA公司的STRATIX EP1S10 FPGA 芯片,，其中4片作為數(shù)字信號處理算法CORE的載體(文中稱為算法FPGA)；1片作為連接PC機與運算CORE的橋接芯片,、加載程序,、并行總線裁決和中斷判決等仲裁邏輯的載體。與PCI總線的接口使用PLX公司的 PCI9054芯片,。系統(tǒng)硬件結(jié)構(gòu)如圖1所示,。

1.2 邏輯結(jié)構(gòu)
　　BRIDGE FPGA的程序采用自頂向下的設(shè)計方法，其邏輯結(jié)構(gòu)如圖2所示,，按功能可分為以下部分：頂層模塊 PCI_FPGA_PARALLEL,；與PCI9054的接口模塊PCI接口；數(shù)據(jù)緩存及仲裁部分：數(shù)據(jù)緩存模塊 FIFO,、寄存器模塊 regpart,、數(shù)據(jù)回傳模塊deserial、內(nèi)部總線仲裁和流控模塊 CORE接口等,。

　　PCI接口部分實現(xiàn)與PCI9054 芯片的接口時序,，使得復用的地址和數(shù)據(jù)分開，產(chǎn)生地址空間的選取及使能信號,，便于后端處理,。
　　仲裁邏輯部分：
　　(1)實現(xiàn)對地址空間內(nèi)數(shù)據(jù)緩沖區(qū)、各種寄存器的讀寫,，以及根據(jù)配置寄存器的內(nèi)容對算法CORE和橋FPGA做相應的操作(配置,、啟動、停止,、復位等),。
　　(2)利用緩沖區(qū)及FIFO的隊列長度信號wrusedw、rdusedw,、
　　full和empty進行數(shù)據(jù)流控制,。數(shù)據(jù)由PC機下載時首先進入緩沖區(qū)，每一塊算法CORE均對應一個數(shù)據(jù)下行FIFO,，由FIFO當前狀態(tài)來判定是否從緩沖區(qū)中取數(shù),。具體邏輯模型如圖3所示,。

　　(3)返回結(jié)果引入本地中斷機制，當有正確結(jié)果產(chǎn)生,、或無正確結(jié)果但密鑰匹配完成,、或系統(tǒng)異常狀態(tài)，均產(chǎn)生中斷信號并填寫中斷類型寄存器,，經(jīng)級聯(lián)后產(chǎn)生向PC機的中斷,。中斷判決如圖4所示。
　　(4)實現(xiàn)與算法core間的協(xié)議邏輯,，控制多種數(shù)據(jù)流的下行以及結(jié)果的返回,。

2 MD5算法簡介
　　MD5(Message Digest 5)報文摘要算法是一種應用廣泛的提取數(shù)字指紋的算法標準，它由MIT的密碼學專家,、RSA算法的發(fā)明人之一Rivest設(shè)計發(fā)明,。MD5算法結(jié)構(gòu)如圖5所示。
　　對任意長度的信息輸入,，MD5都將產(chǎn)生一個長度為128bit的輸出,，這一輸出可以被看作是原輸入報文的“報文摘要值(Message Digest)”。
　　MD5的特點：
　　(1)兩條不同的報文具有相同的報文摘要值的可能 性極小,。
　　(2)對于預先給定的報文摘要值,，要想尋找到一條報文，使得其報文摘要值與某個給定的報文摘要值相等,，在計算上是不可能的,。
　　(3)根據(jù)報文的摘要值，要
　　想推測出原來的報文是極端困難的,。
　　MD5算法被廣泛地應用于網(wǎng)絡(luò)數(shù)據(jù)完整性檢查以及各種數(shù)據(jù)加密技術(shù)中,。Yahoo郵箱密碼算法是基于兩次MD5算法。共算法步驟如下：
　　step1: 對一個密碼字段(例如:'dfertgrhyt'),用MD5算法加密：h=md5('dfertgrhyt'),。
　　step2: 將step1所得結(jié)果轉(zhuǎn)換為32Bytes的hex值：hex(h),。
　　step3: 將step2所得結(jié)果與一個yahoo提供的chanllenge值簡單級聯(lián)：string=hex(h)+chanllenge
　　step4:將step3所得結(jié)果再進行一次MD5運算：hash=md5(string)。
　　由于未得到實際Yahoo郵箱密碼生成參數(shù)(例如challenge碼),，本文構(gòu)造了相近算法以測試本系統(tǒng)性能,。測試方案如下：
　　提供一個已知的challenge值與相應的Hash值，從提供的字典中提取合適密碼,，由生成算法計算出對應的Hash值與提供的Hash值匹配來校驗匹配的密碼,。密鑰字典的產(chǎn)生有兩種方式：人為構(gòu)造字典及系統(tǒng)自加、窮舉產(chǎn)生密鑰,。
3 實測性能分析
　　實際系統(tǒng)中算法CORE運算時鐘為20MHz,，64bit數(shù)據(jù)寬度輸入；采用多級流水線設(shè)計及運算速度就是系統(tǒng)運行時鐘的速度,。除運算初期流水線建立過程和運算結(jié)束時流水線完成過程,，運算速度均可視為20MHz,；實際制成的系統(tǒng)為四片算法FPGA并行運算，實際吞吐量為4×20M×16bit=1.28Gb,；經(jīng)Altera Quartus 4.1 綜合,，實際仲裁邏輯占用3 725個邏輯單元。綜合頻率最高為156.2MHz,，單算法邏輯占用7 718個邏輯單元,，綜合頻率最高為37.10MHz。
　　典型的普通PC機定點運算需要多個指令周期,，包括取指令、取數(shù)據(jù),、計算,、保存數(shù)據(jù)等指令周期，而一個x86指令周期又由多個CPU時鐘周期組成,，大大降低了實際運算速度,。由于單個CORE以20MHz時鐘流水線運算，相當于一臺普通PC機的運算速度,，因此多個CORE并行運算即可達到多臺PC機并行運算的效率,。
　　采取密鑰字典自FPGA窮舉產(chǎn)生方式，可發(fā)揮算法CORE的最大效能,。若采取密鑰字典自PC機下載方式,，則實際速率由PCI總線最高速率決定。但由于字典可以人為選取,，大大降低了密鑰選取的盲目性,。本系統(tǒng)接入普通PC機上32bit、32MHz的PCI總線,，單算法CORE連續(xù)運算(64bit×20MHz)即可滿足PCI總線全速下載,。若使用64bit、66MHz的PCI總線或 PCI EXPRESS,，將進一步提高系統(tǒng)的實際吞吐量,。
　　本文提出了一種基于FPGA的適合大規(guī)模數(shù)字信號處理的并行處理結(jié)構(gòu)，利用CORE的可置換性,，可以針對不同應用的數(shù)字運算設(shè)計不同的CORE,，系統(tǒng)通用性的特點非常顯著。一臺普通PC機中可以同時插入數(shù)塊PCI卡,，每塊卡上的任意一塊算法FPGA都可提供相當或超過一臺普通PC機的運算速度,。而每增加一塊算法FPGA，在效率提高一倍的前提下,，功耗增加不超過10W,，而體積幾乎不變,，成本也只是比普通PC機增加了五分之一。因此,，本文提出的并行結(jié)構(gòu)具有極高的性價比,。
　　如果將PCI總線接口模塊集成到FPGA中以取代PCI9054芯片，將進一步降低硬件成本,，減少硬件設(shè)計的復雜度,；因?qū)嶋H運算速度與算法的并行度和優(yōu)化有密切的關(guān)系，因此,，設(shè)計不同應用的CORE以及相關(guān)算法的優(yōu)化是下一步要進行的重要工作,。
參考文獻
1 Rivest R L. The MD5 message-digest algorithm. RFC 1321,MIT Laboratory for Computer Science and RSA Data Security,Inc.,April 1992
2 Jarvinen K, Tommiska M, Skytta J. Hardware implementation analysis of the MD5 hash algorithm. System Sciences, 2005. HICSS ′05. Proceedings of the 38th Annual Hawaii International Conference on 03-06 Jan. 2005:298
3 Shanley T. Anderson D. PCI系統(tǒng)結(jié)構(gòu).北京：電子工業(yè)出版社, 2000
4 侯伯亨，顧 新. VHDL硬件描述語言與數(shù)字邏輯電路設(shè)計.西安：西安電子科技大學出版社, 1999