Re: Priority revisited: a new primitive

[M_Boosten <mboosten@xxxxxxxxxxxxxxxxxxx>]

Hi Adrian, Ian, Gerald, ...

General remark: I love mails that introduce new/different concepts,
like Adrian's PAR PRI.

The fact that one talks about (1) PRI PAR, (2) PAR, (3) PRI ALT, (4) ALT, 
and (5) PAR PRI tells me: all this is TOO COMPLEX!  Something is
FUNDAMENTALLY WRONG!

Note: I do not know a good solution for the moment, but this e-mail is
      an attempt to start finding it...

Ian wrote:
> I believe priority should be associated with events, and events only. 

I know/believe/think/guess/hope the following:

1. CSP Processes specify the order in which events occur.
2. This is a partial ordering: the system may make an arbitrary choice
   at some point.
3. The choice MUST be arbitrary for processes that are considered part
   of physically parallel systems.  Note: multi processor machines, and
   different processes on parallel hardware (FPGAs/ICs).
   [I find it difficult to express point 3 properly...]
   [I find it difficult to abstract from hardware here, but, I would like
   to in my reasoning...]
4. The ordering is important for those situations in which a single
   physical execution unit is used.

I restrict myself to single-execution unit based systems:
1. The ordering must be hierarchically composable.
2. The hierarchy is the process hierarchy.
3. The ordering has to do with the events, not with the processes.
4. The processes just specify the order.
5. Since processes consist of other processes, they can specify their
   order by mixing the order of their childeren together with their
   own influence.
   
Ok. Towards math:

Assume: Process Px has events Ex and ordering Zx

The ordering is a SEQUENCE of subSETs of Ex.

Example: Zx = [ {e1,e2}, {e3,e4,e5}]

Events e1 and e2 have the same priority, but their priority is
higher than the priority of {e3,e4,e5}.

Assume: Process Pxy consists of Px and Py.

Then: Pxy can specify how the ordering of Px and Py is interleaved.

Zx may be inconflict with Zy, if Px and Py share events.
In that case, Px and Py cannot be composed (I think).

Assume Px and Py do not conflict.
- If Px and Py share events, they communicate.  In that case, I would
  expect Pxy not to be involved with those events.
- The non-shared events can be ordered.
- Zxy "kind of" zips Zx and Zy.  So: Zxy = Zx zip Zy.
- Any zip operator can be useful... I guess...

Conclusion: many prioritisation functions exist.

Questions:
  Shouldn't CSP allow all zip operators/functions...
            
I hope I could be followed... I hope I make sense...  Adrian...?
What does anyone think...?

Cheers,
	Marcel

