### 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 = 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 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 2^{n} 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 language | English |
---|---|

Title of host publication | Proceedings of the 8th International Conference on Networks, ICN 2009 |

Pages | 185-190 |

Number of pages | 6 |

DOIs | |

State | Published - 23 Jul 2009 |

Event | 8th International Conference on Networks, ICN 2009 - Gosier, Guadeloupe Duration: 1 Mar 2009 → 6 Mar 2009 |

### Publication series

Name | Proceedings of the 8th International Conference on Networks, ICN 2009 |
---|

### Conference

Conference | 8th International Conference on Networks, ICN 2009 |
---|---|

Country | Guadeloupe |

City | Gosier |

Period | 1/03/09 → 6/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

*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