Browsing by Author "Chou, Well Y."

Now showing 1 - 4 of 4

All-to-All Personalized Exchange Algorithms in Generalized Shuffle-exchange Networks
(2009)
Chou, Well Y.
;
Chen, Richard B.
;
Chen, Chiuyuan
;
應用數學系
;
Department of Applied Mathematics
All-to-all personalized exchange (ATAPE) occurs in many parallel applications. Previous ATAPE algorithms were mainly developed for hypercube, mesh, and torus networks. Recently; Yang and Wang [8] and also Massini [4] proposed an alternative approach to ATAPE by using multistage interconnection. networks (MINs); they proposed new ATAPE algorithms for a class of unique-path,.self-routable MINs (for example, baseline, shuffle-exchange (or omega), banyan network, and the reverse networks of these networks). However, the algorithms in [4] and [8] require that the given. MIN must have unique-path property and satisfy N = 2(n), in which N is the number of inputs (outputs) and n is the number of stages in the MIN. In [5], Padmanabhan proposed the generalized shuffle-exchange network (GSEN), which allows N to be any every number. Since the GSEN is not a unique-path MIN, the algorithms in [4] and [8] do not work on it. The purpose of this paper is to consider ATAPE in MINs without unique-path property. To our knowledge, no one has studied ATAPE in this type of MINs. We prove that under stage control technique, ATAPE algorithms for GSENs require at least 2(n) rounds. We propose an algorithm. which uses a variation, of stage control and works for all N equivalent to 2 (mod 4). We will prove that our algorithm takes N rounds and therefore is optimal.
All-to-all personalized exchange in generalized shuffle-exchange networks
(2010-03-28)
Chou, Well Y.
;
Chen, Chiuyuan
;
應用數學系
;
Department of Applied Mathematics
An all-to-all communication algorithm is said to be optimal if it has the smallest communication delay. Previous all-to-all personalized exchange algorithms are mainly for hypercube, mesh, and torus. In Yang and Wang (2000) [13], Yang and Wang proved that a multistage interconnection network (MIN) is a better choice for implementing all-to-all personalized exchange and they proposed optimal all-to-all personalized exchange algorithms for MINs. In Massini (2003)[9], Massini proposed a new optimal algorithm for MINs, which is independent of the network topology. Do notice that the algorithms in [9] and [13] work only for MINs with the unique path property (meaning that there is a unique path between each pair of source and destination) and satisfying N = 2(n), in which N is the number of processors, 2 means all the switches are of size 2 x 2, and n is the number of stages. In Padmanabhan (1991) [10], Padmanabhan proposed the generalized shuffle-exchange network (GSEN), which is a generalization of the shuffle-exchange network. Since a GSEN does not have the unique path property, the algorithms in [9] and [13] cannot be used. The purpose of this paper is to consider the all-to-all personalized exchange problem in GSENs. An optimal algorithm and several bounds will be proposed. (C) 2010 Published by Elsevier B.V.
Constructing independent spanning trees for hypercubes and locally twisted cubes
(2009)
Liu, Yi-Jiun
;
Chou, Well Y.
;
Lan, James K.
;
Chen, Chiuyuan
;
應用數學系
Multiple independent spanning trees (ISTs) have applications to fault-tolerant and data broadcasting in interconnections. Thus the designs of multiple ISTs in several classes of networks have been widely investigated. There are two versions of the n ISTs conjecture. The vertex (edge,) conjecture is that any n-connected (n-edge-connected) graph has n vertex-ISTs (edge-ISTs) rooted at an arbitrary vertex r. Note that the vertex conjecture implies the edge conjecture. Recently, Hsieh and Tu proposed an algorithm to construct n edge-ISTs rooted at vertex 0 for the n-dimensional locally twisted cube (LTQ(n)), which is a variant of the n-dimensional hypercube (Q(n)). Since LTQ(n) is not vertex-transitive, Hsieh and Tu's result does not solve the edge conjecture for LTQ(n). In the paper we confirm the vertex conjecture (and hence also the edge conjecture) for LTQ(n) by proposing an algorithm to construct n vertex-ISTs rooted at any vertex. We also confirm the vertex (and also the edge) conjecture for Q(n). To the best of our knowledge, our algorithm is the first algorithm that can construct n vertex-ISTs rooted at any vertex for both LTQ(n) and Q(n).
Constructing independent spanning trees for locally twisted cubes
(2011-05-13)
Liu, Yi-Jiun
;
Lan, James K.
;
Chou, Well Y.
;
Chen, Chiuyuan
;
應用數學系
The independent spanning trees (ISTs) problem attempts to construct a set of pairwise independent spanning trees and it has numerous applications in networks such as data broadcasting, scattering and reliable communication protocols. The well-known ISTs conjecture, Vertex/Edge Conjecture, states that any n-connected/n-edge-connected graph has n vertex-ISTs/edge-ISTs rooted at an arbitrary vertex r. It has been shown that the Vertex Conjecture implies the Edge Conjecture. In this paper, we consider the independent spanning trees problem on the n-dimensional locally twisted cube LTQ(n). The very recent algorithm proposed by Hsieh and Tu (2009) [12] is designed to construct n edge-ISTs rooted at vertex 0 for LTQ(n). However, we find out that LTQ(n) is not vertex-transitive when n >= 4; therefore Hsieh and Tu's result does not solve the Edge Conjecture for LTQ(n),,. In this paper, we propose an algorithm for constructing n vertex-ISTs for LTQ(n); consequently, we confirm the Vertex Conjecture (and hence also the Edge Conjecture) for LTQ(n),. (C) 2011 Elsevier B.V. All rights reserved.