Sequence-pair creating apparatus and sequence-pair creating method

• US 20080244490A1
• Filed: 03/29/2007
• Published: 10/02/2008
• Est. Priority Date: 03/29/2007
• Status: Active Grant

• Current Assignee: Shigetoshi Nakatake, Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Shigetoshi Nakatake, Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Nakatake, Shigetoshi, Ito, Takao, Kawakita, Masahiro
• Granted Patent: US 7,584,445 B2
• Time in Patent Office: Days
• US Class Current: 716/9
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A sequence-pair creating apparatus includes a block placement storing unit that stores information of size of a block b_i in a block set B and information of block placement, creates a sequence-pair (P, M), serving as a pair of a sequence P and a sequence M of the block b_i, and further includes a binary relation setting unit that sets, in accordance with the information of block placement and information of size, a binary relation serving as an order relation that indicates a relative configuration between the blocks of a block pair of two blocks and that is derived from a configuration constraint between the blocks extracted from the information of block placement and information of size or designated by an external input, and a total order relation setting unit that sets a series of ranks of the sequences P and M for all the blocks on the basis of the information of block placement and information of size so as to satisfy all binary relations set by the binary relation setting unit.

Claims

1. A sequence-pair creating apparatus comprising block placement storing means that stores information of size serving as information of a weight w(b_i) and a height h(b_i) of a block b_i (b_i∈

B) in a set B of N (≧

2) rectangle blocks (hereinafter, referred to as a “

block set”

) having a width and a height, and information of block placement having positional coordinates (x(b_i), y(b_i)) of the block b_i (b_i∈

B) upon configuring all blocks in the block set B on a chip, the sequence-pair creating apparatus creating a sequence-pair (P, M), serving as a pair of a sequence P of the N blocks b_i (b_i∈

B) and a sequence M of the N blocks b. (b_i∈

B) different from the sequence P, for uniquely specifying a positional relation between the blocks in the case of configuring all the blocks in the block set B on the chip without an overlap of the block, the sequence-pair creating apparatus comprising;

binary relation setting means that sets, in accordance with the information of block placement and information of size, a binary relation serving as an order relation that indicates a relative configuration between the blocks of a block pair (b_i, b_j) of two blocks b_i and b_j (∈

BB) and that is derived from a configuration constraint between the blocks extracted from the information of block placement and information of size or designated by an external input; and

total order relation setting means that sets a series of ranks of the sequences P and M for all the blocks on the basis of the information of block placement and information of size so as to satisfy all binary relations set by the binary relation setting means.

2. The sequence-pair creating apparatus according to claim 1, wherein the binary relation setting means comprises separation constraint extracting means that,

by referring to positional coordinates (x(b_i), y(b_i)) and (x(b_j), y(b_j)), widths w(b_i) and w(b_j), and heights h(b_i) and h(b_j) of the two blocks b_i and b_j (∈

B) stored in the block placement storing means,

sets the binary relation between the block b_i and block b_j in accordance with a left-and-right relation of the positional coordinates of the block b_i and b_j when the y coordinates of sides in the vertical direction (hereinafter, this is referred to as the y direction) do not have a clearance with a predetermined width not less than 0 and those in the horizontal direction (hereinafter, this is referred to as the x direction) of the block b_i and block b_j have a clearance with a predetermined width not less than 0, and

further sets the binary relation between the block b_i and block b_j in accordance with an above-and-below relation between the positional coordinates of the blocks b_i and b_j when the x coordinates of sides in the x direction of the block b_i and block b_j do not have a clearance with a predetermined width not less than 0 and those in the y direction of the block b_i and block b_j have a clearance with a predetermined width not less than 0.

3. The sequence-pair creating apparatus according to claim 1, wherein the binary relation setting means comprises:

vertical collinear constraint extracting means that sets the binary relation between the two blocks b_i and b_j in a partial set B_k (⊂

B) of the block set B stored in the block placement storing means in accordance with an above-and-below relation between the positional coordinates of the block b_i (∈

B_k) upon imposing a configuration constraint (hereinafter, referred to as a “

vertical collinear constraint”

) for aligning a left side or right side or representative points of the block b_i (∈

B_k) on a vertical line to the blocks in the partial set B_k.

