Delay-Insensitivity and Semi-Modularity |
| |
Authors: | J.A. Brzozowski H. Zhang |
| |
Affiliation: | (1) Department of Computer Science, University of Waterloo, Waterloo, ON, Canada, N2L 3G1;(2) Department of Computer Science, University of Toronto, Toronto, ON, Canada, M5S 3G4 |
| |
Abstract: | The study of asynchronous circuit behaviors in the presence of component and wire delays has received a great deal of attention. In this paper, 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-intensitive if and only if its behavior is quasi semi-modular. |
| |
Keywords: | asynchronous bisimulation delay-dense isochronic module network semi-modular speedindependent delay-insensitive |
本文献已被 SpringerLink 等数据库收录! |
|