A Layout for the Shuffle-Exchange Network.
Abstract
This paper describes a technique for producing a VLSI layout of the shuffle-exchange graph. It is based on the layout procedure which lays out a graph by bisecting the graph, recursively laying out the two halves, and then combining the two sublayouts. The area of the layout is related to the number of edges that must be cut to bisect the graph. For the shuffle-exchange graph on n vertices, we present a bisection schema for which the above procedure yields an O(n-squared/lg n) area layout when n = 2 to the K power and k is a power of two. The bisection involves a mapping from vertices of the graph to polynomials, and the polynomials are subsequently evaluated at complex roots of unity. Incidental to this construction is a result on the combinatorial problem of necklace enumeration. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 18, 1980
- Accession Number
- ADA096368
Entities
People
- Charles E. Leiserson
- Dan Hoey
Organizations
- Carnegie Mellon University