METHOD AND SYSTEM FOR FACILITATING FLOORPLANNING FOR 3D IC

• US 20100031217A1
• Filed: 07/30/2008
• Published: 02/04/2010
• Est. Priority Date: 07/30/2008
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Chiang, Charles C., Sinha, Subarnarekha
• Granted Patent: US 8,006,212 B2
• Time in Patent Office: Days
• US Class Current: 716/122
• 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/3323 using formal methods, e.g. equivalence checking or property checking
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

One embodiment of the present invention provides a system for facilitating floorplanning for three-dimensional integrated circuits (3D ICs). During operation, the system receives a number of circuit blocks. The system places the blocks in at least one layer of a multi-layer die structure and sets an initial value of a time-varying parameter. The system then iteratively perturbs the block arrangement until the time-varying parameter reaches a pre-determined value.

Claims

1. A computer-executed method for facilitating floorplanning for three-dimensional integrated circuits (3D ICs), the method comprising:

receiving a number of circuit blocks;

receiving a set of parameters for a 3D structure, wherein the parameters include one or more of;

die area;

maximum total wirelength;

maximum number of through-silicon vias (TSVs) on a respective layer; and

aspect ratio of a respective layer in the 3D structure; and

computing a floorplan for the circuit blocks across the layers in the 3D structure by optimizing a cost function, wherein the cost function is based on the total area, wirelength, and TSVs used by the circuit blocks, the aspect ratio of the area occupied by the circuit blocks in each layer, and the highest temperature produced by the circuit blocks for a given floorplan.

2. A computer-executed method for facilitating floorplanning for three-dimensional integrated circuits (3D ICs), the method comprising:

receiving a number of circuit blocks;

placing the blocks in at least one layer of a multi-layer die structure;

setting an initial value of a time-varying parameter;

iteratively performing the following operations until the time-varying parameter reaches a pre-determined value;

perturbing the current arrangement of the blocks;

computing a value of a cost function based on a total die area, a total wirelength, a total number of through-silicon vias (TSVs), and an aspect ratio of the die required by the blocks in the pre-perturbation arrangement and the perturbed arrangement;

if the computed value of the cost function is less than the cost-function value associated with the pre-perturbation arrangement, accepting the perturbed block arrangement as the current block arrangement;

if the computed value of the cost function is greater than or equal to the cost-function value associated with the pre-perturbation arrangement, accepting the perturbed block arrangement as the current block arrangement with a non-zero probability which decreases with the time-varying parameter; and

decrementing the time-varying parameter; and

subsequent to the iterative operations, producing a result indicating the final block arrangement across different layers.

3. The method of claim 2, wherein perturbing the current arrangement of the blocks comprises performing one or more of the following operations:

moving at least one block;

swapping two blocks;

rotating at least one block; and

flipping at least one block.

4. The method of claim 3, wherein the perturbation is performed with an increased probability of moving blocks from a congested layer to a layer with more unused space.

5. The method of claim 3, wherein the perturbation is performed based on the slack of one or more blocks within the bound of the die area on a respective layer.

6. The method of claim 5, wherein slack-based block moving is favored when the time-varying parameter is above a pre-determined value.

7. The method of claim 5, wherein slack-based block swapping is favored when the time-varying parameter is equal to or below the pre-determined value.

8. The method of claim 2, further comprising decomposing at least one block larger than a pre-determined size to smaller blocks after the time-varying parameter reaches a pre-determined intermediate value.

9. The method of claim 8, further comprising increasing the time-varying parameter after the time-varying parameter reaches the pre-determined intermediate value, thereby allowing the decomposed blocks to experience additional perturbation.

10. The method of claim 2, wherein receiving the circuit blocks comprises receiving the blocks in a pre-existing two-dimensional (2D) or 3D floorplan.

11. A computer-readable storage medium storing code which when executed by a computer causes the computer to perform a method for facilitating floorplanning for three-dimensional integrated circuits (3D ICs), the method comprising:

receiving a number of circuit blocks;

receiving a set of parameters for a 3D structure, wherein the parameters include one or more of;

die area;

maximum total wirelength;

maximum number of through-silicon vias (TSVs) on a respective layer; and

aspect ratio of a respective layer in the 3D structure; and

computing a floorplan for the circuit blocks across the layers in the 3D structure by optimizing a cost function, wherein the cost function is based on the total area, wirelength, and TSVs used by the circuit blocks, the aspect ratio of the area occupied by the circuit blocks in each layer, and the highest temperature produced by the circuit blocks for a given floorplan.

12. A computer-readable storage medium storing code which when executed by a computer causes the computer to perform a method for facilitating floorplanning for three-dimensional integrated circuits (3D ICs), the method comprising:

receiving a number of circuit blocks;

placing the blocks in at least one layer of a multi-layer die structure;

setting an initial value of a time-varying parameter;

iteratively performing the following operations until the time-varying parameter reaches a pre-determined value;

perturbing the current arrangement of the blocks;

computing a value of a cost function based on a total die area, a total wirelength, a total number of through-silicon vias (TSVs), and an aspect ratio of the die required by the blocks in the pre-perturbation arrangement and the perturbed arrangement;

