undefined | Better HN

0 pointsalain9404016y ago0 comments

languages with side-effects cannot be automatically parallelized without changing the semantics and introducing observable nondeterminism

Considering I spent years working on automatic parallelizing compilers for Fortran and C++, I'd say it is possible. I don't know why you consider the heavily computational kernels of C programs less interesting just because they don't have side effects or make IO calls.

For instance I worked on some algorithms to parallelize linked-list traversals, something that you would normally think is by definition serial.

0 comments

3 comments · 2 top-level

astine16y ago· 1 in thread

Could you share the algorithm (or a link)? I'm very interested.

codexon16y ago

http://software.intel.com/en-us/blogs/2007/12/20/linked-list...

"Traversing a linked list is inherently serial. [Theorists will point out that traversal can be done in parallel if you have a processor per node in the list. Feel free to buy that many Intel processors -- I own Intel stock.]"

One possible implementation would be to use a skip list where you have each core search each level.

mbrubeck16y ago

I didn't say that side-effect-free program kernels are "less interesting" - I said they were beside the point of this post. (But I do think they're very cool and important in their own right!)

The GHC developers' point was that restricted side effects are necessary for automatic parallelization. Your answer seems to be, "I can parallelize languages with unrestricted side-effects... in sections where you restrict yourself to a side-effect-free subset."

Yes, I'm happy when a C++ compiler automatically optimizes my inner loop. But I'd rather be able to use "par" at the highest level of my program, and parallelize anything from XML parsing to physics simulation, without worrying that some library call ten functions down the stack will turn out to be non-reentrant.

j / k navigate · click thread line to collapse