Parallel programming in itself is not hard. It's just that most of today's computing has origins in single-pipeline architectures, and parallelism came to be a massive layer of hacks on top of it.
That's why I chuckle a bit when parallel programming is reduced to discussions about barriers and mutexes -- paradigms such as dataflow don't need these kludges. That is, until you try to implement dataflow in a von-Neumann architecture (and today you have little choice).
We can probably agree that moving limbs isn't intrinsically "hard". But it probably would be if our biological makeup was built for photosynthesis.
One of the easiest ways to create a parallel program is to split your data, or split your processing. When you split your data, you can just apply the same algorithm to both sets, and re-integrate the processed data. This necessitates that the processing can be done apart, however. Graphics cards already do this. They have many, many cores that are used for 3d graphics. You can easily split the work done on the screen into small chunks, process these individually, then put it back together. The other way is to have one core do one set of work, and another core do another set. The algorithms should process a similar amount of data though, otherwise you are wasting processing power.
The other problem is representation of data in the programming language. Objects, which are used in a lot of programming languages, can be hard to use when it comes to parallelism. An object can only be operated on by one algorithm at a time, and to achieve parallelism, you must use concurrency (locking). You can switch to a different paradigm away from OOP (object orientated programming), to something like FP (functional programming). Since everything is a function, with data just being passed around, you can abstract a program to multiple cores in a more natural way. FP comes with its own difficulties though. This isn't to say parallel programs can't be written in OOP programs successfully, it just requires a different mindset to normal programming.
And data parallelism is the type of thing that gets called "embarrassingly parallel" a lot, if the data is independent enough to be easy to partition into lots of parallel bits.
Not in my experience. I've seen "embarrassingly parallel" used only to describe when an entire application can be divided up and they never need to communicate again until the end. That is obviously data parallel, but "data parallelism" is also used for finer granularities such as SIMD operators, or parallelizing independent loop iterations. Such things are not considered embarrassingly parallel because the granularity can be fine enough that the synchronization costs can still dominate.
I don't disagree. That's sort of what I said: often data parallelism is what is called "embarrassingly parallel", but there are certainly plenty of cases of data parallelism which are not embarrassingly parallel. I would say that "embarrassingly parallel" problems are a subset of "data parallel" problems.
b) GPUs are still first and foremost special purpose hardware. Few applications are benefitting from moving all your data over to your graphics memory, pushing it through a broad but slow pipe and copying everything back to your CPU. You need to pull out all the low-level stops to get the most out of the hardware, which means dealing with really low-level libraries. CUDA has something like 7 types of memory locations you can declare for your data to sit in and some are calling OpenCL too abstract.
Dataflow does something need barriers and synchronization if you have to deal with parallel data sources. If you have sources of data coming in independently of each other, you sometimes have to contend with the fact that some of the paths might be faster than the other, and the right data might not be able to be paired without some form of synchronization.
Even if your dataflow application does not need synchronization, then you need to be able to reason about the fact that you have inherent asynchrony when you go to look at your results. That is, you may see this item and that item paired together - is that a valid result? The kind of reasoning required to figure that out is similar to what's required in, say, multithreaded programming.
IMHO, the real breakthrough with non-threading-based concurrency like message passing or STM or any of the other more recent primitives isn't that they make concurrency issues "go away"; it is that they reduce the complexity of implementing concurrent programs from exponential in the number of instructions to polynomial in the number of instructions. You'll probably never get to entirely stop thinking about race conditions, but they're much easier to deal with in Erlang, for instance, where there's only a very limited number of ways to create a race condition, as opposed to how there's only a very limited number of ways to fail to create a race condition in imperative-mutable threaded programming. It isn't made trivial, if you try to push it isn't necessarily even easy, but it is made feasible.
You don't need to be using Earlang to greatly simplify parallel coding though message passing. A lot of fairly clean C code started by using the man thread spawns worker thread who pushes results to a message queue. And then got messy because they stopped using messages for some side channel communication.
"And then got messy because they stopped using messages for some side channel communication."
... can't happen in pure-Erlang code. Of course there's nothing you can do in Erlang or Haskell that you can't do in pure C, but the problem is that if you are working in C you can't ever quite be sure that something somewhere accidentally mutated a value, when the language makes it so easy. (And let's not talk about C++.) Some of the Haskell leaders call it "wearing the hair shirt".
This is extended agreement, by the way, not a disagreement. If you are stuck in C, there are far worse things you can do that try to impose your own message-passing paradigm, just as there are an awful lot of object-oriented C programs in the world.
"an awful lot of object-oriented C programs in the world"
IMO, the good parts of object-oriented programming was applying the constraints of mulithreaded messaging passing to the single threaded world. Really clean multithreaded code tends to be extremely decoupled and treat each message is something to be decoded not blindly followed. Yet somehow that fell to the point where using lots of getter/setter are considered acceptable.
PS: That could actually be a good metric how many objects do you use that don't have a single getter or setter.
I agree. My problem is when people say that you don't have to consider concurrency and synchronization at all. And I also agree that such abstractions make the reasoning significantly easier - much as reasoning about the flow of a sequential program is significantly easier with structure programming than with code that has gotos all over the place.
It's interesting in that in the supercomputing world the message passing model has been popular for decades, but not by choice. It was the only way to get good performance. But the holy grail has always been shared memory, not message passing. But perf for shared memory applications has continued to be horrible. But anyone who has experience writing a message passing and a shared memory version almost always concedes the shared memory version is easier.
Large scale parallel message passing apps are extremely difficult to get right. Most people just haven't done it. With that said, some of the difficulties in the past where tied to the fact that message passing was done with a weak type system, no contracts (I sent you message, but how do I know you're ever going to respond to it?), and weak support for gather/scatter.
AFAICT, not having done much at all with Erlang, it deals nicely with the type system issue, but contracts are still a problem. Gather/scatter is partially assisted in the same way that PM/FM handled it in the past (you get to write code to pull messages out of your mailbox).
My prediction is that if message passing does take off in a big way, we'll see a pretty strong backlash to shared memory with functionality, such as type ownership and data representation synthesis. Unfortunatley, most of this research is ignored in favor of the more popular functional work (which in itself is good, just not currently balanced in the language community by other types of thinking).
Dataflow means a language or machine who's execution is driven by the availability of data.
In a dataflow computational model you do not have the concept of memory.
In a Von Neumann architecture (viz. your current CPU) execution is determined by the previous instruction. Data is stored in a global, randomly accessible memory space.
Synchronizing two data streams in dataflow is just a matter of having an instruction with two inputs. The very semantics of your machine tells you the node's instruction will only trigger when both its inputs are available.
Critical systems with the problems you described are often written in dataflow languages for exactly these reasons. Citing wikipedia:
Lustre is a formally defined, declarative, and synchronous dataflow programming language for programming reactive systems. [...] It is now used for critical control software in aircraft, helicopters, and nuclear power plants.
What other side is there to "parallel programming"? How many cases of parallel programming are there, in which you need no concurrency and synchronization at all?
Dataflow architectures and languages for example. Or even vanilla SIMD instructions.
The heart of the issue is that von-Neumann architectures are really not well suited to doing parallel programming: global PC in a single random access read/write memory. Any modification you make to that model to duplicate one module will introduce some heavy concurrency issues for you to deal with. For example multi-threading gives you multiple PC in the same memory space, leading to races, deadlocks, starvation etc.
Compare this to simple SIMD. You do a parallel operation float4 + float4 without any need for concurrency or synchronization.
But even in dataflow architectures (for example, the float4+float4 example) there are places where you want the different paths to meet. That's where synchronization (a barrier) is needed, as both results need to be available before the operation can be stared.
Of course in the case of SIMD this nicely happens internally in the hardware so nothing can go wrong, but in more complicated cases, for example if you're programming CUDA you need to care about it sometimes.
I agree that an alternative hardware architecture could probably solve this, but that is taking it a bit far and doesn't help solving any immediate problems.
Even if you have merged paths in dataflow and you don't need a barrier, it can be difficult to reason about. Specifically, it's difficult to figure out what a legal result even is.
But even in dataflow architectures (for example, the float4+float4 example) there are places where you want the different paths to meet. That's where synchronization (a barrier) is needed, as both results need to be available before the operation can be stared.
A dataflow architecture should be doing this in hardware -- don't issue an instruction for execution until all of its operands have been reported. The point is that it's not something the programmer needs to be explicitly concerned about.
"should be", yes, let's move our problems to the hardware guys. I'm all for it.
But hardware takes long to develop (if practical at all; a hw implementation might become to slow and expensive), and even longer to be mainstream, so I don't really see changing the hardware as a solution.
Someone had to do the hard work of reasoning about concurrency and enforcing synchronization; it doesn't come for free. In the case of SIMD instructions, it was the processor designers.
With well designed interfaces, parallel programming can be easier. But such interfaces abstract away the need to consider concurrency and synchronization - mostly. If you use the constructions outside of the bounds where safety is promised, then all bets are off. For example, parallelizing for loops with independent iterations with OpenMP is trivial, and you don't have to consider concurrency and synchronization. But once you provide non-independent loops, everything blows up and now those things are very important.
Agreed, the cost is shifted to the back-end. But sometimes it is worth to pay that cost up-front, cfr the memory management debate.
Synchronization and concurrency are much simpler in a system where you do have guarantees. No amount of interfaces or libraries will indeed make OpenMP in C safe, but no amount of hacks are going to make a fine-grained acyclic data flow graph deadlock or share state. The backend of the latter can pay the upfront cost of optimizing the shit away, for example no-copy optimizations, in a safe environment.
One of the biggest research effort in dataflow at MIT came in the aftermath of Multics; the ambitious SMP time-sharing OS research project that later spawned UNIX. citing: http://en.wikipedia.org/wiki/Jack_Dennis
Synchronization and concurrency are much simpler in a system where you do have guarantees.
I agree wholeheartedly, but there is a consequence that cannot be ignored: the resulting programming model is less expressive. The consequence of providing those guarantees is that there are something programmers just can't do. It's a trade-off, and I think we're still exploring how to provide a programming model that both abstracts away the complexity while still providing an expressive enough programming model to be useful in most circumstances.
You are right because the current hardware is biased towards sequential computation where threads&locks are the most efficient. This gives rise to situations where a handful of specialists work years on giving you that one lockless queue in the JVM. They would indeed not give you that edge in any higher-level programming model. It does not help the average programmer however.
Our exploration of programming models seems to be stuck in the current processor architecture, which was designed for sequential work with some stuff bolted on to make it run parallel. I could say John Backus' speech is becoming relevant again.
This is not ivory tower dreaming. The GPUs have made insane progress because they weren't tied to any computational model to start with.
In other words, not being able to do some things is often exactly what is needed to go forward. I wouldn't for the world want to introduce shared memory in Erlang, nor would I want pointer arithmetic under Java's GC.
Take for example problems you can solve with map-reduce. Very easy to parallelize. From the application developers point of view there is no concurrency or synchronization necessary, because it was already solved in general by the framework.
Unfortunately, there are lots of problems, where this is not possible. For example, for a distributed concensus problem the conflict resolution is application-specific.
Parallel programming in itself is not hard. It's just that most of today's computing has origins in single-pipeline architectures, and parallelism came to be a massive layer of hacks on top of it.
That's why I chuckle a bit when parallel programming is reduced to discussions about barriers and mutexes -- paradigms such as dataflow don't need these kludges. That is, until you try to implement dataflow in a von-Neumann architecture (and today you have little choice).
We can probably agree that moving limbs isn't intrinsically "hard". But it probably would be if our biological makeup was built for photosynthesis.
If parallel programming can be made easy using some exotic technique, would the first people to use that technique commercially be ATI and nVidia?
One of the easiest ways to create a parallel program is to split your data, or split your processing. When you split your data, you can just apply the same algorithm to both sets, and re-integrate the processed data. This necessitates that the processing can be done apart, however. Graphics cards already do this. They have many, many cores that are used for 3d graphics. You can easily split the work done on the screen into small chunks, process these individually, then put it back together. The other way is to have one core do one set of work, and another core do another set. The algorithms should process a similar amount of data though, otherwise you are wasting processing power.
The other problem is representation of data in the programming language. Objects, which are used in a lot of programming languages, can be hard to use when it comes to parallelism. An object can only be operated on by one algorithm at a time, and to achieve parallelism, you must use concurrency (locking). You can switch to a different paradigm away from OOP (object orientated programming), to something like FP (functional programming). Since everything is a function, with data just being passed around, you can abstract a program to multiple cores in a more natural way. FP comes with its own difficulties though. This isn't to say parallel programs can't be written in OOP programs successfully, it just requires a different mindset to normal programming.
The high-performance computing community calls what you described "data parallelism": http://en.wikipedia.org/wiki/Data_parallelism
And data parallelism is the type of thing that gets called "embarrassingly parallel" a lot, if the data is independent enough to be easy to partition into lots of parallel bits.
Not in my experience. I've seen "embarrassingly parallel" used only to describe when an entire application can be divided up and they never need to communicate again until the end. That is obviously data parallel, but "data parallelism" is also used for finer granularities such as SIMD operators, or parallelizing independent loop iterations. Such things are not considered embarrassingly parallel because the granularity can be fine enough that the synchronization costs can still dominate.
I don't disagree. That's sort of what I said: often data parallelism is what is called "embarrassingly parallel", but there are certainly plenty of cases of data parallelism which are not embarrassingly parallel. I would say that "embarrassingly parallel" problems are a subset of "data parallel" problems.
I guess my quibble is that, in my experience, the frequency that problems are "embarrassingly parallel" is so small that I never use the term.
A fair point. I normally don't use the term myself either, but I hear it thrown around a good bit.
a) They have, ATI implemented Brook+
b) GPUs are still first and foremost special purpose hardware. Few applications are benefitting from moving all your data over to your graphics memory, pushing it through a broad but slow pipe and copying everything back to your CPU. You need to pull out all the low-level stops to get the most out of the hardware, which means dealing with really low-level libraries. CUDA has something like 7 types of memory locations you can declare for your data to sit in and some are calling OpenCL too abstract.
Dataflow does something need barriers and synchronization if you have to deal with parallel data sources. If you have sources of data coming in independently of each other, you sometimes have to contend with the fact that some of the paths might be faster than the other, and the right data might not be able to be paired without some form of synchronization.
Even if your dataflow application does not need synchronization, then you need to be able to reason about the fact that you have inherent asynchrony when you go to look at your results. That is, you may see this item and that item paired together - is that a valid result? The kind of reasoning required to figure that out is similar to what's required in, say, multithreaded programming.
IMHO, the real breakthrough with non-threading-based concurrency like message passing or STM or any of the other more recent primitives isn't that they make concurrency issues "go away"; it is that they reduce the complexity of implementing concurrent programs from exponential in the number of instructions to polynomial in the number of instructions. You'll probably never get to entirely stop thinking about race conditions, but they're much easier to deal with in Erlang, for instance, where there's only a very limited number of ways to create a race condition, as opposed to how there's only a very limited number of ways to fail to create a race condition in imperative-mutable threaded programming. It isn't made trivial, if you try to push it isn't necessarily even easy, but it is made feasible.
You don't need to be using Earlang to greatly simplify parallel coding though message passing. A lot of fairly clean C code started by using the man thread spawns worker thread who pushes results to a message queue. And then got messy because they stopped using messages for some side channel communication.
What Erlang brings you is precisely that...
"And then got messy because they stopped using messages for some side channel communication."
... can't happen in pure-Erlang code. Of course there's nothing you can do in Erlang or Haskell that you can't do in pure C, but the problem is that if you are working in C you can't ever quite be sure that something somewhere accidentally mutated a value, when the language makes it so easy. (And let's not talk about C++.) Some of the Haskell leaders call it "wearing the hair shirt".
This is extended agreement, by the way, not a disagreement. If you are stuck in C, there are far worse things you can do that try to impose your own message-passing paradigm, just as there are an awful lot of object-oriented C programs in the world.
"an awful lot of object-oriented C programs in the world"
IMO, the good parts of object-oriented programming was applying the constraints of mulithreaded messaging passing to the single threaded world. Really clean multithreaded code tends to be extremely decoupled and treat each message is something to be decoded not blindly followed. Yet somehow that fell to the point where using lots of getter/setter are considered acceptable.
PS: That could actually be a good metric how many objects do you use that don't have a single getter or setter.
I agree. My problem is when people say that you don't have to consider concurrency and synchronization at all. And I also agree that such abstractions make the reasoning significantly easier - much as reasoning about the flow of a sequential program is significantly easier with structure programming than with code that has gotos all over the place.
In fact, I made a similar argument in the conclusion of my dissertation (first full paragraph on page 96): http://people.cs.vt.edu/~scschnei/papers/scott_dissertation....
It's interesting in that in the supercomputing world the message passing model has been popular for decades, but not by choice. It was the only way to get good performance. But the holy grail has always been shared memory, not message passing. But perf for shared memory applications has continued to be horrible. But anyone who has experience writing a message passing and a shared memory version almost always concedes the shared memory version is easier.
Large scale parallel message passing apps are extremely difficult to get right. Most people just haven't done it. With that said, some of the difficulties in the past where tied to the fact that message passing was done with a weak type system, no contracts (I sent you message, but how do I know you're ever going to respond to it?), and weak support for gather/scatter.
AFAICT, not having done much at all with Erlang, it deals nicely with the type system issue, but contracts are still a problem. Gather/scatter is partially assisted in the same way that PM/FM handled it in the past (you get to write code to pull messages out of your mailbox).
My prediction is that if message passing does take off in a big way, we'll see a pretty strong backlash to shared memory with functionality, such as type ownership and data representation synthesis. Unfortunatley, most of this research is ignored in favor of the more popular functional work (which in itself is good, just not currently balanced in the language community by other types of thinking).
Your last paragraph is talking about the languages community only, correct? In my experience, functional programming is still exotic in the HPC world.
Yes. It's becoming less exotic in the HPC world, but still greatly lags in popularity compared the languages community world.
Dataflow means a language or machine who's execution is driven by the availability of data. In a dataflow computational model you do not have the concept of memory.
In a Von Neumann architecture (viz. your current CPU) execution is determined by the previous instruction. Data is stored in a global, randomly accessible memory space.
Synchronizing two data streams in dataflow is just a matter of having an instruction with two inputs. The very semantics of your machine tells you the node's instruction will only trigger when both its inputs are available.
Critical systems with the problems you described are often written in dataflow languages for exactly these reasons. Citing wikipedia:
Lustre is a formally defined, declarative, and synchronous dataflow programming language for programming reactive systems. [...] It is now used for critical control software in aircraft, helicopters, and nuclear power plants.
Dataflow hardware is not the only realization of the dataflow programming model.
It is not "parallel programming", which is hard. Concurrency and synchonization is.
What other side is there to "parallel programming"? How many cases of parallel programming are there, in which you need no concurrency and synchronization at all?
Dataflow architectures and languages for example. Or even vanilla SIMD instructions.
The heart of the issue is that von-Neumann architectures are really not well suited to doing parallel programming: global PC in a single random access read/write memory. Any modification you make to that model to duplicate one module will introduce some heavy concurrency issues for you to deal with. For example multi-threading gives you multiple PC in the same memory space, leading to races, deadlocks, starvation etc.
Compare this to simple SIMD. You do a parallel operation float4 + float4 without any need for concurrency or synchronization.
But even in dataflow architectures (for example, the float4+float4 example) there are places where you want the different paths to meet. That's where synchronization (a barrier) is needed, as both results need to be available before the operation can be stared.
Of course in the case of SIMD this nicely happens internally in the hardware so nothing can go wrong, but in more complicated cases, for example if you're programming CUDA you need to care about it sometimes.
I agree that an alternative hardware architecture could probably solve this, but that is taking it a bit far and doesn't help solving any immediate problems.
Even if you have merged paths in dataflow and you don't need a barrier, it can be difficult to reason about. Specifically, it's difficult to figure out what a legal result even is.
But even in dataflow architectures (for example, the float4+float4 example) there are places where you want the different paths to meet. That's where synchronization (a barrier) is needed, as both results need to be available before the operation can be stared.
A dataflow architecture should be doing this in hardware -- don't issue an instruction for execution until all of its operands have been reported. The point is that it's not something the programmer needs to be explicitly concerned about.
A dataflow architecture should be doing this in hardware -- don't issue an instruction for execution until all of its operands have been reported.
There is still a need for application-level synchronization. For example, to keep the same money from being withdrawn from a bank account twice.
"should be", yes, let's move our problems to the hardware guys. I'm all for it.
But hardware takes long to develop (if practical at all; a hw implementation might become to slow and expensive), and even longer to be mainstream, so I don't really see changing the hardware as a solution.
Someone had to do the hard work of reasoning about concurrency and enforcing synchronization; it doesn't come for free. In the case of SIMD instructions, it was the processor designers.
With well designed interfaces, parallel programming can be easier. But such interfaces abstract away the need to consider concurrency and synchronization - mostly. If you use the constructions outside of the bounds where safety is promised, then all bets are off. For example, parallelizing for loops with independent iterations with OpenMP is trivial, and you don't have to consider concurrency and synchronization. But once you provide non-independent loops, everything blows up and now those things are very important.
Agreed, the cost is shifted to the back-end. But sometimes it is worth to pay that cost up-front, cfr the memory management debate.
Synchronization and concurrency are much simpler in a system where you do have guarantees. No amount of interfaces or libraries will indeed make OpenMP in C safe, but no amount of hacks are going to make a fine-grained acyclic data flow graph deadlock or share state. The backend of the latter can pay the upfront cost of optimizing the shit away, for example no-copy optimizations, in a safe environment.
One of the biggest research effort in dataflow at MIT came in the aftermath of Multics; the ambitious SMP time-sharing OS research project that later spawned UNIX. citing: http://en.wikipedia.org/wiki/Jack_Dennis
Synchronization and concurrency are much simpler in a system where you do have guarantees.
I agree wholeheartedly, but there is a consequence that cannot be ignored: the resulting programming model is less expressive. The consequence of providing those guarantees is that there are something programmers just can't do. It's a trade-off, and I think we're still exploring how to provide a programming model that both abstracts away the complexity while still providing an expressive enough programming model to be useful in most circumstances.
You are right because the current hardware is biased towards sequential computation where threads&locks are the most efficient. This gives rise to situations where a handful of specialists work years on giving you that one lockless queue in the JVM. They would indeed not give you that edge in any higher-level programming model. It does not help the average programmer however.
Our exploration of programming models seems to be stuck in the current processor architecture, which was designed for sequential work with some stuff bolted on to make it run parallel. I could say John Backus' speech is becoming relevant again.
This is not ivory tower dreaming. The GPUs have made insane progress because they weren't tied to any computational model to start with.
In other words, not being able to do some things is often exactly what is needed to go forward. I wouldn't for the world want to introduce shared memory in Erlang, nor would I want pointer arithmetic under Java's GC.
I don't disagree, I just think the limitations should be stated.
Then let's agree to agree. :)
Take for example problems you can solve with map-reduce. Very easy to parallelize. From the application developers point of view there is no concurrency or synchronization necessary, because it was already solved in general by the framework.
Unfortunately, there are lots of problems, where this is not possible. For example, for a distributed concensus problem the conflict resolution is application-specific.
It is not "running fast" which is hard. Moving your legs up and down very fast is.
It is a bad example.
"Running fast" is a subset of "moving your legs up and down."
What do you do about it? Why, use Erlang! :-D