格網(wǎng)網(wǎng)絡(luò)的容錯(cuò)路由算法研究.pdf

1、最近幾年，大規(guī)模多處理器系統(tǒng)在計(jì)算領(lǐng)域起到了越來(lái)越重要的作用。為了解決大型的應(yīng)用問(wèn)題必須要求多處理器系統(tǒng)中的每個(gè)處理器協(xié)同工作。這就要求在處理器之間需要進(jìn)行數(shù)據(jù)交換，即在整個(gè)系統(tǒng)中的每個(gè)節(jié)點(diǎn)需要發(fā)送和接受數(shù)據(jù)。因此，通信的效率對(duì)整個(gè)多處理器系統(tǒng)的性能起著至關(guān)重要的作用。 同時(shí)，隨著處理單元的增多，系統(tǒng)部件出錯(cuò)的可能性也隨之增加。容錯(cuò)是指在部件失效的情況下網(wǎng)絡(luò)運(yùn)作的能力，然而容錯(cuò)技術(shù)的實(shí)現(xiàn)往往是以巨大的性能降低為代價(jià)，所以設(shè)計(jì)具有

2、容錯(cuò)能力的高性能通信技術(shù)是一個(gè)極具挑戰(zhàn)性的問(wèn)題。路由是其中的一種通信方式，即把數(shù)據(jù)從一個(gè)源節(jié)點(diǎn)發(fā)送到一個(gè)目的節(jié)點(diǎn)的一種通信過(guò)程。為了保證多處理器系統(tǒng)的高性能和高可靠性，必須設(shè)計(jì)具有良好容錯(cuò)能力的路由算法。 網(wǎng)格拓?fù)浣Y(jié)構(gòu)是多處理器系統(tǒng)中很流行的一種互連網(wǎng)絡(luò)結(jié)構(gòu)。它具有很多優(yōu)點(diǎn)，如拓?fù)湫螤詈?jiǎn)單、直觀，很適合進(jìn)行大規(guī)模集成；另外它具有良好的可擴(kuò)展性。故許多商用和試驗(yàn)的多處理器系統(tǒng)都采用網(wǎng)格拓?fù)浣Y(jié)構(gòu)。本文就是在網(wǎng)格結(jié)構(gòu)的多處理器系統(tǒng)上研

3、究其容錯(cuò)路由。 首先介紹了多處理器中容錯(cuò)路由算法研究意義和作用，并介紹了容錯(cuò)路由研究的主要內(nèi)容和相關(guān)的基礎(chǔ)知識(shí)。在介紹基于網(wǎng)格的新的容錯(cuò)算法之前，介紹了容錯(cuò)路由研究領(lǐng)域里一些著名算法。基于這些算法，分析它們存在的不足，設(shè)計(jì)了兩個(gè)新型的基于網(wǎng)格結(jié)構(gòu)的容錯(cuò)路由算法。第一個(gè)算法是基于二維網(wǎng)格的自適應(yīng)和最小容錯(cuò)路由算法。提出了二維網(wǎng)格中存在最小通路的一個(gè)充分必要條件。通過(guò)在網(wǎng)格中建立最小通路區(qū)(RMP) 來(lái)，該算法能確保路由路徑的最優(yōu)性