Integrated circuit layout routing using multiprocessing
First Claim
1. A multithreaded wavefront routing system for creating a plan of a route for wiring for a semiconductor chip surface having a grid arrangement located thereon based on a netlist, comprising:
- a sequencing processor for sequentially stepping through the grid arrangement from one chip surface location to another chip surface location in a wavefront, thereby establishing a current grid on the chip surface; and
a plurality of processors, wherein each processor comprises;
a pin identifier for recognizing pins located on the surface of the chip;
a planner for establishing a proposed route proceeding from a first pin on the chip surface to a subsequent pin on the chip surface; and
a current grid wire direction planner for individually planning a direction for a wire traversing the current grid.
11 Assignments
0 Petitions
Accused Products
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.
-
Citations
51 Claims
-
1. A multithreaded wavefront routing system for creating a plan of a route for wiring for a semiconductor chip surface having a grid arrangement located thereon based on a netlist, comprising:
-
a sequencing processor for sequentially stepping through the grid arrangement from one chip surface location to another chip surface location in a wavefront, thereby establishing a current grid on the chip surface; and a plurality of processors, wherein each processor comprises; a pin identifier for recognizing pins located on the surface of the chip; a planner for establishing a proposed route proceeding from a first pin on the chip surface to a subsequent pin on the chip surface; and a current grid wire direction planner for individually planning a direction for a wire traversing the current grid. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A method for creating a routing plan for wiring a semiconductor chip surface based on a given netlist, comprising the steps of:
-
establishing a first location, a second location, and a grid system on said chip; and sequentially traversing from said first location to said second location by sequentially stepping through grids on the surface to establish a current grid using a plurality of processors, comprising the substeps of; recognizing pin positions on said surface; and simultaneously planning routes from a plurality of first pins through the current grid toward at least one subsequent target pin using said plurality of processors. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
-
-
29. A method of simultaneously planning routes for wiring a semiconductor chip surface having a plurality of grids located thereon based on a given netlist from a plurality of first pins through a current grid toward at least one subsequent target pin using a plurality of processors, comprising the steps of:
determining a plan for the current grid using each processor according to the substeps of; evaluating current wire position; assessing target location; appraising currently planned routes; designating reserved locations wherein the route may be planned subsequent to said current grid; and establishing a wire direction for each wire traversing the current grid. - View Dependent Claims (30, 31, 32, 33, 34, 35, 36, 37, 38)
-
39. A method of planning multiple routes along a surface of a semiconductor chip surface divided into a plurality of grids using multiple processing threads according to a predetermined netlist, comprising the following steps:
-
sequentially stepping through the grid arrangement from one chip surface location to another chip surface location in a wavefront, thereby establishing a current grid on the chip surface; recognizing pins along the wavefront; using each processing thread to separately plan routes between pins according to the netlist; and individually planning a direction for each wire traversing the current grid. - View Dependent Claims (40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51)
-
Specification