應用CUDA加速免疫算法——Jacket與Matlab實現

摘要：作為繼遺傳算法后新興的一種人工智能算法——免疫算法最近幾年在理論研究和工程應用方面得到了極大的關注和發展，但由于免疫算法本身機理的并行性使得其在通用CPU上進行測試和運行時效率低下，不利于評價算法的性能。通過通用并行計算架構CUDA使用GPU運行則更符合算法本身機理，大幅節省運行時間，降低硬件成本。

關鍵詞：免疫算法 CUDA GUP MATLAB jacket

1 人工免疫算法

人體具有著諸如胸腺、淋巴結、皮膚、血管細胞膜等在通常情況下能與外部有害物質（抗原）產生反應來保持生命體處于有利或正常狀態的機制，當然在某些情況下也會起到相反的作用。這一反應是一個復雜的自適應過程，能夠優化自身以更好的檢測抗原，并對接觸比較頻繁的抗原產生記憶，以提高下次對相同抗原的反應速度。而反應類型有三種：非特異性免疫、特異性免疫以及遺傳性免疫。根據其反應過程中的多樣性，人們探索出了不同的免疫理論以解決非生物環境下的問題，這就是人工免疫系統。

基本人工免疫算法過程如下：

①隨機產生一個人工免疫細胞集合作為初始群體。

②根據群體的收斂性或預設的迭代次數設定算法的終止條件。

③根據不同的抗原模式從①中生成的群體中抽取整個或隨機抽取若干個體構成子集。

④計算③中所抽取的子集每個個體與抗原之間的相似程度，即抗原親和度。根據抗原模式的數目返回③循環。

⑤根據預先設定的親和度閥值和④計算所得結果選取最佳親和度子集。

⑥調整⑤所得到的子集，主要依據為④的結果或者子集之間的親和度。

⑦更新⑥所調整的子集激活程度。若未達到算法終止條件，則回到②循環迭代。

目前免疫算法的多樣性尚未被完整認識，缺乏一個通用的數學框架，使得在評價算法性能時缺乏全面有效的依據。從以上基本算法模型中可以看出算法有很高的隨機性和復雜的遞歸迭代，對于串行執行指令的通用CPU構架，顯然得不到很高的執行效率。

2CUDA與GPU

目前在一般的個人計算機系統中，GPU扮演著協處理器的角色，將計算任務從CPU上的中央處理模式轉變為CPU 、GPU協同工作的處理模式。由于體系結構的不同，各自分工處理不同類型的計算任務。GPU相對CPU有著更高的并行度、浮點計算能力和內存位寬等優勢，目前GPU已經不再局限于以往的圖形處理專用，而向著通用目的計算（GPGPU）方向發展。

表1是在傳統SIMD(Single Instruction Multiple Data)模式下，Intel Core i7-960與NVIDIA GTX280性能比較圖。其中 BW：local DRAM bandwidth，SP：Single-Precision Floating Point，DP：Double-Precision Floating Point.

從該表中的數據來看，GPU的性能僅為CPU的2.5倍，這是由于在SIMD模式下，矢量寬度由硬件固定，數據需要打包成固定寬度的矢量進行處理，使得GTX280 GPU中高達240個SP以及支持數以百計的線程同時運行的能力受到限制，這無疑降低了運行效率。

Compute Unified Device Architecture CUDA，是NVIDIA公司為使其公司的NVIDIA GPU能夠完成復雜科學計算任務而推出的一種并行計算通用設備架構。與以往數據必須打包成矢量才能處理不同，CUDA框架使用了一個統一標準的渲染流水線，讓基于通用目的計算任務的程序能夠對片上任何一個ALU毫無例外的進行立即處理，使用SIMT（single Instruction Multiple thread）執行模式，以硬件細節的形式將數據寬度隱藏起來。支持數以千計的線程同時運行，這時，內存延遲對性能的影響就不再那么明顯了。CUDA極大的發揮的GPU的空閑資源，提高浮點運算效率。圖1是NVIDIA CUDA系統框架。

