Algorithmen Und Datenstrukturen Im Vlsi-Design: Obdd -- Grundlagen Und Anwendungen

ISBN-13: 9783540638698 / Niemiecki / Miękka / 1998 / 308 str.

Thorsten Theobald; Christoph Meinel

Opis

Eines der Hauptprobleme beim Chipentwurf besteht darin, da die Anzahl der zu bew ltigenden Kombinationen der einzelnen Chipbausteine ins Unerme liche steigt. Hier hat sich eine sehr fruchtbare Verbindung zu einem Kerngebiet der Theoretischen Informatik, dem Gebiet des Entwurfs von Datenstrukturen und effizienten Algorithmen, herstellen lassen: das Konzept der geordneten bin ren Entscheidungsgraphen, das in zahlreichen CAD-Projekten zu einer betr chtlichen Leistungssteigerung gef hrt hat. Die Autoren stellen die Grundlagen dieses interdisziplin ren Forschungsgebiets dar und behandeln wichtige Anwendungen aus dem rechnergest tzten Schaltkreisentwurf.

Spis treści

Einleitung.- Grundlagen.- Aussagen und Prädikate.- Mengen, Relationen und Funktionen.- Graphen.- Algorithmen und Datenstrukturen,- Komplexität von Algorithmen.- Endliche Automaten und Finite State Machines.- Referenzen.- Datenstrukturen für Schaltfunktionen.- Boolesche Funktionen.- Boolesche Algebra.- Boolesche Formeln und Funktionen.- Schaltfunktionen.- Referenzen.- Klassische Darstellungen.- Wahrheitstabellen.- Zweistufige Normalformen.- Schaltkreise und Formeln.- Binäre Entscheidungsbäume und -graphen.- Referenzen.- Anforderungen an Datenstrukturen für die formale Schaltkreisverifikation.- Formale Schaltkreisverifikation.- Funktionale Verifikation kombinatorischer Schaltkreise.- Referenzen.- OBDDs: Eine effiziente Datenstruktur.- OBDDS - Geordnete binäre Entscheidungsgraphen.- Bezeichnungen und Beispiele.- Reduzierte OBDDs: eine kanonische Darstellung für Schaltfunktionen.- Der Reduktionsalgorithmus.- Grundlegende Konstruktionen.- Ausführung binärer Operationen und Äquivalenztest.- Referenzen.- Effiziente Implementierung von OBDDs.- Schlüsselkonzepte.- Bekannte OBDD-Pakete.- Referenzen.- Einfluß der Variablenordnung auf die Komplexität von OBDDs.- Zusammenhang zwischen Variablenordnung und OBDD-Größe.- Exponentielle untere Schranken.- OBDDs mit verschiedenen Variablenordnungen.- Komplexität der Minimierung.- Referenzen.- Optimierung der Variablenordnung.- Heuristiken.- Dynamisches Umordnen.- Quantitative Aussagen.- Referenzen.- Anwendungen und Erweiterungen.- Analyse sequentieller Systeme.- Formale Verifikation.- Grundlegende Operatoren.- Erreichbarkeitsanalyse.- Effiziente Bildberechnung.- Referenzen.- Symbolisches Model Checking.- Computation Tree Logic.- CTL-Model Checking.- Implementierungen.- Referenzen.- Varianten und Erweiterungen von OBDDs.- Lockerung der Ordnungsrestriktionen.- Alternative Dekompositionstypen.- Zero-suppressed BDD.- Mehrwertige Funktionswerte.- Referenzen.- Transformationtechniken zur Optimierung.- TransformierteEntscheidungsgraphen.- Typbasierte Transormationen.- Lineare Transformationen.- Referenzen.- Literaturverzeichnis.

O autorze

Dr. sc. nat. Christoph Meinel (1954) ist Direktor und Geschäftsführer des Hasso-Plattner-Instituts für Softwaresystemtechnik GmbH (HPI) und ordentlicher Professor (C4) für Internet-Technologien und Systeme. Er hat Mathematik und Informatik an der Humboldt-Universität in Berlin studiert, dort 1981 promoviert und sich 1988 an der Akademie der Wissenschaften in Berlin habilitiert. Er wurde 1992 zum ordentlichen Professor (C4) für Informatik an die Univ. Trier berufen und hat dort in den Jahren 1998-2002 neben seinem Lehrstuhl das von der Fraunhofer-Gesellschaft betreute Institut für Telematik e.V. geleitet. Seit 2004 ist er Direktor und Geschäftsführer des HPIs und hat einen Lehrstuhl (C4) für Internet-Technologien und Systeme an der Universität Potsdam. Neben seiner Lehrtätigkeit in Potsdam ist er Gastprofessor an der Univ. Luxembourg (Luxembourg) und an der TU Peking (China) und als Programmdirektor des HPI-Stanford Forschungsprogramms zum Design Thinking Research tätig. Christoph Meinel ist Autor bzw. Co-Autor und Inhaber internationaler Patente. Seine aktuellen Forschungsinteressen liegen in den Bereichen IT-Sicherheit, Teleteaching, Semantic/Social Web und e-Health. Er war wissenschaftlich aktiv auch auf dem Gebiet der Komplexitätstheorie und hat (BDD-basierte) Datenstrukturen und effiziente Algorithmen untersucht und entworfen. Er ist Chairman des 2007 gegründeten deutschen IPv6-Rats, Herausgeber von ECCC - Electronic Colloquiums on Computational Complexity, des IT-Gipfelblog und des tele-TASK-Archivs. 1996-2007 gehörte er dem Direktorium des IBFI Schloss Dagstuhl an und war Sprecher der GI-Fachgruppe 'Komplexität'. Er hat in einer großen Zahl internationaler Programm-Komitees mitgewirkt, diverse Konferenzen und Symposien veranstaltet und ist in wissenschaftlichen Aufsichtsräten aktiv.

Blurb

Eines der Hauptprobleme beim Chipentwurf besteht darin, daß die Anzahl der zu bewältigenden Kombinationen der einzelnen Chipbausteine ins Unermeßliche steigt. Hier hat sich eine sehr fruchtbare Verbindung zu einem Kerngebiet der Theoretischen Informatik, dem Gebiet des Entwurfs von Datenstrukturen und effizienten Algorithmen, herstellen lassen: das Konzept der geordneten binären Entscheidungsgraphen, das in zahlreichen CAD-Projekten zu einer beträchtlichen Leistungssteigerung geführt hat. Die Autoren stellen die Grundlagen dieses interdisziplinären Forschungsgebiets dar und behandeln wichtige Anwendungen aus dem rechnergestützten Schaltkreisentwurf.