在Baseline 網路和Omega 網路中設定排列的連線

Abstract

在一個多級式連接網路中設定排列的連線，是平行和交換式計算系統中的一個重要運算。令N 為給定的多級式連接網路的輸入及輸出端的個數。一個眾所皆知的結果是：一個多級式連接網路不一定能實現所有N!種可能的排列。如果一個排列能在一個多級式連接網路中被實，則我們稱這個排列在該多級式連接網路是可被允許的。一些研究人員在多級式連接網路中增加額外的硬體，以實現所有N!種可能的排列（見文獻8）；另一些研究人員則考慮增加額外的步驟來實現所有N!種可能的排列（見文獻16, 17）。本篇論文的目的有二，第一個目的是：提出一個演算法來判斷一個排列在Baseline 網路中是否是可被允許的、以及提出一個演算法來判斷一個排列在Omega 網路中是否是可被允許的；第二個目的是：將文獻17 中的演算法實作成電腦程式。