NVIDIA CUDA系統框架除了包含ISA指令集構架以及并行計算硬件引擎意外，還包含了一個CUDA集成開發環境，允許程序員使用C語言進行基于GPU的通用運算目的程序開發，簡化GPU編程難度，提高開發效率。

3 使用JACKET加速免疫算法在MATLAB中的運行

在最新的Matlab 2010b中包含支持GPU編程的Parallel Computing Toolbox，不過它及支持CUDA運算能力在1.3 以上的NVIDIA GPU，不能用于配置較低的計算機系統。

Jacket 是AccelerEyes公司開發的專用于MATLAB基于GPU的計算引擎，最新版本為1.7.1，其包含了高層的接口，完全屏蔽了底層硬件的復雜性，并支持所有支持CUDA GPU，降低了進行CUDA開發的門檻。

Jacket包含了一套運行于Matlab環境中優化并行計算的基礎函數庫。并支持Matlab 數據類型，可將任何存儲于Matlab CPU內存中的變量數據轉換為GPU上的數據類型，對以往的Matlab程序來說，只需更改數據類型，就能遷移到GPU上運行。本文以De Castro 和Von Zuben 的經典aiNET人工免疫網絡模型作為實驗對象。

其算法偽代碼見參考文獻，在此略去不表，僅給出使用jacket函數進行并行優化后的部分偽代碼。

選取親和度最高偽代碼如下：

Gfor每個yj∈ do

生成nc個yj的克隆；

將對nc個克隆進行變異后合并到集合中；

Gend

使用訓練模式zp與網絡中抗體yj之間的歐幾里得距離d（zp，yj）來衡量親和度，其中 為計算親和度后抽取具有最高親和度抗體的集合。Gfor ….Gend循環將循環體轉移至GPU上進行并行循環，極大的提高了運行效率。

4 結論

本文所使用的原始代碼為De Castro于2001年編制的關于AIS的DEMO，經過修改后成功在MATLAB 2010b中運行，并獲得較佳效果。運行環境為Microsoft windows 7 build 7601，Nvidia CUDA Tool-kit 3.2，AccelerEyes jacket 1.7.1 15天試用版。所使用的硬件為Intel core i5 M520，Gforce GT 325M，可見即使在較低配置的硬件環境下，也能使用CUDA通過GPU加速免疫算法的運行和調試，若想獲得更好的GPU ，CPU運行時間比，可采用不同的算法或者改變算法參數。

參考文獻：

[1]Leandro Nunes de Castro Fernando José Von Zuben， aiNet:An Artificial Immune Network for Data Analysis，http://www.dca.fee.unicamp.br/~lnunes 2001 [2] Jon Timmis ? Paul Andrews ? Emma， Hart On artificial immune systems and swarm intelligence. Springer Science+Business Media，LLC 2010 []Victor W Lee，Changkyu Kim，Jatin Chhugani Debunking the 100X GPU vs. CPU Myth: An Evaluation of Throughput Computing on CPU and GPU. ISCA’10， June 19-23，2010，Saint-Malo，France.

[3] 劉紹波，劉明貴，張國華，基于CUDA的加速MATLAB計算研究，計算機應用研究，第27卷第6期，2010年6月.

[4]譚彩鳳，馬安國，邢座程.基于CUDA平臺的遺傳算法并行實現研究，計算機工程與科學，2009年第31卷第A1期.

[5]Andries.P.Engelbrecht，Computational Intelligence:An Introduction，2E Wiley Publishing.Inc 2009.

[6]FunctionReferenceGuide，http://www.accelereyes.com/content/do

c/FunctionReferenceGuide.pdf，2011.

[7]http://www.nvidia.com/object/cuda_home_new.html.

[8]http://developer.nvidia.com/category/zone/cuda-zone.