一種基于人工免疫系統(tǒng)的FPGA容錯方法

董暘暘，楊孟飛

(1.北京控制工程研究所，北京 100190;2.中國空間技術研究院，北京100194)

一種基于人工免疫系統(tǒng)的FPGA容錯方法

董暘暘1，楊孟飛2

(1.北京控制工程研究所，北京 100190;2.中國空間技術研究院，北京100194)

通過對人工免疫系統(tǒng)容錯性的分析和研究，提出了將人工免疫系統(tǒng)應用于硬件容錯的4個條件.在此基礎上設計了一種仿照人體細胞結構的新型FPGA可編程邏輯單元和一種基于人工免疫系統(tǒng)的容錯方法.最后通過實驗模擬故障的方法對該設計和容錯方案的正確性和有效性進行了驗證.

人工免疫系統(tǒng);容錯 ;FPGA

人工免疫系統(tǒng)(artificial immune system)是一類受免疫學原理啟發(fā)和人體免疫系統(tǒng)機制而發(fā)展的各種人工范例的統(tǒng)稱［1］.與人體免疫系統(tǒng)相同，人工免疫系統(tǒng)也具有自我學習，非我識別維持免疫對象穩(wěn)定等功能.因而能被用于容錯系統(tǒng)的設計.

人工免疫系統(tǒng)在容錯領域中的應用主要集中在系統(tǒng)級和器件級兩方面，并取得了一些成果.美國空軍基于人工免疫系統(tǒng)設計了一套航空器健康管理系統(tǒng)用于對航空器的實時機動動作進行檢查［2］，英國約克大學則利用人工免疫系統(tǒng)設計了一套FPGA容錯系統(tǒng)，用于對有限狀態(tài)機進行故障診斷［3］.因此通過對人工免疫系統(tǒng)在容錯領域中的應用進行研究對于跟蹤新技術，提升設計水平具有指導意義.

目前，對人工免疫系統(tǒng)的研究主要集中于如何提高故障檢測效率［4］.由于受免疫算法本身效率和免疫對象與人工免疫系統(tǒng)之間適用性不足以及對依據(jù)生物學原理進行故障修復的研究缺乏使得人工免疫系統(tǒng)在容錯領域的應用一直停留在故障檢測階段.

此外在硬件容錯領域，由于現(xiàn)有硬件結構不適用于人工免疫系統(tǒng)，因此還沒有一種實用的基于人工免疫系統(tǒng)的硬件容錯方法.

本文以FPGA為容錯對象，利用人工免疫系統(tǒng)探索一種新的容錯方法.

1 人工免疫系統(tǒng)與容錯

1.1 人工免疫系統(tǒng)結構

一般認為，人工免疫系統(tǒng)由一些人工免疫組件及其免疫算子構成，用以模擬人類免疫系統(tǒng)的自體構建、異體檢測與識別、異體清除和系統(tǒng)修復等功能［7］.

一個完整的人工免疫系統(tǒng)的結構如圖1所示，包括免疫對象、免疫算法和修復手段三個方面.

圖1 人工免疫系統(tǒng)結構

免疫算法是人工免疫系統(tǒng)的核心，其主要功能是通過智能算法，實現(xiàn)對免疫對象狀態(tài)或行為的監(jiān)測和學習.

免疫對象是人工免疫系統(tǒng)監(jiān)測和保護的對象，一般是一個系統(tǒng)或具體的器件.

修復手段是一組對免疫對象進行錯誤糾正、故障修復或屏蔽的方法.

將免疫系統(tǒng)和傳統(tǒng)的容錯系統(tǒng)相對比，可以發(fā)現(xiàn)免疫系統(tǒng)就是一個成功且有效的容錯系統(tǒng).免疫系統(tǒng)容錯的基本思想是“識別-修復”(如圖2所示)即通過不斷監(jiān)視機體的狀態(tài)找出對機體造成影響的因素并將其清除以維持機體的正常工作.

圖2 免疫容錯流程

1.2 人工免疫系統(tǒng)用于硬件容錯的條件

將人工免疫系統(tǒng)應用于硬件容錯系統(tǒng)設計時硬件應滿足以下幾個條件以適應人工免疫系統(tǒng)的工作方式:

