Accession Number:

ADA207171

Title:

Parallel Global Routing for Standard Cells

Descriptive Note:

Corporate Author:

STANFORD UNIV CA COMPUTER SYSTEMS LAB

Personal Author(s):

Report Date:

1987-01-01

Pagination or Media Count:

18.0

Abstract:

Standard cell placement algorithms have traditionally used cost functions that poorly predict the final area of the circuit, and so can result in placements with good wire length but large final area. A good estimation of the area can be obtained by global routing the placement, but routing has been considered too slow to be used as the placement metric. This paper presents a new, fast global routing algorithm for standard cels and its parallel implementation. The router is based on enumerating a subset of all two-bend routes between two points, and results in 16 to 37 fewer total number of tracks than the TimberWolf global router for standard cells Sech85. It is comparable in quality to a maze router and an industrial router, but is faster by a factor of 10 or more. Three axes of parallelism are implemented wire-by- wire, segment-by-segment and route-by-route. Two of these approaches achieve significant speedup - route-by-route achieves up to 4.6 using eight processors, and wire-by-wire achieves from 10 to 14 using 15 processors. Because these axes are orthogonal, when combined we demonstrate that their respective speedups multiply each other. A simple model is used to predict speedups of up to 61 using 120 processors.

Subject Categories:

  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE