Subcircuit recognition (SR) is important for IC verification: ERC (electrical rule check), static timing analysis, etc. Many different algorithms were devised to support this segment of chip verification. The theoretical basis for these algorithms is pattern matching in graphs, i.e. subgraph isomorphism. Algorithms developed so far work only with inefficient flat input netlists. We provide a novel solution for the SR problem in hierarchical netlists. Virtually Flattened View (VFV), a sophisticated concept that prepares the hierarchical data for the user algorithms and allows them to see that data as if they were flat, is proposed. We apply the defined concept to incremental flat pattern matching. In this way we obtain the methodology to solve the problem of pattern matching in hierarchical netlists. For several reference scenarios, quantitative and qualitative improvements of our approach are demonstrated.     «

Subcircuit recognition (SR) is important for IC verification: ERC (electrical rule check), static timing analysis, etc. Many different algorithms were devised to support this segment of chip verification. The theoretical basis for these algorithms is pattern matching in graphs, i.e. subgraph isomorphism. Algorithms developed so far work only with inefficient flat input netlists. We provide a novel solution for the SR problem in hierarchical netlists. Virtually Flattened View (VFV), a sophisticat...     »

Subcircuit Recognition (SR) ist wichtig für die Verifikation von ICs: ERC (Electrical Rule Check), Statische Timinganalyse, etc. Verschiedene Algorithmen wurden in der Vergangenheit entwickelt, um SR zu unterstützen. Die theoretische Basis für diese Algorithmen ist Mustererkennung in Graphen, d.h. Teilgraphisomorphismus. Die Algorithmen, die entwickelt wurden, bearbeiten nur ineffiziente, flache Netzlisten. Wir führen eine neue Lösung für das SR-Problem mit hierarchischen Netzlisten ein. Wir schlagen die neue Lösung als „Virtually Flattened View„ (VFV) vor. VFV bereitet die hierarchischen Netzlisten für die Benutzeralgorithmen vor, sodass sie von diesen als flach angesehen werden können. Wir wenden die neuen Konzepte mit inkrementeller Mustererkennung an. Somit erreichen wir eine neue Methode für SR in hierarchischen Netzlisten. In mehreren Beispielen werden die quantitativen und qualitativen Verbesserungen unserer Methode aufgezeigt.     «

Subcircuit Recognition (SR) ist wichtig für die Verifikation von ICs: ERC (Electrical Rule Check), Statische Timinganalyse, etc. Verschiedene Algorithmen wurden in der Vergangenheit entwickelt, um SR zu unterstützen. Die theoretische Basis für diese Algorithmen ist Mustererkennung in Graphen, d.h. Teilgraphisomorphismus. Die Algorithmen, die entwickelt wurden, bearbeiten nur ineffiziente, flache Netzlisten. Wir führen eine neue Lösung für das SR-Problem mit hierarchischen Netzlisten ein. Wir sch...     »