Skip to content
PodSubs
ShowsPeopleGuestsJobsNewsEvents
More
BlogPodCred
Menu
ShowsPeopleGuestsJobsNewsEventsBlogPodCredNetworksSign in
Join nowSign in
  • Shows
  • People
  • Jobs
  • News
  • More
    • Guests
    • Events
    • Blog
    • PodCred
    • Networks
    Join nowSign in

ADSP: Algorithms + Data Structures = Programs

ADSP: Algorithms + Data Structures = Programs artwork

Episode 174: Parallel chunk_by (Part 2)

Mar 22, 202431 minAudio
ShareXLinkedInFacebookWhatsAppEmail

In this episode, Conor and Bryce continue their conversation on parallel chunk_by. Link to Episode 174 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Twitter ADSP: The Podcast Conor Hoekstra Bryce Adelstein Lelbach Show Notes Date Recorded: 2024-03-06 Date Released: 2024-03-22 C++23 std::views::chunk_by thrust::copy_if thrust::inclusive_scan thrust::gather thrust::reduce thurst::reduce_by_key thurst::inclusive_scan_by_key Think Parallel ACCU Talk ArrayCast Episode 33 - João Araújo and Tools of Thought cub/cub/agent/agent_reduce.cuh Intro Song Info Miss You by Sarah Jansen https://soundcloud.com/sarahjansenmusic Creative Commons - Attribution 3.0 Unported - CC BY 3.0 Free Download / Stream: http://bit.ly/l-miss-you Music promoted by Audio Library https://youtu.be/iYYxnasvfx8

Audio and video play straight from the show's own hosting. PodSubs stores and serves no media.

Transcript

From the show. Tap a time to play from there.

BryceReduce in Cub is two passes.

ConorReduce in Cub is two passes.

BryceYeah. Because it's more fit instead of com communicating between threads, it's more efficient to have all of the thread blocks reduce locally right into an array and then do a second pass that reduces that final array. So in CUDA on NVIDIA GPUs, you tend to have hundreds of thousands of threads, you know, many, many inputs, and you tend to have maybe thousands of blocks.

ConorWelcome to ADSP the podcast episode 174, recorded on March 6, 2024. My name is Connor, and today with my co-host Bryce, we continue part two of our discussion of parallel chunk pie.

BryceOkay, Connor. I'm gonna show you a function signature. We've got a function chunk pie. It takes a range, an output iterator, and a predicate. And what it does is it chunks up the input according to the predicate. So it can buy it it creates chunks of uh uh of elements for which the predicate returns true. And whenever there's a there's uh an element for the predicate returns false, then that's the start of a new chunk.

BryceAnd then it assigns these um uh these subranges, it assigns it into the output iterator. How do you implement this chunk by algorithm in parallel?

ConorI mean chunk by does nothing, so there's nothing to implement. Perfect. Done.

BryceWoo, folks. You missed the prompt.

ConorI'd miss the prom?

BryceThe prompt.

ConorThe prompt?

BryceYes.

ConorI was gonna say, why did I miss prom? That doesn't have anything to do with miss.

BryceYou've missed the prompt.

ConorI mean chunk buy.

BryceThis is not this is not a view. This is an algorithm called chunk by where it needs to produce an output sequence of subranges.

ConorI mean, even if it this isn't a view, I literally would, like, unless if you're calling, you know, two vector after the view thing, which is where my head's at right now, literally I wouldn't change the shape of the data. I would create uh a second thing called flags. You know, whether you even want to materialize that or not, you could just do it with a transform iterator, zip iterator trick.

BryceYou can't you can't do this one lazily.

ConorI'm not saying you're doing it lazily, but like until you need to print it, you don't actually need to do anything. And it doesn't need to be a scan.

BryceIt's just literally how are you implementing this in parallel?

ConorWhat do you mean, a transform iterator? That already is parallelizable.

BryceOkay, describe your implementation again.

