Layouts for the Shuffle-Exchange Graph Based on the Complex Plane Diagram.

Abstract

The shuffle-exchange graph is one of the best structures known for parallel computation. Among other things, a shuffle-exchange computer can be used to compute discrete Fourier transforms, multiply matrices, evaluate polynomials, perform permutations and sort lists. The algorithms needed for these operations are extremely simple and many require no more than logarithmic time and constant space per processor. In this paper, we analyze the algebraic structure of the shuffle-exchange graph in order to find area-efficient embeddings of the graph in a two-dimensional grid. The results are applicable to the design of very large Scale Integration (VLSI) circuit layouts for a shuffle-exchange computer.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1982
Accession Number
ADA121596

Entities

People

  • Frank Thomson Leighton
  • Gary L. Miller
  • Margaret Lepley

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Discrete Fourier Transforms
  • Distribution Functions
  • Embedding
  • Large Scale Integration
  • Massachusetts
  • Mathematical Models
  • Military Research
  • Models
  • Parallel Computing
  • Polynomials
  • Random Variables
  • Two Dimensional
  • Very Large Scale Integration

Readers

  • Approximation Theory.
  • Integrated Circuit Design and Technology.
  • Regression Analysis.

Technology Areas

  • Space