Titre:
Delay-Insensitivity and Semi-Modularity
Conférencier:
John Brzozowski ,
University of Waterloo (Ontario)
Lieu:
Université de Montréal, Pavillon André-Aisenstadt ,
Room 1175
Date et heure:
mercredi le 24 février 1999 de
10:30 à 00:00
Résumé:
The study of asynchronous circuit behaviors in the presence of component and wire delays has received a great deal of attention. In this talk, we consider asynchronous circuits whose components can be any non-deterministic sequential machines of the Moore type, and describe a formal model for these circuits and their behaviors under the inertial delay model.
We model an asynchronous circuit C by a network N of modules with delays associated with its components and/or wires. We compute the behavior of N assuming arbitrary inertial delays in the modules, and take this behavior to be correct. We define N to be strongly delay-insensitive if its behavior remains correct in the presence of arbitrary stray delays, where correctness is defined through the notion of observational equivalence (or bisimulation), one of the strongest forms of behavioral equivalence. We introduce the notion of quasi semi-modularity, which generalizes Muller's definition of semi-modularity to non-deterministic networks. We prove that a circuit, with all the wire delays taken into account, is strongly delay-insensitive if its behavior is quasi semi-modular.
In asynchronous circuit theory, most authors use the interleaving model of concurrency, where only one signal can change at a time. In contrast to this, true concurrency models allow multiple signal changes, and, in general, may produce results that differ from those obtained with interleaving. We have proved that, in the context of delay-insensitivity and semi-modularity, the simpler interleaving model suffices.
Note biographique:
Janusz A. (John) Brzozowski received the BASc and MASc degrees in electrical engineering from the University of Toronto in 1957 and 1959, respectively, and the MA and PhD degrees in electrical engineering from Princeton University in 1962.
He was Assistant Professor from 1962 to 1965 and Associate Professor from 1965 to 1967 in the Department of Electrical Engineering, University of Ottawa. From 1967 to 1996 he was Professor in the Department of Computer Science, University of Waterloo. In the periods 1978-1983 and 1987-1989 he was chair of that department. He has had visiting appointments at the University of California, Berkeley (1965-1966), University of Paris (1974-1975), University of Sao Paulo (1983), Kyoto University (1984), and Eindhoven University (1989-1990). In 1996 he received the title Distinguished Professor Emeritus from the University of Waterloo, where he is also Adjunct Professor.
Dr. Brzozowski has published many papers in the areas of regular languages, finite automata, asynchronous circuits, and testing. He is co-author of Digital Networks (Prentice-Hall, 1976), and of Asynchronous Circuits (Springer-Verlag, 1995). His present research interests include Asynchronous Circuits, VLSI Models, Testing, Automata and Formal Languages.