Signal transition graphs

Last updated

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.

Contents

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. VME-bus-example.png
VME bus controller. Block-diagram and timing diagrams (a) and the corresponding STGs (b). This example originates from.

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]

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]

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]

Related Research Articles

<span class="mw-page-title-main">Petri net</span> Model to describe distributed systems

A Petri net, also known as a place/transition net, is one of several mathematical modeling languages for the description of distributed systems. It is a class of discrete event dynamic system. A Petri net is a directed bipartite graph that has two types of elements: places and transitions. Place elements are depicted as white circles and transition elements are depicted as rectangles. A place can contain any number of tokens, depicted as black circles. A transition is enabled if all places connected to it as inputs contain at least one token. Some sources state that Petri nets were invented in August 1939 by Carl Adam Petri—at the age of 13—for the purpose of describing chemical processes.

AMULET is a series of microprocessors implementing the ARM processor architecture. Developed by the Advanced Processor Technologies group at the Department of Computer Science at the University of Manchester, AMULET is unique amongst ARM implementations in being an asynchronous microprocessor, not making use of a square wave clock signal for data synchronization and movement.

Asynchronous circuit is a sequential digital logic circuit that does not use a global clock circuit or signal generator to synchronize its components. Instead, the components are driven by a handshaking circuit which indicates a completion of a set of instructions. Handshaking works by simple data transfer protocols. Many synchronous circuits were developed in early 1950s as part of bigger asynchronous systems. Asynchronous circuits and theory surrounding is a part of several steps in integrated circuit design, a field of digital electronics engineering.

<span class="mw-page-title-main">C-element</span> Digital logic circuit

In digital computing, the Muller C-element is a small binary logic circuit widely used in design of asynchronous circuits and systems. It outputs 0 when all inputs are 0, it outputs 1 when all inputs are 1, and it retains its output state otherwise. It was specified formally in 1955 by David E. Muller and first used in ILLIAC II computer. In terms of the theory of lattices, the C-element is a semimodular distributive circuit, whose operation in time is described by a Hasse diagram. The C-element is closely related to the rendezvous and join elements, where an input is not allowed to change twice in succession. In some cases, when relations between delays are known, the C-element can be realized as a sum-of-product (SOP) circuit. Earlier techniques for implementing the C-element include Schmitt trigger, Eccles-Jordan flip-flop and last moving point flip-flop.

<span class="mw-page-title-main">Metastability (electronics)</span> Ability of a digital electronic system to remain in unstable equilibrium forever

In electronics, metastability is the ability of a digital electronic system to persist for an unbounded time in an unstable equilibrium or metastable state. In digital logic circuits, a digital signal is required to be within certain voltage or current limits to represent a '0' or '1' logic level for correct circuit operation; if the signal is within a forbidden intermediate range it may cause faulty behavior in logic gates the signal is applied to. In metastable states, the circuit may be unable to settle into a stable '0' or '1' logic level within the time required for proper circuit operation. As a result, the circuit can act in unpredictable ways, and may lead to a system failure, sometimes referred to as a "glitch". Metastability is an instance of the Buridan's ass paradox.

Static timing analysis (STA) is a simulation method of computing the expected timing of a synchronous digital circuit without requiring a simulation of the full circuit.

In digital logic design, an asynchronous circuit is quasi delay-insensitive (QDI) when it operates correctly, independent of gate and wire delay with the weakest exception necessary to be turing-complete.

In electronic design, wire routing, commonly called simply routing, is a step in the design of printed circuit boards (PCBs) and integrated circuits (ICs). It builds on a preceding step, called placement, which determines the location of each active element of an IC or component on a PCB. After placement, the routing step adds wires needed to properly connect the placed components while obeying all design rules for the IC. Together, the placement and routing steps of IC design are known as place and route.

The primary focus of this article is asynchronous control in digital electronic systems. In a synchronous system, operations are coordinated by one, or more, centralized clock signals. An asynchronous system, in contrast, has no global clock. Asynchronous systems do not depend on strict arrival times of signals or messages for reliable operation. Coordination is achieved using event-driven architecture triggered by network packet arrival, changes (transitions) of signals, handshake protocols, and other methods.

The asynchronous array of simple processors (AsAP) architecture comprises a 2-D array of reduced complexity programmable processors with small scratchpad memories interconnected by a reconfigurable mesh network. AsAP was developed by researchers in the VLSI Computation Laboratory (VCL) at the University of California, Davis and achieves high performance and energy-efficiency, while using a relatively small circuit area. It was made in 2006.

Business process discovery (BPD) related to business process management and process mining is a set of techniques that manually or automatically construct a representation of an organisations' current business processes and their major process variations. These techniques use data recorded in the existing organisational methods of work, documentations, and technology systems that run business processes within an organisation. The type of data required for process discovery is called an event log. Any record of data that contains the case id, activity name, and timestamp. Such a record qualifies for an event log and can be used to discover the underlying process model. The event log can contain additional information related to the process, such as the resources executing the activity, the type or nature of the events, or any other relevant details. Process discovery aims to obtain a process model that describes the event log as closely as possible. The process model acts as a graphical representation of the process. The event logs used for discovery could contain noise, irregular information, and inconsistent/incorrect timestamps. Process discovery is challenging due to such noisy event logs and because the event log contains only a part of the actual process hidden behind the system. The discovery algorithms should solely depend on a small percentage of data provided by the event logs to develop the closest possible model to the actual behaviour.

