呂雅麗

摘要：該文給出了在存在結(jié)構(gòu)故障的情況下，k-元n-立方體網(wǎng)絡(luò)容錯哈密頓圈嵌入的構(gòu)造算法及實(shí)驗(yàn)結(jié)果。在這些實(shí)驗(yàn)中，得到了相應(yīng)的數(shù)據(jù)，為互連網(wǎng)絡(luò)多播算法的應(yīng)用提供了依據(jù)。

關(guān)鍵詞：結(jié)構(gòu)故障；k-元n-立方體網(wǎng)絡(luò)；哈密頓圈

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）27-0217-02

1 概述

隨著高性能計(jì)算機(jī)在國防太空、生物制藥、天氣預(yù)報(bào)等領(lǐng)域應(yīng)用的不斷深入，迫切需要速度更快的高性能計(jì)算機(jī)系統(tǒng)，進(jìn)而開辟了并行分布式系統(tǒng)的研究領(lǐng)域。在并行分布式系統(tǒng)中，多處理器之間連接的拓?fù)浣Y(jié)構(gòu)（稱為互連網(wǎng)絡(luò)）至關(guān)重要?；ミB網(wǎng)絡(luò)的選擇直接影響到并行分布式系統(tǒng)的性能和功能的實(shí)現(xiàn)。迄今，已有許多著名的互連網(wǎng)絡(luò)被相繼提出。例如：超立方體、類超立方體（BC網(wǎng)絡(luò)）、星圖、k-元n-立方體、蝶形圖等。k-元n-立方體網(wǎng)絡(luò)是一類重要的網(wǎng)絡(luò)。它具有許多優(yōu)良的性質(zhì)，例如直徑小、正則性、迭代性等。它包含一些重要的網(wǎng)絡(luò)拓?fù)渥鳛樗淖宇?，如環(huán)網(wǎng)絡(luò)，mesh，torus和超立方體網(wǎng)絡(luò)。目前許多并行分布式系統(tǒng)都是用k-元n-立方體網(wǎng)絡(luò)作為其連接模式，例如IBM BlueGene/L超級計(jì)算機(jī)、Cray T3D、Cray T3E以及J-machine等。

互連網(wǎng)絡(luò)可以表示為一個圖，圖的頂點(diǎn)表示系統(tǒng)中的處理器，邊表示處理器之間的通信鏈路。在實(shí)際的應(yīng)用系統(tǒng)中，設(shè)備或通信鏈路發(fā)生故障是在所難免的。當(dāng)網(wǎng)絡(luò)出現(xiàn)故障時(shí)，如何使得網(wǎng)絡(luò)能夠正常地工作，原網(wǎng)絡(luò)的性能如何得到最大程度的保持，即容錯性，是互連網(wǎng)絡(luò)研究必須考慮的問題。評估互連網(wǎng)絡(luò)容錯性的一個重要參數(shù)是連通度。圖G的連通度，記為[κ]（G），是使得圖G不連通或成為平凡圖所需刪除的最小頂點(diǎn)數(shù)。連通度常常用于評價(jià)一個系統(tǒng)的容錯性。這一評價(jià)存在明顯的缺點(diǎn)。它假設(shè)一個頂點(diǎn)的所有鄰接點(diǎn)可能同時(shí)出現(xiàn)故障。Esfahanian指出在實(shí)際多處理器系統(tǒng)中，一個無故障頂點(diǎn)的所有鄰接點(diǎn)同時(shí)出現(xiàn)故障的情況是幾乎不存在的[1]。為了討論更一般性的故障情形，Harary提出條件連通度的概念，對刪除故障頂點(diǎn)后的圖加上了一定的限制條件[2]。隨后，多種條件連通度被相繼提出并得以廣泛研究，比如g-超連通度與Rg-連通度。至今，關(guān)于容錯性的研究主要關(guān)注于單個頂點(diǎn)或者單個邊出現(xiàn)故障，沒有考慮一個頂點(diǎn)的狀態(tài)（故障與否）與它的鄰接點(diǎn)的狀態(tài)的關(guān)聯(lián)。實(shí)際應(yīng)用中，故障點(diǎn)和邊的分布可能比較集中或局部化。同樣，隨著片上網(wǎng)絡(luò)的提出和發(fā)展，一個或一些頂點(diǎn)出現(xiàn)故障，就認(rèn)為其所在“片”不可用。這些都啟發(fā)我們在研究容錯性時(shí)，不能僅考慮頂點(diǎn)故障，還應(yīng)考慮圖的某些子圖或子結(jié)構(gòu)故障，這類故障稱為結(jié)構(gòu)故障。