4. The sequence-pair creating apparatus according to claim 1, wherein the binary relation setting means comprises:

horizontal collinear constraint extracting means that sets the binary relation between two blocks b_i and b_j in a partial set B_k of the block set B stored in the block placement storing means in accordance with a left-and-right relation between positional coordinates the block b_i (∈

B_k) in the partial set B_k when imposing a configuration constraint (hereinafter, referred to as a “

horizontal collinear constraint”

) for aligning top sides or bottom sides or representative points of the blocks in the partial set B_k on a horizontal line to the blocks in the partial set B_k.

5. The sequence-pair creating apparatus according to claim 1, wherein the binary relation setting means comprises:

horizontal symmetrical constraint extracting means that sets the binary relation in accordance with a left-and-right relation of the positional coordinates of both blocks b_i and b_k of three blocks b_i, b_j, and b_k in the block set B stored in the block placement storing means upon configuration constraint (hereinafter, referred to as a “

horizontal symmetrical constraint”

) for configuring the block b_i and block b_k at positions symmetrical to the block b_j in the horizontal direction.

6. The sequence-pair creating apparatus according to claim 1, wherein the binary relation setting means comprises:

vertical symmetrical constraint extracting means that sets the binary relation in accordance with an above-and-below relation of the positional coordinates of both blocks b_i and b_k of three blocks b_i, b_j, and b_k in the block set B stored in the block placement storing means when a configuration constraint (hereinafter, referred to as “

vertical symmetrical constraint”

) for configuring the block b_i and block b_k at positions symmetrical to the block b_j in the vertical direction.

7. The sequence-pair creating apparatus according to claim 1, wherein the binary relation setting means comprises:

binary relation transition setting means that transitively sets the binary relation between blocks b_i and b_k of three blocks b_i, b_j, and b_k in the block set B from the binary relation between the blocks b_i and b_j and the binary relation between the blocks b_j and b_k when the binary relation between the blocks b_i and b_j and the binary relation between the blocks b_j and b_k are set and the binary relation between the blocks b_i and b_k is not set.

8. The sequence-pair creating apparatus according to claim 1, wherein the binary relation setting means sets, with respect to two blocks b_i and b_j in the block set B, a binary relation between the sequences P and M to p_ord(b_i, b_j)=1 and m_ord(b_i, b_j)=1 when the block b_i is on the left of the block b_j and further sets a binary relation between the sequences P and M to p_ord(b_i, b_j)=0 and m_ord(b_i, b_j)=1 when the block b_i is below the block b_j, and

the total order relation setting means comprises:

P-order setting means that sequentially sets ranks of the blocks at the sequence P from the left by repeating

operation for extracting a block b_i (∈

B_n) in a set B_n (⊂

B) of blocks to which the rank is not set at the sequence P, having a binary order relation p_ord(b_i, b_j) between the block b_i (∈

B_n) and all blocks b_j (∈

B_n) other than the block b_i in the set B_n, which is not 1, and for setting the set of the extracted blocks as a set B_s (⊂

B_n) and

operation for selecting the block b_i in the set B_n having the right side thereof that is on the left or at the collinear position of the left side of all blocks b_j (∈

B_s) other than the block b_i in the set B_s or having the bottom side thereof that is upper than the top side of the block b_j, and for aligning the selected block b_i at the sequence P packing from the left; and

M-order setting means that sequentially sets ranks of the blocks at the sequence M from the left by repeating

operation for extracting a block b_i (∈

B_m) in a set B_m (⊂

B) of blocks to which the rank is not set at the sequence M, having a binary order relation m_ord(b_i, b_j) between the block b_i (∈

B_m) and all blocks b_j (∈

B_m) other than the block b_i in the set B_m, which is not 1, and for setting the set of the extracted blocks as a set B_t (⊂

B_m) and

operation for selecting the block b_i in the set B_t having the right side of the block b_i is on the left or at the collinear position of the left side of all the blocks b_j (∈

B_t) in the set B_t other than the block b_i or the bottom side of the block b_i is upper than the top side of the block b_j, and for aligning the selected block b_i at the sequence M packing from the left.

9. The sequence-pair creating apparatus according to claim 1, further comprising:

overlap removing means that creates the information of block placement and information of size without an overlap of the blocks, upon overlapping the blocks in the block set B stored in the block placement storing means, by reducing the width or height of one or both of the two overlapped blocks,

wherein the total order relation setting means sets a total order relation of the blocks at the sequences P and M in accordance with the information of block placement and information of size without the overlap of blocks created by the overlap removing means so as to satisfy the binary relation set by the binary relation setting means.

10. The sequence-pair creating apparatus according to claim 1, wherein the binary relation setting means sets a left-and-right relation serving as the binary relation for the horizontal direction and an above-and-below relation serving as the binary relation for the vertical direction from one of all block pairs of the blocks in the block set B, which is extracted from the block placement information and information of size or to which the configuration constraint between the blocks designated by the external input is imposed, on the basis of the configuration constraint, and further sets a left-and-right relation and an above-and-below relation which are transitively determined from the set left-and-right relation and above-and-below relation,

the total order relation setting means comprises:

temporary binary relation setting means that sets a temporary binary relation serving as a temporary left-and-right relation or above-and-below relation of a block pair (b_k, b_l) (b_k, b_l∈

B) other than one of all the block pairs of the blocks in the block set B, which is related by the left-and-right relation or above-and-below relation (hereinafter, “

fundamental binary relation”

) set by the binary relation setting means;

initial layout area size calculating means that calculates a width W and a height H of a layout area of an initial block placement (hereinafter, referred to as an “

initial block placement”

);

constraint graph creating means that creates a horizontal constraint graph and a vertical constraint graph on the basis of the fundamental binary relation and the temporary binary relation;

compaction executing means that executes upper-right-compaction or upper-left-compaction on the basis of both the horizontal constraint graph and vertical constraint graph created by the constraint graph creating means after the creation thereof and further executes lower-left-compaction or lower-right-compaction on the basis of both the horizontal constraint graph and vertical constraint graph;

current layout area size calculating means that calculates a width W′ and

a height H′

of a layout area of a minimum block placement (hereinafter, referred to as “

current block placement”

) obtained as results of the compaction executed by the compaction executing means;

convergence determining means that determines whether or not the width W′

of the layout area is not more than the width W of the layout area of the initial block placement and whether or not the height H′

of the layout area is not more than the height H of the layout area of the initial block placement;

temporary binary relation changing means that changes one or a plurality of temporary binary relations for the horizontal direction into a temporary binary relation for the vertical direction and further changes one or a plurality of the temporary binary relations for the vertical direction into the temporary binary relation for the horizontal direction when the convergence determining means does not determine that the width W′ and

height H′

of the layout area are not more than the width W and height H of the layout area of the initial block placement; and

total order relation calculating means that sets a series of ranks of all the blocks at the sequences P and M on the basis of the current block placement when the convergence determining means determines that the width W′ and

height H′

of the layout area are not more than the width W and height H of the layout area of the initial block placement, and

the constraint graph creating means creates again a horizontal constraint graph and a vertical constraint graph, when the temporary binary relation changing means changes the temporary binary relation, on the basis of the changed temporary binary relation and fundamental binary relation.

11. The sequence-pair creating apparatus according to claim 10, wherein the total order relation setting means comprises:

movement slack calculating means that calculates the difference |x_t(b_i)−

x_b(b_i)| (hereinafter, referred to as a “

horizontal movement slack”

) between distances x_t(b_i) and x_b(b_i) of movement of the blocks b_i (b_i∈

B) as results of the compaction executed by the compaction executing means and the difference |y_t(b_i)−