1)從可觀測性看，人體細胞正常工作時在表面會有表征“自我”的信息，硬件電路在工作的時候也會通過電路狀態(tài)產(chǎn)生表征電路工作狀態(tài)的“自我”信息.

2)從可觀測性看，當人體細胞受到抗原感染后表面特征會發(fā)生變化，同樣當硬件電路發(fā)生故障后其狀態(tài)也會發(fā)生與正常情況不同的變化.

3)從可修復性看，人體免疫系統(tǒng)會殺傷已被抗原感染的病變細胞，并由干細胞重新生成一個新的細胞以替代原病變細胞.人工免疫系統(tǒng)也應該能夠修復發(fā)生錯誤的電路，使其恢復正常工作.

4)從系統(tǒng)結構看，人體是由大量細胞構成的集合體一樣，硬件也是由大量電路構成的集合體.

當硬件和人工免疫系統(tǒng)均滿足上述條件時就能構成一套基于人工免疫系統(tǒng)的硬件容錯平臺，該平臺能夠通過對免疫對象進行學習實現(xiàn)錯誤檢測和故障修復.

2 基于人工免疫系統(tǒng)的FPGA容錯方法

將硬件免疫系統(tǒng)中的免疫對象具體化為FPGA便可得到一套FPGA容錯系統(tǒng).該系統(tǒng)依照人體免疫系統(tǒng)中適應性免疫的發(fā)生和發(fā)展過程，對 FPGA工作狀態(tài)進行檢測，發(fā)現(xiàn)錯誤并進行修復.

2.1 FPGA容錯系統(tǒng)結構

人工免疫系統(tǒng)在FPGA容錯系統(tǒng)中主要實現(xiàn)人體免疫系統(tǒng)中B細胞、記憶T細胞和殺傷T細胞這三種細胞的功能，其結構和功能如圖3所示.

圖3 采用人工免疫系統(tǒng)的FPGA容錯平臺結構

其中，F(xiàn)PGA工作狀態(tài)檢測模塊負責模擬人體B細胞抗原匹配和抗體產(chǎn)生功能.通過將當前FPGA工作狀態(tài)位串和隨機位串進行比對實現(xiàn)對FPGA工作狀態(tài)的檢測.模擬人體記憶T細胞的功能的是位串存儲模塊，該模塊負責存儲能檢測電路工作狀態(tài)的位串，以加快檢測速度并提高檢測效率.錯誤修復模塊負責實現(xiàn)人體殺傷T細胞的功能，該模塊負責在檢測到FPGA發(fā)生故障后對故障FPGA進行錯誤修復，恢復FPGA的正常工作.這些模塊中除位串生成和部分匹配檢測在FPGA外由程序實現(xiàn)外其余部分都在FPGA內部實現(xiàn).

人工免疫系統(tǒng)在FPGA容錯系統(tǒng)中主要完成模式識別、錯誤檢測和錯誤修復功能，其工作分為學習、錯誤檢測、修復三個階段.

2.1.1 學習階段

在該階段中需要保持被測系統(tǒng)的正常工作，以便人工免疫系統(tǒng)將電路狀態(tài)作為“自我”進行學習，該過程主要由陰性選擇算法(Negative Selection Algorithm-NSA)實現(xiàn)［8］.陰性選擇算法產(chǎn)生大量的隨機位串作為抗體，這些位串與本體抗原具有相同的長度和編碼方式，陰性選擇算法每生成一個隨機位串，就相當于產(chǎn)生了一個能產(chǎn)生某種抗體的B細胞，這種抗體會與“自我”抗原進行部分匹配，以模擬人體免疫系統(tǒng)中抗原決定基匹配模式.如果陰性選擇算法所產(chǎn)生的抗體與本體抗原相匹配則表明該B細胞沒有通過考核將會被淘汰.反之，如果產(chǎn)生的抗體和本體抗原沒有發(fā)生匹配則說明該B細胞通過了考核，其所產(chǎn)生的抗體字符串將會被存儲起來，產(chǎn)生具有免疫記憶效應的記憶T細胞，而人工免疫系統(tǒng)則對被測系統(tǒng)產(chǎn)生了免疫耐受能力.在這一過程體現(xiàn)了人工免疫系統(tǒng)的智能性.