ConorAll right. So if I need to like it to me, I'm like stuck in ViewLAN because like chunk buy by itself, like you rarely ever want that. But if literally what you want to do in parallel is write to a screen and you've got a million elements, and you want to chunk by a binary predicate, which is what chunk buy does, and you want like you want like the bracket and the bra left bracket, right bracket indicating where your chunks are. I literally wouldn't change the data at all. All it would be is a printing mechanism, and I would create a transform iterator composed with a zip iterator that gives you two elements at a time, and your transform iterator is gonna take that binary predicate, and then you're basically just gonna like however you do printing in parallel to the screen, and anytime what is this printing?

BryceLike my point is is like the output that I want is a vector of subranges, not printing. I want you to produce a vector of subranges.

ConorWell, if that's the case, then it's a bit more complicated. I mean, I I feel like it's why would you want that?

BryceOkay, but that's not the prompt.

ConorBut I I think in general, you're always gonna there's always an operation after chunk pie, whether it's a permutation of the elements in each chunk or a reduction.

BryceBut the the materialized answering this question answers how you would implement this in parallel when you're composing it with other operations.

ConorIt answers a way to do that. With my way where you just have a lazy, basically, mask that determines where your stuff is.

BryceI don't see how you could do this lazily like that in parallel.

ConorLike what does reduced by key do? That comes by It's a scan.

BryceIt's all scans, buddy.

ConorReduced by key is a scan.

BryceYeah.

ConorWell, I don't think that's the only way to implement that.

BryceOkay, well you let me be the parallel programming expert. I let you be the programming languages expert.

ConorI'm just saying doing that via scan versus like a bunch of different reductions that then the results just get copied.

BryceI mean, I think that's that's uh well no, for reduced by key.

ConorUm like a scan by key, obviously, inclusive scan by key, obviously that's a scan, but a reduced by key, if you're telling me that's implemented with a scan, maybe that is the best way to do it. I'm just saying that sounds suspicious.

BryceBecause you you yeah, you have to do it. Um I'm pretty sure. But anyways, you're you're getting us off topic. We can check that in a moment. How do you implement the stop stop questioning the utility of the thing and just trust me and answer how do you implement uh trunks of the code?

ConorSo if you actually want to materialize a vector of vectors, which for the record sounds like a bad idea to me. Sounds like a bad idea to me. Uh if you actually want to do that, and you're starting off with a single vector on your device, you're gonna end up It's the It's the same thing that you want to do for copy if basically. Yeah, I mean there's two different ways in my head. Like you can you can create that mask and then do the plus scans and do a bunch of copy ifs based on those indices, or you can calculate the indices of where the starts of your new chunks are and perform copyifs to each of your new like vectors within your vector.

ConorSo there's two different ways to do it. I don't actually know which one's best. So one of them, yes, is is very similar to the first one that you describ what I described.

BryceOkay. So what I've got here is how I've done it, which is three passes, just like a copy of. The first pass, we build up a vector of flags. One for each element. Ish. Now, chunk by takes a predicate that's applied to every two adjacent elements, so it's not just a straight transform.

BryceSo we do a essentially an adjacent transform to build up the flags. And then we've got a vector of flags where there's one flag for every input element, um, and the flag is true if the chunk by predicate returned true for that particular element. And then we're gonna introduce a struct. I'm gonna call it interval. And this struct is gonna be the thing that we're gonna scan.

BryceAnd a struct, and an interval has four different components. One has the flag, which is just the flag from the transform. It's just a bool. It also has an integer, which is the index. And this is the same index from the copy if, where this is the index of what is the current location uh the that uh it's a plus scan on your flags vec.

BryceYes, it's a plus scan on your flags vec. But then we also have an int start. And this is the start of whatever the current chunk is. And then we also have an int end. An int is just a count of from like for every element we just count once. You fall so far?

ConorUh maybe. Keep going.

