Printed circuit board CAD device which alternates placing components and routing connectors between them

• US 5,847,968 A
• Filed: 02/16/1996
• Issued: 12/08/1998
• Est. Priority Date: 02/20/1995
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Nishimura, Yuichi, Tsuchida, Masayuki, Miura, Shinji, Yoshimura, Hiroyuki, Uemura, Hirokazu
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Fiul, Dan
• Application Number:
  US08/605,540
• Time in Patent Office: 1,026 Days
• Field of Search: 364/488-491, 395/560
• US Class Current: 716/123
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347

Abstract

When a component is placed on a circuit board, a placement position is determined by method of elastic center. Then, it is determined whether the component was placed on the circuit board. After that, connectors are routed between the component and a design candidate component which is already placed. After that, the next component is set, and the above mentioned packaging processing is repeated.

Claims

1. A printed circuit board CAD device for determining a placement position of each component and routing paths of connectors between them in a component group in a schematic circuit diagram comprising:

placement order storage means in which placement order included in the component group is stored;

read-out means for reading out, while avoiding any components whose placement positions are already determined, a next component waiting to be read out from the placement order storage means;

occupied area storage means in which occupied area information describing, when the next component is read out by the read-out means, an area occupied by a component whose placement position is already determined and connectors whose routing paths area are already determined on a circuit board is stored;

placement position determination means for determining a placement position of a latest component read out by the read-out means, while avoiding the occupied area on the circuit board by referring to the occupied area information already stored in the occupied area storage means;

routing path determination means for determining, during a period starting from a point when the placement position of the latest component is determined by the placement position determination means to a point when a placement position of the next component is determined by the placement position determination means, routing paths of connectors between terminals of the latest component and terminals of a component whose placement position is already determined, avoiding the occupied area on the circuit board by referring to the occupied area information already stored in the occupied area storage means;

write-in means for writing, when the routing paths of the connectors are determined, occupied area information describing an area occupied by the component whose placement position is already determined and by the connectors whose routing paths are already determined in a space area of the occupied area storage means; and

instruction means for instructing, when the occupied area information, describing the area occupied by the component whose placement position is already determined and by the connectors whose routing paths are already determined, is written in the space area of the occupied area storage means, the read-out means to read out a next component waiting to be read out from the placement order storage means.

2. The printed circuit board CAD device of claim 1, wherein the placement position determination means includes:

calculation means for calculating, by placement position determination algorithm, a placement position of the latest component read out by the read-out means outside of areas occupied by components whose placement positions are already determined; and

overlap determination means for determining whether the calculated placement position overlaps with the connectors whose routing paths are already determined;

change means for changing, when overlap of the calculated placement position and the connectors whose routing paths are determined is recognized, routing paths of obstacle connectors; and

update means for updating, when the routing paths of the obstacle connectors are changed, occupied area information describing an area occupied by the obstacle connectors, the occupied area information being already stored in the occupied area storage means.

3. The printed circuit board CAD device of claim 2, wherein the change means includes:

space area determination unit for determining whether a space area is adjacent to the area occupied by the obstacle connectors, the space area being equal to or larger than the size of the area occupied by the obstacle connectors; and

change unit for changing the routing paths of the obstacle connectors so that they pass through the space area when adjacency of the space area and the area occupied by the obstacle connectors is recognized.

4. The printed circuit board CAD device of claim 3, wherein the change means further includes:

read-out unit for reading out, when adjacency of the space area and the area occupied by the obstacle connectors is not recognized, occupied area information describing an area occupied by components and connectors in the vicinity of the area occupied by the obstacle connectors, the occupied area information being written in the occupied area storage means; and

movement unit for moving, based on the occupied area information read out by the read-out unit, the components and connectors away from the obstacle connectors,

wherein the change unit changes the routing paths of the obstacle connectors so that they pass through an area generated by the movement of the occupied area information, and

the update means further updates occupied area information describing an area occupied by components and connectors to be moved when the component and connectors are moved, the occupied area information being written in the occupied area storage means.

5. The printed circuit board CAD device of claim 1 further includes:

net information storage means in which net information describing all connectors and terminals of components connected with the connectors in the schematic circuit diagram is stored, and

wherein the routing path determination means includes;

fetch means for fetching, when a placement position of the latest component is determined by the placement position determination means, net information describing connection relation between terminals of the latest component and terminals of the component whose placement position is already determined; and

routing path creation means for creating routing paths between terminals described by the fetched net information outside of areas occupied by connectors whose routing paths are already determined on the circuit board.

6. The printed circuit board CAD device of claim 5, wherein the routing path determination means includes:

