Beaver: A Computational Geometry-Based Tool for Switchbox Routing

Authors:Cohoon, James, Department of Computer ScienceUniversity of Virginia Heck, P, Department of Computer ScienceUniversity of Virginia

A new fast switchbox router, BEAVER is presented. BEAVER combines a delayed layering scheme with computational geometry techniques to heuristically produce a switchbox solution that minimizes both via usage and wire length, and maximizes the use of a preferred routing layer. Other important features are its use of priority queues to determine the order that nets are routed and its prioritized control of individual track and column usage to prevent routing conflicts. BEAVER consists of four tools that are run successively - - ~a comer router, a line sweep router, a thread router, and a layerer. The comer router makes single-bend terminal-toterminal connections. The line sweep router makes straight - line connections, single-bend connections, and two - bend connections. The thread router makes connections of arbitrary form. The layerer completes the switchbox by layering wires that have been assigned a location but not yet a layer. BEAVER has successfully routed all of the classic switchboxes. Its solution quality with respect to wire length was better or comparable to the best previous solutions and its via usage was consistently the minimum. These characteristics make it appropriate for its intended use as the initial router invoked to solve a switchbox.
Note: Abstract extracted from PDF file via OCR

All rights reserved (no additional license for public reuse)
Source Citation:

Cohoon, James, and P Heck. "Beaver: A Computational Geometry-Based Tool for Switchbox Routing." University of Virginia Dept. of Computer Science Tech Report (1987).

University of Virginia, Department of Computer Science
Published Date: