一種基于分布式平臺(tái)的規(guī)則處理架構(gòu)*

陳孟東，原 昊，謝向輝，吳 東

(數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫 214125)

1 引言

隨著計(jì)算機(jī)技術(shù)的發(fā)展和互聯(lián)網(wǎng)規(guī)模的擴(kuò)大，互聯(lián)網(wǎng)安全問題也越來越受到公眾的關(guān)注，為確保私人、企業(yè)乃至國家的網(wǎng)絡(luò)安全，人們采取多種手段來保護(hù)自身的信息安全。其中很常用的方式就是對(duì)重要信息或系統(tǒng)進(jìn)行身份認(rèn)證，除軍事、金融等對(duì)安全性要求極高的領(lǐng)域之外，操作系統(tǒng)、數(shù)據(jù)庫、文件加密應(yīng)用、流行的網(wǎng)絡(luò)應(yīng)用(如電子郵件、即時(shí)通訊工具、論壇等)都依靠身份認(rèn)證機(jī)制進(jìn)行用戶賬戶或者使用權(quán)限的認(rèn)證[1]。廣泛使用的身份認(rèn)證機(jī)制需要一個(gè)用戶名和安全字符串組合的身份信息。通常使用單向哈希函數(shù)來計(jì)算摘要值，并將摘要值與用戶憑據(jù)一同存儲(chǔ)。當(dāng)用戶進(jìn)行身份驗(yàn)證時(shí)，其認(rèn)證系統(tǒng)通過接收用戶輸入的安全字符串，重新使用哈希函數(shù)把用戶名和安全字符串轉(zhuǎn)換成摘要值，并和系統(tǒng)存儲(chǔ)的摘要值進(jìn)行對(duì)比，以此完成認(rèn)證過程[2]。通常使用的哈希函數(shù)包括MD4、MD5和SHA1等。

身份認(rèn)證機(jī)制在提供安全保障的同時(shí)，也會(huì)帶來一些問題。過多或者過于復(fù)雜的安全字符串會(huì)給用戶帶來記憶負(fù)擔(dān)，一旦遺忘字符串，用戶將無法獲取權(quán)限或者無法訪問文檔，因而帶來不便和損失。同時(shí)，采用安全字符串認(rèn)證的系統(tǒng)和文檔也會(huì)對(duì)國家安全部門的取證工作造成阻力[3]。為滿足個(gè)人、企業(yè)和政府在這方面的需求，安全字符串的恢復(fù)技術(shù)應(yīng)運(yùn)而生。安全字符串的恢復(fù)通過在大量候選字符串上進(jìn)行哈希運(yùn)算并驗(yàn)證，從而找到丟失或遺忘的正確字符串，它已經(jīng)成為密碼學(xué)的重要研究方向之一[4]。安全字符串的恢復(fù)方法主要有暴力搜索法、字典法和時(shí)空折衷法等，其中字典法通過搜集已知的安全字符串可能的取值，形成一個(gè)字典文件，恢復(fù)時(shí)僅從這個(gè)字典文件中取值進(jìn)行正向的哈希運(yùn)算并和存儲(chǔ)摘要進(jìn)行比較，具有搜索空間小、命中率高的特點(diǎn)，是一種行之有效的方法。然而字典法也存在問題，其恢復(fù)的成功率與字典的質(zhì)量密切相關(guān)，如何提高字典的覆蓋空間、提升字典的質(zhì)量是一個(gè)重點(diǎn)[5]。

