PMC模型下EQn,k和Q(d1,d2)的條件診斷度.pdf

1、計(jì)算機(jī)大規(guī)模處理數(shù)據(jù)有多種方式，伴隨著因特網(wǎng)的普及和云計(jì)算的高速發(fā)展，網(wǎng)絡(luò)與計(jì)算機(jī)更緊密的結(jié)合在了一起。在龐大的網(wǎng)絡(luò)環(huán)境中散布著大量的處理終端和服務(wù)器，發(fā)生錯(cuò)誤或者物理性故障是不可避免的。如何在發(fā)生故障時(shí)依靠網(wǎng)絡(luò)系統(tǒng)自身的能力進(jìn)行錯(cuò)誤判別，并且不額外增加系統(tǒng)資源的投入和消耗就變得非常具有現(xiàn)實(shí)意義。
　　應(yīng)用圖論中的無(wú)向圖理論對(duì)計(jì)算機(jī)網(wǎng)絡(luò)進(jìn)行抽象分析是普遍的方法。將網(wǎng)絡(luò)中的處理器抽象成頂點(diǎn)，將通信鏈路抽象成無(wú)向邊，即可構(gòu)造出系統(tǒng)所對(duì)

2、應(yīng)的圖。如果系統(tǒng)中某些處理器或者服務(wù)器錯(cuò)誤，那么如何通過(guò)一定的算法將錯(cuò)誤節(jié)點(diǎn)查找出來(lái)就是網(wǎng)絡(luò)診斷問(wèn)題。這一類算法已經(jīng)有過(guò)比較深入系統(tǒng)的研究，可以應(yīng)用于復(fù)雜網(wǎng)絡(luò)系統(tǒng)的診斷，也可以應(yīng)用于多處理器系統(tǒng)的診斷。
　　對(duì)于一些特殊網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究比較成熟，比如超立方圖Qn就已經(jīng)在IBM大型機(jī)上得到實(shí)際應(yīng)用。擴(kuò)展超立方體EQn,k是經(jīng)典的超立方體網(wǎng)絡(luò)Qn的一種改進(jìn)和推廣，廣義立方體Q(d1，d2，…，dn）是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的更一般化的推廣。他

3、們不但繼承了超立方體網(wǎng)絡(luò)的優(yōu)點(diǎn)，還在某些方面大大的改進(jìn)了網(wǎng)絡(luò)性質(zhì)。本文通過(guò)對(duì)小規(guī)模圖進(jìn)行分析歸納找到規(guī)律，再通過(guò)嚴(yán)格的數(shù)學(xué)證明來(lái)研究上述兩類網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的診斷性質(zhì)，得出診斷度:
　　(1)當(dāng)n≥3，k≥3的情況下，EQn,k的條件診斷度為4n-3。
　　(2)當(dāng)n≥3，k=2的情況下，EQn,k的條件診斷度為4n-7。
　　(3)當(dāng)d2≤2d1的情況下，有tc(Q(d1，d2))=2d1+2d2-7。
　　(4)