Signal transition graphs

From Wikipedia, the free encyclopedia

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. 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]

In order to capture concurrency and choice in compact form, a model called Conditional Partial Order Graph (CPOG) was proposed by Andrey Mokhov in his PhD thesis and published in.^[33] It has advantages over widely used interpreted Petri Nets and Finite State Machines for a class of systems which have many behavioral scenarios defined on the same set of actions, e.g., CPU microarchitecture controllers.^[34]

Links with Hardware Description Languages

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

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).^[40] 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^[41] as a front-end has been developed.^[42]^[43]

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.^[44] 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.^[45]

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]^[46]^[47]^[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.^[48]^[49] Another method exploited theory of regions which connects elements of Petri nets with regions of states in state graphs.^[50]

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

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

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,^[56] 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 ^[57] 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.^[58]^[59]

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).^[60]

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

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^[62]^[63] and implemented in Workcraft.^[14]^[64]