Multicore programmers must 'think different'

3/24/2011 5:55 AM EDT

"... human brain, an ultra-parallel computer, cannot makes sense of its sensory space unless it is temporally deterministic"

This is just a grandly-worded but bland assertion.

For a example of formally modelled non-determinism, see CSP.

If you are referring to the non-deterministic timing introduced by layering hierarchies of memories to try to emulate an infinite "tape", then you are right - this non-determinism is a bane.

I think non-deterministic ordering of events is very different from non-deterministic running times for sub-computations or instructions - the latter being the problem.

3/24/2011 12:10 PM EDT

yes Dave's a smart guy after all he did invent the transputer :D
they could do a lot worse than rush an invite have him on the panel as guest speaker and to raise his profile in the wider tech world.

its hard to believe but there are actually people out there that have never heard of him or his transputer innovation http://www.cs.bris.ac.uk/~dave/transputer.html
long before today's multi core/multi desktop CPU configurations become common place.

keep in mind too his law still seems true today :P
"May's Law

Software efficiency halves every 18 months, compensating Moore's Law."

http://en.wikipedia.org/wiki/David_May_(computer_scientist)

3/24/2011 12:20 PM EDT

oops dont know what happened there, this should have been lower down under the XMOS/OCCAM aka transputer reference

no relation to him although cool name, im sure you agree Jonathan :P

3/24/2011 3:41 PM EDT

Me: "... human brain, an ultra-parallel computer, cannot makes sense of its sensory space unless it is temporally deterministic"

Jonathan: "This is just a grandly-worded but bland assertion."

How so? Consider, for example, that the brain's 3-D visual system, would not work if the laws of optics were not deterministic. The brain expects visual signals to obey these laws as we move around in our environment. Without this determinism in nature, we would never learn anything.

My point is that events in a software system that are supposed to be deterministic should remain so always. Otherwise, you run into all sorts of reliability and software comprehension problems. The concurrent-threads model used by the multicore industry does not guarantee this sort of determinism and therein lies the major part of the problem. One man's opinion, of course.

3/25/2011 5:28 AM EDT

I cited two examples of nondeterminism - one by calculus model (CSP) and one by architecture implementation (memory hierarchies). One I believe causes a problem (the latter), the other I think does not.

I completely agree that "events that are supposed to be deterministic should remain so". But I cannot think of any examples where this is not true. Even non-deterministic timing from memory hierarchies is generally thoroughly documented and you can design around the worst-case to give you either asymptotic estimates or absolute bounds on program performance. And in some cases non-determinism is by design and therefore does not break your rule above.

If I were being really picky, your original statement demanded "temporal" determinism, whereas your follow-up claim relates to essentially spatial determinism.

With your final point - what is this "concurrent-threads model used by the multicore industry"? Which model are you referring to? Why does it not guarantee determinism? Why is determinism needed?

3/25/2011 5:29 AM EDT

Haha another David May?

David is my father by the way.

3/25/2011 7:43 AM EDT

cool, :D he does seem hard to find online generally...

you should get him to come here under "transputer dave"

and have him write some articles for EEtimes, im sure they would take them :P

and OC many people would love to read his thoughts and many subjects.

3/25/2011 6:56 PM EDT

The big nondeterminism-related issue with parallel programming is dealing with race conditions and timing. Depending on how quickly the different threads execute, you can get potentially completely different results. Compounding the problem is that such bugs are very difficult to reproduce, and may only occur under very unusual conditions.

Structures like caches do not affect the actual program result, assuming of course that there's no bugs in the caches. The only nondeterminism that occurs is with how long the program takes to execute.

In short, parallel programming can potentially make correctness nondeterministic.

3/24/2011 6:09 AM EDT

The point here seems to be that we need to come up with a model of concurrency which is easy enough for anyone to code with. E.g. a web "programmer".

Taking your example, web programmers are heavily insulated from the metal by so many layers that they are very often totally unaware what happens underneath. They are, however, rarely given enough rope to hang themselves.

The challenge to make this work for concurrent languages is a harder intellectual challenge for the designer of the tools - and requires a different way of thinking from the programmer.

Models do exist - the work done by Leslie Valiant on BSP and related models of computation are methods by which it is possible to achieve asymptotic efficiency in the mapping of for example the dreaded shared-memory model to massively-parallel hardware. It can work with other models of computation - it is a universal model of parallel computation which leaves the programmer as unable to make a noose for themselves as a web programmer is today.

It is a shame that so few of these ideas have been picked up and explored in the past 20 years.

Architectures need to better support vital primitives for concurrency efficiently and deterministically (e.g. thread synchronisation). See e.g. XMOS for examples of this.

Low-level languages need to express concurrency in an elegant and "exposed" form - see for example CSP as a computational model and OCCAM/XC or even languages such as Go for examples of how to achieve this. Apologies to the many languages I've missed out.

Higher-level languages "for the masses" will need to build on the techniques and work of "bridging"/"universal" models to create programming metaphors much in way the Turing model led to the programming metaphors for sequential computation.

3/24/2011 12:51 PM EDT

ooh i dont know , people just need to look off the beaten track for instance did you ever look at and try REBOL (the internet and GUI programming language) by Carl Sassenrath, who also did the Amiga message passing OS back in the day

