Output-Determinacy and Asynchronous Circuit Synthesis

in: Augsburg Technical Report, Institute of Computer Science, University of Augsburg, January 2007

Signal Transition Graphs (STG) are a formalism for the description of asynchronous circuit behaviour. In this paper we propose (and justify) a formal semantics of non-deterministic STGs with dummies. For this, we introduce a concept of output-determinacy, which is a relaxation of determinism, and argue that it is reasonable and useful in the speed-independent context.

We apply the developed theory to justification of a new STG decomposition algorithm used to tackle the state explosion problem during circuit synthesis.

Downloads:

• Output-Determinacy and Asynchronous Circuit Synthesis  -  (output-determinacy-tr.pdf, 418 KB)