Regular sparse crossbar concentrators

A bipartite concentrator is a single stage sparse crossbar switching device that can connect any m of its n/spl ges/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 construc...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1998-03, Vol.47 (3), p.363-368
Main Authors: Guo, W., Oruc, A.Y.
Format: Article
Language:English
Subjects:
Adaptive systems
Applied sciences
Bipartite graph
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Exact sciences and technology
Multiprocessing systems
Multiprocessor interconnection networks
Software
Sorting
Switches
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A bipartite concentrator is a single stage sparse crossbar switching device that can connect any m of its n/spl ges/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.
ISSN:0018-9340
1557-9956
DOI:10.1109/12.660174