基于GPU并行枚舉DES密鑰Bitslice方法的實現(xiàn)

（石化盈科信息技術(shù)有限責(zé)任公司，北京 100007）

1 研究背景

統(tǒng)一計算設(shè)備架構(gòu)CUDA（Compute Unified Device Architecture），它是NVIDIA公司提出的一種通用并行計算平臺和編程模型。通過使用GPU高性能并行多線程能力，解決大數(shù)據(jù)計算的模型已被廣泛應(yīng)用在密碼破譯[1-5]、模型分析[6-9]、圖形圖像[10-13]等領(lǐng)域。通過使用CUDA開發(fā)平臺可以開發(fā)在CPU和GPU上運行的通用計算程序。并行編程的中心思想是分組數(shù)據(jù)：將大數(shù)據(jù)劃分為一些小塊數(shù)據(jù)組，再把這些小塊數(shù)據(jù)組交給相應(yīng)的處理單元并行處理。CUDA中的問題被粗粒度地劃分為若干子問題（塊Block），每個塊都由一些線程組成，線程是CUDA中最小的處理單元。子問題進一步劃分為若干更小的細粒度的線程問題以解決。CUDA線程數(shù)目通常能達到數(shù)千個甚至上萬個，通過不同的優(yōu)化方法，劃分模型可以數(shù)十倍地提升計算性能。

GPU是由多個流處理器構(gòu)成的，流處理器以塊（Block）為基本調(diào)度單元，因此，對于流處理器較多的GPU，它一次可以處理的塊（Block）更多，從而運算速度更快，時間更短。反之對于流處理器較少的GPU，其運算速度便會較慢[14]。這一原理可以通過圖1看出來：

圖1 GPU流處理器處理性能的比較

對于浮點數(shù)操作能力，CPU與GPU的能力相差在GPU更適用于計算強度高、流程簡單的并行計算中。GPU擁有更多晶體管，而不是像CPU一樣具有數(shù)據(jù)Cache和流控制器。這樣的設(shè)計是因為并行計算的時候每個數(shù)據(jù)單元執(zhí)行相同程序，不需要那么繁瑣的流程控制，而更需要高計算能力，從而也不需要大Cache來緩存數(shù)據(jù)。CPU架構(gòu)與GPU架構(gòu)的對比如圖2所示[15]。

圖2 CPU架構(gòu)與GPU架構(gòu)的對比

隨著“三金”工程尤其是金卡工程的啟動，DES算法在POS、ATM、智能卡、收費站等領(lǐng)域被廣泛使用，例如持卡人的PIN碼保護加密算法、智能卡與設(shè)備交互之間的雙向認證、數(shù)據(jù)包的MAC效驗等均使用到了DES算法。DES算法的入口有3個參數(shù)：key、data、mode。其中key是一個8字節(jié)64位；data也是8字節(jié)64位；而key實際上的每一字節(jié)是7bit位，最后一位是奇偶效驗位。DES的算法框圖如圖3所示[16]。

圖3 DES算法框圖

本文開發(fā)的基于CPU和GPU枚舉DES密鑰的Bitslice程序所使用的開發(fā)環(huán)境為Microsoft Windows 10 Professional 64位，Intel Core i5-2300@2.8GHz，8GB內(nèi) 存，GPU為 Geforce GTX Titan Z，GPU詳細的引擎規(guī)格如圖4所示。由于Geforce GTX Titan Z是GPU×2。為了對比研究僅使用一個GPU芯片單元，顯存大小也為原始的1/2即6GB。驅(qū)動程序版本號為344.11。CUDA開發(fā)環(huán)境為V6.5，SDK版本為4.2.9，CPU和GPU所使用的開發(fā)編譯環(huán)境為Visual Studio2013。

圖5為Geforce GTX Titan Z顯卡的CUDA詳細參數(shù)，每個處理器的最大線程數(shù)為2048個，每個block中的線程數(shù)為1024個。還包括Grid和不同維度上block塊的大小（維度上不對稱）。最重要的是memory pitch數(shù)據(jù)的大小為2147483647 Bytes，這個參數(shù)與復(fù)制的數(shù)組的容量有關(guān)。

圖4 GPU詳細的引擎規(guī)格

圖5 CUDA詳細參數(shù)

2 CUDA并行化的實現(xiàn)

GPU并行化程序的調(diào)試，首先實現(xiàn)在CPU上的單線程過程，通過單線程程序再改寫成GPU多線程并行化程序，這樣做的好處是能方便的計算出GPU相對于CPU的性能提升比。由于在支持超線程技術(shù)的單CPU上目前線程數(shù)一般不會超過48個線程。因此使用CPU進行多線程解決大數(shù)據(jù)問題并不具有可操作性。

