Wiring design apparatus, wiring determination apparatus and methods thereof

• US 6,295,634 B1
• Filed: 04/02/1999
• Issued: 09/25/2001
• Est. Priority Date: 04/02/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Matsumoto, Hiroyuki
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): JONES, HUGH M
• Application Number:
  US09/285,942
• Time in Patent Office: 907 Days
• Field of Search: 716/12-15, 703/2
• US Class Current: 716/126
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

The present invention relates generally to effectively design a wiring of a semiconductor package, etc., in a short time. A wiring design software (SW) reads in design information indicating disposition of pads on a chip, disposition of pins on a package, and relationship of correspondence between the pads and the pins, analyzes it to prepare a wiring problem, classifies the pads and the pins into source and sink elements, and assigns consecutive identification numbers to the pads and the pins with a same identification number being assigned to a pad and a pin which are connected each other (S102, . . . , S108). The wiring design SW generates a virtual triangle having a source/sink element as an apex by applying Delaunay triangulation to the source and the sink elements (S110). The wiring design SW level classifies the pins using the generated triangle (S200). The wiring design SW determines whether or not an edge of the triangle crosses a wiring and connects the edges which are determined to cross each other to derive a route of wiring (S220), outputting the result of wiring design (S118).

Claims

1. A wiring design apparatus for designing wiring routes which connect a plurality of sink elements on a plane to a plurality of source elements on said plane with a route lying on said plane comprising:

triangle generating means for generating by a Delaunay triangulation method a plurality of virtual triangles each having as apexes at least one of said sink elements and at least one of said source elements,

level classifying means for classifying a level for each sink element, wherein a first sink element forming an apex of one of said generated triangles, which also has as an apex one of said source elements, is classified as a lowest level (level 1), and a second sink element forming an apex of another of said generated triangles, which also has as an apex a sink element of a level K, is classified as a level (K+1), wherein K is an integer equal to or greater than 1, and

wiring design means for designing a plurality of wiring routes connecting said sink elements to corresponding source elements wherein the level of the sink element forming an apex of one of said generated triangles which is passed by the wiring is the lowest level for each of the wiring routes,

wherein the wiring design apparatus provides improved wiring routes connecting said sink elements on said plane to the corresponding source elements on said plane.

2. The wiring design apparatus of claim 1, wherein said wiring design means comprises:

crossing determination means for determining that an edge of one of said generated triangles having as an apex a sink element which is classified as a level no higher than (K+n) is an edge which is crossed by one or more wirings (wirings M) each connecting a sink element which is classified as a level no lower than K to a source element corresponding to said sink element, and

route deriving means for sequentially connecting two edges which form a same one of said triangles and are determined to be crossed by said wiring M to derive a route for each of the wiring M.

3. The wiring design apparatus of claim 2, wherein:

said plurality of source elements are bonding pads of a semiconductor chip mounted on a semiconductor package,

said plurality of sink elements are terminals provided in said semiconductor package surrounding said semiconductor chip, and

said plane is a wiring plane of said semiconductor package on which is provided wiring connecting each of said terminals to each of said bonding pads.

4. The wiring design apparatus of claim 2, wherein:

said wiring design means further comprises identification number assigning means for assigning a sequential identification number to each of the sink elements,

said crossing determination means determines that each edge of said triangle is crossed by wiring (wiring M′

) connecting each of the sink elements (points M′

), having an assigned number between the identification numbers of the sink elements at the ends of the edge, to each of the source elements corresponding to each of said points M′

, and

said route deriving means derives a route of each of the wirings M determined to be crossed by each of the edges of said triangle.

5. The wiring design apparatus of claim 4, wherein:

one or more sink elements (points N) having assigned identification numbers near a lowest identification number and one or more sink elements (points N′

) having assigned identification numbers near a highest identification number form apexes of one of said generated triangles,

said apparatus further comprises grouping means for separating from the sink elements a first group containing points N and a last group containing points N′

,

said crossing determination means determines, when a sink element of said first group and a sink element of said last group form apexes of said triangle, that each edge of said triangle is crossed by a wiring M′

which connects each of sink elements having assigned identification numbers which are larger than the identification number of the sink elements of the last group and sink elements having assigned identification numbers which are smaller than the identification number of the sink elements of the first group to each corresponding source element, and

