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

于中寶， 邵方明

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

并行系統(tǒng)提供了高速的運(yùn)算潛力，但在高可靠性和容錯(cuò)性方面仍然存在問題，其原因與并行系統(tǒng)的網(wǎng)絡(luò)拓?fù)溆嘘P(guān)，如超立方體，星圖和排列圖等。系統(tǒng)的可靠性定義為系統(tǒng)沒有故障的概率，每個(gè)處理器正常運(yùn)行的概率被記為p。排列圖具有高容錯(cuò)性、直徑小和低節(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 個(gè)不同的整數(shù)得到排列 a1a2···ak，其中 ai=aj當(dāng)且僅當(dāng) i=j。

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

1.2 排列圖子圖的定義

2 排列圖子圖可靠性的近似計(jì)算

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

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

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

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

∑Table 1 Calculation of表 1 的計(jì)算∑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 子圖可靠性的近似計(jì)算Fig. 3 Approximate calculations of subgraph reliability of A5,4

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

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

3.1 蒙特卡羅介紹

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

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

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

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

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

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

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

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

算法2：

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

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

（3）每個(gè)節(jié)點(diǎn)正常運(yùn)行的概率為p，則失敗的概率為q=1-p；若步驟(2)中向量γi的第j 個(gè)隨機(jī)數(shù)大于q，記作對(duì)應(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è)排列圖子圖，如果構(gòu)成一個(gè)排列圖子圖，則s+=1，否則s=s；

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

（6）可靠性為 s/N。

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

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

利用容斥原理，得到

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

（2）隨機(jī)生成一個(gè)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；

通過仿真計(jì)算，得到表2。

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

表 2 A3,2 的子圖可靠性蒙特卡羅近似計(jì)算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子圖可靠性的界以及近似計(jì)算的結(jié)果見表3。

表 3 排列圖An,k 子圖可靠性的界以及近似計(jì)算（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)了異常，這就是魯棒性問題。對(duì)于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 的近似計(jì)算會(huì)出現(xiàn)魯棒性問題，已有近似計(jì)算的結(jié)果要大于真實(shí)值，利用蒙特卡羅得到近似結(jié)果和真實(shí)值基本重合。

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

5 結(jié) 論

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