Signal transition graphs: Difference between revisions

Add links
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Added references
No edit summary
Line 16: Line 16:


STGs with timing (delays) information annotation were first introduced in <ref name=":0" />, where the ideas of analysis of behaviour of circuits with timing constraints<ref>{{Cite journal|last=Cortadella|first=Jordi|last2=Kishinevsky|first2=Michael|last3=Kondratyev|first3=Alex|last4=Lavagno|first4=Luciano|last5=Taubin|first5=Alexander|last6=Yakovlev|first6=Alex|date=1998|title=Lazy transition systems: application to timing optimization of asynchronous circuits|url=http://portal.acm.org/citation.cfm?doid=288548.288633|journal=Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design - ICCAD '98|language=en|location=San Jose, California, United States|publisher=ACM Press|pages=324–331|doi=10.1145/288548.288633|isbn=978-1-58113-008-9}}</ref>, later called Relative Timing<ref>{{Cite journal|last=Stevens|first=K.|last2=Ginosar|first2=R.|last3=Rotem|first3=S.|date=1999|title=Relative timing|url=http://ieeexplore.ieee.org/document/761535/|journal=Proceedings. Fifth International Symposium on Advanced Research in Asynchronous Circuits and Systems|location=Barcelona, Spain|publisher=IEEE Comput. Soc|pages=208–218|doi=10.1109/ASYNC.1999.761535|isbn=978-0-7695-0031-7}}</ref>, were also first introduced.
STGs with timing (delays) information annotation were first introduced in <ref name=":0" />, where the ideas of analysis of behaviour of circuits with timing constraints<ref>{{Cite journal|last=Cortadella|first=Jordi|last2=Kishinevsky|first2=Michael|last3=Kondratyev|first3=Alex|last4=Lavagno|first4=Luciano|last5=Taubin|first5=Alexander|last6=Yakovlev|first6=Alex|date=1998|title=Lazy transition systems: application to timing optimization of asynchronous circuits|url=http://portal.acm.org/citation.cfm?doid=288548.288633|journal=Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design - ICCAD '98|language=en|location=San Jose, California, United States|publisher=ACM Press|pages=324–331|doi=10.1145/288548.288633|isbn=978-1-58113-008-9}}</ref>, later called Relative Timing<ref>{{Cite journal|last=Stevens|first=K.|last2=Ginosar|first2=R.|last3=Rotem|first3=S.|date=1999|title=Relative timing|url=http://ieeexplore.ieee.org/document/761535/|journal=Proceedings. Fifth International Symposium on Advanced Research in Asynchronous Circuits and Systems|location=Barcelona, Spain|publisher=IEEE Comput. Soc|pages=208–218|doi=10.1109/ASYNC.1999.761535|isbn=978-0-7695-0031-7}}</ref>, were also first introduced.

Special extensions of the basic underlying Petri net models, to capture asynchrony and interrupts in a compact form, were introduced in Place Chart Nets<ref>{{Cite journal|last=Kishinevsky|first=Michael|last2=Cortadella|first2=Jordi|last3=Kondratyev|first3=Alex|last4=Lavagno|first4=Luciano|last5=Taubin|first5=Alexander|last6=Yakovlev|first6=Alex|date=1997|editor-last=Azéma|editor-first=Pierre|editor2-last=Balbo|editor2-first=Gianfranco|title=Coupling asynchrony and interrupts: Place Chart Nets|url=https://link.springer.com/chapter/10.1007/3-540-63139-9_44|journal=Application and Theory of Petri Nets 1997|series=Lecture Notes in Computer Science|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=328–347|doi=10.1007/3-540-63139-9_44|isbn=978-3-540-69187-7}}</ref>.


== References ==
== References ==
<references />
<references />

==Further reading==
*Newcastle upon Tyne Async Group page http://async.org.uk


[[Category:Automata (computation)]]
[[Category:Automata (computation)]]

Revision as of 13:39, 31 July 2021

Signal Transition Graphs (STGs) are typically used in electronic engineering and computer engineering 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.

VME bus controller. Block-circuit and timing diagrams (a) and the corresponding STGs (b).

More formally, an STG is a type of an interpreted (or labelled) Petri net whose transitions are labelled with the names of changes in the values of signals (cf. signal transitions). 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][7][8][9] which has led to the development of popular software tools for analysis and synthesis of asynchronous control circuits, such as Petrify[10] and Workcraft.[11]

Besides STGs, based on binary signals, there are also Symbolic STGs[12], where signals can be multi-valued.

STGs with timing (delays) information annotation were first introduced in [3], where the ideas of analysis of behaviour of circuits with timing constraints[13], later called Relative Timing[14], were also first introduced.

Special extensions of the basic underlying Petri net models, to capture asynchrony and interrupts in a compact form, were introduced in Place Chart Nets[15].

References

  1. ^ Л. Я. Розенблюм. "Язык сигнальных графов и его использование для моделирования протоколов информационного обмена и апериодических схем," Всесоюзный семинар Моделирование дискретных управляющих и вычислительных систем, стр. 22-24, 1981" (PDF).{{cite web}}: CS1 maint: url-status (link)
  2. ^ 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)
  3. ^ a b 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)
  4. ^ Chu, T.-A. (1986-06-01). "On the models for designing VLSI asynchronous digital systems". Integration. 4 (2): 99–113. doi:10.1016/S0167-9260(86)80002-5. ISSN 0167-9260.
  5. ^ Yakovlev, A.V. (1992). "On limitations and extensions of STG model for designing asynchronous control circuits". Proceedings 1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors. Cambridge, MA, USA: IEEE Comput. Soc. Press: 396–400. doi:10.1109/ICCD.1992.276300. ISBN 978-0-8186-3110-8.
  6. ^ Yakovlev, Alex; Kishinevsky, Michael; Kondratyev, Alex; Lavagno, Luciano (1994). Valette, Robert (ed.). "OR causality: Modelling and hardware implementation". Application and Theory of Petri Nets 1994. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 568–587. doi:10.1007/3-540-58152-9_31. ISBN 978-3-540-48462-2.
  7. ^ Yakovlev, A.V.; Koelmans, A.M.; Lavagno, L. (21/1995). "High-level modeling and design of asynchronous interface logic". IEEE Design & Test of Computers. 12 (1): 32–40. doi:10.1109/54.350688. {{cite journal}}: Check date values in: |date= (help)
  8. ^ Yakovlev, Alexandre; Lavagno, Luciano; Sangiovanni-Vincentelli, Alberto (November 1996). "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.
  9. ^ 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.
  10. ^ "Petrify: Related publications".{{cite web}}: CS1 maint: url-status (link)
  11. ^ "Workcraft".{{cite web}}: CS1 maint: url-status (link)
  12. ^ A. Yakovlev and A. Petrov and L. Rosenblum (1993). "Synthesis of Asynchronous Control Circuits from Symbolic Signal Transition Graphs, Asynchronous Design Methodologies, 1993" (PDF).{{cite web}}: CS1 maint: url-status (link)
  13. ^ Cortadella, Jordi; Kishinevsky, Michael; Kondratyev, Alex; Lavagno, Luciano; Taubin, Alexander; Yakovlev, Alex (1998). "Lazy transition systems: application to timing optimization of asynchronous circuits". Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design - ICCAD '98. San Jose, California, United States: ACM Press: 324–331. doi:10.1145/288548.288633. ISBN 978-1-58113-008-9.
  14. ^ Stevens, K.; Ginosar, R.; Rotem, S. (1999). "Relative timing". Proceedings. Fifth International Symposium on Advanced Research in Asynchronous Circuits and Systems. Barcelona, Spain: IEEE Comput. Soc: 208–218. doi:10.1109/ASYNC.1999.761535. ISBN 978-0-7695-0031-7.
  15. ^ Kishinevsky, Michael; Cortadella, Jordi; Kondratyev, Alex; Lavagno, Luciano; Taubin, Alexander; Yakovlev, Alex (1997). Azéma, Pierre; Balbo, Gianfranco (eds.). "Coupling asynchrony and interrupts: Place Chart Nets". Application and Theory of Petri Nets 1997. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 328–347. doi:10.1007/3-540-63139-9_44. ISBN 978-3-540-69187-7.

Further reading

Retrieved from "https://en.wikipedia.org/w/index.php?title=Signal_transition_graphs&oldid=1036429817"