Multi-Branched Recursive Partitioning using an Area-Constrained FM Algorithm

Research Project & Tool Implementation
Authors: Subham Prasad Gupta, Sanjay A., Vinayak S. Salunke
Affiliation: B.Tech. VLSI, VIT Chennai

---

📌 Abstract

The Fiduccia-Mattheyses (FM) algorithm is one of the most widely applied heuristics for graph and circuit partitioning in VLSI Physical Design Automation (PDA). Its primary objective is cutsize minimization while maintaining balanced partitions.

This repository provides an extended, multi-branched, area-constrained, recursive, and randomized FM partitioning tool for digital Verilog netlists:

1. Randomized Multi-Start Optimization: Executes $N$ randomized initial cuts per partitioning step to avoid entrapment in local minima.
2. Recursive Area-Constrained Branching: Evaluates sub-partitions against user-defined area constraints $[a, b]$ and recursively sub-partitions blocks exceeding upper bound $b$ while freezing blocks within bounds.
3. Hypergraph Reconstruction & Dangling Net Pruning: Dynamically rebuilds internal connectivity networks at each recursion depth level, discarding dangling nets with fewer than two connected cells in the subpartition.
4. GUI & Performance Visualization: Built with Tkinter and Matplotlib to visualize finalized sectioned bar graph partition blocks, track iteration complexity, and inspect step-by-step partition history logs.

---

📁 Repository Structure

.
├── LICENSE                         # MIT License
├── README.md                       # Complete documentation & research guide
├── requirements.txt                # Python dependencies (matplotlib)
├── main.py                         # Unified entry point (GUI / CLI)
├── src/
│   ├── __init__.py                 # Package declaration
│   ├── verilog_parser.py           # Structural Verilog netlist parser & hypergraph generator
│   ├── fm_partitioner.py           # Core FM bipartitioner with multi-run random restarts
│   ├── recursive_partitioner.py    # Recursive multi-branched partition engine & tree builder
│   ├── gui.py                      # Tkinter + Matplotlib interactive visualization GUI
│   └── cli.py                      # Command-line interface runner
├── netlists/
│   ├── fa_asic.v                   # 1-bit Full Adder ASIC Netlist (Paper Benchmark)
│   ├── cont_netlist.v              # Controller Module Structural Netlist Benchmark
│   └── dp_netlist.v                # Datapath Module Netlist Benchmark
└── tests/
    ├── test_parser.py              # Tests for Verilog netlist parsing
    ├── test_fm.py                  # Tests for core FM algorithm gain & cut reduction
    └── test_recursive.py           # Tests for recursive area bounds adherence

---

💻 Codes Section

This section outlines the primary source code implementations included in this project.

1. src/verilog_parser.py (Netlist Hypergraph Parser)

Parses structural Verilog netlists (.v), strips comments (//, /* */), port headers, and wire declarations, constructing bidirectional dictionary mappings:

• cells_to_nets: Cell Instance Name -> List of Net Names
• nets_to_cells: Net Name -> List of Connected Cell Instance Names

2. src/fm_partitioner.py (Core FM Algorithm & Multi-Run Engine)

Implements single-pass FM bipartitioning with gain computation ($G(v) = FS(v) - TE(v)$), cell move locking, and dynamic balance ratio checking. multi_run_fm executes $N$ multi-start passes with random seeds to select the global minimum cut configuration.

3. src/recursive_partitioner.py (Recursive Area-Constrained Partitioner)

Engineers the hierarchical tree decomposition. For each subpartition with cell count $> b$ (max_block_size), it prunes dangling nets and recursively splits the block using multi-run FM, generating PartitionNode hierarchy and history step logs.

4. src/gui.py (Graphical User Interface)

Tkinter GUI featuring input fields for Netlist File (Browse), Minimum Block Size ($a$), Maximum Block Size ($b$), a Matplotlib sectioned horizontal bar chart visualizer ("Final Partition Blocks"), and a scrollable "Partitioning Details" modal window.

5. src/cli.py & main.py (CLI & Entry Point)

Unified entrypoint providing terminal execution options via --cli or graphical launcher mode.

---

⚡ Benchmark Verilog Netlists

netlists/fa_asic.v (1-bit Full Adder ASIC Netlist)

// Generated by Cadence Genus(TM) Synthesis Solution 21.14-s082_1
module fa_asic(cout, s, a, b, c, clk);
  input a, b, c, clk;
  output cout, s;
  wire a, b, c, clk;
  wire cout, s;
  wire n_0, n_1, reg_a, reg_b, reg_c;

  DFFHQXL cout_reg(.CK (clk), .D (n_0), .Q (cout));
  DFFHQXL s_reg(.CK (clk), .D (n_1), .Q (s));
  ADDFX1 g156__2398(.A (reg_b), .B (reg_a), .CI (reg_c), .S (n_1), .CO (n_0));
  DFFHQX1 reg_c_reg(.CK (clk), .D (c), .Q (reg_c));
  DFFHQX1 reg_b_reg(.CK (clk), .D (b), .Q (reg_b));
  DFFHQX1 reg_a_reg(.CK (clk), .D (a), .Q (reg_a));
endmodule

---

🚀 Installation & Usage

1. Requirements & Setup

Ensure Python 3.8+ is installed. Clone the repository and install dependencies:

git clone https://github.com/your-username/optimised-recursive-fm-partitioning.git
cd optimised-recursive-fm-partitioning
pip install -r requirements.txt

2. Running GUI Mode

To launch the interactive graphical application:

python main.py

• Click Browse to select a structural Verilog netlist (e.g., netlists/fa_asic.v or netlists/cont_netlist.v).
• Set Minimum Block Size (e.g., 2) and Maximum Block Size (e.g., 5).
• Click Run Partitioning to generate the horizontal bar plot visualizer.
• Click Show Details to open the partition step history and iteration complexity modal window.

3. Running CLI Mode

To run headless partitioning from the command line:

python main.py --cli --netlist netlists/fa_asic.v --min 2 --max 4 --runs 10

---

🧪 Running Unit Tests

Run the test suite to verify netlist parsing, FM gain calculation, and recursive area bounds adherence:

python -m unittest discover -s tests -p "test_*.py"

---

📜 References

1. Kernighan, B. W. & Lin, S. "An Efficient Heuristic Procedure for Partitioning Graphs." Bell System Technical Journal, 1970.
2. Fiduccia, C. M. & Mattheyses, R. M. "A Linear-Time Heuristic for Improving Network Partitions." DAC, 1982.
3. Karypis, G. & Kumar, V. "Multilevel k-way Hypergraph Partitioning." DAC, 1999.