The Organization of Permutation Architectures with Bussed Interconnections
Abstract
This paper explores the problem of efficiently permuting data stored in VLSI chips in accordance with a predetermined set of permutations. By connecting chips with shared bus interconnections, as opposed to point-to-point interconnections, the number of pins per chip can often be reduced. For example, for infinitely many n, permutation architectures are exhibited with Sq. rt. n pins per chip that can realize any of the n cyclic shifts on n chips in one clock tick. When the set of permutations forms a group with p elements, any permutation in the group can be realized in one clock tick by an architecture with 0 (Sq. rt. (p1g p) pins per chip. When the permutation group is abelian, 0 (Sq. rt. p) pins suffice. These results are all derived from a mathematical characterization of uniform permutation architectures based on the combinatorial notion of a difference cover. Consider uniform permutation architectures that realize permutations in several clock ticks, instead of one, further savings is shown in the number of pins per chip can be obtained. Keywords: Barrel shifter, Bussed interconnections, Cyclic shifter, Difference cover, Difference set, Group theory, Permutation, Permutation architecture, Projective plane, Special-purpose architecture, Uniform architecture, Reprints.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 14, 1987
- Accession Number
- ADA208817
Entities
People
- Charles E. Leiserson
- Joe Kilian
- Shlomo Kipnis
Organizations
- Massachusetts Institute of Technology