k元n方體網絡的子網絡可靠性

2021-08-19 10:38:52馮凱，李婧

計算機工程與應用 2021年16期

關鍵詞：故障

馮凱，李婧

山西大學計算機與信息技術學院，太原030006

隨著并行計算機系統規模的不斷增大，系統功能的實現越來越依賴于系統元件之間支撐通信和數據交互的連接模式（即系統的互連網絡，其中的每個頂點對應一個處理器，每條邊對應一對處理器之間的一條直接通信線路）。以具有優良性能的互連網絡為底層拓撲結構設計高性能并行計算機系統已經成為高性能計算領域的一個發展趨勢[1]。人們往往選用具有遞歸結構（即高維的網絡可以被劃分為一些獨立的低維的子網絡，并且這些子網絡與原網絡具有相同的拓撲性質）的互連網絡來構建并行計算機系統。一方面，這類網絡可以通過特定的機制指派各個子網絡完成用戶任務的不同部分，從而有效地利用系統資源；另一方面，這類網絡便于在原有基礎上進行擴容和升級，并且能夠保持原網絡的良好性能。當基于遞歸互連網絡構建的并行計算機系統中有故障發生時，系統互連網絡關于其子網絡的保持能力對系統實際應用至關重要。在此背景下，遞歸互連網絡的子網絡可靠性得到了學者們的關注[2-5]。Abraham和Padmanabhan[2]對n維超立方體的子網絡可靠性進行了研究，分別在不同故障模型下給出了子超立方體保持無故障狀態的平均失效時間的估計值。受此啟發，Fitzgerald等[3]分別在不同故障模型下基于固定劃分模式得出了n維星圖網絡中不同數目的(n-1)維星圖子網絡保持無故障狀態的平均失效時間，并基于靈活劃分模式對這一子網絡可靠性評估參數進行了估算。最近，文獻[4]和文獻[5]分別對(n,k)-星圖網絡和DCell數據中心網絡中不同數目的某一規模子網絡保持無故障狀態的平均失效時間也進行了分析。

k元n方體網絡是一類著名遞歸互連網絡，諸多基于k元n方體網絡構建的并行計算機系統已經問世，如Cray T3E[6]、IBM Blue Gene[7]等。近年來，k元n方體網絡的拓撲性質得到了廣泛的研究[8-14]。針對k為奇數的k元n方體網絡，文獻[9]在點故障模型下研究了使得k元n方體網絡中不存在k元(n-m)方體子網絡(0≤m≤n-1)的最小的點故障數，并構建出與任意規模子網絡一一對應的符號化表示。隨后，文獻[13]基于概率故障模型給出了k為奇數的k元n方體網絡中存在k元(n-1)方體子網絡的概率估計，文獻[14]在點故障模型下分析了k為奇數的k元n方體網絡中不同數目的k元(n-1)方體子網絡保持無故障狀態的平均失效時間。

在實際中，許多并行計算機系統可以利用故障診斷算法快速判斷出發生故障的處理器并及時進行維修和更換，而處理器之間的通信線路可能由于物理損壞、電磁干擾、人為損壞等因素產生故障且無法得到及時修復（由于系統的處理器對之間大都不存在重復的直接通信線路，不同處理器對之間的通信線路通常可以看作是沒有關聯的）。基于這一考慮，本文將在邊故障模型下（假定互連網絡中的頂點不會發生故障，各條邊發生故障是相互獨立的，且邊的故障率是不變的），對k為奇數的k元n方體網絡中不同數目的k元(n-1)方體子網絡保持無故障狀態的平均失效時間進行估計，這一研究可以幫助工程師更加全面地了解k元n方體網絡中不同數目的k元(n-1)方體子網絡存在性的保持能力。

1 基本概念與性質

k元n方體（k≥2,n≥1為整數）記為，是一個具有kn個頂點的無向簡單圖。的任一頂點可表示為u=u0u1…un-1，其中對于任意的整數i(0≤i≤n-1)均有ui∈{0,1,…,k-1}。兩個頂點u=u0u1…un-1和v=v0v1…vn-1相鄰當且僅當存在j∈{0,1,…,n-1}使得uj=vj±1(modk)且對于任意的l∈{0,1,…,n-1}{j}均有ul=vl,這樣的一條邊(u,v)稱為中的一條j維邊。容易得出，當k≥3時共有nkn條邊，且j維邊的數目為kn，其中j∈{0,1,…,n-1}。

性質1[9]中共有nk個不同的子網絡。

給定任一整數d∈{0,1,…,n-1}，可以將沿第d維劃分為k個不相交的子網絡其中Hd,i為中由點集導出的子圖，這里i∈{0,1,…,k-1}。結合性質1可知，當k≥3為奇數時，中所有不同的子網絡恰好是由沿不同維劃分得出的。在無特殊說明的情況下，假定下文中出現的均滿足k≥3為奇數。

在介紹主要結果之前，先引入一些基本概念和標記（見表1）。對于文中其他未加定義而被使用的圖論術語和記號參見文獻[15]。