2.1 CPU單線程Bitslice程序設(shè)計

單CPU端的單線程的Bitslice程序的流程如下：輸入兩個8字節(jié)的明文iv_p和pt_p這兩個數(shù)字按位做異或運算，運算后得到64位的明文并存在在ptext[64]中，每一個字節(jié)的最后一位與前七位進行與操作，判斷是否為非零，如果非零則輸出非零的無符號長整型，否則則輸出零。將這個數(shù)作為明文存在p[64]中。同樣的道理將密文和預(yù)輸入的key也存在c[64]和k[64]中。在32位系統(tǒng)中32bit為25，取位長的log值，使key的后五位與1或運算，如果這5位bit數(shù)與密文的相對應(yīng)的bit位一致則進行另5bit位的比較，一次比較相當(dāng)于進行了32次密鑰搜索，Bitslice程序相當(dāng)于自身并行運行提高破解效率。CPU單線程Bitslice程序不對密鑰數(shù)據(jù)分組，會從高位一直向低位遍歷，每一字節(jié)為0～255的數(shù)，通過Bitslice程序和最后一位奇偶效驗位的簡化，0～255被分成1，3，5，7.....255的128個數(shù)，相當(dāng)于每個字節(jié)搜索128個數(shù)。如表1所示，程序?qū)ey[56]的一維數(shù)組輸入到deseval函數(shù)中進行計算，如果對比發(fā)現(xiàn)為0，進行increment_key函數(shù)改變key的5個bit位之后的一位置為無符號的1，再進行deseval函數(shù)計算，以此類推直到所有的bit位全部對上才算找到key。

表1 CPU遍歷key的查詢函數(shù)

2.2 GPU多線程Bitslice程序設(shè)計

GPU多線程Bitslice程序設(shè)計的主要思想則是為了多線程的調(diào)用而優(yōu)化的，它是將密鑰數(shù)據(jù)進行分組到每個block中，每個block中的線程又執(zhí)行不同分組的數(shù)據(jù)密鑰，眾多的線程累加起來完成全部的密鑰空間。將密鑰分塊為若干個區(qū)域，每個區(qū)域作為一個流要執(zhí)行的部分。再次使用與流數(shù)相關(guān)的第二個區(qū)域作為第二個流的數(shù)據(jù)區(qū)域，以此類推。

而對于每個數(shù)據(jù)分塊，直到線程為止。定義每個塊中含有256（ThreadN）個線程，含有BlockN個塊。因此，ThreadN×BlockN就是一共含有的線程數(shù)。將大數(shù)據(jù)分成ThreadN×BlockN個小模塊中處理，假設(shè)單步處理總時間為T，理想情況下所需時間應(yīng)為T/ThreadN×BlockN，但是實際情況下顯卡處理器性能會對其產(chǎn)生限制。舉例說，顯卡處理器為W位，在ThreadN×BlockN＞W(wǎng)的情況下，數(shù)據(jù)處理仍是位一組，提高時速應(yīng)在W倍附近。數(shù)組的列即枚舉key的bit長度——56位長度。

圖6 數(shù)據(jù)分組結(jié)構(gòu)示意圖

數(shù)據(jù)分組結(jié)構(gòu)的示意圖如圖6所示，假設(shè)形成標(biāo)準(zhǔn)的XYZ三軸坐標(biāo)軸體系，那么X軸就為BlockN表示塊數(shù)。Z軸為Rows表示每塊數(shù)據(jù)的一個數(shù)據(jù)的首地址。Y軸為Cols表示為經(jīng)過Bitslice轉(zhuǎn)換的56位密鑰的數(shù)據(jù)。由CPU端到GPU端涉及到線程關(guān)聯(lián)問題，即將現(xiàn)有問題或數(shù)據(jù)分成多塊，并將這樣的數(shù)據(jù)多塊與每一個線程關(guān)聯(lián)，得到一個與線程ID有關(guān)的函數(shù)。這樣每個線程ID與沒有數(shù)據(jù)塊進行關(guān)聯(lián)后進行計算可以得到每個線程計算的結(jié)果。如表2，GPU遍歷Key的查詢函數(shù)，但是數(shù)據(jù)塊ID與線程ID的關(guān)聯(lián)模型并不是惟一，不同關(guān)聯(lián)方式對性能的影響也不一樣。

表2 GPU遍歷key的查詢函數(shù)

