Hypermesh網(wǎng)絡(luò)的容錯(cuò)與診斷.pdf

1、多處理器系統(tǒng)是超級(jí)計(jì)算機(jī)的主要實(shí)現(xiàn)方式.目前超級(jí)計(jì)算機(jī)有幾萬(wàn)甚至幾十萬(wàn)個(gè)處理器節(jié)點(diǎn).這些處理器節(jié)點(diǎn)之間的連接方式稱為互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)(互連網(wǎng)絡(luò)).互連網(wǎng)絡(luò)是決定超級(jí)計(jì)算機(jī)性能的一個(gè)關(guān)鍵因素.關(guān)于互連網(wǎng)絡(luò)的一些圖論參數(shù)的研究對(duì)多處理器系統(tǒng)的設(shè)計(jì)和維護(hù)都有著重要的理論意義.隨著多處理器互連網(wǎng)絡(luò)中處理器的數(shù)目的不斷增加，難免會(huì)有一些處理器發(fā)生故障.因此需要考察其可靠性和研究其故障診斷性能.連通度、限制連通度、超連通度、額外連通度是度量互連網(wǎng)絡(luò)

2、可靠性的一些重要的理論參數(shù).系統(tǒng)級(jí)診斷是多處理器系統(tǒng)故障診斷的一種重要方法.PMC模型是系統(tǒng)級(jí)診斷中的一個(gè)重要模型，是在1967年由Prearata，Metze和Chien首先提出的.k元n維Hypermesh網(wǎng)絡(luò)擁有許多較好的性質(zhì)，如點(diǎn)和邊對(duì)稱、較小的直徑、高連通性、簡(jiǎn)單的路由算法等,因此被看作下一代超級(jí)計(jì)算機(jī)可能的拓?fù)浣Y(jié)構(gòu).在本文中，我們研究了k元n維Hypermesh網(wǎng)絡(luò)的可靠性和可診斷性能.主要結(jié)果如下：
　　1)當(dāng)n≥4

3、，k≥3時(shí)，k元n維Hypermesh網(wǎng)絡(luò)的超連通度是2n(k-1)-k；當(dāng)n≥5，k≥3時(shí)，它的超邊連通度是2n(k-1)-2；
　　2)當(dāng)n≥5，k≥3時(shí)，k元n維Hypermesh網(wǎng)絡(luò)的額外邊連通度是2n(k-1)-2；當(dāng)n≥7，k≥4時(shí)，它的2-額外邊連通度是3n(k-1)-6；
　　3)當(dāng)k≥2，n≥3時(shí)，k元n維Hypermesh網(wǎng)絡(luò)在PMC模型下它的t-可診斷數(shù)是n(k-1)；當(dāng)k≥2，n≥3時(shí)，它的t/t-可