Contents
This page is in groups Technology, My Go (golang) notes and My XMOS pages.
This blog note has been moved from http://oyvteig.blogspot.no/2012/04/045-nondeterministic-note-about.html. I have written a little about nondeterminism before [1], [2]. [1] is about Ada and the Ravenscar Profile for safety-critical systems. The newer note IEC 61508 and (safe?) concurrency also covers the matter somewhat. Observe that (non)determinsm is a wide term; I do attempt to discuss it from several angles.
Intro
This note deals with several aspects of nondeterminism (or non-determinism) in sowftware programs. Some times nondeterminism is unwanted, some time is doesn’t matter. There will be tools that can analyse whether pathologic nondeterminism is present and help you remove it. There will also be nondeterminstic «Lego bricks».
I have tried to dream up an example from real life. If you only have a small spot to allow spilt rain water to be drained to: make sure there is only one drain correctly placed in the lowest tank (spot). If it’s practical for you to collect rain water in many tanks and it doesn’t matter where these tanks are drained: drain them all onto the lowest tank. Rain will fall on the roofs of your house rather nondeterminstically (site, amount, time and duration), individual tanks will have different sizes and will spill over rather nondeterminstically (amount, time and duration), but the final drain spot in the ground will be at one place – rather determinstically (site). You could even make the lowest drain empty once per hour (depending on the max capacity), and make start time deterministic (spot and time). But the amount of rain water would be nondeterministic (duration, amount). In this real life example we can see that internal nondeterminism seems ok but external nondeterminism is not wanted. We also see that nondeterminism and nondeterminism may be different things (spot, amount, time, duration etc.).
Basically, in programming, nondeterminstic programming [18] means that there is a kind of if-then-else where the different clauses are are not evaluated sequentially, but «all at once». If more than one evaluates to true, then it’s nondeterminstic which choice is taken. We simply cannot tell. And we should not rely on any one of them being taken. It’s often called nondeterminstic choice. Several operating systems have it, and several languages.
This choice could be the result of an evaluation of any value (like Promela), including communication (like Promela), or only communication (like Go, Ada, occam or CSPm). Some languages allow a fallthrough (like Promela and Go), some consider none to choose from as an error (like occam and xC). Timers also often may be in the choice set.
A little early: CSPm (see note FDR2 notes) has internal choice |~|, also called nondeterministic choice since there are matters «inside the box» that has the last say on the nondeterminstically chosen set available for an external user. Phrase: «May refuse one for the other, must take one if both«.
CSPm also has external choice [], where the nondeterminism is visible – almost to the point of it being deterministic. Phrase: «willing to handle any«. If a process diverges (livelocks) or if some event may be refused after a trace of visible events, then it is said to pathologically be nondeterministic. Observe that for external deterministic choice, «If both a and b were communicated simultaneously, the choice would be resolved nondeterministically.» (Wikipedia CSP:Primitives:Deterministic choice). Also written out as «Nondeterminism can be inadvertently introduced into a nominally deterministic choice if the initial events of both sides of the choice are identical.» CSP:Primitives:Nondeterministic choice.
However, a computer program that does one thing at one time based on input x, which nondeterministically does another thing based on the same input x – should light a red light. Most often it’s not acceptable. More below.
In other words: either nondeterministic in specifications as internal («unsafe») «nondeterministic choice» or alternatively («safe») external deterministic choice (present in programming languages for code that runs). However, also in the latter the choice may be resolved nondeterministically (hopefully also as «safe» nondeterminsism, but this is depending on the language or implementation of it). And for hiding events of external choice may cause nondeterminism to appear. This is quite interesting! See (CSP).
Mindstorms
In Mindstorms [17] (page xviii) Seymour Papert in 1980 writes about how he as a child was fascinated by the differential gear:
«I found particular pleasure in such systems as the differential gear, which does not follow a linear chain of causaility since the motion in the transmission shaft can be distributed in many different ways to the two wheels depending on what resistance they encounter. I remember quite vividly my excitement at discovering that a system could be lawful and completely comprehensible without being rigidly deterministic.«
I added this quote after having written most of this blog note, because it in a way set certain things straight for me: a naïve feeling of what rule-based nondeterminism is.
Promela
Have a look at the Promela Wikipedia article [3]. Promela’s non-determinsitc choice goes like this:
if :: (A == true) -> option1; :: (B == true) -> option2; /* May arrive here also if A==true */ :: else ->; fallthrough_option; fi
«The consequence of the non-deterministic choice is that, in the example above, if A is true, »both choices may be taken». In «traditional» programming, one would understand an »if – if – else» structure sequentially. Here, the »if – double colon – double colon» must be understood as «any one being ready» and if none is ready, only then would the »else» be taken.» This can be used to set a bool to a random value:
if :: mybool = true; :: mybool = false; fi
But the most used choice is to receive and send on channels between concurrent processes. The same choice may have any mix of them. So, if one send and one receive is possible, it would either send or receive – but not both. In the «Executability» chapter of [3] this is said: «When Spin analyzes a model like the above, it will verify the choices with a non-deterministic algorithm, where all executable choices will be explored. However, when Spin’s simulator visualizes possible non verified communication patterns, it may use a random generator to resolve the «non-deterministic» choice. Therefore the simulator may fail to show a bad execution (in the example there is no bad trail). This illustrates a difference between verification and simulation.»
Go or go or golang
The Go programming language [4] also does this in its select statement. Different from Promela this select only takes a communication clause as its parameter. Also for Go we may have channel send or receive. «If multiple cases can proceed, a uniform pseudo-random choice is made to decide which single communication will execute.» They call it pseudo-random to avoid saying nondeterministic, probably to hit programmers better at home. (31July2012:) Rob Pike (one of the original authors of Go) posted this code on golang-nuts as a direct response to a Promela example like the above which I posted on a thread there:
package main
import "fmt"
func main() {
c := make(chan int, 1000)
go func() {
for {
c <- 1
}
}()
for i := 0; i < 100; i++ {
select {
case <-c:
fmt.Println(0)
case <-c:
fmt.Println(1)
}
}
}
«Using select as a random generator»
When I ran the code it printed 45 ‘1’ and 55 ‘0’, average of 0.45. Several times. I modified the code with two counters and printed those instead, and experimented with the max value (1000, 2000, 5000 etc.) and the average got better. I just noticed how the counters followed each other. Of course the pseudo-random generator is correct. Here, channel c in func sends any value (1) to the concurrent block with a select. This select listens to the same channel in both components of the select. The selection is done nondeterministically on the set of all executable components. This set has two components, and it doesn’t even care that those two components come from the same channel. To select nondeterministically some kind of pseudo-random sequence is probably used. Run the code at http://play.golang.org/p/INacl7a-BU and read the post as a registered user at https://groups.google.com/d/msg/golang-nuts/YOs5K0zvfWk/2SFFXaI7ZswJ. The thread is at https://groups.google.com/d/topic/golang-nuts/YOs5K0zvfWk/discussion. Thanks, Rob Pike for letting me copy the code.
-Nondeterministic selective choice in implementations is not good
In a lunch at a visit (being an external examiner) to the university here I heard this statement laid out. I had told that the new book The Go Programming Language (Addison-Wesley Professional Computing) by Alan A. A. Donovan and Brian W. Kernighan (so the C-book guy must be still faring well) (Amazon) didn’t even mention nondeterminism or determinism. I assumed it’s been deliberately left out. (*)
But CSP deliberately has non-determinism that’s used in specifications for don’t care, in addition to the fact that it appears out of thin air when state is hidden (in any CSPm verfied by FDR3. This effect also appears in implementations but may be verified to be ok). Abstraction by hiding (building modules) = introduces non-determinism. The easy way is to say that you might know what’s going on in your own house when the doors to the rooms are open, but when closed it’s non-deterministic for you, the observer…
The statement was that with the non-deterministic guarded choice in Go, what happens is up to the run-time, which is «not good». This is implementation, not specification. With occam there is ALT or PRI ALT, always coded as PRI ALT. For a server to be «fair» I have to code it myself, it’s up to me, at the application level to find the best algorithm. Which, during my years as occam programmer was «new starting channel index in the ALT-set is the channel index of the served channel + 1 modulo-divided by number of channels». Channels are clients[0..4] (five) ALT‘ed in set [4,0,1,2,3] served index 4, then 4+1 rem 5 == 0 yields next ALT set [0,1,2,3,4]. Just served 4 and you’re at the back of the set.
So, no wonder that the PRI ALT was introduced into occam on the transputer to make application control of fairness possible . They did this building a mechanism designed to be unfair (ref. Roger Shepherd in a private mail Dec2015)
If I try the Go code shown above (or this) then you can change the parameters and see that it’s so and so about the distribution of the randomness. It’s almost never 50/50. In other words, Go takes care of the fairness, I don’t. But of course, the Go solution may be just good enough! (Based on the Go code above I did make a Topic in Go Forum called Lexical scope of variables needed by conditional choice select case, see here.)
A model, being theoretically non-deterministic simply means to traverse all possibilities. Doing it at run-time implies some random function. Plus a certain pattern on the normal racing between processes or goroutines. I guess that’s the problem. It shouldn’t rely on any of those, even if it’s good enough.
(*) That’s not entirely true, I discovered later. The book briefly mentions (on page 245) that when more than one select case are ready then select picks «at random», and then follows up with the word «nondeterminstic». But I still haven’t found any chapter on nondeterminism. (See the Promela chapter above for a description of the difference between random and nondeterministic.). I have discussed some points of the book more detailed in a separate blog note, see 120.
Deterministic pattern in Go
This chapter is an update 13Sep2020.
In [20] (Hajesmaeeli) I discovered a pattern for Go. It is interesting, and does away with select, and merges everything into a chan bundle. If, in 2020 they had added a pri select in Go, this solution would not have been necessary.
There also is some in a Nondeterminism chapter in note 072 (here), with a summary of Rob Pike’s comments.
Still «missing» priority or ordered select in go?
I have a separate chapter on this at 113:[golang-nuts: Still “missing” priority or ordered select in go?].
29Apr2021. See Still «missing» priority or ordered select in go? where I write:
I know from some years ago that go did not have any priority or ordered select construct [ref this note]. The idea is that select always is a nondeterministic choice operator, if this is still so. Implemented with a random, I assume. Programming user defined «fair» algorithms or patterns is then not possible, I believe. Is this still so in Go? No prioritised or ordered select in go? But is there still a way to code this by f.ex. combining several selects? I saw a different take at this at [ref above chapter’s ref], where the select is replaced a single chan containing a chan bundle, thus becoming «deterministic».
Have a look at this code example by Jan Mercl, much discussed in the thread (also here):
select {
case x := <-highPriority:
handle(x)
default:
select {
case x := <-highPriority:
handle(x)
case x := <-lowPriority:
handle(x)
}
}
-The question is irrelevant with enough processor power
(Update 9Oct2016) A very experienced Go programmer I talked with the other day thought that the theme was irrelevant if the processor has enough power and quite often enters idle. This was at a night out for a beer, also with others who didn’t agree on this. Here’s a summary (plus some) from our talk around the table.
Of course he is right, especially if it enters sleep quite quite often. A server goroutine will be able to serve all clients and the selection scheme is irrelevant. If all clients are satisfied then it’s fair, isn’t it? Yes and no. Because fairness isn’t a term that one would naturally relate to with this mindset.
(Horizontal scaling is when one adds more CPUs to get more power, vertical scaling is when a single CPU’s is used more efficiently.)
However, if the processor that’s sleeping quite quite often gets more to do and sleeps quite often, then just often and then seldom and then never, that’s when select’s selection algorithm becomes important. If it’s a random choice then any one client may never ever be served. For any definition of it this can’t be fair. (Exception: if the random generator for that select is a pseudorandom sequence (like 16 bits as ([0..(2exp16)-1=65535]) and during that sequence all values are seen and none twice.) The rest of the scenario is described elsewhere in this note. Short said: the prioritised ALT of occam makes it explicitly possible for occam programmers to make selection fair.
When writing this note I see another problem. That’s with buffered channels. With the nondeterministic / random algorithm of Go for select, then they also don’t need to think about what happens with clients writing into a many-to-one shared channel. A prioritized select would have moved the semantics of the select all the way to the input side(s) of the buffered channel. occam solved this with not having many-to-one channels, not buffered channels; only array of channels. So a server would do PRI ALT i=0 for N then listen on myArrayChan[i+1 rem N] – as already mentioned.
Fairness as defined
In the excellent Wikipedia article about Unbounded nondeterminism is discussed quite well ([19]). The definining paragraph goes like this (28Nov2016):
Discussion of unbounded nondeterminism tends to get involved with discussions of fairness. The basic concept is that all computation paths must be «fair» in the sense that if the machine enters a state infinitely often, it must take every possible transition from that state. This amounts to requiring that the machine be guaranteed to service a request if it can, since an infinite sequence of states will only be allowed if there is no transition that leads to the request being serviced. Equivalently, every possible transition must occur eventually in an infinite computation, although it may take an unbounded amount of time for the transition to occur. This concept is to be distinguished from the local fairness of flipping a «fair» coin, by which it is understood that it is possible for the outcome to always be heads for any finite number of steps, although as the number of steps increases, this will almost surely not happen.
I found this by reading the CSP article, where it’s stated that «The version of CSP presented in Hoare’s original 1978 paper was essentially a concurrent programming language rather than a process calculus. It had a substantially different syntax than later versions of CSP, did not possess mathematically defined semantics,[..] and was unable to represent unbounded nondeterminism.»
From Wikipedia : Unbounded nondeterminism : On the possibility of implementing unbounded nondeterminism we read «Edsger Dijkstra [1976] argued that it is impossible to implement systems with unbounded nondeterminism. For this reason, Tony Hoare [1978] suggested that ‘an efficient implementation should try to be reasonably fair.‘»
xC by XMOS
The xC language by XMOS [5], [6] (and in newer blog note here and here) is perhaps the most elegant of concurrent languages, after occam (…). But then, there is much the same designer (David May, and now also Ali Dixon).
Aside: Some updates
24Feb2021: Have a look at an xC example of not fair code, see 217:[Top_03 is not fair]
5Mar2018: see an example of fair handling of two clients by one server at xC code examples.
29Apr2019: I did send a query about all this at XCore Exchange: select, nondeterminism and deterministic properties. Maybe that post will make this a bit clearer.
This language also has select on channel inputs, ports, hardware events and timers. XMOS states, while describing an example (page 23 of [5]) that: «If both inputs become ready at the same time, only one is selected, the other remaining ready on the next iteration of the loop.» Page 47 of [6] states it differently: «If more than one of these inputs or transactions is ready then the choice of which is executed is made nondeterministically.» The first quote takes «the other» and «next iteration» into account. This is interesting, if there is a concern of «fairness» in it. More later.
The XMOS XCore processors have «deterministic thread execution», as they write in the introducery texts about them. Or «up to 8 concurrent, deterministic real-time tasks». Nondeterministic elements in the language and deterministic execution by the processor. If I don’t use select then the sum would be a deterministic system, just as required by the Ada Ravenscar Profile [1]? How much am I messing things up now?
(9.2015) The architecture has tiles with I/O, memory and logical cores and a shared communication fabric (xCONNECT). The memory on each tile has no cache. Since the I/O subsystem does not use the memory bus by having no DMA then there is no data bus contention. Therefore worst case execution time analysis is possible.
Will XCore plus full xC still become deterministic? More research: A core in an XMOS processer, the XCore, shares its cycles out to its possible eight threads. If only four of them may run, they mostly get a quarter of the cycles each. If they all wait for something arriving on a channel (another message, a port or a timer), then XMOS guarantees that any one thread will start to treat its event within a 3/4th of the total cycles. If only one waits, I assume it would take at most 1/4th of the cycles to deschedule the running thread. If eight threads run, the guarantee is still there, provided each thread does not want to use all the cycles that they potentially could.
Ref [7] states that «If more than four threads are active, the processing power is divided equally between the active threads; for example, if eight threads are active, each gets 62.5 MIPS and executes an instruction every 16ns.» Often, with other schedulers utilization cannot be 100%. An example is rate-monotonic scheduling [8], where 8 processes give a utilization of 8*(8√2 – 1) = 0.72 (72%), and the worst ever is 69%. However, fully used eight XCore threads, each of them may max use 1/8th of the total cycles. Overhead is zero, because the thread scheduler is implemented in hardware, and each thread has its own registers, so context switches are instantaneous. The sum of 8 times 1/8th is 100%!
Again, it goes like this: If I have one thread it gets max 1/4 of the cycles, two 2/4, three 3/4 and four all cycles. So parallel slackness for this processor means that coding single-threaded is 1/4 as good an idea as coding 4-threaded! Any thread you add after this cost nothing in utilization – be it 5, 6, 7 or 8 threads – still the scheduler is able to deliver all of its cycles to real processing!
20Apr2021: In 219:[3] the XUF216-512 (or XE216-512) processor has this limit at 5 logical tasks, not 4. This is connected with the length of the instruction pipeline. The first processor, like the one in the startKIT, XS1-U16A-128 (here) indeed has a four stage pipeline. This document states it very generally:
«The threads in an XCore are intended to be used to perform several simultaneous real- time tasks such as input-output operations, so it is important that the performance of an individual thread can be guaranteed. The scheduling method used allows any number of threads to share a single unified memory system and input-output system whilst guaranteeing that with n threads able to execute, each will get at least 1/n processor cycles. In fact, it is useful to think of a thread cycle as being n processor cycles.» … «The set of n threads can therefore be thought of as a set of virtual processors each with clock rate at least 1/n of the clock rate of the processor itself. The only exception to this is that if the number of threads is less than the pipeline depth p, the clock rate is at most 1/p.» from 141:[6].
No idle loop is needed, like with many other scheduling algorithms. That being said, one of four threads each gets double cycles compared to one of eight threads. So there is a trade-off. The extra four are free, provided the problem is composable to more than the four. I have discovered in a note from a SIG (Special Interest Group) at WoTUG-16 in Aberdeen in 1992 that if sampling frequencies of rate-monotonoc are harmonics (like 10 – 20 – 60 µs) and priorities are n, then if the remainder of a division of the two are zero, then 100% utilization is possible. I think this is a description that may be used for the XCore. I now know that XCore runs 100%! This architecture yields XCore schedulability as deterministic.
However, what’s going to happen after a thread has been scheduled may be nondeterministic if you use select! This makes perfect sense! A reader asked me to post a pointer to this note to the XCore Exchange. I did.
Pseudo-random choice, fairness and deadline assurance
Here is an example of the problem: an http server serves clients. We don’t need many clients to understand the problem. Two will suffice. They both try to be served as fast as they can. Immediately after having been served, they want to be served again. The job to be done is just to increment a number that each client holds and sends down to the server, which increments it and sends it back (by the way, that was an example of state-less programming). Is there a way to guarantee that both clients get served, not just one of them? I could model this in Promela, and all would be fine. By the help of the nondeterministic operator it will verify that there is no starvation. However, the criterion is that eventually any one will be served (I think it will reason by the help of temporal logic [9] to get to this conclusion, with words like always, until and eventually). They will not be served every other time, there is no pattern. One could be served a hundred times and the other one time, or worse a million times and the other one time, or even worse.. (still eventually holds, because there is no random selection in the nondeterministic choice in the Promela model. It’s nondeterministic.) As the Promela chapter above shows (with quote from Wikipedia), in the real world implementation (used by the simulator) a pseudorandom number generator is used. It delivers a number series that sooner or later repeats. So it would deliver as many even as odd numbers. And if one client is treated by even number selection and the other at odd number selection, then we’d have a fair server. And as long as the series starts at a truly random number (generated by the seed), it would only repeat the same sequence as often as the series’ periodicity. If you think this is interesting, read Wikipedia’s articles [10] and [11]. Fairness means that when competing for a resource, all are treated to a satisfactory degree. And if one starts to complain about it getting slow, all would complain. But there are other ways to make it fair, without nondeterministic operators, ie. without pseudorandom selection. Have clients log in while they need the server. They all stay through a session. So the server knows the set of clients, and their names are stored in a table. The index in the table is a client’s id. The server would search for clients to possibly serve, starting at the last index served plus one (it must wrap around, or index with modulo arithemtic). In the old days I did this in occam, running in boxes that we actually sold. I won’t write this up, since [12] covers it very well. And these days we could do it in Go or any language. Now, the question of deadline assurance. If you jump up to the «XC by XMOS» chapter’s final part, you will see that deadline assurance may not be correlated with nondeterministic (or pseudorandom) behaviour. You may have both!
Parallel programming, cognitive thinking and a mail sequence
This quote is from Marowka [13], page 53: MANY-CORE PROGRAMMING CHALLENGES Thinking in parallel
«Many-core programming demands new programming skills and a different kind of problem-solving thinking. Sequential programming is a deterministic and sequential process, so it arises intuitively from the way programmers solve problems using algorithms. In contrast, many-core programming is intrinsically a nondeterministic process. Parallelism requires the programmer to think in a way that humans find difficult. However, allowing nondeterminism in parallel programs is the key to achieving high-performance and scalable programs. A parallel program’s nondeterministic behavior is controllable, but must be used only when necessary. Moreover, it is possible to learn how to think in parallel and how to write bug-free parallel programs.»
I mailed Marowka and asked about this, and after that we have had several mails between us. He allowed me to be public about it. The first thing he did was to send me some «homework» [14] and [15]! I threw myself over the two papers and clipped what I thought interesting: Here are some statements from Bocchino et.al. [14]:
«In particular, deterministic algorithms must be expressible in a style that guarantees determinism, and nondeterministic behaviors, where desired, must be requested explicitly. (p1)
How to guarantee determinism in a modern object-oriented language?.. The key is to determine when concurrent tasks make conflicting accesses. The language can help provide this capability by enforcing structured parallel control flow (to make it easy to analyze which tasks can execute concurrently)… (p2)
How to specify explicit nondeterminism when needed?..First, any nondeterministic behavior must be explicit, e.g., using nondeterministic control statements; hence the term “deterministic by default.” (p2)
Algorithms that are deterministic overall may benefit from “locally nondeterministic” behaviors for higher performance. Some operations, such as associative…. (p4)
First, nondeterminism is explicitly expressed, e.g., using a nondeterministic control statement. (p5)»
[13] there: E. A. Lee. The problem with threads. Computer, 2006.
And here some by Wallis [15]
«YOUR BRAIN WHEN IT MULTITASKS
The switching of attention from one task to another, the toggling action, occurs in a region right behind the forehead called Brodmann’s Area 10 in the brain’s anterior prefrontal cortex, according to a functional magnetic resonance imaging (fMRI) study by Grafman’s team. Brodmann’s Area 10 is part of the frontal lobes, which «are important for maintaining long-term goals and achieving them,» Grafman explains. «The most anterior part allows you to leave something when it’s incomplete and return to the same place and continue from there.» This gives us a «form of multitasking,» he says, though it’s actually sequential processing. Because the prefrontal cortex is one of the last regions of the brain to mature and one of the first to decline with aging, young children do not multitask well, and neither do most adults over 60.»
I thought it very strange that Boccino [14] did not mention the CSP (Communicating Sequential Processes) algebra. And that I had also made a separate blog note 021 about reference E.A.Lee [13] there. I also did not understand that going from speaking about “anterior prefrontal cortex” and how it switches attention for us – to arguing that explicit nondeterministic operators will make multi-core programming easier to grasp. But Marowka did not seem to give up on me. He argued that «parallel programming is difficult. Period«, and that the programming community still had a long way to go. He said that «writing a parallel algorithms demands thinking in parallel.» He gave me two blocks of code Q1 and Q2 and asked if I could spot which could be parallelized. I couldn’t, like 50% of his students. I was pointed to Herb Sutter’s paper from 2005 [16] which states that parallelism is inevitable. I remembered the transputer days in the 1980-90’s, and since then and even now (2012) it seems like single processors are still developing alongside multi-core. But Marowka stated that «MPI and OpenMP are the de-facto programming models of the scientific community. All the others remain research projects or niche solutions. CSP likes BSP and others are still waiting for widespread recognition. Solutions like UPC, Intel solutions (Cilk, TBB, Ct), Microsoft TPL, but after that MPI.» I then understood that the two of us might see this from different perspectives. He from the MPI and OpenMP world (where those examples Q1 and Q2 are relevant). I see it from a «real-time» perspective. But we are both concerned about getting it right.
I am more interested in getting things done at all, I thought – and he about getting things done faster. Even if these are not orthogonal goals!
Of course it was interesting to me that I have been brought up with the view that «concurrency is easy. Period.» Or did they say the «parallelism is easy. Period.«? With the tools that I now know more about than many other thing, yes, I do feel that both are «easy». Especially when not «embarrasingly parallel». A real-time system never is embarraingly parallel. But then, getting this easyness to be seen by the others is hard. Are they the ones that are right? I then did this long paragraph in a mail: «But we seem to disagree a little. The CSP people (should I place myself in any group, I would probably be there) have always said that parallelism is easy. Period. These applications scale rather well, they may be single core, shared memory multicore or nonshared multicore, same code at application level. That also answers the heterogeneous answer. They are not embarrasingly parallel, which only is a special little group anyhow. (Google Go supports only shared memory multicore.) If occam is used for a real-time system or a typical multicore, of course speed is also wanted. And CSP is deterministic default with nondeterministic (and deterministic) choice. As far as I understand, nondeteministic choice is not readily available in MPI, so that makes that hard. Since CSP-type code (where occam-pi is the most adherring language, which also has barrier synchronisation and shared channels) may run alone or concurrently on one machine, it’s easy to tune down the number of processors as much as possible, without using virtual machines – and save energy. Since you do remember the Meiko machines and know about them, there must have been some reason why you in your life has come to the «opposite» conclusion. We can’t both be wrong or both be right with the same set of facts. There were some university professors at the conference (CPA-2012), as always, and they keep discussing this «is easy» thing, and reinforcing it. The biggest problem is when teaching parallelism comes after the basic constructs like conditional, looping, invariant handling etc. in the schools. In that group also belong seq and par they state, and also the alt/select. Also remember that in CSP (99% certain, but 100% certain for occam) all evaluations are side effect free, which makes things simpler. Also, aliasing is out of the language. But safe recursion is coming, since they now seem to accept dynamic memory handling. And most importantly, this leads to WYSIWYG semantics. Always. Some of this means that doubly linked lists may not be used, but those problems may be solved by rewriting the algorithm. This also means that no construct in the language ever needs busy polling, and there is no «notify all» to waste schedulings. Some of this should be tought before 14 they say, and some of it need not be tought at all, since it would just be preventing a whole group of errors to be present. And I believe they are right! But then, spotting your parallisable (or not) equations Q1 and Q2 is not easy. But it is a rather defined engineering discipline, to do analysis and design and find out about exactly what is parallelisable.» And then, at all the CPA and WoTUG conferences I have been to, the people haven’t been as self assured as it may sound like. Something is easy and something is in fact hard. Then comes this problem, then comes that. This solution, and that solution. But maybe this is even better? We certainly are not there. Neither the CSP community or the MPI community (I understand). Thanks Ami Morawka for a very enlightning mail sequence! And you said that we don’t disagree much at all. I think I understand that now.
Good and bad nondeterminism
I have written about this above. However, I did get a letter from a computer scientist and author the other day, stating this:
«I tend to say the functional correctness of a program should not depend on the choice made where there is a non-deterministic choice – but the temporal correctness of a program may.»
«..if you could show that any choice leads to temporal correctness then that would be fine. I tend to stress that determinism is not necessary – what we need is predictability. Of course one way to get predictability is to be deterministic, but this is not the only way»
This note could not be better summed up!
Other points
The Linux Completey Fair Scheduler
The Completely Fair Scheduler (CFS) is called SCHED_NORMAL in Linux and SCHED_OTHER in POSIX.
I don’t think this addresses the problem of fair handling of clients in servers, ie. handling the select choice operator. The CFS handles scheduling of when processes are allowed to run, to burn cycles.
See https://en.wikipedia.org/wiki/Completely_Fair_Scheduler – but also see SCHED_DEADLINE which is an Earliest Deadline First (EDF) scheduler.
Disclaimer
Please help me improve on any inaccuracies in this blog note. Even if all has an inaccurate form, I’d still like it to be correct. I have streched my limits on this one! Search phrases: non-determinsm non-deterministic nondeterminism nondeterministic [18] [19]
References
- Channels and rendezvous vs. safety-critical systems
- 009 – The «knock-come» deadlock free pattern
- Promela
- The Go Programming Language
- XC-Programming-Guide(X1009A) → https://www.xmos.ai/file/xmos-programming-guide
- XC-Reference-Manual(8.7-[Y-M]) → xC is C plus x References
- XS1-Architecture-Product-Brief → xC is C plus x References
- Rate-monotonic scheduling: en.wikipedia.org/wiki/Rate-monotonic_scheduling
- Temporal logic
- Random number generation
- Pseudorandom number generator
- Fair alting: www.cs.kent.ac.uk/projects/ofa/co538/anonqa/key-fair-alt.html
- Ami Marowka, Bar-Ilan University, Israel, “Back to Thin-Core Massively Parallel Computers”, IEEE Computer, Dec. 2011, pp 49-54
- Robert L. Bocchino Jr., Vikram S. Adve, Sarita V. Adve and Marc Snir, University of Illinois at Urbana-Champaign, «Parallel Programming Must Be Deterministic by Default». static.usenix.org/event/hotpar09/tech/full_papers/bocchino/bocchino.pdf
- Time Magazine, Claudia Wallis, Monday, Mar. 27, 2006, «The Multitasking Generation». www.time.com/time/magazine/article/0,9171,1174696,00.html
- Herb Sutter, «The free lunch is over», http://en.wikipedia.org/wiki/The_Free_Lunch_Is_Over and http://www.gotw.ca/publications/concurrency-ddj.htm
- Seymour Papert, «Mindstorms». All about LOGO – How it was invented and how it works. 1980. My book is from 1993: ISBN 978-0-465-04674-4 (2nd ed paper)
- http://en.wikipedia.org/wiki/Nondeterministic_programming
- https://en.wikipedia.org/wiki/Unbounded_nondeterminism#Fairness
- Pedram Hajesmaeeli (here), «A pattern for overcoming non-determinism of Golang select statement» (3May2019), see https://medium.com/@pedram.esmaeeli/a-pattern-for-overcoming-non-determinism-of-golang-select-statement-139dbe93db98