# Computational complexity of current netlist matching algorithms

I understand that the problem of matching two netlists could be reduced to the graph isomorphism problem which is NP-intermediate. Apart from that what are the complexity results of some of the currently used netlist matching algorithm?

• Welcome, Omar! Although your question is about netlists, I suspect that it's a bit off-topic here because you are asking about computational aspects of algorithms. Maybe you'd get better answers from Theoretical Computer Science Stack Exchange site. It may even be on-topic on StackOverflow.com ifself. – Ricardo Jun 3 '14 at 19:31
• @Ricardo, I was looking for netlist specific algorithms. I suspect netlists might have some special constraints on the graphs associated with it. – Omar Shehab Jun 4 '14 at 1:48
• Yes, I understand that your question requires interdisciplinary expertise. That's what makes it more difficult to answer, I suppose. Maybe you'd get better results if you elaborated a bit on your question, for example, by showing more details of the formulation of the graph isomorphism problem you mentioned, or even if you listed some examples of netlist matching algorithms that you know of, just so people know what you're looking for? Or maybe you could expand on what constraints you think netlists may have, so users here can elaborate on it? – Ricardo Jun 4 '14 at 2:11
• I'm keeping an eye on this thread. If there are no answers within 24h from posting here on EE.SE, I'll migrate it to the Theoretical CS stack. I'm a bit weary that while the CS guys might know more about graphs, Omar would have to explain to them what a netlist is. – Nick Alexeev Jun 4 '14 at 3:13
• This is a very valid question, it's on the other end of the spectrum from the tinkerers and hobbyists that also ask questions here, but it is kind of refreshing. The fact is, most EDA tools are stuck back in the 70's and the only real solution is to throw more processors at a design during tape out. There very clearly is a better way and it probably lies in the area of better/different data representation. – placeholder Jun 6 '14 at 9:03

TL;DR: The OP asked if the computational complexity of matching netlists is different from matching other types of graphs. It isn't because netlists are still GI-complete graphs.

The computational complexity is still GI if you add the restriction to netlists, because netlists experience the same worst case scenarios than other types of graphs and computational complexity only looks at the worst case behavior.

The only real thing that have all kinds of netlists in common is that they are heavily labeled.

Within the set of all netlists there are of course cases that are easier and cases that are harder. In general the problem is easier if you have a graph with many different labels. I.e. a netlist of transistors where you only have n-types and p-types is harder to match than a netlist of gates where you have a larger number of cell types, which in turn is harder to match than a netlist for an FPGA architecture with N-input LUTs with $2^{2^N}$ different LUT configurations.

When looking at the subgraph isomorphism problem (i.e. trying to find and extract a given sub circuit), you can give a max. polynomial for each given sub circuit. This is imo pretty intuitive: If I give you a specific circuit and ask you to write code that looks for this circuit you could simply encode the pattern by iterating over all candidates for node_1, each candidate when chosen reducing the possible number of candidates for node_2, and so on. In the worst case this will create K cascaded loops for a pattern of K cells, yielding a complexity of $O(N^K)$ for finding the circuit in a graph of N nodes. (Each pattern-circuit may allow for different optimizations that allow for reducing the complexity.)

As a side note: Algorithms that use a neighborhood matrix usually use the following encoding for the circuit: There is a node for each cell and a node for each net. A connection between two cells is therefore encoded as as two edges in the graph: one from cell_1 to net_1 and one from the net_1 to cell_2. (I've also seen encodings that create an intermediate nodes for each cell port, but in most cases information regarding cell ports is stored in edge labels.) This will ensure that even for nets with large fan-out (such as reset signals, for example) the neighborhood matrix stays very sparse (number of non-zeros linear to the number of cells and nets, instead of the quadratic complexity for the naive encoding).

A nice algorithm that can be extended easily to the needs of a specific problem domains is the Ullmann subgraph isomorphism algorithm. It is already pretty old and not the most efficient algorithm, but I think it is a very clear algorithm and learning it helps you to better understand the problem it solves.