Abstract
The object of this article is the analysis of asynchronous circuits for speed independence or delay insensitivity. The circuits are specified as a netlist of logic functions describing the components. The analysis is based on a derivation of an event specification of the circuit behavior in a form of a signal graph. Signal graphs can be viewed either as a formalization of timing diagrams, or as a signal interpreted version of marked graphs (a subclass of Petri nets). The main advantage of this method is that a state explosion is avoided. A restoration of an event specification of a circuit also helps to solve the behavior identification problem, i.e., to compare the obtained specification with the desired specification. We illustrate the method by means of some examples.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
C.L. Seitz. System timing. InIntroduction to VLSI Systems, C. Mead and L. Conway, (eds.), Addison-Wesley, Reading, MA, 1980, ch. 7.
V.I. Varshavsky, M.A. Krishnevsky, V.B. Marakhovsky, V.A. Peschansky, L. Ya. Rosenblum, A.R. Taubin, and B.S. Tzirlin.Self-Timed Control of Concurrent Processes. Kluwer Academic Publishers, Boston, 1990.
A.J. Martin. Programming in VLSI: From communicating processes to delay-insensitive circuits. InUT Year of Programming Institute on Concurrent Programming, C.A.R. Hoare (ed.), Addison-Wesley, Reading, MA, 1989.
J. Staunstrup and M.R. Greenstreet. Synchronized transitions. InFormal Methods for VLSI Design, J. Staunstrup (ed.), Elsevier, Amsterdam, 1990, pp. 71–128.
C.H. (Kees) van Berkel, C. Niessen, M. Rem and S. Saeijs. VLSI programming and Silicon Compilation. InProceedings of the International Conference on Computer Design (ICCD'88), IEEE Computer Society Press, Rye Brook, NY, 1988, pp. 150–166.
M.A. Kishinevsky, A. Yu. Kondratyev, and A.R. Taubin. Formal methods for self-timed design. InProceedings of the European Conference on Design Automation (EDAC'91), IEEE Computer Society Press, Amsterdam, 1991, pp. 197–201.
Ch.E. Molnar, T.P. Fang, and F.U. Rosenberg. Synthesis of delay-insensitive modules. InProceedings of 1985 Chapel Hill Conference on Very Large Scale Integration, Computer Science Press, Rockville, MD, 1985, pp. 67–86.
S.M. Burns.Performance Analysis and Optimization of Asynchronous Circuits, Ph.D. thesis, California Institute of Technology, Computer Science Department, Pasadena, CA, 1991.
M.A. Kishinevsky, A.Yu. Kondratyev, A.R. Taubin, and V.I. Varshavsky. Analysis and identification of Self-Timed Circuits. InProceedings of IFIP 2nd Workshop on Designing Correct Circuits, Elsevier, Lyngby, Denmark, 1992, pp. 275–287.
D.E. Muller and W.S. Bartky. A theory of asynchronous circuits. InProceedings of an International Symposium on the Theory of Switching. Harvard University Press, Cambridge, MA, 1959, pp. 204–243.
Jo C. Ebergen and S. Gingras. A verifier for network decompositions of command-based specifications. InProceedings of the 26th Hawaii International Conference on System Sciences, IEEE Computer Society Press, Wailea, Hawaii, Vol. 1, pp. 310–318.
M.A. Kishinevsky,Implementation and Analysis of Self-Timed Circuits, Ph. D. thesis, Leningrad Electrical Engineering Institute, Department of Computer Science, 1982.
W.D. Frazer and D.E. Muller. A method for factoring and action of asynchronous circuits. InProceedings of the First Annual AIEE Symposium on Switching Circuit Theory and Logical Design, New York, 1961, pp. 246–249.
P.A. Beerel and T.H.-Y. Meng. Semi-modularity and testability of speed-independent circuits,Integration, 13(3): 301–322, 1992.
V.I. Varshavsky, et al. Theory, methods and software support for self-timing design, Research Report PIN-2, R&D Coop “Trassa.” Institute of Informatics Problems, Leningrad, Moscow, 1990.
I.E. Sutherland. Micropipelines,Communications of the ACM, 32(6):720–738, 1989.
G. Birkhoff.Lattice Theory. American Mathematical Society, Providence, RI, 1967.
T.A. Chu,Synthesis of Self-Timed VLSI Circuits from Graph-Theoretic Specifications. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 1987.
V.I. Varshavsky, M.A. Kishinevsky, A.Yu. Kondratyev, L.Ya. Rosenblum, and A.R. Taubin. Models for specification and analysis of processes in asynchronous circuits.Soviet Journal of Computer and Systems Sciences, 26(2): 61–76, 1989.
M.A. Kishinevsky, A.Yu. Kondratyev, and A.R. Taubin. Specification and analysis of self-timed circuits,Journal of VLSI Signal Processing, Special Issue on Asynchronous Design, 6:331–349, 1993.
A. Yakovlev, L. Lavagno and A. Sangiovanni-Vincentelli. A unified signal transition graph model for asynchronous control circuit synthesis. Technical Report UCB/ERL M92/78, University of California-Berkeley, July 1992.
A.Yu. Kondratyev.Design at Self-Timed Circuits from Change Diagrams. Ph. D. thesis, Leningrad Electrical Engineering Institute, Department of Computer Science, 1987.
J. Sparsø, C.D. Nielsen, L.S. Nielsen, and J. Staunstrup. Design of self-timed multipliers: A Comparison. InProceedings of Working Conference on Asynchronous Design Methodologies, Elsevier, Manchester, March 1993.
D. Dill.Trace Theory for Automatic Hierarchical Verification of Speed-Independent Circuits. MIT Press, Cambridge, MA, 1989.
L. Ya. Rosenblum. The Signal graph language for the modeling of exchange protocols and aperiodic circuits. InProceedings “Simulation of digital control and computer systems.” Sverdlovsk, IMM, 1981 (in Russian).
F. Commoner, A.W. Holt, S. Even, and A. Pnueli. Marked directed graphs.Journal of Computer and System Sciences, 5: 511–523, 1971.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kishinevsky, M., Kondratyev, A., Taubin, A. et al. Analysis and identification of speed-independent circuits on an event model. Form Method Syst Des 4, 33–75 (1994). https://doi.org/10.1007/BF01383956
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01383956