> From owner-occam-com-out@xxxxxxxxx Sat Oct  7 22:40 MET 2000
> Date: Sat, 07 Oct 2000 21:22:26 +0100
> From: A E Lawrence <adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
> X-Accept-Language: en
> MIME-Version: 1.0
> To: occam-com@xxxxxxxxx
> Subject: Priority revisited: a new primitive
> Content-Transfer-Encoding: 7bit
> 
> In occam and HCSP we have two primitives:
>   PRI PAR
> and
>   PRI ALT
> The purpose of this note is to suggest the addition of a 3rd primitive:
>   PAR PRI  .
> 
> {Eh, is this too much like a maze of little twisty passages?}
> 
> As the occam community has observed, neither PRI PAR nor PRI ALT gives a
> simple way to assign an enduring priority to particular events. PRI ALT
> gives priority to events rather than processes, but only to initial
> events. PRI PAR gives enduring priority to the set of events performed
> by a process, but a process almost always must perform events of lower
> priority as well. This side effect of raising the priority of less
> important events leads to pathologies like priority inversion.
> 
> A new primitive: PAR PRI
> ~~~~~~~~~~~~~~~~~~~~~~~~
> 
> I therefore propose a very simple new form of parallel constructor
> 
>   PAR PRI [S] .
> 
> S is the set of events with raised priority. I am not sure whether we
> need to specify that S be a subset of the alphabets of the component
> processes, although it would be pointless to include extra events in S.
> 
> Thus 
> 
>   PAR PRI [{a}]
>     P1
>     P2
> 
> is a process which will always perform the event a if it is available:
> that is when it is offered by the environment and can be accepted by
> P1||P2.
> If a is a common event jointly executed by P1 and P2 and P1 and P2 are
> both capable of performing a, then it will be performed in preference to
> any other events. The more interesting case is when P1 or P2 or both can
> perform a independently of its partner (interleaving) : once again, a is
> performed in preference to other events. 
> 
>   PAR PRI [{a,b}]
>     P1
>     P2
>     P3
> 
> is similarly a process that gives priority to the events a and b. If
> both are offered and can be accepted, the choice between a and b is non
> deterministic.
> 
>   PAR PRI [{a}]
>     PAR PRI [{b}]
>       P1
>       P2
> 
> is a process that will always perform a if it is offered and can be
> accepted; otherwise it performs b if that is available; and performs
> other available events otherwise.
> 
> It seems worthwhile to have a compact way of writing more complicated
> priorities, so we have
> 
>  PAR PRI [S1,S2,...,Sn]
> 
> where S1,S2,...,Sn are each sets of events. And events in Si take
> priority over events in Sj when i>j. In effect, we have a partial order
> relation with
> 
>   xi > xj  when i >j for xi \in Si and xj \in Sj.
> 
> It is easy to give an HCSP (and THCSP) denotational semantics for these
> constructors. We have a clean easily understood compositional element.
> 
> This seems such an obvious and simple primitive: why hasn't it been
> suggested before? Probably because a software implementation on a
> conventional sequential CPU will have a large overhead, although of
> course conventional interrupt hardware is essentially an implementation
> of PAR PRI for certain special external events. 
> 
> In occam, are the sets of events just channels?
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> 
> So far, I have used an abstract occam-like pseudo syntax. At present
> occam does not include an explicit syntax for sets. How do we write S =
> {a,b}? Perhaps exactly in that form: {a,b}?
> 
> However, channels are simply sets of events. So an occam binding could
> just use channels as in
> 
> PAR PRI [{c,d}] .
> 
> Then any events on channels c and d have priority. That applies whether
> the communications are outputs or inputs or both when the communicating
> partners are in the scope of the PAR PRI.
> 
> 
> What about assignment? In HCSP. assignments can be regarded as special
> sorts of event. Is there a need to allow assignments in the list of
> prioritized events? If so, what syntax would be sensible?
> 
> Efficiency
> ~~~~~~~~~~
> 
> Hardware compilation of PAR PRI is elementary and efficient. It can be
> as efficient as an ordinary PAR: indeed a typical compilation of PAR
> will actually be a PAR PRI!
> 
> Software implementations on conventional CPUs however may pose greater
> challenges. PRI PAR is, of course, easily handled with a set of run time
> queues, and one suspects that this is the real reason for its presence
> in the language. Would one ever want PRI PAR if one could have PAR PRI
> at no extra cost?  PAR PRI needs to examine the potential high priority
> events after every action, and possibly context switch. As noted above,
> this is exactly what the interrupt machinery of a conventional CPU does;
> the interrupt status is sampled at each machine cycle. Likewise various
> other mechanisms. And we all know that typical CPUs are abysmal at such
> context switching in these and other circumstances. 
> 
> I haven't given much thought to this software implementation question,
> but I suspect that the spectacular strategies used in KRoC and SPOC
> aren't going to help much here. But over to Kent and SOTON here... If
> this is right, it looks as if one should use PAR PRI sparingly when the
> target is a conventional CPU. 
> 
> But if this is the right primitive, then it is conventional CPU's that
> need to be "adjusted" rather than the language :-)
> 
> Of course, I still agree with a comment made by Barry at Keele: we
> probably need a higher level of abstraction in which we declare what
> timeliness properties we require rather than reason at the lower level
> of priority. But as I don't know how to do that yet, and because an
> implementation of such a specification may well require it, I offer PAR
> PRI for your consideration.
> 
> Comments?
> 
> 
> Adrian
> -- 
> Dr A E Lawrence (from home)
> 
>