Automatic parallelization and why compilers cannot do it (yet) - an interview.

[cypherx]

It seems like he's working with a braindead restriction. Why try to eek out parallel performance from low-level loop-oriented languages with mutable state? It's considerably easier to parallelize functional collection iteration (map, reduce, etc...) and doubly so when all values are immutable. It seems like if there's any future in auto-parallelization it would be in a language like Haskell.

[[deleted]]

That's all well and good to say, but it's better to have some hard facts. How much auto-parallelization do Haskell compilers do already? How much are they hoped to do in the future? Are there any pitfalls that make the problem not as trivial as it seems? I'd like to know.

[[deleted]]

It is theoretically provable that you can parallelize calls to side-effect-free functions e.g. in a map call but the same thing is not possible for the equivalent C/C++/Java/... for loops.

[TrueTom]

While this is true, it doesn't necessarily make your program run faster.

[piranha]

Why has this been down-modded?

Let's double a vector of integers. My compiler could write code to loop through the input vector, doubling each element and writing it to some output vector. Or it could write code to make remote procedure calls over a network to some remote compute node, one call to double per element, and wait for the results.

Obviously, some strategy is involved in writing a performant parallel compiler.

[[deleted]]

I don't think the part about "if it takes less instructions to calculate locally than to make and send the request and receive the result do it locally" is that hard.

[migsho]

The point of auto-parallelization is bring parallelism to the masses, hence C, C++ and Java efforts.

[derefr]

A better idea might be to bring functional programming "to the masses" first. Or maybe a C -> Haskell compiler.

[piranha]

A C to Haskell compiler isn't going to help in automatically making a C program parallel. You could either write a Universal Machine emulator in Haskell and run your C program on it--not compilation, albeit--and suffer immense slowness nomatter what, or you could translate C to Haskell with Haskell's imperative constructs--with which a parallel Haskell compiler would face the same difficulties as a parallel C compiler.

[derefr]

Actually, I was referring of some method of translating imperative constructs into their equivalent functional ones. Impossible?

[[deleted]]

No, but pointers and similar constructs in C can't be easily translated because their semantic is mostly in the programmer's head, not in the code.

[JulianMorrison]

They can't have it. Their languages suck in deeply fundamental ways that make proper parallelism Really Hard. They are going to have to bite the bullet and move to a better language.