Goal

Implement and experiment a partitioning algorithm for gate-level designs. Goal of partitioning is to minimize the cutset size while meeting the area constraints
fixed for partitions. Additionally, each group will address specific requirements/constraints as defined bellow:
 
 

Task	Kernighan-Lin	Fiduccia-Mattheyses	Simulated annealing	Tabu search
Implement algo & experiment	Group 1, Group 5, Group 9	Group 2, Group 6, Group 10	Group 3, Group 7, Group 11	Group 4, Group 8, Group 12
k-way partitioning	Group 1	Group 2	Group 3	Group 4
Each gate is characterized by a set of at least 4 different shapes and areas. This will change the way the area of a partition is calculated.	Group 5	Group 6	Group 7	Group 8
Each partition is described by a set of different areas. This areas correspond to different packaging options. Bi-partitioning has to find what partition areas will offer the minimal cutset size.	Group 9	Group 10	Group 11	Group 12

 
 

Benchmark Examples

To experiment with the developed algorithms, you will use a set of benchmark examples that can be downloaded
from http://vlsicad.cs.ucla.edu/~cheese/ispd98.html.
 
 

What to hand in?

A technical report must be handed in. The report will contain following sections:

• Introduction and Problem Statement.
• Related Work.
• Propsoed solution to the problem and relevant implementation issues.
• Experimental results.
• Conclusion.
• Bibliography.

Deadline

    Wednesday, October 3, 2001.