VLSI Design Partitioning - Very Large Scale Integration - Practical Problems

Practical Problems in VLSI Physical Design

1. Practical Problems in VLSIPhysical Design
FBB Algorithm (1/6)
„
Perform flow-based bipartitioningunder:
ƒ
Area constraint [4,5]
ƒ
Source = a, sink = i
ƒ
Break ties alphabetically
Network Flow-based Bipartitioning

2. Practical Problems in VLSIPhysical Design
FBB Algorithm (2/6)
First Max-Flow and Its Cut

3. Practical Problems in VLSIPhysical Design
FBB Algorithm (3/6)
First Node Merging

4. Practical Problems in VLSIPhysical Design
FBB Algorithm (4/6)
Second Max-Flow and Its Cut

5. Practical Problems in VLSIPhysical Design
FBB Algorithm (5/6)
Second Node Merging

6. Practical Problems in VLSIPhysical Design
FBB Algorithm (6/6)
Third Max-Flow and Its Cut

7. Practical Problems in VLSIPhysical Design
FBB Algorithm (1/6)
„
Perform flow-based bipartitioningunder:
ƒ
Area constraint [4,5]
ƒ
Source = a, sink = i
ƒ
Break ties alphabetically
Network Flow-based Bipartitioning

8. Practical Problems in VLSIPhysical Design
FBB Algorithm (2/6)
First Max-Flow and Its Cut

9. Practical Problems in VLSIPhysical Design
FBB Algorithm (3/6)
First Node Merging

10. Practical Problems in VLSIPhysical Design
FBB Algorithm (4/6)
Second Max-Flow and Its Cut

11. Practical Problems in VLSIPhysical Design
FBB Algorithm (5/6)
Second Node Merging

12. Practical Problems in VLSIPhysical Design
FBB Algorithm (6/6)
Third Max-Flow and Its Cut

13. Practical Problems in VLSIPhysical Design
FM Partitioning (1/12)
„
Perform FM algorithm on the following circuit:
ƒ
Area constraint = [3,5]
ƒ
Break ties in alphabetical order.
Fiduccia-MattheysesAlgorithm

14. Practical Problems in VLSIPhysical Design
FM Partitioning (2/12)
Initial Partitioning „
Random initial partitioning is given.

15. Practical Problems in VLSIPhysical Design
FM Partitioning (3/12)
Gain Computation and Bucket Set Up

16. Practical Problems in VLSIPhysical Design
FM Partitioning (4/12)
First Move

17. Practical Problems in VLSIPhysical Design
FM Partitioning (5/12)
Second Move

18. Practical Problems in VLSIPhysical Design
FM Partitioning (6/12)
Third Move

19. Practical Problems in VLSIPhysical Design
FM Partitioning (7/12)
Forth Move

20. Practical Problems in VLSIPhysical Design
FM Partitioning (8/12)
Fifth Move

21. Practical Problems in VLSIPhysical Design
FM Partitioning (9/12)
Sixth Move

22. Practical Problems in VLSIPhysical Design
FM Partitioning (10/12)
Seventh Move

23. Practical Problems in VLSIPhysical Design
FM Partitioning (11/12)
Last Move

24. Practical Problems in VLSIPhysical Design
FM Partitioning (12/12)
Summary „
Found three best solutions.
ƒ
Cutsizereduced from 6 to 3.
ƒ
Solutions after move 2 and 4 are better balanced.

25. Practical Problems in VLSIPhysical Design
KL Partitioning (1/6)
„
Perform single KL pass on the following circuit:
ƒ
KL needs undirected graph (clique-based weighting)
Kernighan-Lin Algorithm

26. Practical Problems in VLSIPhysical Design
KL Partitioning (2/6)
First Swap

27. Practical Problems in VLSIPhysical Design
KL Partitioning (3/6)
Second Swap

28. Practical Problems in VLSIPhysical Design
KL Partitioning (4/6)
Third Swap

29. Practical Problems in VLSIPhysical Design
KL Partitioning (5/6)
Fourth Swap „
Last swap does not require gain computation

30. Practical Problems in VLSIPhysical Design
KL Partitioning (6/6)
Summary „
Cutsizereduced from 5 to 3
ƒ
Two best solutions found (solu tions are always area-balanced)