overlap determination means for determining whether the routing paths created by the routing path creation means overlap with a component whose placement position is already determined;

change means for changing, when overlap of the routing paths created by the routing path creation means and the component whose placement position is already determined is recognized, placement position of the obstacle component and routing paths of its connectors; and

update means for updating, when the placement position of obstacle component and routing paths of its connectors are changed, occupied area information written in the occupied area storage means, the occupied area information describing an area occupied by the obstacle component and an area occupied by the obstacle connectors.

7. The printed circuit board CAD device of claim 6, wherein the change means includes:

space area determination unit for determining whether a space area is adjacent to the area occupied by the obstacle connectors, the space area being equal to or larger than the size of the area occupied by the obstacle connectors; and

change unit for changing, when adjacency of the space area and the area occupied by the obstacle connectors is recognized, the placement positions of the obstacle component so that it exists in the space area and routing paths of connectors of the obstacle component so that they pass through the space area.

8. The printed circuit board CAD device of claim 7, wherein the change means includes:

read-out unit for reading out, when adjacency of the space area and the area occupied by the obstacle connectors is not recognized, occupied area information describing an area occupied by components and connectors in the vicinity of the area occupied by the obstacle components, the occupied area information being written in the occupied area storage means; and

movement unit for moving, based on the occupied area information read out by the read-out unit, the components and connectors away from the obstacle connectors,

wherein the change unit changes placement position of the obstacle component so that it exists in the space area, and routing paths of connectors of the obstacle component so that they pass through the space area,

wherein the update means further updates the occupied area information describing an area occupied by components and connectors to be moved when the occupied area information is moved, the occupied area information being written in the occupied area storage means.

9. The printed circuit board CAD device of claim 5, wherein information describing whether a connector is a critical path is added to the net information stored in the net information storage means, and

wherein the printed circuit board CAD device further includes:

determination means for determining whether the net information fetched by the fetch means is about a critical path by referring to the net information storage means when routing paths are created by the routing path creation means for the component read out by the read-out means;

position moving means for moving, when a critical path is recognized, the component whose placement position is determined to a component which is connected to the component through the critical path, shortening length of the critical path; and

update means for updating, when the placement position is moved, a placement position of the component read out by the read-out means from the occupied area storage means with a placement position after the movement, and routing paths of its connectors with routing paths after the movement.

10. The printed circuit board CAD device of claim 9, wherein the position moving means moves the component whose placement position is determined to a component which is connected to the component through a critical path in a broken line, reducing the critical path using a given scale.

11. The printed circuit board CAD device of claim 5, wherein the information describing whether a connector is included in a bus group is added to the net information stored in the net information storage means;

and

wherein the printed circuit board CAD device further includes;

determination means for determining whether the net information fetched by the fetch means is about a bus group by referring to the net information storage means when routing paths are created by the routing path creation means for a component read out by the read-out means;

position moving means for moving, when a bus group is recognized, the component whose placement position is determined to a component which is connected to the component through the bus group, shortening length of the bus group; and

update means for updating, when the placement position is moved, a placement position of the component read out by the read-out means from the occupied area storage means with a placement position after the movement, and routing paths of its connectors with routing paths after the movement.

12. The printed circuit board CAD device of claim 11, wherein the position moving means moves the component whose placement position is determined to a component connected to the component through the bus group in broken lines, reducing the entire bus group using a given scale.

13. The printed circuit board CAD device of claim 1 further includes:

length and width measurement storage means for storing length and width measurements of each component in the component group;

component area calculation means for calculating, when the placement position determination means cannot determine a placement position of a component, area to be occupied by the component and subsequent components on the circuit board by referring to the length and width measurement storage means;

connector area estimation means for estimating area to be occupied by connectors between terminals of the component whose placement position cannot be determined and its subsequent components and terminals of a component whose placement position is already determined; and

enlargement means for enlarging circuit board area by total of area to be occupied by the component whose placement position cannot be determined and subsequent components and area to be occupied by connectors between terminals of the component whose placement positions cannot be determined and its subsequent components and terminals of the component whose placement position is already determined.

14. The printed circuit board CAD device of claim 13,

wherein the length and width measurement storage means stores length and width measurements of each component in the component group,

wherein the component area calculation means calculates, when the placement position determination means cannot determine a placement position of a component, area to be occupied by the component and subsequent components on the circuit board by referring to the length and width measurement storage means,

wherein the connector area estimation means estimates area to be occupied by connectors between terminals of the component whose placement position cannot be determined and its subsequent components and terminals of a component whose placement position is already determined, and