由于人的記憶力限制以及個(gè)人習(xí)慣等因素，人們?cè)谠O(shè)置安全字符串時(shí)常常是基于一個(gè)基礎(chǔ)加以簡(jiǎn)單變形形成新的字符串，如增加前綴、增加后綴、大小寫變換、修改部分字母等，每種變形稱為一個(gè)基本規(guī)則[6,7]。幾個(gè)基本規(guī)則可以組合在一起共同對(duì)字符串進(jìn)行處理，稱為一次變換。相反地，在字符串恢復(fù)過程中，將每一個(gè)字典條目按照一定的規(guī)則進(jìn)行變形變換，形成新的安全字符串，膨脹擴(kuò)大了原字典文件的規(guī)模和覆蓋率，是提升字典質(zhì)量的有效方法。基于規(guī)則變換的安全字符串恢復(fù)方式通過模擬人在設(shè)置安全字符串時(shí)的內(nèi)在規(guī)律，進(jìn)一步提升字典的質(zhì)量，巧妙設(shè)置的字典結(jié)合規(guī)則變換，可以在滿足搜索規(guī)模、時(shí)效等限制時(shí)，顯著提升恢復(fù)的命中率。同時(shí)，使用規(guī)則變換對(duì)字典進(jìn)行擴(kuò)充，在處理單元內(nèi)部進(jìn)行規(guī)則的處理以及新字符串的生成，還可以減少字典本身的存儲(chǔ)和傳輸需求，解決哈希計(jì)算模塊和字典存取模塊之間的速度差異問題，保證整體的恢復(fù)效率。這種恢復(fù)方式越來越受到重視，多個(gè)研究證明了采用規(guī)則變換的有效性[8 - 10]?；谝?guī)則變換的安全字符串恢復(fù)過程如圖1所示，圖中虛線框內(nèi)為規(guī)則的處理過程，新生成的字符串?dāng)?shù)量是原字典條目數(shù)與變換條目數(shù)的乘積。

Figure 1 Secure string recovery process based on rule transformation圖1 基于規(guī)則變換的安全字符串恢復(fù)過程

業(yè)界有許多總結(jié)積累而成的字符串變形規(guī)則，多個(gè)安全字符串恢復(fù)工具[6,7,11]都有自己支持的規(guī)則，并提供字典加規(guī)則的恢復(fù)模式。這其中，hashcat[6]應(yīng)用廣泛，是一款多平臺(tái)的免費(fèi)恢復(fù)套件，支持包括CPU、GPU(支持NVIDIA GPU和AMD GPU)、DSP、FPGA等包含OpenCL運(yùn)行時(shí)的各種平臺(tái)，支持Linux、Windows、MacOS多種操作系統(tǒng)，支持分布式處理，支持近200種算法，支持多種恢復(fù)模式，支持字典與規(guī)則的處理，其規(guī)則的處理過程主要在CPU和GPU上進(jìn)行。

hashcat所采用的規(guī)則具有代表性，其共支持基本規(guī)則41種，表1列出了幾種典型的基本規(guī)則，并以字符串p@ssW0rd為輸入，舉例說明了基本規(guī)則的變形結(jié)果。hashcat自帶301 472個(gè)條目的變換文件，每次變換由一到幾個(gè)基本規(guī)則組成。例如變換“{$0l”代表先循環(huán)左移，然后將字符“0”作為后綴，然后再全部變換為小寫字母，所有3個(gè)基本規(guī)則處理結(jié)束后才生成1個(gè)新的字符串。

Table 1 Examples of typical rules表1 典型規(guī)則示例

性能和功耗成本是規(guī)則處理乃至安全字符串恢復(fù)系統(tǒng)的重要考慮因素?；疽?guī)則包括幾十種，而且還有復(fù)雜的組合情況，實(shí)際使用中，在任務(wù)規(guī)模大的情況下，字典文件可能多達(dá)幾億個(gè)條目，變換文件可能包含幾十萬次變換，規(guī)則處理過程是一項(xiàng)計(jì)算量大、對(duì)處理時(shí)間要求很高的任務(wù)，到目前為止公開的實(shí)現(xiàn)方式中，不管是開源工具[6,7]還是學(xué)術(shù)研究[12 - 14]都是基于CPU和GPU進(jìn)行處理，在處理速度、系統(tǒng)功耗等方面有諸多不足。本文針對(duì)hashcat自帶的基本規(guī)則及其變換文件，基于現(xiàn)有工程中使用的安全字符串恢復(fù)系統(tǒng)，提出了一種適用于規(guī)則的分布式處理架構(gòu)。實(shí)驗(yàn)結(jié)果表明該處理架構(gòu)滿足實(shí)際工程需求，在處理性能、系統(tǒng)能效等方面表現(xiàn)良好。

2 分布式的規(guī)則處理架構(gòu)

2.1 分布式平臺(tái)介紹

