From: A E Lawrence (adrian.lawrence_at_email.domain.hidden)
Date: 2001-08-09 07:41:28
I hope that the note below might clarify why compliant processes are
relevant. Sometimes. In hardware.
Adrian
--
Dr A E Lawrence
[ Part 2: "Attached Text" ]
Compliant processes: examples
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
I have been puzzled about why people seem to have trouble understanding
compliant processes.
Compliance is irrelevant for typical software implementations
-------------------------------------------------------------
I now suspect that the difficulty arises from thinking about
sequential transputer style software implementations.
For then there are no truely simultaneous offers of events.
Priority only arises when an implementation becomes aware of two or
more offers of events and cannot, or chooses not to, determine
which happened first.
An example of that is when several channel words may be marked ready.
As far as the software is concerned, this is a simultaneous offer
of events. But when a scheduler selects a partner process to run, only
one such is active at any moment, so only one of those events could be
selected. There can be no priority conflict there. There is only
one potential event: call it a "completed offer". Or possibly
regard the scheduler as the environment, offering only one of the
events - corresponding to which of the partners it has choosen to
schedule first.
And this sort of behaviour is entirely desirable: we want to avoid
conflict.
Compliance and external communication
--------------------------------------
Consider
CHAN OF INT link1,link2:
PLACED PAR
PRI PAR
link1 ! 1
link2 ! 2
PRI PAR
link2 ? x
link1 ? y
Once again an implementation using a software scheduler will almost
certainly result in the link offers - here attempting to start the
communication - being ordered. Not because the link engines cannot
operate truely concurrently, but because the link engine
initialization will be done in some order determined by the
sequential scheduler.
What if the sender has a much higher clock than the receiver?
It might have prepared both link engines before the link engines
of the very slow receiver had sampled the lines and seen the
incoming data. Then the receiver sees simultaneosu offers.
But now the situation is just the same as for the case of
two channel words being ready: the scheduler of the receiver in
effect serializes the offers. Once more there is no simultaneous
'completed offer'. And so no contention (priority conflict) can
arise.
Compliance is only relevant when there are simultaneous offers.
---------------------------------------------------------------
So we see that compliance is seldom an issue in familiar situations.
And indeed my simplified CSPP omitted it.
But in synchronous hardware, there can be really simultaneous
offers.
Suppose channels are implemented with Handel-style handshaking lines:
each channel has a pair of `ready' signals:
--------- ready_to_send --------->
<-------- ready_to_receive ------
============= data ==============>
Both ends share a common clock. One each clock edge, the state is
both sampled and updated. The next state is determined by the previous
state sampled on the preceeding clock edge. In particular handshake
lines and data are simultaneously sampled on each edge.
So a simple channel communication is:
1) Clock edge 1
---------------
The sender raises ready_to_send and simultaneously presents the
data. This happens as a consequence of the clock edge, so
immediately following that edge. This covers propagation delay,
setup time, overshoot and all the other physics: all that matters
is that there is an valid state of the lines for the receiver to
sample on the next clock edge.
Assume that the receiver also raises or had already raised its
ready_to_receive line.
2) Clock edge 2
_______________
The receiver samples both ready_to_send and the data lines. Had the
ready_to_send line not been asserted, it would discard - that is
not gate it anywhere - the datum. But in our case, it collets
the datum, if any. If `ANY' would not have a datum, of course :-)
The sender simultaneously samples the ready_to_receive, and thus
knows that the event is complete, and removes or updates tha data.
And if there is no new event due on clock edge 3, it drops the
ready_to_send signal.
Notice that that simple scheme allows a communication on every clock
edge.
It is easy to implement
PRI ALT
c1 ? x
cough
c2 ? y
sneeze
with this sort of hardware. There is just a simple circuit sampling
the ready_to_send_c1 and ready_to_send_c2, which controls which
ready_to_receive line is raised on the the next clock edge in
response to offers which can be truely simultaneous.
Now consider our example above as:
CHAN OF INT c1,c2:
PAR
PRI PAR
link1 ! 1
link2 ! 2
PRI PAR
link2 ? x
link1 ? y
implemented in this sort of hardware. Now both sides may assert both
handshake lines on a clock edge. Indeed if we are using the hardware
efficiently we will want everything to be simultaneous as far as
possible. Now we have real simultaneosu offers and real contention.
The point here is *not* that
a) the above code looks silly in this sort of hardware;
b) we can design a extra combinational circuit as part of the
channel implementation to arbitrate and resolve the contention
in a single cycle;
or
c) that a compiler might refuse to accept such a construct.
The point *is* that
a) the above syntax is valid, or at least its equivalent CSPP is;
and
b) the way in which the contention is to be resolvedby that extra
circuit need to be specified.
But that example, choosen to illustrate the software case, is not
something one would think of implementing in hardware.
However
PAR
PRI ALT
c1 ? x
...
c2 ? y
...
PRI PAR
c1 ! 1
c2 ! 2
is a sensible circuit. Why? The receiver might be something expensive
to implement in hardware. A divider, perhaps. So we can't afford
two copies. So it multiplexes its input with the PRI ALT.
And one can think of reasons why we have PRI PAR on the other side,
not least in safety critical situations.
So the above code for synchronous hardware is plausible.
Now consider what happens when both channels are ready at both ends at
a clock edge. We have contention. It must be resolved somehow.
Probably by a dedicated circuit generated by the compiler as part
of the channel circuit. Or by negotiation between each of the partners
over several clock cycles. Whatever. Apart from noting that it is costly
in hardware and possibly time, we need to specify the behaviour.
So that we know what the complier is entitled to do.
That is one reason why CSPP exists. To define precisely the allowed
behaviours of such processes.
But what has happened to compliance?
Ambiguity of PAR
----------------
In CSPP PAR is abstract. That is it allows many implementation: it is
non deterministic about interleaved events.
And in CSPP as in CSP, simultaneous, but unrelated,
events are modelled by interleaving. That is a touch disconcerting
in the context of simultaneous events. Untimed HCSP introduces merged
events as a more comfortable way of handling that.
Thus PAR can be implemented as PRI PAR. Or PAR PRI.
In my original simplified CSPP, on each offer, an implementation
of PAR had to behave like PRI PAR or like PAR PRI. It could change
character an each offer, but if it was presented with more than one
vents simultaneously, it would always select one. So behaving, as
far as that event was concerned, like PRI PAR or PAR PRI.
An it is perfectly valid to implement PAR as PRI PAR.
Technically, PRI PAR is a refinement of PAR.
Now consider
PAR
PRI ALT
c1 ? x
...
c2 ? y
...
PAR
c1 ! 1
c2 ! 2 .
But if PRI PAR is a possible implementation of PAR, then we can get
contention. That is *not* what we want, nor is it what we intuitively
expect. But the compiler is perfectly entitled to compile the
'bad' program.
What we want is
PAR
PRI ALT
c1 ? x
...
c2 ? y
...
SYM PAR
c1 ! 1
c2 ! 2 .
Without compliant processes in CSPP, we cannot specify the above, and we
cannot specify in CSPP that the compiler must avoid the contention.
Notice that most occam programmers think of PAR as SYM PAR. And that
doesn't matter in almost all software situations because
real simultaneous events do not occur.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
I hope that this makes the reason for including compliance in CSPP
a little clearer.
Adrian
This archive was generated by hypermail 2.1.7 on 2004-10-31 20:03:59 GMT
© Copyright WoTUG
All rights reserved