3 ms·
This is what parallelizing Fortran compilers do. The space of programs that can be automatically parallelized is all computable programs (see http://en.wikipedi
by sedachv 16y ago
This is what parallelizing Fortran compilers do. The space of programs that can be automatically parallelized is all computable programs (see http://en.wikipedia.org/wiki/Church–Rosser_theorem http://en.wikipedia.org/wiki/Church–Rosser_theorem). The space of programs that can be efficiently automatically parallelized is very small.
- adrianN 16y agoMany problems aren't parallelizable for reasonable definitions of the word (i.e. polylogarithmic depth and polynomial work: Nick's class) unless there are some major breakthroughs in complexity theory.
- sedachv 16y agoAs a class of problems, probably (although it hasn't been proven either way), but in terms of programs it comes down to the vagaries of data structures and algorithms - if the dataflow in your reduction graph makes it look like a linked list, there's only one way to reduce it. Guy Steele gave a really good talk about this at ICFP 2009: http://labs.oracle.com/projects/plrg/Publications/ICFPAugust2009Steele.pdf http://labs.oracle.com/projects/plrg/Publications/ICFPAugust...
- eru 16y agoThe good thing is that functional programmers will barely notice that they are using the new data structures. (It's still just filters and maps. Just your fold-functions will take slightly different arguments.)