本文的分布式規(guī)則處理架構(gòu)基于“蟻群”平臺(tái)實(shí)現(xiàn)，蟻群平臺(tái)是由眾多可重構(gòu)計(jì)算結(jié)點(diǎn)構(gòu)成的計(jì)算系統(tǒng)，每個(gè)計(jì)算結(jié)點(diǎn)內(nèi)含1塊Zynq芯片(Zynq7030)，有低功耗 CPU 和 FPGA 混合計(jì)算核心[15]，2種異構(gòu)計(jì)算資源通過高速的互連總線緊密耦合，可以支持通用計(jì)算任務(wù)和加速計(jì)算任務(wù)的并行協(xié)同執(zhí)行?；旌虾诵耐鈬闪? GB的低功耗DDR內(nèi)存、32 GB Flash存儲(chǔ)器、千兆以太網(wǎng)接口、高速環(huán)形網(wǎng)接口等。蟻群硬件系統(tǒng)采用了模塊化設(shè)計(jì)的方法，16個(gè)低功耗混合計(jì)算核心的異構(gòu)結(jié)點(diǎn)通過2套環(huán)網(wǎng)構(gòu)成計(jì)算板，多塊計(jì)算板組成ATCA機(jī)箱，按照需求可組建包含數(shù)千、數(shù)萬個(gè)結(jié)點(diǎn)的計(jì)算加速系統(tǒng)，系統(tǒng)結(jié)構(gòu)如圖2所示。

Figure 2 Structure of distributed computing platform圖2 分布式計(jì)算平臺(tái)結(jié)構(gòu)

結(jié)點(diǎn)內(nèi)，CPU和FPGA通過高級(jí)可擴(kuò)展接口AXI(Advanced eXtensible Interface)總線相連，有4個(gè)高速接口可用于數(shù)據(jù)傳輸，總帶寬可超過4 GB/s。結(jié)點(diǎn)間，F(xiàn)PGA通過高速串行口GTX組成高速環(huán)網(wǎng)，單端口傳輸帶寬可達(dá)6.6 Gb/s；CPU通過千兆以太網(wǎng)相連。蟻群系統(tǒng)中，結(jié)點(diǎn)內(nèi)的混合核心以及結(jié)點(diǎn)間均有著很高的數(shù)據(jù)傳輸帶寬。

2.2 規(guī)則的分布式拆分

安全字符串的恢復(fù)需要在短時(shí)間內(nèi)完成規(guī)則的處理，生成新的字符串以便進(jìn)行驗(yàn)證工作，而單個(gè)計(jì)算結(jié)點(diǎn)的計(jì)算能力畢竟有限，因此充分利用蟻群分布式的計(jì)算資源，提升規(guī)則處理速度很有必要。如圖1所示，規(guī)則處理的過程需要對(duì)所有的字典條目和規(guī)則變換條目進(jìn)行處理，不同變換間、不同字典條目之間沒有關(guān)聯(lián)性，沒有數(shù)據(jù)的交互，可以通過拆分變換文件和字典文件，將整體任務(wù)分割成不同的子任務(wù)，進(jìn)行分布式并行處理，通過分布規(guī)模的擴(kuò)大，提高整體的處理速度。

此外，硬件資源的限制也對(duì)分布式處理提出了需求。規(guī)則的處理是同哈希算法的驗(yàn)證過程結(jié)合一起使用的，規(guī)則處理生成的安全字符串需要正向的哈希運(yùn)算來計(jì)算摘要值，從而和存儲(chǔ)的摘要值進(jìn)行比較，以便找到正確的安全字符串。在蟻群結(jié)點(diǎn)內(nèi)部，主要的計(jì)算能力來自可重構(gòu)FPGA，規(guī)則的處理工作以及哈希運(yùn)算工作主要都是在FPGA上進(jìn)行。當(dāng)在1個(gè)芯片內(nèi)同時(shí)實(shí)現(xiàn)41種基本規(guī)則時(shí)，需要占用較多的硬件資源，通過前期實(shí)驗(yàn)發(fā)現(xiàn)，在1個(gè)結(jié)點(diǎn)內(nèi)實(shí)現(xiàn)所有的規(guī)則處理功能需要占用Zynq 7030芯片約70%的硬件資源，此時(shí)，對(duì)于一些簡(jiǎn)單的哈希算法，可以利用剩余30%的資源進(jìn)行片上的運(yùn)算驗(yàn)證，而對(duì)于一些復(fù)雜的哈希算法已經(jīng)沒有足夠的面積和資源來進(jìn)行片內(nèi)的驗(yàn)證運(yùn)算。而在分布式環(huán)境中，考慮將規(guī)則組合進(jìn)行拆分，每個(gè)結(jié)點(diǎn)支持不同的基本規(guī)則，僅對(duì)部分變換進(jìn)行支持，通過多個(gè)結(jié)點(diǎn)支持所有的規(guī)則變換功能。同時(shí)，單個(gè)結(jié)點(diǎn)僅支持幾個(gè)基本規(guī)則，可以有足夠的硬件資源來對(duì)處理的流程進(jìn)行優(yōu)化，從而提升每個(gè)結(jié)點(diǎn)內(nèi)規(guī)則處理的速度。

如圖3所示，對(duì)41種基本規(guī)則進(jìn)行拆分，根據(jù)拆分的結(jié)果將變換文件也進(jìn)行拆分，每個(gè)計(jì)算結(jié)點(diǎn)僅支持幾種基本規(guī)則，僅處理由這幾種基本規(guī)則組合形成的變換。

Figure 3 Schematic diagram of splitting of rules and transformation files圖3 規(guī)則與變換文件拆分示意圖

對(duì)規(guī)則的拆分，基于已有的規(guī)則變換文件進(jìn)行。本文用“N組合”來表示1次變換中使用的基本規(guī)則的種類數(shù)，理論上N的取值可以從1～41。但是，對(duì)301 472個(gè)已有規(guī)則變換進(jìn)行分析，可以發(fā)現(xiàn)N的取值只是從1～6，即并不是41種基本規(guī)則都存在組合在一起使用的情況。表2統(tǒng)計(jì)了已有變換文件中所有N組合出現(xiàn)的種類數(shù)，占據(jù)大多數(shù)的是1組合、2組合和3組合。如3組合一共出現(xiàn)了4 934種，這個(gè)數(shù)字是小于C(41,3)的，即不是41種基本規(guī)則中任意3種都存在組合的情況。表2的第2行是該種組合覆蓋的總的變換數(shù)量，可見1組合、2組合和3組合覆蓋了總的變換的99.6%，由于1組合包含在2組合和3組合中，所以規(guī)則的拆分主要針對(duì)2組合和3組合進(jìn)行。

Table 2 Statistical results of rule combinations表2 規(guī)則組合的統(tǒng)計(jì)結(jié)果

如果每個(gè)結(jié)點(diǎn)僅支持1種規(guī)則組合的情況，將需要太多的計(jì)算結(jié)點(diǎn)，所以對(duì)規(guī)則進(jìn)行拆分時(shí)，每個(gè)結(jié)點(diǎn)在滿足資源限制的情況下應(yīng)支持盡量多的規(guī)則組合。所要恢復(fù)的哈希算法已經(jīng)通過硬件實(shí)現(xiàn)，可以知道其在芯片中的資源占用，據(jù)此可以確定剩余給規(guī)則處理的資源，而每種基本規(guī)則的資源占用情況通過前期實(shí)驗(yàn)也可以獲得。根據(jù)以上數(shù)據(jù)，可以將基本規(guī)則拆分成不同的組合，具體拆分時(shí)，按照?qǐng)D4所示流程進(jìn)行。根據(jù)基本規(guī)則拆分的結(jié)果，將三十余萬個(gè)變換也進(jìn)行拆分，形成較小的任務(wù)課題，對(duì)應(yīng)到蟻群結(jié)點(diǎn)上。

Figure 4 Flow chart for rule splitting圖4 規(guī)則拆分流程圖

2.3 硬件規(guī)則處理器

對(duì)基本規(guī)則進(jìn)行拆分后，每個(gè)結(jié)點(diǎn)僅需要支持幾個(gè)基本規(guī)則即可。規(guī)則的處理功能主要在可重構(gòu)FPGA上實(shí)現(xiàn)，只需占用較少的硬件資源，保證哈希算法的處理性能。處理時(shí)，該結(jié)點(diǎn)對(duì)應(yīng)的字典文件和變換文件存放于片外DDR內(nèi)存中，通用ARM核心配置好字典文件與變換文件的大小以及存儲(chǔ)位置，F(xiàn)PGA便可以自動(dòng)通過AXI總線從片外獲取字典和變換，并解析處理，生成新的字符串。

