并行系統(tǒng)中排列圖的可靠性近似算法

于中寶， 邵方明

（華東理工大學(xué)數(shù)學(xué)系，上海 200237）

并行系統(tǒng)提供了高速的運(yùn)算潛力，但在高可靠性和容錯性方面仍然存在問題，其原因與并行系統(tǒng)的網(wǎng)絡(luò)拓?fù)溆嘘P(guān)，如超立方體，星圖和排列圖等。系統(tǒng)的可靠性定義為系統(tǒng)沒有故障的概率，每個處理器正常運(yùn)行的概率被記為p。排列圖具有高容錯性、直徑小和低節(jié)點(diǎn)度等特點(diǎn)，因此進(jìn)一步分析排列圖的可靠性具有重要意義。

1 排列圖的相關(guān)性質(zhì)

1.1 排列圖An,k 的定義[2]

n，k 都是整數(shù)，其中 1≤k＜n。

（1）點(diǎn)的定義：從{1,2,···, n}中取 k 個不同的整數(shù)得到排列 a1a2···ak，其中 ai=aj當(dāng)且僅當(dāng) i=j。

（2）邊的定義：排列圖中的兩點(diǎn)連接成邊，當(dāng)且僅當(dāng)點(diǎn)（排列）中對應(yīng)位置只有一個不同，比如節(jié)點(diǎn) a1···ai-1aiai+1···ak和 a1···ai-1biai+1···ak的 第 i 個 位置不同，則這兩個節(jié)點(diǎn)之間有邊，其中1≤i≤k。圖1中是以A4,2為例說明了排列圖、子圖和節(jié)點(diǎn)。

1.2 排列圖子圖的定義

2 排列圖子圖可靠性的近似計算

排列圖子圖可靠性的計算是一個NP-hard 問題，所以可以用排列圖子圖可靠性的界去衡量排列圖子圖可靠性。

文獻(xiàn)[1]已經(jīng)給出上界的計算

（2）兩個位置：因?yàn)閺乃膫€位置中選擇兩個位置放置symbol，所以位置的選擇有 C42種。因?yàn)閷? 個symbol 放置在兩個位置上，有 3 種分法：(1, 3)、(2,2)和(3, 1)。(1, 3)表示取得的兩個位置，第一個位置放 1 個 symbol，第二個位置放 3 個 symbol。(2, 2)表示取得的兩個位置，第一個位置放2 個symbol，第二個位置放2 個symbol，(3, 1)表示取得兩個位置，第一個位置放 3 個 symbol，第二個位置放 1 個 symbol，其所得結(jié)果和(1, 3)情況類似。

（3）三個位置：因?yàn)閺乃膫€位置中選擇三個位置放置symbol，所以位置的選擇有種。因?yàn)閷? 個symbol 放置在三個位置上，有三種分法：(1, 1, 2)、(1,2, 1)和 (2, 1, 1)。(1, 1, 2)表示第一個位置放 1 個symbol，第二個位置放 2 個 symbol，第三個位置放2 個symbol。由排列組合知這三種分法所得結(jié)果一樣，所以只對(1, 1, 2)討論。

