XML CO538 Anonymous Questions and Answers Keyword Index

This page provides a keyword index to questions and answers. Clicking on a keyword will take you to a page containing all questions and answers for that keyword, grouped by year.

To submit a question, use the anonymous questions page. You may find the keyword index and/or top-level index useful for locating past questions and answers.

Keyword reference for choice

Question 53 (2012):

Submission reference: IN2357

I'm reading the "Choice" slides, slide 99, but I'm struggling to understand:

"By only allowing input guards, only one process is ever involved in any choice (i.e. if one process is ALTing, no process communicating with it can be ALTing)."

Can you explain this in a bit more detail?

Answer 53:

There's not much more to say ... but let's talk it through ...

The network in "Choice" slide 99 shows two processes communicating with each other by ALTing over the same two channels (a and b). Each ALT contains an input guard and an output guard. One decision has to be made – namely, which communication (over a or over b) will take place? Both processes must make this decision and they must make the same decision, which is what makes this expensive to implement.

But output guards are not allowed (currently) in occam-pi. Therefore, if one process is making a choice (ALTing) and that choice involves a channel, that involvement must be an offer to input from that channel. The process at the other end of that channel is only able, of course, to output to that channel – which it cannot be doing as part of an ALT, so it cannot be making a choice! Therefore, it cannot be involved in the choice being made by the first process.

Similarly, processes at the other end of all channels involved in the ALT of the first process cannot be involved in that choice.

The only other possible guards in the ALT of the first process are timeouts and SKIPs, none of which involve other proesses.

Therefore, if one process is making a choice, no other process is making a choice that impacts on the first choice – i.e. only one process is ever involved in deciding any individual choice. This makes ALTs inexpensive to implement, which is why output guards are (currently) not allowed!

Keywords: alt , choice

Question 9 (2011):

Submission reference: IN2039

Regarding the integrate process, I was confused on how the network was initiated. Is the following explanation correct?

Thinking sequentially, from the network diagram, it appears to begin with a number read in by the plus component. plus requires two inputs, so my thought was that the network would deadlock since only a single number could possibly be read in.

However, since all components are ran in parallel, the network is in-fact initiated by the *prefix* component. prefix outputs a 0, which is read in by plus (as well as the input number), passed to delta, with prefix copying the stream from delta from then on.

Answer 9:

Thank you for this question. Apologies for this lengthy reply ...

Thinking sequentially about a parallel network is not a good idea. The network does not begin with, nor is it initiated by, any of its parallel components. All its components start independently and in whatever order they happen to get going.

The platform on which the components run does not matter. They could be physically separate pieces of silicon real-estate, part of a larger chip, in which case the order in which they power up is indeterminate (though separated by nanoseconds). They could be on different computers in the cloud (in separate parts of the planet), in which case the order in which they start is also indeterminate (and may be hours apart). They could be software scheduled on a single core (as is the case with the Transterpreter) – in which case the order they are scheduled is still indeterminate! On some magic platform of the future, they might even start up simultaneously (though the Special Theory of Relativity pours scorn on the idea of simultaneity).

The point is that PAR components start in any order and that order does not matter! So, stop worrying about which component physically starts first.

In the case of the integrate process, its components' first actions are to communicate either between each other or with devices external to integrate. Indeed, apart from the addition in the plus component, there is nothing else that they do!

Other components (of other PARs) may get on with lots of computation (e.g. calculate pi to a billion decimal places, invert some very large matrices) before any communication. If those components are placed on separate computational engines (e.g. separate cores on a microprocessor or separate computers in the cloud), then their computations can proceed in parallel (i.e. at the same time). Clearly, the order in which they actually start is not relevant.

Back with integrate, because they communicate with each other, we do need to consider the patterns (i.e. sequences) of communication that are possible. In general (and in this case), there can be several.

The last paragraph in your question pretty much says it right.

• Initially, plus and delta wait to receive and prefix is trying to send.
• plus has spawned 2 short-lived sub-processes that each wait to receive one message and, then, terminate. One of these is connected to prefix and receives the zero that prefix sends. In parallel (i.e. before, at the same time, or afterwards), the other is connected to the external input channel and receives the first input sent to integrate.
• When both the above have happened, plus does its addition and offers the result to its output channel ... on which delta is still waiting to receive. This communication is the only thing that can happen (since prefix is now waiting for input from delta, which isn't sending anything) and it does.
• plus loops back to its initial state (waiting to receive on both its input channels) and delta now spawns 2 short-lived sub-processes that each try to output the value received and, then, terminate. One of these is connected to prefix, which is duly takes it. In parallel (i.e. before, at the same time, or afterwards), the other is connected to the external output channel and the communication happens when/if the message is ever taken.
• When both the above have happened, delta loops back to its initial waiting state and prefix offers to send on the value it received (which happens to be the running sum of the first 1 numbers input) to plus.
• All processes are now in their initial state ... and so it continues.

The above bullets, however, do not describe all the possible initial patterns of communication!

For example, in the fourth bullet above, the second input value could be taken (it it is being offered by some external device) by plus (actually, by one if its freshly spawned sub-processes). So, that second external input could happen inteleaved anywhere between the two outputs from delta described in this bullet.

Do not be alarmed by all these different possible sequences in which the communications may happen. Apart from getting a feel for the rules of synchronised communication (fundemental to the occam-pi/CSP concurrency model), we don't need to think at this low-level about what is actually happening! A crucial property of the occam-pi/CSP concurrency algebra is that the function performed by a network is deterministic (i.e. independent of the order in which events actually happen). For integrate, its outputs are the running sums of its inputs, regardless of the order of its internal actions.

At least, that's the story so far ...

In lecture 6, we will introduce Choice mechanisms that are provided so that we can design processes whose functions are determined by the order in which events happen. However, the nice thing about occam-pi is that we only get non-determinism by explicitly programming it. For almost all other concurrency models, non-determinacy is the default mode of operation (which means that the understanding we had about serial coding no longer applies) and we have to become skillful in eliminating it ... and that turns out to be very hard ...

With occam-pi/CSP concurrency, our intuition about serial programming remains trustworthy. For example, a variable only changes its value if the code working on it changes its value. There's no guarantee of that with, for example, threads-and-locks concurrency – i.e. what you see is not what you get.

[Aside: in most Object Oriented languages (including Java), the position is even worse ... that guarantee does not even apply to purely serial programming ... but that's another story ...]

Keywords: q2 , non-determinism , choice , alt