ESE 556 Project 1
- Partitioning -
 
 

Goal

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

Task	Kernighan-Lin	Fiduccia-Mattheyses	Simulated annealing
Implement algo & experiment	Group 1, Group 5, Group 9	Group 2, Group 6, Group 4	Group 3, Group 7, Group 8
k-way partitioning	Group 1	Group 2	Group 3
Each gate is characterized by a set of (at least) 4 different rectangular shapes and areas. The shapes differ by their aspect ratio. This will affect the way the area of a partition is calculated.	Group 5	Group 6	Group 7
Each partition is described by a set of different areas. This areas correspond to different packaging options. Bi-partitioning has to find which partition areas offer the minimal cutset size.	Group 9	Group 4	Group 8

Groups:

Group 1: Lili Zhou, Shanshan Xu.
Group 2: Aashish Shah, Prakash Shekar, Balasubramanian Natarajan.
Group 3: Baskar Mukherjee, Kartik Rao, Puloma Mukherjee.
Group 4: Prashant Kher, Mandeep Singh Sawhney, Samir Raut.
Group 5: Pallavi Gokhale, Gopa Dutta, Saujanya Gosangari.
Group 6: -
Group 7: Krishna Kumar Nair, Praveen Ranachandran, Sheela Rangarajan.
Group 8: Prakshep Padia, Prachi Ughade, Vaishali Wani.
Group 9: Nima Shah, Tejas Brahmbhatt, Venkat.

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.
• Presentation of the proposed solution and relevant implementation issues.
• Experimental results.
• Conclusion.
• Bibliography.

Deadline

February 24 2003 - midnight.