多模冗余可重構計算機可靠性研究

李興偉，白 博，周 軍

(西北工業大學，精確制導與控制研究所，西安 710072)

多模冗余可重構計算機可靠性研究

李興偉，白 博，周 軍

(西北工業大學，精確制導與控制研究所，西安 710072)

為了以最小代價提高多模可重構計算機的可靠性，需要結合系統體積功耗等因素,對不同計算機體系結構的可靠性進行評估；首先，針對三模冗余、三熱一冷以及四模熱備這幾種不同冗余可重構計算機體系結構，給出了他們的故障狀態轉移圖；其次，運用馬爾可夫模型理論，對這些計算機結構進行可靠性建模；第三，根據上述3種系統的可靠性模型，在考慮失效率和維修率兩個參數對系統可靠性影響的情況下，對各結構的可靠性指標進行了評價；結果表明，三熱一冷的可靠性大于三模冗余，而小于四模熱備；但綜合考慮系統的可靠度、體積、功耗等因素后，在這幾種形式的表決系統中，三熱一冷是最優的；同時，設計完善的三模可重構系統可靠度會比一個設計不合理的四模可重構系統要高。

多模冗余；馬爾可夫模型；可重構計算機

0 引言

近年來，隨著大容量可重構FPGA的出現，掃除了可重構計算機技術在工程實現方面的障礙。與傳統的計算機相比，可重構計算機在系統部分部件出現故障時，能夠自主地改變自身的系統功能，使系統按原定性能指標或比原性能指標略有降低 (但可接受)的要求安全地完成任務。這樣就避免了固定硬件結構的計算機一旦發生硬件損傷，將導致系統崩潰這一問題。

為了保證可重構計算機的可靠性指標，除了選擇高質量的元器件外，普遍的做法是采用余度技術來實現這一目標[1]。常用的冗余結構有雙機備份、二乘二取二、三模冗余、三熱一冷等結構[2]。文獻[3]闡述了兩種不同工作策略的“二乘二取二”的可靠性與安全性，并與三模冗余系統進行了比較。文獻[4]對雙模冗余系統與三模冗余系統各系統的工作狀態進行了詳細分析，并利用馬爾可夫過程對不同維修率和故障檢測覆蓋率對系統可靠度和安全度的影響進行了仿真計算。文獻[5]對軌道交通里的三模冗余系統的可靠性與安全性進行了詳細分析，并給出了故障檢測率及維修率對三模冗余系統可靠性與安全性的影響。但以上文獻并未對具有更多冗余器件的可重構系統的可靠性進行討論。

本文針對由FPGA構成的幾種比較典型的多模冗余可重構系統結構，利用馬爾可夫過程對其進行可靠性建模。同時，在考慮系統失效率和維修率兩個參數對系統可靠性影響的情況下，對各系統的可靠性指標進行了評價，分析了以最小代價提高多模可重構計算機可靠性的途徑。

1 系統結構及工作原理

由FPGA構成的可重構計算機系統的最大特點是可以通過重新配置，進行系統的重構。這樣當系統出現故障后，系統通過可重構機制使得系統得以修復。同時，為了進一步提高可重構計算機的可靠性，采用多模結構組成多模冗余可重構計算機系統。本文主要針對比較常用的三模冗余、三熱一冷以及四模熱備這幾種冗余可重構計算機的可靠性進行分析。首先來看三模冗余系統。

1.1 三模冗余結構

圖1所示為三模冗余系統結構圖。

圖1 三模冗余表決系統結構圖

其工作原理是3個模塊同時對輸入信號進行運算處理，處理完畢后，送給表決器，由表決器選擇輸出。當3個模塊的輸出相同時，隨機選擇一個輸出；當有兩個模塊輸出相同而另一個模塊輸出不同時，從相同的兩個模塊中選擇一個輸出；當3個模塊輸出都不同時，系統產生報警。因此三模冗余可以屏蔽一個錯誤。

1.2 四模冗余結構