硬件規(guī)則處理器總體結(jié)構(gòu)如圖5所示，其主體為規(guī)則執(zhí)行單元REU (Rule Execute Unit)。REU負(fù)責(zé)各個(gè)規(guī)則的處理功能；譯碼電路負(fù)責(zé)對(duì)變換中的基本規(guī)則進(jìn)行譯碼，對(duì)各個(gè)REU進(jìn)行調(diào)度；總線接口電路包含AXI總線接口，并負(fù)責(zé)與片外的數(shù)據(jù)交互；預(yù)處理電路負(fù)責(zé)將連續(xù)存儲(chǔ)在一起的變換和字典數(shù)據(jù)處理成變換條目和字典條目，數(shù)據(jù)交互網(wǎng)絡(luò)負(fù)責(zé)REU間數(shù)據(jù)的交互以及將最終生成的安全字符串寫入FIFO中供哈希算法模塊使用。

Figure 5 Hardware structure rule processor圖5 硬件規(guī)則處理器結(jié)構(gòu)圖

因?yàn)楣Ｋ惴K以流水線實(shí)現(xiàn)，每個(gè)時(shí)鐘周期都可以對(duì)1個(gè)安全字符串進(jìn)行驗(yàn)證，對(duì)規(guī)則執(zhí)行的速度提出很高的要求，為了盡量提升規(guī)則執(zhí)行的速度，設(shè)計(jì)中將單個(gè)規(guī)則執(zhí)行的過程進(jìn)行優(yōu)化，使其在1個(gè)時(shí)鐘周期內(nèi)完成，在譯碼電路的調(diào)度下，做到1個(gè)時(shí)鐘周期處理完1個(gè)基本規(guī)則，當(dāng)規(guī)則組合在一起進(jìn)行1次變換時(shí)，1次變換的執(zhí)行過程示意圖如圖6所示，圖6以3次規(guī)則組合使用為例進(jìn)行說明，3個(gè)時(shí)鐘周期執(zhí)行完畢。

Figure 6 Schematic diagram of execution process of one transformation圖6 1次變換的執(zhí)行過程示意圖

對(duì)于大量存在的規(guī)則組合使用的情況，即便1個(gè)基本規(guī)則在1個(gè)時(shí)鐘周期之內(nèi)執(zhí)行完成，完整的變換過程處理完畢，生成1個(gè)新的字符串仍需要多個(gè)周期，幾個(gè)規(guī)則組合在一起便需要幾個(gè)周期完成。此時(shí)，每個(gè)時(shí)刻只有1個(gè)REU在工作，處理效率較低。因此，需要在譯碼電路的控制下，盡量將整個(gè)變換過程做到全流水實(shí)現(xiàn)。

在只有1套規(guī)則處理單元的情況下，只有滿足同一時(shí)刻不能有處理單元的沖突，才可以做到全流水處理。通過對(duì)hashcat自帶變換文件的分析發(fā)現(xiàn)，大多數(shù)情況下，1次變換不使用相同的基本規(guī)則，據(jù)此設(shè)計(jì)了全流水的執(zhí)行結(jié)構(gòu)，執(zhí)行結(jié)構(gòu)的示意圖如圖7所示。此時(shí)，每1個(gè)時(shí)鐘周期都有1個(gè)安全字符串處理完畢，都有1個(gè)新的字符串產(chǎn)生，每1個(gè)時(shí)刻都有多個(gè)規(guī)則執(zhí)行單元在同時(shí)工作，無需插入氣泡，無需等待，最大限度提升了規(guī)則處理的效率。對(duì)于另外少部分的情況，在1次變換中存在相同基本規(guī)則時(shí)，通過譯碼電路的有效控制，字符串嚴(yán)格按照串行方式進(jìn)行處理，1個(gè)安全字符串完全處理完畢后才開始下1個(gè)處理工作，此時(shí)生成1個(gè)新的字符串需要多個(gè)時(shí)鐘周期。

Figure 7 Rule execution architecture supporting full flow圖7 支持全流水的規(guī)則執(zhí)行結(jié)構(gòu)