http://www.rebol.com/docs/reference.html

that is making slow progress by other standards but is really good for quickly prototyping many a GUI and remote networked control interface , and wrapping your generic C,assembly routines library's etc in a nice simple cross plaform script.

he's also against "Software complexity pollution: just say no to "the standard of practice".
"
http://www.rebol.com/article/0497.html

3/25/2011 6:36 AM EDT

I would even go one step further. In 1988 (that's already years after Hoare wrote the book on CSP), Chandy and Misra (Uni TX, Austin) write "Parallel Program Design", basically a book on using UNITY (a kind of formal notation) for specifiying what a program should do, not on how it should do it. What the book made clear to me, is that there are no parallel algorithms. You have algorithms and they have sequential as well as parallel (or mixed) implementations. Often the parallel version is a lot easier and simpler. Even a quicksort is very easy to rewrite in a parallel version.

The issue is that the processor architects and hence the programming language developers suffer from the "von Neuman" syndrome. Hence, they can only think in terms of shared memory, shared state spaces and sequential logic. And of course, this is hard because you must control the state space in time to keep it consistent.
If you think in terms of concurrency, the problem largely goes away because the state spaces become local. How does one achieve determinism? By synchronisation, ths makes the logic time-independent. Most RTOS do this quite well. Thread based programming doesn't and that's why it is hard. Unfortunately, this bad reputation has spread to the whole notion of parallel programming. For the wrong reasons. Think parallel, optimise sequentially (because you exploit local propertie. Makes the cod emaybe faster, but you loose the scalability that a good concurrent programming model offers.

4/19/2011 6:09 AM EDT

I agree that the Economics have to be right, but practical experiences have shown that Computer Science students find it harder to program in parallel than in serial, FACT. I hence do not agree with Prof. Patt's assertion. Also, the human brain, while parallel in its functioning, is much more comfortable with deterministic sequential behaviour. As for the parallel programming question, it has to be a decision based on return on investment, yes. High level APIs or skeletons have to be developed for the average programmer for the sake of productivity, while low level parellel programming should be the craft of a few, when it is economically viable to do so.

4/19/2011 6:55 AM EDT

I tend to disagree. If you know that the brain essentially works as a pattern matching neural net, then you know that if you train it in certain way, the pattern 'sticks' and the nit only seems like sequential thinking is more natural. For every carpenter, every problem can be solved with a hammer and a nail.
I speak of personal experience. I only learned to program in parallel 10 years after I had learned to program (sequentially). Then I wanted to learn occam (the forgotten language based on CSP). I didn't get anywhere even after 1 month. Then I went to a training course and during the first exercise I made the mental switch, the typical Ha-Ha Erlebniss. From then one, I never understood my people wanted to make life so difficult by forcing everything to be programmed sequentially. The world is parallel and software programs are essentially models of such a world, so why not program in a natural way?

4/20/2011 4:56 AM EDT

@Eric Verhulst_Altreonic, I heard such stories before (the Damascene conversion moment etc.) but they are the exception rather than the rule in my experience. Yes, the brain is parallel in its functionning, that's why it's good at tasks such as pattern matching but try to ask 100 kids to do 2 or 3 tasks at the same time and you'll see :-) Some can be trained to do it, but most would struggle.

On a side comment, do not they say women are better at multi-tasking than men? Should not women then be better parallel programmers? May be we should invest in female parallel programmers :-)

4/20/2011 5:11 AM EDT

I certainly would love to see more female engineers. Never understood why they shy away from this no-muscles-involved domain.
But to come back to the topic. Concurrent programming (the CSP type of paradigms) is exactly a way to reduce the number of things you have to keep in your head. It is a divide and conquer strategy. While a sequential program has a huge state-space to keep track off in the head, concurrency provides modularity and smaller state spaces. Each process can be a small, dedicated function. This reduces the global space problem to only look at how the modules are interacting. And as the protocol is then fixed, one can change any module without having to look at the state space of the other modules. Our programming model even achieves this across network and processor boundaries. How do you handle this with a single sequential thread on each processor? It is vastly more complex and close to impossible.

3/25/2011 3:23 PM EDT

What you need is to learn and teach parallelism at the highest level and with an appropriate language. Then the parallel programming nature of problems become obvious and not hard at all.

I don't know what happened to him after all these years but Jon Webb (from CMU's Vision and Autonomous Systems Center) did some GREAT work on this. The Adapt language was the perfect example of what I am talking about. A general language that let's you think about and break down the inherently parallel processes in image processing into a very simple language and set of constructs that can then be compiled on to any machine architecture efficiently, no matter how linear or how parallel that architecture is and take full advantage of any parallelism afforded. You could run on a basic Intel x86 machine, a toroidal iWarp of any number of nodes, or even a Cray Y-MP and you saw very efficient scaling in terms of processor resources at your disposal.

Parallel Programming is easy when you know the right language to use. Developing those languages is the hard part and a part of computer science (in my opinion of course) that has been withering away for at least 15 years... I believe due to the mostly brute-force, inelegant methods thrown at the ever increasing resources available. Elegance is gone... mapping elegance onto crude architectures with bad compilers makes parallel programming appear hard...

4/1/2011 9:20 AM EDT

This kind of tools have been around since 1970s ...