Accession Number : ADA206545

Title :   Channel and Switchbox Routing Using a Greedy Based Channel Algorithm with Outward Scanning Technique.

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : Roderick, Michael J

PDF Url : ADA206545

Report Date : Dec 1988

Pagination or Media Count : 149

Abstract : The problem of channel routing and for that matter routing in general has been attacked in a heuristic manner vice analytical. This is not necessarily wrong, however it means that there is not always a solution to the problem. Channel routing is one of the most important phases in VLSI CAD (Very Large Scale Integration Computer Aided Design). It performs the detailed routing of a given channel. The switchbox is a four sided channel area, rectangular in shape, with nets entering from all four sides. There has been much work done in the channel and switchbox routing areas. The Greedy router, a proven heuristic, is one of the important building blocks for most of today's detailed routers and is used as basis for this thesis. Most routers scan the routing area using a left to right scanning method. This thesis attempts a different variation in routing, using an outward scanning technique. The thesis demonstrates how this new algorithm can be applied to various channel routing problems, by performing tests and making comparisons. The thesis also demonstrates how this new router can be used as a CAD tool. The new router assumes that all pins and wiring lie on a common grid, and that vertical wires are on one layer horizontal on another. The thesis also shows how this new channel router can be modified to allow for a switchbox router implementation. Theses. (jhd)

Descriptors :   *ROUTING, *COMPUTER AIDED DESIGN, *SWITCHING CIRCUITS, ALGORITHMS, CHANNELS, GRIDS, HEURISTIC METHODS, LAYERS, MODULAR CONSTRUCTION, PINS, ROUTING, SCANNING, SIDES, THESES, WIRE

Subject Categories : Electricity and Magnetism

Distribution Statement : APPROVED FOR PUBLIC RELEASE