y_b(b_i)| (hereinafter, referred to as a “

vertical movement slack”

) between distances y_t(b_i) and y_b(b_i) of movement thereof, and

the temporary binary relation changing means changes, when the convergence determining means does not determine that an area of the layout area is minimum, the temporary binary relation having the minimum sum of the horizontal movement slacks of both the blocks from among the temporary binary relations for the horizontal direction into the temporary binary relation for the vertical direction and further changes the temporary binary relation having the minimum sum of the vertical movement slacks of both the blocks from among the temporary binary relations for the vertical direction into the temporary binary relation for the horizontal direction.

12. The sequence-pair creating apparatus according to claim 10, wherein the total order relation setting means comprises:

overlap length calculating means that calculates an overlap length d_x(b_i, b_j) for the horizontal direction and an overlap length d_y(b_i, b_j) for the vertical direction for a block pair (b_i, b_j) (b_i, b_j∈

B) having overlapped blocks from among all the block pairs in a set B×

B of the block pairs, and

the temporary binary relation setting means comprises;

temporary left-and-right relation setting means that sets the temporary binary relation for the horizontal direction between the block b_k and the block b_l in accordance with the left-and-right relation between horizontal positional coordinates x(b_k) and x(b_i) of the blocks b_k and b_l for the block pair with an overlap in the vertical direction and without an overlap in the horizontal direction of the block pairs (b_k, b_l) to which the fundamental binary relation is not set;

temporary above-and-below relation setting means that sets the temporary binary relation for the vertical direction between the block b_k and the block b_l in accordance with an above-and-below relation between vertical positional coordinates y(b_k) and y(b_l) of the blocks b_k and b_l for the block pair with the overlap in the horizontal direction and without the overlap in the vertical direction of the block pairs (b_k, b_l) to which the fundamental binary relation is not set;

temporary binary relation transition setting means that sets a temporary binary relation transitively determined from the temporary binary relations set by the temporary left-and-right relation setting means and the temporary above-and-below relation setting means and the fundamental binary relations; and

temporary binary relation complementing means that sets, with respect to the block pair (b_i, b_j) to which neither the fundamental binary relation nor the temporary binary relation is set, the temporary binary relation for the horizontal direction between the block b_i and the block b_j in accordance with the left-and-right relation between the horizontal positional coordinates x(b_i) and x(b_j) of the blocks b_i and b_j when the overlap length d_x(b_i, b_j) for the vertical direction is shorter than the overlap length d_y(b_i, b_j) for the vertical direction and, in the case except for the time, further sets the temporary binary relation for the vertical direction between the block b_i and the block b_j in accordance with an above-and-below relation between the vertical positional coordinates y(b_i) and y(b_j) of the blocks b_i and b_j.

