The present work is devoted to the development of software tool written in Java for synthesis of asynchronous speed-independent circuits. A special type of Petri nets - Signal Transition Graph, was used for the synthesis. Using the algorithm based on the theory of regions, a logic function is derived from this graph. In order to reduce the complexity of the resulting asynchronous circuit the number of gates should be minimized by optimization of logical function with a Quine-McCluskey algorithm.
Asynchronous circuits have gained in importance along with the expansion of the production of high integration circuits. By that time, mostly synchronous systems were designed. Decreasing the dimensions and increasing the operating frequency, however, made the synchronisation of individual function blocks on a chip more difficult. The time delay is generally caused by the increased cycle of timing signal. This delay (for the individual function blocks) differs locally to such a degree that it results in the synchronisation failure of the individual subsystems and the malfunction of the circuit. This issue can be solved by adding a special regulation circuit providing a constant clock frequency in the whole chip. Such a circuit would occupy relatively much space on a chip (approx. 10%) and consume much power (approximately 40% of the input power). This would result in the increasing cost and energy demand of such chips. The application of asynchronous circuits provides a different approach.
events and not by time. As no clock signal generation is required and no regulation circuitry is needed, such circuits are smaller and consume less energy. The only issue that is common for both synchronous and asynchronous circuits is the presence of socalled hazardous states.
that generates a circuit diagram as a result of the circuit behavior. The field of digital circuit synthesis is complex and provides many solution approaches. One of them is represented by the application of the Petri nets formalism as a description tool for the behavior of an arbitrary digital circuit. Application of algorithms for STG synthesis (e.g. based on the region theory) a logical function is derived (using Quine
2
as a heptad (P, T, F, M0, N, s0, λT), where P is set of places, T is the set of transitions, F is the flow relation F ⊆ (P × T) ∪ (T × P), M0 is the initial marking of Petri net, N = I ∪ O is a set of signals, I is a set of input signals and O is a set of output signals. s0 represents the initial value for each signal in its initial state and λT: T → N × {+, −} is the transition labelling function.
The state graph SG [
Each state is labelled by a binary vector (s(0), s(1), ..., s(n)), where each signal s(i) i ∈{0, 1, … n} can acquire values from the set {0, 1}. Although for a better illustration of the graphical representation of possible states, individual signals can also acquire possible values from the set {0, 1, R, F}. This form of labelling also provides information as to whether the respective signal is excited or not. The excited signal represents a change in its value from 0 to 1 or vice versa. This is illustrated by the characters R or F. The R character denotes the signal value in the SG being equal to 0 but where its value has changed to 1 in the subsequent state s(i). The signal is able to reach the next state because the respective transition could be started. This transition is labelled ui+ by using the labelling function λT(t). Similarly, the F character denotes the signal value being equal to 1 and to 0 in the subsequent state. The excited state can be formally defined as follows: ∃(si, t, sj) ∈ δ . λT(t) = ui+ ∨ λT(t) = ui−. (1)
signal ui+ or the decay of the signal ui−. As stated hereinabove, STG is a special Petri net fulfilling the following properties:
must strictly alter between + and − in any execution of the STG.
pair of states of S has a unique state coding defined by the labelling function λS, or it does not have the unique state coding but it does contain the same output signal excited in each state. If this property is not fulfilled, a new signal or signals are to be inserted into the SG.
place ahead of the transition to the place or places behind, provided that this start shall not be deactivated by another transition. This property must be provided for the input and internal signals. The persistency of the input signals must be ensured by the environment of the designed circuit.
[
nous speed–independent circuit whose behavior is characterized by the STG. Speed
independence is a property ensuring the correct circuit operation considering that all
logical gates have unbounded delay [
After loading STG in the software, the required properties (boundedness,
consistency, persistency, input free-choice, liveness, and complete state coding) are verified
and the SG is derived. In some cases, the state graph does not comply with the CSC
property. The solution of this issue is based on the insertion of new states into the SG
according to the algorithm published in [
neighbor regions) and the cost function is calculated [
PNEditor [
out LDS+ in LDTACK+
in DSr+ out D+ out DTACK
in LDTACKout DTACK+ out D
P8 out LDS
P1
P5 P3 P4 P6 P9 in DSr
P2 P0 P7 p10 (a) 100R01 csc0+ 10000R
DSr+
R00000 DTACK- 0F0000 LDS+ 10R101 LDTACK+ 1011R1 D+ 1R1111
DTACK+ 10F000
LDS101F00
LDTACK
LDTACK
LDTACKDSr+
R0F000 DTACK- 0FF000
LDS
LDSDSr+
R01F00 DTACK- 0F1F00 F11111
01111F
DSr(b) csc0
D0111F0 (c)
Fig. 2. (a) Input format of Petri nets - STG, (b) SG fulfilling the CSC property, binary vector is <DSr, DTACK, LDTACK, LDS, D, csc0>, (c) resulting logical circuit.
4
The algorithm of the synthesis of asynchronous speed-independent circuits was implemented for the first time in the petrify tool [10]. Due to the absence of the graphical visualisation of the resulting circuit, we decided to programme our own tool, which would include this functionality. The software is written in Java ver. 1.6, which ensures platform independence. The implementation of more methods of logical circuits’ synthesis will be the next step. These methods should take advantage of a non-standard memory element (C-element). The utilization of this element may prevent the occurrence of several hazardous states. Moreover, it has a very fast memory and can be easily implemented on a chip. The extension of support to multiple input and output formats is another important step in our development. One of the possible input formats could be the timing diagram, which is easy understandable to many designers. If a logical circuit is designed, it must be verified by the simulation process.