1	CE653 – Asynchronous Circuit Design Instructor: C. Sotiriou
2	Contents Fundamental Definitions Net, Marking, etc. PTnet Classes Siphons/Deadlocks and Traps Handles S-Covers and T-Covers An Algorithm for S-Covering FCPTnets
3	PTnet Definitions Definition [PTnet]: A Place Transition net (or PTnet) is a triple N = (S, T, F), where S is the set of places, T is the set of transitions (S ∩T = Ø) F ≤ (S x T) U (T x S) is the flow relation Elements of S U T are called nodes pre-set •x of x in (S U T) is given by •x = {y in S U T \| (y, x) in F} post-set x• of x in (S U T) is given by x• = {y in S U T \| (x, y) in F} A Marking M is a function M: SàN A Marked PTnet <N, M0> is a PTnet with an initial marking
4	PTnet Definitions A transition t in T is enabled at marking M iff: For all p in •t: M(p) > 0 When t fires at M a new marking M’ is produced: M’(p) = M(p) – F(p, t) + F(t, p) (F is characteristic function of F) M[t>M’ denotes that M’ is reachable from M by the occurrence of transition t The set of markings reachable from the initial marking M0 by the occurrence of a sequence of transitions σ = t₁t₂…t_{n =}is denoted by R(N, M0)
5	PTnet Definitions – Net Subclasses Definition [S-graph – State Machine]: A net N = (S, T, F) is called an S-graph or State Machine, iff each transition has exactly one input place and one output place for all t in T: \|•t\| = 1 = \|t•\| Definition [T-graph – Signal Transition Graph]: A net N = (S, T, F) is called an T-graph or STG, iff each place has exactly one input transition and one output transition for all s in S: \|•s\| = 1 = \|s•\|
6	PTnet Definitions – Net Subclasses Definition [Free-Choice]: N is called free-choice iff all p in S such that \|p•\|>1, •(p•) = p Definition [Asymmetric-Choice]: N is called asymmetric-choice (or simple net) iff for every two places p1, p2, p1•∩ p2• ≠ Ø è p1• ≤ p2• or p1• ≥ p2•
7	PTnet Definitions – Net Subclasses
8	PTnet Definitions - Subnets Definition [S-Components and T-Components]: N’ = (S’, T’, F’) is a subnet of N = (S, T, F) iff S’ ≤ S, T’ ≤ T and F’ = F ∩ ((S’ x T’) U (T’ x S’)) N’ is an S-component (T-component) of N iff N’ is a strongly connected S-graph (T-graph) and\| T’ = •S’∩S’• (S’ = •T’∩T’•). N’ is generated by a set X’ ≤ S ∩ T iff: S’ = (X’ ∩ S) U •(X’ ∩ T) U (X’ ∩ T)• T’ = (X’ ∩ T) U •(X’ ∩ S) U (X’ ∩ S)•
9	PTnet Definitions – Behavioural Properties Definition [Bounded Net]: A marked net (N, M0) is bounded iff: for all p in S, there exists k in N, s.t. for all markings M reachable from M0: M(p) ≤ k Definition [Structurally Bounded Net]: A net N is structurally bounded iff it is bounded for any initial marking M0. Definition [Liveness]: A transition t in T is live in (N, M0) iff: For all M in R(N, M0) there exists M’ in R(N, M): M’ enables t. The marked net (N, M0) is live iff all t in T are live. N is structurally live iff there exists initial marking M0 such that (N, M0) is live
10	PTnet Definitions – Graph Properties Definition [Path]: A path of a net N=(S, T, F) is an alternating sequence π = (x₀f₀x₁…f_r-1x_r) of elements X = S U T such that: for all I, 0 ≤ i ≤ r – 1: f_i = (x_i, x_i+1) in F A path is elementary iff all x_i are distinct except x₀ and x_r A circuit is a path such that x₀ = x_r A circuit is elementary iff it is elementary as a path Definition[Alternating Circuit] Let N = (S, T, F) be a net. A circuit Γ of N (not necessarily elementary) is an alternating circuit iff for all arcs in Γ of the form (p, t) the equality •t = {p} holds
11	PTnet Definitions - Subnets Definition [Well-formed Net]: A Net N is well-formed if there exists a marking M0 of N such that (N, M0) is a live and bounded system Thus, the net is not necessarily live at the current marking… Theorem [S-Components and Well-Formed Nets]: Well formed Nets are covered by S-Components
12	PTnet Definitions – Siphons and Traps Definition [Siphons (Deadlocks) and Traps]: Let N = (S, T, F) be a net. D ≤ S is a siphon (deadlock) iff D ≠ Ø and •D ≤ D• Θ ≤ S is a trap iff Θ ≠ Ø and Θ• ≤ •Θ A siphon (deadlock) or trap is minimal iff there exists no deadlock or trap D’ such that D’ ≤ D A siphon (deadlock) or trap is strongly-connected iff the subnet generated by D U •D is strongly connected
13	PTnet Definitions – Siphons and Traps Theorem[Minimal Siphon for General PTnets] Let N = (S, T, F) be a net, D ≤ S a siphon of N and N_D the subnet of N generated by D U •D. D is minimal iff there exists a circuit Γ in N_D (not necessarily elementary) that passes through all places of D such that for every transition t in Γ either: \|•t ∩ D\| = 1 (if net is FC) or \|•t ∩ D\| ≥ 2 and the places of (•t ∩ D) belong to an alternating circuit
14	PTnet Definitions – Siphons and Traps The set {s1, s2} is a siphon; the set {s3, s4} is a trap
15	PTnet Definitions – Graph Properties Definition [Handle]: Let N’ be a partial subnet of N. An elementary path π = (x₀f₀x₁…f_n-1x_n) is a handle of N’ iff π ∩ N’ = {x₀, x_n}
16	PTnet Examples
17	PTnet Examples - 1
18	PTnet Examples - 2
19	PTnet Examples - 3
20	Minimal Siphons and S-Components – Esparsa/Kemper Algorithm
21	Get Handle Algorithm N is strongly-connected FC-Net with S, S’ ≤ P U T S ∩ S’ = Ø, p in S, t in S’, t is in •p, Outputs handle H = (x₀, x₁, …, x_n-2, t, p) or 0 Num(v) values: num(v) == -1 è v in S, start point of handle, num(v) ==0 è v in S’, not visited before num(v) > 0 è v has been visited before and either (a) no handle was found or (b) has been reached again. In both cases v cannot belong to the handle
22	Get Minimal Siphon (Deadlock) Algorithm N = (P, T, F) strongly-connected FC-Net with p in P D is minimal deadlock D ≤ P, containing P To be an S-Component, minimal deadlock D must satisfy: It is strongly connected For all t in D: \|•t∩D\| = \|t•∩D\| = 1
23	S-Covering - Example Original Net:
24	S-Covering – Example – S-Cover
25	S-Cover for non Well-formed Net
26	Minimal Siphons – Cordone et. al (PIPE2) Algorithms
27	Rules for Siphon Extraction/Minimisation Definition [PTnet Reduction Function RED] Let G = (P, T, F) be a PTnet and ~P ≤ P. The reduction function RED is defined as follows: ~G = red(G, ~P), where the reduced net ~G = (~P, ~T, ~F) is defined by: ~T = {t in T \| (•t U t•) ∩ ~P ≠Ø} ~F(p, t) = F(p, t), ~F(t, p) = F(t, p), forall p in ~P, t in ~T Rule 1 [place subset reduction] Let G = (P, T, F) be PTnet and ~P ≤ P Set of siphons of G contained in ~P is the same as siphons of reduced net ~G = red(G, ~P)
28	Rules for Siphon Extraction/Minimisation Places with empty subset and places with all net transitions as post-set are special cases! Rule 2 [empty subset places] Let G = (P, T, F) be PTnet and _P ≤ P such that •_P = Ø Then, minimal siphons of G are minimal siphons of ~G = red(G, P - _P), plus the individual places in _P Rule 3 [all net transitions in post-set places] Let G = (P, T, F) be a PTnet such that P• = T Then P is a siphon
29	Rules for Siphon Extraction/Minimisation Places in post-set of transitions with empty pre-set cannot belong to a siphon and can be eliminated If all transitions are in post-set of some place, T = P• then P is a siphon (see Rule 3) Rule 4 [trap places elimination] Let G = (P, T, F) be a PTnet and let _T ≤ T be such that •_T = Ø. Then, if _P = _T•, G has same siphons as ~G = red(G, P - _P) Rule 5 [redundant places] Let G = (P, T, F) be a PTnet and S ≤ P a siphon of G. If there exists _p in S: for all t in _p• either (t• ∩ S) > {_p} or (•t ∩ S) = Ø, then S – {_p} is also a siphon of G
30	Rules for Siphon Extraction/Minimisation Rule 6 [Siphon Minimality] Let G = (P, T, F) be a PTnet and S ≤ P a siphon of G. S is minimal for G, iff all reduced nets: ~Gp = red(G, S-{p}) for all p in S do not contain siphons Rule 7 [Siphon Decomposition into Smaller Siphons] Let G = (P, T, F) be a PTnet and ~P = {p1, p2, …, pn} ≤ P The set of Siphons of G NOT containing ~P is the Union where Si is the set of siphons of the reduced net: ~Gi = red(G, P – {pi}), i.e. containing the n places except i.
31	Find a Siphon - Algorithm ~P is a set of places (one or more) which should be contained in the siphon Elimination based on Rule 4 (trap places)
32	Find a Minimal Siphon - Algorithn Computes one minimal siphon S ≤ ~S and containing ~P
33	Find all Minimal Siphons - Algorithn Find_All_Min_Siphons(G, Ø) returns all minimal siphons of G Worst-case complexity is O(2ⁿ) Due to Recursive call for Rule 7