An application-specific instruction set processor (ASIP) is a component used in system on a chip design. The instruction set architecture of an ASIP is tailored to benefit a specific application. This specialization of the core provides a tradeoff between the flexibility of a general purpose central processing unit (CPU) and the performance of an application-specific integrated circuit (ASIC).

John Patrick Hayes is an Irish-American computer scientist and electrical engineer, the Claude E. Shannon Chair of Engineering Science at the University of Michigan. He supervised over 35 doctoral students, coauthored seven books and over 340 peer-reviewed publications. His Erdös number is 2.

Stochastic Petri nets are a form of Petri net where the transitions fire after a probabilistic delay determined by a random variable.

Approximate computing is an emerging paradigm for energy-efficient and/or high-performance design. It includes a plethora of computation techniques that return a possibly inaccurate result rather than a guaranteed accurate result, and that can be used for applications where an approximate result is sufficient for its purpose. One example of such situation is for a search engine where no exact answer may exist for a certain search query and hence, many answers may be acceptable. Similarly, occasional dropping of some frames in a video application can go undetected due to perceptual limitations of humans. Approximate computing is based on the observation that in many scenarios, although performing exact computation requires large amount of resources, allowing bounded approximation can provide disproportionate gains in performance and energy, while still achieving acceptable result accuracy. For example, in k-means clustering algorithm, allowing only 5% loss in classification accuracy can provide 50 times energy saving compared to the fully accurate classification.

Vishwani D. Agrawal is the James J. Danaher Professor of Electrical and Computer Engineering at Auburn University. He has over four decades of industry and university experience, including working at Bell Labs, Murray Hill, NJ, Rutgers University, TRW and IIT, Delhi. He is well known as a cofounder and long-term mentor of the International Conference on VLSI Design held annually in India since 1985.

<span class="mw-page-title-main">Sum coloring</span>

In graph theory, a sum coloring of a graph is a labeling of its vertices by positive integers, with no two adjacent vertices having equal labels, that minimizes the sum of the labels. The minimum sum that can be achieved is called the chromatic sum of the graph. Chromatic sums and sum coloring were introduced by Supowit in 1987 using non-graph-theoretic terminology, and first studied in graph theoretic terms by Ewa Kubicka in her 1989 doctoral thesis.

An event camera, also known as a neuromorphic camera, silicon retina or dynamic vision sensor, is an imaging sensor that responds to local changes in brightness. Event cameras do not capture images using a shutter as conventional (frame) cameras do. Instead, each pixel inside an event camera operates independently and asynchronously, reporting changes in brightness as they occur, and staying silent otherwise.

Analysis of Petri nets can be performed by means of constructing either reachable state spaces or via the process of graph-based unfolding. The prefix of a Petri net unfolding, which is an acyclic Petri net graph, contains the same information about the properties of the Petri net as the reachability graph, plus it contains information about sequence, concurrency and conflict relations between Petri net transitions and Petri net places. The advantages of the use of unfolding in practice are typically associated with the fact that the unfolding prefix is much more compact than the reachability graph of the Petri net being analysed.

<span class="mw-page-title-main">Igor L. Markov</span> American computer scientist and engineer

Igor Leonidovich Markov is an American professor, computer scientist and engineer. Markov is known for mathematical and algorithmic results in quantum computation, work on limits of computation, research on algorithms for optimizing integrated circuits and on electronic design automation, as well as artificial intelligence. Additionally, Markov is a California non-profit executive responsible for aid to Ukraine worth tens of millions dollars.

