廣義的 Shuffle-Exchange 網路之最佳全體對全體私人化交換

Abstract

全體對全體私人化交換溝通（all-to-all personalized exchange communication）出現在許多平行與分散式處理系統之應用。在文獻〔12〕中，Yang以及Wang運用拉丁方陣的技巧，針對了具有unique-path以及self-routable性質的多級式連接網路，提出了時間複雜度為 的最佳全體對全體私人化交換演算法。所有在文獻〔12〕中被討論到的網路（包括shuffle-exchange網路），皆滿足 （ 表示多級式網路的輸入及輸出端的個數， 是多級式網路的階級數）。值得注意的是，Yang以及Wang的演算法要求多級式網路中的每一階級裡的所有交換器的狀態都必須相同；換句話說，Yang以及Wang的演算法使用階級控制技術。在文獻〔7〕中，Padmanabham提出了廣義的shuffle-exchange網路；在廣義的shuffle-exchange網路中， ，不再要求 。由於廣義的shuffle-exchange網路不一定具有unique-path性質，因此無法使用Yang以及Wang的演算法。本論文的目的即在於：針對廣義的shuffle-exchange網路，提出兩個最佳全體對全體私人化交換演算法。和Yang以及Wang的演算法不同的是，我們的演算法沒有使用拉丁方陣，也不要求網路要具有unique-path性質。我們的第一個演算法使用階級控制技術，而且適用於任何的 ；我們證明了：當要求使用階級控制技術、而且 時，此演算法是最佳的。我們的第二個演算法不使用階級控制技術、而且只適用於 時；我們證明了，此演算法是最佳的。