| 1 MuxTree结构模型的原理
MuxTree是一种新型的基于多路复用器基础上的SRAM FPGA的结构模型。由于MuxTree结构模型阵列能容易地配置成二叉判定图BDD [1]，而BDD又是逻辑函数的有效表示方法，所以MuxTree结构模型理论上可以实现所有的数字电路基本单元。MuxTree结构模型基本单元包括三个部分：可编程功能模块FU、可编程长距离连接模块SB和配置寄存器CREG。
可编程功能模块是由一个多路复用器实现的， D型触发器F用于实现时序功能，单元的输出是组合还是时序由配置信号S控制。在MuxTree基本单元中有两套独立的连接线路，一个是短距离连接线路（图中黑色的），另一个是长距离连接线路（图中灰色的）。可编程功能模块与连接模块的配置信号保存在配置寄存器中，整个电路的配置信号数据流决定电路的功能 [2]。
2 MuxTree结构的容错模型
MuxTree结构容错模型的设计流程主要是由自检测和重配置两个部分组成。它的设计原理是先通过自检测发现错误，然后重新布线使出错的 MuxTree单元停止工作，并将出错的MuxTree单元的配置信号重新配置到冗余的单元中。
2.1 MuxTree容错模型的自检测
容错系统首先是要实现自检测功能。这里自检测要求是能实现错误检测和错误定位，并且自检测逻辑电路要分散在MuxTree各个基本单元中。
对于可编程功能模块，由于它的规模比较小，所以可通过完整的备份电路进行测试。用两个相同的子电路，对它们的输出进行简单比较就能检测出故障。同时为了保证电路在修复后不会丢失检测到故障时所存储的信息，又引入了触发器的第三个副本和一个2-3的判决器。
对于配置寄存器，因为基本单元的配置在电路编程后就不变了，所以可以认为，保存在寄存器中的值，在正常运行中发生的任何改变是出现故障的结果。测试变量从左至右移入配置寄存器，如果没有故障，该变量组的头1到达寄存器的头H，而它的尾11将同时到达寄存器的尾部T，这时与门输出为1，异或门的输入由00 变为11，异或门输出0。如果检测到错误，异或门输出为1。
2.2 MuxTree容错模型的自修复
要使一个电路系统具有自修复的功能，通常都要求两种内建机制，即资源冗余和功能重配置。
所谓冗余就是当检测到错误时，要求有备份的单元来替代出错的单元。为了指定一组备用单元作为冗余，这里引进了一个可编程自复制机——细胞自动机[3]。这个自动机可以完成下面两项任务：把阵列划分成矩形方块；指定其中一列作为备用列。它可以通过修改备用列的疏密，来改变系统的自修复能力。在不用改变MuxTree基本单元的配置信号情况下，就可以使它从没有容错功能（没有备用列）到100%冗余度（一个活动列配一个备用列）。
就功能重配置而言，主要是如何利用这些冗余，将故障单元的信息转移到工作单元中去。这里提出的自修复机制，是通过用右边邻居单元替代故障单元，再对网络进行重配置来实现的。这个右边邻居单元本身的配置信号一直向右移位，直至到达一个备用单元。在信息移位完成后，故障单元对于网络就停止工作，也就是通过重新布线来避开故障单元。
3 容错全加器的设计和实现
下面将在MuxTree_SR（自修复MuxTree）阵列上设计一个具有容错功能的一位全加器。主要是用Xilinx Foundation工具实现原理的编辑和仿真。
3.1 容错全加器模型的建立
设计这个系统的第一步就是分析实现MuxTree_SR阵列所须基本单元的数目。一位全加器正常运行时的真值表如表1。通过真值表可得到如图2所示的全加器的两个输出 Cn+1和Sn 的二叉判定图BDD。经过化简后，原本需要14个单元的结构简化为10个单元的最简形式。由BDD图可以得到MuxTree各单元的配置信号和连接线路图如图3(a)(b)。因此，要实现一个具有自检测、自修复能力的全加器，需要用到5×2个活动单元和5个备用单元。
3.2 容错全加器的配置实现
容错全加器的配置可分为以下三个阶段：
3.2.1 细胞自动机分区阶段
将15个基本单元排列成5×3的阵列，其中前两列为活动的基本单元，后一列为备用列。由于有15个基本单元，细胞自动机隔板要完全将它们包含起来，需要6×4个细胞自动机模块。
3.2.2 寄存器测试阶段
在输入有效的配置信号数据流之前，要进行配置寄存器的测试。在状态机复位后，测试十六进制变量组18000001通过共用配置线，并行地移位进入所有的配置寄存器中，以检测是否存在故障。如果有故障，测试序列的头1无法到达寄存器的末端，产生一个错误检测信号。由于有效的配置信号还没有进入，所以在此阶段不用进行重配置，而只须简单地将单元变成DEAD，自动引发重新布线。
3.2.3 配置阶段
寄存器测试完成后，有效的配置信号从西南角入口点，通过共用配置线按照细胞自动机定义的传输路径进入每个块。当配置流遇到出错单元时，自动改变方向到右边邻居单元，右边邻居单元的配置再依次改变方向，直至到达相应的备用单元。
3.3 容错全加器的功能仿真
当活动单元配置完成后，电路就开始运行，全加器开始工作。如果电路在运行时检测到故障,那么将激活重构机制。重配置时钟生效，自修复机制开始启动，将出错单元的配置信号转到它右边的单元中去。一旦备用单元的配置信号充满，自修复完成，故障单元停止工作，自动重新布线。这时工作时钟重新启动，电路恢复工作。 由于故障单元中的触发器的内容是连接到配置寄存器上的，所以重配置过程中，把原触发器的内容也移到右边的基本单元中，因此，电路将在检测到故障时的状态起继 续工作。只要有足够的备用单元，就可以修复更多的故障，保证全加器正常工作。
4 结论
本文通过对一位容错加法器的设计和实现，探讨了基于SRAM FPGA的MuxTree模型结构容错系统的可行性。
因为MuxTree能容易地配置成BDD，所以从原理上来讲，能实现任何功能的容错电路，可以说具有通用性。同时，因为引入了细胞自动机来定义备用列，实现了动态冗余，提高了系统的可靠性。
由于是在阵列的所有单元间进行分配诊断和重构机制，所以硬件开销较大，不适合复杂应用。
参考文献：
[1] Akers S B. Binary decision diagrams[J]. IEEE Transactions on Computers, 1978, 6: 509-516.
[2] Prodan L, Mange D, Tempesti G.The embryonics project: Specifications of the MuxTree field programmable gate array, 1999.
[3] Tempesti G. A self-repairing multiplexer-Based FPGA inspired by biological processes. The Swiss Federal Institute of Technology, Lausanne, 1998.
|