said route deriving means derives the route of each of the wirings M′

which is determined to cross each edge of said triangle.

6. The wiring design apparatus of claim 5, wherein:

said apparatus further comprises route modifying means for modifying, when the number of said wirings M′

crossing the edge of said triangle is larger than a predetermined wiring capacity, a route of said wiring M′

crossing said edge to a route crossing an edge of another triangle.

7. A wiring design apparatus for designing wiring routes which connect a plurality of sink elements on a plane to a plurality of source elements on said plane with a route lying on said plane, said wiring passing a wiring route including a predetermined partial route, said apparatus comprising:

triangle generating means for generating by a Delaunay triangulation method a plurality of virtual triangles each having as apexes at least one of said sink elements and at least one of said source elements,

level classifying means for classifying a level for each sink element, wherein a first sink element forming an apex of one of said generated triangles, which also has as an apex one of said source elements, is classified as a lowest level (level 1), and a second sink element forming an apex of another of said generated triangles, which also has as an apex a sink element of a level K, is classified as a level (K+1), wherein K is an integer equal to or greater than 1,

weighting coefficient setting means for setting a weighting coefficient, wherein the weighting coefficient has as larger value as said level is higher, and

partial route selecting means for selecting said partial route such that a cumulative sum of multiplication of the length of each of said partial route by a weighting coefficient set to each of the edge of said triangle crossing each of said partial route is minimized,

wherein the wiring design apparatus provides improved wiring routes connecting the sink elements on said plane to the corresponding source elements on said plane.

8. A wiring determination apparatus for determining the validity of wiring routes which connect a plurality of sink elements on a plane to a plurality of source elements on said plane with a route lying on said plane comprising:

triangle generating means for generating by a Delaunay triangulation method a plurality of virtual triangles each having as apexes at least one of said sink elements and at least one of said source elements,

level classifying means for classifying a level for each sink element, wherein a first sink element forming an apex of one of said generated triangles, which also has as an apex one of said source elements, is classified as a lowest level (level 1), and a second sink element forming an apex of another of said generated triangles, which also has as an apex a sink element of a level K, is classified as a level (K+1), wherein K is an integer equal to or greater than 1, and

wiring determination means for determining that a wiring route connecting a sink element classified as a level K to a source element is valid when said wiring route crosses only an edge of said triangle having only sink elements classified as a level lower than (K+n+1) (n is an integer) as the ends thereof, and determining that a wiring connecting a sink element classified as a level K to a source element is invalid when said wiring route crosses an edge of said triangle having only sink elements classified as a level higher than (K−

1) as the ends thereof,

wherein the wiring determination apparatus identifies the validity of wiring routes connecting the sink elements on said plane to the corresponding source elements on said plane.

9. A wiring determination apparatus for determining the validity of wiring routes which connect a plurality of sink elements on a plane to a plurality of source elements on said plane with a route lying on said plane comprising:

triangle generating means for generating by a Delaunay triangulation method a plurality of virtual triangles each having as apexes at least one of said sink elements and at least one of said source elements,

level classifying means for classifying a level for each sink element, wherein a first sink element forming an apex of one of said generated triangles, which also has as an apex one of said source elements, is classified as a lowest level (level 1), and a second sink element forming an apex of another of said generated triangles, which also has as an apex a sink element of a level K, is classified as a level (K+1), wherein K is an integer equal to or greater than 1,

weighting coefficient setting means for setting a weighting coefficient, wherein the weighting coefficient has as larger value as said level is higher, and

wiring determination means for accumulating the sum of multiplication of the length of each of said partial route by a weighting coefficient set to each of the edge of said triangle crossing each of said partial route to determine the validity of each of said wiring routes,

wherein the wiring determination apparatus identifies the validity of wiring routes connecting the sink elements on said plane to the corresponding source elements on said plane.

10. A wiring design method for designing wiring routes which connect a plurality of sink elements on a plane to a plurality of source elements on said plane with a route lying on said plane comprising the steps of:

generating by a Delaunay triangulation method a plurality of virtual triangles having as apexes at least one of said sink elements and at least one of said source elements,

classifying a level for each sink element, wherein a first sink element forming an apex of one of said generated triangles, which also has as an apex one of said source elements, is classified as a lowest level (level 1), and a second sink element forming an apex of another of said generated triangles, which also has as an apex a sink element of a level K, is classified as a level (K+1), wherein K is an integer equal to or greater than 1, and

