分散式計算方法

Abstract

隨著半導體技術的發展及計算機的普遍使用，現今個人電腦和工作站（WORKSTATION ）已日益普及，而且它們的計算能能力也相當於過去的大型電腦（MAINFRAIMS），因 此聯結網路的技術，使得構造一個包含無數個運算單元的分散式系統已成為實際可行 。 分散式系統的計算方法與傳統集中式的計算方法有下列幾點的基本不同（Ⅰ）它的控 制訊息是同時分散於不同的運算單元，而且沒有單一的運算單元點可以擁有完整的訊 息；（Ⅱ）它運算結果的順序是不可預期的；（Ⅲ）控制及運算同時在不同的獨立運 算單元進行；（Ⅳ）計算方法績效的評估是訊息的數量及傳播時間的延遲，而不是傳 統的CPU 使用時間。 在本篇論文□，我們在分散式計算的模型下提出了幾個圖型問題的計算方法，包括最 長路徑，拓撲撲排序，全對間最短路徑，最大流量，推銷員旅行路徑等問題。另外我 們也計對網路拓撲的改變所引發的問題，提出應對解決的計算方法。