對基于不規(guī)則拓?fù)涞牟⑿邢到y(tǒng)通信中路由算法的研究.pdf

1、并行分布式系統(tǒng)是計算機(jī)行業(yè)和日常生活中不斷增長的應(yīng)用領(lǐng)域，特別是在分布式計算、工業(yè)控制、軍事航天領(lǐng)域、以及商務(wù)應(yīng)用等。對實(shí)現(xiàn)有如此關(guān)鍵性應(yīng)用的分布式系統(tǒng)來說，努力提高其可用性、可靠性、適用性，具有十分重要的現(xiàn)實(shí)意義。工作站集群（NOWs）被認(rèn)為是一種低價并行計算機(jī)的替代品，越來越廣泛應(yīng)用于各種分布式計算和協(xié)同作業(yè)之中。 而在一個實(shí)時系統(tǒng)中，必須滿足有限響應(yīng)時間的要求，否則將導(dǎo)致嚴(yán)重的后果。因此有效的進(jìn)程間通信機(jī)制是分布式系統(tǒng)中的

2、一個不可或缺的組成部分，對分布式系統(tǒng)的性能是至關(guān)重要的。 以往的分布式并行計算機(jī)系統(tǒng)大多采用規(guī)則的拓?fù)渚W(wǎng)絡(luò)，這種處理器之間的連接方式下的路由就變得固定而且相對容易，卻帶來了容錯性差等缺點(diǎn)，只要有一個節(jié)點(diǎn)出現(xiàn)差錯，就導(dǎo)致整個網(wǎng)絡(luò)的不可用?；陂_關(guān)交換的不規(guī)則拓?fù)渚W(wǎng)絡(luò)互連就提供了布線的靈活性、可測量性和遞增可擴(kuò)充性，而這些特性正是分布式系統(tǒng)所需要的環(huán)境。然而，正是由于網(wǎng)絡(luò)的不規(guī)則也使系統(tǒng)中路由和死鎖的避免變得十分的復(fù)雜。設(shè)計網(wǎng)絡(luò)路由

3、的目的也變得十分的明確，就是在防止死鎖和增加自適應(yīng)性的基礎(chǔ)之上，提高其運(yùn)行效率。 已經(jīng)商業(yè)化的產(chǎn)品里，分布式UP*/DOWN*路由算法被用于實(shí)踐之中。因?yàn)槠浔容^呆板和非最短路徑性，人們又對它提出了種種改進(jìn)措施。除此之外，為進(jìn)一步提高性能，蟲孔交換和虛通道等相關(guān)技術(shù)也被用于并行機(jī)的通信之中。 本文在介紹了當(dāng)前人們已經(jīng)提出的幾種消息傳遞方式的基礎(chǔ)之上，使用蟲孔交換，結(jié)合已有算法的優(yōu)點(diǎn)，提出自己的三段式路由方案，用三個不同的路