2.1.2 錯誤檢測階段

在該階段，人工免疫系統(tǒng)會實時收集被測對象的工作狀態(tài)并將其與存儲在記憶T細胞中的抗體進行比對，一旦發(fā)現(xiàn)被測對象的當前狀態(tài)和某個抗體匹配則意味著被測對象出現(xiàn)了故障，此時記憶T細胞就會向人工免疫系統(tǒng)中執(zhí)行故障恢復任務的殺傷T細胞發(fā)出激活信號開啟故障修復過程.

2.1.3 故障恢復階段

一旦人工免疫系統(tǒng)檢測到被測系統(tǒng)的故障便會激活負責進行故障修復的殺傷T細胞執(zhí)行故障修復任務.殺傷T細胞將會按照設定的故障修復程序對出現(xiàn)故障的FPGA進行不同粒度和不同策略的修復，而修復所需要的時間和修復過程對FPGA正常工作的干擾則會時修復的粒度和策略而定.

2.2 適用于人工免疫系統(tǒng)的FPGA結構

為了能夠更好地理解人工免疫系統(tǒng)如何作用于FPGA并實現(xiàn)對它的故障檢測和修復，建立了如表1所示的FPGA結構和生物體的映射關系.

通過這一映射關系就可以用人體細胞的工作流程來描述描述FPGA的工作流程，如表2所示.

通過類比生物體細胞的工作流程可以看出FPGA從不具有用戶設計的功能到被配置為具有用戶設計功能的過程和生物體細胞的工作流程具有相似之處，使得人工免疫系統(tǒng)在FPGA容錯領域的應用滿足第二章所提出的4個條件.

表1 生物體結構和FPGA結構映射關系

表2 FPGA工作流程和人體細胞工作流程

但由于現(xiàn)有FPGA內部結構并沒有針對容錯設計進行優(yōu)化，使得人工免疫系統(tǒng)無法實現(xiàn)對 FPGA故障的準確定位和修復.有鑒于此，本文提出一種基于查找表(Look Up Table-LUT)的新型FPGA可編程邏輯塊(Configurable Logic Block-CLB)結構，該結構對于配置寄存器、LUT和基本單元中的寄存器被單粒子擊中后發(fā)生翻轉的故障［9］提供更精確的故障定位和修復能力.

2.3 FPGA可編程邏輯塊設計

為了使FPGA在工作時能夠反映出電路工作的現(xiàn)態(tài)和前態(tài)以供人工免疫系統(tǒng)對電路工作狀態(tài)進行檢查，對 FPGA中原有的 CLB結構進行改進，構成圖4中所示的被稱為“細胞(Cell)”的結構作為FPGA中的最小可編程單元.

該結構由基本單元(basic unit-BU)和配置寄存器構成.每個BU由一個查找表(LUT)、三個寄存器(register)和一個多路選擇器(mux)構成，LUT和MUX均可配置.由于 LUT的輸出存在三條延遲分別為0時鐘周期、1時鐘周期和2時鐘周期的路徑，因此兩個BU可以被配置為具有同樣功能但是輸出延遲不同以便于人工免疫系統(tǒng)對FPGA中細胞的工作狀態(tài)進行檢測.

圖4(a) FPGA中細胞內基本單元(BU)結構

圖4(b) FPGA中細胞(cell)結構

2.3.1 FPGA中“細胞”的配置過程

針對FPGA中“細胞”結構的特點并參照生物體細胞的工作流程，F(xiàn)PGA中“細胞”的配置過程可分為以下幾個階段:

1)干細胞階段:上電，配置寄存器中沒有任何用戶數(shù)據(jù)，“細胞”輸出全部被封鎖，不表現(xiàn)任何功能.

2)分化階段:配置位流寫入配置寄存器，默認情況下三個BU中的第一路會按用戶設計被配置為組合邏輯或時序邏輯(用戶設計)，第二路則會被配置為與用戶設計具有相同功能但輸出慢一個時鐘周期的邏輯(用戶設計的過去時)，第三路BU則會被配置為具有相同功能但是不輸出結構的邏輯(用戶邏輯的隱式).此時“細胞”具備反映自我當前和上一個時鐘周期工作狀態(tài)的能力.

