容錯(cuò)系統(tǒng)中的自校驗(yàn)技術(shù)及實(shí)現(xiàn)方法
摘要:闡述了自校驗(yàn)技術(shù)在容錯(cuò)系統(tǒng)中的作用,給出了自校驗(yàn)網(wǎng)絡(luò)實(shí)現(xiàn)原理及實(shí)現(xiàn)方法,指出用VHDL語(yǔ)言結(jié)合FPGA/CPLD是實(shí)現(xiàn)大規(guī)模自校驗(yàn)網(wǎng)絡(luò)的有效途徑。
關(guān)鍵詞:容錯(cuò)自校驗(yàn)完全自校驗(yàn)VHDLFPGA/CPLD
容錯(cuò)是容忍錯(cuò)誤的簡(jiǎn)稱,容錯(cuò)系統(tǒng)是指在發(fā)生硬件故障或存在軟件錯(cuò)誤的情況下,仍能繼續(xù)正確完成指定任務(wù)的系統(tǒng)。設(shè)計(jì)與分析容錯(cuò)系統(tǒng)的各種技術(shù)稱為容錯(cuò)技術(shù)。有關(guān)計(jì)算機(jī)容錯(cuò)技術(shù)的各種理論及研究已經(jīng)發(fā)展成為計(jì)算機(jī)學(xué)科的一個(gè)重要分支,稱為容錯(cuò)計(jì)算(Fault-tolerantComputing)。設(shè)計(jì)容錯(cuò)系統(tǒng)的指導(dǎo)思想是:系統(tǒng)發(fā)生故障時(shí)能自動(dòng)檢出并使系統(tǒng)自動(dòng)恢復(fù)正常運(yùn)行。
為保證系統(tǒng)具有高可靠、長(zhǎng)壽命和響應(yīng)迅速,必須采用容錯(cuò)技術(shù)。從功能上講,一個(gè)容錯(cuò)系統(tǒng)可用圖1所示框圖來(lái)描述,系統(tǒng)模塊可由若干個(gè)功能相同的子模塊并聯(lián)組成,故障檢測(cè)模塊對(duì)系統(tǒng)模塊的功能進(jìn)行檢測(cè),檢測(cè)到故障后由故障處理模塊對(duì)系統(tǒng)模塊進(jìn)行重新配置,使系統(tǒng)在部分模塊失效的情況下,仍能輸出正確結(jié)果。在這個(gè)系統(tǒng)中,故障檢測(cè)模塊和故障處理模塊起著至關(guān)重要的作用,它們往往是系統(tǒng)的薄弱點(diǎn)。因此,容錯(cuò)系統(tǒng)要有高的可靠性必須保證故障檢測(cè)和處理模塊的可靠性,故障檢測(cè)系統(tǒng)不僅要檢測(cè)系統(tǒng)模塊的故障,而且還要能夠檢測(cè)自身的故障,使故障處理模塊得以正確處理所發(fā)生的故障。
自校驗(yàn)技術(shù)是用于故障快速檢測(cè)的一種有效手段,特別是具有完全自校驗(yàn)性質(zhì)的自校驗(yàn)裝置,它不僅能及時(shí)檢出系統(tǒng)模塊的差錯(cuò),還能檢測(cè)出自身的差錯(cuò)。在容錯(cuò)系統(tǒng)設(shè)計(jì)中,將自校驗(yàn)網(wǎng)絡(luò)置于系統(tǒng)中,可大大提高系統(tǒng)對(duì)差錯(cuò)的反應(yīng)能力,使差錯(cuò)潛伏期縮短,有效地防止錯(cuò)誤傳播。
1自校驗(yàn)網(wǎng)絡(luò)定義
一個(gè)容錯(cuò)系統(tǒng),其所有可能的輸出值組成的集合U(稱輸出空間)由S和U-S兩部分組成。當(dāng)系統(tǒng)中無(wú)故障時(shí),系統(tǒng)輸出S中的元素,一旦系統(tǒng)發(fā)生故障則輸出U-S中的元素。
如果一個(gè)電路的正常輸出集S是一個(gè)檢錯(cuò)碼集,則該電路稱為自校驗(yàn)電路。在無(wú)故障發(fā)生的情況下,自校驗(yàn)電路輸出碼向量;當(dāng)預(yù)定故障發(fā)生時(shí),則輸出非碼向量。連接在自校驗(yàn)電路輸出端的校驗(yàn)器監(jiān)督電路的輸出,當(dāng)非碼向量出現(xiàn)時(shí),校驗(yàn)器給出差錯(cuò)指示。自校驗(yàn)電路與校驗(yàn)器一起構(gòu)成了自校驗(yàn)網(wǎng)絡(luò),其結(jié)構(gòu)如圖2所示。
下面我們給出自校驗(yàn)網(wǎng)絡(luò)的幾個(gè)概念,設(shè)S(X)是輸入向量空間,
是合法輸入向量空間,
是非法輸入向量空間,S(F)是輸出向量空間,
是合法輸出向量空間,
是非法輸出向量空間,
是組合邏輯網(wǎng)絡(luò)所考慮的單故障集,網(wǎng)絡(luò)的所有輸入取自其合法輸入集。
定義1:組合邏輯網(wǎng)絡(luò)對(duì)
是自測(cè)試的(簡(jiǎn)稱ST),若:對(duì)任意故障
存在
,使網(wǎng)絡(luò)輸出
。
該定義是說(shuō)對(duì)給定單故障集中的任何一個(gè)故障,總存在一個(gè)合法輸入,它將導(dǎo)致組合邏輯網(wǎng)絡(luò)產(chǎn)生非法輸出,即用該輸入可檢測(cè)此故障。
定義2:組合邏輯網(wǎng)絡(luò)對(duì)
是故障保險(xiǎn)的(簡(jiǎn)稱FSE),若:對(duì)任意故障
存在
使網(wǎng)絡(luò)輸出
,或者
,其中G(X)是網(wǎng)絡(luò)的正確輸出。
該定義是說(shuō)在合法輸入條件下,對(duì)給定單故障集中的任何一個(gè)故障,組合邏輯網(wǎng)絡(luò)將給出一個(gè)合法輸出或一個(gè)非法輸出,但不會(huì)給出同該合法輸入不相對(duì)應(yīng)的另一個(gè)合法輸出。
定義3:組合邏輯網(wǎng)絡(luò)對(duì)
是完全自校驗(yàn)的,若它對(duì)
是自測(cè)試的和故障保險(xiǎn)的。
對(duì)給定單故障集中的任何一個(gè)故障,完全自校驗(yàn)的組合邏輯網(wǎng)絡(luò)在合法輸入的情況下,或者產(chǎn)生一個(gè)合法輸出,或者產(chǎn)生一個(gè)非法輸出,且后者在故障存在期間是必然要出現(xiàn)的。這就使得網(wǎng)絡(luò)在不產(chǎn)生不正確合法輸出的同時(shí),能并發(fā)檢測(cè)
中的所有故障,這也正是在線測(cè)試對(duì)差錯(cuò)檢測(cè)及時(shí)性的要求。
若采用檢錯(cuò)編碼技術(shù)實(shí)現(xiàn)自校驗(yàn)邏輯網(wǎng)絡(luò)時(shí),校驗(yàn)器的任務(wù)是用來(lái)檢查功能模塊輸出碼字的有效性,它能區(qū)分功能模塊輸出是否合法,這種特性被稱為碼分離特性,其定義如下。
定義4:一個(gè)邏輯網(wǎng)絡(luò)具有碼分離特性,若滿足:
(1)任給
,有
(合法輸入映射為合法輸出)
(2)任給
,有
(非法輸入映射為非法輸出)
定義5:一個(gè)邏輯網(wǎng)絡(luò)是完全自校驗(yàn)器,若它具有完全自校驗(yàn)及碼分離特性。
設(shè)組合邏輯網(wǎng)絡(luò)正確輸入矢量為
,則矢量空間
稱作錯(cuò)誤輸入空間,記作
;空間
被稱作非法及錯(cuò)誤輸入空間,記作
。由正確輸入空間
經(jīng)電路G可在S(F)中產(chǎn)生一個(gè)子空間,這個(gè)子空間稱為正確輸出空間,記為
。同樣,對(duì)于合法輸入
,由組合邏輯網(wǎng)絡(luò)可映射為合法輸出空間
它也是輸出矢量空間S(F)的子集。同樣,空間
被稱作錯(cuò)誤輸出空間,記作
;空間
被稱為非法及錯(cuò)誤輸出空間,表示為
。上述輸出之間有如下關(guān)系:
由上面集合之間的關(guān)系我們可以看出,對(duì)于無(wú)故障組合網(wǎng)絡(luò)的正確輸入,其輸出應(yīng)落入正確輸出空間
中。通過(guò)對(duì)網(wǎng)絡(luò)的輸出可部分判定系統(tǒng)工作是否正常(無(wú)法判斷某些故障)。當(dāng)網(wǎng)絡(luò)發(fā)生故障時(shí),可分成以下幾種情況:①非法及錯(cuò)誤輸入被映射成
;②輸入
被映射成為
;③
映入
但已不是正確的映射關(guān)系,也就是說(shuō)輸入輸出關(guān)系發(fā)生了變化。對(duì)于一個(gè)高可靠容錯(cuò)系統(tǒng)來(lái)說(shuō),必須能夠以比較高的故障覆蓋率來(lái)檢測(cè)出以上三類差錯(cuò)(最好在一拍內(nèi)檢出),使系統(tǒng)及時(shí)采取措施,隔離故障,將其影響減小到最低限度。在三類錯(cuò)誤中,第①類和第②類與第③類相比要好檢測(cè)一些,高效檢測(cè)第③類錯(cuò)誤是提高系統(tǒng)故障覆蓋率的關(guān)鍵,只有設(shè)計(jì)出對(duì)以上三類錯(cuò)誤檢出率均較高的檢錯(cuò)系統(tǒng),才能保證系統(tǒng)有較高的可靠性。
2自校驗(yàn)網(wǎng)絡(luò)的結(jié)構(gòu)
自校驗(yàn)網(wǎng)絡(luò)具有在無(wú)任何外加激勵(lì)的情況下能自動(dòng)檢測(cè)其內(nèi)部是否存在故障,這些故障或是永久性的或是暫時(shí)性的。設(shè)計(jì)自校驗(yàn)網(wǎng)絡(luò)的主要技術(shù)有檢錯(cuò)編碼技術(shù),基于自對(duì)偶函數(shù)的交替邏輯技術(shù)(交織邏輯技術(shù)),基于對(duì)偶函數(shù)的互補(bǔ)邏輯技術(shù),還有基于多值邏輯的實(shí)現(xiàn)方法,下面我們主要討論一些實(shí)用的實(shí)現(xiàn)方法。
2.1雙軌碼校驗(yàn)器
雙軌碼校驗(yàn)器的原理圖如圖3所示。
輸入矢量為
,其中
,(i=1,2),輸出矢量為
且滿足:
若
且校驗(yàn)器無(wú)故障。
利用雙軌碼校驗(yàn)器的上述特點(diǎn),設(shè)計(jì)一對(duì)偶組合邏輯網(wǎng)絡(luò),使其輸出向量
和
恰好反相,將
和
加到雙軌碼校驗(yàn)器輸入端,根據(jù)
就可以判定系統(tǒng)是否發(fā)生故障。
2.2可分碼校驗(yàn)器
可分碼校驗(yàn)器的結(jié)構(gòu)如圖4所示。校驗(yàn)器的輸入矢量為
),矢量
和
分別對(duì)應(yīng)可分碼的信息分量和校驗(yàn)分量。其中,信息分量寬度為
是校驗(yàn)分量的寬度,且1+K=n,n=‖Y‖。校驗(yàn)位生成電路根據(jù)信息位
重新生成校驗(yàn)位W,由雙軌碼校驗(yàn)器比較W與
的一致性,在無(wú)故障的情況下,校驗(yàn)器的輸出
指示輸入矢量的有效性。下面的定理給出了圖4完全自校驗(yàn)可分碼校驗(yàn)器的構(gòu)造條件。
定理:圖4所示的可分碼校驗(yàn)器是完全自校驗(yàn)的,若校驗(yàn)位生成器是一個(gè)無(wú)冗余的組合邏輯網(wǎng)絡(luò),且比較器是完全自校驗(yàn)的。
2.3互補(bǔ)邏輯網(wǎng)絡(luò)
利用互補(bǔ)邏輯也可以構(gòu)成自校驗(yàn)電路,如果某一邏輯網(wǎng)絡(luò)其輸入輸出關(guān)系為
,則可構(gòu)造一互補(bǔ)邏輯網(wǎng)絡(luò),使其輸入輸出關(guān)系為
其中f和f是互補(bǔ)的,在無(wú)故障的情況下,其輸出是互補(bǔ)的;若發(fā)生輸出相同,則兩個(gè)邏輯電路中必定有存在故障的情況?;パa(bǔ)邏輯網(wǎng)絡(luò)實(shí)現(xiàn)原理比較直觀,但對(duì)較復(fù)雜的系統(tǒng),有許多故障它是檢測(cè)不出來(lái)的。
2.4交織邏輯網(wǎng)絡(luò)
交織邏輯網(wǎng)絡(luò)是基于自對(duì)偶函數(shù)的自校驗(yàn)邏輯網(wǎng)絡(luò)。一個(gè)二進(jìn)制變量是交替的,記作
若x在兩個(gè)連續(xù)的時(shí)間間隔內(nèi)所取的值互補(bǔ)。
對(duì)任意一個(gè)開關(guān)函數(shù)
,若假設(shè)
是交替二進(jìn)制變量,且它們是同步交替的,則g的輸入矢量可表示為
,其輸出可表示為
,要使輸出變量也是交替的,必須滿足
,顯然,g必須是自對(duì)偶函數(shù)。利用交織邏輯網(wǎng)絡(luò)的這個(gè)特點(diǎn),可以檢測(cè)出系統(tǒng)的一部分故障。
3自校驗(yàn)網(wǎng)絡(luò)實(shí)現(xiàn)方法
對(duì)于一些比較簡(jiǎn)單的應(yīng)用場(chǎng)合,利用數(shù)字邏輯方法進(jìn)行設(shè)計(jì),使用SSI及MSI集成電路即可方便地構(gòu)成自校驗(yàn)網(wǎng)絡(luò)。但實(shí)際容錯(cuò)系統(tǒng)非常復(fù)雜,涉及大量邏輯設(shè)計(jì),若仍采用傳統(tǒng)的數(shù)字邏輯設(shè)計(jì)方法,不僅工作量大、容易出差錯(cuò),而且修改和功能仿真都不方便。使用電子設(shè)計(jì)硬件描述語(yǔ)言VHDL(或VerilogHDL對(duì)電路功能進(jìn)行描述,用FPGA或CPLD器件實(shí)現(xiàn)自校驗(yàn)網(wǎng)絡(luò)是比較現(xiàn)實(shí)的,對(duì)于大批量生產(chǎn),可將VHDL描述的電路送半導(dǎo)體器件廠進(jìn)行批量生產(chǎn),VHDL硬件描述語(yǔ)言實(shí)現(xiàn)自校驗(yàn)網(wǎng)絡(luò)的步驟如下:
①建立自校驗(yàn)網(wǎng)絡(luò)的功能模型。對(duì)系統(tǒng)的輸入/輸出、狀態(tài)轉(zhuǎn)換、信號(hào)傳遞等進(jìn)行詳細(xì)的說(shuō)明。
②用VHDL語(yǔ)言或VerilogHDL語(yǔ)言對(duì)電路功能進(jìn)行描述。對(duì)復(fù)雜系統(tǒng)可采用撟隕隙?聰?shù)脑O(shè)計(jì)方法,將系統(tǒng)分解成不同層次的、功能較簡(jiǎn)單的模塊,利用VHDL語(yǔ)言對(duì)系統(tǒng)功能進(jìn)行分層描述,減少系統(tǒng)描述造成的錯(cuò)誤。
③對(duì)不同層次的模塊進(jìn)行功能仿真,以檢驗(yàn)各模塊設(shè)計(jì)的正確性,最后對(duì)整個(gè)系統(tǒng)進(jìn)行功能仿真,及早排除系統(tǒng)設(shè)計(jì)中的錯(cuò)誤。
④用VHDL或VerilogHDL綜合編譯器對(duì)設(shè)計(jì)好的系統(tǒng)進(jìn)行編譯,經(jīng)過(guò)邏輯化簡(jiǎn)及綜合布線,生成可對(duì)FPGA或CPLD編程的數(shù)據(jù)文件。
⑤將數(shù)據(jù)文件通過(guò)編程器寫入FPGA或CPLD,進(jìn)行實(shí)際測(cè)試,若測(cè)試數(shù)據(jù)滿足設(shè)計(jì)要求,則開發(fā)工作完成;否則,轉(zhuǎn)①重新進(jìn)行檢查和設(shè)計(jì)。
采用自校驗(yàn)技術(shù)后,可有效地提高容錯(cuò)系統(tǒng)的可靠性,隨著集成電路技術(shù)的飛速發(fā)展,可將一些自校驗(yàn)功能模塊進(jìn)行封裝,作為標(biāo)準(zhǔn)單元使用,在模塊級(jí)上提高容錯(cuò)系統(tǒng)的可靠性。采用高級(jí)語(yǔ)言和FPGA或CPLD開發(fā)容錯(cuò)系統(tǒng)具有重要的現(xiàn)實(shí)意義,可有效縮短開發(fā)周期,降低開發(fā)成本,提高系統(tǒng)可靠性,應(yīng)在工程設(shè)計(jì)中加以推廣應(yīng)用。