EDIS:
Guide 
FAQ 
New 
Search 
Bibliography 
Index 
Feedback
kSequencer
Informal
A kSequencer
(k>0) has k+1 input terminals
a_i (0<=i<k) and b,
and k output terminals c_i (0<=i<k).
It waits for a signal on at least one of the a inputs and
a signal on the b input.
In contrast to a kLatch,
the environment need not guarantee mutual exclusion of the ainputs.
Having received input signals on a_i (0<=i<k)
and b, it produces a signal on output terminal c_i.
When a kSequencer
receives signals on b and more than
one a_i,
it produces a signal on exactly one of the c_ioutputs
(the others are delayed till the next b input arrives).
The specification leaves the choice open.
Often there is a fairness requirement
on this choice:
if a choice situation arises `infinitely often'
then both outputs are chosen `infinitely often'.
Each pair of terminals (a_i, c_i) can be viewed as one passive
2phase handshake port.
A kSequencer
`sequences' handshakes on its handshake ports
in syncrhony with signals on the b input.
The b input is also referred to as next input.
Schematic diagram
for a kSequencer:
[ZoomFIG]
XDI state graph
and specification
for a kSequencer with k=3:
[ZoomFIG]
Specification in XDI model.
.
(Not available for general k)
Parameterized definitions are not possible in VERDECT,
but this sketch gives the general idea:
Specification in Verdect:
define S( a0?, .., a(k1)?, b?, c0!,.., c(k1)! ) =
pref *[ a0?; c0! ]
 ...
 pref *[ a(k1)?; c(k1)! ]
 pref *[ b?; (c0!  ...  c(k1)! ) ]
end
Also available through this link
Pure DI Algebra does not allow a generalized specification. The following
specification therefore needs instantiation before interpretation:
Specification in DI Algebra:
I = { a0, .. ,a(k1)?, b? }
O = { c0!, .. , c(k1)! }
S_k = b?; [ a0? > c0!; S_k, ... , a(k1)? > c(k1)!; S_k ]
Also available through this link.
The specification of the case k=3 is as follows:
Specification in DI Algebra:
# Generated by expexp.pl
NAME ="S"
I = { a0?, b?, a1?, a2? }
O = { c0!, c1!, c2! }
S_3 = b?;[
a0? > c0!;S_3
, a1? > c1!;S_3
, a2? > c2!;S_3
]
Also available through this link.
XDI Report for the case k=3.
(Not available for general k)
The roles of subscripts i can be permuted
(on a and c simultaneously).
The kSequencer
satisfies Rules Y' and Z^in, but not Z^out
(choice between c outputs).
DI Decompositions

A kSequencer with k=1
is a Join.

A kSequencer with k=2
is a Sequencer.

A kSequencer with k=(m+n)
can be implemented with
a kmixer with k=m and
a kSequencer with k=(n+1)
(equ):
[ZoomFIG]
Taking n=0,
we find an implementation of a kSequencer (k=m)
with a kmixer with k=m
and a Join.

With a little hunting we can find that for m>1,
a kmixer with k=m
can be implemented
with m1 enabled
Sequencers
m1
Latches
2m2
Merges
and 4m4
Forks.
By suitably combining this implementation with schemes 2 and 4 above,
one can obtain implementations of
a kSequencer (k=m)
for arbitrary m>1,
in terms of
m1
Sequencers
(of which m2 are enabled),
m2
Latches
2m4
Merges
4m8
Forks.
Using Boolean Gates
No information available
Using Transistors
No information available
No information available
In [Ebergen89],
the kSequencer
is referred to as kSEQ component.
Section 6.2.6 of [Ebergen89]
presents decomposition 4
(without kmixers,
RGDA Arbiters, or
NonReceptive Mixers as stepping stones).
[Ebergen89]
Last modified at Fri Nov 20 10:11:40 1998
Encyclopaedia of DelayInsensitive Systems
Copyright © 19951998
Tom Verhoeff /
Tom.Verhoeff@acm.org