Stack monoid take 3

[raphlinus]

I have figured out a seriously faster version of the stack monoid algorithm (see stack monoid revisited) and want to write that up.

The implementation exists in a PR on the piet-gpu repo, where it will become part of the GPU test suite.

This will become a blog post at least at some point, but I'm also doing a submission to the HPDC conference. Attached is a very early draft of that paper, for review while I iterate on it. It's also possible I'll do a PR adding the paper to the assets section here.

stack.pdf

[rschreyer]

I’m just getting started digging into the algorithms themselves, but two initial questions:

Section 3

Note that Bic(s[i..j]).b is monotonically increasing as i increases

What about this example? Am I calculating the semigroup incorrectly?

s = “(((“
Bic(s[0..3]) = (0, 3)
Bic(s[1..3]) = (0, 2)

In Section 5, what is the meaning of the Stk(enum(s))[…]) syntax? Especially the enum token? Is the reverse can an inclusive or exclusive scan?

[raphlinus]

I got this wrong, it should be as i decreases. This is fixed in my current draft. I'll upload a new one today, which will address these and more. Glad you're interested!

[raphlinus]

What's attached is just a snapshot of the current state, but it doesn't reflect what I want it to be. I'll take a solid pass tomorrow and hopefully fill in the major gaps.
stack.pdf

[rschreyer]

I'm trying to understand the output of Section 5.1 Simple Algorithm / Stack Slices

As described, I'd expect the reverse scan for the string )(()( to produce:
rev_scan(")(()(") --> (1,2), (0,2), (0,1), (1,1), (0,1) (I'm assuming this is an inclusive scan)
rev_scan(")(()(").compact(.a==0) --> (0,2),(0,1),(0,1)
So the partition produces 3 elements. However, one of those elements is already matched with a closing parenthesis within the partition, and so shouldn't be visible as an element-of-interest by subsequent partitions? (and two of them have .b==1, so they'd write to the same location in the produced stack).

[rschreyer]

Section 5.2, first bullet says It consists of a forward Hillis-Steele scan.... Is it a forward scan, or reverse scan? I think you'd need a reverse scan to make this work, and the implementation also appears to be a reverse scan?

[raphlinus]

Thanks for these questions, they're very useful in making me describe things more clearly. In 5.2, yes, this is a reverse scan.

The description of 5.1 is too informal, and is also missing the fact that only open parentheses are written (this is why your interpretation is that 3 elements are written when it should only be 2).

Index i is written to location Bic(s).b - Bic(s[i..n]).b if s[i] = '(' and Bic(s[i+1..n]).a = 0. So for ")(()(", Bic(s).b is 2, the sequence Bic(s[i+1..n]).a is (0, 0, 1, 0, 0). The predicate hits at indices 1 and 4, which results in 1 written at 0 and 4 written at 1. I think giving an example here will help.

[raphlinus]

Attached is my latest draft. I haven't done a real polish pass yet, but there's a new introduction (following the suggested format for the HPDC conference) and one graphic, so I think it says mostly what I want it to say now. I'll do some measurements and see if I can get another graphic in there. I'm very open to comments and suggestions: what's not clear? what could be better illustrated?

stack.pdf

[raphlinus]

Still needs work, but here it is in the recommended template form, and incorporating some of the feedback I've gotten.

stack.pdf

[raphlinus]

I'm actually pretty happy with this version, though of course there's always more that can be done.

stack.pdf

[rschreyer]

'𝑟𝑒𝑣(Stk(𝑒𝑛𝑢𝑚(𝑠)[𝑖0..𝑖2])[𝑘]'

That's missing a closing parenthesis.

It's taken me quite awhile to understand Equation 1 and the following paragraph. I think some additional exposition may have helped me (assuming I've gotten it right):
In cases where Bic(s[i1..i2]).b is non-zero, then a the match the index i2 will be found within the slice s[i1..i2]. If .b is zero, then a match will need to index into a stack monoid covering the slice s[i0..i1]. Maybe this is a good place for a forward reference to justify the division of the sequence into i0..i1 and i1..i2 to say that one of these is solved within the workgroup, and the other requires reading the stack generated by other workgroups?

Section 7.2: This section does feel like it is missing context. For example, the introduction of segments, and that they can be empty vs. non-empty. Would these be tokens other than ( and )? Or is an empty segment an entire prior partion that doesn't have any unclosed open parenthesis?

[raphlinus]

Thanks! Since posting that draft I've actually added an explanation English, I hope that will explain it better. I'll have another look, fix the parentheses, and have another go at 7.2 (I know this is still a bit in shorthand). New draft up soon.

[raphlinus]

I rewrote the section, expanding out a bit what was previously in shorthand. Hopefully, there's enough detail there to figure out what it's actually saying. (empty refers strictly to unmatched open parentheses, and I believe I've made that more precise and explicit now).

I don't really expect people to get 7.2, it's pretty detailed and weedsy. But it should be a description of what I've done, and arguably important as it's what supports the performance result and the ability to scale up pretty well even with two dispatches.

In any case, I very much appreciate your review and comments. I've been getting some on the Zulip as well, and between the two it makes me feel a lot less like I'm shouting into the void. I think I'll submit this version, and then I do have a small window to revise that further if I feel the need.

stack.pdf

[rschreyer]

Sorry for the delay, I didn't see a notification of a new post.

In cases where Bic([s1..i2])
That should probably be i1. Also, the long sentence that follows is confusing. It should probably be split into two separate statements, with the latter being explicit as using the stack monoid for [i0..i] if the match can't be found within [i1..i2]`.

Materialize the stack for the prefix of the input up to the current partition
This immediately makes me think you are materializing the entire stack. Perhaps rephrase to 'Materialize the w-suffix of the stack at the beginning of the current partition'

I think the new Section 7.2 works quite well. Send it!

[raphlinus]

An update. The paper submission above was rejected. I am trying again. The new forum allows publication of the work but asks that the forum not be identified. I am furiously working to make the May 2 deadline. I've done some writing and editing, but the measurements (both of the existing stack monoid and the new bbox oriented work) haven't been done yet.

So at this point I'd love to have feedback on the writing, understanding that the obvious TODO sections will be filled in later.

bbox-04-30.pdf

[raphlinus]

Attached is a new draft, this time with performance measurements and analysis. I don't think I will have time to create a new visual as originally planned, so from here I will basically take a pass to clean up typos and obvious TODO items.

bbox-05-02.pdf