廣義的Shuffle-Exchange網路之最佳化全體對全體個人訊息交換演算法

Abstract

以往文獻中全體對全體個人訊息交換演算法提出的對象主要是針對hypercube、mesh 及torus 網路。在文獻[17]中，Yang 以及Wang 首先提出了針對多級式連接網路的全體對全體個人訊息交換演算法。他們的演算法是最佳的，但是只能在具有唯一路徑(unique-path)與自動找路(self-routable)性質的多級式連接網路中運作(例如：baseline、omega、banyan 網路)。必須注意到的是，文獻[17]中所有被考慮到的多級式連接網路都必須具有唯一路徑性質、而且滿足N 是2 的n+1 次方，其中N 表示多級式連接網路中輸入及輸出端的個數，2 表示所有的交換器為2×2大小，n+1 是多級式連接網路的層級數。就我們所知，目前尚未有人針對不具有唯一路徑性質、而且不滿足N 為2 的整數次方的多級式連接網路做過全體對全體個人訊息交換的研究。在文獻[12] 中， Padmanabhan 提出了廣義的shuffle-exchange 網路(GSEN)，允許N 不是2 的次方(在此N 可以是任一偶數)。而當N 為2 的次方時，GSEN 即為omega 網路(也就是原來的shuffle-exchange 網路)。既然GSEN 未必具有唯一路徑性質，Yang 和Wang 的最佳演算法就不一定適用。本篇論文的目的即在於提出兩個GSEN 之最佳化全體對全體個人訊息交換演算法。不同於Yang 和Wang 的演算法的是，我們捨棄對唯一路徑性質的要求。第一個演算法利用層級控制技術，且能應用在所有偶數N；在使用層級控制技術之下，我們將證明它是最佳的。相反地，第二個演算法並不使用層級控制技術，它只能應用在N 是偶數但不是4 的倍數的GSEN；我們也會證明它是最佳的。

Previous all-to-all personalized exchange algorithms are mainly for hypercube, mesh, and torus. In [17], Yang andWang first proposed an all-to-all personalized ex- change algorithm for multistage interconnection networks (MINs). Their algorithm is optimal and works for a class of unique-path, self-routable MINs (for example, baseline, omega, banyan networks). Do notice that all the MINs considered in [17] must have the unique-path property and must satisfy N = 2n+1, in which N is the number of inputs (outputs), 2 means all the switches are of size 2 × 2, and n + 1 is the number of stages in the MINs. To our knowledge, no one has studied all-to-all personalized exchange in MINs which do not have the unique-path property and do not satisfy N = 2^(n+1). In [12], Padmanabhan proposed the generalized shuffle-exchange network (GSEN), which allows N != 2^(n+1) (thus N can be any even number). A GSEN becomes an omega network (i.e., the shuffle-exchange network) when N = 2^(n+1). Since a GSEN is not necessarily a unique-path MIN, Yang and Wang’s optimal algorithm may not apply. The purpose of this thesis is to propose two optimal all-to-all personalized exchange algorithms for GSENs. Unlike Yang and Wang’s algorithm, we abandon the the requirement on the unique-path. The first algorithm uses the stage control technique and works for all even N. We will prove it is optimal when the stage control technique is assumed. On the contrary, the second algorithm does not use the stage control technique and works for all N such that N ≡ 2 (mod 4). We will prove that it is optimal.