3 實(shí)驗(yàn)結(jié)果

為驗(yàn)證所設(shè)計(jì)的分布式規(guī)則處理架構(gòu)的功能正確性和性能指標(biāo)，本文在蟻群分布式平臺(tái)上進(jìn)行了開發(fā)實(shí)現(xiàn)，并針對(duì)不同的情況進(jìn)行了測(cè)試，分析了其性能以及功耗情況，并與其他平臺(tái)的運(yùn)行結(jié)果進(jìn)行了對(duì)比分析。

3.1 硬件規(guī)則處理器實(shí)驗(yàn)

在蟻群結(jié)點(diǎn)的ARM通用計(jì)算核心上開發(fā)配置管理程序，通過Vivado工具對(duì)FPGA設(shè)計(jì)部分進(jìn)行綜合與實(shí)現(xiàn)，結(jié)果顯示，單結(jié)點(diǎn)的硬件規(guī)則處理器運(yùn)行結(jié)果正確，可以達(dá)到的最高工作頻率為150 MHz。

本文首次以FPGA硬件進(jìn)行規(guī)則的解析處理工作，并與Intel CPU和NVIDIA GPU上的軟件實(shí)現(xiàn)進(jìn)行對(duì)比。將相同的規(guī)則文件和字典文件分別在CPU和GPU上運(yùn)行，并與本文的硬件規(guī)則處理器的結(jié)果進(jìn)行對(duì)比分析，對(duì)比了處理性能和功耗2個(gè)方面。軟件實(shí)現(xiàn)采用最新的hashcat 5.1.0進(jìn)行，hashcat號(hào)稱是業(yè)界最快的恢復(fù)工具[6]，軟件的結(jié)果與其運(yùn)行平臺(tái)有很大的關(guān)系，如NVIDIA GPU中其桌面產(chǎn)品和專門用于高性能計(jì)算的產(chǎn)品，計(jì)算能力差距非常大，本文選取主流偏上的產(chǎn)品平臺(tái)進(jìn)行實(shí)驗(yàn)，采用的CPU平臺(tái)為：Intel(R)Core(TM)i7-6700 CPU @ 3.40 GHz，32 GB內(nèi)存，GPU平臺(tái)為：NVIDIA GeForce GTX 1080 Ti。

對(duì)于變換情況，在每種平臺(tái)上分別測(cè)試了1組合、2組合和3組合的情況，字典中字符串的長(zhǎng)度以8個(gè)字符為例進(jìn)行實(shí)驗(yàn)，處理性能以每秒生成多少兆個(gè)新字符串進(jìn)行統(tǒng)計(jì)，結(jié)果如表3所示。

Table 3 Performance comparison of different platforms when dictionary length is 8表3 字典長(zhǎng)度為8時(shí)不同平臺(tái)的性能對(duì)比 M個(gè)/s

通過分析可以發(fā)現(xiàn)：在全流水情況下，規(guī)則的組合情況對(duì)本文處理器的處理性能沒有影響，但對(duì)CPU和GPU平臺(tái)的影響較大，規(guī)則組合的次數(shù)越多，其處理性能越差。2或者3個(gè)基本規(guī)則組合在一起進(jìn)行1次變換占據(jù)絕大多數(shù)情況，此時(shí)規(guī)則處理器每秒生成150M個(gè)新字符串，處理性能優(yōu)于CPU平臺(tái)，差于GPU平臺(tái)。然而，當(dāng)使用該規(guī)則處理器來構(gòu)建大規(guī)模、分布式的規(guī)則處理系統(tǒng)時(shí)，其計(jì)算能力會(huì)顯著增加。

在規(guī)則處理過程中，對(duì)蟻群結(jié)點(diǎn)和GPU平臺(tái)的運(yùn)行功耗進(jìn)行觀測(cè)，CPU的功耗以65 W計(jì)算，計(jì)算性能功耗比(每瓦特每秒可以處理的規(guī)則變換數(shù)量)，結(jié)果如圖8所示。對(duì)于2個(gè)或者3個(gè)基本規(guī)則組合在一起的情況，本文硬件規(guī)則處理器的性能功耗比相比于GPU提升1.4倍～2.1倍，相比于CPU提升49～70倍，在能效方面具有優(yōu)勢(shì)。