References

  1. 1 2 "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" (PDF).
  2. ↑ Л. Я. Розенблюм. "Язык сигнальных графов и его использование для моделирования протоколов информационного обмена и апериодических схем" (PDF). Всесоюзный семинар Моделирование дискретных управляющих и вычислительных систем, стр. 22-24, 1981.
  3. 1 2 Yakovlev, Alex. "Design and Implementation of Asynchronous Communication Protocols in Systems Interfaces" (Проектирование и реализация протоколов асинхронного обмена информацией в межмодульном интерфейсе), PhD thesis (in Russian), 1982".
  4. 1 2 Rosenblum, L.Ya.; Yakovlev, A.V. "Signal Graphs: from Self-timed to Timed ones" (PDF). Proceedings of International Workshop on Timed Petri Nets, Torino, Italy, July 1985, IEEE CS Press, Pp. 199-207.
  5. 1 2 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.
  6. 1 2 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. S2CID   47325879.
  8. ↑ Yakovlev, Alex; Kishinevsky, Michael; Kondratyev, Alex; Lavagno, Luciano (1994). "OR causality: Modelling and hardware implementation". In Valette, Robert (ed.). Application and Theory of Petri Nets 1994. Lecture Notes in Computer Science. Vol. 815. Berlin, Heidelberg: Springer. pp. 568–587. doi:10.1007/3-540-58152-9_31. ISBN   978-3-540-48462-2.
  9. 1 2 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.
  10. ↑ 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. S2CID   264205433.
  11. 1 2 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.
  12. ↑ Lavagno, Luciano; Sangiovanni-Vincentelli, Alberto (1993). Algorithms for Synthesis and Testing of Asynchronous Circuits. doi:10.1007/978-1-4615-3212-5. ISBN   978-1-4613-6410-8.
  13. 1 2 "Petrify: Related publications".
  14. 1 2 3 4 5 "Workcraft".
  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" (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". Integration. 21 (3): 143–170. doi:10.1016/S0167-9260(96)00010-7. ISSN   0167-9260.
  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. S2CID   27216794.
  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. S2CID   133188921.
  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. S2CID   148566115.
  20. ↑ Mileiko, Sergey (2020). "Power-compute co-design for robust pervasive IoT applications, PhD Thesis, Newcastle University" (PDF).
  21. ↑ Li, Danhui (2021). "Analysis and Design of Switched-Capacitor DC-DC Converters with Discrete Event Models, PhD Thesis, Newcastle University" (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" (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. S2CID   61935560.
  24. ↑ Cortadella, Jordi; Kishinevsky, Michael; Kondratyev, Alex; Lavagno, Luciano; Taubin, Alexander; Yakovlev, Alex (1998). "Lazy transition systems". 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. hdl: 2117/133832 . ISBN   978-1-58113-008-9. S2CID   12302564.
  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. S2CID   195352018.
  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 (eds.). Application and Theory of Petri Nets 1997. Lecture Notes in Computer Science. Vol. 1248. Berlin, Heidelberg: Springer. pp. 328–347. doi:10.1007/3-540-63139-9_44. ISBN   978-3-540-69187-7.
  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. hdl: 2117/125784 . S2CID   2128502.
  28. ↑ Badouel, Eric; Darondeau, Philippe (1998). "Theory of regions". In Reisig, Wolfgang; Rozenberg, Grzegorz (eds.). 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". Formal Methods in System Design. 12 (1): 39–71. doi:10.1023/A:1008649930696. ISSN   1572-8102. S2CID   14497213.
  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. S2CID   26434994.
  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". Formal Methods in System Design. 9 (3): 189–233. doi:10.1007/BF00122082. ISSN   1572-8102. S2CID   7456859.
  33. ↑ Starodubtsev, N.; Yakovlev, A.; Petrov, S. "Use of VHDL Environment for Interactive Synthesis of Asynchronous Circuits" (PDF). Newcaslte University.
  34. ↑ Blunno, Ivan; Lavagno, Luciano (2000), Yakovlev, Alex; Gomes, Luis; Lavagno, Luciano (eds.), "Deriving Signal Transition Graphs from Behavioral Verilog HDL", 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 , 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". IEE Proceedings - Computers and Digital Techniques. 151 (3): 209–220. doi:10.1049/ip-cdt:20040525. ISSN   1359-7027. S2CID   62708582.
  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. S2CID   9219686.
  37. ↑ "Asynchronous High Level Synthesis Tool (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. hdl: 2117/114897 . ISBN   978-1-5386-2749-5. S2CID   5836204.
  39. ↑ Nowick, Steve. "Automatic synthesis of burst-mode asynchronous controllers (PhD Thesis)" (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. S2CID   236150734.
  41. 1 2 Khomenko, Victor (2003). Model Checking Based on Prefixes of Petri Net Unfoldings, PhD thesis (PDF). Newcastle University.
  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 (eds.). 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. S2CID   17410812.
  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 (eds.). 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.
  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. S2CID   32318274.
  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. hdl: 2117/125782 .
  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. hdl: 2117/129959 . ISBN   978-0-8186-7922-3. S2CID   7883418.
  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. S2CID   62773126.
  51. ↑ Madalinski, A.; Bystrov, A.; Khomenko, V.; Yakovlev, A. (2003). "Visualisation and resolution of encoding conflicts in asynchronous circuit design". IEE Proceedings - Computers and Digital Techniques. 150 (5): 285. doi: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. hdl: 2117/133434 . ISBN   978-0-7695-1071-2. S2CID   16280258.
  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. S2CID   10434495.
  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. S2CID   10431976.
  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. S2CID   39407927.
  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. S2CID   704120.
  57. ↑ Khomenko, Victor; Schaefer, Mark; Vogler, Walter; Wollowski, Ralf (2009-10-01). "STG decomposition strategies in combination with unfolding". Acta Informatica. 46 (6): 433–474. doi:10.1007/s00236-009-0102-y. ISSN   1432-0525. S2CID   9955410.
  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. S2CID   6811851.
  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. hdl: 2117/128605 . ISBN   978-0-8186-6210-2. S2CID   14524732.
  60. ↑ Low, K-S.; Yakovlev, A. (1995). "Token Ring Arbiters: An Exercise in Asynchronous Logic Design with Petri-Nets" (PDF). Newcastle University.
  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. S2CID   57192066.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.