3)分化結束階段:用戶配置位流由配置寄存器寫入查找表，“細胞”完成配置.

4)工作階段:“細胞”按照用戶設計進行工作，同時外部系統(tǒng)以一定的速率對其中的配置寄存器進行刷新以保證配置數(shù)據(jù)正確性，該過程不影響FPGA的正常工作.

2.3.2 錯誤檢測

當“細胞”完成配置后便開始按用戶設計進行工作.此時“細胞”會有兩路輸出，一路是按照用戶設計工作的組合邏輯或時序邏輯輸出，稱為用戶邏輯，另一路是按照用戶設計工作的比前一路輸出慢一個時鐘周期的輸出，用以反映用戶邏輯過去的工作狀態(tài)，稱為用戶邏輯的過去時.人工免疫系統(tǒng)采集“細胞”的輸入和輸出并與“記憶T細胞”中的抗體進行比對實現(xiàn)錯誤檢測.

2.3.3 錯誤修復

當FPGA中的“細胞”被單粒子擊中發(fā)生翻轉后，輸出就會發(fā)生錯誤，這一過程類似于生物體細胞被病毒感染后發(fā)生細胞功能錯誤.當人工免疫系統(tǒng)檢測到錯誤后便會激活“殺傷T細胞”執(zhí)行錯誤修復功能，其具體步驟如下:

1)關閉“細胞”中第一路BU的輸出，防止錯誤的繼續(xù)傳播.

2)將“細胞”中的第二路BU配置為用戶邏輯.

3)將“細胞”中第三路BU配置為用戶邏輯的過去時.

4)重新向第一路BU中的查找表寫入配置數(shù)據(jù)，并將其配置為用戶邏輯的隱式.

5)人工免疫系統(tǒng)再次檢測“細胞”工作狀態(tài)，若沒有錯誤則保持其現(xiàn)有狀態(tài)，如果故障依然存在則繼續(xù)進行下面的操作.

6)將第三路BU配置為用戶邏輯.

7)將第一路BU配置為用戶邏輯的過去時.

8)將第二路BU配置為用戶邏輯的隱式.

9)人工免疫系統(tǒng)重新執(zhí)行檢測若沒有錯誤則保持“細胞”的現(xiàn)有狀態(tài)，如果故障依然存在則清除當前出錯“細胞”的功能，使其干細胞化并重新執(zhí)行一次完整的配置過程.

3 實現(xiàn)與驗證

為了驗證上述適應于人工免疫系統(tǒng)的FPGA結構的可用性和正確性，在Altera公司的Cyclone II型FPGA上用VHDL語言對該系統(tǒng)進行了實現(xiàn)，其結構如圖5所示.

圖5 新型FPGA可編程邏輯單元框圖

系統(tǒng)上電后 FPGA中的“細胞”被配置為實現(xiàn)“0-1”計數(shù)器功能，通過人工免疫系統(tǒng)對“細胞”的輸入和輸出進行耦合采樣并將其作為表征“細胞”工作狀態(tài)的特征進行學習和檢測，結果如圖6所示(從下往上分別對應“細胞”的輸入、第三路輸出、第二路輸出和第一路輸出)從圖中可以看出“細胞”的三路輸出間存在時延，正是因為這一時延使得“細胞”可以產(chǎn)生表征自己當前和過去狀態(tài)的信息以利于人工免疫系統(tǒng)對其工作狀態(tài)的檢測.

圖6 “細胞”輸出波形

為了驗證人工免疫系統(tǒng)對錯誤的診斷和修復能力，實驗中模擬了因“細胞”內LUT被單粒子擊中造成配置信息改變而發(fā)生的輸出“stuck-at-0”和“stuck-at-1”故障(如圖7、8所示)并驗證了在這兩種故障模式下人工免疫系統(tǒng)對“細胞”的修復功能.

圖7 “細胞”發(fā)生stuck-at-0故障

圖8 “細胞”發(fā)生stuck-at-1故障

