Component refinement and CSC-solving for STG decomposition

STGs (Signal Transition Graphs) give a formalism for the description of asynchronous circuits based on Petri nets. To overcome the state explosion problem one may encounter during circuit synthesis, a nondeterministic algorithm for decomposing STGs was suggested by Chu and improved by one of the present authors. Here we study how CSC-solving–which is essential for circuit synthesis–can be combined with decomposition. For this purpose, the correctness definition for decomposition is enhanced with internal signals and hierarchical decomposition is proven correct. Based on this, it is shown that speed-independent CSC-solving preserves correctness and can be combined with decomposition. Furthermore, we use our new correctness definition to give the first correctness proof for the decomposition method of Carmona and Cortadella. Finally, we compare three different implementation relations for STGs: one derived from our correctness definition; one defined by Dill based on trace structures; and one derived from I/O-compatibility defined by Carmona and Cortadella.

Authors

• Mark Schaefer
• Walter Vogler

Keywords

• Asynchronous circuits
• STG
• Petri nets
• Decomposition
• Implementation relation