designing a plurality of wiring routes connecting said sink elements to corresponding source elements wherein the level of the sink element forming an apex of one of said generated triangles which is passed by the wiring is the lowest level for each of the wiring routes,

wherein the wiring design method provides improved wiring routes connecting said sink elements on said plane to the corresponding source elements on said plane.

11. The wiring design method of claim 10, further comprising:

determining that an edge of one of said generated triangles having as an apex a sink element which is classified as a level lower than (K+n+1) is an edge which is crossed by one or more wirings (wirings M) each connecting a sink element which is classified as a level above (K−

1) to a source element corresponding to said sink element, and sequentially connecting two edges which form a same one of said triangles and are determined to be crossed by said wiring M to derive a route of the wiring M.

12. A wiring determination method for determining the validity of wiring routes which connect a plurality of sink elements on a plane to a plurality of source elements on said plane with a route lying on said plane comprising:

generating by a Delaunay triangulation method a plurality of virtual triangles having as apexes one of said sink elements and one of said source elements,

classifying a level for each sink element, wherein a first sink element forming an apex of one of said generated triangles, which also has as an apex one of said source elements, is classified as a lowest level (level 1), and a second sink element forming an apex of another of said generated triangles, which also has as an apex a sink element of a level K, is classified as a level (K+1), wherein K is an integer equal to or greater than 1, and

determining that a wiring route connecting a sink element classified as a level K to a source element is valid when said wiring route crosses only an edge of said triangle having only sink elements classified as a level lower than (K+n+1) (n is an integer) as the ends thereof, and determining that a wiring route connecting a sink element classified as a level K to a source element is invalid when said wiring route crosses an edge of said triangle having only sink elements classified as a level higher than (K−

1) as the ends thereof,

wherein the wiring determination method determines the validity of wiring routes connecting said sink elements on said plane to the corresponding source elements on said plane.

13. A computer readable recording medium recording a program for use in a wiring design apparatus for designing wiring routes which connect a plurality of sink elements on a plane to a plurality of source elements on said plane with a route lying on said plane, said program causing a computer to execute:

a triangle generating step for generating by a Delaunay triangulation method a plurality of virtual triangles having as apexes at least one of said sink elements and at least one of said source elements,

a level classifying step for classifying a level for each sink element, wherein a first sink element forming an apex of one of said generated triangles, which also has as an apex one of said source elements, is classified as a lowest level (level 1), and a second sink element forming an apex of another of said generated triangles, which also has as an apex a sink element of a level K, is classified as a level (K+1), wherein K is an integer equal to or greater than 1, and

a wiring design step for designing a plurality of wiring routes connecting said sink elements to corresponding source elements wherein the level of the sink element forming an apex of one of said generated triangles which is passed by the wiring is the lowest level for each of the wiring routes, and

wherein said program provides improved wiring routes connecting said sink elements on said plane to the corresponding source elements on said plane.

14. The computer readable recording medium of claim 13, wherein said wiring design step further comprises:

a crossing determination step for determining that an edge of one of said generated triangles having as an apex a sink element which is classified as a level no higher than (K+n) is an edge which is crossed by one or more wirings (wiring M) each connecting a sink element which is classified as a level no lower than K to a source element corresponding to such sink element, and

a route deriving step for sequentially connecting two edges which form a same one of said triangles and are determined to be crossed by said wiring M to derive a route of the wiring M.

15. The computer readable recording medium of claim 14, wherein said wiring design step further comprises:

an identification number assigning step for assigning a sequential identification number to each of the sink elements,

said crossing determination step determines that each edge of said triangle is crossed by wiring (wiring M′

) connecting each of the sink elements (points M′

) having an assigned number between the identification numbers of the sink elements at the ends of the edge to each of the source elements corresponding to each of said points M′

, and

said route deriving step derives a route of each of the wirings M′

determined to be crossed by each of the edges of said triangle.

16. The computer readable recording medium of claim 15, wherein:

one or more sink elements (points N) having assigned identification numbers near a lowest identification number and one or more sink elements (points N′

) having assigned identification numbers near a highest identification number form apexes of one of said generated triangles,

said recording medium further records a grouping step for separating from the sink elements a first group containing points N and a last group containing points N′

,

