Hierarchical pattern matching in VLSI [Elektronische Ressource] / Marko Milošević

Mm

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2009
• Nombre de lectures: 15
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Institut für Informatik
der Technischen Universität München

Lehrstuhl für Informatik mit Schwerpunkt
Wissenschaftliches Rechnen


Hierarchical Pattern Matching in VLSI


Marko Milošević


Vollständiger Abdruck der von der Fakultät für Informatik der Technischen Universi-
tät München zur Erlangung des akademischen Grades eines

Doktors der Naturwissenschaften (Dr. rer. nat.)

genehmigten Dissertation.




Vorsitzender: Univ.-Prof. Tobias Nipkow Ph.D.

Prüfer der Dissertation: 1. Univ.-Prof. Dr. Hans-Joachim Bungartz

2. Univ.-Prof. Dr. Erich Barke, Leibniz Universität Hannover

3. Univ.-Prof. Dr. Thomas Huckle



Die Dissertation wurde am 25.03.2009 bei der Technischen Universität München ein-
gereicht und durch die Fakultät für Informatik am 06.07.2009 angenomen.
Abstract









Structural pattern matching is an important part of the microchip design
verification process. It is necessary to isolate semantic structural contexts in a given
design netlist in order to be able to perform flexible and intelligent checks like, for
example LVS (Layout Versus Schematics), ERC (Electrical Rule Checks), gate level
netlist timing analysis and others. Because of that, many different algorithms were
devised to support this particular segment of chip verification. The theoretical basis
for these algorithms is pattern matching in graphs, i.e. subgraph isomorphism. Algo-
rithms developed so far are working with flat input netlists. This is not efficient and
limits the application of the mentioned algorithms due to the flat netlist´s extensive
size. Making the pattern matching hierarchical can improve the processes of chip de-
sign verification and simulation.
We provide the solution for the problem of the structural pattern matching in
hierarchical netlists by defining the new methodology which employs the concept of
Layered Views to present the hierarchical layout of a given netlist in a "friendly" way
to an arbitrary application domain (user) algorithm. This general framework solves
typical problems that algorithms working with hierarchical netlists are facing. Particu-
larly, we propose the 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. We achieve this by materializing (creating a proxy copy) a small
data portion which is kept consistent with the source hierarchical netlist by specific
algorithms and data structures. The view offers the possibility to emboss the materia-
lized data portion into the primary design's hierarchy, as a separate instance, altering
the primary hierarchy. The outcome of this process is again a valid hierarchical netlist.
We, further, apply the defined concepts to Incremental Pattern Matching, originally
developed for flat input netlists only. 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. The quantitative improvement is discussed through
runtime and memory requirement tests. The qualitative improvement comes from the
fact that the new methodology allows full-chip analysis and concise, hierarchical re-
sult reports.

iii Zusammenfassung

