System for assigning positions of block terminals in a VLSI

• US 5,404,313 A
• Filed: 03/25/1993
• Issued: 04/04/1995
• Est. Priority Date: 01/31/1989
• Status: Expired due to Term

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Fukui, Masahiro, Shiohara, Takahiro
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US08/037,463
• Time in Patent Office: 740 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A system in which blocks are classified into one or more fixed shape blocks in which terminal positions are previously determined and one or more variable shape blocks in which terminal positions are changeable. The system includes an initial terminal assign section for provisionally assigning terminal positions relating to the variable shape blocks for the purpose of minimizing the total length of the wirings; and a terminal distribution and assign section for evaluating the provisionally assigned terminal positions and for distributing the provisionally assigned terminal positions on the basis of the evaluation.

Claims

1. A system for assigning positions of block terminals, said terminals being connected through wirings, said system comprising:

initial terminal assign means for provisionally assigning terminal positions for the purpose of minimizing the total length of said wirings; and

terminal distribution and assign means for evaluating said provisionally assigned terminal positions and for distributing said provisionally assigned terminal positions on the basis of said evaluation, said terminal distribution and assign means comprising;

means for dividing an area at the periphery of each of said blocks into quantized areas;

means for setting a first set of vertices which corresponds to a set of terminals of said block;

means for setting a second set of vertices which corresponds to a set of said quantized areas;

means for setting first directed edges from each of first vertices which belong to said first set to second vertices which belong to said second set and to which a terminal corresponding to said first vertex can be assigned, to each of which a cost is added, said cost being at a minimum when said terminal is assigned to said provisional terminal position, said cost increasing in accordance with one or more predetermined conditions;

means for setting second directed edges from a third vertex to each of said first vertices, the flow capacity of said second directed edge being 1;

means for setting third directed edges from each of said second vertices to a fourth vertex, the flow capacity of said third directed edge being the maximal number of terminals which can be assigned to said quantized area;

means for determining a flow from said third vertex to said fourth vertex in which the flow is an integer, the cost is minimized, and the flow is maximized; and

means for obtaining terminal assignment which corresponds to directed edges between said first vertices and said second vertices and having a flow of 1.

2. A system according to claim 1 wherein said system further comprises a terminal fine assign means for determining fine positions of said terminals.

3. A system according to claim 1 wherein said initial terminal assign means comprises:

means for dividing an area for forming said wirings into quantized areas;

means for representing the length of a wiring connecting equipotential terminals by the number of quantized areas through which said wiring passes; and

means for minimizing the length of each wiring.

4. A system according to claim 1 wherein said predetermined conditions include one or more of the followings:

the distance from said provisional terminal position;

whether inside or outside the minimum rectangle which enclose a wiring between a set of equipotential terminals including said terminal;

the number of bends of said wiring;

the distance with respect to previously assigned one or more terminals of adjacent blocks which are connected equipotentially to said terminal; and

whether on one edge of said block or on another edge, said one edge corresponding to said provisional terminal position.

5. A system for assigning positions of block terminals, said terminals being connected through wirings, said blocks being classified into one or more fixed shape blocks in which terminal positions are previously determined and one or more variable shape blocks in which terminal positions are changeable, said system comprising:

initial terminal assign means for provisionally assigning terminal positions relating to said variable shape blocks, for the purpose of minimizing the total length of said wirings; and

terminal distribution and assign means for evaluating said provisionally assigned terminal positions and for distributing said provisionally assigned terminal positions on the basis of said evaluation, said terminal distribution and assign means comprising;

means for dividing an area at the periphery of each of said blocks into quantized areas;

means for setting a first set of vertices which corresponds to a set of terminals of said block;

means for setting a second set of vertices which corresponds to a set of said quantized areas;

means for setting first directed edges from each of first vertices which belong to said first set to said second vertices which belong to said second set and to which a terminal corresponding to said first vertex can be assigned, to each of which a cost is added, said cost being at a minimum when said terminal is assigned to said provisional terminal position, said cost increasing in accordance with one or more predetermined conditions;

means for setting second directed edges from a third vertex to each of said first vertices, the flow capacity of said second directed edge being 1;

means for setting third directed edges from each of said second vertices to a fourth vertex, the flow capacity of said third directed edge being the maximal number of terminals which can be assigned to said quantized area;

means for determining a flow from said third vertex to said fourth vertex in which the flow is an integer, the cost is minimized, and the flow is maximized; and

means for obtaining terminal assignment which corresponds to directed edges between said first vertices and said second vertices and having a flow of 1.

6. A system according to claim 5 wherein said system further comprises a terminal fine assign means for determining fine positions of said terminals.

7. A system according to claim 5 wherein said initial terminal assign means comprises:

means for dividing an area for forming said wirings into quantized areas;

means for representing the length of a wiring connecting equipotential terminals by the number of quantized areas through which said wiring passes; and

means for minimizing the length of each wiring.

8. A system according to claim 5 wherein said predetermined conditions includes one or more of the followings:

the distance from said provisional terminal position;

whether inside or outside the minimum rectangle which enclose a wiring between a set of equipotential terminals including said terminal;

the number of bends of said wiring;

the distance with respect to previously assigned one or more terminals of adjacent blocks which are connected equipotentially to said terminal; and

whether on one edge of said block or on another edge, said one edge corresponding to said provisional terminal position.

9. A system for assigning positions of terminals of blocks, comprising:

means for dividing an area at the periphery of each of said blocks into quantized areas;

means for setting a first set of vertices which corresponds to a set of terminals of said block,

means for setting a second set of vertices which corresponds to a set of said quantized areas;

means for setting first directed edges from each of first vertices which belong to said first set to second vertices which belong to said second set, to each of which a cost is added, said cost representing a usefulness specification for assigning a terminal to a quantized area, the flow capacity of said first directed edge being 1;

means for setting second directed edges from a third vertex to each of said first vertices, the flow capacity of said second directed edge being 1;

means for setting third directed edges from each of said second vertices to a fourth vertex, the flow capacity of said third directed edge being the maximal number of terminals which can be assigned to said quantized area;

means for determining a flow from said third vertex to said fourth vertex in which the flow is an integer, the cost is minimized, and the flow is maximized; and

means for obtaining terminal assignment which corresponds to directed edges between said first vertices and said second vertices and having a flow of 1.

10. A method for automatically designing a layout for a semi-conductor device such as a VLSI, said method comprising the steps of:

(i) positioning a terminal on the periphery of a rectangular block by a relative position of one dimension at a position j, where j is a real number, and the center of said block is represented by a real number a, said step (i) comprising the steps of;

(i)-a selecting one of a first, second, third and fourth edge of said block on which to position said terminal;

(i)-b provisionally positioning said terminal relative to said layout according to the following conditions;

(a) when said first edge of said block is selected in step (i)-a, positioning said terminal such that said terminal is separated from one end of said first edge by (j-a)/b, where a<

j≦

a+b, and b is a real number,

(b) when said second edge of said block is selected in step (i)-a, positioning said terminal such that said terminal is separated from one end of said second edge connected to the other end of said first edge by (j-a-b)/b, where a+b <

j≦

a+2b,

(c) when said third edge of said block is selected in step (i)-a, positioning said terminal such that said terminal is separated from one end of said third edge connected to the other end of said second edge by (j-a-2b)/b, where a+2b<

j≦

a+3b, and

(d) when said fourth edge of said block is selected in step (i)-a, positioning said terminal such that said terminal is separated from one end of said fourth edge connected to the other end of said third edge by (j-a-3b)/b, where a+3b<

j≦

a+4b;

(ii) evaluating said provisional position of said terminal as a function of reducing chip area;

(iii) repositioning said provisionally positioned terminal with respect to said layout relative to said selected one of said first, second, third and fourth edge of said block, based on said evaluating step; and

(iv) placing a block terminal on said semi-conductor device at a position corresponding to said repositioned terminal relative to said layout, and connecting wires thereto.