Parallel approach to chip wiring
First Claim
1. A method for wiring areas on an integrated circuit chip in parallel, comprising the steps of:
- (a) dividing said chip into a plurality of rectangular bays with rough wiring coordinates;
(b) grouping said rectangular bays into a plurality of bay groups, each bay group containing a contiguous group of bays including non-edge bays and at least one edge bay adjacent another bay group;
(c) assigning a different bay group to each wiring task of a plurality of wiring tasks; and
(d) each of said wiring tasks including performing of wiring of said bays in a bay group assigned thereto according to said rough coordinates and performing said wiring in parallel with said other wiring tasks,(1) if wiring an edge bay, before wiring begins checking whether the adjacent edge bay has been wired, is currently being wired, or has not been wired, and(i) if said adjacent edge bay has been wired, wiring said edge bay in accordance with said adjacent edge bay wiring, or(ii) if said adjacent edge bay is currently being wired, waiting for said adjacent edge bay to finish being wired and then wiring said edge bay in accordance with said adjacent edge bay wiring, or(iii) if said adjacent edge bay has not been wired, wiring said edge bay, otherwise wiring said non-edge bay.
1 Assignment
0 Petitions
Accused Products
Abstract
In any of the post-global physical design phases an integrated circuit chip is wired in parallel. The chip is first divided into adjacent bays with rough wiring coordinates from the global wiring phase. Next the bays are grouped into bay groups, with each bay group containing a contiguous group of non-edge bays as well as edge bays which are adjacent another bay group. Each bay group is assigned to a wiring task on a processor, so that the wiring of the bay groups is performed in parallel, using the rough coordinates from the global wiring phase. The wiring tasks are coordinated regarding edge bays in order to achieve wiring consistency between bay groups.
24 Citations
26 Claims
-
1. A method for wiring areas on an integrated circuit chip in parallel, comprising the steps of:
-
(a) dividing said chip into a plurality of rectangular bays with rough wiring coordinates; (b) grouping said rectangular bays into a plurality of bay groups, each bay group containing a contiguous group of bays including non-edge bays and at least one edge bay adjacent another bay group; (c) assigning a different bay group to each wiring task of a plurality of wiring tasks; and (d) each of said wiring tasks including performing of wiring of said bays in a bay group assigned thereto according to said rough coordinates and performing said wiring in parallel with said other wiring tasks, (1) if wiring an edge bay, before wiring begins checking whether the adjacent edge bay has been wired, is currently being wired, or has not been wired, and (i) if said adjacent edge bay has been wired, wiring said edge bay in accordance with said adjacent edge bay wiring, or (ii) if said adjacent edge bay is currently being wired, waiting for said adjacent edge bay to finish being wired and then wiring said edge bay in accordance with said adjacent edge bay wiring, or (iii) if said adjacent edge bay has not been wired, wiring said edge bay, otherwise wiring said non-edge bay. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method for performing a plurality of wiring tasks for wiring areas on an integrated circuit chip in a parallel process of wiring, comprising the steps of:
-
(a) dividing said chip into a plurality of parallel slices spanning an entire dimension of a length or width of a chip, and dividing each said slice into parallel rectangular bays spanning an entire dimension of a length or width of a chip, said bays including rough wiring coordinates, (b) grouping said rectangular bays into a plurality of bay groups, each of said bay groups containing a contiguous group of bays including a non-edge bay and at least one edge bay adjacent another bay group, (c) assigning each successive bay group to be wired in a different one of said wiring tasks, and (d) each of said wiring tasks including performing of wiring of said bays in a bay group assigned thereto according to said rough wiring coordinates and performing said wiring in parallel with performance of said other wiring tasks, (1) if wiring an edge bay, before wiring begins checking edge bays status as to whether said adjacent edge bay has been wired, whether said adjacent edge bay is currently being wired, and whether said adjacent edge bay is as yet unwired, and (i) if said adjacent edge bay has been wired, wiring said edge bay in accordance with said adjacent edge bay wiring, or (ii) if said adjacent edge bay is currently being wired, waiting for said adjacent edge bay to finish being wired and then wiring said edge bay in accordance with said adjacent edge bay wiring, or (iii) if said adjacent edge bay is as yet unwired, wiring said edge bay, and otherwise, (2) wiring said non-edge bay. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A method for performing a plurality of wiring tasks for wiring areas on an integrated circuit chip in a parallel process of wiring, comprising the steps of:
-
(a) dividing said chip into a plurality of parallel slices spanning an entire dimension of a length or width of a chip, and dividing each of said slices into parallel rectangular bays spanning an entire dimension of a length or width of a chip, said bays including rough wiring coordinates, (b) grouping said rectangular bays into a plurality of bay groups, each said bay group containing a contiguous group of bays including a non-edge bay and at least one edge bay adjacent another bay group, (c) assigning each successive bay group to be wired in a different one of said wiring tasks, and (d) each of said wiring tasks including performing of wiring of said bays in a bay group assigned thereto according to said rough wiring coordinates and performing said wiring in parallel with performance of said other wiring tasks, (1) if wiring an edge bay, before wiring begins checking edge bays status as to whether said adjacent edge bay has been wired, whether said adjacent edge bay is currently being wired, and whether said adjacent edge bay is as yet unwired, and (i) if said adjacent edge bay has been wired, wiring said edge bay in accordance with said adjacent edge bay wiring, or (ii) if said adjacent edge bay is currently being wired, waiting for said adjacent edge bay to finish being wired and then wiring said edge bay in accordance with said adjacent edge bay wiring, or (iii) if said adjacent edge bay is as yet unwired, wiring said edge bay, and otherwise, (2) wiring said non-edge bay, (e) assigning a next available unwired bay group to a task that has completed wiring its assigned bay group, and (f) repeating steps (d) and (e) until all unwired bay groups have been assigned to wiring tasks, (g) after step (f), upon completion of wiring of bay groups assigned to a task, thereby rendering said task idle, performing the further steps comprising; (1) assessing the degree of completion of each of said remaining wiring tasks in wiring its assigned bay group, (2) selecting a low completion wiring task that has the lowest degree of completion, (3) creating a new bay group by subdividing said bay group assigned to said low completion wiring task, (4) assigning said new bay group to said idle task, (5) repeating step (d), and (6) repeating steps (g) (1) through (g) (5) until all bay groups have been wired. - View Dependent Claims (22, 23, 24, 25)
-
-
26. A method for performing a plurality of wiring tasks for wiring areas on an integrated circuit chip in a parallel process of wiring, comprising the steps of:
-
(a) dividing said chip into a plurality of parallel slices spanning an entire dimension of selected from the length and the width of a chip, and dividing each of said slices into parallel rectangular bays, said bays spanning an entire dimension selected from the length and the width of a chip, each of said bays covering a generally rectangular area of the integrated circuit chip, said bays including rough wiring coordinates, (b) grouping said rectangular bays into a plurality of bay groups, each said bay group containing a contiguous group of bays including a non-edge bay and at least one edge bay adjacent another bay group, (c) assigning each successive bay group to be wired in a different one of said wiring tasks, and (d) each of said wiring tasks including performing of wiring of said bays in a bay group assigned thereto according to said rough wiring coordinates and performing said wiring in parallel with performance of said other wiring tasks wherein each of said wiring tasks is controlled by a respective computer processor, and (1) if wiring an edge bay, before wiring begins checking edge bays status as to whether said adjacent edge bay has been wired, whether said adjacent edge bay is currently being wired, and whether said adjacent edge bay is as yet unwired, and (i) if said adjacent edge bay has been wired, wiring said edge bay in accordance with said adjacent edge bay wiring, or (ii) if said adjacent edge bay is currently being wired, waiting for said adjacent edge bay to finish being wired and then wiring said edge bay in accordance with said adjacent edge bay wiring, or (iii) if said adjacent edge bay is as yet unwired, wiring said edge bay in accordance with said adjacent edge bay by accessing a database of detailed wiring data for said plurality of bays, and otherwise, (2) wiring said non-edge bay, (e) assigning a next available unwired bay group to a task that has completed wiring its assigned bay group, (f) repeating steps (d) and (e) until all unwired bay groups have been assigned to wiring tasks, (g) after step (f) upon completion of wiring of bay groups assigned to a task thereby rendering said task idle, performing the further steps comprising; (1) assessing the degree of completion of each of said remaining wiring tasks in wiring its assigned bay group, (2) selecting a low completion wiring task that has the lowest degree of completion, (3) creating a new bay group by subdividing said bay group assigned to said low completion wiring task, (4) assigning said new bay group to said idle task, (5) repeating step (d), and (6) repeating steps (g) (1) through (g) (5) until all bay groups have been wired, (h) all steps are performed twice, once for the relatively horizontal bays, and once for the relatively vertical bays, and (i) merging said wiring of said bay groups to complete said chip wiring.
-
Specification