Routing program generating method and apparatus therefor, placement program generating method and apparatus therefor, and automatic routing method and apparatus therefor

• US 5,644,500 A
• Filed: 07/01/1996
• Issued: 07/01/1997
• Est. Priority Date: 03/18/1994
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Iwahara, Kazufumi, Miura, Hiroshi, Yamashita, Yasuhiro, Murakami, Naoki, Okano, Mitsunobu, Sakata, Toshiyasu, Yamane, Atsushi, Nishimura, Masaharu, Yamada, Ryouji, Hamamura, Hirofumi, Iida, Kazuyuki, Ariyama, Masato, Katsumata, Akira, Yasuda, Mitsuru, Orihara, Hiroyuki
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): LOUIS JACQUES, JACQUES H
• Application Number:
  US08/673,472
• Time in Patent Office: 365 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 364/578, 257/206, 257/209, 257/211, 257/390, 327/566, 326/37
• US Class Current: 716/120
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

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.

Claims

1. 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.

2. 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.

3. A routing method according to claim 2, wherein said routing approach is prepared, in advance, as a plurality of routing fundamental process steps.

4. 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.

5. 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.

6. 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.

7. 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.

8. A routing method according to claim 1, wherein said routing approach is prepared, in advance, as a plurality of routing fundamental process steps.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. 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.

33. 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.

34. 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.

35. 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.

36. 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.

37. 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.

38. 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.

39. 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.

40. 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.

41. 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.

42. 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.

43. 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.

44. 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.

45. 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.

46. 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.

47. 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.

48. 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.

49. 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.

50. 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.