Regular sparse crossbar concentrators

Abstract

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.