US6301686B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Graphic layout compaction system capable of compacting a layout at once
Assignee: NEC Toppan Circuit Solutions Toyama Inc
•
Filing: 1999-03-23
•
Granted: 2001-10-09
•
Expires: 2019-03-23
Abstract
Abstract In a graphic layout compaction system for compacting a layout where components and routes are placed on a two-dimensional space, a terminal graph generator prepares terminal graph data indicative of terminal graphs having component terminals as nodes. The terminal graph generator calculates, as a movement amount for allowing a first component terminal to come near a second component terminal, a movement limit area within which the first component terminal can move in any directions towards the second component terminal in consideration of a route bandwidth interposed therebetween. A component compactor moves the first component terminal on a position where the first component terminal is not interfered with the movement limit area. A rerouting unit shapes routes into shaped routes having configurations including oblique parts to reroute the shaped routes in a space between the first and the second component terminals.
Inventors
- 👤 Hideo Kikuchi
- 👤 Yutaka Akimoto
- 👤 Toshiyuki Kaneko
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:13
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/398
Claims Analysis
Total Claims: 72
Claim 1
Independent Claim
136 words
A graphic layout compaction system for compacting a layout where components and routes are placed on a two-dimensional space, said graphic layout compaction system comprising: calculating means for calculating a movement limit area within which a first component can move in any directions towards a second component in consideration of a route bandwidth interposed therebetween, the route bandwidth being obtained by adding a necessary space to a width of particular routes put between the first component and the second component; component compacting means for moving the first component on a position where the first component is not interfered with the movement limit area; and rerouting means for shaping the particular routes into shaped particular routes having configurations including oblique parts to reroute the shaped particular routes in a space between the first and the second components.
Claim 2
Dependent Claim
136 words
A graphic layout compaction system for compacting a layout where components and routes are placed on a two-dimensional space, said graphic layout compaction system comprising: calculating means for calculating a movement limit area within which a first component can move in any directions towards a second component in consideration of a route bandwidth interposed therebetween, the route bandwidth being obtained by adding a necessary space to a width of particular routes put between the first component and the second component; component compacting means for moving the first component on a position where the first component is not interfered with the movement limit area; and rerouting means for shaping the particular routes into shaped particular routes having configurations including oblique parts to reroute the shaped particular routes in a space between the first and the second components.
Claim 3
Dependent Claim
29 words
A graphic layout compaction system as claimed in claim 1 , wherein said component compacting means shifts a movement direction for the first component from longitudinal and lateral directions.
Claim 4
Dependent Claim
109 words
A graphic layout compaction system as claimed in claim 1 , wherein said calculating means comprises: means for subtracting widths of the first and the second components in a quantization direction from a length where a vector connecting the first and the second components is projected in the quantization direction to produce a subtracted distance, the quantization direction being obtained by quantizing the any directions by a predetermined angle; means for calculating a polygonal configuration having a width in the quantization direction that is obtained by subtracting the route bandwidth from the subtracting distance; and means for obtaining an area inside the polygonal configuration as the movement limit area.
Claim 5
Dependent Claim
19 words
A graphic layout compaction system as claimed in claim 3 , wherein the predetermined angle is equal to 45°.
Claim 6
Dependent Claim
103 words
A graphic layout compaction system as claimed in claim 1 , wherein said calculating means comprises: means for adding a width of the first component in a quantization direction and a width of the second component in the opposite direction of the quantization direction to produce an added distance, the quantization direction being obtained by quantizing the any direction by a predetermined angle; means for calculating a polygonal configuration having a width in the quantization direction that is obtained by adding the route bandwidth to the added distance; and means for obtaining an area outside the polygonal configuration as the movement limit area.
Claim 7
Dependent Claim
19 words
A graphic layout compaction system as claimed in claim 5 , wherein the predetermined angle is equal to 45°.
Claim 8
Dependent Claim
83 words
A graphic layout compaction system as claimed in claim 1 , wherein said graphic layout compaction system further comprises: a display unit for displaying said components thereon; operator command input means for receiving a command from an operator; and component movement designating means for freely designating movement target positions for the components in response to the commands from said operator command input means, said component compacting means moving the components on the respective movement target positions, and said rerouting means fixing the routes.
Claim 9
Dependent Claim
26 words
A graphic layout compaction system as claimed in claim 7 , wherein further comprises means for making said display unit display a shortest route network graph.
Claim 10
Dependent Claim
54 words
A graphic layout compaction system as claimed in claim 7 , wherein said component movement designating means receives particular commands for inserting additional routes and additional components, and said component compacting means carrying out component movement so as to maintain spaces between the components in consideration of the additional routes and the additional components.
Claim 11
Dependent Claim
60 words
A graphic layout compaction system as claimed in claim 1 , wherein said graphic layout compaction system further comprises: a display unit for displaying said components thereon; and component movement designating means for designating movement directions and movement distances for the components, individually, said component compacting means moving the components in accordance with the movement directions and the movement distances.
Claim 12
Dependent Claim
53 words
A graphic layout compaction system as claimed in claim 10 , wherein said component compacting means comprises: means for enlarging distances between the components and a layout center into similar distances; means for automatically routing between terminals of each component; and means for compacting the components and the routes toward the layout center.
Claim 13
Dependent Claim
71 words
A graphic layout compaction system as claimed in claim 1 , wherein said graphic layout compaction system further comprises: a display unit for displaying said components thereon; and component movement designating means for collectively designating a movement direction and a movement distance for the components toward a direction turning to a predetermined layout position, said component compacting means moving the components in accordance with the movement direction and the movement distance.
Claim 14
Dependent Claim
53 words
A graphic layout compaction system as claimed in claim 12 , wherein said component compacting means comprises: means for enlarging distances between the components and a layout center into similar distances; means for automatically routing between terminals of each component; and means for compacting the components and the routes toward the layout center.
Claim 15
Dependent Claim
71 words
A graphic layout compaction system as claimed in claim 1 , wherein said graphic layout compaction system further comprises: a display unit for displaying said components thereon; and component movement designating means for collectively designating a movement direction and a movement distance for the components toward a direction apart from a predetermined layout position, said component compacting means moving the components in accordance with the movement direction and the movement distance.
Claim 16
Dependent Claim
53 words
A graphic layout compaction system as claimed in claim 14 , wherein said component compacting means comprises: means for enlarging distances between the components and a layout center into similar distances; means for automatically routing between terminals of each component; and means for compacting the components and the routes toward the layout center.
Claim 17
Dependent Claim
62 words
A graphic layout compaction system as claimed in claim 1 , wherein said graphic layout compaction system further comprises: component set expanding means for cutting off a partial area of the layout to replace the partial area by parallel movement and rotation; and renewing means for renewing connections between component terminals inside the partial area and component terminals outside the partial area.
Claim 18
Dependent Claim
34 words
A graphic layout compaction system as claimed in claim 1 , wherein said graphic layout compaction system further comprises routing renewing means for switching the order of first and second routes with each other.
Claim 19
Dependent Claim
135 words
A graphic layout compaction system for compacting a layout where components and routes are placed on a two-dimensional space, said graphic layout compaction system comprising: a calculator for calculating a movement limit area within which a first component can move in any directions towards a second component in consideration of a route bandwidth interposed therebetween, the route bandwidth being obtained by adding a necessary space to a width of particular routes put between the first component and the second component; component compactor for moving the first component on a position where the first component is not interfered with the movement limit area; and rerouting unit for shaping the particular routes into shaped particular routes having configurations including oblique parts to reroute the shaped particular routes in a space between the first and the second components.
Claim 20
Dependent Claim
135 words
A graphic layout compaction system for compacting a layout where components and routes are placed on a two-dimensional space, said graphic layout compaction system comprising: a calculator for calculating a movement limit area within which a first component can move in any directions towards a second component in consideration of a route bandwidth interposed therebetween, the route bandwidth being obtained by adding a necessary space to a width of particular routes put between the first component and the second component; component compactor for moving the first component on a position where the first component is not interfered with the movement limit area; and rerouting unit for shaping the particular routes into shaped particular routes having configurations including oblique parts to reroute the shaped particular routes in a space between the first and the second components.
Claim 21
Dependent Claim
29 words
A graphic layout compaction system as claimed in claim 18 , wherein said component compacting means shifts a movement direction for the first component from longitudinal and lateral directions.
Claim 22
Dependent Claim
111 words
A graphic layout compaction system as claimed in claim 18 , wherein said calculator comprises: a unit for subtracting widths of the first and the second components in a quantization direction from a length where a vector connecting the first and the second components is projected in the quantization direction to produce a subtracted distance, the quantization direction being obtained by quantizing the any directions by a predetermined angle; a unit for calculating a polygonal configuration having a width in the quantization direction that is obtained by subtracting the route bandwidth from the subtracting distance; and a unit for obtaining an area inside the polygonal configuration as the movement limit area.
Claim 23
Dependent Claim
19 words
A graphic layout compaction system as claimed in claim 20 , wherein the predetermined angle is equal to 45°.
Claim 24
Dependent Claim
105 words
A graphic layout compaction system as claimed in claim 18 , wherein said calculator comprises: a unit for adding a width of the first component in a quantization direction and a width of the second component in the opposite direction of the quantization direction to produce an added distance, the quantization direction being obtained by quantizing the any direction by a predetermined angle; a unit for calculating a polygonal configuration having a width in the quantization direction that is obtained by adding the route bandwidth to the added distance; and a unit for obtaining an area outside the polygonal configuration as the movement limit area.
Claim 25
Dependent Claim
19 words
A graphic layout compaction system as claimed in claim 22 , wherein the predetermined angle is equal to 45°.
Claim 26
Dependent Claim
83 words
A graphic layout compaction system as claimed in claim 18 , wherein said graphic layout compaction system further comprises: a display unit for displaying said components thereon; an operator command input device for receiving a command from an operator; and a component movement designator for freely designating movement target positions for the components in response to the commands from said operator command input means, said component compactor moving the components on the respective movement target positions, and said rerouting unit fixing the routes.
Claim 27
Dependent Claim
27 words
A graphic layout compaction system as claimed in claim 24 , wherein further comprises a unit for making said display unit display a shortest route network graph.
Claim 28
Dependent Claim
52 words
A graphic layout compaction system as claimed in claim 24 , wherein said component movement designator receives particular commands for inserting additional routes and additional components, and said component compactor carrying out component movement so as to maintain spaces between the components in consideration of the additional routes and the additional components.
Claim 29
Dependent Claim
59 words
A graphic layout compaction system as claimed in claim 18 , wherein said graphic layout compaction system further comprises: a display unit for displaying said components thereon; and a component movement designator for designating movement directions and movement distances for the components, individually, said component compactor moving the components in accordance with the movement directions and the movement distances.
Claim 30
Dependent Claim
55 words
A graphic layout compaction system as claimed in claim 27 , wherein said component compactor comprises: a unit for enlarging distances between the components and a layout center into similar distances; a unit for automatically routing between terminals of each component; and a unit for compacting the components and the routes toward the layout center.
Claim 31
Dependent Claim
70 words
A graphic layout compaction system as claimed in claim 18 , wherein said graphic layout compaction system further comprises: a display unit for displaying said components thereon; and a component movement designator for collectively designating a movement direction and a movement distance for the components toward a direction turning to a predetermined layout position, said component compactor moving the components in accordance with the movement direction and the movement distance.
Claim 32
Dependent Claim
55 words
A graphic layout compaction system as claimed in claim 29 , wherein said component compactor comprises: a unit for enlarging distances between the components and a layout center into similar distances; a unit for automatically routing between terminals of each component; and a unit for compacting the components and the routes toward the layout center.
Claim 33
Dependent Claim
70 words
A graphic layout compaction system as claimed in claim 18 , wherein said graphic layout compaction system further comprises: a display unit for displaying said components thereon; and a component movement designator for collectively designating a movement direction and a movement distance for the components toward a direction apart from a predetermined layout position, said component compactor moving the components in accordance with the movement direction and the movement distance.
Claim 34
Dependent Claim
55 words
A graphic layout compaction system as claimed in claim 31 , wherein said component compactor comprises: a unit for enlarging distances between the components and a layout center into similar distances; a unit for automatically routing between terminals of each component; and a unit for compacting the components and the routes toward the layout center.
Claim 35
Dependent Claim
62 words
A graphic layout compaction system as claimed in claim 18 , wherein said graphic layout compaction system further comprises: a component set expander for cutting off a partial area of the layout to replace the partial area by parallel movement and rotation; and a renewer for renewing connections between component terminals inside the partial area and component terminals outside the partial area.
Claim 36
Dependent Claim
34 words
A graphic layout compaction system as claimed in claim 18 , wherein said graphic layout compaction system further comprises a routing renewer for switching the order of first and second routes with each other.
Claim 37
Independent Claim
127 words
A method of compacting a layout where components and routes are placed on a two-dimensional space, said method comprising the steps of: calculating a movement limit area within which a first component can move in any directions towards a second component in consideration of a route bandwidth interposed therebetween, the route bandwidth being obtained by adding a necessary space to a width of particular routes put between the first component and the second component; compacting said components by moving the first component on a position where the first component is not interfered with the movement limit area; and shaping the particular routes into shaped particular routes having configurations including oblique parts to reroute the shaped particular routes in a space between the first and the second components.
Claim 38
Independent Claim
127 words
A method of compacting a layout where components and routes are placed on a two-dimensional space, said method comprising the steps of: calculating a movement limit area within which a first component can move in any directions towards a second component in consideration of a route bandwidth interposed therebetween, the route bandwidth being obtained by adding a necessary space to a width of particular routes put between the first component and the second component; compacting said components by moving the first component on a position where the first component is not interfered with the movement limit area; and shaping the particular routes into shaped particular routes having configurations including oblique parts to reroute the shaped particular routes in a space between the first and the second components.
Claim 39
Dependent Claim
28 words
A method as claimed in claim 35 , wherein said step of compacting said components shifts a movement direction for the first component from longitudinal and lateral directions.
Claim 40
Dependent Claim
108 words
A method as claimed in claim 35 , wherein said step of calculating the movement limit area comprises the substeps of: subtracting widths of the first and the second components in a quantization direction from a length where a vector connecting the first and the second components is projected in the quantization direction to produce a subtracted distance, the quantization direction being obtained by quantizing the any directions by a predetermined angle; calculating a polygonal configuration having a width in the quantization direction that is obtained by subtracting the route bandwidth from the subtracting distance; and obtaining an area inside the polygonal configuration as the movement limit area.
Claim 41
Dependent Claim
16 words
A method as claimed in claim 37 , wherein the predetermined angle is equal to 45°.
Claim 42
Dependent Claim
102 words
A method as claimed in claim 35 , wherein said step of calculating the movement limit area comprises the substeps of: adding a width of the first component in a quantization direction and a width of the second component in the opposite direction of the quantization direction to produce an added distance, the quantization direction being obtained by quantizing the any directions by a predetermined angle; calculating a polygonal configuration having a width in the quantization direction that is obtained by adding the route bandwidth to the added distance; and obtaining an area outside the polygonal configuration as the movement limit area.
Claim 43
Dependent Claim
16 words
A method as claimed in claim 39 , wherein the predetermined angle is equal to 45°.
Claim 44
Dependent Claim
65 words
A method as claimed in claim 35 , wherein said method further comprises the steps of: displaying said components on a display unit; receiving commands from an operator; and freely designating movement target positions for the components in response to the commands, said step of compacting the components moving the components on the respective movement target positions, and said step of rerouting fixing the routes.
Claim 45
Dependent Claim
25 words
A method as claimed in claim 41 , wherein said step of compacting the components displaying a shortest route network graph on said display unit.
Claim 46
Dependent Claim
55 words
A method as claimed in claim 41 , wherein said step of designating the component movement receives particular commands for inserting additional routes and additional components, and said step of compacting said components carrying out component movement so as to maintain spaces between the components in consideration of the additional routes and the additional components.
Claim 47
Dependent Claim
53 words
A method as claimed in claim 35 , wherein said method further comprises the steps of: displaying said components on a display unit; and designating movement directions and movement distances for the components, individually, said step of compacting the components moving the components in accordance with the movement directions and the movement distances.
Claim 48
Dependent Claim
49 words
A method as claimed in claim 44 , wherein said step of compacting the components comprises the substeps of: enlarging distances between the components and a layout center into similar distances; automatically routing between terminals of each components; and compacting the components and the routes toward the layout center.
Claim 49
Dependent Claim
64 words
A method as claimed in claim 35 , wherein said method further comprises the steps of: displaying said components on a display unit; and collectively designating a movement direction and a movement distance for the components toward a direction turning to a predetermined layer position, said step of compacting the components moving the components in accordance with the movement direction and the movement distance.
Claim 50
Dependent Claim
49 words
A method as claimed in claim 46 , wherein said step of compacting the components comprises the substeps of: enlarging distances between the components and a layout center into similar distances; automatically routing between terminals of each components; and compacting the components and the routes toward the layout center.
Claim 51
Dependent Claim
64 words
A method as claimed in claim 35 , wherein said method further comprises the steps of: displaying said components on a display unit; and collectively designating a movement direction and a movement distance for the components toward a direction apart from a predetermined layer position, said step of compacting the components moving the components in accordance with the movement direction and the movement distance.
Claim 52
Dependent Claim
49 words
A method as claimed in claim 48 , wherein said step of compacting the components comprises the substeps of: enlarging distances between the components and a layout center into similar distances; automatically routing between terminals of each components; and compacting the components and the routes toward the layout center.
Claim 53
Dependent Claim
51 words
A method as claimed in claim 35 , wherein said method further comprises the steps of: cutting off a partial area of the layout to replace the partial area by parallel movement and rotation; and renewing connections between component terminals inside the partial area and component terminals outside the partial area.
Claim 54
Dependent Claim
27 words
A method as claimed in claim 35 , wherein said method further comprises the step of switching the order of first and second routes with each other.
Claim 55
Dependent Claim
155 words
A recording medium for recording a program to make a computer execute processing for compacting a layout where components and routes are placed on a two-dimensional space, said recording medium recording the program to make said computer execute: a first processing of calculating a movement limit area within which a first component can move in any directions towards a second component in consideration of a route bandwidth interposed therebetween, the route bandwidth being obtained by adding a necessary space to a width of particular routes put between the first component and the second component; a second processing of compacting said components by moving the first component on a position where the first component is not interfered with the movement limit area; and a third processing of shaping the particular routes into shaped particular routes having configurations including oblique parts to reroute the shaped particular routes in a space between the first and the second components.
Claim 56
Dependent Claim
155 words
A recording medium for recording a program to make a computer execute processing for compacting a layout where components and routes are placed on a two-dimensional space, said recording medium recording the program to make said computer execute: a first processing of calculating a movement limit area within which a first component can move in any directions towards a second component in consideration of a route bandwidth interposed therebetween, the route bandwidth being obtained by adding a necessary space to a width of particular routes put between the first component and the second component; a second processing of compacting said components by moving the first component on a position where the first component is not interfered with the movement limit area; and a third processing of shaping the particular routes into shaped particular routes having configurations including oblique parts to reroute the shaped particular routes in a space between the first and the second components.
Claim 57
Dependent Claim
37 words
A recording medium as claimed in claim 52 , wherein said second processing is processing of moving the first component on the position by shifting a movement direction of the first component from longitudinal and lateral directions.
Claim 58
Dependent Claim
104 words
A recording medium as claimed in claim 52 , wherein said first processing comprises the subprocessings of: subtracting widths of the first and the second components in a quantization direction from a length where a vector connecting the first and the second components is projected in the quantization direction to produce a subtracted distance, the quantization direction being obtained by quantizing the any direction by a predetermined angle; calculating a polygonal configuration having a width in the quantization direction that is obtained by subtracting the route bandwidth from the subtracting distance; and obtaining an area inside the polygonal configuration as the movement limit area.
Claim 59
Dependent Claim
17 words
A recording medium as claimed in claim 54 , wherein the predetermined angle is equal to 45°.
Claim 60
Dependent Claim
98 words
A recording medium as claimed in claim 52 , wherein said first processing comprises the subprocessings of: adding a width of the first component in a quantization direction and a width of the second component in the opposite direction of the quantization direction to produce an added distance, the quantization direction being obtained by quantizing the any direction by a predetermined angle; calculating a polygonal configuration having a width in the quantization direction that is obtained by adding the route bandwidth to the added distance; and obtaining an area outside the polygonal configuration as the movement limit area.
Claim 61
Dependent Claim
17 words
A recording medium as claimed in claim 56 , wherein the predetermined angle is equal to 45°.
Claim 62
Dependent Claim
84 words
A recording medium as claimed in claim 52 , wherein said recording medium further makes the computer execute: a fourth processing of displaying said components on a display unit; a fifth processing of receiving commands from an operator; and a sixth processing of freely designating movement target positions for the components in response to the commands, said second processing including a subprocessing of moving the components on the respective movement target positions, and said third processing including a subprocessing of rerouting fixing the routes.
Claim 63
Dependent Claim
32 words
A recording medium as claimed in claim 58 , wherein said recording medium further makes the computer execute a seventh processing of displaying a shortest route network graph on said display unit.
Claim 64
Dependent Claim
57 words
A recording medium as claimed in claim 58 , wherein said sixth processing includes a subprocessing of receiving particular commands for inserting additional routes and additional components, and said second processing including a subprocessing of carrying out component movement so as to maintain spaces between the components in consideration of the additional routes and the additional components.
Claim 65
Dependent Claim
64 words
A recording medium as claimed in claim 52 , wherein said recording medium further makes the computer execute: a fourth processing of displaying said components on a display unit; and a fifth processing of designating movement directions and movement distances for the components, individually, said second processing including a subprocessing of moving the components in accordance with the movement directions and the movement distances.
Claim 66
Dependent Claim
47 words
A recording medium as claimed in claim 61 , wherein said second processing includes the subprocessings of: enlarging distance between the components and a layout center into similar distances; automatically routing between terminals of each component; and compacting the components and the routes toward the layout center.
Claim 67
Dependent Claim
75 words
A recording medium as claimed in claim 52 , wherein said recording medium further makes the computer execute: a fourth processing of displaying said components on a display unit; and a fifth processing of collectively designating a movement direction and a movement distance for the components toward a direction turning to a predetermined layout positions, said second processing including a subprocessing of moving the components in accordance with the movement direction and the movement distance.
Claim 68
Dependent Claim
47 words
A recording medium as claimed in claim 63 , wherein said second processing includes the subprocessings of: enlarging distance between the components and a layout center into similar distances; automatically routing between terminals of each component; and compacting the components and the routes toward the layout center.
Claim 69
Dependent Claim
75 words
A recording medium as claimed in claim 52 , wherein said recording medium further makes the computer execute: a fourth processing of displaying said components on a display unit; and a fifth processing of collectively designating a movement direction and a movement distance for the components toward a direction apart from a predetermined layout positions, said second processing including a subprocessing of moving the components in accordance with the movement direction and the movement distance.
Claim 70
Dependent Claim
47 words
A recording medium as claimed in claim 65 , wherein said second processing includes the subprocessings of: enlarging distance between the components and a layout center into similar distances; automatically routing between terminals of each component; and compacting the components and the routes toward the layout center.
Claim 71
Dependent Claim
61 words
A recording medium as claimed in claim 52 , wherein said recording medium further makes the computer execute: a fourth processing of cutting off a partial area of the layout to replace the partial area by parallel movement and rotation; and a fifth processing of renewing connections between component terminals inside the partial area and component terminals outside the partial area.
Claim 72
Dependent Claim
32 words
A recording medium as claimed in claim 52 , wherein said recording medium further makes the computer execute a processing of switching the order of first and second routes with each other.
References Cited (Backward Citations)
JPS63181349A
Cited
JPH01279373A
Cited
JPH05274392A
Cited
JPH06268062A
Cited
JPH09204461A
Cited
US5987086A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-10-08 | 2005-04-09 | 2005-10-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-10-08 | 2009-04-09 | 2009-10-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-10-08 | 2013-04-09 | 2013-10-09 | $7700.00 | Window Closed / Lapsed |