if the computed value of the cost function is less than the cost-function value associated with the pre-perturbation arrangement, accepting the perturbed block arrangement as the current block arrangement;

if the computed value of the cost function is greater than or equal to the cost-function value associated with the pre-perturbation arrangement, accepting the perturbed block arrangement as the current block arrangement with a non-zero probability which decreases with the time-varying parameter; and

decrementing the time-varying parameter; and

subsequent to the iterative operations, producing a result indicating the final block arrangement across different layers.

13. The computer-readable storage medium of claim 12, wherein perturbing the current arrangement of the blocks comprises performing one or more of the following operations:

moving at least one block;

swapping two blocks;

rotating at least one block; and

flipping at least one block.

14. The computer-readable storage medium of claim 13, wherein the perturbation is performed with an increased probability of moving blocks from a congested layer to a layer with more unused space.

15. The computer-readable storage medium of claim 13, wherein the perturbation is performed based on the slack of one or more blocks within the bound of the die area on a respective layer.

16. The computer-readable storage medium of claim 15, wherein slack-based block moving is favored when the time-varying parameter is above a pre-determined value.

17. The computer-readable storage medium of claim 15, wherein slack-based block swapping is favored when the time-varying parameter is equal to or below the pre-determined value.

18. The computer-readable storage medium of claim 12, wherein the method further comprises decomposing at least one block larger than a pre-determined size to smaller blocks after the time-varying parameter reaches a pre-determined intermediate value.

19. The computer-readable storage medium of claim 18, wherein the method further comprises increasing the time-varying parameter after the time-varying parameter reaches the pre-determined intermediate value, thereby allowing the decomposed blocks to experience additional perturbation.

20. The computer-readable storage medium of claim 12, wherein receiving the circuit blocks comprises receiving the blocks in a pre-existing two-dimensional (2D) or 3D floorplan.

21. A computer system for facilitating floorplanning for three-dimensional integrated circuits (3D ICs), the computer system comprising:

a processor;

a memory;

a receiving mechanism configured to receive a number of circuit blocks and a set of parameters for a 3D structure, wherein the parameters include one or more of;

die area;

maximum total wirelength;

maximum number of through-silicon vias (TSVs) on a respective layer; and

aspect ratio of a respective layer in the 3D structure; and

a computing mechanism configured to compute a floorplan for the circuit blocks across the layers in the 3D structure by optimizing a cost function, wherein the cost function is based on the total area, wirelength, and TSVs used by the circuit blocks, the aspect ratio of the area occupied by the circuit blocks in each layer, and the highest temperature produced by the circuit blocks for a given floorplan.

22. A computer system for facilitating floorplanning for three-dimensional integrated circuits (3D ICs), the computer system comprising:

a processor;

a memory;

a receiving mechanism configured to receive a number of circuit blocks;

an initial placement mechanism configured to place the blocks in at least one layer of a multi-layer die structure;

a time-varying parameter setting mechanism configured to set an initial value of a time-varying parameter;

an iteration mechanism configured to iteratively perform the following operations until the time-varying parameter reaches a pre-determined value;

perturbing the current arrangement of the blocks;

computing a value of a cost function based on a total die area, a total wirelength, a total number of through-silicon vias (TSVs), and an aspect ratio of the die required by the blocks in the pre-perturbation arrangement and the perturbed arrangement;

if the computed value of the cost function is less than the cost-function value associated with the pre-perturbation arrangement, accepting the perturbed block arrangement as the current block arrangement;

if the computed value of the cost function is greater than or equal to the cost-function value associated with the pre-perturbation arrangement, accepting the perturbed block arrangement as the current block arrangement with a non-zero probability which decreases with the time-varying parameter; and

decrementing the time-varying parameter; and

a result producing mechanism configured to produce, subsequent to the iterative operations, a result indicating the final block arrangement across different layers.

23. The computer system of claim 22, wherein while perturbing the current arrangement of the blocks, the iteration mechanism is further configured to perform one or more of the following operations:

moving at least one block;

swapping two blocks;

rotating at least one block; and

flipping at least one block.

24. The computer system of claim 23, wherein the perturbation is performed with an increased probability of moving blocks from a congested layer to a layer with more unused space.

25. The computer system of claim 23, wherein the perturbation is performed based on the slack of one or more blocks within the bound of the die area on a respective layer.

26. The computer system of claim 25, wherein slack-based block moving is favored when the time-varying parameter is above a pre-determined value.

27. The computer system of claim 25, wherein slack-based block swapping is favored when the time-varying parameter is equal to or below the pre-determined value.

28. The computer system of claim 22, further comprising a block-decomposition mechanism configured to decompose at least one block larger than a pre-determined size to smaller blocks after the time-varying parameter reaches a pre-determined intermediate value.

29. The computer system of claim 28, wherein the time-varying parameter setting mechanism is further configured to increase the time-varying parameter after the time-varying parameter reaches the pre-determined intermediate value, thereby allowing the decomposed blocks to experience additional perturbation.

30. The computer system of claim 22, wherein while receiving the circuit blocks, the receiving mechanism is configured to receive the blocks in a pre-existing two-dimensional (2D) or 3D floorplan.