6 ms·

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

by Animus7 15y ago

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.

wisty 15y ago
If parallel programming can be made easy using some exotic technique, would the first people to use that technique commercially be ATI and nVidia?
- keeperofdakeys 15y ago
  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.
  - scott_s 15y ago
    The high-performance computing community calls what you described "data parallelism": http://en.wikipedia.org/wiki/Data_parallelism http://en.wikipedia.org/wiki/Data_parallelism
    - dkersten 15y ago
      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.
      - scott_s 15y ago
        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.
        dkersten 15y ago
        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.
        scott_s 15y ago
        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.
        15y ago
- yvdriess 15y ago
  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.
scott_s 15y ago
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.
- jerf 15y ago
  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.
  - Retric 15y ago
    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.
    - jerf 15y ago
      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.

by Animus7 15y ago

wisty 15y ago

If parallel programming can be made easy using some exotic technique, would the first people to use that technique commercially be ATI and nVidia?

keeperofdakeys 15y ago
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.
- scott_s 15y ago
  The high-performance computing community calls what you described "data parallelism": http://en.wikipedia.org/wiki/Data_parallelism http://en.wikipedia.org/wiki/Data_parallelism
  - dkersten 15y ago
    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.
    - scott_s 15y ago
      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.
      - dkersten 15y ago
        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.
        scott_s 15y ago
        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.
        15y ago
yvdriess 15y ago
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.

scott_s 15y ago

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.

jerf 15y ago
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.
- Retric 15y ago
  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.
  - jerf 15y ago
    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.