3 ms·

This was a really interesting talk. Pretty high information density. It makes sense to use divide-and-conquer rather than a first-rest pattern when doing paral

by htor 12y ago

This was a really interesting talk. Pretty high information density. It makes sense to use divide-and-conquer rather than a first-rest pattern when doing parallel computations on sequences. But I'm curious if that pattern can be applied to other data structures as well and not just tree structures like the conc list?

anaphor 12y ago
Well nested data parallelism generally applies to hierarchical structures like trees, whereas flat data parallelism applies to things like arrays and whatnot. You might want to watch this (similar in some ways) talk by SPJ on Data Parallel Haskell http://youtu.be/NWSZ4c9yqW8 http://youtu.be/NWSZ4c9yqW8
dwenzek 12y ago
This pattern can be applied to a large set of collection representations, as long as a former collection can be divided into smaller parts which can be processed independently giving partial results to be combined into a final outcome using an associative combiner. For instance, to compute a count of words, the former word collection can be either a conc tree in memory or a file divided in chunks or a bunch of files. In each case, the sub counts can be computed independently and reconciled into a total count. The deep insight Guy Steele provides in his talk, is how to deal with the non trivial cases like the count of words in a file divided in chunks where words can cross chunk boundaries. Hence, I highly recommend watching this talk. As further reading, I recommend too a post [1] that I written after having watched Guy Steele talk. [2] is a work in progress to implement the idea in OCaml. [1] http://acidalie.free.fr/unfoldvalue/blog/map-reduce-spirit.html http://acidalie.free.fr/unfoldvalue/blog/map-reduce-spirit.h... [2] https://github.com/didier-wenzek/odist https://github.com/didier-wenzek/odist
- agumonkey 12y ago
  Indeed the cross-chunk recombination is quite something. We're used to clean cut boundaries and here he is going away from this rule to bring new opportunities. But I wonder how hard it is to think about, design and test such assoc. combiners ..
  - dwenzek 12y ago
    Yes, it may be quit hard to design such a combiner due to constraints both on the input (as the need for cross-chunk recombination), and on the output (as too early finalization preventing further combinations); with the consequence that we often have to imagine a genuine intermediate data representation of the problem. But this complexity is mitigated by the fact that these associative combiners can be built incrementally using a reduced set of patterns, combiner compositions and transformations. Have a look to this remarkably well written post [1] on incremental regular expressions (it appears that incremental computation is deeply related with parallel computation). It shows well, on a non-trivial example, how to build such an intermediate data representation with its associative combiner. [1] http://jkff.info/articles/ire/ http://jkff.info/articles/ire/

by htor 12y ago

anaphor 12y ago

Well nested data parallelism generally applies to hierarchical structures like trees, whereas flat data parallelism applies to things like arrays and whatnot. You might want to watch this (similar in some ways) talk by SPJ on Data Parallel Haskell http://youtu.be/NWSZ4c9yqW8 http://youtu.be/NWSZ4c9yqW8

dwenzek 12y ago

This pattern can be applied to a large set of collection representations, as long as a former collection can be divided into smaller parts which can be processed independently giving partial results to be combined into a final outcome using an associative combiner. For instance, to compute a count of words, the former word collection can be either a conc tree in memory or a file divided in chunks or a bunch of files. In each case, the sub counts can be computed independently and reconciled into a total count. The deep insight Guy Steele provides in his talk, is how to deal with the non trivial cases like the count of words in a file divided in chunks where words can cross chunk boundaries. Hence, I highly recommend watching this talk. As further reading, I recommend too a post [1] that I written after having watched Guy Steele talk. [2] is a work in progress to implement the idea in OCaml. [1] http://acidalie.free.fr/unfoldvalue/blog/map-reduce-spirit.html http://acidalie.free.fr/unfoldvalue/blog/map-reduce-spirit.h... [2] https://github.com/didier-wenzek/odist https://github.com/didier-wenzek/odist

agumonkey 12y ago
Indeed the cross-chunk recombination is quite something. We're used to clean cut boundaries and here he is going away from this rule to bring new opportunities. But I wonder how hard it is to think about, design and test such assoc. combiners ..
- dwenzek 12y ago
  Yes, it may be quit hard to design such a combiner due to constraints both on the input (as the need for cross-chunk recombination), and on the output (as too early finalization preventing further combinations); with the consequence that we often have to imagine a genuine intermediate data representation of the problem. But this complexity is mitigated by the fact that these associative combiners can be built incrementally using a reduced set of patterns, combiner compositions and transformations. Have a look to this remarkably well written post [1] on incremental regular expressions (it appears that incremental computation is deeply related with parallel computation). It shows well, on a non-trivial example, how to build such an intermediate data representation with its associative combiner. [1] http://jkff.info/articles/ire/ http://jkff.info/articles/ire/