13. A sequence-pair creating method for, on the basis of information of size serving as information of a weight w(b_i) and a height h(b_i) of a block b_i (b_i∈

B) in a set B of N (≧

2) rectangle blocks (hereinafter, referred to as a “

block set”

) having a shape, and information of block placement having positional coordinates (x(b_i), y(b_i)) of the block b_i (b_i∈

B) upon configuring all blocks in the block set B on a chip, creating a sequence-pair (P, M), serving as a pair of a sequence P of the N blocks b_i (b_i(B) and a sequence M of the N blocks b_i (b_i∈

B) different from the sequence P, for uniquely specifying a positional relation between the blocks in the case of configuring all the blocks in the block set B on the chip without an overlap of the blocks, the sequence-pair creating method comprising;

a binary relation setting step of setting, in accordance with the information of block placement and information of size, a binary relation serving as an order relation that indicates a relative configuration between the blocks of a block pair (b_i, b_j) of two blocks b_i and b_j (∈

B) and that is derived from a configuration constraint between the blocks extracted from the information of block placement and information of size or designated by an external input; and

a total order relation setting step of setting a series of ranks of the sequences P and M for all the blocks on the basis of the information of block placement and information of size so as to satisfy all binary relations set by the binary relation setting step.

14. The sequence-pair creating method according to claim 13, wherein the binary relation setting step comprises an separation constraint extracting step of,

by referring to positional coordinates (x(b_i), y(b_i)) and (x(b_j), y(b_j)), widths w(b_i) and w(b_j), and heights h(b_i) and h(b_j) of the two blocks b_i and b_j (∈

B) in the block set B.

setting the binary relation between the block b_i and block b_j in accordance with a left-and-right relation of the positional coordinates of the block b_i and b_j when the y coordinates of sides in the vertical direction (hereinafter, this is referred to as the y direction) do not have a clearance with a predetermined width not less than 0 and those in the horizontal direction (hereinafter, this is referred to as the x direction) of the block b_i and block b_j have a clearance with a predetermined width not less than 0, and

further setting the binary relation between the block b_i and block b_j in accordance with an above-and-below relation between the positional coordinates of the blocks b_i and b_j when the x coordinates of sides in the x direction of the block b_i and block b_j do not have a clearance with a predetermined width not less than 0 and those in the y direction of the block b_i and block b_j have a clearance with a predetermined width not less than 0.

15. The sequence-pair creating method according to claim 13, wherein the binary relation setting step comprises:

a vertical collinear constraint extracting step of setting the binary relation between the two blocks b_i and b_j in a partial set B_k (⊂

B) of the block set B in accordance with an above-and-below relation between the positional coordinates of the block b_i (∈

B_k) upon imposing a configuration constraint (hereinafter, referred to as a “

vertical collinear constraint”

) for aligning a left side or right side or representative points of the block b_i (∈

B_k) on a vertical line to the blocks in the partial set B_k.

16. The sequence-pair creating method according to claim 13, wherein the binary relation setting step comprises:

a horizontal collinear constraint extracting step of setting the binary relation between two blocks b_i and b_j in a partial set B_k of the block set B in accordance with a left-and-right relation between positional coordinates the block b_i (∈

B_k) in the partial set B_k when imposing a configuration constraint (hereinafter, referred to as a “

horizontal collinear constraint”

) for aligning top sides or bottom sides or representative points of the blocks in the partial set B_k on a horizontal line to the blocks in the partial set B_k.

17. The sequence-pair creating method according to claim 13, wherein the binary relation setting step comprises:

a horizontal symmetrical constraint extracting step of setting the binary relation in accordance with a left-and-right relation of the positional coordinates of both blocks b_i and b_k of three blocks b_i, b_j, and b_k in the block set B upon configuration constraint (hereinafter, referred to as a “

horizontal symmetrical constraint”

) for configuring the block b_i and block b_k at positions symmetrical to the block b_j in the horizontal direction.

18. The sequence-pair creating method according to claim 13, wherein the binary relation setting step comprises:

a vertical symmetrical constraint extracting step of setting the binary relation in accordance with an above-and-below relation of the positional coordinates of both blocks b_i and b_k of three blocks b_i, b_j, and b_k in the block set B when a configuration constraint (hereinafter, referred to as “

vertical symmetrical constraint”

) for configuring the block b_i and block b_k at positions symmetrical to the block b_j in the vertical direction.

19. The sequence-pair creating method according to claim 13, wherein the binary relation setting step comprises:

a binary relation transition setting step of transitively setting the binary relation between blocks b_i and b_k of three blocks b_i, b_j, and b_k in the block set B from the binary relation between the blocks b_i and b_j and the binary relation between the blocks b_j and b_k when the binary relation between the blocks b_i and b_j and the binary relation between the blocks b_j and b_k are set and the binary relation between the blocks b_i and b_k is not set.

20. The sequence-pair creating method according to claim 13, wherein the binary relation setting step sets, with respect to two blocks b_i and b_j in the block set B, a binary relation between the sequences P and M to p_ord(b_i, b_j)=1 and m_ord(b_i, b_j)=1 when the block b_i is on the left of the block b_j and further sets a binary relation between the sequences P and M to p_ord(b_i, b_j)=0 and m_ord(b_i, b_j)=1 when the block b_i is below the block b_j, and

the total order relation setting step comprises:

a P-order setting step of sequentially setting ranks of the blocks at the sequence P from the left by repeating operation for extracting a block b_i (∈

B_n) in a set B_n (⊂

B) of blocks to which the rank is not set at the sequence P, having a binary order relation p_ord(b_i, b_j) between the block b_i (∈

B_n) and all blocks b_j (∈

B_n) other than the block b_i in the set B_n, which is not 1, and for setting the set of the extracted blocks as a set B_s (⊂

B_n) and operation for selecting the block b_i in the set B_s having the right side thereof that is on the left or at the collinear position of the left side of all blocks b_j (∈

B_s) other than the block b_i in the set B_s or having the bottom side thereof that is upper than the top side of the block b_j, and for aligning the selected block b_i at the sequence P packing from the left; and

an M-order setting step of sequentially setting ranks of the blocks at the sequence M from the left by repeating

operation for extracting a block b_i (∈

B_m) in a set B_m (⊂

B) of blocks to which the rank is not set at the sequence M, having a binary order relation m_ord(b_i, b_j) between the block b_i (∈

B_m) and all blocks b_j (∈

B_m) other than the block b_i in the set B_m, which is not 1, and for setting the set of the extracted blocks as a set B_t (⊂

B_m) and

operation for selecting the block b_i in the set B_t having the right side of the block b_i is on the left or at the collinear position of the left side of all the blocks b_j (∈

B_t) in the set B_t other than the block b_i or the bottom side of the block b_i is upper than the top side of the block b_j, and for aligning the selected block b_i at the sequence M packing from the left.

21. The sequence-pair creating method according to claim 13, further comprising:

an overlap removing step of creating the information of block placement and information of size without the overlap of the blocks, upon overlapping the blocks in the block set B, by reducing the width or height of one or both of the two overlapped blocks,

wherein the total order relation setting step sets a total order relation of the blocks at the sequences P and M in accordance with the information of block placement and information of size without the overlap of the blocks created by the overlap removing step so as to satisfy the binary relation set by the binary relation setting step.

22. The sequence-pair creating method according to claim 13, wherein the binary relation setting step sets a left-and-right relation serving as the binary relation for the horizontal direction and an above-and-below relation serving as the binary relation for the vertical direction from one of all block pairs of the blocks in the block set B, which is extracted from the block placement information and information of size or to which the configuration constraint between the blocks designated by the external input is imposed, on the basis of the configuration constraint, and further sets a left-and-right relation and an above-and-below relation which are transitively determined from the set left-and-right relation and above-and-below relation,

the total order relation setting step comprises:

a temporary binary relation setting step of setting a temporary binary relation serving as a temporary left-and-right relation or above-and-below relation of a block pair (b_k, b_l) (b_k, b_l∈

B) other than one of all the block pairs of the blocks in the block set B, which is related by the left-and-right relation or above-and-below relation (hereinafter, “

fundamental binary relation”

) set by the binary relation setting step;

an initial layout area size calculating step of calculating a width W and a height H of a layout area of an initial block placement (hereinafter, referred to as an “

initial block placement”

);

a constraint graph creating step of creating a horizontal constraint graph and a vertical constraint graph on the basis of the fundamental binary relation and the temporary binary relation;

a compaction executing step of executing upper-right-compaction or upper-left-compaction on the basis of both the horizontal constraint graph and vertical constraint graph created by the constraint graph creating step after the creation thereof and further executing lower-left-compaction or lower-right-compaction on the basis of both the horizontal constraint graph and vertical constraint graph;

a current layout area size calculating step of calculating a width W′ and

a height H′

of a layout area of a minimum block placement (hereinafter, referred to as “

current block placement”

) obtained as results of the compaction executed by the compaction executing step;

a convergence determining step of determining whether or not the width W′

of the layout area is not more than the width W of the layout area of the initial block placement and whether or not the height H′

of the layout area is not more than the height H of the layout area of the initial block placement;

a temporary binary relation changing step of changing one or a plurality of temporary binary relations for the horizontal direction into a temporary binary relation for the vertical direction and further changing one or a plurality of the temporary binary relations for the vertical direction into the temporary binary relation for the horizontal direction when the convergence determining step does not determine that the width W′ and

height H′

of the layout area are not more than the width W and height H of the layout area of the initial block placement; and

a total order relation calculating step of setting a series of ranks of all the blocks at the sequences P and M on the basis of the current block placement when the convergence determining step determines that the width W′ and

height H′

of the layout area are not more than the width W and height H of the layout area of the initial block placement, and

the constraint graph creating step creates again a horizontal constraint graph and a vertical constraint graph, when the temporary binary relation changing step changes the temporary binary relation, on the basis of the changed temporary binary relation and fundamental binary relation.

23. The sequence-pair creating method according to claim 22, wherein the total order relation setting step comprises:

a movement slack calculating step of calculating the difference |x_t(b_i)−

x_b(b_i) (hereinafter, referred to as a “

horizontal movement slack”

) between distances x_t(b_i) and x_b(b_i) of movement of the blocks b_i (b_i∈

B) as results of the compaction executed by the compaction executing step and the difference |y_t(b_i)−

y_b(b_i)| (hereinafter, referred to as a “

vertical movement slack”

) between distances y_t(b_i) and y_b(b_i) of movement thereof, and

the temporary binary relation changing step changes, when the convergence determining step does not determine that an area of the layout area is minimum, the temporary binary relation having the minimum sum of the horizontal movement slacks of both the blocks from among the temporary binary relations for the horizontal direction into the temporary binary relation for the vertical direction and further changes the temporary binary relation having the minimum sum of the vertical movement slacks of both the blocks from among the temporary binary relations for the vertical direction into the temporary binary relation for the horizontal direction.

24. The sequence-pair creating method according to claim 22, wherein the total order relation setting step comprises:

an overlap length calculating step of calculating an overlap length d_x(b_i, b_j) for the horizontal direction and an overlap length d_y(b_i, b_j) for the vertical direction for a block pair (b_i, b_j) (b_i, b_j∈

B) having overlapped blocks from among all the block pairs in a set B×

B of the block pairs, and

the temporary binary relation setting step comprises;

a temporary left-and-right relation setting step of setting the temporary binary relation for the horizontal direction between the block b_k and the block b_l in accordance with the left-and-right relation between horizontal positional coordinates x(b_k) and x(b_l) of the blocks b_k and b_l for the block pair with an overlap in the vertical direction and without an overlap in the horizontal direction of the block pairs (b_k, b_l) to which the fundamental binary relation is not set;

a temporary above-and-below relation setting step of setting the temporary binary relation for the vertical direction between the block b_k and the block b_l in accordance with an above-and-below relation between vertical positional coordinates y(b_k) and y(b_l) of the blocks b_k and b_l for the block pair with the overlap in the horizontal direction and without the overlap in the vertical direction of the block pairs (b_k, b_l) to which the fundamental binary relation is not set;

a temporary binary relation transition setting step of setting a temporary binary relation transitively determined from the temporary binary relations set by the temporary left-and-right relation setting step and the temporary above-and-below relation setting step and the fundamental binary relations; and

a temporary binary relation complementing step of setting, with respect to the block pair (b_i, b_j) to which neither the fundamental binary relation nor the temporary binary relation is set, the temporary binary relation for the horizontal direction between the block b_i and the block b_j in accordance with the left-and-right relation between the horizontal positional coordinates x(b_i) and x(b_j) of the blocks b_i and b_j when the overlap length d_x(b_i, b_j) for the vertical direction is shorter than the overlap length d_y(b_i, b_j) for the vertical direction and, in the case except for the time, further setting the temporary binary relation for the vertical direction between the block b_i and the block b_j in accordance with an above-and-below relation between the vertical positional coordinates y(b_i) and y(b_j) of the blocks b_i and b_j.

25. A program for enabling a computer to execute the sequence-pair creating method according to claim 13.