關(guān)鍵詞：MuxTree；全加器；容錯系統(tǒng)

中圖分類號：TP302 文獻(xiàn)標(biāo)識碼：A 文章編號：1003-353X(2003)05-0061-04

MuxTree是一種新型的基于多路復(fù)用器基礎(chǔ)上的SRAM FPGA的結(jié)構(gòu)模型。由于MuxTree結(jié)構(gòu)模型陣列能容易地配置成二叉判定圖BDD [1]，而BDD又是邏輯函數(shù)的有效表示方法，所以MuxTree結(jié)構(gòu)模型理論上可以實(shí)現(xiàn)所有的數(shù)字電路基本單元。MuxTree結(jié)構(gòu)模型基本單元包括三個部分：可編程功能模塊FU、可編程長距離連接模塊SB和配置寄存器CREG。

可編程功能模塊是由一個多路復(fù)用器實(shí)現(xiàn)的， D型觸發(fā)器F用于實(shí)現(xiàn)時序功能，單元的輸出是組合還是時序由配置信號S控制。在MuxTree基本單元中有兩套獨(dú)立的連接線路，一個是短距離連接線路（圖中黑色的），另一個是長距離連接線路（圖中灰色的）?？删幊坦δ苣K與連接模塊的配置信號保存在配置寄存器中，整個電路的配置信號數(shù)據(jù)流決定電路的功能 [2]。

2 MuxTree結(jié)構(gòu)的容錯模型

MuxTree結(jié)構(gòu)容錯模型的設(shè)計流程主要是由自檢測和重配置兩個部分組成。它的設(shè)計原理是先通過自檢測發(fā)現(xiàn)錯誤，然后重新布線使出錯的 MuxTree單元停止工作，并將出錯的MuxTree單元的配置信號重新配置到冗余的單元中。

2.1 MuxTree容錯模型的自檢測

容錯系統(tǒng)首先是要實(shí)現(xiàn)自檢測功能。這里自檢測要求是能實(shí)現(xiàn)錯誤檢測和錯誤定位，并且自檢測邏輯電路要分散在MuxTree各個基本單元中。

對于可編程功能模塊，由于它的規(guī)模比較小，所以可通過完整的備份電路進(jìn)行測試。用兩個相同的子電路，對它們的輸出進(jìn)行簡單比較就能檢測出故障。同時為了保證電路在修復(fù)后不會丟失檢測到故障時所存儲的信息，又引入了觸發(fā)器的第三個副本和一個2-3的判決器。

對于配置寄存器，因?yàn)榛締卧呐渲迷陔娐肪幊毯缶筒蛔兞耍钥梢哉J(rèn)為，保存在寄存器中的值，在正常運(yùn)行中發(fā)生的任何改變是出現(xiàn)故障的結(jié)果。測試變量從左至右移入配置寄存器，如果沒有故障，該變量組的頭1到達(dá)寄存器的頭H，而它的尾11將同時到達(dá)寄存器的尾部T，這時與門輸出為1，異或門的輸入由00 變?yōu)?1，異或門輸出0。如果檢測到錯誤，異或門輸出為1。

2.2 MuxTree容錯模型的自修復(fù)

要使一個電路系統(tǒng)具有自修復(fù)的功能，通常都要求兩種內(nèi)建機(jī)制，即資源冗余和功能重配置。

所謂冗余就是當(dāng)檢測到錯誤時，要求有備份的單元來替代出錯的單元。為了指定一組備用單元作為冗余，這里引進(jìn)了一個可編程自復(fù)制機(jī)——細(xì)胞自動機(jī)[3]。這個自動機(jī)可以完成下面兩項(xiàng)任務(wù)：把陣列劃分成矩形方塊；指定其中一列作為備用列。它可以通過修改備用列的疏密，來改變系統(tǒng)的自修復(fù)能力。在不用改變MuxTree基本單元的配置信號情況下，就可以使它從沒有容錯功能（沒有備用列）到100%冗余度（一個活動列配一個備用列）。

就功能重配置而言，主要是如何利用這些冗余，將故障單元的信息轉(zhuǎn)移到工作單元中去。這里提出的自修復(fù)機(jī)制，是通過用右邊鄰居單元替代故障單元，再對網(wǎng)絡(luò)進(jìn)行重配置來實(shí)現(xiàn)的。這個右邊鄰居單元本身的配置信號一直向右移位，直至到達(dá)一個備用單元。在信息移位完成后，故障單元對于網(wǎng)絡(luò)就停止工作，也就是通過重新布線來避開故障單元。

3 容錯全加器的設(shè)計和實(shí)現(xiàn)

下面將在MuxTree_SR（自修復(fù)MuxTree）陣列上設(shè)計一個具有容錯功能的一位全加器。主要是用Xilinx Foundation工具實(shí)現(xiàn)原理的編輯和仿真。

3.1 容錯全加器模型的建立

設(shè)計這個系統(tǒng)的步就是分析實(shí)現(xiàn)MuxTree_SR陣列所須基本單元的數(shù)目。一位全加器正常運(yùn)行時的真值表如表1。通過真值表可得到如圖2所示的全加器的兩個輸出 Cn+1和Sn 的二叉判定圖BDD。經(jīng)過化簡后，原本需要14個單元的結(jié)構(gòu)簡化為10個單元的簡形式。由BDD圖可以得到MuxTree各單元的配置信號和連接線路圖如圖3(a)(b)。因此，要實(shí)現(xiàn)一個具有自檢測、自修復(fù)能力的全加器，需要用到5×2個活動單元和5個備用單元。

3.2 容錯全加器的配置實(shí)現(xiàn)

容錯全加器的配置可分為以下三個階段：

3.2.1 細(xì)胞自動機(jī)分區(qū)階段

將15個基本單元排列成5×3的陣列，其中前兩列為活動的基本單元，后一列為備用列。由于有15個基本單元，細(xì)胞自動機(jī)隔板要完全將它們包含起來，需要6×4個細(xì)胞自動機(jī)模塊。

在輸入有效的配置信號數(shù)據(jù)流之前，要進(jìn)行配置寄存器的測試。在狀態(tài)機(jī)復(fù)位后，測試十六進(jìn)制變量組18000001通過共用配置線，并行地移位進(jìn)入所有的配置寄存器中，以檢測是否存在故障。如果有故障，測試序列的頭1無法到達(dá)寄存器的末端，產(chǎn)生一個錯誤檢測信號。由于有效的配置信號還沒有進(jìn)入，所以在此階段不用進(jìn)行重配置，而只須簡單地將單元變成DEAD，自動引發(fā)重新布線。

3.2.3 配置階段

寄存器測試完成后，有效的配置信號從西南角入口點(diǎn)，通過共用配置線按照細(xì)胞自動機(jī)定義的傳輸路徑進(jìn)入每個塊。當(dāng)配置流遇到出錯單元時，自動改變方向到右邊鄰居單元，右邊鄰居單元的配置再依次改變方向，直至到達(dá)相應(yīng)的備用單元。

4 結(jié)論

本文通過對一位容錯加法器的設(shè)計和實(shí)現(xiàn)，探討了基于SRAM FPGA的MuxTree模型結(jié)構(gòu)容錯系統(tǒng)的可行性。

因?yàn)镸uxTree能容易地配置成BDD，所以從原理上來講，能實(shí)現(xiàn)任何功能的容錯電路，可以說具有通用性。同時，因?yàn)橐肓思?xì)胞自動機(jī)來定義備用列，實(shí)現(xiàn)了動態(tài)冗余，提高了系統(tǒng)的可靠性。

參考文獻(xiàn)：

[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.