said crossing determination step determines, when the sink element of said first group and the sink element of said last group form apexes of said triangle, that each edge of said triangle is crossed by a wiring M′

which connects each of sink elements having assigned identification numbers which are larger than the identification number of the sink elements of the last group and sink elements having assigned identification numbers which are smaller than the identification number of the sink elements of the first group to each corresponding source element, and

said route deriving step derives the route of each of the wirings M′

which is determined to cross each edge of said triangle.

17. The recording medium of claim 16, further comprising:

a route modifying step for modifying, when the number of said wirings M′

crossing the edge of said triangle is larger than a predetermined wiring capacity, a route of said wiring M′

crossing said edge to a route crossing the edge of another triangle.

18. A computer readable recording medium recording a program for use in a wiring design apparatus for designing wiring routes which connect a plurality of sink elements on a plane to a plurality of source elements on said plane with a route lying on said plane, said wiring passing a wiring route including a predetermined partial route, said program causing a computer to execute:

a triangle generating step for generating by a Delaunay triangulation method a plurality of virtual triangles having as apexes at least one of said sink elements and at least one of said source elements,

a level classifying step for classifying a level for each sink element, wherein a first sink element forming an apex of one of said generated triangles, which also has as an apex one of said source elements, is classified as a lowest level (level 1), and a second sink element forming an apex of another of said generated triangles, which also has as an apex a sink element of a level K, is classified as a level (K+1), wherein K is an integer equal to or greater than 1,

a weighting coefficient setting step for setting a weighting coefficient, wherein the weighting coefficient has as larger value as said level is higher, and

a partial route selecting step for selecting said partial route such that a cumulative sum of multiplication of the length of each of said partial route by a weighting coefficient set to each of the edge of said triangle crossing each of said partial route is minimized,

wherein said program provides improved wiring routes connecting said sink elements on said plane to the corresponding source elements on said plane.

19. A computer readable recording medium recording a program for use in a wiring determination apparatus for determining the validity of wiring routes which connect a plurality of sink elements on a plane to a plurality of source elements on said plane with a route lying on said plane, said program causing a computer to execute:

a triangle generating step for generating by a Delaunay triangulation method a plurality of virtual triangles having as apexes at least one of said sink elements and at least one of said source elements,

a level classifying step for classifying a level for each sink element, wherein a first sink element forming an apex of one of said generated triangles, which also has as an apex one of said source elements, is classified as a lowest level (level 1), and a second sink element forming an apex of another of said generated triangles, which also has as an apex a sink element of a level K, is classified as a level (K+1), wherein K is an integer equal to or greater than 1, and

a wiring determination step for determining that a wiring route connecting a sink element classified as a level K to a source element is valid when said wiring route crosses only an edge of said triangle having only sink elements classified as a level lower than (K+n+1) (n is an integer) as the ends thereof, and determining that a wiring connecting a sink element classified as a level K to a source element is invalid when said wiring route crosses an edge of said triangle having only sink elements classified as a level higher than (K−

1) as the ends thereof,

wherein said program determines the validity of wiring routes connecting said sink elements on said plane to the corresponding source elements on said plane.

20. A computer readable recording medium recording a program for use in a wiring determination apparatus for determining the validity of wiring routes which connect a plurality of sink elements on a plane to a plurality of source elements on said plane with a route lying on said plane, said wiring passing a wiring route including a predetermined partial route, said program causing a computer to execute:

a triangle generating step for generating by a Delaunay triangulation method a plurality of virtual triangles having as apexes at least one of said sink elements and at least one of said source elements,

a level classifying step for classifying a level for each sink element, wherein a first sink element forming an apex of one of said generated triangles, which also has as an apex one of said source elements, is classified as a lowest level (level 1), and a second sink element forming an apex of another of said generated triangles, which also has as an apex a sink element of a level K, is classified as a level (K+1), wherein K is an integer equal to or greater than 1,

a weighting coefficient setting step for setting a weighting coefficient, wherein the weighting coefficient has as larger value as said level is higher, and

a wiring determination step for accumulating the sum of multiplication of the length of each of said partial route by a weighting coefficient set to each of the edge of said triangle crossing each of said partial route to determine the validity of each of said wiring routes,

wherein said program determines the validity of wiring routes connecting said sink elements on said plane to the corresponding source elements on said plane.