在程序中Dsize的大小很重要，這個參數(shù)用于控制枚舉的數(shù)量。在GPU并行多線程中，有些線程會重復(fù)操作，因此以密鑰的一個字節(jié)為例：枚舉{255，0，0，0，0，0，0，0}時，Dsize的數(shù)量最小為 Threads×3+1。當(dāng)枚舉 {255，255，0，0，0，0，0，0}時，Dsize的數(shù)量最小為 Threads×511+1。枚舉 {255，255，255，0，0，0，0，0}時，Dsize的數(shù)量最小為Threads×65535+1。

我們設(shè)計的程序分塊的思想為前3個字節(jié)都為0，讓GPU去累加，而從第4個字節(jié)開始使用Bitslice思想讓其分為128段（1，3，5，7...255）。以線程數(shù)的累加增加分塊的數(shù)量同時增加密鑰的累積長度，實現(xiàn)在同等時間內(nèi)搜索密鑰的長度更長。Dsize與搜索時間的關(guān)系圖如圖7所示。

圖7 時間隨Dsize變化的趨勢圖

由于單粒GPU的并行量和計算速度都不可能獨立破解DES算法。因此，為了能驗證GPU并行化所帶來的優(yōu)勢，在一定密鑰的長度下同時考驗GPU和CPU所花費的時間來計算GPU加速倍數(shù)，且這個密鑰的長度不能選擇太長，由于CPU計算時間過長而失去驗證的意義。選取密鑰長度為{255，255，255，255，255，1，1，1}，即密鑰長度為2^36次方。使用GPU多線程計算設(shè)計線程為16384個線程，Dsize大小為：1073741824，窮舉出密鑰的時間為402秒，而通過CPU進行計算的Bitslice程序在計算同樣密鑰長度的時間為：15343秒。因此可以看出使用GPU數(shù)據(jù)分塊，并行計算的性能提升是使用CPU的38.2倍。由于在一個GPU中的一個Grid中最大的線程數(shù)只能是65536個。因此使用GPU單流的最大BlockN為：256個。無論如何優(yōu)化這個程序在單核單網(wǎng)格的情況下窮舉DES的全部密鑰成為天方夜譚。必然會想到使用多網(wǎng)格計算或多核計算繼續(xù)優(yōu)化并且擴大并行化操作。在使用多核計算之前，本文先介紹一種流技術(shù)的多網(wǎng)格優(yōu)化方法。下面我們首先對使用CPU和GPU進行計算的性能差異進行簡單的分析，進而論述多網(wǎng)格優(yōu)化的Stream技術(shù)。

3 性能分析及優(yōu)化

3.1 SSE2 vs CUDA

采取Microsoft Windows 10 Professional 64bit操作系統(tǒng)，Intel（R） Core（R）i5-2300 @2.8GHz CPU8GB 內(nèi)存，軟件則使用SSE2加速算法。當(dāng)前的x86處理器采用亂序執(zhí)行和緩存上下文讀取，使用CPU的軟SSE2指令集計算同樣的程序，事實是CPU的執(zhí)行效率和速度明顯的優(yōu)于GPU的單線程。使用不同的配置進行測試，SSE2優(yōu)化代碼（基于位計數(shù)的查表法）通常會快很多，而使用矩陣換位變換的則速度完全相同。這一點在英特爾凌動處理器上的SSE2代碼更為突出，因此英特爾凌動處理器Atom的單指令多數(shù)據(jù)流（Single Instruction Multiple Data，SIMD）單元明顯是經(jīng)過定制優(yōu)化。Nehalem微架構(gòu)實現(xiàn)了硬件POPCNT，所以應(yīng)該會更快。但不幸的是，有證據(jù)表明它并沒有不執(zhí)行POPCNT真正的SIMD128位版本，所以SSE+ POPCNT組合成為最后的選擇[17-21]。

數(shù)據(jù)組作為GPU不變參量傳入，常量內(nèi)存交換速度快，但速度也就相當(dāng)于CPU的Cache緩存速率。因此設(shè)定傳入GPU的常量數(shù)組或數(shù)據(jù)為share類型。但是通常share類型的數(shù)據(jù)存儲容量非常有限，一般的share類型的容量僅有16K。實現(xiàn)線程ID與數(shù)據(jù)結(jié)構(gòu)ID的關(guān)聯(lián)時，則必須找到起始線程和寄存器之間復(fù)制關(guān)系代碼，且由于CUDA使用的是地址復(fù)制，一般在一維數(shù)組的復(fù)制上很容易編程，而在二維、三維數(shù)組的復(fù)制時，必須找到代碼與硬件調(diào)用之間的良好平衡。這也就是為什么CUDA的例子里很少有使用二維以上的數(shù)組。如表3所示為主機端到設(shè)備端的二維數(shù)組復(fù)制的方法。如果使用Stream流技術(shù)進行優(yōu)化的話，需增加一維為流ID，則主機端（Host）到設(shè)備端（Device）的數(shù)據(jù)復(fù)制為三維數(shù)組復(fù)制。

