Signal transition graphs

From HandWiki
Revision as of 15:57, 6 February 2024 by Smart bot editor (talk | contribs) (correction)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

Main definitions and applications

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. In that way, STGs help to formalise the description of a circuit typically represented by timing diagrams, sometimes also called waveforms. The latter are widely used by electronic engineers.

VME bus controller. Block-diagram and timing diagrams (a) and the corresponding STGs (b). This example originates from.[1]

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.[2] They were studied more formally and applied to the design of asynchronous interfaces by Alex Yakovlev in 1982, in his PhD thesis [3] (in Russian). They were later presented in English in 1985, in two independent sources, one by Rosenblum and Yakovlev in[4] and the other by Tam-Anh Chu in [5] (an earlier version was presented at ICCD'85). Since then, STGs have been studied extensively in theory and practice,[6][7][8][9][10][11][12] which has led to the development of popular software tools for analysis and synthesis of asynchronous control circuits, such as Petrify[13] (chief developer: Jordi Cortadella) and Workcraft (a toolkit from Newcastle University).[14]

Amongst the various examples of using STGs in designing asynchronous circuits, the most well known are those in the domain of asynchronous interfaces, controllers, arbiters and analog-mixed signal circuits, cf.,[15][9][16][17][18][19] most recently STGs have been extended to model causal behaviour involving causality mediated by capacitive coupling, such as those used in switched capacitor converters (SCCs).[20][21]

Extensions and Related Models

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

STGs with timing (delays) information annotation were first introduced in,[4] and later in,[23] where ideas of analysis of behaviour of circuits with timing constraints,[24] later called Relative Timing,[25] 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.[26] An important connection between state-based models of asynchronous circuits and Petri net-based models (inc. STGs) has been established in[27] using Theory of Regions (cf.[28]). Theory of regions was used to derive an STG model and its circuit implementation in[29] for Counterflow Pipeline Processor due to Robert Sproull, Ivan Sutherland and Charles Molnar.[30]

One of the models closely related to STGs is Change Diagrams, proposed by Michael Kishinevsky, Alex Kondratyev, Alexander Taubin and Victor Varshavsky in.[31] Change Diagrams have the advantages of being able to model both AND and OR causality in a compact way. But they lack descriptive power in terms of choice. The comparison between Petri nets and change diagrams in terms of their descriptive power and their unification in the form of Causal Logic Nets has been presented in.[32]

Links with Hardware Description Languages

STGs have been interfaced with various HDLs, see for example links with VHDL[33] (1996) and Verilog[34] (2000) with the aim to support asynchronous design. Placed into the synthesis flow from VHDL, STGs and Petri nets have been shown instrumental,[35] and likewise with Verilog,[36] where a tool VERISYN was developed.[37]

More recently STGs have been connected with notations that are believed to be easier for practical hardware designers, hence the emergence of the model of waveform-transition graphs (WTG).[38] Likewise, realising that the model of finite state machine (FSM) can be easier for designers to handle than, for example, Petri nets or STGs, a link with Burst Mode FSMs[39] as a front-end has been developed.[40]

Analysis Methods

At the moment, arguably the most efficient methods for analysis and synthesis of asynchronous circuits are based on Petri net unfoldings - they were studied by Victor Khomenko in his PhD thesis.[41] They are implemented under Workcraft.[14]

Performance analysis of certain subclasses of Petri net models of asynchronous circuits has been investigated by Aiguo Xie and Peter Beerel in.[42]

Asynchronous Circuit Synthesis

Various problems in the synthesis of asynchronous circuits from STG specification have been investigated. One of the ways for their classification is based on the analysis approaches used to represent the state space of the STG specification, such as explicit state spaces, unfolding of the underlying Petri net, structural analysis of Petri nets and direct mapping (syntax-direct translation) of STGs. These approaches are usually linked with the complexity of the algorithms of synthesis and, hence, run-time of the tools. On the other hand, some of these techniques impose certain constraints on the class of the Petri nets. For example, explicit state space based methods typically work for an arbitrary Petri net type, whereas some structural methods require that the underlying Petri net is a marked graph or a free-choice net.

Complete State Coding problem

One of the key well-known problems in the synthesis of circuit implementations is that of complete state coding (CSC). To tackle this problem various methods have been developed.[6][43][44][11] A particularly original way to analyse for CSC satisfaction is based on the notion of coupledness relation or, equivalently, lock relation, developed independently by Alex Yakovlev[3][1] and Peter Vanbekbergen.[45][46] Another method exploited theory of regions which connects elements of Petri nets with regions of states in state graphs.[47]

Synthesis methods for CSC detection and resolution based on partial orders and Petri net unfoldings have been developed by Alex Semenov[48][49] and Victor Khomenko.[41][50] These methods have helped to formalise and implement a method for effective visualization of CSC problems based on CSC cores,[51] implemented in Workcraft.[14]

Structural encoding methods for STG-based synthesis have been developed by Josep Carmona.[52]

Synthesis in restricted logic bases

An important problem in synthesis of speed-independent (or equivalently quasi-Delay-Insensitive - QDI) circuits is synthesis within a restricted logical basis, for example, using ONLY restricted basis logic gates such as AND and OR - see, for example, the work of Alex Yakovlev,[53] where the condition of E(excitation)-persistency was introduced to ensure hazard-freedom in the implementation consisting of two-level Sum-of-Products (SOP) logic for excitation functions and SR-latches for the main output signals of a given STG specification. Later, the work Alex Kondratyev et al [54] generalised this condition in the notion of monotonic cover, which found its realisation in software tools.[13][14] More challenging is the problem of synthesis in negative gate bases, NAND and NOR. Several methods have been developed for that, mostly led by Nikolay Starodoubtsev.[55][56]

Decomposition of STGs for synthesis

The problem of scalability of synthesis for large size STGs, and needs to alleviate state space explosion have been tackled in methods based on contraction of STGs with respect to structural properties of the underlying Petri net - such as ways of partitioning a free-choice Petri net into state machines or marked graphs[5] - as well as fan-in signal subsets (trigger events for a signal).[57]

Another approach to deal with scalability is via a direct mapping of STGs to asynchronous circuits that has been investigated by Danil Sokolov.[58]

Synthesis from STGs with arbitration

A particularly challenging problem is to automatically synthesise asynchronous circuits for arbiters, as their STG specification would contain behavioural conflicts in their underlying Petri nets. Behavioural conflicts imply existence of transitions that are non-persistent. For usual, logic based implementation of such STGs, the circuit would be prone to hazards. Special techniques such as semi-automated insertion of mutex signal transitions, preserving the original specification, have been developed[59][60] and implemented in Workcraft.[14][61]

References

  1. ↑ 1.0 1.1 "A. Yakovlev and A. Petrov. Petri nets and parallel bus controller design. Proc. of 11th Int. Conf. on Applications and Theory of Petri Nets, Paris, France, June 1990". https://www.staff.ncl.ac.uk/alex.yakovlev/home.formal/AY-AP-PN90.pdf. 
  2. ↑ Л. Я. Розенблюм. "Язык сигнальных графов и его использование для моделирования протоколов информационного обмена и апериодических схем". Всесоюзный семинар Моделирование дискретных управляющих и вычислительных систем, стр. 22-24, 1981. https://www.ee.bgu.ac.il/~kushnero/asynchronous/Varshavsky%20and%20Co/Rosenblum/Rosenblum_1981.pdf. 
  3. ↑ 3.0 3.1 Yakovlev, Alex. "Design and Implementation of Asynchronous Communication Protocols in Systems Interfaces" (Проектирование и реализация протоколов асинхронного обмена информацией в межмодульном интерфейсе), PhD thesis (in Russian), 1982". http://async.org.uk/ay-thesis/. 
  4. ↑ 4.0 4.1 Rosenblum, L.Ya.; 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.. https://www.staff.ncl.ac.uk/alex.yakovlev/home.formal/LR-AY-TPN85.pdf. 
  5. ↑ 5.0 5.1 Chu, T.-A. (1986-06-01). "On the models for designing VLSI asynchronous digital systems" (in en). Integration 4 (2): 99–113. doi:10.1016/S0167-9260(86)80002-5. ISSN 0167-9260. https://www.sciencedirect.com/science/article/abs/pii/S0167926086800025. 
  6. ↑ 6.0 6.1 Chu, Tam-Anh (1987). Synthesis of self-timed VLSI circuits from graph-theoretic specifications (Thesis thesis). Massachusetts Institute of Technology. hdl:1721.1/14794.
  7. ↑ 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. pp. 396–400. doi:10.1109/ICCD.1992.276300. ISBN 978-0-8186-3110-8. https://ieeexplore.ieee.org/document/276300. 
  8. ↑ Yakovlev, Alex; Kishinevsky, Michael; Kondratyev, Alex; Lavagno, Luciano (1994). "OR causality: Modelling and hardware implementation". in Valette, Robert (in en). Application and Theory of Petri Nets 1994. Lecture Notes in Computer Science. 815. Berlin, Heidelberg: Springer. pp. 568–587. doi:10.1007/3-540-58152-9_31. ISBN 978-3-540-48462-2. https://link.springer.com/chapter/10.1007/3-540-58152-9_31. 
  9. ↑ 9.0 9.1 Yakovlev, A.V.; Koelmans, A.M.; Lavagno, L. (1995). "High-level modeling and design of asynchronous interface logic (21/1995)". IEEE Design & Test of Computers 12 (1): 32–40. doi:10.1109/54.350688. https://ieeexplore.ieee.org/document/350688. 
  10. ↑ Yakovlev, Alexandre; Lavagno, Luciano; Sangiovanni-Vincentelli, Alberto (November 1996). "A unified signal transition graph model for asynchronous control circuit synthesis" (in en). Formal Methods in System Design 9 (3): 139–188. doi:10.1007/BF00122081. ISSN 0925-9856. http://link.springer.com/10.1007/BF00122081. 
  11. ↑ 11.0 11.1 Cortadella, J.; Kishinevsky, M.; Kondratyev, A.; Lavagno, L.; Yakovlev, A. (2002) (in en). Logic Synthesis for Asynchronous Controllers and Interfaces. Springer Series in Advanced Microelectronics. 8. Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/978-3-642-55989-1. ISBN 978-3-642-62776-7. http://link.springer.com/10.1007/978-3-642-55989-1. 
  12. ↑ Lavagno, Luciano; Sangiovanni-Vincentelli, Alberto (1993) (in en-gb). Algorithms for Synthesis and Testing of Asynchronous Circuits. doi:10.1007/978-1-4615-3212-5. ISBN 978-1-4613-6410-8. 
  13. ↑ 13.0 13.1 "Petrify: Related publications". https://www.cs.upc.edu/~jordicf/petrify/refs/. 
  14. ↑ 14.0 14.1 14.2 14.3 14.4 "Workcraft". https://workcraft.org/. 
  15. ↑ Yakovlev, Alex. "Designing arbiters using Petri nets. Proceedings of the 1995 Israel Workshop on Asynchronous VLSI, Nof Genossar, Israel, March 1995, VLSI Systems Research Center, Technion, Haifa, Israel, pp. 178-201". https://www.staff.ncl.ac.uk/alex.yakovlev/home.formal/DesignArbitersUsingPNs-IsraelAsync1995.pdf. 
  16. ↑ Yakovlev, A.V.; Koelmans, A.M.; Semenov, A.; Kinniment, D.J. (1996-12-01). "Modelling, analysis and synthesis of asynchronous control circuits using Petri nets" (in en). Integration 21 (3): 143–170. doi:10.1016/S0167-9260(96)00010-7. ISSN 0167-9260. https://www.sciencedirect.com/science/article/abs/pii/S0167926096000107. 
  17. ↑ Yakovlev, A.; Furber, S.; Krenz, R.; Bystrov, A. (July 2004). "Design and analysis of a self-timed duplex communication system". IEEE Transactions on Computers 53 (7): 798–814. doi:10.1109/TC.2004.26. ISSN 1557-9956. https://ieeexplore.ieee.org/document/1321042. 
  18. ↑ Sokolov, Danil; Khomenko, Victor; Mokhov, Andrey; Dubikhin, Vladimir; Lloyd, David; Yakovlev, Alex (May 2020). "Automating the Design of Asynchronous Logic Control for AMS Electronics". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 39 (5): 952–965. doi:10.1109/TCAD.2019.2907905. ISSN 1937-4151. https://ieeexplore.ieee.org/document/8675314. 
  19. ↑ Golubcovs, Stanislavs; Mokhov, Andrey; Bystrov, Alex; Sokolov, Danil; Yakovlev, Alex (June 2019). "Generalised Asynchronous Arbiter". 2019 19th International Conference on Application of Concurrency to System Design (ACSD). pp. 3–12. doi:10.1109/ACSD.2019.00005. ISBN 978-1-7281-3843-5. https://ieeexplore.ieee.org/document/8843647. 
  20. ↑ Mileiko, Sergey (2020). "Power-compute co-design for robust pervasive IoT applications, PhD Thesis, Newcastle University.". http://async.org.uk/tech-reports/NCL-EEE-MICRO-TR-2020-218.pdf. 
  21. ↑ Li, Danhui (2021). "Analysis and Design of Switched-Capacitor DC-DC Converters with Discrete Event Models, PhD Thesis, Newcastle University". http://async.org.uk/tech-reports/NCL-EEE-MICRO-TR-2021-219.pdf. 
  22. ↑ A. Yakovlev and A. Petrov and L. Rosenblum (1993). "Synthesis of Asynchronous Control Circuits from Symbolic Signal Transition Graphs, Asynchronous Design Methodologies, 1993". https://www.staff.ncl.ac.uk/alex.yakovlev/home.formal/async-des-methods-Manchester-1993-SymbSTG-yakovlev.pdf. 
  23. ↑ Vanbekbergen, P.; Goossens, G.; De Man, H. (1992). "Specification and analysis of timing constraints in signal transition graphs". [1992] Proceedings the European Conference on Design Automation. Brussels, Belgium: IEEE Comput. Soc. Press. pp. 302–306. doi:10.1109/EDAC.1992.205943. ISBN 978-0-8186-2645-6. https://ieeexplore.ieee.org/document/205943. 
  24. ↑ Cortadella, Jordi; Kishinevsky, Michael; Kondratyev, Alex; Lavagno, Luciano; Taubin, Alexander; Yakovlev, Alex (1998). "Lazy transition systems" (in en). Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design - ICCAD '98. San Jose, California, United States: ACM Press. pp. 324–331. doi:10.1145/288548.288633. ISBN 978-1-58113-008-9. http://portal.acm.org/citation.cfm?doid=288548.288633. 
  25. ↑ 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. pp. 208–218. doi:10.1109/ASYNC.1999.761535. ISBN 978-0-7695-0031-7. https://ieeexplore.ieee.org/document/761535. 
  26. ↑ Kishinevsky, Michael; Cortadella, Jordi; Kondratyev, Alex; Lavagno, Luciano; Taubin, Alexander; Yakovlev, Alex (1997). "Coupling asynchrony and interrupts: Place Chart Nets". in Azéma, Pierre; Balbo, Gianfranco (in en). Application and Theory of Petri Nets 1997. Lecture Notes in Computer Science. 1248. Berlin, Heidelberg: Springer. pp. 328–347. doi:10.1007/3-540-63139-9_44. ISBN 978-3-540-69187-7. https://link.springer.com/chapter/10.1007/3-540-63139-9_44. 
  27. ↑ Cortadella, J.; Kishinevsky, M.; Lavagno, L.; Yakovlev, A. (August 1998). "Deriving Petri nets from finite transition systems". IEEE Transactions on Computers 47 (8): 859–882. doi:10.1109/12.707587. https://ieeexplore.ieee.org/document/707587. 
  28. ↑ Badouel, Eric; Darondeau, Philippe (1998). "Theory of regions". in Reisig, Wolfgang; Rozenberg, Grzegorz (in en). Lectures on Petri Nets I: Basic Models. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. pp. 529–586. doi:10.1007/3-540-65306-6_22. ISBN 978-3-540-49442-3. 
  29. ↑ Yakovlev, Alexandre (1998-01-01). "Designing Control Logic for Counterflow Pipeline Processor Using Petri Nets" (in en). Formal Methods in System Design 12 (1): 39–71. doi:10.1023/A:1008649930696. ISSN 1572-8102. 
  30. ↑ Sproull, R.F.; Sutherland, I.E.; Molnar, C.E. (Autumn 1994). "The counterflow pipeline processor architecture". IEEE Design & Test of Computers 11 (3): 48–. doi:10.1109/MDT.1994.303847. ISSN 1558-1918. https://ieeexplore.ieee.org/document/303847. 
  31. ↑ M. A. Kishinevskiĭ (1994). Concurrent hardware: the theory and practice of self-timed design. Chichester: Wiley. ISBN 0-471-93536-0. OCLC 28889359. 
  32. ↑ Yakovlev, Alexandre; Kishinevsky, Michael; Kondratyev, Alex; Lavagno, Luciano; Pietkiewicz-Koutny, Marta (1996-11-01). "On the models for asynchronous circuit behaviour with OR causality" (in en). Formal Methods in System Design 9 (3): 189–233. doi:10.1007/BF00122082. ISSN 1572-8102. 
  33. ↑ Starodubtsev, N.; Yakovlev, A.. "Use of VHDL Environment for Interactive Synthesis of Asynchronous Circuits". https://eprints.ncl.ac.uk/file_store/production/160502/C2EDAB40-31DB-4A53-94BA-4C8F93BB8372.pdf. 
  34. ↑ Blunno, Ivan; Lavagno, Luciano (2000), Yakovlev, Alex; Gomes, Luis; Lavagno, Luciano, eds., "Deriving Signal Transition Graphs from Behavioral Verilog HDL" (in en), Hardware Design and Petri Nets (Boston, MA: Springer US): pp. 151–170, doi:10.1007/978-1-4757-3143-9_8, ISBN 978-1-4419-4969-1, http://link.springer.com/10.1007/978-1-4757-3143-9_8, retrieved 2022-05-30 
  35. ↑ Shang, D.; Burns, F.; Koelmans, A.; Yakovlev, A.; Xia, F. (2004-05-01). "Asynchronous system synthesis based on direct mapping using VHDL and Petri nets" (in en). IEE Proceedings - Computers and Digital Techniques 151 (3): 209–220. doi:10.1049/ip-cdt:20040525. ISSN 1359-7027. https://digital-library.theiet.org/content/journals/10.1049/ip-cdt_20040525. 
  36. ↑ Burns, F.; Shang, D.; Koelmans, A.; Yakovlev, A. (2004). "An asynchronous synthesis toolset using Verilog". Proceedings Design, Automation and Test in Europe Conference and Exhibition. Paris, France: IEEE Comput. Soc. pp. 724–725. doi:10.1109/DATE.2004.1268948. ISBN 978-0-7695-2085-8. https://ieeexplore.ieee.org/document/1268948. 
  37. ↑ "Asynchronous High Level Synthesis Tool (VERISYN)". http://async.org.uk/besst/verisyn/. 
  38. ↑ Cortadella, Jordi; Moreno, Alberto; Sokolov, Danil; Yakovlev, Alex; Lloyd, David (2017). "Waveform Transition Graphs: A Designer-Friendly Formalism for Asynchronous Behaviours". 2017 23rd IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC). IEEE. pp. 73–74. doi:10.1109/ASYNC.2017.24. ISBN 978-1-5386-2749-5. https://ieeexplore.ieee.org/document/8097387. 
  39. ↑ Nowick, Steve. "Automatic synthesis of burst-mode asynchronous controllers (PhD Thesis)". http://i.stanford.edu/pub/cstr/reports/csl/tr/95/686/CSL-TR-95-686.pdf. 
  40. ↑ Chan, Alex; Sokolov, Danil; Khomenko, Victor; Lloyd, David; Yakovlev, Alex (2021-02-01). "Synthesis of SI Circuits from Burst-Mode Specifications". 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE). Grenoble, France: IEEE. pp. 366–369. doi:10.23919/DATE51398.2021.9474117. ISBN 978-3-9819263-5-4. https://ieeexplore.ieee.org/document/9474117. 
  41. ↑ 41.0 41.1 Khomenko, Victor (2003). Model Checking Based on Prefixes of Petri Net Unfoldings, PhD thesis. Newcastle University. http://homepages.cs.ncl.ac.uk/victor.khomenko/home.formal/papers/thesis.pdf. 
  42. ↑ Xie, Aiguo; Beerel, Peter A. (2000). "Performance Analysis of Asynchronous Circuits and Systems Using Stochastic Timed Petri Nets". in Yakovlev, Alex; Gomes, Luis; Lavagno, Luciano (in en). Hardware Design and Petri Nets. Boston, MA: Springer US. pp. 239–268. doi:10.1007/978-1-4757-3143-9_13. ISBN 978-1-4757-3143-9. 
  43. ↑ Lavagno, L.; Moon, C.W.; Brayton, R.K.; Sangiovanni-Vincentelli, A. (1992). "Solving the state assignment problem for signal transition graphs". [1992] Proceedings 29th ACM/IEEE Design Automation Conference. Anaheim, CA, USA: IEEE Comput. Soc. Press. pp. 568–572. doi:10.1109/DAC.1992.227821. ISBN 978-0-8186-2822-1. https://ieeexplore.ieee.org/document/227821. 
  44. ↑ Vanbekbergen, Peter; Lin, Bill; Goossens, Gert; De Man, Hugo (1994). "A Generalized State Assignment Theory for Transformations on Signal Transition Graphs". in Meng, Teresa H.; Malik, Sharad (in en). Asynchronous Circuit Design for VLSI Signal Processing. Boston, MA: Springer US. pp. 101–115. doi:10.1007/978-1-4615-2794-7_8. ISBN 978-1-4615-2794-7. 
  45. ↑ Vanbekbergen, P.; Catthoor, F.; Goossens, G.; De Man, H. (1990). "Optimized synthesis of asynchronous control circuits from graph-theoretic specifications". 1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers. Santa Clara, CA, USA: IEEE Comput. Soc. Press. pp. 184–187. doi:10.1109/ICCAD.1990.129875. ISBN 978-0-8186-2055-3. https://ieeexplore.ieee.org/document/129875. 
  46. ↑ Vanbekbergen, P.; Goossens, G.; Catthoor, F.; De Man, H.J. (November 1992). "Optimized synthesis of asynchronous control circuits from graph-theoretic specifications". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 11 (11): 1426–1438. doi:10.1109/43.177405. https://ieeexplore.ieee.org/document/177405. 
  47. ↑ Cortadella, J.; Kishinevsky, M.; Kondratyev, A.; Lavagno, L.; Yakovlev, A. (August 1997). "A region-based theory for state assignment in speed-independent circuits". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 16 (8): 793–812. doi:10.1109/43.644602. https://ieeexplore.ieee.org/document/644602. 
  48. ↑ Semenov, A.; Yakovlev, A.; Pastor, E.; Pena, M.A.; Cortadella, J.; Lavagno, L. (1997). "Partial order based approach to synthesis of speed-independent circuits". Proceedings Third International Symposium on Advanced Research in Asynchronous Circuits and Systems. Eindhoven, Netherlands: IEEE Comput. Soc. Press. pp. 254–265. doi:10.1109/ASYNC.1997.587179. ISBN 978-0-8186-7922-3. https://ieeexplore.ieee.org/document/587179. 
  49. ↑ Semenov., Alexei (1997). Verification and synthesis of asynchronous control circuits using petri net unfoldings (Thesis thesis). Newcastle University.
  50. ↑ Khomenko, Victor (July 2009). "Efficient Automatic Resolution of Encoding Conflicts Using STG Unfoldings". IEEE Transactions on Very Large Scale Integration (VLSI) Systems 17 (7): 855–868. doi:10.1109/TVLSI.2008.2012156. ISSN 1063-8210. https://ieeexplore.ieee.org/document/5089937. 
  51. ↑ Madalinski, A.; Bystrov, A.; Khomenko, V.; Yakovlev, A. (2003). "Visualisation and resolution of encoding conflicts in asynchronous circuit design" (in en). IEE Proceedings - Computers and Digital Techniques 150 (5): 285. doi:10.1049/ip-cdt:20030831. https://digital-library.theiet.org/content/journals/10.1049/ip-cdt_20030831. 
  52. ↑ Carmona, J.; Cortadella, J.; Pastor, E. (2001). "A structural encoding technique for the synthesis of asynchronous circuits". Proceedings Second International Conference on Application of Concurrency to System Design. Newcastle upon Tyne, UK: IEEE Comput. Soc. pp. 157–166. doi:10.1109/CSD.2001.981773. ISBN 978-0-7695-1071-2. https://ieeexplore.ieee.org/document/981773. 
  53. ↑ Yakovlev, A.V. (1993). "Synthesis of Hazard-free Asynchronous Circuits from Generalized Signal-Transition Graphs". The Sixth International Conference on VLSI Design. Bombay, India: IEEE. pp. 21–24. doi:10.1109/ICVD.1993.669629. ISBN 978-0-8186-3180-1. https://ieeexplore.ieee.org/document/669629. 
  54. ↑ Kondratyev, Alex; Kishinevsky, Michael; Lin, Bill; Vanbekbergen, Peter; Yakovlev, Alex (1994-06-06). "Basic gate implementation of speed-independent circuits". Proceedings of the 31st annual conference on Design automation conference - DAC '94. New York, NY, USA: Association for Computing Machinery. pp. 56–62. doi:10.1145/196244.196275. ISBN 978-0-89791-653-0. 
  55. ↑ Starodoubtsev, N.; Bystrov, S.; Goncharov, M.; Klotchkov, I.; Smirnov, A. (2001). "Towards synthesis of monotonic asynchronous circuits from signal transition graphs". Proceedings Second International Conference on Application of Concurrency to System Design. Newcastle upon Tyne, UK: IEEE Comput. Soc. pp. 179–188. doi:10.1109/CSD.2001.981775. ISBN 978-0-7695-1071-2. https://ieeexplore.ieee.org/document/981775. 
  56. ↑ Starodoubtsev, N.; Bystrov, S.; Yakovlev, A. (2003). "Monotonic circuits with complete acknowledgement". Ninth International Symposium on Asynchronous Circuits and Systems, 2003. Proceedings.. Vancouver, BC, Canada: IEEE Comput. Soc. pp. 98–108. doi:10.1109/ASYNC.2003.1199170. ISBN 978-0-7695-1898-5. https://ieeexplore.ieee.org/document/1199170. 
  57. ↑ Khomenko, Victor; Schaefer, Mark; Vogler, Walter; Wollowski, Ralf (2009-10-01). "STG decomposition strategies in combination with unfolding" (in en). Acta Informatica 46 (6): 433–474. doi:10.1007/s00236-009-0102-y. ISSN 1432-0525. 
  58. ↑ Sokolov, Danil; Bystrov, Alexander; Yakovlev, Alex (June 2007). "Direct Mapping of Low-Latency Asynchronous Controllers From STGs". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 26 (6): 993–1009. doi:10.1109/TCAD.2006.884416. ISSN 0278-0070. https://ieeexplore.ieee.org/document/4167995. 
  59. ↑ Cortadella, J.; Lavagno, L.; Vanbekbergen, P.; Yakovlev, A. (1994). "Designing asynchronous circuits from behavioural specifications with internal conflicts". Proceedings of 1994 IEEE Symposium on Advanced Research in Asynchronous Circuits and Systems. Salt Lake City, UT, USA: IEEE Comput. Soc. Press. pp. 106–115. doi:10.1109/ASYNC.1994.656296. ISBN 978-0-8186-6210-2. https://ieeexplore.ieee.org/document/656296. 
  60. ↑ Low, K-S.; Yakovlev, A. (1995). "Token Ring Arbiters: An Exercise in Asynchronous Logic Design with Petri-Nets". https://eprints.ncl.ac.uk/file_store/production/160499/E8A2B49F-411C-4B9A-BB2E-21169D582D9A.pdf. 
  61. ↑ Sokolov, Danil; Khomenko, Victor; Yakovlev, Alex; Lloyd, David (May 2018). "Design and Verification of Speed-Independent Circuits with Arbitration in Workcraft". 2018 24th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC). pp. 30–31. doi:10.1109/ASYNC.2018.00017. ISBN 978-1-5386-5883-3. https://ieeexplore.ieee.org/document/8589980. 

Further reading



Retrieved from "https://handwiki.org/wiki/index.php?title=Signal_transition_graphs&oldid=3364373"