Four Reasons Why Parallel Programs Should Have Serial Semantics(cilk.com)
cilk.com
Four Reasons Why Parallel Programs Should Have Serial Semantics
http://www.cilk.com/multicore-blog/bid/7659/Four-Reasons-Why-Parallel-Programs-Should-Have-Serial-Semantics
6 comments
I understand why some people want sequential semantics in parallel programs: it's very easy to reason about, especially for those who are used to sequential reasoning (like most imperative programmers). Certainly, if your goal is to use parallelism to speed up your existing software (and this is, indeed, Cilk's goal) then it makes lots of sense.
But most software programs can accept a little nondeterminism. Object-oriented design (at least, GOOD design) is built around the fact that your object's methods might be called at any time; you're just providing an interface. So (this was a programming language idea I was working on for a while) why don't we make it work that way? Make all method calls asynchronous, make methods transactions upon objects, and just schedule as many method calls in parallel as you can get your hands on. Good for server design, potentially good for parallelizing existing code (you'd still have to go through it and make sure it made sense -- no reaching into other people's objects and tweaking their internal state, etc.)
I guess my point is that while serial equivalence is a strong property, it's not necessary for many programs, and it completely prevents the existence of some, especially server-type programs.
But most software programs can accept a little nondeterminism. Object-oriented design (at least, GOOD design) is built around the fact that your object's methods might be called at any time; you're just providing an interface. So (this was a programming language idea I was working on for a while) why don't we make it work that way? Make all method calls asynchronous, make methods transactions upon objects, and just schedule as many method calls in parallel as you can get your hands on. Good for server design, potentially good for parallelizing existing code (you'd still have to go through it and make sure it made sense -- no reaching into other people's objects and tweaking their internal state, etc.)
I guess my point is that while serial equivalence is a strong property, it's not necessary for many programs, and it completely prevents the existence of some, especially server-type programs.
It's a shame the CSP style of tackling parallel programming hasn't caught on more. The Bell Labs guys know how to do this, see their languages Alef and Limbo. Channels, message passing, etc. Also, a UK university used to have some nice slides about doing the same thing in Occam, including an O(1) "sort pump". They all inherit the concept from Hoare's CSP. Perhaps now some of them, rob, ken, etc., have moved to Google we'll see a resurgence with it.
There is this idea that the current approach to parallel programming is wrong. When spawning a thread, there is instantly a huge space of possible paths for the program to go through. The coder then proceeds to prune off all paths that will lead to bad results, with the usual arsenal of mutex, semaphores, locks etc. etc. It's intellectually unbearable.
The alternative would be to explicitly specify which paths are allowable, rather than allow them all and then forbid which isn't.
I don't know how that would work, I don't remember who said it. Still, it feels good.
The alternative would be to explicitly specify which paths are allowable, rather than allow them all and then forbid which isn't.
I don't know how that would work, I don't remember who said it. Still, it feels good.
Has anyone read the section in Beautiful Code where one of haskell's designers talks about STM in haskell? I thought the code looked pretty neat. It is a very smooth serial semantic for parallel programming, and really fits the beautiful criteria.
Unfortunately, I've recently read that STM is turning out to have too much overhead in practical applications. Hope they figure it out.
Unfortunately, I've recently read that STM is turning out to have too much overhead in practical applications. Hope they figure it out.
I've read Simon Peyton Jones's Beautiful Code excerpt (http://lambda-the-ultimate.org/node/1964 for those who need it), and it's very nice.
I would be interested in the "too much overhead" article -- can you track it down? I've been researching STM for a while and seen a lot of papers focused on performance and such, so I'd be surprised if whatever the article claims are the problems are not fixable in the long term.
(STM can be nearly reduced to "taking locks", especially if you are compiling, so it really shouldn't be worse than lock-based synchronization, and it's much easier to reason about.)
I would be interested in the "too much overhead" article -- can you track it down? I've been researching STM for a while and seen a lot of papers focused on performance and such, so I'd be surprised if whatever the article claims are the problems are not fixable in the long term.
(STM can be nearly reduced to "taking locks", especially if you are compiling, so it really shouldn't be worse than lock-based synchronization, and it's much easier to reason about.)
Here you go:
http://www.acmqueue.com/modules.php?name=Content&pa=show...
The issue is that STMs have a lot of book-keeping overhead in addition to the locking.
The issue is that STMs have a lot of book-keeping overhead in addition to the locking.
No promises about tracking down the article, but I'll make sure you get it if I do.
I've been waiting for a Haskell response to that STM article, because the STM article didn't pay any attention to Haskell at all. One criticism of the article fails in Haskell entirely (in Haskell, you don't get the problem of IO repeating if the transaction repeats, because you can't have IO in transactions (barring cheating)). I'd like to hear how their performance compares, and if it does have a lot of overhead, whether they think it'll ever come out.
The fact that there wasn't one leads me to believe that they are susceptible to the same problems and have no hope of getting around it in the future, though; I suspect if that wasn't true, dons would have been all over the comments on proggit, and he was silent. It's thin logic, admittedly, but...
The fact that there wasn't one leads me to believe that they are susceptible to the same problems and have no hope of getting around it in the future, though; I suspect if that wasn't true, dons would have been all over the comments on proggit, and he was silent. It's thin logic, admittedly, but...
Hmm, that's unfortunate. If successful, haskell's STM would really put it on the map.
I'm not convinced. It looks a bit like spawning threads in Java, but doesn't seem to offer that much more.
well, there was this joke about a dog, an octopus, and wooden legs.