表3 Host-to-Device多維數(shù)組復(fù)制

cudaMemcpyHostToDevice）；hKo = （unsigned int**）malloc（ROWS*sizeof（unsigned int*））；ho = （unsigned int*）malloc（ROWS*COLS*sizeof（unsigned int））；cudaMalloc（（void**）（&dKo），ROWS*sizeof（unsigned int*））；cudaMalloc（（void**）（&dco），ROWS*COLS*sizeof （unsigned int））；hRes = （unsigned int*）malloc（8 * sizeof（unsigned int））；cudaMalloc（（void**）&dRes，sizeof（unsigned int） * 8）；hbuf = （unsigned int**）malloc（ROWS * sizeof（unsigned int*））；for （int i = 0；i ＜ ROWS；i++）{cudaMalloc（（void **）&hbuf[i]，ROWS * sizeof（unsigned int））；}cudaMalloc（（void**）（&dKK），ROWS*sizeof（unsigned int*））；for （int i = 0；i ＜ ROWS；i++）{cudaMemcpyAsync（hbuf[i]，KK[i]，sizeof（unsigned int）*ROWS，cudaMemcpyHostToDevice）；}cudaMemcpyAsync（（void*）dKK，（void*）hbuf，ROWS *sizeof（unsigned int*），cudaMemcpyHostToDevice）；hKo = （unsigned int**）malloc（ROWS*sizeof（unsigned int*））；for （int r = 0；r ＜ ROWS；r++）{hKo[r] = dco + r*COLS；}cudaMemcpyAsync（（void*）（dKo），（void*）（hKo），ROWS*sizeof（unsigned int*），cudaMemcpyHostToDevice）；

頻繁進行host到device之間的上下文內(nèi)存?zhèn)鬏敃r，CUDA內(nèi)核視調(diào)用內(nèi)存上下文訪問為高延遲操作。這對于相對簡單的和高速整數(shù)運算尤為重要，這能提高計算程序調(diào)用硬件的效率。而對于需要頻繁進行內(nèi)存操作交換數(shù)據(jù)的程序則不能通過GPU進行加速。顯卡沒有操作系統(tǒng)或者受控于自身的復(fù)雜任務(wù)規(guī)劃或調(diào)度，硬件的直接訪問可以很好地對任務(wù)進行擴展。允許將程序分割成不均勻子任務(wù)。但是，不能并行太多不同的任務(wù)異步。由于著色器可預(yù)見的復(fù)雜和脆弱的存在。CPU-GPU中間件復(fù)雜限于結(jié)合并行在GPU上執(zhí)行的任務(wù)次數(shù)。

總之，CPU編程中使用SIMD矢量編程（SSE）是需要一定編程技巧的，這里的主要問題是當(dāng)前一代SSE并不是完整的圖靈架構(gòu)。從Michael Abrash[21]似乎看出LEBni（Larrabee的矢量指令集）將更好，Larabee有512位矢量寄存器。另外，Nvidia公司似乎并沒有重點發(fā)展異構(gòu)計算架構(gòu)，其麥克斯韋架構(gòu)也沒有慢上下文切換。上下文切換計算可以使得GPU像CPU一樣，利用上下文切換來管理多任務(wù)，每一個任務(wù)都可以通過分時的方法利用計算機資源。隨著AMD公司的GCN異構(gòu)計算架構(gòu)（計算單元是基于新指令集的架構(gòu)，拋棄了以往的VLIW（甚長指令字），而且每個計算單元都能同時從多個內(nèi)核那里執(zhí)行指令，單位周期單位面積的指令數(shù)也有所增加。這種架構(gòu)相比以往利用率和吞吐量更高，多線程多任務(wù)并行執(zhí)行的能力也大大增強）的發(fā)展，GCN架構(gòu)的緩存體系也經(jīng)過了完全重新設(shè)計，規(guī)模相當(dāng)龐大而復(fù)雜。每四個計算單元共享16KB指令緩存和32KB標(biāo)量數(shù)據(jù)緩存，并與二級緩存相連；每個計算單元都有自己的寄存器和本地數(shù)據(jù)共享，搭配16KB可讀寫一級緩存，每時鐘周期帶寬為64字節(jié)；二級緩存總?cè)萘?68KB，可讀寫，對應(yīng)每個顯存控制器分成六組，每組容量128KB，每時鐘周期帶寬也是64字節(jié)；全局數(shù)據(jù)共享則用于不同計算單元之間的同步輔助。因此通用計算平臺會成為GCN vs CUDA的對立格局。