當發(fā)生輸出“stuck-at-0”故障時，由于人工免疫系統(tǒng)所采集到的“細胞”特征與學習得到的細胞正常工作特征相背，因此認定“細胞”出現(xiàn)故障，并按第三章中所給出的修復流程對故障“細胞”進行修復使其恢復正常工作，如圖9所示.同理，當發(fā)生輸出“stuck-at-1”故障時，人工免疫系統(tǒng)也能發(fā)現(xiàn)故障并對“細胞”進行修復.

圖9 修復后恢復正常的“細胞”

4 結束語

本文通過對人體免疫系統(tǒng)中適應性免疫的研究，提出了將人工免疫系統(tǒng)應用到硬件容錯設計中的4條原則.為讓人工免疫系統(tǒng)在FPGA容錯方面發(fā)揮最優(yōu)效果，設計了一種仿照人體細胞工作原理的新型FPGA可編程邏輯單元，該單元能夠模擬人體細胞通過輸出反映內部工作狀態(tài)，并能方便地進行故障修復.

在實驗中將通過模擬FPGA發(fā)生故障的情況對人工免疫系統(tǒng)和新型FPGA可編程邏輯結構進行了驗證.結果表明新型FPGA可編程邏輯結構設計正確，工作正常，人工免疫系統(tǒng)也發(fā)揮了對FPGA進行狀態(tài)檢測和錯誤修復的功能，實現(xiàn)了基于人工免疫系統(tǒng)的FPGA容錯.

［1］ 莫宏偉，左興權，畢曉君.人工免疫系統(tǒng)研究進展［J］.智能系統(tǒng)學報，2009， 4(1):21-29

［2］ Krishna K K.Artificial immune system approaches for aerospace applications［R］.The 41stAIAA Aerospace Sciences Meetingamp;Exhibit，Nevada USA，2003

［3］ Bradley D W，Tyrrell A M.Immunotronics-novel finitestate-machine architectures with built-in self-test using self-nonself differentiation ［J］.IEEE Transactions on Evolutionary Computation，2002，6(3):227-238

［ 4 ］ Zhao P，Zhang L，Mu X D，et al.A matrix negative selection algorithm for anomaly detection ［C］.IEEE Congress on Evolutionary Computation，Washington， DC，USA，July 22-24， 2008

［5］ Tian X， Yang H D，Deng F Q.A novel artificial immune network algorithm［C］.The 23rdInternational Conference on Machine Learning and Cybernetics(ICML)，Pittsburgh，USA，June 25-29，2006

［ 6 ］ Erhan A，Mehmet K，Ilhan A.Artificial immune inspired fault detection algorithm based on fuzzy clustering and genetic algorithm methods［C］.IEEE International Conference on Computational Intelligence for Measurement Systems and Applications(CISMA)，Istanbul，Turkey，July 14-16，2008

［7］ 莫宏偉，左興權，人工免疫系統(tǒng)［M］.北京:科學出版社，2009.

［8］ Forrest S，Perelson A， Allen L， et al.Self-nonself discrimination in a computer［C］.IEEE Computer Society Symposium on Research in Security and Privacy，Oakland，USA，May 16-18，1994

［9］ Violante M，Ceschia M，Sonza R M，et al.Analyzing SEU effects is SRAM-based FPGAs［C］.The 9thIEEE On-Line Testing Symposium(IOLTS)， Koss Island，Greece，July 7-9，2003

An Artificial Immune System-Based Method for Fau lt-Tolerant FPGA

DONG Yangyang1，YANG Mengfei2
(1.Beijing Institute of Control Engineering，Beijing 100190，China;2.China Academy of Space Technology， Beijing 100194， China)

The fault-tolerance capability of an artificial immune system is analyzed and researched，and four conditions for the artificial immune system used for hardware fault-tolerant are presented.A new human cell based FPGA configurable logic block architecture and an artificial immune system based fault tolerant method are designed.Finally fault simulations demonstrate that the design and the fault-tolerant scheme are valid and effective.

artificial immune system;fault tolerant;FPGA

V4

A

1674-1579(2011)02-0054-06

10.3969/j.issn.1674-1579.2011.02.010

2011-01-23

董暘暘(1985-)，男，四川人，碩士研究生，研究方向為計算機應用和空間容錯技術 (e-mail:brent.dyy@gmail.com).