DFG-Projekt (WO 814/1-1)

Dekomposition von Signalflankengraphen zur Synthese asynchroner Steuerwerksverbünde

Interdisziplinäres Forschungsprojekt mit Prof. W. Vogler (Theoretische Informatik, Universität Augsburg).

Zusammenfassung
Wegen ihrer hohen, der jeweiligen Situation angepassten Reaktionsgeschwindigkeit, der geringen Ruheverlustleistung und der günstigeren EMV-Eigenschaften genießen asynchrone Schaltungen derzeit besondere Aufmerksamkeit. Aufgrund der Nebenläufigkeit haben sich zu ihrer Spezifikation Signalflankengraphen (signal transition graphs, STGs) bewährt. Aus diesen werden zur Synthese endliche Automaten abgeleitet, deren Zustandszahl aber oft prohibitiv groß ist. Zur Bewältigung dieser Zustandsexplosion kann man den STG in kleinere Teilnetze dekomponieren; unabhängig vom Problem der Zustandsexplosion führt dies auf eine Verbund-Lösung, die einer En-bloc-Lösung i.a. vorzuziehen ist.
Die bisher bekannten Dekompositionsverfahren sind allerdings nur für sehr eingeschränkte Netzklassen anwendbar. Ziel des Projektes ist es, diese Verfahren zu verallgemeinern – speziell auch auf die sog. generalized STGs – und dabei besonderen Wert auf eine saubere formale Absicherung zu legen. Weiter sollen Qualitätskriterien zum Vergleich verschiedener Dekompositionen sowie an diesen Kriterien ausgerichtete Dekompositionsmethoden entwickelt werden, wobei die Wiederverwendung von Bausteinen ein wichtiger Gesichtspunkt ist. Schließlich sollen die Ergebnisse in ein CAD-Werkzeug integriert werden (Download DESI).
 

Erste Forschungsergebnisse:
W.Vogler, R.Wollowski: Decomposition in Asynchronous Circuit Design.
Report 2002-5, Universität Augsburg, März 2002. Beispiele zum Bericht.

Project Summary
Today, asynchronous circuits are seriously considered because of their fast response times, low power consumption, and improved noise and electromagnetic compatibility properties.
As event-driven systems, asynchronous circuits react immediately and concurrently to changes of their input signals. Therefore, an adequate design basis is a specification of the desired behaviour from a causal point of view. Focussing on the design of asynchronous controllers, the best-known causal specification is the Petri net based Signal Transition Graph (STG), where the firing of a transition is interpreted as the occurrence of a signal edge.
Usually, a finite state machine is derived from the STG specification as a first step of circuit synthesis, but the number of resulting states often is prohibitively high. To cope with this state explosion problem, the STG can be decomposed into component-STGs. This leads to a distributed implementation, which is also to be preferred for performance reasons.
However, the decomposition procedures known up to now can only be applied to very restricted Petri net classes that do not cover all of the causal relations present in asynchronous behaviour. The goal of the project is to generalize these procedures stressing a proper formal validation. Furthermore, quality criteria for the comparison of different decomposi-tions should be developed as well as decomposition procedures based on these criteria; an important aspect is the reuse of components. Finally, the results should be integrated into a CAD tool. (Download DESI).