[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: Occam-Tau - the natural successor to Occam-Pi - or is there one already?

Isn't a single processor now an outdated concept for a modern parallel programming paradigm.

If I understood David (May) correctly, we should assume that we have a large pool of everything, and only in some cases will physical resources provide a practical limitation. 

Tony Gore
Sent from my mobile
tony@xxxxxxxxxxxx +44 7768 598570
-----Original Message-----
From: Eric Verhulst (OLS)
Sent:  02-10-2012, 20:11 
To: 'Larry Dickson'
Cc: 'Occam Family'
Subject: RE: Occam-Tau - the natural successor to Occam-Pi - or is there one already?

Am I understanding this right? The assumption is that all happens on a single processor?


Even if the system has no system-wide transparent semantics (and routing), it still means that the output on the channels (assuming occam) could have originated on another processor if there is more than one processor. That processor runs its own set of processes, independently of the scheduling on the processor where the ALT? is taken place. It might be idling or being locked up by an CPU eating process.

So the ALT? has no control whatsoever about the order in which the channels it is waiting on will trigger.  When the ALT? is reached, some other channels might be ready already. When this point is reached, the first one on the list is passed on.

This means in practice and semantically, that the PRI doesn't matter. Hence the notion of PRI is wrong.


In the ALT construct, the notion of PRI on the channel reading side makes no sense because one doesn't control when the channels trigger. It only makes sense at the moment of the channel output, in its turn added to the list of enabled channels of the ALT construct. The synchronisation happens at some point but independently of when the channels were triggered. Fairness however does not help to reach real-time goals. It follows semantics of "eventually" (= soft real-time).

To be side-effect free, either all these outputs must be equal (in priority) either the notion of priority must be system-wide and consistently applied. Which means, anything that can execute (= ready to run) does it in order of priority and the system must guarantee that. If not, all are equal.  

The two priorities on the transputer were than also not sufficient for hard real-time. The Hi Pri queue was more like the ISR llevel on standard processors. So everything else  is Lo Pri of equal priority. Notwithstanding, it was a lot easier to program than the way it has to be done on standard processors.


From: Larry Dickson [mailto:tjoccam@xxxxxxxxxxx]
Sent: Tuesday, October 02, 2012 7:59 PM
To: eric.verhulst@xxxxxxxxxxxxx
Cc: 'Occam Family'
Subject: Re: Occam-Tau - the natural successor to Occam-Pi - or is there one already?



On Oct 2, 2012, at 10:26 AM, "Eric Verhulst \(ALTREONIC\)" <eric.verhulst@xxxxxxxxxxxxx> wrote:

I guess you are right. But this also means that the notion of PRI(ority) was screwed up.


It really meant "the first one in the list". Assuming that the second one on the list had a higher priority (which could not be specified) but was inserted later, it wouldn't have mattered. Hence the conclusion remains the same: assume nothing about the order or priority.


With a priority sorted list, this dilemma disappears. The priority is a system wide property (e.g. assigned to a task at design time following a RMA). When waiting on a priority sorted list, one gets the highest priority one that was inserted (before the waiting) even if inserted the last.


"One gets the highest priority one that was inserted" is always true but "before the waiting" is ambiguous. It's the highest priority one that was inserted before its own disabling. (If the ALT is in a low-priority process and the sender high priority, it could have even been inserted via an interrupt just before that disable instruction was executed, i.e. after the "waiting" was finished and some higher-ALT-priority disable instructions came up empty.)


"The first one on the list" (the source listing of the PRI ALT, or the assembly code listing of the disables) is the one that gets the highest priority. However, if by "list" you mean the readies that are inserted by the prospective senders, the one that has higher priority does get chosen even if it came ready later, as long as it came ready before the disable. This is a frequent occurrence when senders come ready to communicate before this ALT instance is executed --- for example, while the code branch resulting from a previous ALT selection in this same loop is still being executed, which may take a while. In such a case there is no wait. If the ALT suffers a wait, that is if no senders are in line when it got enabled, then the race is still possible but less frequent.


If there is a wait, and an ALT-lower-priority sender beats the ALT-higher-priority one by a few cycles, then the ALT disables will trigger fast enough to draw a blank on the higher-priority one and select the lower-priority one. It is immaterial whether the lower priority sender is PRI-high-priority or PRI-low-priority, though PRI-high-priority senders will tend to win these races because they can interrupt. In any such case, the ALT-high-priority sender will be picked up on the next loop iteration.



Again, one should not assume anything about  the order but at least now the highest priority one is received first. This mechanism reduces the blocking time for higher priority tasks in the system and generally improves the real-time behavior without affecting the logical behaviour, if correctly used.




From: Mailing List Robot [mailto:sympa@kent.ac.uk] On Behalf Of Larry Dickson
Sent: Tuesday, October 02, 2012 6:46 PM
To: Occam Family
Subject: Re: Occam-Tau - the natural successor to Occam-Pi - or is there one already?
Importance: Low



On Oct 2, 2012, at 9:18 AM, Eric Verhulst (ALTREONIC) <eric.verhulst@xxxxxxxxxxxxx> wrote:




The PRI ALT is just a language concept. As far as I know never implemented.


This appears to be exactly backward. The PRI ALT is the only thing ever implemented. The priority depends on the order of disabling. See the Inmos Compiler Writers Guide.




The consequence is that it is really an ALT. Which means , don't assume anything about the order in which the ALT triggers. If not, you are likely to introduce side-effects in the code. Therefore the opposite is better. Always implement in order of priority but still assume that the "select" is priority independent. It keeps the behaviour consistent even if the timings (in a network) vary. Because in practice, one should not assume anything about the order of things on other nodes. Logical (functional) behaviour and timing behavior should be independent.