|標題:||All-to-All Personalized Exchange Algorithms in Generalized Shuffle-exchange Networks|
|作者:||Chou, Well Y.|
Chen, Richard B.
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  and also Massini  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  and  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 , 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  and  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.|
|期刊:||2009 EIGHTH INTERNATIONAL CONFERENCE ON NETWORKS|
|Appears in Collections:||Conferences Paper|
Files in This Item: