System for assigning positions of block terminals in a VLSI

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

Claim 2

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.

Claim 6

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.

Claim 7

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.