Figure 8 Comparison of energy efficiency on different platforms圖8 不同平臺(tái)間的能效對(duì)比

3.2 分布式拆分實(shí)驗(yàn)

根據(jù)每個(gè)結(jié)點(diǎn)可以使用的硬件資源，將41種基本規(guī)則拆分成不同的小的集合，利用蟻群系統(tǒng)的分布式資源，支持所有三十余萬條目的規(guī)則變換。對(duì)規(guī)則進(jìn)行拆分時(shí)，結(jié)合2種實(shí)際的工作環(huán)境進(jìn)行：一種是哈希算法較復(fù)雜，留給規(guī)則處理的硬件資源較少的情況；另一種是哈希算法較簡(jiǎn)單的情況。在分布式環(huán)境中，利用每個(gè)計(jì)算結(jié)點(diǎn)有限的硬件資源，實(shí)現(xiàn)完整的規(guī)則處理功能所需要的拆分?jǐn)?shù)量如表4所示。

Table 4 Results of rules splitting 表4 規(guī)則拆分結(jié)果

對(duì)表4進(jìn)行分析可以發(fā)現(xiàn)，所需要的拆分?jǐn)?shù)量受可用資源的影響較大。對(duì)于復(fù)雜算法，單個(gè)結(jié)點(diǎn)上留給規(guī)則處理的硬件資源較少，需要較大的分布規(guī)模才能完全實(shí)現(xiàn)所有的規(guī)則處理功能。對(duì)于簡(jiǎn)單算法，片上留給規(guī)則處理的資源較多，只需較小的分布規(guī)模即可實(shí)現(xiàn)完整的規(guī)則處理功能。

在192個(gè)結(jié)點(diǎn)規(guī)模的蟻群系統(tǒng)上進(jìn)行分布式規(guī)則處理架構(gòu)的實(shí)現(xiàn)，此時(shí)蟻群系統(tǒng)的形態(tài)為14U的標(biāo)準(zhǔn)ATCA機(jī)箱。通過腳本語言開發(fā)自動(dòng)化工具，調(diào)用Vivado工具，對(duì)規(guī)則拆分后各結(jié)點(diǎn)的FPGA邏輯進(jìn)行綜合與實(shí)現(xiàn)，生成比特流文件；在ARM通用計(jì)算核心上開發(fā)配置管理程序，對(duì)硬件規(guī)則處理器進(jìn)行配置管理；根據(jù)分布式系統(tǒng)的規(guī)模限制，結(jié)合FPGA的可重構(gòu)特性，對(duì)字典和變換文件進(jìn)行劃分，形成子課題；通過蟻群系統(tǒng)的Condor分布式管理程序進(jìn)行任務(wù)的分配管理。最終結(jié)果顯示，分布式規(guī)則處理架構(gòu)運(yùn)行結(jié)果正確。因?yàn)橐?guī)則處理任務(wù)結(jié)點(diǎn)間沒有數(shù)據(jù)的交互，結(jié)合課題的劃分和FPGA的重構(gòu)，實(shí)際運(yùn)行性能為單結(jié)點(diǎn)的192倍，性能相比GPU提升2.4～3.6倍，相比CPU提升288～411倍，能效相比GPU提升1.4～2.1倍，相比CPU提升49～70倍。

4 結(jié)束語

字符串變換規(guī)則在安全字符串的恢復(fù)中具有重要作用，其處理過程復(fù)雜，對(duì)處理性能、系統(tǒng)功耗有很高的要求，本文針對(duì)這些需求，提出分布式的規(guī)則處理架構(gòu)，并首次采用FPGA硬件加速規(guī)則的處理過程，有效利用蟻群計(jì)算平臺(tái)的分布式計(jì)算資源，利用FPGA高并行、低功耗的特點(diǎn)，構(gòu)建了規(guī)則處理架構(gòu)，并進(jìn)行了設(shè)計(jì)實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，該分布式規(guī)則處理架構(gòu)處理性能高、運(yùn)行功耗低，能效相比CPU、GPU有顯著提升，隨著分布式規(guī)模的擴(kuò)大可以達(dá)到很高的計(jì)算性能，滿足實(shí)際工程需求。