4 ms·
Many problems aren't parallelizable for reasonable definitions of the word (i.e. polylogarithmic depth and polynomial work: Nick's class) unless there are some
by adrianN 16y ago
Many 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.)