# Discussion: Parallel reductions using semidirect products

**URL:** <https://discourse.julialang.org/t/discussion-parallel-reductions-using-semidirect-products/62654>\
**Category:** General Usage\
**Tags:** announcement, parallel, math\
**Created:** [June 10, 2021, 2:55am UTC](https://discourse.julialang.org/t/discussion-parallel-reductions-using-semidirect-products/62654 "2021-06-10T02:55:38Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [June 10, 2021, 2:55am UTC](https://discourse.julialang.org/t/discussion-parallel-reductions-using-semidirect-products/62654/1 "2021-06-10T02:55:38Z")

</div>

Hi, I just wrote a discussion on [Parallel reductions using semidirect products](https://juliafolds.github.io/data-parallelism/explanation/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](https://en.wikipedia.org/wiki/Semidirect_product) (of semigroups) and [semigroup action](https://en.wikipedia.org/wiki/Semigroup_action) are useful in parallel reduction; i.e., this onelinear Julia function lets us compute some interesting reductions:

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

```

Apparently, this is known at least since 70s ([Kogge and Stone, 1973](https://doi.org/10.1109/TC.1973.5009159)) 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.