The Stack Monoid

Thanks for the insightful post, specially the Dyck language plug. Really cool stuff.

Citation dump gratefully received!

The Dyck language I was already aware of; I linked it in the previous post in the series. But the bicyclic semigroup was new to me. Yes, the bones of it are very similar to my "stack monoid;" if you erase the actual element values of the stack contents and just count the lengths, it's clearly the same thing. No doubt there's some theory that justifies adding the elements back in as well.

I'll have to check out the Kmett talk - from the description it sounds very interesting.

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.

Didn't SIGFPE's blog cover this years ago?

Bonus clip: https://www.youtube.com/watch?v=j4YNPhllDXU

It's a good question, and it's been suggested I write a GPU compute 101. I did do a talk at Jane Street earlier in the year called "A taste of GPU compute" which has some relevant resources (a Google search on that term will give you a number of links).

I think there are probably a number of on-ramps. One easy way to get started is shadertoy, which if nothing else should give familiarity with GLSL syntax and intuition for performance in the simplest case: each "thread" computes something (a pixel value) independently of the others. You'll quickly run into limitations though, as it can't really do any of the more advanced compute stuff. I think as WebGPU becomes real, an analogous tool that unlocks compute kernels (aka compute shaders) could be very powerful for pedagogy.

I think most people that do compute on GPU use CUDA, as it's the only really practical toolchain for it. That has a large number of high quality open source libraries, which tend to be well-documented and have good research papers behind them. You can start by using these libraries, then digging deeper to see how they're implemented.

As I've been going on about, I believe this space is ripe for major growth in the next decade or so. As a rough guide, if you can make your algorithm fit the GPU compute model nicely, you'll get about 10x the compute per dollar, which is effectively the same as compute per watt. Why leave such performance on the table? The answer is that programming GPUs is just too hard. In certain areas, including machine learning, an investment of research has partially fixed that problem. But in others there is fruit at medium height, ripe for the picking. And in some other areas, you'll need a tall ladder, of which I believe a solid understanding of monoids is but one rung.

In a sense GPU programming is similar to cellular automata. Each cell is an invocation on the GPU, and you can assume that you may have unlimited number of these invocations. You can freeze cells infinitely or temporarily, but you cannot group them. You can assume you know the identifier number of each cell, and you can assume you know the number of cells for each program. The hard part is now to generalize algorithms in which only control structures are based on freezing, identifying, and counting of cells. The cells can communicate information to the neighboring cells, and to any arbitrary cell, but the latter is not good for performance.

Most universities don't really teach parallel algorithm development in any way despite the core count increasing in both CPU and GPU world.

Current languages like GLSL and CUDA are very abstracted in the sense that they don't really tell why some approach is better or worse than the other. To me, if you can create as general cellular automata -like solution, then such logic can be converted and is generally fine performance-wise for SIMD orientated programming.

Shader toys are definitely a fun way to get your head around the GPU, reading and forking other people's shaders is great to learn.

I made this [1] simple shader because I couldn't find the effect in Open-Source video software...

[1] https://www.shadertoy.com/view/WtfGzX

I may be extrapolating too much but I think Steele team workig on Fortress was also doing monoid like thinking to parallelize heavy. He made a talk on how to delinearize problems into partially solved subproblems to be reconciled later.

Search for "monoid category" on google. A monoid is a mathematical object in cathegory theory.

A monoid is a set S with an associative binary operation and a unit. For instance, strings with string concatenation and the empty string form a monoid.

Functions form a monoid as well. Function composition is associative and id is the unit.

From math: https://en.m.wikipedia.org/wiki/Monoid

A monoid is a concept from math. They have a set of objects (like the integers), and a binary operation (like addition or multiplication over integers). The operation is associative (like addition where the order you compute a set of additions doesn’t matter, you get the same sum). And there’s an identity element (in addition this would be 0).

For CS there are some nice results where the operation can be automatically parallelized. Useful for things like MapReduce if you need to run things at large scale, or in this case for distributing the work over the many shader units of a GPU.

I Googled around too and this was the most satisfying one I found: https://medium.com/@michelestieven/a-monad-is-just-a-monoid-...

The author defines a monoid early on, in terms of the three properties that someone else also posted.

I understand this definition but am still trying to make the leap to how it applies in the original article.

A monoid is a mathematical structure which captures associativity (a+(b+c) = (a+b)+c) and has an identity notion (a + 0 = 0 + a = a).

They're useful because knowing them allows for identifying and mechanically applying transformations to better leverage parallelism and easily implement incremental computations†.

I highly recommend this article and the section on monoid homomorphisms in particular, which covers why you should care about monoids and gives a practical example: https://fsharpforfunandprofit.com/posts/monoids-part2/#monoi...

If you've been programming for a while, I can guarantee you already intuitively understand the concept. Giving it a name allows you to automatically recognize and notice that you've already solved this problem before in another guise.

Alternatively, having named the concept, it's now chunked into your toolkit for use whenever applicable. Structuring your solution so you know it's a monoid allows leveraging all those benefits almost for free.

†With divide and conquer, add memoization and pay attention to the order of subproblems such that you can reuse earlier work, and if you can, we're nearly at dynamic programming. We can specify a bit more structure, to get semirings and collapse a whole heap of disparate seeming machine learning algorithms. But now I have gone too far afield.

To relate it to something you're more likely to already know: it's like a group (in the mathematical sense), except that it doesn't necessarily have inverses.

From a programming perspective it is a way go generalize adding two things together, but where the order might matter (or might not!).

+ is a monoid. It adds to numbers together. (3+3)+4 = 3+(3+4)

But also concatenation is a monoid

"a" + ("b" + "c") = ("a" + "b") + "c".

Monoids have an empty thing you can add to anything.

E.g. 0 for + and "" for concatenation.

In Haskell, Monoids are abstracted out into a typeclass so that you can write code on any monoid. For example fold up a list of monoid elements into a single element.

An important example from CS would be the semigroup action on the set of states of a deterministic finite automaton.

The action takes a state from Q, and a symbol from E, and returns a new state. ie f:QxE->Q. In the case when you have some "no op" action the semigroup action is actually a monoid action.

This all corresponds to the DFA moving through states as it "eats" the string.

So a bunch of people are giving you good definitions. Here's an article that does FizzBuzz with monoids. I think this is the first thing I saw that actually cemented them into my mind. Probably because it takes a problem-to-solution teaching method. (Unfortunately looks like the original page is dead.)

https://web.archive.org/web/20200325013049/http://dave.fayr....

Good call, that rings a bell and I'll look into it. A bounded k-stack with overflow seems like a really good fit for the capabilities provided by GPU.