A Framework for Solving VLSI (Very Large Scale Integration) Graph Layout Problems.

Abstract

This paper introduces a new divide- and conquer framework for VLSI graph layout. Universally close upper and lower bounds are obtained for important cost functions such as layout area and propagation delay. The framework is also effectively used to design regular and configurable layouts, to assemble large networks of processors using restructurable chips, and to configure networks around faulty processors. It is also shown how good graph partitioning heuristics may be used to develop a probably good layout strategy. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1983
Accession Number
ADA136143

Entities

People

  • F. T. Leighton
  • S. N. Bhatt

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Advanced Electronics
  • C4I
  • Energy and Power Technologies
  • Weapons Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Circuits
  • Computer Science
  • Computers
  • Crossings
  • Decomposition
  • Electrical Engineering
  • Fabrication
  • Information Processing
  • Integrated Circuits
  • Large Scale Integration
  • Mathematics
  • Separators
  • Three Dimensional
  • Trees (Data Structures)
  • Two Dimensional
  • Very Large Scale Integration

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Integrated Circuit Design and Technology.
  • Operations Research