Browsing by Author "Chen, Richard B."

Now showing 1 - 2 of 2

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.
Optimal all-to-all personalized exchange in d-nary banyan multistage interconnection networks
(2007-10-01)
Liu, Victor W.
;
Chen, Chiuyuan
;
Chen, Richard B.
;
應用數學系
;
Department of Applied Mathematics
All-to-all personalized exchange occurs in many important applications in parallel processing. In the past two decades, algorithms for all-to-all personalized exchange were mainly proposed for hypercubes, meshes, and tori. Recently, Yang and Wang (IEEE Trans Parallel Distrib Syst 11:261-274, 2000) proposed an optimal all-to-all personalized exchange algorithm for binary (each switch is of size 2x2) banyan multistage interconnection networks. It was pointed out in Massini (Discret Appl Math 128:435-446, 2003) that the algorithm in Yang, Wang (IEEE Trans Parallel Distrib Syst 11:261-274, 2000) depends on the network topologies and requires pre-computation and memory allocation for a Latin square. Thus in (Discret Appl Math 128:435-446, 2003), Massini proposed a new optimal algorithm, which is independent of the network topologies and does not require pre-computation or memory allocation for a Latin square. Unfortunately, Massini's algorithm has a flaw and does not realize all-to-all personalized exchange. In this paper, we will correct the flaw and generalize Massini's algorithm to be applicable to d-nary (each switch is of size dxd) banyan multistage interconnection networks.