A correctness criterion for asynchronous circuit validation and optimization

Update Item Information
Publication Type technical report
School or College College of Engineering
Department School of Computing
Program Advanced Research Projects Agency
Creator Brunvand, Erik L.
Other Author Gopalakrishnan, Ganesh; Michell, Nick; Nowick, Steven M.
Title A correctness criterion for asynchronous circuit validation and optimization
Date 1992
Description In order to reason about the correctness of asynchronous circuit implementations and specifications, Dill has developed a variant of trace theory [1]. Trace theory describes the behavior of an asynchronous circuit by representing its possible executions as strings called "traces" A useful relation defined in this theory is called conformance which holds when one trace specification can be safely substituted for another. We propose a new relation in the context of Dill's trace theory called strong conformance. We show that this relation is capable of detecting certain errors in asynchronous circuits that cannot be detected through conformance, Strong conformance also helps to justify circuit optimization rules where a component is replaced by another component having extra capabilities (e.g., it can accept more inputs). The structural operators of Dill's trace theory compose rename and hide - are shown to be monotonic with respect to strong conformance. Experiments are presented using a modified version of Dill's trace theory verifier which implements the check for strong conformance.
Type Text
Publisher University of Utah
Subject Asynchronous circuits; Circuit optimizations; Formal verification of hardware; Trace theory; Asynchronous circuit validation
Subject LCSH Asynchronous circuits
Language eng
Bibliographic Citation Gopalakrishnan, G., Brunvand, E. L., Michell, N., & Nowick, S. M. (1992). A correctness criterion for asynchronous circuit validation and optimization. UUCS-92-004.
Series University of Utah Computer Science Technical Report
Relation is Part of ARPANET
Rights Management ©University of Utah
Format Medium application/pdf
Format Extent 256,669 bytes
Source University of Utah School of Computing
ARK ark:/87278/s6765zgh
Setname ir_uspace
ID 703084
Reference URL https://collections.lib.utah.edu/ark:/87278/s6765zgh