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

Routing Permutations in the Baseline Network and in the Omega Network

陳子鴻(Tzu-Hung Chen)

指導教授 ： 陳秋媛

國立交通大學/理學院/應用數學系所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00034

摘要

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

關鍵字

多級式連接網路 ； 設定連線 ； 排列 ； 半排列 ； Baseline 網路 ； Omega 網路

並列摘要

無資料

並列關鍵字

Multistage interconnection network ； Routing ； Permutation ； Semipermutation ； Baseline network ； Omega network

參考文獻

[1] V. E. Benes, “Optimal rearrangeable multistage connecting networks,” Bell System Tech. J., vol. 43, pp. 1641-1656, 1964.

[2] H. Cam, “Rearrangeability of (2n − 1)-stage shuffle-exchange networks,” SIAM J. Comput., vol. 32, no. 3, pp. 557-585, 2003.

[3] Z. Chen, Z. Liu, and Z. Qiu, “Bidirectional shuffle-exchange network and tag-based routing algorithm,” IEEE Commun. Lett., vol. 7, no. 3, pp. 121-123, 2003.

[4] S. J. Gu, “Nonblocking conditions for self-routing Benes network,” in Proc. of IEEE TENCON’93, vol. 3, pp. 203-206, 1993.

[5] S.-T. Huang and S. K. Tripathi, “Finite state model and compatibility theory: new analysis tools for permutation networks,” IEEE Trans. Comput., vol. 35, no. 7, pp. 591-601, 1986.