∑Table 1 Calculation of表 1 的計算∑r(i,j,l,q)(p)i＜ j＜l＜q r(i,j,l,q)(p)i＜ j＜l＜q Reliability One position Two positions Three positions Four positions R1=C1kC4n p4Ak-1 n-1 R2=C2k(2C1nC2n-1p4Ak-1 n-1-2Ak-2n-2+2C1nC3n-1p4Ak-1 n-1-3Ak-2n-2+2C2nC1n-2 p4Ak-1 n-1-3Ak-2n-2+C2n p4Ak-1 n-1-2Ak-2n-2+C2nC2n-2p4Ak-1 n-1-4Ak-2n-2 R3=C3k(3C1nC1n-1 p4Ak-1 n-1-2Ak-2n-2+3C1nC2n-1p4Ak-1 n-1-4Ak-2n-2+6C1nC1n-1C1 n-2p4Ak-1 n-1-4Ak-2n-2+Ak-3n-3+3C1nC1n-1p4Ak-1 n-1-3Ak-2n-2 R4=C4k(C1n p4Ak-1 n-1+4C1nC1n-1p4Ak-1 n-1-3Ak-2n-2+3C1nC1n-1p4Ak-1 n-1-4Ak-2n-2+6C1nC1n-1C1n-2p4Ak-1 n-1-5Ak-2n-2+2Ak-3n-3+C1nC1n-1C1n-2C1n-3p4Ak-1 n-1-6Ak-2n-2+4Ak-3n-3-Ak-4n-4)

圖 3 排列圖A5,4 子圖可靠性的近似計算Fig. 3 Approximate calculations of subgraph reliability of A5,4

針對魯棒性的情況，本文提出了基于排列圖的子圖可靠性的蒙特卡羅算法近似計算排列圖的子圖可靠性。

3 蒙特卡羅方法計算排列圖子圖的可靠性

3.1 蒙特卡羅介紹

蒙特卡羅方法是以概率統(tǒng)計理論為指導(dǎo)的一種非常重要的數(shù)值方法，它使用隨機(jī)數(shù)解決許多計算問題：

（1）輸入最小值、最大值和最可能的估算數(shù)據(jù)，并為其選擇合適的先驗(yàn)分布模型;

（2）根據(jù)以上輸入，采用一定的規(guī)則，快速實(shí)施大量的隨機(jī)抽樣;

（3）對隨機(jī)抽樣的數(shù)據(jù)進(jìn)行數(shù)學(xué)計算并處理結(jié)果;

（4）基于累積概率的分析，對結(jié)果進(jìn)行概率分析，得出結(jié)論。

3.2 排列圖子圖的可靠性的蒙特卡羅近似計算

對于排列圖An,k，排列圖子圖的可靠性定義為：當(dāng)系統(tǒng)發(fā)生故障時，仍然存在一個正常運(yùn)行子圖的概率。

利用蒙特卡羅方法對排列圖子圖的可靠性進(jìn)行計算的一般過程如下：

算法2：

（1）已知排列圖An,k，輸入循環(huán)次數(shù)N，節(jié)點(diǎn)正常運(yùn)行概率p，計數(shù)器s=0；

（2）對于第i 次循環(huán)，生成(0, 1)之間的n!/(n-k)!個隨機(jī)數(shù)，構(gòu)成一個n!/(n-k)!維的向量γi；

（3）每個節(jié)點(diǎn)正常運(yùn)行的概率為p，則失敗的概率為q=1-p；若步驟(2)中向量γi的第j 個隨機(jī)數(shù)大于q，記作對應(yīng)的節(jié)點(diǎn)j 正常運(yùn)行，狀態(tài)變量記為1，否則記為0，得到狀態(tài)向量λi；

（4）根據(jù)步驟(3)中λi狀態(tài)，判斷剩下正常運(yùn)行的節(jié)點(diǎn)，是否構(gòu)成一個排列圖子圖，如果構(gòu)成一個排列圖子圖，則s+=1，否則s=s；

（5）如果 i≤N，i+=1，返步驟 (2)；否則，返步驟 (6)；

（6）可靠性為 s/N。

例2：以A3,2(圖4)為例，對蒙特卡羅方法進(jìn)行說明：

圖 4 排列圖A3,2Fig. 4 Arrangement graph A3,2

利用容斥原理，得到

（1）輸入循環(huán)次數(shù) N=100，計數(shù) s=0，p=0.8，q=0.2；

（2）隨機(jī)生成一個6 維的向量(0.282 07, 0.136 92,0.438 19, 0.526 09, 0.065 82, 0.207 75)；

（3）生成狀態(tài)向量 (1,0,1,1,0,1)；

（4）存在正常運(yùn)行的子圖X2(12, 32)和2X(23,21)，則 s+=1；

通過仿真計算，得到表2。

通過表2，發(fā)現(xiàn)蒙特卡羅得到的誤差不足1%，而且隨著循環(huán)次數(shù)的增多，誤差越小。

表 2 A3,2 的子圖可靠性蒙特卡羅近似計算Table 2 Approximate calculation of the Monte Carlo Method for A3,2 subgraph

4 實(shí)例驗(yàn)證

取p=0.85，N=1 000，得到An,k子圖可靠性的界以及近似計算的結(jié)果見表3。

表 3 排列圖An,k 子圖可靠性的界以及近似計算（n=3,4,5,6,7；k=2,3,4）Table 3 Bounds and the approximate calculation of subgraph reliability for An,k（n=3,4,5,6,7; k=2,3,4）

通過表3 發(fā)現(xiàn)，A3,2、A4,2的上、下界出現(xiàn)了異常，這就是魯棒性問題。對于A5,4、A6,3、A7,3，文獻(xiàn)[1]中的近似值都大于上界值，而蒙特卡羅模擬的可靠性都在上、下界之間，可見蒙特卡羅模擬的可靠性結(jié)果要優(yōu)于已知算法。

取p=0.5, 0.6, 0.7, 0.8, 0.9 得到排列圖A3,2子圖可靠性的近似解如表4 所示，結(jié)果表明算法1 的近似計算會出現(xiàn)魯棒性問題，已有近似計算的結(jié)果要大于真實(shí)值，利用蒙特卡羅得到近似結(jié)果和真實(shí)值基本重合。

表 4 排列圖A3,2 子圖可靠性的近似計算Table 4 Approximate calculation of subgraph reliability for A3,2

5 結(jié) 論

本文主要研究了排列圖子圖的可靠性問題，提出了排列圖子圖的下界，在此基礎(chǔ)上提出了算法1：將上、下界的平均值作為排列圖子圖可靠性的近似值。在算法1 的計算過程中會有魯棒性問題，針對這一問題，本文提出了基于排列圖的蒙特卡羅模擬算法，利用蒙特卡羅去計算A3,2的排列圖子圖的可靠性，其誤差不足1%。對于其他排列圖的可靠性，蒙特卡羅算法也優(yōu)于已知的近似算法。