將圖1所示的三模冗余表決系統再加上一模，這樣就組成了四模冗余表決系統，如圖2所示。

圖2 四模冗余表決系統結構圖

其工作原理是4個模塊同時對輸入信號進行運算處理，處理完畢后，送給表決器，由表決器選擇輸出。當4個模塊的輸出相同時，隨機選擇一個輸出；當有兩個模塊輸出相同而另兩個模塊輸出不同時，從相同的兩個模塊中選擇一個輸出；當3個模塊輸出都不同時，系統產生報警。因此四模冗余可以屏蔽兩個錯誤。

1.3 三熱一冷冗余結構

將圖1所示的三模冗余表決系統上再加一模冷備份，這樣就組成三熱一冷的冗余表決系統，如圖3所示。

圖3 三熱一冷表決系統結構圖

其工作原理如下，在正常情況下，由3個工作的模塊同時對輸入信號進行運算處理，冷備份模塊不工作，表決器僅對3個工作模塊的結果進行處理。當3個模塊的輸出相同時，隨機選擇一個輸出；當有兩個模塊輸出相同而另一個模塊輸出不同時，從相同的兩個模塊中選擇一個輸出；當有一個模塊無法修復時，啟動冷備份模塊，重新構成三模冗余系統；當3個模塊輸出都不同時，系統產生報警。因此三熱一冷冗余結構同樣可以屏蔽兩個錯誤，但其與四模冗余結構在可靠性上會有區別。

2 可靠性模型及分析

在研究各系統的可靠性之前，首先對系統做如下假設：

1)假設系統中除了幾個計算機模塊外，其他系統的可靠度均為1；

2)每個計算機模塊的失效率為λ，系統維修率為μ，同時假設維修時間分布為指數分布；

3)某一時刻只有一個模塊發生故障；

4)系統開始工作時，系統處于完好狀態。

基于以上假設，對各結構的可靠性進行研究。

2.1 三模表決系統

對于圖1所示的三模冗余表決系統，定義每個模塊的維修率為常值μ，同時假設維修時間的分布為指數分布，則某一模塊在時刻t處于失效狀態，而在時刻t+Δt處于正常工作狀態的概率為1-e-μΔt，將其按級數展開，對于很小的Δt，可簡化為1-e-μΔt≈μΔt。

對于三模冗余表決系統，當且僅當至少有2個計算機正常時，系統才能工作。當有2個計算機故障時，系統故障，此時系統無法表決，系統停止輸出。因此其馬爾克夫狀態可描述為：

1)定義隨機變量X(t)=0，該狀態表示時刻t時有0個計算機故障，此狀態對應系統正常工作。稱此狀態為狀態0。

2)定義隨機變量X(t)=1，該狀態表示時刻t時有1個計算機故障，在此狀態下，系統仍能正常工作。稱此狀態為狀態1。

3)定義隨機變量X(t)=2，該狀態表示時刻t時有2個計算機故障，在此狀態下，系統故障。稱此狀態為狀態2。

X(t)是一個齊次馬爾可夫鏈。模塊的失效率為常數λ，根據假設模塊壽命的分布為指數分布，則某模塊在時刻t處于正常狀態，而在時刻t+Δt處于正常故障狀態的概率為1-e-λΔt，將其按級數展開，對于很小的Δt，可簡化為1-e-λΔt≈λΔt。由于系統由3個模塊組成，因此系統從狀態0到狀態1的轉移概率用語言來描述，則為3個模塊中僅有1個模塊出現故障。這樣，由于有3個模塊，該轉移概率就為3λΔt。其它狀態轉移概率依此類推。系統的狀態轉移圖如圖4所示。

圖4 三模冗余表決系統狀態轉移圖

2.2 四模表決系統

如果將圖1所示的三模冗余表決系統上再加一模，這樣就組成四模冗余表決系統。同樣定義模塊的維修率為常值μ。根據假設維修時間的分布為指數分布，則某一模塊在時刻t處于失效狀態，而在時刻t+Δt處于正常工作狀態的概率為1-e-μΔt，將其按級數展開，對于很小的Δt，可簡化為1-e-μΔt≈μΔt。