Der Verifikationsprozess integrierter Schaltungen beinhaltet eine ganze Reihe
wichtiger Prüfungen wie LVS (Layout vs. Schematics), ERC (Electrical Rule Check),
Statische Timinganalyse und andere, die flexibler und effizienter durchgeführt werden
können, wenn der funktionale Aufbau der Schaltung der Prüfung zugänglich ist (und
nicht nur eine rein transistorbasierte Netzliste ohne weitere Struktur vorliegt).
Aus diesem Grund ist eine strukturbasierte Mustererkennung, die es erlaubt, die für
den Verifikationsprozess wichtigen Kontexte aus der Schaltung zu isolieren, ein we-
sentlicher Differentiator für die Qualität der eingesetzten Verifikationsprogramme
hinsichtlich Performanz und Fehlerabdeckung. Dies hat in der Vergangenheit zu etli-
chen Aktivitäten in diesem Gebiet geführt, so dass eine Vielzahl unterschiedlicher
Algorithmen und Implementierungen zur Mustererkennung vorliegt. Gemeinsam ist
ihnen die Identifizierung von Mustern in Graphen, also die Erkennung von
Teilgraphisomorphismen.
Die bisher entwickelten Algorithmen setzen flache Netzlisten ohne innere
Struktur (Hierarchie) voraus. Das ist bei grossen Datenmengen nicht effizient und
limitiert das Anwendungsgebiet. Gelingt es also, die Strukturerkennung auf hierarchi-
schen Daten zu ermöglichen, so kann eine sehr grosse Verbesserung der Verifikati-
onsperformanz erzielt werden.
In dieser Arbeit stellen wir eine Lösung für die hierarchische Erkennung von
Mustern in hierarchischen Netzlisten vor, die auf der Einführung der neuen Technik
sogenannter "Layered Views" beruht. Mit ihrer Hilfe werden die hierarchischen Daten
den Applikationen auf eine sehr benutzerfreundliche und einfach zu nutzende Weise
präsentiert. Insbesondere schlagen wir an dieser Stelle "Virtually Flattened Views"
(VFV) vor. Diese präsentieren die hierarchischen Daten in einer Weise, die der Ap-
plikation erlaubt, sie zu interpretieren, als kämen sie von einer flachen Datenbasis.
Typische Probleme, die beim Arbeiten mit hierarchischen Daten gelöst werden müs-
sen, lassen sich auf diesem Weg einmal lösen, die Applikationen können in weiten
Teilen unverändert von einer flachen Implementierung auf eine hierarchische Imple-
mentierung portiert werden, nur durch die Umstellung auf die Nutzung des VFV als
Beispiel eines "Layered Views". Der VFV wird durch eine sehr lokale Ausflachung
der hierarchischen Datenbasis implementiert, die dynamisch den Anforderungen der
flachen Applikation entsprechend aktualisiert wird.
Auf diesem Weg können wir aber nicht nur die hierarchischen Daten lokal
flach zur Verfügung stellen, wir können auch die Ergebnisse der Mustererkennung,
die nun ja flach entstehen, ohne weiteres in die hierarchische Datenbasis unter Modi-
fikation der existierenden Hierarchie zurückschreiben. Das Ergebnis der Musterer-
kennung ist also wieder eine hierarchische Netzliste. Weiter gehend wenden wir die
neuen Techniken auf die inkrementelle Mustererkennung an, die ursprünglich nur für
flache Daten implementiert wurde. Insgesamt gesehen haben wir damit das Problem
der Mustererkennung in hierarchischen Netzlisten vollständig gelöst.
Für einige Referenzszenarios, die aus realen Industrieapplikationen stammen, de-
monstrieren wir die quantitativen und qualitativen Verbesserungen, die mit unserem
Ansatz erzielt werden können. Die quantitativen Aspekte werden anhand von Laufzeit
und Speicherverbrauchsvergleichen diskutiert. Die qualitativen Verbesserungen erzie-
len wir zum einen durch sehr kompakte (hierarchische) Ergebnisse, zum anderen kön-
nen nun erstmals Netzlisten für das komplette Design bearbeitet werden, während
vorher nur Teilausschnitte geprüft werden konnten.

v vi
Acknowledgemens









I thank my professor, Prof. Dr. Hans-Joachim Bungartz for leading me
through this project methodologically and giving me self-confidence in crucial mo-
ments. I want to thank Dr. Martin Frerichs, Dr. Tilman Neunhöffer, Hannes Arm-
ruster and the rest of the ATS department of Qimonda AG for the substantial support
of my work. I am especially grateful to Dr. Alexander Seidl for having the organisa-
tional side of my project in a perfect grip. In the end, I want to thank my family and
friends for understanding and believing in me.



Marko Milošević




vii viii Contents



1 INTRODUCTION ....................................................................................................................... 13
1.1 MOTIVATION ........................................................................................................................ 13
1.2 OBJECTIVES AND SCOPE ....................................................................................................... 15
1.3 OUTLINE .............................................................................................................................. 16
2 GRAPH MATCHING CONCEPTS IN VLSI .......................................................................... 19
2.1 BASICS OF GRAPH NOTATION ................................................................................................ 19
2.2 GRAPH MATCHING ................................................................................................................ 21
2.3 SUBCIRCUIT RECOGNITION, THE APPLICATION OF SUBGRAPH MATCHING ............................. 23
2.4 INCREMENTAL PATTERN MATCHING ............................................