-
This is a minor project related to the course work - VLSI Design and Automation
-
This is a C++ implementation of Fiduccia Mattheyses Algorithm Implemntation.
-
Here is the abstract: In all of the motivating applications for hypergraph partitioning, the size of input is grow- ing and the demand for performance is high. The physical design methodology we apply to these designs must scale to tens of millions of components today and hundreds of millions in the foreseeable future. Because of these large inputs, any partitioning technique used must have near-linear complexity in the worst case in order to be ective. State-of-the-art partitioning tools use local search heuristics to re ne a given partitioning solution. The basic technique common to all VLSI partitioning applications is the Fiduccia Mattheyses (FM) algorithm [1], which applies linear-time passes to iteratively improve a given parti- tioning solution by moving every node exactly once. In our project, we have implemented the at FM algorithm on C++.
More details are in the pdf attached - fm_vlda.pdf
- Compile and run main.cpp on a Windows System to see the results.