Importance

Loading Importance Indicators...

Abstract

A multithreaded wavefront routing system for simultaneously planning routes for wiring a semiconductor chip surface. The surface has a plurality of grids located thereon, and routes are planned according to a predetermined netlist. The system steps across the surface from a first location to a second location in a wave-type pattern. The system sequentially steps through the grid arrangement on the chip surface and plans routing one grid at a time using a plurality of threaded processors. The system recognizes pins as it steps through grids and determines a plan for the current grid by evaluating current wire position, target pin location, and any currently planned routes, designating reserved locations wherein the route may be planned subsequent to the current grid, and establishing a wire direction for each wire traversing the current grid. The system plans wiring through grids using multiple threaded processors employing shared memory and a semi-hard coded rule based expert system applying heuristics by planning various routes based on current and potential wire locations. The system propagates wiring and performs memory bookkeeping functions. The system also has the capability to plan an additional route from one target pin toward a first pin. Meetings between routes are designated and resolved. Reservations may be established when a processor plans a route. Mutex locks may be utilized to avoid multiprocessor conflicts.

Loading the Abstract Image...

First Claim