一种基于人工免疫系统的FPGA容错方法

董暘暘，杨孟飞

(1.北京控制工程研究所，北京 100190;2.中国空间技术研究院，北京100194)

一种基于人工免疫系统的FPGA容错方法

董暘暘1，杨孟飞2

(1.北京控制工程研究所，北京 100190;2.中国空间技术研究院，北京100194)

通过对人工免疫系统容错性的分析和研究，提出了将人工免疫系统应用于硬件容错的4个条件.在此基础上设计了一种仿照人体细胞结构的新型FPGA可编程逻辑单元和一种基于人工免疫系统的容错方法.最后通过实验模拟故障的方法对该设计和容错方案的正确性和有效性进行了验证.

人工免疫系统;容错 ;FPGA

人工免疫系统(artificial immune system)是一类受免疫学原理启发和人体免疫系统机制而发展的各种人工范例的统称［1］.与人体免疫系统相同，人工免疫系统也具有自我学习，非我识别维持免疫对象稳定等功能.因而能被用于容错系统的设计.

人工免疫系统在容错领域中的应用主要集中在系统级和器件级两方面，并取得了一些成果.美国空军基于人工免疫系统设计了一套航空器健康管理系统用于对航空器的实时机动动作进行检查［2］，英国约克大学则利用人工免疫系统设计了一套FPGA容错系统，用于对有限状态机进行故障诊断［3］.因此通过对人工免疫系统在容错领域中的应用进行研究对于跟踪新技术，提升设计水平具有指导意义.

目前，对人工免疫系统的研究主要集中于如何提高故障检测效率［4］.由于受免疫算法本身效率和免疫对象与人工免疫系统之间适用性不足以及对依据生物学原理进行故障修复的研究缺乏使得人工免疫系统在容错领域的应用一直停留在故障检测阶段.

此外在硬件容错领域，由于现有硬件结构不适用于人工免疫系统，因此还没有一种实用的基于人工免疫系统的硬件容错方法.

本文以FPGA为容错对象，利用人工免疫系统探索一种新的容错方法.

1 人工免疫系统与容错

1.1 人工免疫系统结构

一般认为，人工免疫系统由一些人工免疫组件及其免疫算子构成，用以模拟人类免疫系统的自体构建、异体检测与识别、异体清除和系统修复等功能［7］.

一个完整的人工免疫系统的结构如图1所示，包括免疫对象、免疫算法和修复手段三个方面.

图1 人工免疫系统结构

免疫算法是人工免疫系统的核心，其主要功能是通过智能算法，实现对免疫对象状态或行为的监测和学习.

免疫对象是人工免疫系统监测和保护的对象，一般是一个系统或具体的器件.

修复手段是一组对免疫对象进行错误纠正、故障修复或屏蔽的方法.

将免疫系统和传统的容错系统相对比，可以发现免疫系统就是一个成功且有效的容错系统.免疫系统容错的基本思想是“识别-修复”(如图2所示)即通过不断监视机体的状态找出对机体造成影响的因素并将其清除以维持机体的正常工作.

图2 免疫容错流程

1.2 人工免疫系统用于硬件容错的条件

将人工免疫系统应用于硬件容错系统设计时硬件应满足以下几个条件以适应人工免疫系统的工作方式:

1)从可观测性看，人体细胞正常工作时在表面会有表征“自我”的信息，硬件电路在工作的时候也会通过电路状态产生表征电路工作状态的“自我”信息.

2)从可观测性看，当人体细胞受到抗原感染后表面特征会发生变化，同样当硬件电路发生故障后其状态也会发生与正常情况不同的变化.

3)从可修复性看，人体免疫系统会杀伤已被抗原感染的病变细胞，并由干细胞重新生成一个新的细胞以替代原病变细胞.人工免疫系统也应该能够修复发生错误的电路，使其恢复正常工作.

4)从系统结构看，人体是由大量细胞构成的集合体一样，硬件也是由大量电路构成的集合体.

当硬件和人工免疫系统均满足上述条件时就能构成一套基于人工免疫系统的硬件容错平台，该平台能够通过对免疫对象进行学习实现错误检测和故障修复.

2 基于人工免疫系统的FPGA容错方法

将硬件免疫系统中的免疫对象具体化为FPGA便可得到一套FPGA容错系统.该系统依照人体免疫系统中适应性免疫的发生和发展过程，对 FPGA工作状态进行检测，发现错误并进行修复.

2.1 FPGA容错系统结构

人工免疫系统在FPGA容错系统中主要实现人体免疫系统中B细胞、记忆T细胞和杀伤T细胞这三种细胞的功能，其结构和功能如图3所示.

图3 采用人工免疫系统的FPGA容错平台结构

