4 ms·

Seconded! I had the pleasure of taking Guy Belloch's parallel programming class at CMU as a sophomore. A large majority of the homework assignments involved l

Seconded! I had the pleasure of taking Guy Belloch's parallel programming class at CMU as a sophomore. A large majority of the homework assignments involved leveraging the segmented scan operator to solve all sorts of classical parallel programming problems. Really eye opening stuff! I am still impressed that prefix sum (generalized over all associative operators, not just +) can be done in O(log n) span. And the algorithm is not too complicated either, I was able to get the gist of it even as an undergrad.

zoltar 6y ago
Reminds me of Guy Steele tackling this trivial problem on stage: https://www.youtube.com/watch?v=ftcIcn8AmSY https://www.youtube.com/watch?v=ftcIcn8AmSY
sitkack 6y ago
I recently tried getting back into Haskell, the goal as to write Haskell and drop into Rust for speed. Even with Stack,the toolchains and the library compatibility was too daunting to figure out, cargo just works, with Rustup and Jetbrains toolbox, I can have a fully configured dev environment that can build everything I need in under 5 minutes. Now if Cargo could install Haskell and its libs, I would jump on it in an instant.
throwaway_pdp09 6y ago
I read that the prefix scan is great so I read somebody's thesis. I a) didn't really get it and b) felt it was doing some complicated stuff for little value. Doubtless I'm wrong, computer scientists tend to be smarter than me, can you give me some insight why it's so valuable?
- lmeyerov 6y ago
  There are two really cool things going on here. Also, keep in mind NESL was published 1992 (and thus made in ~1990), which was not far from when the Connection Machine + Cray's got hyped and largely failed to mainstream parallel compute. 1. Data parallelism, esp. for super power efficient parallel hardware (SIMD, GPU, all the stuff that lets you go 10-100X over Spark for the same budget) is hard for computing over "irregular" data like trees and graphs. Prefix scan showed a basic way to do it for a bunch of basic math over these. A lot of the 90s / early 2000s became research into covering all sorts of weird cases. This shows data parallelism is broadly applicable so worth pushing forward on. 2. Guy B, and then Manuel C & Gabriele K, then showed you don't have to be a weird HPC person hand-rolling Fortran nor rely on weird one-off special case libraries to use the above. We can build libraries of high-level primitives -- think map/reduce -- and even to the level that compilers can make it look like "normal" haskell. Most things can compile down to prefix scan. This is similar to Impala/Spark figuring out RDDs/dataframes and doing SQL on top, except again, for 10-100X better performance, and you don't have to contort everything into 1970s SQL. RE:Prefix scan in particular, we don't _have_ to implement all the algs as prefix scan, but it's reliable base case, and where possible (most cases!), we nowadays instead swap in more efficient hand-written CUDA library calls. Nowadays, when GPUs are in the cloud, Moore's Law stalled out for CPUs but is still going strong for GPUs, and most big data systems realize their latency and data shuttling/serialization sucks, all ^^^ is a big deal. See 10yr AWS price chart I calculated: https://twitter.com/lmeyerov/status/1247382156487213057/photo/1 https://twitter.com/lmeyerov/status/1247382156487213057/phot... . You can just code your Python dataframe code in https://rapids.ai/ https://rapids.ai/ and not really think about it, just know you're doing better than the hadoop stuff underneath and without managing a dirty horde. The existence of NESL and the research area that came after means we're still at the beginning of swapping out crappy CPU software for better data parallel stuff, and _it's doable_.
  - throwaway_pdp09 6y ago
    Thanks for a thorough answer!

zoltar 6y ago

Reminds me of Guy Steele tackling this trivial problem on stage: https://www.youtube.com/watch?v=ftcIcn8AmSY https://www.youtube.com/watch?v=ftcIcn8AmSY

sitkack 6y ago

I recently tried getting back into Haskell, the goal as to write Haskell and drop into Rust for speed. Even with Stack,the toolchains and the library compatibility was too daunting to figure out, cargo just works, with Rustup and Jetbrains toolbox, I can have a fully configured dev environment that can build everything I need in under 5 minutes. Now if Cargo could install Haskell and its libs, I would jump on it in an instant.

throwaway_pdp09 6y ago

I read that the prefix scan is great so I read somebody's thesis. I a) didn't really get it and b) felt it was doing some complicated stuff for little value. Doubtless I'm wrong, computer scientists tend to be smarter than me, can you give me some insight why it's so valuable?

lmeyerov 6y ago
There are two really cool things going on here. Also, keep in mind NESL was published 1992 (and thus made in ~1990), which was not far from when the Connection Machine + Cray's got hyped and largely failed to mainstream parallel compute. 1. Data parallelism, esp. for super power efficient parallel hardware (SIMD, GPU, all the stuff that lets you go 10-100X over Spark for the same budget) is hard for computing over "irregular" data like trees and graphs. Prefix scan showed a basic way to do it for a bunch of basic math over these. A lot of the 90s / early 2000s became research into covering all sorts of weird cases. This shows data parallelism is broadly applicable so worth pushing forward on. 2. Guy B, and then Manuel C & Gabriele K, then showed you don't have to be a weird HPC person hand-rolling Fortran nor rely on weird one-off special case libraries to use the above. We can build libraries of high-level primitives -- think map/reduce -- and even to the level that compilers can make it look like "normal" haskell. Most things can compile down to prefix scan. This is similar to Impala/Spark figuring out RDDs/dataframes and doing SQL on top, except again, for 10-100X better performance, and you don't have to contort everything into 1970s SQL. RE:Prefix scan in particular, we don't _have_ to implement all the algs as prefix scan, but it's reliable base case, and where possible (most cases!), we nowadays instead swap in more efficient hand-written CUDA library calls. Nowadays, when GPUs are in the cloud, Moore's Law stalled out for CPUs but is still going strong for GPUs, and most big data systems realize their latency and data shuttling/serialization sucks, all ^^^ is a big deal. See 10yr AWS price chart I calculated: https://twitter.com/lmeyerov/status/1247382156487213057/photo/1 https://twitter.com/lmeyerov/status/1247382156487213057/phot... . You can just code your Python dataframe code in https://rapids.ai/ https://rapids.ai/ and not really think about it, just know you're doing better than the hadoop stuff underneath and without managing a dirty horde. The existence of NESL and the research area that came after means we're still at the beginning of swapping out crappy CPU software for better data parallel stuff, and _it's doable_.
- throwaway_pdp09 6y ago
  Thanks for a thorough answer!