Signal transition graphs
Signal Transition Graphs (STGs) are typically used to describe dynamic behaviour of asynchronous circuits, for the purposes of their analysis or synthesis.
Informally, an STG is a graphical description of the behaviour of an asynchronous circuit in the form where information about causal relations between signalling events is represented directly, as opposed to descriptions based on states.
More formally, an STG is a type of interpreted (or labelled) Petri net whose transitions are labelled with the names of changes in the values of signals. For example, the typical case of the labelling is the case where signals are binary, hence the transition are interpreted as rising and falling edges of the signals in the circuit.
STGs usually give more compact descriptions of the behaviour of asynchronous circuits than state graphs. The complexity of an STG specification of a circuit is typically linear in the number of signals in the circuit while the complexity of a state graph can grow exponentially, due to the fact that asynchronous circuits have high degree of concurrency. In STGs concurrent events are represented via cause-sequence relations (cf. true concurrency) while in state graphs concurrency is represented via interleaving.
STGs were first proposed in 1981, under the name Signal Graphs, by Leonid Rosenblum (in Russian) in [1]. They were studied more formally and applied to the design of asynchronous interfaces by Alex Yakovlev in 1982, in his PhD thesis[2] (in Russian). They were later presented in English in 1985, in two independent sources, one by Rosenblum and Yakovlev in[3] and the other by Tam-Anh Chu in [4] (an earlier version was presented at ICCD'85) . Since then, STGs have been been studied extensively in theory and practice [5][6], which has led to the development of popular software tools for analysis and synthesis of asynchronous control circuits, such as Petrify[7] and Workcraft[8].
- ^ Л. Я. Розенблюм. "Язык сигнальных графов и его использование для моделирования протоколов информационного обмена и апериодических схем," Всесоюзный семинар Моделирование дискретных управляющих и вычислительных систем, стр. 22-24, 1981" (PDF).
{{cite web}}: CS1 maint: url-status (link) - ^ Yakovlev, Alex. "Design and Implementation of Asynchronous Communication Protocols in Systems Interfaces" in Russian (Проектирование и реализация протоколов асинхронного обмена информацией в межмодульном интерфейсе), PhD thesis (in Russian), 1982".
{{cite web}}: CS1 maint: url-status (link) - ^ Rosenblum, L.Ya. and Yakovlev, A.V. "Signal Graphs: from Self-timed to Timed ones. Proceedings of International Workshop on Timed Petri Nets, Torino, Italy, July 1985, IEEE CS Press, pp. 199-207" (PDF).
{{cite web}}: CS1 maint: multiple names: authors list (link) CS1 maint: url-status (link) - ^ "On the models for designing VLSI asynchronous digital systems". Integration. 4 (2): 99–113. 1986-06-01. doi:10.1016/S0167-9260(86)80002-5. ISSN 0167-9260.
- ^ Yakovlev, Alexandre; Lavagno, Luciano; Sangiovanni-Vincentelli, Alberto (1996-11). "A unified signal transition graph model for asynchronous control circuit synthesis". Formal Methods in System Design. 9 (3): 139–188. doi:10.1007/BF00122081. ISSN 0925-9856.
{{cite journal}}: Check date values in:|date=(help) - ^ Cortadella, J.; Kishinevsky, M.; Kondratyev, A.; Lavagno, L.; Yakovlev, A. (2002). Logic Synthesis for Asynchronous Controllers and Interfaces. Springer Series in Advanced Microelectronics. Vol. 8. Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/978-3-642-55989-1. ISBN 978-3-642-62776-7.
- ^ "Petrify: Related publications".
{{cite web}}: CS1 maint: url-status (link) - ^ "Workcraft".
{{cite web}}: CS1 maint: url-status (link)