對于四模冗余表決系統，當且僅當至少有2個計算機正常時，系統才能正常工作。當有3個計算機故障時，系統故障，此時系統無法表決，系統停止輸出。其馬爾克夫狀態可描述為：

1)定義隨機變量X(t)=0，該狀態表示時刻t時有0個計算機故障，此狀態對應系統正常工作。稱此狀態為狀態0。

2)定義隨機變量X(t)=1，該狀態表示時刻t時有1個計算機故障，在此狀態下，系統仍能正常工作。稱此狀態為狀態1。

3)定義隨機變量X(t)=2，該狀態表示時刻t時有2個計算機故障，在此狀態下，系統仍能正常工作。稱此狀態為狀態2。

4)定義隨機變量X(t)=3，該狀態表示時刻t時有3個計算機故障，在此狀態下，系統故障。稱此狀態為狀態3。

X(t)是一個齊次馬爾可夫鏈。模塊的失效率為常數λ，根據假設模塊壽命的分布為指數分布，則某模塊在時刻t處于正常狀態，而在時刻t+Δt處于正常故障狀態的概率為1-e-λΔt，將其按級數展開，對于很小的Δt，可簡化為1-e-λΔt≈λΔt。由于系統由4個模塊組成，因此系統從狀態0到狀態1的轉移概率用語言來描述，則為4個模塊中僅有1個模塊出現故障。這樣，由于有4個模塊，該轉移概率就為4λΔt。其它狀態轉移概率依此類推。系統的狀態轉移圖如圖5所示。

圖5 四模冗余表決系統狀態轉移圖

2.3 三熱一冷表決系統

將圖1所示的三模冗余表決系統上再加一模冷備份，這樣就組成三熱一冷的冗余表決系統。同樣定義模塊的維修率為常值μ。根據假設維修時間的分布為指數分布，則某一模塊在時刻t處于失效狀態，而在時刻t+Δt處于正常工作狀態的概率為1-e-μΔt，將其按級數展開，對于很小的Δt，可簡化為1-e-μΔt≈μΔt。

對于三熱一冷的表決系統，仍然當且僅當至少有2個計算機正常時，系統才能正常工作。當有3個計算機故障時，系統故障，此時系統無法表決，系統停止輸出。其馬爾克夫狀態可描述為：

1)定義隨機變量X(t)=0，該狀態表示時刻t時有0個計算機故障，此狀態對應系統正常工作。稱此狀態為狀態0。

2)定義隨機變量X(t)=1，該狀態表示時刻t時有1個計算機故障，在此狀態下，系統將冷備份模塊切換進來，系統組成仍為三模冗余，仍能正常工作。稱此狀態為狀態1。

3)定義隨機變量X(t)=2，該狀態表示時刻t時有2個計算機故障，在此狀態下，系統仍能正常工作。稱此狀態為狀態2。

4)定義隨機變量X(t)=3，該狀態表示時刻t時有3個計算機故障，在此狀態下，系統故障。稱此狀態為狀態3。

X(t)是一個齊次馬爾可夫鏈。模塊的失效率為常數λ，根據假設模塊壽命的分布為指數分布，則某模塊在時刻t處于正常狀態，而在時刻t+Δt處于正常故障狀態的概率為1-e-λΔt，將其按級數展開，對于很小的Δt，可簡化為1-e-λΔt≈λΔt。由于系統為三熱一冷的形式，則在正常工作中，實際是三模系統在工作，因此系統從狀態0到狀態1的轉移概率用語言來描述，則為3個模塊中僅有1個模塊出現故障。這樣，由于僅計算3個模塊，該轉移概率就為3λΔt。而在狀態1時，實際上系統仍為3模，因此狀態1向狀態2轉移的概率仍為3λΔt。其它狀態轉移概率依此類推。系統的狀態轉移圖如圖6所示。

