Sharp-Looking Geometric Partitioning

Abstract

A new technique, named SHARP, is presented for the partitioning of Very-Large-Scale Integration (VLSI) integrated circuits. SHARP is a hill-climbing heuristic that is designed to be incorporated into a partitioning-based placement algorithm. The method is more strongly influenced by the geometry of the layout surface than other partitioning methods, such as min-cut partitioning and the quadrisection approach. It is tuned for intra-package connections rather than inter-package connections. The method is named SHARP because the layout circuit surface is decomposed geometrically into nine regions in a manner that resembles a musical "#", or sharp sign. Its other important features include a multi-objective function that more accurately represents wire usage than the standard min-cut criterion, and extensive use of Steiner trees. A series of experiments demonstrates that the SHARP technique produces very high quality partitions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1991
Accession Number
ADA466431

Entities

People

  • J. P. Cohoon
  • S. Bapat

Organizations

  • University of Virginia

Tags

Communities of Interest

  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Annealing
  • Automation
  • Circuits
  • Classification
  • Climbing
  • Computer Science
  • Computer-Aided Design
  • Decomposition
  • Genetic Algorithms
  • Information Science
  • Integrated Circuits
  • Networks
  • Standards
  • Terminals
  • Very Large Scale Integration

Readers

  • Graph Algorithms and Convex Optimization.
  • Integrated Circuit Design and Technology.
  • Operations Research