BryceOkay. And then we're going to do a scan of the flags array. And uh to we we convert a flag to an interval um as follows. Uh the flag parameter of the interval is just whatever the Boolean flag is, and then zero for the index, zero for the start, and one for the end. Because remember, the end is just the count of how many elements we have.

BryceSo the way that you take a representation of a particular element, like any arbitrary element, and turn it into an interval, is you compute the predicate for it, and that's the flag uh member of the interval, and then index is zero, start a zero, and then end is one because you've got one element that you're dealing with. Follow so far?

ConorMaybe. Keep going.

BryceOkay. And then our reduction operator for our or sorry, our scan operator. Um, it takes a left and a right, both of which are intervals, and it combines them together. And it always takes the flag from the right interval, just because of the nature of how this scan is applied from left to right, it's always gonna be representing the element on the right when we combine things.

BryceSo the the newly returned interval from this sum function will have the flag of the right one. And if the flag of the right interval is true, then the index is the left index plus the right index. Um because and that's uh yeah. I won't explain that any further. But if it if the flag on the right is not true, then it's the left index plus the right index plus one.

BryceUh because if it's not true, then we've started a new group and we need to increment the index. Then for the start field, which represents the beginning of the current chunk that we're working on. If the flag is true, then we are continuing the current chunk, and so we add the start from the left and the start from the right.

BryceBut if the flag is false, then we're at the start of a new chunk. Well, where do we start a new chunk? Well, we're starting a new chunk at this element. So what is the position of this element? The position of this element is the end of the left, is the count of how many elements we've gone to thus far. And fortunately we have that count. And then the end, which is again the count of how many elements, it's just like if you were gonna do a std count, end is is always just the end on the left plus the end on the right.

BryceAnd so you do that, you do that scan with that operator, and then you do um a gather if. Um and uh or I'll describe it in terms of a for each. And so the for each is um it's a little bit uh tricky because the you you end up needing to have that flag parameter in the interval thing, um, but I also have to keep the original flags around because I end up overwriting the flags in there.

BryceAnd there's maybe a slightly more elegant way to structure this, but the fore each functor, um if the the flag is false, then that means that we're at the end, we're at an element that represents uh uh the end of a chunk, and so we need to write that chunk to the output iterator. And we know what index we're gonna write it to in the output iterator because that's a part of this interval data structure.

BryceBut do you understand how this algorithm works? This is the same style of algorithm, it's the same implementation that we have for copy if. We did three fundamental things. First of all, we computed the flags. Second, we did a scan that scanned the flags and computed some indices into the original input.

BryceAnd third, we did some gathering operation, which used those indices and those flags to write to the output in the correct positions with the correct values. This is how we implement stream compaction. And my argument is that this implementation strategy the thing that we do for copy if we would do the same thing for chunk buy.

BryceIt's the same parallel algorithm. Flag building, scan, gather. And so, and and that is why I say to you that I am thinking of these grouping operations as removing operations because they're gonna be implemented in parallel in the same exact way.

ConorUh so I I have three comments, and I'm not even sure if I remember all three of them. So I might I might forget the third one.

BryceWhile you while you do that, I'm gonna go look at reduced by key, but continue.

ConorAlright, my first comment, I mean Bryce kind of needs to hear these, but uh if he needs to refute them if they're wrong, I didn't fully understand. So I I think the the actually the first comment is yes, I agree that they all share the same flags plus scan on flags, gather if style. That's my first comment. So I agree with you there. My second comment is I'm not sure I fully understood the struct across blocks or chunks, uh, but I don't think that's important.

ConorI understand what the purpose of them was. I was thinking in my head, what if there's a bunch of chunks within a single block? Is that a problem? But my guess is that it comprehensively covers all the cases, whether a chunk is longer than a block and straddles both the left and right side of it, whether it's split by a block, um, or there's a bunch of them inside a bunch of chunks inside a block, I'm guessing your struck covers all those situations, correct?

BryceRight. It doesn't cover them explicitly, it's just by property of the scan.

