A Network Flow Approach to the Wafer Scale Integration of vlsi Arrays.

Abstract

An algorithm is described for reconfiguring a 2-dimensional VLSI array on a silicon wafer that has some faulty cells. The functional cells of the array are interconnected in order to simulate a fault-free array of smaller size, where the interconnection wires are routed inside horizontal and vertical channels, according to the Manhattan model. The concept of simulation distance is introduced, and it is shown to be related to the length of the longest interconnection wire. The algorithm makes use of network flow techniques in order to find wiring with minimum simulation distance. This results in a practical heuristic for minimum simulation distance. This results in a practical heuristic for minimizing the maximum wire length. The complexity and performance of this algorithm are also discussed in the paper. Keywords: Network Flow, VLSI Array, Fault Tolerance.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1985
Accession Number
ADA161345

Entities

People

  • Bruno Codenotti
  • Roberto Tamassia

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Advanced Electronics

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Computational Science
  • Computations
  • Computer Science
  • Contracts
  • Fault Tolerance
  • Graphs
  • Illinois
  • Probabilistic Models
  • Security
  • Simulations
  • Two Dimensional

Fields of Study

  • Engineering

Readers

  • Electrical Engineering
  • Graph Algorithms and Convex Optimization.
  • Operations Research