US5198987A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Wiring-pattern-determination system
Assignee: Fujitsu Ltd
•
Filing: 1990-10-24
•
Granted: 1993-03-30
•
Expires: 2010-10-24
Abstract
Abstract A wiring pattern determination system includes a label setting unit for setting labels from a starting point to an ending point by performing a labeling utilizing a maze running, and a reference point setting unit for setting a corner of a wiring pattern to be determined or the ending point as a reference point for a back trace of the maze running. The wiring-pattern-determination system has a corner judging unit for judging the next corner as the next reference point based on the label set at the reference point, a termination judging unit for judging the termination of the back trace when the starting point and the corner determined by the corner judging unit match and a reference point revising unit for instructing the reference point setting unit to set the next corner as a new reference point when the starting point and the corner determined by the corner judging unit mismatch. In the back trace, the wiring pattern is immediately and quickly determined between the corner and the next corner obtained by the corner judging unit.
Inventors
- 👤 Tatsuya Shindo
- 👤 Kaoru Kawamura
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 17:19
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
219 words
A wiring-pattern-determination system implemented by a computer including processors connected orthogonally to each other, each having a processor memory, comprising: label setting means, implemented by the computer, for setting labels corresponding to each of the processors from a starting point to an ending point by performing a labeling operation utilizing a maze running and storing each of the labels in each processor memory; reference point setting means, implemented by the computer, for setting a corner of a wiring pattern to be determined by setting said ending point as a reference point assigned with a label for a back-trace, performed by a collection logical operation circuit connected to the processors, of said maze running; corner judging means, implemented by the computer, for determining a next corner of the wiring pattern as a next reference point based on the label assigned to the reference point by said reference point setting means; termination judging means, implemented by the computer, for determining a termination of the back-trace when said starting point and the next corner determined by said corner judging means match; and reference point revising means, implemented by the computer, for instructing said reference point setting means to set said next corner as a new reference point when said starting point and the next corner determined by said corner judging means mismatch.
Claim 2
Dependent Claim
219 words
A wiring-pattern-determination system implemented by a computer including processors connected orthogonally to each other, each having a processor memory, comprising: label setting means, implemented by the computer, for setting labels corresponding to each of the processors from a starting point to an ending point by performing a labeling operation utilizing a maze running and storing each of the labels in each processor memory; reference point setting means, implemented by the computer, for setting a corner of a wiring pattern to be determined by setting said ending point as a reference point assigned with a label for a back-trace, performed by a collection logical operation circuit connected to the processors, of said maze running; corner judging means, implemented by the computer, for determining a next corner of the wiring pattern as a next reference point based on the label assigned to the reference point by said reference point setting means; termination judging means, implemented by the computer, for determining a termination of the back-trace when said starting point and the next corner determined by said corner judging means match; and reference point revising means, implemented by the computer, for instructing said reference point setting means to set said next corner as a new reference point when said starting point and the next corner determined by said corner judging means mismatch.
Claim 3
Dependent Claim
44 words
The wiring-pattern-determination system according to claim 1, wherein said labeling operation performed by said label setting means is applied to a subject plane which is divided into a plurality of grid points, and a processor element is assigned to each of said grid points.
Claim 4
Dependent Claim
108 words
The wiring-pattern-determination system according to claim 2, wherein said labeling setting means comprises: means for initializing each processor element including source and target processor element; means for setting a source at the source processor element provided at the starting point of said wiring pattern; means for setting a target at the target processor element provided at the ending point of said wiring pattern; means for sequentially transmitting a label from said source to said target; means for determining whether the label has been transmitted until the label is transmitted to the target; and means for ending the labeling operation when the label has been transmitted to the target.
Claim 5
Dependent Claim
41 words
The wiring-pattern-determination system according to claim 3, wherein said means for determining comprises means for reading a target flag in the processor element, for determining whether the target flag is cleared and for transmitting the label to an adjacent processor element.
Claim 6
Dependent Claim
54 words
The wiring-pattern-determination system according to claim 2, wherein said reference point setting means reads the starting point for said back-trace, and said corner judging means comprises: means for initializing a candidate flag in each processor element; means for determining corner candidates; and means for determining the next corner selected from said corner candidates. PG,31
Claim 7
Dependent Claim
111 words
The wiring-pattern-determination system according to claim 5, wherein said means for determining corner candidates comprises: means for determining whether a particular processor element is on a line drawn in an arrow direction of the reference point from a coordinate of a reference point; and means for determining whether the arrow direction of the particular processor element is different from the arrow direction of the reference point, and said means for determining the next corner selects a minimum coordinate from the corner candidates when the arrow direction of the reference point is positive or selects a maximum coordinate from the corner candidates when the arrow direction of the reference point is negative.
Claim 8
Dependent Claim
61 words
The wiring-pattern-determination system according to claim 6, wherein said means for determining the next corner comprises the collection logical operation circuit including a plurality of stages of comparison circuits, each having a first stage of the comparison circuits which receives outputs of two processor elements, and a last stage of the comparison circuits for providing a maximum or a minimum output.
Claim 9
Dependent Claim
125 words
The wiring-pattern-determination system according to claim 5, wherein said means for determining corner candidates comprises: means for detecting whether an arrow direction in a particular processor element having X and Y coordinates is horizontal; means for detecting whether the Y coordinate of the particular processor element is the same as that of the reference point when the arrow direction in the particular processor element is horizontal; means for determining whether the arrow direction of the reference point is positive; and means for determining whether the X coordinate of the particular processor element is larger than the reference point and for determining that the particular processor element is a candidate of the X coordinate of the particular processor element and is larger than the reference point.
Claim 10
Dependent Claim
183 words
A wiring-pattern determination method implemented by a computer including processors connected orthogonally to each other, each having a processor memory, comprising steps of: (a) setting labels corresponding to each of the processors from a beginning point to an ending point by performing a labeling operation utilizing a maze running and storing each of the labels in each processor memory using the computer; (b) setting a corner of a wiring pattern to be determined by setting said ending point as a reference point assigned with a label for a back-trace, performed by a collection logical operation circuit connected to the processors, of said maze running using the computer; (c) determining a next corner as a next reference point based on the label assigned to the reference point using the computer; (d) determining a termination of the back-trace when said beginning point and the next corner determined by said determining step (c) match using the computer; and (e) setting the next corner as a new reference point when said beginning point and the next corner determined by said determining step (c) mismatch using the computer.
Claim 11
Dependent Claim
183 words
A wiring-pattern determination method implemented by a computer including processors connected orthogonally to each other, each having a processor memory, comprising steps of: (a) setting labels corresponding to each of the processors from a beginning point to an ending point by performing a labeling operation utilizing a maze running and storing each of the labels in each processor memory using the computer; (b) setting a corner of a wiring pattern to be determined by setting said ending point as a reference point assigned with a label for a back-trace, performed by a collection logical operation circuit connected to the processors, of said maze running using the computer; (c) determining a next corner as a next reference point based on the label assigned to the reference point using the computer; (d) determining a termination of the back-trace when said beginning point and the next corner determined by said determining step (c) match using the computer; and (e) setting the next corner as a new reference point when said beginning point and the next corner determined by said determining step (c) mismatch using the computer.
Claim 12
Dependent Claim
44 words
The wiring-pattern-determination system according to claim 9, wherein said labeling operation performed by said setting step (a) is applied to a subject plane which is divided into a plurality of grid points, and a processor element is assigned to each of said grid points.
Claim 13
Dependent Claim
105 words
The wiring-pattern-determination system according to claim 10, wherein said setting step (a) comprises the steps of: (a1) initializing each processor element including source and target processor elements; (a2) setting a source at the source processor element provided at the starting point of said wiring pattern; (a3) setting a target at the target processor element provided at the ending point of said wiring pattern; (a4) sequentially transmitting a label from said source to said target; (a5) determining whether the label has been transmitted until the level is transmitted to the target; and (a6) ending the labeling operation when the label has been transmitted to the target.
Claim 14
Dependent Claim
40 words
The wiring-pattern-determination system according to claim 11, wherein said determining step (a5) comprises the steps of: reading a target flag in the processor element; determining whether the target flag is cleared; and transmitting the label to an adjacent processor element.
Claim 15
Dependent Claim
51 words
The wiring-pattern-determination system according to claim 10, wherein said setting step (b) reads the starting point for said back-trace, and said determining step (c) comprises the steps of: (c1) initializing a candidate flag in each element; (c2) determining corner candidates; and (c3) determining the next corner selected from said corner candidates.
Claim 16
Dependent Claim
105 words
The wiring-pattern-determination system according to claim 13, wherein said determining step (c2) comprises the steps of: determining whether a particular processor element is on a line drawn in an arrow direction of the reference point from a coordinate of a reference point; and determining whether the arrow direction of the particular processor element is different from the arrow direction of the reference point, and said determining steps (c3) selects a minimum coordinate from the corner candidates when the arrow direction of the reference point is positive or selects a maximum coordinate from the corner candidates when the arrow direction of the reference point is negative.
Claim 17
Dependent Claim
60 words
The wiring-pattern-determination system according to claim 14, wherein said determining step (c3) is implemented by the collection logical operation circuit including a plurality of stages of comparison circuits, each having a first stage of the comparison circuits which receives outputs of two processor elements, and a last stage of the comparison circuits for providing a maximum or a minimum output.
Claim 18
Dependent Claim
118 words
The wiring-pattern-determination system according to claim 13, wherein said determining step (c2) comprises the steps of: detecting whether an arrow direction in a particular processor element having X and Y coordinates is horizontal; detecting whether the Y coordinate of the particular processor element is the same as that of the reference point when the arrow direction in the particular processor element is horizontal; determining whether the arrow direction of the reference point is positive; and determining whether the X coordinate of the particular processor element is larger than the reference point and for determining that the particular processor element is a candidate of the X coordinate of the particular processor element and is larger than the reference point.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-03-29 | 1996-09-28 | 1997-03-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-03-29 | 2000-09-28 | 2001-03-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-03-29 | 2004-09-28 | 2005-03-30 | $7700.00 | Window Closed / Lapsed |