A Survey of Algorithms for Integrating Wafer-Scale Systolic Arrays.

Abstract

VLSI technologists are fast developing wafer-scale integration. Rather than partitioning a silicon wafer into chips as is usually done, the idea behind wafer-scale integration is to assemble an entire system (or network of chips) on a single wafer, thus avoiding the costs and performance loss associated with individual packaging of chips. A major problem with assembling a large system of microprocessors on a single wafer, however, is that some of the processors, or cells, on the wafer are likely to be defective. This paper surveys practical procedures for integrating 'around' such faults. The procedures are designed to minimize the length of the longest wire in the system, thus minimizing the communication time between cells. Although the underlying network problems are NP-complete, all the procedures can be proved reliable by assuming a probabilistic model of cell failure. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1986
Accession Number
ADA171623

Entities

People

  • Charles Leiserson
  • Tom Leighton

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Advanced Electronics

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computer Programming
  • Computer Science
  • Computers
  • Engineering
  • Information Processing
  • Linear Arrays
  • Massachusetts
  • Mathematics
  • Models
  • Operations Research
  • Probabilistic Models
  • Probability
  • Random Variables
  • Three Dimensional
  • Two Dimensional

Readers

  • Graph Algorithms and Convex Optimization.
  • Integrated Circuit Design and Technology.
  • Systems Analysis and Design