The Parallel Decomposition and Implementation of an Integrated Circuit Global Router

Abstract

Better quality automatic layout of integrated circuit can be obtained by combining the placement and routing phases so that routing is used as the cost function for placement optimization. Conventional routers are too slow to make this feasible, and so this paper presents a parallel decomposition and implementation of an integrated circuit global router. The LocusRoute router is divided into three orthogonal 'axes' of parallelism: routing several wires at once, routing segments of a wire in parallel, and dividing up the potential routes of a segment among different processors to be evaluated. The implementation of two of these approaches achieve significant speedup - wire-by- wire parallelism attains speedups from 6.9 to 13.6 using sixteen processors, and route-by-route achieves up to 4.6 using eight processors. When combined, these approaches can potentially provide speedups of as much as 55 times.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1987
Accession Number
ADA207228

Entities

People

  • Jonathan Rose

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Automatic
  • Circuits
  • Computations
  • Computers
  • Decomposition
  • Degradation
  • Integrated Circuits
  • Integrated Systems
  • Iterations
  • Measurement
  • Parallel Computing
  • Parallel Processing
  • Permutations
  • Processing Equipment
  • Standards

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Networking
  • Parallel and Distributed Computing.