Accession Number:

ADA210832

Title:

The Organization of Permutation Architectures with Bussed Interconnections

Descriptive Note:

Technical rept.

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

• Kilian, Joe
• Kipnis, Sholomo
• Leiserson, Charles E.

Report Date:

1989-01-01

Pagination or Media Count:

33.0

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, we show the number of pins per chip can often be reduced. We also consider uniform permutation architectures that realize permutations in several clock ticks, instead of one, and show that further savings 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.

Descriptors:

• *CIRCUIT INTERCONNECTIONS
• *PINS
• *ARCHITECTURE
• *PERMUTATIONS
• *SHARING
• *CHIPS(ELECTRONICS)
• *CLOCKS
• SHIFTING
• TICKS
• CYCLES
• JOINING
• GROUPS(MATHEMATICS)
• ORGANIZATIONS

Subject Categories:

• Electrical and Electronic Equipment
• Command, Control and Communications Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE