Regular sparse crossbar concentrators
- 1 March 1998
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 47 (3) , 363-368
- https://doi.org/10.1109/12.660174
Abstract
A bipartite concentrator is a single stage sparse crossbar switching device that can connect any m of its n驴m inputs to its m outputs, possibly without the ability to distinguish their order. Fat-and-slim crossbars were introduced recently to show that bipartite concentrators can be constructed with a minimum number of crosspoints for any number of inputs and outputs. We generalize these graphs to obtain bipartite concentrators with nearly a fixed fanout without altering their (n$-$m + 1)m crosspoint complexity. We also present an O(log n)-time algorithm to route arbitrary concentration assignments on this new family of fat-and-slim crossbars.Keywords
This publication has 6 references indexed in Scilit:
- Adaptive binary sorting schemes and associated interconnection networksIEEE Transactions on Parallel and Distributed Systems, 1994
- Fast self-routing permutation switching on an asymptotically minimum cost networkIEEE Transactions on Computers, 1993
- Eigenvalues and expandersCombinatorica, 1986
- Lower Bounds on Crosspoints in ConcentratorsIEEE Transactions on Computers, 1982
- Binomial Switching Networks for Concentration and DistributionIEEE Transactions on Communications, 1977
- SuperconcentratorsSIAM Journal on Computing, 1977