3.2 Stream流技術(shù)優(yōu)化

一些計算能力2.x或更高的設(shè)備可以同時并行執(zhí)行多個內(nèi)核函數(shù)。應(yīng)用程序可以檢查設(shè)備屬性中的concurrentKernels項來確定設(shè)備是否支持這一功能，值為1代表支持。運算能力3.5的設(shè)備在同一時刻能夠并行執(zhí)行的最大內(nèi)核函數(shù)數(shù)量為32，運算能力小于3.5的硬件則最多支持同時啟動16個內(nèi)核函數(shù)的執(zhí)行。同時需要注意的是，在一個CUDA上下文中的內(nèi)核函數(shù)不能與另一個CUDA上下文中的內(nèi)核函數(shù)同時執(zhí)行。使用很多紋理內(nèi)存或者大量本地內(nèi)存的內(nèi)核函數(shù)也很可能無法與其他內(nèi)核函數(shù)并行執(zhí)行。為了并行化數(shù)據(jù)拷貝和內(nèi)核執(zhí)行，主機端內(nèi)存必須分配為鎖頁（page-locked）內(nèi)存其模塊結(jié)構(gòu)如圖8所示[22-26]。

圖8 CUDA流技術(shù)加速原理示意圖

流的作用是任務(wù)之間的并行化，把要計算的數(shù)據(jù)分塊，讓不同的流執(zhí)行不同的數(shù)據(jù)塊，這樣Stream1執(zhí)行數(shù)據(jù)塊1的時候，Stream2把數(shù)據(jù)塊2從內(nèi)存拷貝到顯存，這樣做不用等到所有數(shù)據(jù)拷貝完之后再計算從而提高并行力度。通過使用Stream流技術(shù)加速并擴大并行運算密鑰Key的長度后，可以實現(xiàn)240次方的密鑰長度計算時間為7.46小時。這個長度的密鑰在CPU上的實現(xiàn)是非常困難的。但是在GPU多線程并行加速的架構(gòu)下，只需執(zhí)行幾個小時即可完成。但是這個長度的密鑰離完全窮舉完全部密鑰還差很遠，以這樣的速度計算下去全部窮舉完的時間是無法接受的。

4 結(jié)束語

計算速率競爭的時代已經(jīng)結(jié)束，現(xiàn)代的計算全面進入到并行時代。這意味著算法和系統(tǒng)的自適應(yīng)性，并行架構(gòu)的組織以滿足數(shù)以萬計的并行線程的現(xiàn)實，其中數(shù)據(jù)需要分塊、重組，減少沖突和適應(yīng)并行訪問將成為并行計算的核心計算。GP-GPU計算的使用必須使用大量的計算資源，結(jié)合不斷增長的數(shù)據(jù)挖掘集群服務(wù)器才能提供高效的計算服務(wù)。結(jié)合目前發(fā)展的快速隨機訪問固態(tài)硬盤SSD、高速RAM驅(qū)動器、DDR4代內(nèi)存以節(jié)省帶寬減緩可以提供更高效的上下文訪問機制。并行計算作為一種科學(xué)手段，隨著科研需求而迅猛發(fā)展，幫助學(xué)者們解決了很多復(fù)雜、冗余的問題。同時也給密碼計算帶來了前所未有的挑戰(zhàn)，傳統(tǒng)的CPU密碼計算逐步的轉(zhuǎn)向了分布式GPU陣列密碼破譯網(wǎng)絡(luò)。通過使用大量并行多線程技術(shù)，能有效的降低密碼在單線程任務(wù)上的計算容量，大量的線程任務(wù)同時工作提升了計算效率。雖然相比單CPU的Bitslice程序而言已有38.2倍的性能提升，但是其單個GPU的計算性能仍無法在可接受的時間內(nèi)破解DES算法，因此，下一步的工作就是通過使用MPI多機技術(shù)將多塊GPU組建成集群多機計算陣列。從上述研究可以表明DES在GPU上的運算并不消耗過多的計算資源，因此，每一個GPU的性能并不需太強，可以降低集群計算陣列的整體成本，同時也實現(xiàn)解決問題的目的。