ConorYes. So as long as I didn't fully understand that, but my guess is that it works for that, so uh, we're good to go there. My third and final comment, and this is the most important one, is that although I although I uh made my first comment about agreeing with the structure, I think I still morally take issue with referring to that flags plus scan and then gather if as dropping because I can see I can see why you're saying that because how about compacting or combining?

BryceThose are less objectionable. But hang on, but can can you at least see how some could view chunk by, which applies a predicate like like think about what chunk by does. Chunk by it says, like, okay, I'm gonna I'm gonna start at the beginning of the sequence, and I'm gonna apply this predicate and start accumulating elements until I hit one that's false, and then I'm gonna pop out a chunk.

ConorWell, I mean specifically it's a binary predicate that's applied to adjacent.

BryceCould you could could you see that as an operation that combines things together?

ConorYes, but it doesn't drop anything. The moral issue that I have is with saying that it drops stuff, which is it never drops anything.

BryceBut in a world where we have to do our work distribution a priori, but we end up we end up where we distribute a certain number of work items to each thread, and then as we do this combining operation, some of the threads have to bow out. It's like back to that example of the word count where we had 20 threads but four words. Not some of the bat some of the threads have to choose not to participate, and that's what I mean by dropping.

ConorWell, so I still take issue with it because if an execution strategy necessitates some kind of dropping, the execution strategy has nothing to do with the algorithm from like a semantic point of view.

BryceBut if you think about the algorithm differently, then that can lead you to an execution strategy that you might not have thought of.

ConorI'm not disagreeing with that, but from a like a semantic point of view of what chunk buy does, it doesn't drop. Just because an execution strategy does. I choose to think of it as dropping. I'm not saying that you're wrong for thinking about it, but you're trying to convince me to think about it that way.

BryceI'm not I'm not I'm not saying that you should think about it that way in general. So what are you saying? I'm saying I'm saying that if you're implementing it in parallel, that's a good mindset to have. Also, let's talk about reduced by key. It it it I did confirm it is it is implemented by a scan. And in fact, interestingly, it's it's it's a it's a by-key scan, so it is very similar to the by key scan?

ConorThat's even worse than implemented by a scan.

BryceWell, how else would you would you do? I mean, you the scan, you do the scan to um to compute the groups.

ConorYou could do a reduced by key with a yeah, with a reduction. With the same little struct that you're building up with little pieces of information that like when your chunks, because that's basically a reduced by key, is exactly what we're talking about. It's a chunk by followed by a transform, where the operation that your transform is applying is a reduction. That's exactly what this is. And in the case where you know that that operation is a reduction, aka a reduced by key, then you know that you definitely don't need to do like any scanning stuff.

ConorYou can have some object that, sure, it's got some internal vector that might be growing over time as you are um, you know, you'd have to turn it basically each of your elements into one of these structs, and then at the end of the day, you're gonna end up with a vector of these structs where the only thing you care about is the reduced element. But you definitely don't need to do it by with a scan or a scan by key. Maybe that is actually the best implementation. Lord knows I'm not a uh CUDA ninja when it comes to implementing this stuff, so I don't actually know you know what is best.

ConorBut I'm I'm saying that like when I when I think about you know how to implement a copy if it matched up with what what uh we have in Thrust. But when I think about how to implement a reduced by key, I definitely don't think of scan, and I definitely don't think of scan by key. I see how you can definitely implement them in terms of those. Uh, but like a scan by key, my guess is what they do is they do the scan and then they just do a copy if where they're copying the last element of each of the scans, correct? Um I would expect to see like I would expect to see a gather if or a copy if where Yeah, there's a there's a gather if in the scan.

ConorYeah, and the gather if is just looking into the final index of each scan, which means that you've materialized a whole scan, a whole like, you know, chunks worth of data. Only it's like it's a basically when we talk about the missing reduction where we're doing the associative only reduce, but the only way to do that currently because we don't have that reduction, it's missing, we have to basically do an inclusive scan and then just take the last element. That's what we're doing here for every single chunk. Bryce is thinking. He's not ignoring me, he's just staring up at the ceiling.