Lin等提出了結(jié)構(gòu)故障的概念，定義了兩種新的連通度，結(jié)構(gòu)連通度和子結(jié)構(gòu)連通度，并對超立方體網(wǎng)絡(luò)的這兩種連通度進(jìn)行了研究[3]。本文作者對k-元n-立方體網(wǎng)絡(luò)的結(jié)構(gòu)連通度進(jìn)行了研究[4]，同時(shí)對其結(jié)構(gòu)故障情況下的哈密頓性質(zhì)進(jìn)行了研究[5]。這里我們給出結(jié)構(gòu)故障下k-元n-立方體網(wǎng)絡(luò)的容錯哈密頓圈嵌入的模擬實(shí)驗(yàn)。

2 相關(guān)定義

一條路是哈密頓路當(dāng)且僅當(dāng)它通過G中的每一個頂點(diǎn)一次且僅一次。經(jīng)過圖G中所有頂點(diǎn)一次且僅一次的圈稱為哈密頓圈。一個圖如果包含有哈密頓圈，則稱該圖是哈密頓的。一個圖中如果任意兩個頂點(diǎn)之間都存在哈密頓路，則稱該圖G是哈密頓連通的?；ミB網(wǎng)絡(luò)的哈密頓性質(zhì)在網(wǎng)絡(luò)通信中具有重要的應(yīng)用，哈密頓路可以用于雙路徑或多路徑的路由算法，以減少或避免死鎖或擁塞的出現(xiàn)?？疾炀W(wǎng)絡(luò)可靠性和容錯性的一個重要方面就是其容錯哈密頓性質(zhì)，即故障網(wǎng)絡(luò)中是否存在無故障的哈密頓圈和哈密頓路，以及如何構(gòu)造。當(dāng)k是偶數(shù)時(shí)，k-元n-立方體網(wǎng)絡(luò)是二分圖，任何二分圖都不是哈密頓連通的，所以本文我們討論k是奇數(shù)情形下k-元n-立方體網(wǎng)絡(luò)的容錯哈密頓圈嵌入問題。

3 容錯哈密頓圈的構(gòu)造算法

在一個存在結(jié)構(gòu)故障的圖[Qkn]中，我們首先選擇一個無故障頂點(diǎn)s作為起始頂點(diǎn)，用頂點(diǎn)集合C記錄圈中的頂點(diǎn)。將頂點(diǎn)s加入C，然后查找任何一個與s相鄰但未加入圈C的頂點(diǎn)s1； 然后將頂點(diǎn)s1加入C，然后查找任何一個與s1相鄰但未加入圈C的頂點(diǎn)s2，…，直到到達(dá)一個頂點(diǎn)t，其所有的無故障鄰接點(diǎn)都已加入C為止。此時(shí)如果C中包含所有無故障頂點(diǎn)并且頂點(diǎn)t是頂點(diǎn)s的鄰接點(diǎn)，則構(gòu)造成功，C為哈密頓圈。否則選擇頂點(diǎn)s的其它無故障鄰接點(diǎn)，執(zhí)行上述過程，直到構(gòu)造成功或者頂點(diǎn)s的所有無故障鄰接點(diǎn)均查找完畢，返回失敗。算法hamiltonCycle給出了我們的構(gòu)造方法的偽代碼。

5 總結(jié)

本文我們結(jié)合前期研究的理論基礎(chǔ)，給出了在存在結(jié)構(gòu)故障的情況下，k-元n-立方體網(wǎng)絡(luò)容錯哈密頓圈嵌入的構(gòu)造算法，并編程實(shí)現(xiàn)了算法并給出了實(shí)驗(yàn)結(jié)果。在這些實(shí)驗(yàn)中，我們得到了相應(yīng)的數(shù)據(jù)，為互連網(wǎng)絡(luò)多播算法的應(yīng)用提供了依據(jù)。

參考文獻(xiàn)：

[1] Abdol-Hossein Esfahanian. Generalized measures of fault tolerance with application to n-cube networks[J]. IEEE Transactions on Computers， 1989， 38（11）：1586-1591.

[2] Frank Harary. Conditional connecticity[J]. Networks， 1983， 13（3）：347-357.

[3] Cheng-Kuan Lin， Lili Zhang， Dajin Wang and Jianxi Fan. Structure connectivity and substructure connectivity of hypercubes[J]. Theoretical Computer Science， 2016， 634： 97-107.

[4] Yali Lv， Jianxi Fan， D. Frank Hsu， Cheng-Kuan Lin. Structure Connectivity and Substructure Connectivity of k-Ary n-Cube Networks[J]. Information Sciences， 2018， 433：115-124.

[5] Yali Lv， Cheng-Kuan Lin， Jianxi Fan. Hamiltonian Cycle and Path Embeddings in k-Ary n-Cubes Based on Structure Faults[J]. The Computer Journal， 2017， 60（2）：159-179.

[通聯(lián)編輯：代影]