圖6 三熱一冷表決系統狀態轉移圖

3 可靠性計算

根據以上的可靠性模型進行可靠性計算。

3.1 三模表決系統

根據圖4所示的狀態轉移圖，可得到如下轉移概率，即條件概率。

P00=P{X(t+Δt)=0|X(t)=0}=1-3λΔt

(1)

P10=P{X(t+Δt)=1|X(t)=0}=3λΔt

(2)

P20=P{X(t+Δt)=2|X(t)=0}=0

(3)

P01=P{X(t+Δt)=0|X(t)=1}=μΔt

(4)

P11=P{X(t+Δt)=1|X(t)=1}=1-2λΔt-μΔt

(5)

P21=P{X(t+Δt)=2|X(t)=1}=2λΔt

(6)

P02=P{X(t+Δt)=0|X(t)=2}=0

(7)

P12=P{X(t+Δt)=1|X(t)=2}=μΔt

(8)

P22=P{X(t+Δt)=2|X(t)=2}=1-μΔt

(9)

現欲求X(t)在不同狀態下的概率，P0(t)=P{X(t)=0}，P1(t)=P{X(t)=1}，P2(t)=P{X(t)=2}。根據全概率公式。

(10)

將式(1)～式(9)代入式(10)后，經過整理并求Δt→0的極限，可將式(10)寫成微分方程組的形式。

(11)

考慮系統初始狀態為正常的初值情況，[P0(t)P1(t)P2(t)]’=[1 0 0]’。利用拉普拉斯變換將微分方程變換成線性方程組后，解得[P0(s)P1(s)P2(s)]，再通過反拉式變換可解得時域解P0(t)，P1(t)，P2(t)。則據此可以算得三模表決系統的可靠度A3m(t)，

A3m(t)=P0(t)+P1(t)

(12)

3.2 四模表決系統

根據圖5所示的狀態轉移圖，可得到如下轉移概率，即條件概率。

P00=P{X(t+Δt)=0|X(t)=0}=1-4λΔt

(13)

P10=P{X(t+Δt)=1|X(t)=0}=4λΔt

(14)

P20=P{X(t+Δt)=2|X(t)=0}=0

(15)

P30=P{X(t+Δt)=3|X(t)=0}=0

(16)

P01=P{X(t+Δt)=0|X(t)=1}=μΔt

(17)

P11=P{X(t+Δt)=1|X(t)=1}=1-(3λ+μ)Δt

(18)

P21=P{X(t+Δt)=2|X(t)=1}=3λΔt

(19)

P31=P{X(t+Δt)=3|X(t)=1}=0

(20)

P02=P{X(t+Δt)=0|X(t)=2}=0

(21)

P12=P{X(t+Δt)=1|X(t)=2}=μΔt

(22)

P22=P{X(t+Δt)=2|X(t)=2}=1-(2λ+μ)Δt

(23)

P32=P{X(t+Δt)=3|X(t)=2}=2λΔt

(24)

P03=P{X(t+Δt)=0|X(t)=3}=0

(25)

P13=P{X(t+Δt)=1|X(t)=3}=0

(26)

P23=P{X(t+Δt)=2|X(t)=3}=μΔt

(27)

P33=P{X(t+Δt)=3|X(t)=3}=1-μΔt

(28)

現欲求X(t)在不同狀態下的概率，P0(t)=P{X(t)=0}，P1(t)=P{X(t)=1}，P2(t)=P{X(t)=2},P3(t)=P{X(t)=3}。根據全概率公式。

(29)

將式(13)～式(28)代入式(29)后，經過整理并求Δt→0的極限，可將式(29)寫成微分方程組的形式。

(30)

考慮系統初始狀態為正常的初值情況，[P0(t)P1(t)P2(t)P3(t)]’=[1 0 0 0]’。利用拉普拉斯變化將微分方程變換成線性方程組后，解得[P0(s)P1(s)P2(s)P3(s)]，再通過反拉式變化可解得時域解P0(t)，P1(t)，P2(t)，P3(t)。則據此可以算得四模表決系統的可靠度A4m(t)，

