US5644500A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Routing program generating method and apparatus therefor, placement program generating method and apparatus therefor, and automatic routing method and apparatus therefor
Assignee: Fujitsu Ltd
•
Filing: 1996-07-01
•
Granted: 1997-07-01
•
Expires: 2016-07-01
Abstract
Abstract This invention is directed to a method and apparatus to find out an optimum solution in automatic routing or automatic placement with certainty and at a high-speed to improve a routing rate, and to realize automatic routing in a high-density. To these end, a routing approach is selected in a conversational mode while routing efficiency is consulted to compose routing processing procedure so as to generate a routing program. Besides, component placement processing procedures designated according to placement control information are combined to generate the placement program. A straight line between component pins adjacent to each other is defined as a chord, a wave for maze method routing is generated from a start point toward an end point of a routing path and propagated between the chords adjacent to each other. Positions of the chords through which the wave has passed until reaching the end point from the start point are successively stored and the positions through which the wave has passed is traced back to the start point from the end point when the wave reaches the end point to decide a routing path of the routing pattern. The method and apparatus of this invention are applicable to routing design or component placement design of LSIs, multichip modules, printed circuit boards, etc.
Inventors
- 👤 Hiroshi Miura
- 👤 Masato Ariyama
- 👤 Kazuyuki Iida
- 👤 Kazufumi Iwahara
- 👤 Mitsunobu Okano
- 👤 Hiroyuki Orihara
- 👤 Akira Katsumata
- 👤 Toshiyasu Sakata
- 👤 Masaharu Nishimura
- 👤 Hirofumi Hamamura
- 👤 Naoki Murakami
- 👤 Mitsuru Yasuda
- 👤 Yasuhiro Yamashita
- 👤 Ryouji Yamada
- 👤 Atsushi Yamane
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 19:30
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392; G06F30/394
Claims Analysis
Total Claims: 56
Claim 1
Independent Claim
97 words
A routing method for composing a routing processing procedure on the basis of predetermined routing design data to generate a routing in the placement of a plurality of components on at least a circuit board, comprising the steps of: composing the routing processing procedure by selecting a routing approach in a communication mode; and evaluating routing efficiency to generate said routing program, wherein said routing program is used in the placement of said plurality of components on at least a circuit board based on at least one of the sizes, types and power consumption of said components.
Claim 2
Dependent Claim
97 words
A routing method for composing a routing processing procedure on the basis of predetermined routing design data to generate a routing in the placement of a plurality of components on at least a circuit board, comprising the steps of: composing the routing processing procedure by selecting a routing approach in a communication mode; and evaluating routing efficiency to generate said routing program, wherein said routing program is used in the placement of said plurality of components on at least a circuit board based on at least one of the sizes, types and power consumption of said components.
Claim 3
Dependent Claim
45 words
A routing method according to claim 1, wherein in a stage of an electrical device package design based on said predetermined routing design data, said routing approach is selected and said routing processing procedure is composed as a result of said electrical device package design.
Claim 4
Dependent Claim
23 words
A routing method according to claim 2, wherein said routing approach is prepared, in advance, as a plurality of routing fundamental process steps.
Claim 5
Dependent Claim
25 words
A routing method according to claim 3, wherein said routing processing procedure is designated in a routing control language when said routing approach is selected.
Claim 6
Dependent Claim
28 words
A routing method according to claim 4, wherein routed object information, routed place information, routing condition information, and routing order information are designated as said routing control language.
Claim 7
Dependent Claim
25 words
A routing method according to claim 2, wherein said routing processing procedure is designated in a routing control language when said routing approach is selected.
Claim 8
Dependent Claim
28 words
A routing method according to claim 6, wherein routed object information, routed place information, routing condition information, and routing order information are designated as said routing control language.
Claim 9
Dependent Claim
23 words
A routing method according to claim 1, wherein said routing approach is prepared, in advance, as a plurality of routing fundamental process steps.
Claim 10
Dependent Claim
25 words
A routing method according to claim 8, wherein said routing processing procedure is designated in a routing control language when said routing approach is selected.
Claim 11
Dependent Claim
28 words
A routing method according to claim 9, wherein routed object information, routed place information, routing condition information, and routing order information are designated as said routing control language.
Claim 12
Dependent Claim
25 words
A routing method according to claim 1, wherein said routing processing procedure is designated in a routing control language when said routing approach is selected.
Claim 13
Dependent Claim
28 words
A routing method according to claim 11, wherein routed object information, routed place information, routing condition information, and routing order information are designated as said routing control language.
Claim 14
Dependent Claim
144 words
A routing program generating apparatus for composing a routing processing procedure on the basis of predetermined design data to generate a routing program for use in the placement of a plurality of components on at least a circuit board, comprising: a routing efficiency evaluating means for evaluating routing efficiency depending on a routing approach on the basis of said predetermined routing design data; a display means for displaying a result of evaluation made by said routing efficiency evaluating means; and a selecting means for selecting the routing approach, wherein said selecting means selects the routing approach in a communication mode while said result of the evaluation displayed on said display means is consulted to compose the routing processing procedure, thereby generating said routing program, wherein said routing proqram is used in the placement of said plurality of components on at least a circuit board.
Claim 15
Dependent Claim
144 words
A routing program generating apparatus for composing a routing processing procedure on the basis of predetermined design data to generate a routing program for use in the placement of a plurality of components on at least a circuit board, comprising: a routing efficiency evaluating means for evaluating routing efficiency depending on a routing approach on the basis of said predetermined routing design data; a display means for displaying a result of evaluation made by said routing efficiency evaluating means; and a selecting means for selecting the routing approach, wherein said selecting means selects the routing approach in a communication mode while said result of the evaluation displayed on said display means is consulted to compose the routing processing procedure, thereby generating said routing program, wherein said routing proqram is used in the placement of said plurality of components on at least a circuit board.
Claim 16
Dependent Claim
44 words
A routing program generating apparatus according to claim 13, wherein in a stage of a packaging design based on said predetermined routing design data, said selecting means selects said routing approach to compose said routing processing procedure as a result of said package design.
Claim 17
Dependent Claim
25 words
A routing program generating apparatus according to claim 14, wherein said routing approach is prepared, in advance, as a plurality of routing fundamental process steps.
Claim 18
Dependent Claim
33 words
A routing program generating apparatus according to claim 15 further comprising: a designating means for designating the routing processing procedure in a routing control language when said selecting means selects said routing approach.
Claim 19
Dependent Claim
38 words
A routing program generating apparatus according to claim 16, wherein said designating means designates routed object information, routed place information, routing condition information and routing order information as said routing control language to designate the routing processing procedure.
Claim 20
Dependent Claim
33 words
A routing program generating apparatus according to claim 14 further comprising: a designating means for designating the routing processing procedure in a routing control language when said selecting means selects said routing approach.
Claim 21
Dependent Claim
38 words
A routing program generating apparatus according to claim 18, wherein said designating means designates routed object information, routed place information, routing condition information and routing order information as said routing control language to designate the routing processing procedure.
Claim 22
Dependent Claim
25 words
A routing program generating apparatus according to claim 13, wherein said routing approach is prepared in advance, as a plurality of routing fundamental process steps.
Claim 23
Dependent Claim
32 words
A routing program generating apparatus according to claim 20 further comprising: a designating means designating the routing processing procedure in a routing control language when said selecting means selects said routing approach.
Claim 24
Dependent Claim
38 words
A routing program generating apparatus according to claim 21, wherein said designating means designates routed object information, routed place information, routing condition information and routing order information as said routing control language to designate the routing processing procedure.
Claim 25
Dependent Claim
33 words
A routing program generating apparatus according to claim 13 further comprising: a designating means for designating the routing processing procedure in a routing control language when said selecting means selects said routing approach.
Claim 26
Dependent Claim
38 words
A routing program generating apparatus according to claim 23, wherein said designating means designates routed object information, routed place information, routing condition information and routing order information as said routing control language to designate a routing processing procedure.
Claim 27
Dependent Claim
99 words
A placement method for use in the placement of a plurality of components on at least a circuit board, comprising the steps of: when placing said plurality of components within a placed region on the basis of predetermined design dam, designating component placement processing procedures according to placement control information depending on said predetermined design data and said placed region; and combining said designated component placement processing procedures to generate a placement program for automatically placing said plurality of components within said placed region based on at least one of the sizes, types and power consumption of said components.
Claim 28
Dependent Claim
99 words
A placement method for use in the placement of a plurality of components on at least a circuit board, comprising the steps of: when placing said plurality of components within a placed region on the basis of predetermined design dam, designating component placement processing procedures according to placement control information depending on said predetermined design data and said placed region; and combining said designated component placement processing procedures to generate a placement program for automatically placing said plurality of components within said placed region based on at least one of the sizes, types and power consumption of said components.
Claim 29
Dependent Claim
31 words
A placement method according to claim 25, wherein placed component grouping information, placed region designating information, placing condition information and group placing order information are designated as said placement control information.
Claim 30
Dependent Claim
100 words
A placement apparatus for automatically placing a plurality of components within a placed region of at least a circuit board on the basis of predetermined design data comprising: a designating means for designating component placement processing procedures according to placement control information depending on said predetermined design data and said placed region, said placement processing procedures designated by said designating means being combined to generate a placement program for automatically placing said plurality of components within said placed region of at least a circuit board based on at least one of the sizes, types and power consumption of said components.
Claim 31
Dependent Claim
100 words
A placement apparatus for automatically placing a plurality of components within a placed region of at least a circuit board on the basis of predetermined design data comprising: a designating means for designating component placement processing procedures according to placement control information depending on said predetermined design data and said placed region, said placement processing procedures designated by said designating means being combined to generate a placement program for automatically placing said plurality of components within said placed region of at least a circuit board based on at least one of the sizes, types and power consumption of said components.
Claim 32
Dependent Claim
35 words
A placement program generating apparatus according to claim 27, wherein said designating means designates placed component grouping information, placed region designating information, placing condition information and group placing order information as said placement control information.
Claim 33
Dependent Claim
140 words
An automatic routing method for deciding a routing path of a routing pattern in order to automatically route said routing pattern on a circuit board having a number of component pins comprising the steps of: defining a straight line connecting component pins adjacent to each other as a chord; generating a wave for maze method routing from a start point of said routing path toward an end point of the same; propagating said wave between said chords adjacent to each other; successively storing positions of said chords through which said wave has passed until reaching said end point from said start point; and tracing said positions of said chords through which said wave has passed back to said start point from said end point when said wave reaches said end point to determine a routing path for said routing pattern.
Claim 34
Dependent Claim
140 words
An automatic routing method for deciding a routing path of a routing pattern in order to automatically route said routing pattern on a circuit board having a number of component pins comprising the steps of: defining a straight line connecting component pins adjacent to each other as a chord; generating a wave for maze method routing from a start point of said routing path toward an end point of the same; propagating said wave between said chords adjacent to each other; successively storing positions of said chords through which said wave has passed until reaching said end point from said start point; and tracing said positions of said chords through which said wave has passed back to said start point from said end point when said wave reaches said end point to determine a routing path for said routing pattern.
Claim 35
Dependent Claim
39 words
An automatic routing method according to claim 29, wherein when said wave is propagated between said adjacent chords, the passing of said routing pattern is judged on the basis of a capacity between said component pins forming said chord.
Claim 36
Dependent Claim
89 words
An automatic routing method according to claim 30 further comprising the steps of: calculating a total sum of a line width of a routing pattern passing through said chord in this wave propagation and line widths of routing patterns that have been permitted to pass through said chord up to this wave propagation; comparing said total sum of line widths with a distance between said component pins forming said chord; and permitting said routing pattern to pass when said total sum of line widths is smaller than said distance.
Claim 37
Dependent Claim
48 words
An automatic routing method according to claim 31 further comprising the steps of: when a plurality of routing patterns are permitted to pass through said chord, storing a position on said chord through which each of said plural routing patterns passes as a relative position on said chord.
Claim 38
Dependent Claim
49 words
An automatic routing method according to claim 32 further comprising the steps of: when at least two routing patterns pass through said chords adjacent to each other, judging crossing of said routing patterns on the basis of relative positions of each of said routing patterns on said adjacent chords.
Claim 39
Dependent Claim
41 words
An automatic routing method according to claim 33 further comprising the steps of: after all routing paths of said routing patterns on said circuit board have been decided, equally spacing said routing patterns passing through said chord between said component pins.
Claim 40
Dependent Claim
41 words
An automatic routing method according to claim 32 further comprising the steps of: after all routing paths of said routing patterns on said circuit board have been decided, equally spacing said routing patterns passing through said chord between said component pins.
Claim 41
Dependent Claim
48 words
An automatic routing method according to claim 30 further comprising the steps of: when a plurality of routing patterns are permitted to pass through said chord, storing a position on said chord through which each of said plural routing patterns passes as a relative position on said chord.
Claim 42
Dependent Claim
50 words
An automatic routing method according to claim 36 further comprising the steps of: when at least two routing patterns pass through said chords adjacent to each other, judging crossing of said routing patterns on the basis of a relative positions of each of said routing patterns on said adjacent chords.
Claim 43
Dependent Claim
41 words
An automatic routing method according to claim 37 further comprising the steps of: after all routing paths of said routing patterns on said circuit board have been decided, equally spacing said routing patterns passing through said chord between said component pins.
Claim 44
Dependent Claim
41 words
An automatic routing method according to claim 36 further comprising the steps of: after all routing paths of said routing patterns on said circuit board have been decided, equally spacing said routing patterns passing through said chord between said component pins.
Claim 45
Dependent Claim
172 words
An automatic routing apparatus deciding a routing path of a routing pattern in order to automatically route said routing pattern on a circuit board having a number of component pins comprising: a chord information forming means for forming positional information about a chord that is a straight line connecting said component pins adjacent to each other on the basis of positional information about said component pins; and a maze routing control means for generating a wave for maze method routing from a start point toward an end point of said routing path, propagating wave between said adjacent chords on the basis of information about said chords formed by said chord information forming means, successively storing positions of said chords through which said wave has passed until reaching said end point from said start point, and tracing said positions of said chords through which said wave has passed back to said start point from said end point when said wave reaches said end point to decide a routing path of said routing pattern.
Claim 46
Dependent Claim
172 words
An automatic routing apparatus deciding a routing path of a routing pattern in order to automatically route said routing pattern on a circuit board having a number of component pins comprising: a chord information forming means for forming positional information about a chord that is a straight line connecting said component pins adjacent to each other on the basis of positional information about said component pins; and a maze routing control means for generating a wave for maze method routing from a start point toward an end point of said routing path, propagating wave between said adjacent chords on the basis of information about said chords formed by said chord information forming means, successively storing positions of said chords through which said wave has passed until reaching said end point from said start point, and tracing said positions of said chords through which said wave has passed back to said start point from said end point when said wave reaches said end point to decide a routing path of said routing pattern.
Claim 47
Dependent Claim
51 words
An automatic routing apparatus according to claim 40 further comprising: a passability judging means for judging the passing of said routing pattern on the basis of a capacity between said component pins forming said chord when said maze routing control means propagates said wave between said chords adjacent to each other.
Claim 48
Dependent Claim
112 words
An automatic routing apparatus according to claim 41, wherein said passability judging means comprises: an adding means for calculating a total sum of a line width of a routing pattern passing through said chord in the wave propagation and line widths of routing patterns that have been permitted to pass through said chord up to the wave propagation; a comparing means for comparing said total sum of line widths calculated by said adding means with a distance between said component pins forming said chord; and a judging means for permitting said routing pattern to pass if said comparing means judges that said total sum of line widths is smaller than said distance.
Claim 49
Dependent Claim
46 words
An automatic routing apparatus according claim 42, wherein when said passability judging means permits a plurality of routing patterns to pass through said chord, a position on said chord through which each of said routing patterns passes is stored as a relative position on said chord.
Claim 50
Dependent Claim
51 words
An automatic routing apparatus according to claim 43 further comprising: a crossing judging means for judging, when at least two routing patterns pass through said chords adjacent to each other, crossing of said routing patterns on the basis of relative positions on said adjacent chords of each of said routing patterns.
Claim 51
Dependent Claim
43 words
An automatic routing apparatus according to claim 44 further comprising: an equally spacing means for equally spacing said routing patterns between said component pins after said maze routing control means has decided all routing paths of said routing patterns on said circuit board.
Claim 52
Dependent Claim
43 words
An automatic routing apparatus according to claim 43 further comprising: an equally spacing means for equally spacing said routing patterns between said component pins after said maze routing control means has decided all routing paths of said routing patterns on said circuit board.
Claim 53
Dependent Claim
47 words
An automatic routing apparatus according to claim 41, wherein when said passability judging means permits a plurality of routing patterns to pass through said chord, a position on said chord through which each of said routing patterns passes is stored as a relative position on said chord.
Claim 54
Dependent Claim
51 words
An automatic routing apparatus according to claim 47 further comprising: a crossing judging means for judging, when at least two routing patterns pass through said chords adjacent to each other, crossing of said routing patterns on the basis of relative positions on said adjacent chords of each of said routing patterns.
Claim 55
Dependent Claim
43 words
An automatic routing apparatus according to claim 48 further comprising: an equally spacing means for equally spacing said routing patterns between said component pins after said maze routing control means has decided all routing paths of said routing patterns on said circuit board.
Claim 56
Dependent Claim
43 words
An automatic routing apparatus according to claim 47 further comprising: an equally spacing means for equally spacing said routing patterns between said component pins after said maze routing control means has decided all routing paths of said routing patterns on said circuit board.
References Cited (Backward Citations)
US4593351A
Cited
US4593363A
Cited
US4805113A
Cited
US4754408A
Cited
US4876656A
Cited
US5050090A
Cited
US5200908A
Cited
JPH03257674A
Cited
JPH04286077A
Cited
US5465218A
Cited
US5550750A
Cited
US5513119A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-06-30 | 2000-12-30 | 2001-07-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-06-30 | 2004-12-30 | 2005-07-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-06-30 | 2008-12-30 | 2009-07-01 | $7700.00 | Window Closed / Lapsed |