[nilknarf]

> Automatically generating monoids such as the stack monoid from their corresponding simple sequential programs seems like an extremely promising area for research.

I was interested in this problem a while back and the papers I remembered being useful were:

"Automatic Inversion Generates Divide-and-Conquer Parallel Programs": https://core.ac.uk/download/pdf/192663016.pdf

which is based on "The Third Homomorphism Theorem": http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/th...

The motivating example is whether you can generate a mergesort (where the monoid is combine two sorted lists) given an implementation of an insertion sort (where the sequential program is inserting one element by one into a sorted list).

I remember being disappointed by the answer after reading these papers but in the citation graph there are a bunch of relatively recent program synthesis papers. Maybe there's something better now.

[raphlinus]

Thanks for the reference, it's definitely relevant. I took a pass over the paper somewhere between skimming and reading, and, while it's definitely in the ballpark of deriving parallel programs from sequential, it's also pretty clear their source language can't express the stack monoid problem because it lacks a "cons" operation; basically it seems to be for various fancy reduction problems where it consumes a sequence and spits out a scalar. On a quick read, I have no idea whether that's a fundamental limitation or something that could be extended.

I think examples like generating mergesort from insertion sort are maybe trying to be too clever. I mostly just want something that lets you slice up the problem into chunks, process each chunk in parallel, then combine them back in ways that don't kill performance on modern GPU hardware.