表1 主要符號及含義Table 1 Main symbols and meanings

2 主要結果

2.1 固定劃分模式下Ti的計算

選定d∈{0,1,…,n-1}，可以將沿第d維劃分為k個不相交的子網絡基于這一固定劃分模式，下面通過計算Ti來評估中不相交的子網絡的可靠性。

由R*(t)和T*的定義可知，中所有故障邊均位于i個子網絡中時中顯然有k-i個子網絡保持無故障狀態，故對于任意的0≤i≤k-1有

因此，為了計算固定劃分模式下T*和Ti(0≤i≤k-1)的值，首先需要厘清S*,S0,S1,…,Sk之間的狀態轉換關系。

基于上述分析可知，當t=0時，P*(0)=1且對于任意的0≤l≤k有Pl(0)=0；當t=∞時，P*(∞)=0,Pk(∞)=1且對于任意的0≤l≤k-1有Pl(∞)=0；P*(t)，P0(t)，P1(t),…,Pk(t)之間的相互關系可表示為：

其中2≤i≤k。

進一步地，有如下結論成立。

證明由r0)dt。結合P*(0)=1求解可得從而可知，

注意到

由P0(0)=0可知：

令r=nknλ，則P*(t)=e-rt。對P*(t)=e-rt做拉普拉斯變換可知：

定理1證畢。

例1選取k∈{5,7}，n∈{4,5}。在固定劃分模式下，不同規模的的Ti的值如表2所示，其中中邊的故障率為λ=10-7/h。

表2 固定劃分模式下的Ti的值Table 2 Values of Ti in under fixed partition pattern

2.2 靈活劃分模式下Ti的計算

注意到，對于任意的d∈{0,1,…,n-1}，可以將沿第d維劃分為k個子網絡。若首條故障邊為l維邊，那么將沿第l維進行劃分（稱這種劃分模式為靈活劃分模式），這樣得到的k個子網絡均不會被首條故障邊所破壞。這意味著，在靈活劃分模式下，若處于狀態S*，首條故障邊不會導致狀態S*轉換為狀態S1。本節將證明靈活劃分模式下Ti的值相比固定劃分模式下這一參數的值有所增加。為了區分不同劃分模式下Ti的計算公式，記靈活劃分模式下Ti的值為

令w*=nknλ,wi=(k-i)(n-1)kn-1λ(0≤i≤k)。此時S*,S0,S1,…,Sk的狀態轉換圖如圖2所示。

圖2 靈活劃分模式下S*,S0,S1,…,Sk的狀態轉換圖Fig.2 State transition diagram of S*,S0,S1,…,Sk under flexible partition pattern

基于上述分析可知，當t=0時，P*(0)=1且對于任意的0≤l≤k有Pl(0)=0；當t=∞時，P*(∞)=0，Pk(∞)=1且對于任意的0≤l≤k-1有Pl(∞)=0；P*(t),P0(t),P1(t),…,Pk(t)之間的相互關系可表示為：

其中1≤i≤k。

采用類似于定理1的證明，可得出以下結論。

可以看出，相比固定劃分模式，靈活劃分模式下S*,S0,S1,…,Sk之間的狀態轉換關系發生了改變，這導致不同劃分模式下得出的不同數目的Qkn-1子網絡保持無故障狀態的平均失效時間的計算公式是不同的。

例2選取k∈{5,7}，n∈{4,5}。在靈活劃分模式下，不同規模的的值如表3所示，其中中邊的故障率為λ=10-7/h。

表3 靈活劃分模式下的值Table 3 Values of under flexible partition pattern

3 仿真分析

為了驗證不同劃分模式下理論結果的精確性，本文采用蒙特卡洛仿真來評估邊故障模型下中不相交的子網絡的可靠性。選取不同規模的n∈{4,5})為實驗對象。假定中邊的可靠性是獨立同分布的，且均服從故障率為λ(λ=10-7/h)的指數分布。在任意時刻t，中邊的可靠性為p(t)=e-λt。令f(t)為t時刻中故障邊的數目。由于可以看作是p(t)的估計值，f(t)可取為

注意到，對于任意的d∈{0,1,…,n-1}，可以將沿第d維劃分為k個子網絡Hd,0,Hd,1,…,Hd,k-1。若邊(u0u1…un-1,v0v1…vn-1)是d維邊，則該邊發生故障不會破壞Hd,0,Hd,1,…,Hd,k-1中任何一個子網絡；若邊(u0u1…un-1,v0v1…vn-1)不是d維邊，則該邊發生故障會破壞子網絡Hd,ud。

在固定劃分模式下，選定d*∈{0,1,…,n-1}，將沿第d*維進行劃分。在靈活劃分模式下，若首條故障邊為l維邊，則將沿第l維進行劃分。在任意時刻t，通過隨機生成10 000次故障邊集（每次生成的故障邊集的邊數為f(t)）對這一時刻在不同劃分模式下發生故障的子網絡的平均個數分別進行仿真計算，并與例1和例2計算出的理論結果進行對比，具體結果如圖3和圖4所示。