A4m(t)=P0(t)+P1(t)+P2(t)

(31)

3.3 三熱一冷表決系統

根據圖3所示的狀態轉移圖，可得到如下轉移概率，即條件概率。

P00=P{X(t+Δt)=0|X(t)=0}=1-3λΔt

(32)

P10=P{X(t+Δt)=1|X(t)=0}=3λΔt

(33)

P20=P{X(t+Δt)=2|X(t)=0}=0

(34)

P30=P{X(t+Δt)=3|X(t)=0}=0

(35)

P01=P{X(t+Δt)=0|X(t)=1}=μΔt

(36)

P11=P{X(t+Δt)=1|X(t)=1}=1-(3λ+μ)Δt

(37)

P21=P{X(t+Δt)=2|X(t)=1}=3λΔt

(38)

P31=P{X(t+Δt)=3|X(t)=1}=0

(39)

P02=P{X(t+Δt)=0|X(t)=2}=0

(40)

P12=P{X(t+Δt)=1|X(t)=2}=μΔt

(41)

P22=P{X(t+Δt)=2|X(t)=2}=1-(2λ+μ)Δt

(42)

P32=P{X(t+Δt)=3|X(t)=2}=2λΔt

(43)

P03=P{X(t+Δt)=0|X(t)=3}=0

(44)

P13=P{X(t+Δt)=1|X(t)=3}=0

(45)

P23=P{X(t+Δt)=2|X(t)=3}=μΔt

(46)

P33=P{X(t+Δt)=3|X(t)=3}=1-μΔt

(47)

現在欲求X(t)在不同狀態下的概率，P0(t)=P{X(t)=0}，P1(t)=P{X(t)=1}，P2(t)=P{X(t)=2},P3(t)=P{X(t)=3}。根據全概率公式。

(48)

將式(32)～式(47)代入式(48)后，經過整理并求Δt→0的極限，可將式(48)寫成微分方程組的形式。

(49)

考慮系統初始狀態為正常的初值情況，[P0(t)P1(t)P2(t)P3(t)]’=[1 0 0 0]’。利用拉普拉斯變化將微分方程變換成線性方程組后，解得[P0(s)P1(s)P2(s)P3(s)]，再通過反拉式變化可解得時域解P0(t)，P1(t)，P2(t)，P3(t)。則據此可以算得三熱一冷表決系統的可靠度A3h1c(t)，

A3h1c(t)=P0(t)+P1(t)+P2(t)

(50)

4 可靠性驗證及分析

根據式(12)、式(31)、式(50)可以分析與比較失效率和修復率對不同形式系統可靠性的影響。根據目前國內器件的平均失效率分析，取單臺計算機的失效率λ=0.001/h。圖7顯示了失效率λ=0.001/h，模塊的維修率μ=0.1/h的情況下，不同系統形式的可靠度隨時間變化的曲線。

由圖中我們可以看出，3種形式的可靠度最后都趨向于常值，這是由于本文僅研究系統穩定可靠期所致。實際上，隨著時間的推移，最終產品都會趨向于失效，這已超出本文所研究的范圍。由圖中可以看出，在相同失效率和修復率的情況下，三熱一冷的可靠度最高，約為99.99825%，四模熱備份的可靠度約為99.99770%，三模熱備份的可靠度最低，約為99.94178%。

雖然四模熱備的可靠度和三熱一冷的可靠度很相似，但在

圖7 不同形式表決系統的可靠度比較

實際使用過程中，三熱一冷的系統形式始終有一模處于冷的狀態，這樣對于減小系統功耗是有利的。因此，在四模熱備、三熱一冷、三模熱備這幾種形式的表決系統中，三熱一冷是最優的。

而對于可重構系統，其修復率不僅取決于硬件結構的設計，同時也取決于可重構系統軟件的架構。下表顯示了不同修復率情況下，不同系統形式的可靠度變化。

