All-to-all personalized exchange algorithms in generalized shuffle-exchange networks

Well Y. Chou, Richard B. Chen, Chiuyuan Chen*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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 = 2n, 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 even 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 2n rounds. We propose an algorithm which uses a variation of stage control and works for all N ≡ 2 (mod 4). We will prove that our algorithm takes N rounds and therefore is optimal.

Original languageEnglish
Title of host publicationProceedings of the 8th International Conference on Networks, ICN 2009
Pages185-190
Number of pages6
DOIs
StatePublished - 23 Jul 2009
Event8th International Conference on Networks, ICN 2009 - Gosier, Guadeloupe
Duration: 1 Mar 20096 Mar 2009

Publication series

NameProceedings of the 8th International Conference on Networks, ICN 2009

Conference

Conference8th International Conference on Networks, ICN 2009
CountryGuadeloupe
CityGosier
Period1/03/096/03/09

Fingerprint Dive into the research topics of 'All-to-all personalized exchange algorithms in generalized shuffle-exchange networks'. Together they form a unique fingerprint.

  • Cite this

    Chou, W. Y., Chen, R. B., & Chen, C. (2009). All-to-all personalized exchange algorithms in generalized shuffle-exchange networks. In Proceedings of the 8th International Conference on Networks, ICN 2009 (pp. 185-190). [4976672] (Proceedings of the 8th International Conference on Networks, ICN 2009). https://doi.org/10.1109/ICN.2009.58