廣義的Shuffle-exchange網路在三種不同的訊息傳送演算法之效益分析

Abstract

Shuffle-exchange網路是一個很常被使用到的多級式連接網路的架構。在shuffle-exchange網路中，如果每一個交換元件的大小是 ，則網路的節點數會是k的指數。在文獻[10]中，Padmanbhan打破了節點數是k的指數的這個限制，提出了廣義的shuffle-exchange網路。Padmanbhan同時也為廣義的shuffle-exchange網路提出了一個聰明的、依據標記的訊息傳送演算法。在文獻[2]中，Chen、Liu、和Qui將廣義的shuffle-exchange網路再推廣為連線都是雙向的，而且他們也為廣義的shuffle-exchange網路中的反向網路提出了一個依據標記的訊息傳送演算法。最近Chen和Lou也為廣義的shuffle-exchange網路中的反向網路提出了一個依據標記的訊息傳送演算法。由於多級式連接網路允許一個以上的處理機同時傳送它們的訊息，因此當兩個傳輸之要求在廣義的shuffle-exchange網路中同時出現時，衝突可能發生。這篇論文的目的就是去分析和比較，當兩個傳輸之要求在廣義的shuffle-exchange網路中同時出現時，前面所提的三種演算法之效益。

The shuffle-exchange network is a popular architecture for multistage interconnection networks. The number of nodes in a shuffle-exchange network is usually a power of k if each switching element in the network is of size kxk. In [10] Padmanbhan relaxed the restriction that the number of nodes must be a power of k and proposed the general shuffle-exchange network (GSEN). Padmanbhan also proposed an elegant tag-based routing algorithm for the GSEN. Later, in [2], Chen, Liu, and Qui enhanced the GSEN with bidirectional links and they proposed a tag-based routing algorithm for the backward network of the GSEN. Recently, Chen and Lou [3] also proposed an tag-based routing algorithm for the backward network of the GSEN. A multistage interconnection network enables processors to send their messages concurrently. When two routing requests occur simultaneously in the GSEN, a conflict may occur. The purpose of this thesis is to analyze the performance of the above three tag-based routing algorithms when there are two rounting requests.