Close

BLIF Parsing and Hypergraph Partitioning

A project log for Open Source FPGA

An open source FPGA implementation.

Will LongWill Long 08/02/2016 at 01:430 Comments

The BLIF parser is shaping up. The core functionality is implemented; it can parse technology-mapped logic gates! These get read into an AST, which it then transformed into a hypergraph. In my original Python prototype, I used a directed graph to hold my circuits. Hypergraphs came into the SML version naturally, as BLIF uses named nets to connect the ports of gates. These named nets can connect an arbitrary number of input and output ports, and so correspond to the concept of a hyperedge.

I have also written the core code for graph partitioning. I decided to continue using the Fiduccia-Mattheyses Algorithm. It needs some tuning of the conditions for partitioning. For example, I have hard-coded the ratio for dividing the nodes into two partitions.

Next steps: parsing LEF files, more placement logic, and DEF file printing.

Discussions