wherein the enlargement means enlarges circuit board area by total of area to be occupied by the component whose placement position cannot be determined and subsequent components and area to be occupied by connectors between terminals of the component whose placement positions cannot be determined and its subsequent components and terminals of the component whose placement position is already determined.

15. The printed circuit board CAD device of claim 1 further includes:

function block storage means for storing all function blocks and components included in each of them in the schematic circuit diagram;

area storage means for storing all function blocks in the schematic circuit diagram and a circuit board area assigned to each of them; and

wherein the placement position determination means determines placement positions of components included in a function block in a circuit board area assigned to the function block, referring to the area storage means, and

the routing path determination means determines, when a placement position of a component is determined, routing paths of connectors between terminals of the component and terminals of a component whose placement position is already determined in a function block which includes the component.

16. The printed circuit board CAD device of claim 15 further includes:

function block determination means for determining, when the placement position determination means cannot determine a placement position of a component, which function block includes the component; and

area enlargement means for enlarging a circuit board area assigned to the function block which includes the component.

17. The printed circuit board CAD device of claim 1 further includes:

outline generation means for generating, when placement positions of components in the schematic circuit diagram are determined and all routing paths between terminals of the components are determined, an outline of an area occupied by the components; and

circuit board area creation means for creating a circuit board area enclosed by the outline.

18. The printed circuit board CAD device of claim 1 further includes extending means for extending, when routing paths of connectors of one component are determined by the routing path determination means, a given length of connector from terminals of a component which is to be connected with terminals of the next component.

19. The printed circuit board CAD device of claim 18 further includes:

occupied terminal storage means for storing a prohibition area around terminals of a chip component in an area occupied by components whose placement positions are determined, the prohibition information corresponding to net information on the terminals; and

terminal presence determination means for determining whether net information is stored in the occupied terminal storage means, the net information including terminals of the latest component read out by the read-out means and terminals of a component which is already placed,

wherein the placement position determination means determines a placement position of the component read out by the read-out means, allowing overlap of a pair of terminals included in the net information stored in the occupied terminal storage means.

20. The printed circuit board CAD device of claim 1, wherein the placement position determination means includes:

first calculation means for calculating, by placement position determination algorithm, a placement position of the latest component read out by the read-out means outside of areas occupied by components whose placement positions are already determined;

first determination means for determining whether the calculated placement position overlaps with connectors whose routing paths are already determined;

first change means for changing, when overlap of the calculated placement position and the connectors whose routing paths are already determined is recognized, routing paths of the obstacle connectors;

first update means for updating, when the routing paths of the obstacle connectors are changed, occupied area information describing an area occupied by the obstacle connectors, the occupied area information being written in the occupied area storage means;

second determination means for determining whether the routing paths created by the routing paths creation means overlap with a component whose placement position is already determined;

second change means for changing, when overlap of the routing paths created by the routing paths creation means and the component whose placement position is determined is recognized, a placement position of the obstacle component and routing paths of its connectors; and

second update means for updating, when the placement position of the obstacle component and the routing paths of its connectors are changed, occupied area information written in the occupied area storage means, the occupied area information describing an area occupied by the obstacle component and an area occupied by the obstacle connectors.

21. A printed circuit board CAD device for determining a placement position of each component and routing paths of connectors between them in a schematic circuit diagram comprising:

placement order storage means in which placement order of components is stored;

read-out means for reading out, while avoiding any components whose placement positions are already determined, a next component waiting to be read out from the placement order storage means;

occupied area storage means in which occupied area information describing, when the next component is read out by the read-out means, an area occupied by a component whose placement position is already determined and connectors whose routing paths area are already determined on a circuit board is stored;

placement position determination means for determining a placement position of a latest component read out by the read-out means, while avoiding the occupied area on the circuit board by referring to the occupied area information already stored in the occupied area storage means, including determining a space area adjacent an occupied area on the circuit board;

routing path determination means for determining, during a period starting from a point when the placement position of the latest component is determined by the placement position determination means to a point when a placement position of the next component is determined by the placement position determination means, routing paths of connectors between terminals of the latest component and terminals of a component whose placement position is already determined, avoiding the occupied area on the circuit board by referring to the occupied area information already stored in the occupied area storage means, including the space area adjacent an occupied area which can be used for routing paths;

write-in means for writing, when the routing paths of the connectors are determined, occupied area information describing an area occupied by the component whose placement position is already determined and by the connectors whose routing paths are already determined in a space area of the occupied area storage means, including any adjacent space area that is now occupied; and

instruction means for instructing, when the occupied area information, describing the area occupied by the component whose placement position is already determined and by the connectors whose routing paths are already determined, is written in the space area of the occupied area storage means, the read-out means to read out a next component waiting to be read out from the placement order storage means.