Accession Number : ADA136143

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

Descriptive Note : Interim research rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s) : Bhatt,S N ; Leighton,F T

PDF Url : ADA136143

Report Date : Sep 1983

Pagination or Media Count : 47

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)

Descriptors :   *Mathematical models, *Bifurcation(Mathematics), *Graphs, *Problem solving, *Chips(Electronics), Nodes, Combinatorial analysis, Configurations, Trees, Heuristic methods, Mesh, Decomposition, Three dimensional, Wafers, Fabrication, Grids

Subject Categories : Electrical and Electronic Equipment
      Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE