Rechnerische Komplexität aktueller Netzlisten-Matching-Algorithmen

TL; DR: Das OP hat gefragt, ob sich die Rechenkomplexität des Abgleichs von Netzlisten vom Abgleich anderer Arten von Diagrammen unterscheidet. Das liegt nicht daran, dass Netzlisten immer noch GI-vollständige Graphen sind .

Die Rechenkomplexität ist immer noch GI, wenn Sie die Einschränkung auf Netzlisten hinzufügen, da Netzlisten dieselben Worst-Case-Szenarien durchlaufen wie andere Arten von Diagrammen und die Rechenkomplexität nur das Worst-Case-Verhalten betrachtet.

Das Einzige, was alle Arten von Netzlisten gemeinsam haben, ist, dass sie stark gekennzeichnet sind.

Innerhalb der Menge aller Netzlisten gibt es natürlich einfachere und schwierigere Fälle. Im Allgemeinen ist das Problem einfacher, wenn Sie ein Diagramm mit vielen verschiedenen Beschriftungen haben. Das heißt, eine Netzliste von Transistoren, bei der Sie nur n-Typen und p-Typen haben, ist schwieriger abzugleichen als eine Netzliste von Gattern, bei der Sie eine größere Anzahl von Zelltypen haben, was wiederum schwieriger abzugleichen ist als eine Netzliste für eine FPGA-Architektur N-Eingangs-LUTs mit$2^{2^N}$verschiedene LUT-Konfigurationen.

Wenn Sie sich das Isomorphismusproblem von Teilgraphen ansehen (dh versuchen, einen bestimmten Teilkreis zu finden und zu extrahieren), können Sie max. Polynom für jede gegebene Teilschaltung. Das ist imo ziemlich intuitiv: Wenn ich Ihnen eine bestimmte Schaltung gebe und Sie auffordere, Code zu schreiben, der nach dieser Schaltung sucht, könnten Sie das Muster einfach codieren, indem Sie alle Kandidaten für durchlaufen, wobei jeder Kandidat, wenn er ausgewählt wird, die mögliche Anzahl von Kandidaten für , node_1und node_2reduziert bald. Im schlimmsten Fall erzeugt dies K kaskadierte Schleifen für ein Muster von K Zellen, was eine Komplexität von ergibt$O(N^K)$um die Schaltung in einem Graphen mit N Knoten zu finden. (Jede Musterschaltung kann unterschiedliche Optimierungen ermöglichen, die eine Verringerung der Komplexität ermöglichen.)

Als Randbemerkung: Algorithmen, die eine Nachbarschaftsmatrix verwenden, verwenden normalerweise die folgende Codierung für die Schaltung: Es gibt einen Knoten für jede Zelle und einen Knoten für jedes Netz. Eine Verbindung zwischen zwei Zellen wird daher im Diagramm als zwei Kanten kodiert: eine von cell_1bis net_1und eine von net_1bis cell_2. (Ich habe auch Codierungen gesehen, die einen Zwischenknoten für jeden Zellenport erstellen, aber in den meisten Fällen werden Informationen zu Zellenports in Kantenetiketten gespeichert.) Dadurch wird sichergestellt, dass selbst für Netze mit großem Fan-Out (wie z. B. Reset-Signale, zum Beispiel) bleibt die Nachbarschaftsmatrix sehr spärlich (Anzahl der Nicht-Nullen linear zur Anzahl der Zellen und Netze, anstelle der quadratischen Komplexität für die naive Codierung).

Ein netter Algorithmus, der leicht auf die Bedürfnisse einer bestimmten Problemdomäne erweitert werden kann, ist der Ullmann-Subgraph-Isomorphismus-Algorithmus . Es ist schon ziemlich alt und nicht der effizienteste Algorithmus, aber ich denke, es ist ein sehr klarer Algorithmus, und wenn Sie ihn lernen, können Sie das Problem, das er löst, besser verstehen.