Apparatus and method for placing a component

• US 6,529,791 B1
• Filed: 03/08/2000
• Issued: 03/04/2003
• Est. Priority Date: 03/15/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Takagi, Makoto
• Primary Examiner(s): Von Buhr, Maria N.
• Assistant Examiner(s): FRANK, ELLIOT L
• Application Number:
  US09/520,729
• Time in Patent Office: 1,091 Days
• Field of Search: 700/97, 700/121, 703/1, 716/8, 716/9
• US Class Current: 700/121
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

Candidate locations in which each of the components is to be placed are assumed. Initially, all the cells on a printed circuit board are the candidates. The range of candidates for the location of each component is narrowed down in some way (for example, the farthest cell from a fixed component is excluded from candidates for the location in which a component that directly relates to the fixed component is to be placed). An approximation problem is created from an original placement problem and a solution that optimizes the approximation problem is find. This solution is a feasible solution of the original placement problem as well. The process of narrowing down the candidates and solving the approximation problem is repeated until one candidate (or more than one candidate having an equal evaluation value) is found ultimately to determine the placement of the component.

Claims

1. A component placement method performed on a component placement apparatus storing a plurality of position information items of a plurality of cells and a plurality of inter-component connection information items about connections between predetermined components in a plurality of components, each of which is placed in one of said cells, comprising steps of:

(a) calculating an evaluation value for each of said components in each of cells included in the current candidate locations of each component;

(b) calculation an evaluation value for each of said components in each of cells included in the current candidate locations according to said inter-component connection information;

(c) determining whether the reduction of said candidate for the location of one of said plurality of components is possible according to said evaluation value calculated at the step (b);

(d) repeating the steps (a) through (d) if it is determined at the step (c) that the reduction of said candidate for the location of any of said components is possible; and

(e) arranging said plurality of components according to the current candidate location if it is determined at the step (c) that the reduction of said candidates for the location of said components is not possible.

2. A component placement method performed on a component placement apparatus storing a plurality of position information items of a plurality of cells, a plurality of inter-component connection information items about connections between predetermined components in a plurality of components, each of which is placed in one of said cells, and a plurality of information items about connections between a component fixed at a predetermined position and a predetermined component in said plurality of components, comprising steps of:

(a) calculation the center of gravity for each of components according to current candidates for the location of each component;

(b) calculation an evaluation value for each of said components in each of cells included in the current candidate locations according to said inter-component connection information and said fixed-component connection information;

(c) determining whether the reduction of said candidate for the location of one of said plurality of components is possible according to said evaluation value calculated at the step (b);

(d) repeating the steps (a) through (d) if it is determined at the step (c) that the reduction of said candidate for the location of any of said components is possible;

(e) arranging said plurality of components according to the current candidate location if it is determined at the step (c) that the reduction of said candidates for the location of said components is not possible.

3. A component placement apparatus for storing a plurality of position information items of a plurality of cells and a plurality of inter-component connection information items about connections between predetermined components in a plurality of components, each of which is placed in one of said cells, comprising:

(a) a first calculator for calculation the center of gravity for each of components according to current candidates for the location of each component;

(b) a second calculator for calculation an evaluation value for each of said components in each of cells included in the current candidate locations according to said inter-component connection information;

(c) a determining means for determining whether the reduction of said candidates for the location of one of said plurality of components is possible according to said evaluation value calculated be said second calculator;

(d) a repeating means for activating said first and second calculator, said determining means and said repeating means if it is determined by the determining means that the reduction of said candidates for the location of any of said components is possible; and

(e) an arranging means for arranging said plurality of components according to the current candidate locations if it is determined by the determining means that the reduction of said candidates for the location of said components is not possible.

4. A storage medium containing a component placement control program executed on a component placement apparatus storing a plurality of position information items of a plurality of cells and a plurality of inter-component connection information items about connections between predetermined components in a plurality of components, each of which is placed in one of said cells, said program comprising:

(a) a program code for instructing said component placement apparatus to calculate the center of gravity for each of components according to current candidates for the location of each component;

(b) a program code for instructing said component placement apparatus to calculate an evaluation value for each of said components in each of cells included in the current candidate locations according to said inter-component connection information;

(c) a program code for instructing said component placement apparatus to determine whether the reduction of said candidate locations for one of said plurality of components is possible according to said evaluation value calculated by the execution of said program code (b);

(d) a program code for instructing said component placement apparatus to repeat to execute said program codes (a) through (d) if it is determined by the execution of said program code (c) that the reduction of said candidate for the location of any of said components is possible; and

(e) a program code for instructing said component placement apparatus to arrange said plurality of components according to the current candidate locations if it is determined by the execution of said program code (c) that the reduction of said candidates for the location of said components is not possible.

5. A storage medium containing a component placement control executed on a component placement apparatus storing a plurality of position information items of a plurality of cells, a plurality of inter-component connection information items about connections between predetermined components in a plurality of components, each of which is placed in one of said cells, and a plurality of information items about connections between a component fixed at a predetermined position and a predetermined component in said plurality of components, said program comprising:

(a) a program code for instructing said component placement apparatus to calculate the center of gravity for each of components according to current candidates for the location of each component;

(b) a program code for instructing said component placement apparatus to calculate an evaluation value for each of said components in each of cells included in the current candidate locations according to said inter-component connection information and said fixed-component connection information;

(c) a program code for instructing said component placement apparatus to determine whether the reduction of said candidate for the location of one of said plurality of components is possible according to said evaluation value calculated by the execution of said program code (b);

(d) a program code for instructing said component placement apparatus to repeat to execute said program codes (a) through (d) if it is determined by the execution of said program code (c) that the reduction of said candidates for the location of any of said components is possible;

(e) a program code for instructing said component placement apparatus to arrange said plurality of components according to the current candidate locations if it is determined by the execution of said program code (c) that the reduction of said candidates for the location of said components is not possible.