Efficient networks for realizing point-to-point assignments in parallel processors
- 2 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 487-490
- https://doi.org/10.1109/spdp.1992.242705
Abstract
Point-to-point assignments constitute a significant part of interprocessor and processor/memory communications in parallel computers. Using a combination of multiplexing, distribution, and concentration schemes, the authors present the first O(n) cost network that can realize all n-element point-to-point assignments, including permutation assignments, in O(lg/sup 2/ n) time. The design of an n-input connector with O(n) cost, O(lg/sup 2/ n) depth, and O(lg/sup 2/ n) routing time is described. The key concept behind this connector is a multiplexing scheme that permits the cost of the radix permuter described by C.Y. Jan and A.J. Oruc to be reduced to O(n) without increasing its routing time.<>Keywords
This publication has 3 references indexed in Scilit:
- A self-routing permutation networkJournal of Parallel and Distributed Computing, 1990
- Parallel Algorithms to Set Up the Benes Permutation NetworkIEEE Transactions on Computers, 1982
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971