其中，FPGA工作状态检测模块负责模拟人体B细胞抗原匹配和抗体产生功能.通过将当前FPGA工作状态位串和随机位串进行比对实现对FPGA工作状态的检测.模拟人体记忆T细胞的功能的是位串存储模块，该模块负责存储能检测电路工作状态的位串，以加快检测速度并提高检测效率.错误修复模块负责实现人体杀伤T细胞的功能，该模块负责在检测到FPGA发生故障后对故障FPGA进行错误修复，恢复FPGA的正常工作.这些模块中除位串生成和部分匹配检测在FPGA外由程序实现外其余部分都在FPGA内部实现.

人工免疫系统在FPGA容错系统中主要完成模式识别、错误检测和错误修复功能，其工作分为学习、错误检测、修复三个阶段.

2.1.1 学习阶段

在该阶段中需要保持被测系统的正常工作，以便人工免疫系统将电路状态作为“自我”进行学习，该过程主要由阴性选择算法(Negative Selection Algorithm-NSA)实现［8］.阴性选择算法产生大量的随机位串作为抗体，这些位串与本体抗原具有相同的长度和编码方式，阴性选择算法每生成一个随机位串，就相当于产生了一个能产生某种抗体的B细胞，这种抗体会与“自我”抗原进行部分匹配，以模拟人体免疫系统中抗原决定基匹配模式.如果阴性选择算法所产生的抗体与本体抗原相匹配则表明该B细胞没有通过考核将会被淘汰.反之，如果产生的抗体和本体抗原没有发生匹配则说明该B细胞通过了考核，其所产生的抗体字符串将会被存储起来，产生具有免疫记忆效应的记忆T细胞，而人工免疫系统则对被测系统产生了免疫耐受能力.在这一过程体现了人工免疫系统的智能性.

2.1.2 错误检测阶段

在该阶段，人工免疫系统会实时收集被测对象的工作状态并将其与存储在记忆T细胞中的抗体进行比对，一旦发现被测对象的当前状态和某个抗体匹配则意味着被测对象出现了故障，此时记忆T细胞就会向人工免疫系统中执行故障恢复任务的杀伤T细胞发出激活信号开启故障修复过程.

2.1.3 故障恢复阶段

一旦人工免疫系统检测到被测系统的故障便会激活负责进行故障修复的杀伤T细胞执行故障修复任务.杀伤T细胞将会按照设定的故障修复程序对出现故障的FPGA进行不同粒度和不同策略的修复，而修复所需要的时间和修复过程对FPGA正常工作的干扰则会时修复的粒度和策略而定.

2.2 适用于人工免疫系统的FPGA结构

为了能够更好地理解人工免疫系统如何作用于FPGA并实现对它的故障检测和修复，建立了如表1所示的FPGA结构和生物体的映射关系.

通过这一映射关系就可以用人体细胞的工作流程来描述描述FPGA的工作流程，如表2所示.

通过类比生物体细胞的工作流程可以看出FPGA从不具有用户设计的功能到被配置为具有用户设计功能的过程和生物体细胞的工作流程具有相似之处，使得人工免疫系统在FPGA容错领域的应用满足第二章所提出的4个条件.

表1 生物体结构和FPGA结构映射关系

表2 FPGA工作流程和人体细胞工作流程

但由于现有FPGA内部结构并没有针对容错设计进行优化，使得人工免疫系统无法实现对 FPGA故障的准确定位和修复.有鉴于此，本文提出一种基于查找表(Look Up Table-LUT)的新型FPGA可编程逻辑块(Configurable Logic Block-CLB)结构，该结构对于配置寄存器、LUT和基本单元中的寄存器被单粒子击中后发生翻转的故障［9］提供更精确的故障定位和修复能力.

2.3 FPGA可编程逻辑块设计

为了使FPGA在工作时能够反映出电路工作的现态和前态以供人工免疫系统对电路工作状态进行检查，对 FPGA中原有的 CLB结构进行改进，构成图4中所示的被称为“细胞(Cell)”的结构作为FPGA中的最小可编程单元.

该结构由基本单元(basic unit-BU)和配置寄存器构成.每个BU由一个查找表(LUT)、三个寄存器(register)和一个多路选择器(mux)构成，LUT和MUX均可配置.由于 LUT的输出存在三条延迟分别为0时钟周期、1时钟周期和2时钟周期的路径，因此两个BU可以被配置为具有同样功能但是输出延迟不同以便于人工免疫系统对FPGA中细胞的工作状态进行检测.

图4(a) FPGA中细胞内基本单元(BU)结构

图4(b) FPGA中细胞(cell)结构

2.3.1 FPGA中“细胞”的配置过程

针对FPGA中“细胞”结构的特点并参照生物体细胞的工作流程，FPGA中“细胞”的配置过程可分为以下几个阶段:

1)干细胞阶段:上电，配置寄存器中没有任何用户数据，“细胞”输出全部被封锁，不表现任何功能.

2)分化阶段:配置位流写入配置寄存器，默认情况下三个BU中的第一路会按用户设计被配置为组合逻辑或时序逻辑(用户设计)，第二路则会被配置为与用户设计具有相同功能但输出慢一个时钟周期的逻辑(用户设计的过去时)，第三路BU则会被配置为具有相同功能但是不输出结构的逻辑(用户逻辑的隐式).此时“细胞”具备反映自我当前和上一个时钟周期工作状态的能力.

3)分化结束阶段:用户配置位流由配置寄存器写入查找表，“细胞”完成配置.

4)工作阶段:“细胞”按照用户设计进行工作，同时外部系统以一定的速率对其中的配置寄存器进行刷新以保证配置数据正确性，该过程不影响FPGA的正常工作.

2.3.2 错误检测

当“细胞”完成配置后便开始按用户设计进行工作.此时“细胞”会有两路输出，一路是按照用户设计工作的组合逻辑或时序逻辑输出，称为用户逻辑，另一路是按照用户设计工作的比前一路输出慢一个时钟周期的输出，用以反映用户逻辑过去的工作状态，称为用户逻辑的过去时.人工免疫系统采集“细胞”的输入和输出并与“记忆T细胞”中的抗体进行比对实现错误检测.

2.3.3 错误修复

当FPGA中的“细胞”被单粒子击中发生翻转后，输出就会发生错误，这一过程类似于生物体细胞被病毒感染后发生细胞功能错误.当人工免疫系统检测到错误后便会激活“杀伤T细胞”执行错误修复功能，其具体步骤如下:

1)关闭“细胞”中第一路BU的输出，防止错误的继续传播.

2)将“细胞”中的第二路BU配置为用户逻辑.

3)将“细胞”中第三路BU配置为用户逻辑的过去时.

4)重新向第一路BU中的查找表写入配置数据，并将其配置为用户逻辑的隐式.

5)人工免疫系统再次检测“细胞”工作状态，若没有错误则保持其现有状态，如果故障依然存在则继续进行下面的操作.

6)将第三路BU配置为用户逻辑.

7)将第一路BU配置为用户逻辑的过去时.

8)将第二路BU配置为用户逻辑的隐式.

9)人工免疫系统重新执行检测若没有错误则保持“细胞”的现有状态，如果故障依然存在则清除当前出错“细胞”的功能，使其干细胞化并重新执行一次完整的配置过程.

3 实现与验证

为了验证上述适应于人工免疫系统的FPGA结构的可用性和正确性，在Altera公司的Cyclone II型FPGA上用VHDL语言对该系统进行了实现，其结构如图5所示.

图5 新型FPGA可编程逻辑单元框图

系统上电后 FPGA中的“细胞”被配置为实现“0-1”计数器功能，通过人工免疫系统对“细胞”的输入和输出进行耦合采样并将其作为表征“细胞”工作状态的特征进行学习和检测，结果如图6所示(从下往上分别对应“细胞”的输入、第三路输出、第二路输出和第一路输出)从图中可以看出“细胞”的三路输出间存在时延，正是因为这一时延使得“细胞”可以产生表征自己当前和过去状态的信息以利于人工免疫系统对其工作状态的检测.

图6 “细胞”输出波形

为了验证人工免疫系统对错误的诊断和修复能力，实验中模拟了因“细胞”内LUT被单粒子击中造成配置信息改变而发生的输出“stuck-at-0”和“stuck-at-1”故障(如图7、8所示)并验证了在这两种故障模式下人工免疫系统对“细胞”的修复功能.

图7 “细胞”发生stuck-at-0故障

图8 “细胞”发生stuck-at-1故障

当发生输出“stuck-at-0”故障时，由于人工免疫系统所采集到的“细胞”特征与学习得到的细胞正常工作特征相背，因此认定“细胞”出现故障，并按第三章中所给出的修复流程对故障“细胞”进行修复使其恢复正常工作，如图9所示.同理，当发生输出“stuck-at-1”故障时，人工免疫系统也能发现故障并对“细胞”进行修复.

图9 修复后恢复正常的“细胞”

4 结束语

本文通过对人体免疫系统中适应性免疫的研究，提出了将人工免疫系统应用到硬件容错设计中的4条原则.为让人工免疫系统在FPGA容错方面发挥最优效果，设计了一种仿照人体细胞工作原理的新型FPGA可编程逻辑单元，该单元能够模拟人体细胞通过输出反映内部工作状态，并能方便地进行故障修复.

在实验中将通过模拟FPGA发生故障的情况对人工免疫系统和新型FPGA可编程逻辑结构进行了验证.结果表明新型FPGA可编程逻辑结构设计正确，工作正常，人工免疫系统也发挥了对FPGA进行状态检测和错误修复的功能，实现了基于人工免疫系统的FPGA容错.

［1］ 莫宏伟，左兴权，毕晓君.人工免疫系统研究进展［J］.智能系统学报，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］ 莫宏伟，左兴权，人工免疫系统［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).