摘要：近幾年圖形處理器GPU的通用計算能力發(fā)展迅速，現(xiàn)在已經(jīng)發(fā)展成為具有巨大并行運算能力的多核處理器，而CUDA架構(gòu)的推出突破了傳統(tǒng)GPU開發(fā)方式的束縛，把GPU巨大的通用計算能力解放了出來。本文利用GPU來加速AES算法，即利用GPU作為CPU的協(xié)處理器，將AES算法在GPU上實現(xiàn)，以提高計算的吞吐量。最后在GPU和CPU平臺上進行了實驗，獲得了GPU的加速結(jié)果，并對實驗結(jié)果進行了優(yōu)化。
關(guān)鍵詞：圖形處理器；統(tǒng)一計算架構(gòu)；高級加密標準算法
0 引言
隨著通信技術(shù)高速發(fā)展，信息安全也越來越重要。加密技術(shù)是對通信系統(tǒng)或者存儲系統(tǒng)中的信息數(shù)據(jù)進行保護的一個很重要的方式。AES(高級加密標準)算法是一種分組密碼算法，具有極高的安全性能，自提出之日起便成為信息安全領(lǐng)域研究的熱點。由于該算法在實現(xiàn)方面具有設(shè)計簡單，速度快，可并行處理，分組長度可以改變，對處理器結(jié)構(gòu)無特殊要求等特點，在電子商務(wù)、網(wǎng)絡(luò)安全和數(shù)據(jù)存儲等多個領(lǐng)域得到了廣泛的應(yīng)用。然而，硬件實現(xiàn)需要較長的開發(fā)周期和很高的成本，并且硬件實現(xiàn)不靈活，不易后續(xù)的升級和維護，而且只適合做部分算法的實現(xiàn)，限制了應(yīng)用領(lǐng)域和范圍。近幾年GPU(圖形處理器)已經(jīng)成為普及的電子消費品，在市場需求的驅(qū)動下，GPU已經(jīng)發(fā)展成為具有巨大運算能力和極高內(nèi)存帶寬的并行多核處理器。近幾年在某些信號處理任務(wù)中使用GPU的運算性能超過了FPGA。
傳統(tǒng)的GPU開發(fā)具有很大的難度，而且由于無法充分利用GPU的資源，并且很多的開發(fā)精力是用在將應(yīng)用轉(zhuǎn)換到圖形上，這就限制了GPU用作通用計算的應(yīng)用范圍，并且影響了GPU進行通用運算的性能。為了改變這一現(xiàn)狀，NVIDIA公司在2006年年底推出了一種利用GPU進行通用計算開發(fā)的架構(gòu)，稱作統(tǒng)一計算設(shè)備架構(gòu)，簡稱為CUDA。它對GPU的結(jié)構(gòu)和資源進行了抽象表示，并且為GPU的資源提供了訪問接口，這就使得開發(fā)者能夠根據(jù)抽象的GPU結(jié)構(gòu)進行通用計算應(yīng)用的設(shè)計，并且可以充分利用到GPU中的資源。
1 AES算法分析
AES算法由NIST在2001年11月26日公布，并在2002年5月26日成為標準。AES算法具有分組長度和密鑰長度均可變的分組密碼。密鑰長度和分組長度可以獨立地指定為128bit、192bit或256bit。AES加密的圈數(shù)是一個變量，主要依賴于密鑰長度，所有的運算都將在一個4×4字節(jié)的模塊上進行。每圈包括4個順序步驟：圈密鑰加，字節(jié)代替，行移位，列混合。在加密以前，我們必須使用密鑰擴展算法擴展密鑰。
狀態(tài)可以用字節(jié)為元素組成二維數(shù)組陣列，共4行，Nb列，Nb等于數(shù)據(jù)塊長度除以32。密鑰的設(shè)計類似二維字節(jié)數(shù)組，也是4行，Nk列，且Nk等于密鑰塊的長度除以32。AES算法使用的是圈變換，其變換的圈數(shù)Nr由Nb和Nk共同決定，如表1所示：
從具體規(guī)則上，AES算法在進行加解密運算時都會按照三大步驟進行，依次為1)初始化的圈密鑰加法；2)(Nr-1)圈變換；3)最后一圈變換。這里以加密過程為例，其加密過程用偽代碼表示如下。
解密過程是加密過程的逆過程。
2 CUDA編程簡介
2．1 CUDA簡介
CUDA全稱是Compute Unified Device Architecture，是NVIDIA公司在2006年11月推出的一種在GPU上進行通用計算的架構(gòu)。它具有全新的并行編程模型，不需要像傳統(tǒng)GPU開發(fā)方式那樣進行圖形API的映射就可以使用GPU的資源進行并行計算。CUDA是一個包含軟件和硬件的完整的并行計算架構(gòu)，它的硬件設(shè)備是具有多個流處理器核的圖形并且支持CUDA的GPU，軟件部分包括編譯工具、驅(qū)動程序、runtime庫和一些常用的數(shù)學運算庫。
2．2 CUDA中GPU結(jié)構(gòu)
在CUDA架構(gòu)下，開發(fā)者可以通過創(chuàng)建和管理大量的線程來使用GPU的硬件資源進行并行計算。在CUDA中線程的創(chuàng)建和切換是由硬件來實現(xiàn)的，不會占用軟件的執(zhí)行時間。在CUDA的rtmtime庫中提供了訪問GPU硬件資源的接口，用戶通過調(diào)用runtime庫中的函數(shù)就可以直接訪問GPU的硬件資源。CUDA的編程語言是一種C語言的擴展，提供了通用的DRAM尋址方式，從而提供了很大的編程靈活性。操作系統(tǒng)可以管理多個并發(fā)運行的CUDA程序和圖形應(yīng)用程序來訪問GPU。
3 CUDA編程模型
由于GPU的特點，它很適合做高密度數(shù)據(jù)的并行運算，但是對于不能并行的具有復(fù)雜執(zhí)行路徑的程序執(zhí)行效率就會很低。因此當通過CUDA在GPU上進行通用計算的開發(fā)時，是把在應(yīng)用程序中高密度數(shù)據(jù)可以進行并行計算的部分做成一個稱作kernel的函數(shù)在GPU設(shè)備上執(zhí)行，而應(yīng)用程序中的其他串行執(zhí)行的部分由主機上的CPU來完成。一個在GPU上執(zhí)行的kernel可以包含極高數(shù)量并發(fā)執(zhí)行的線程，在CUDA架構(gòu)中是通過設(shè)計kernel中的線程來完成通用計算的GPU實現(xiàn)的。主機和GPU設(shè)備之間的交互是通過在主機和設(shè)備各自的DRAM之間傳輸數(shù)據(jù)來實現(xiàn)的，而這種數(shù)據(jù)傳輸是由設(shè)備的DMA引擎完成的，因此數(shù)據(jù)的傳輸并不會造成太多主機CPU開銷。
一個kernel中的線程是被分成具有相同大小的線程塊的，線程塊可以是一維、二維或者三維的，因此對應(yīng)的線程就可以具有一維、二維或者三維的索引。在一個線程塊中每個線程都具有一個一維的ID，這個ID和索引具有以下kernel關(guān)系：對于一維的線程塊，線程就等于其索引；對于大小為ID(Dx，Dy)的二維線程塊，索引為(x，y)的線程ID為(x+v Dx)；對于大小為(Dx，Dy，Dz)的三維線程塊，索引為(x，y，z)的線程ID為(x+y Dx+z Dx Dy)。
同一個線程塊中的線程之間可以通過同步操作來協(xié)同內(nèi)存訪問。當通過調(diào)用內(nèi)置函數(shù)_syncthreads()在kernel中建立同步點時，一個線程塊中的執(zhí)行到同步點的線程會被掛起直到這個線程塊中所有的線程都到達這個同步點。
為了線程之間能夠有效地協(xié)同工作，同步操作被設(shè)計成只需要一條指令就可以實現(xiàn)，并且同一個線程塊中的線程需要在同一個多核處理器上執(zhí)行。因此每個線程塊中全部線程的數(shù)量就受到一個處理器核上的存儲資源的限制。在當前的GPU上，一個線程塊可以包含最多512個線程。
雖然一個線程塊可以包含的線程數(shù)量有限制，但是一個kernel可以包括多個大小相同的線程塊，kernel中的線程數(shù)就等于每個塊中線程的數(shù)量乘以線程塊的數(shù)量。線程塊之間是獨立的，它們可以并行地執(zhí)行，也可以串行地順序執(zhí)行。這就允許線程塊在多個處理器核之間按照任何順序調(diào)度，從而使得開發(fā)具有靈活性和可擴展性。而且這樣線程塊的數(shù)量就可以根據(jù)待處理數(shù)據(jù)的大小決定，而不是由系統(tǒng)中多核處理器的個數(shù)決定，也就是說線程塊的數(shù)量可以大于多核處理器的數(shù)量。因此kernel中可以具有大量的線程塊，從而具有極高的線程數(shù)。但是由于線程塊之間執(zhí)行的不確定性，不同線程塊的線程之間不能進行同步操作。
3．1 算法設(shè)計
首先把待處理的大數(shù)據(jù)塊劃分為尺寸相同的多個小數(shù)據(jù)塊，然后使用標準的AES算法對各個小數(shù)據(jù)塊進行并行的運算，運算完成后把每個小數(shù)據(jù)塊的值按順序保存在一起，最后再把所有的輸出結(jié)果使用標準的AES算法來處理得到最后的結(jié)果，這樣就可以使用大量的線程來并行地對每個小數(shù)據(jù)塊進行運算。但是當數(shù)據(jù)分塊足夠多線程數(shù)很大時，就需要將線程劃分為多個線程塊。由于不同線程塊中的線程之間不能進行同步，所以設(shè)計了兩個kernel，第一個kernel的任務(wù)是使用大量并發(fā)執(zhí)行的線程對原始數(shù)據(jù)分成的多個小塊數(shù)據(jù)進行運算，并把結(jié)果按照順序保存在設(shè)備DKAM中。等第一個kernel執(zhí)行完成后，由主機啟動第二個kernel，這個kernel會根據(jù)主機提供的地址和數(shù)據(jù)大小對第一個kernel的計算得到的中間值進行運算，這一步只需用一個線程來執(zhí)行，由于中間值的大小遠遠小于原始數(shù)據(jù)，所以這一步的計算開銷是很小的。
3．2 算法優(yōu)化
GPU計算雖然高效，但是也有瓶頸。CPU代碼在調(diào)用GPU的kernel函數(shù)時，首先要將內(nèi)存中的數(shù)據(jù)塊讀到流中，處理完后，又要將流寫回內(nèi)存。
GPU和內(nèi)存的數(shù)據(jù)交換是一筆很大的開銷，因此從整體上減小這部分的開銷是優(yōu)化的關(guān)鍵。從GPU執(zhí)行的特點來看，每個線程都獨自從內(nèi)存中讀取一個分組長度的數(shù)據(jù)塊，加密完成后寫回到內(nèi)存中。這樣，每加密一個分組長度都要讀寫一次內(nèi)存，整體IO效率低。根據(jù)程序的局部性原理，如果一次讀入相鄰的多個分組，IO效率會大大提高。在前面的GPU程序中，我們是在一個線程里加密一個分組。現(xiàn)在我們一次讀取多個分組進行加密。這樣從整體上提高了IO效率。鑒于線程處理器還可以進行并行操作，我們還可以使用流數(shù)據(jù)類型，進一步提高并行度。
改進的算法如下：
brook：：Stream<int>*datastream；
datastream．read(Block[m][n])；
AESEncrypt_CPU_Simple(dtatastream)；
Datastream．write(Block[m][n])；
改進后，每個線程一次讀取n個相鄰的分組進行加密。
4 實驗設(shè)計
實驗采用的CPU是GeForce 9800 GTX+，軟件使用GUDA2．1，是在WmdowsXP操作系統(tǒng)下運行的。
CPU對AES算法的加速結(jié)果如圖1所示。從圖中可以看出，當數(shù)據(jù)量較小時(小于100kB)，GPU上的運行性能要低于CPU，這是因為GPU的特點是適合用作高密度數(shù)據(jù)的并行計算，而當數(shù)據(jù)量較小時并無法充分利用到GPU的計算資源，而且從主機向設(shè)備傳輸輸入數(shù)據(jù)和由設(shè)備向主機返回數(shù)據(jù)又會占用一定的開銷，因此對于小數(shù)據(jù)量的處理并不適合使用GPU。隨著數(shù)據(jù)量的增加，GPU運算的性能就會明顯高于CPU。當數(shù)據(jù)量大于1MB時，GPU具有將近兩倍的加速倍數(shù)，之后加速倍數(shù)就基本穩(wěn)定下來，達到飽和，這是因為當數(shù)據(jù)量已經(jīng)足夠多，充分利用了GPU的計算資源。由于GPU的計算能力遠遠高于它訪問設(shè)備內(nèi)存的帶寬以及主機與設(shè)備之間的數(shù)據(jù)傳輸帶寬，在應(yīng)用中這些數(shù)據(jù)傳輸?shù)拈_銷會成為限制GPU運算整體性能的瓶頸，需要對GPU進行優(yōu)化，才能充分開發(fā)出GPU的計算優(yōu)勢。
圖1 GPU對AES算法的加速效果
對實驗結(jié)果進行優(yōu)化。通過優(yōu)化，可以提高超過兩倍的加速效果，在數(shù)據(jù)量大時，優(yōu)化結(jié)果更為明顯，如圖2所示。
5 結(jié)論
本文介紹了在GPU上實現(xiàn)AES加密算法的方法。首先介紹了AES算法，然后對CUDA中的GPU結(jié)構(gòu)和CUDA編程模型進行了深入的研究。最后在GPU和CPU平臺上對設(shè)計進行了實驗對比，取得了理想的加速效果。其實在大多數(shù)應(yīng)用情況下，目前計算機顯卡配置的GPU運算潛能并沒有完全釋放出來，本文介紹的加密方法是GPU通用計算具體應(yīng)用的一個體現(xiàn)。雖然目前以CUDA為代表的GPU仍然存在精度不高，程序編寫限制較多的缺點，但隨著并行流處理概念的進一步發(fā)展，GPU通用計算技術(shù)將在各個領(lǐng)域發(fā)揮更大的作用。
下載文檔