BryceYeah. I just remember what reduce actually looks like. But let's look at scan by key, because you mentioned how scan. Well, no, scan by key actually does the um does the the flags thing too. Scan by key and reduce by key look end up looking very similar in in Cub today. That's sad. I'm trying to think about whether there's a better way to do reduced by key. Is there a reason that it has to be a scan?

ConorOh, you know why it probably is a scan? Because the reduce by key that I'm talking about, my version, you know what it needs? It needs the missing reduce. Building up one of those structs that you combine across blocks requires the associative only reduce.

BryceYeah, but we ha like our reduce does that happens to work that way.

ConorOkay, that's a never mind.

BryceI forgot about that. So let's look at what what does reduce do? Reduce. It'd be funny if it'd be funny if it was a scan too. No, it's not. Um so it's got a block reduce, but then so in cub, a block reduce is something that just does a reduction within a set of blocks, but then you get to combine a block reduce with some sort of global thing to um make it uh device-wide.

BryceSo the way that the way that scan works in in Cub is there's this magical um tile uh prefix thingy that wraps your operator. So you call you still call block scan in cub, but you pass it in this magical wrapped version of your operator, and that wrapped version of the operator does all of the communication between the different blocks. So it's very clever because if you only want to do a block-wide scan, um, you can use the block-wide scan primitive for it.

BryceBut if you want to do a scan that communicates with other blocks, you don't have to use a different primitive. You just use that same primitive and you just plug in this operator that when it gets invoked, it will go and do the communication. And if you're interested in learning more about how that uh that particular scan algorithm is implemented.

ConorOoh, is think parallel? Think parallel is a better title, yeah. Think parallel. Yeah. At ACCU 2024.

BryceThinking parallel is actually I I I don't hate that title.

ConorWhat did uh uh a friend Joao who's uh was a guest on a raycast? He when he listened to that episode, he was like IBM's motto is think, Apple's motto is think different, NVIDIA's motto is uh think parallel or should be. And then I was like, and then I said, Yeah, we could keep going, and Netflix is don't think. And uh where is the OpenAI is uh we can think for you.

BryceWhere is the communication here? So there's no interesting. Alright, somewhere here there's gotta be an atomic or somewhere there there has to be a uh some form of communication.

ConorFor those that like to follow along, Bryce is at agent underscore reduce. We'll leave a permalink to the file in the show notes.

BryceTransform op.

ConorWe've also we're gonna wind this down in the next five minutes here because we have been recording. An hour and a half.

BryceUh this has a transform op that's built into it. That's clever. So we're calling reduce. Does it hang on, you hold on to this for a second.

ConorTesting, testing. That was f that was Bryce dropping his keyboard.

BryceI remember the answer. Reduce in Cub is two passes.

ConorReduce in Cub is two passes. Yeah.

BryceBecause it's more f instead of com communicating between threads, it's more efficient to have all of the thread blocks reduce locally right into an array, and then do a second pass that reduces that final array. So in CUDA on NVIDIA GPUs, you tend to have hundreds of thousands of threads, you know, many, many inputs.

BryceUm and you tend to have maybe thousands of blocks, you know, let's say oh one thousand blocks, um, for like, you know, a good chunky run. Um maybe if you have a smaller problem size, you might have a lot fewer blocks. And you have like up to hundreds of what we call SMs, which are the things that execute blocks, and you can have uh uh I think like modern chips maybe have like 80 SMs, um, but each SM can have multiple blocks active at a time.

BryceI can't remember how many, it could be 16, but so you could have a couple hundred blocks operating at the same time. So if you do a two-pass reduction, your first pass reduces whatever, regardless of input size, it reduces your input size down to O number of blocks values. So you go from ON of arbitrary input size, which could be millions, billions, trillions, down to order of magnitude of how many blocks you've launched, which is a few thousand.

