Discussion: Parallel reductions using semidirect products

Hi, I just wrote a discussion on Parallel reductions using semidirect products:

Solutions to many parallel programming problems can be reduced to a well-designed monoid. As such, interesting parallel solution sometimes require non-trivial monoids. To enrich the repertoire, let us discuss semidirect product; a particularity elegant construction of useful monoids.

  1. Maximum depth of parentheses
  2. Semidirect products (restricted version)
  3. Linear recurrence
  4. Semidirect products and distributive monoid actions
  5. Order-preserving unique
  6. Most nested position of parentheses
  7. Conclusion

This is a note on a neat math fact that semidirect product (of semigroups) and semigroup action are useful in parallel reduction; i.e., this onelinear Julia function lets us compute some interesting reductions:

sdpl(*′, ⊳, +′) = ((a₁, b₁), (a₂, b₂)) -> (a₁ *′ a₂, b₁ +′ (a₁ ⊳ b₂))

Apparently, this is known at least since 70s (Kogge and Stone, 1973) but my impression from digging into this is that this is re-discovered multiple times (at least originally I find it myself when playing with monoids in Transducers.jl) and does not have a coherent terminology. So, it’s rather hard to get the full picture of the application of this. This is my attempt for linking some literature and also giving a motivating introduction to it. I’m very interested in the applications of this so please let me know if you know other use cases or some possible uses of this.

5 Likes