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.
- Maximum depth of parentheses
- Semidirect products (restricted version)
- Linear recurrence
- Semidirect products and distributive monoid actions
- Order-preserving unique
- Most nested position of parentheses
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.