BryceAnd uh then you do a second pass, and it could even be a serial pass, but the way that we do it in Cub is we do a second pass, which is we launch a single block to reduce those values from the the to reduce this the aggregate sums from each one of the first passes blocks into a single result. And this approach requires no communication between blocks.

BryceSo it's embarrassingly parallel across blocks. And this is why reduce by key has to be implemented with a scan. Because for reduced by key, we can't, I think, do a two-pass approach like that because you have to handle the ends of each one of the reduced by key groups.

BryceRight? Like what if what if one of the blocks in the first pass spans two groups or three groups or four groups?

ConorYeah. I mean that's covered by, like I said, the same way where we had the whole missing reduction episode and we were doing the maximum consecutive ones where you had to build that struct that like carried that information.

BryceBut we could we could build a d so the thing that we use to communicate between blocks in a scan is called decoupled look back. And if you want to learn more about that, come to my think parallel talk. Um but uh there's no reason that we couldn't use I think the two pass reduce would still work.

ConorYou just maybe it would. You just need to be smart about it's like it's similar, it's we've had we've talked about it.

BryceBut even if even if it doesn't, um you could do it in one pass with a decoupled look back reduce. That's that's probably slower. We don't even have that right now.

ConorThat's probably slower. I thought that we only have to be able to do it.

BryceAll of the pieces are there. You can actually the communication thing, which is like called like tile prefix callback up or something like that in Cub, that thing is not, I think, specific to scan. Um there's certainly there's a version of it for reduced by key. Um the it is weird that it does the scan.

ConorI I wonder if that Bryce is coming over to the dark side.

BryceI I wonder if the scan is necessary because of the keys.

ConorBecause we usually we usually do a scan anytime we have keys, but why? But but like this is right around the screen.

BryceLet's go back to the let's go back to the two paths reduced by key. Um I'm not convinced that works.

ConorBe sure to check these show notes either in your podcast app or at adsphepodcast.com for links to anything we mentioned in today's episode, as well as a link to a GitHub discussion where you can leave thoughts, comments, and questions. Thanks for listening. We hope you enjoyed and have a great day.

BryceLow quality! High quality. That is the tagline of our podcast.

ConorThat's not the tagline. Our tagline is chaos with sprinkles of information.

Open the transcript file

Hosts and Guests

Nobody is credited on this episode yet.

Credit the people on this episode

Be the first to rate this episode

More episodes

All episodes
  1. Episode 313: C++26 Reflection vs CRTP, AI, Kids & More with Zach Laine

    Nov 20, 202647 minAudio

    In this episode, Conor and Bryce chat with Zach Laine about C++26 Reflection vs CRTP, AI, kids & more. Link to Episode 313 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP:...

    • Apple Podcasts

    Credit the people on this episode

  2. Episode 312: The C++26 Contracts Fiasco

    Nov 13, 202652 minAudio

    In this episode, Conor and Bryce chat with Zach Laine about the C++26 contracts fiasco. Link to Episode 312 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The Podcast:...

    • Apple Podcasts

    Credit the people on this episode

  3. Episode 311: Career Changes, GPUs & More with Zach Laine

    Nov 6, 202628 minAudio

    In this episode, Conor and Bryce talk with Zach Laine about his career and the career changes he has made. Link to Episode 311 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials...

    • Apple Podcasts

    Credit the people on this episode

  4. Episode 310: Leaving NVIDIA for... ?

    Oct 30, 202624 minAudio

    In this episode, Conor and Bryce talk about Bryce's next chapter and where he is leaving NVIDIA for. Link to Episode 310 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The...

    • Apple Podcasts

    Credit the people on this episode

  5. Episode 309: Default Construction & CppCon 2026 with Jason Turner

    Oct 23, 202629 minAudio

    In this episode, Conor and Ben chat with Jason Turner about default construction in C++. Link to Episode 309 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The Podcast:...

    • Apple Podcasts

    Credit the people on this episode