表1 修復率以及系統構成對系統可靠度的影響

由該表可以看出，如果提升修復率后，各系統形式的可靠度均有上升。在高修復率的情況下，三模系統的可靠度能達到低修復率的四模系統。這一點說明，對于三模系統，如果重構系統設計完善，對不同故障都能夠修復，那么該三模系統的可靠度會比一個設計不合理的四模系統要高。

通過以上分析可以得到如下兩點結論：

1)綜合考慮系統的可靠度、體積、功耗等因素后，在四模熱備、三熱一冷、三模熱備這幾種形式的表決系統中，三熱一冷是最優的。

2)對于三模可重構系統，需要設計完善的重構機制，盡量修復不同的故障模式，那么該三模系統的可靠度會比一個設計不合理的四模可重構系統要高。

5 結論

本文針對比較常用的三模冗余、三熱一冷以及四模熱備這幾種冗余可重構計算機的可靠性進行分析。在一定的假設條件下，對比了這幾種體系結構的可靠性。結果表明，在綜合考慮系統的可靠度、體積、功耗等因素后，在四模熱備、三熱一冷、三模熱備這幾種形式的表決系統中，三熱一冷是最優的。同時，如果三模可重構系統的重構機制設計完善，修復率較高，那么該三模系統的可靠度會比一個設計不合理的四模可重構系統要高。因此在這幾種多模冗余可重構計算機體系結構中，可優先考慮三模冗余結構。如果對可靠性有進一步的要求，可選擇三熱一冷的結構形式。

[1] Majid Asadi，Ismihan Bayramoglu.The Mean Residual Life Function of a k-out-of-n Structure at the System Level [J].IEEE Transactions on Reliability，2006，55(2)：314-317.

[2] 李榮強，姜巍巍，曹德舜.基于典型冗余結構的安全儀表系統可靠性對比分析 [J].安全技術，2015，15(8)：11-13.

[3] 張本宏，陸 陽，韓江洪，等.“二乘二取二”冗余系統的可靠性和安全性分析[J].系統仿真學報，2009，21(1)：256-261.

[4] 武曉春，高雪娟.雙模冗余-比較系統與三模冗余系統的性能比較[J].自動化與儀器儀表，2012，164(6)：169-171.

[5] 陳 州，倪 明.三模冗余系統的可靠性與安全性分析[J].計算機工程，2012，38(14)：239-245.

Study on Reliability of Multiple Modular Redundant Reconfigurable Computer

Li Xingwei, Bai Bo, Zhou Jun

(Institute of Precision Guidance and Control, Northwestern Polytechnical University, Xi’an 710072, China)

In order to improve the reliability of multiple modular reconfigurable computers with minimum cost, the reliability of different computer architectures need to be evaluated with system power and volume consideration. First, considering the redundant reconfigurable computer architecture of triple modular redundancy (TMR), quadruple modular redundant (QMR)and triple modular with one cold backup, the fault state transition diagrams of these architectures are proposed. Second, the reliability models of these computer systems are built with Markov model. Third, considering the influences of reliability with failure rate and maintenance ratio, the reliability of different structure are evaluated based on the above three models. The comparison of three results indicates that, the reliability of triple modular with one cold is less than the reliability of QMR, while it is bigger than the reliability of TMR. But after considering the factors of reliability, system volume and power consumption, the triple modular with one cold is optimal. And the reliability of a perfectly designed TMR reconfigurable system will be higher than that of a bad designed QMR reconfigurable system.

multiple modular redundant; Markov model; reconfigurable computer

2016-12-27；

2017-02-06。

航天支撐技術基金(2015-HT-XGD);西北工業大學基礎研究基金(JC201205)。

李興偉(1974-)，男，內蒙古人，博士研究生，主要從事飛行器導航、制導與控制方面的研究。

1671-4598(2017)07-0309-04

10.16526/j.cnki.11-4762/tp.2017.07.077

TP302.8

A