對基于不規(guī)則拓撲的并行系統(tǒng)通信中路由算法的研究.pdf

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

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

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