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 173: Parallel chunk_by

Mar 15, 202430 minAudio

In this episode, Conor and Bryce talking about grouping / cut operations and parallel chunk_by. Link to Episode 173 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-15 J cuts C++23 std::views::chunk_by C++20 std::views::split C++23 std::views::chunk Jello Cut Table The STL Algorithm Cheat Sheet C++Now 2019 - Algorithm Intuition thrust::copy_if thrust::inclusive_scan thrust::gather 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.

ConorAnything that takes, if you're in range land in C20 or 23, a range and turns it into a range of ranges, or if you're in sequence land in Swift, a sequence into a sequence of sequences, or if you're in Haskell land and you take a list and you got a list of lists, or a string and you now have a list of strings. Anything that does that, I consider a cut. And there are four or five different types of cuts. There are index cuts, predicate cuts, function cuts, and then the last one is what I call uh FHM frequency hash map cuts. Welcome to ADSP the podcast episode 173, recorded on March 6, 2024.

ConorMy name is Connor, and today with my co-host Bryce, we chat about the category of algorithms called cuts and how to implement a parallel chunk vibe. This is what, episode 173? Whatever. No, no, no, no, no, no, no. Episode 173, because this this is what just happened, folks. We had a 30-minute episode on Bryce's apartment and couches. This will air. It was just on couches. We didn't even really talk about my. We talked about the fixtures, the brush brass. We'll send pictures of the apartment. And but you're not gonna hear that episode.

ConorSo actually, this is episode 172. That episode's probably gonna be like 170 late, high numbers, 180, because we're gonna record this algorithm episode right now. We're in Bryce's apartment. I'm visiting for the uh New York C meetup tomorrow night. We just had uh sushi last night at Sugarfish with Sean Parent of Adobe.

BryceWe went to a very mediocre comedy show.

ConorAnd we went to a very mediocre comedy show. Shout out to the actually, we're not gonna shut it up because we don't want to make them feel bad. Um But uh we went to a You know who you are. Yeah, you know who you are. And if you're from New York and you're familiar with the comedy club scene, they had mini donuts, and the mini donuts were the best part of the show. We love them, folks. We love them. Anyways, the couch episode and the uh apartment episode isn't gonna come out for a few episodes. Why is that? Because we're gonna do the algorithm episode right now. That's gonna air in like two days on uh March 8th.

ConorThat'll be episode 172. Then we're gonna be recording with Sean Parent live, I think, at Adobe Headquarters, not headquarters, at the New York Adobe Offices. Adobe HQ is back where Sean lives in San Jose, or outside San Jose. I mean the HQ is in San Jose. Sean doesn't live in San Jose. Anyways, trying trying not to dock Sean here, uh, but he lives near San Jose. Anyways, um, and so we're gonna do probably a one-part or two-part episode with Sean. That's gonna be episode 173, 174, and then maybe we'll save the couch episode for when we run low and we need like a backup one, and then that's when it'll air.

ConorSo maybe it might not even be till like the 220s. Who knows? Also, folks, it's been about what, six, seven episodes in a row where we haven't had a guest. That's not for lack of trying. We now have we now have uh DuckDB individual uh who we actually haven't confirmed the time yet.

BryceI think, Connor, I I think you should not announce guests until we have the recording of the guests.

ConorNope, they're coming on. We've they said they'd be willing. We just haven't set up the final time. And scheduled. And we have who reached out. We said if you're if you are listening or if one of your friends is listening.

BryceWell, wait, we haven't even scheduled it.

ConorWe haven't scheduled it. It's gonna happen, though.

BryceDid he write us back? He did. And then did I reply with times? He did.

ConorUh not with times. Yeah. He did write us back though. Anyways, name him. We're gonna have Doug Greger on this one. Woo! We're gonna have Doug Greger on. So we got a couple different people, and we've got Sean coming up. So don't worry. If you're tired of these mono emo with your two co-hosts in 2024, don't worry, we're fixing it.

BryceAnd now, after four minutes of pre-speaking we're gonna talk about you're thinking about grouping operations wrong. I've just been I've just been waiting to pounce. I've just been sick. Also, also, first of all, waiting to pounce brief for now.

ConorLet's do a brief overview of what a grouping operation is. Because I call them, I actually have a new category name for them. They're called cut operations, not grouping.

BryceUh you you do the brief overview, and then you tell me when I can uh when I can fire this load.

ConorIt's brief. There's this new, I mean, we've talked about these lots. Here's a few examples chunk by, splits, chunks, uh, etc. Anything that takes, if you're in range land in C 20 or 23, a range and turns it into a range of ranges, or if you're in sequence land in Swift, a sequence into a sequence of sequences, or if you're in Haskell land and you take a list and you got a list of lists, or a string and you now have a list of strings. Anything that does that, I consider a cut. And there are four or five different types of cuts. There are index cuts, predicate cuts, function cuts, and then the last one is what I call uh FHM frequency hash map cuts.

ConorAnd technically when it comes to predicate cuts, there's different types, unary and binary predicates. Anyways, if Bryce is curious of the different types of cuts, we can get into it. But basically anything that chunks or dices things up, there you go. Alright, so uh a little more context, Connor, and I and by the way, there was only uh 50 seconds, and you got to I've been trying to work on uh not rambling as much because I've gotten some feedback from people, you know, that I just uh remember that one time you asked for me to describe No, don't care. Shut up and listen. Shut up and listen to me.

BryceOkay, a little bit of context. Uh I've been working on a project to figure out how to um uh paralyze uh C ranges in particular, how to deal with um range uh adapters um uh in in ranges that we might want to uh paralyze in C recently. Um and uh some of the uh tricky ones to deal with are the grouping operations like chunk buy and split. Now, Connor, um, and so Connor and I have been talking about this a bit during the day, and so you, the listener, may not have all the context here.

BryceI don't care.

ConorAnd we love that because you know it's been four years since I've been in an office next to someone where you get to chat about work while working.

BryceI mean, hey, you you did you did give me you did give me today uh you either well I I think you later said that you didn't come up with the clever idea, but you you certainly I got I got you half I started you halfway there and then you made an insight on top of my insight. So very well, I'm sure we'll do an upset about that. So here's the thing about grouping operations. Uh you I think are thinking about them wrong. Um because I I I I earlier you made a comment that that they are not removal operations, that they are not like filtering operations.

ConorSome of them are, some of them aren't.

BryceYou you started you started mansplaining to me chunk buy.

ConorFirst of all, can you mansplain to a man? Yeah, you can.

BryceCan you?

ConorYeah. That's a whole other episode.

BryceDude, we're not tangenting now. Make your argument.

ConorWhat?

BryceYou you you were claiming that chunk buy is not in our removal operation.

ConorChunk by is definitely not uh so I have a table inside my Jell-O project where I categorize these types of cuts. And there is a similar to that algorithm table that I had back in C now, 2019's algorithm intuition, where you've got reduced, scan, etc., and then some of them are maps versus reduces. Some of them look at one indexes versus two indexes, etc. This table, one of the columns, that's a binary column, it's either yes or no, is does it drop elements? And chunk by does not drop elements.

BryceIt doesn't drop elements, yes. But it doesn't drop anything. Okay. But you're thinking about it wrong for the purposes of parallelism. Okay. The way that we tackle almost any parallel programming challenge is the first thing we do is work distribution. We take our input and we come up with some strategy for how we're going to distribute it among a group of threads.

BryceYeah? In the case of these like array language operations and things like C ranges, we have some input sequence or data of length n. And typically what we do is we take that n and we divide it up equally or as equally as possible among M threads. Now, when we have something like a filter or chunk by that is going to change the shape of that original N inputs, but it changes it in a way that is not that cannot be known a priori, then we have to discover the the change of the shape in parallel.

BryceSo if it's something like chunk, if it's something like stride, right, where we say we're gonna take every third element, we can simply hand that handle that during work distribution. If we have something like stride, we can just say, okay, we're just gonna pretend, we're just gonna pretend that the input's actually, you know, n divided by three, and then we're going to split up that n divided by three input among the M threads that we have.

ConorYeah, that makes sense.

BryceAnd like likewise for chunk, if we have like chunk three, um, but if we have chunk by, we don't know what uh the size of those groups are gonna be. We don't know how many we're going to have. In the same way that with filter, we don't know how many elements we're gonna have on the other side. So we can't divide uh it up evenly among the threads. We have to, in fact, part of the thing that we're paralyzing is the non-trivial computation of the reshaping.

BryceIn the case of the filter, the non-trivial computation is applying the predicate, and likewise in chunk bi. So, but we still have to do work distribution. And if we can't compute a priori how the shape is going to change, then we must do work distribution based upon that original in elements of input. And so every thread is going to get n divided by m pieces of work.

BryceOkay.

ConorI don't see how anything has had to do with dropping yet though. Right.

BryceSo for something like chunk buy, at least on a platform like a GPU platform, we don't want to create new threads. We want to figure out the chunks, and then we want to like create those chunks and then continue processing the rest of this pipeline of operations after the chunk buy with that same group of threads. So like if we have like chunk by transform like pipe transform, we want to figure out what those chunks are, and then we want to apply, we want to, with those same groups of threads, we want to have them apply the transform function.

BryceSo if we've got M threads, each of which are given in initial pieces of work, then we need to figure out like which one of these threads are going to need to call this transform function. Because it's not going to be every thread. I mean, in the it it it could be. You could you you could be have a chunk by function that makes everything into a chunk of one element. That's that's the limit for the most number of chunks that you can have.

BryceBut let's assume that that's not the case, that we're going to end up with fewer chunks than we had initial elements. In that sense, so then in in that uh situation, when we get to that transform operation after the chunking operation, some of the threads that own some of those original in input items, some of those threads are not going to participate in the transform operation. Because we don't need all of them to participate.

BryceWe don't have n chunks. We have some number less than in chunks. And so we need some way for those threads to decide which, you know, who's gonna do which, which which of these original in pieces of work that we were given are no longer valid. And that process of deciding who's gonna handle the chunks is very similar to how we paralyze removal.

BryceNow let's talk about the algorithm that I was working on last week and was excited to talk about.

ConorOh, we wanted to get some more channels. We can't move on yet.

BryceWe're not moving on, we're talking about how do you implement chunk buy in parallel. In one second. Hang on. I will be right back because I need to look at the signature on my computer.

ConorAlright, well, Bryce is over there. I mean, I'm not fully buying what he's selling, folks. First of all, I'd like an example of the transform operation that he says we're applying to each chunk that has resulted from the chunk buy.

BryceI'm saying if you have chunk buy pipe transform. Yeah, that's what I just said. It's just an arbitrary chunk buy followed by transform.

ConorUh, okay.

BryceLike, well, what do you what do you mean? Are you saying do you want do you want an example of how you would use chunk buy in a pipeline?

ConorI can come up with a ton of examples, but what the reason is why I'm asking for one that might be a good thing.

BryceHere's one. Here's one. Take an input of of text and uh like compute um the the like average length of every word.

ConorThat was I literally as soon as you said the text thing, that's where I thought you were going. So, this is an example where everything that Bryce said doesn't need to apply. Because every thread will get used. An exam like where you are doing a reduction, this is the the one of the easiest things. You're gonna have to move closer because I'm gonna have to read my computer. Well, now I'm recording a podcast. A local friend, Phineas of the Pod. What is it? He's a friend of mine has just uh messaged me.

ConorUh and now we gotta reply back. Recording pod right now.

BryceGood luck editing this section, Connor.

ConorMaybe we'll just leave it in.

BryceUh you better not.

ConorReply quality content we have here. A few minutes. And do you think I'm gonna be done with you in a few minutes? Yeah, well, that's you know, it's it could mean more than that. Anyways, um, so because basically you've got your chunk by and you're chunking by uh spaces, which is gonna give you words or maybe something a little bit more complicated than that. And then your transform is a ranges colon stood colon colon ranges, colon colon distance, which you can think of as a reduction. You definitely can just do that.

ConorIt doesn't matter if like where your blocks are split, you know, that was across a word, because you can just handle that, you know. Oh, the length of this string is three, and the length of this string is two, that was across a border, you just add them together. There's no threads that weren't doing work. Like, so in that example, anytime basically where you're how are there not any threads doing work? Because all of them are doing are are calculating the length of uh the elements that are in your chunk. Why would any th why would any thread not need to do that computation?

BryceOkay, let's say that we have well now he's changing the example. See, and this is No, we're gonna use the same example. Okay. Let's say that we've got some input string of text that has four words in it. Okay? And let's say that it has in total um each word is like four characters long. There's a space after each one, so we have twenty characters total in the input. Okay.

BryceSo we spin up, let's say, twenty threads, each of which is given a single character. And then we apply what?

ConorHow is a th every thread given a single character?

BryceHow are you able to compare it's an example, Connor?

ConorBut how are you supposed to uh calculate like each thread needs at least more than one character?

BryceEvery every thread is responsible for one character. It's it's looking at adjacent characters because that's how chunk buy works, but it's computing the answer for the predicate for one character. Every thread is is checking the predicate for one character, and yes, that may require it to look at a second character, but that's not the character that that thread is responsible for. So you have 20 threads, each of which is going to run the predicate and determine whether this is the end of a word.

BryceRight? Okay. So are you are you somehow claiming that all 20 of those threads are going to run the transform function that calls distance on each one of those chunks? No. Only four of those threads are going to run distance on the chunk because there's only four words. There aren't 20 words, there's only four words.

ConorHow do you figure out the length of the word now that every thread only has one character? There has to be some like thread communication stuff now that and now all the threads need to communicate. So that's work.

BryceYes. But I mean, how else how else would we we divide this problem? How do how do threads how do we have the threads communicate? What is the number one most common communication mechanism that we use? Scans. And for it, for we perhaps haven't talked about this before. Scan is not an algorithm. Scan is a communication mechanism. Scan and a uh uh a non-commutative reduction where where information goes from left to right are communication mechanisms. They are they are uh synchronization primitives for threads to communicate to threads that are later in the computation.

BryceConnor, put your phone away. Put your phone away.

ConorYou just got invited though, so uh You put your phone away. My girlfriend's calling me at the same time. Yeah, well, you know what?

BrycePriorities, buddy. Priorities.

ConorHow do Hey, sweetie?

BryceShe makes he can't talk right now. Sorry, we're recording the podcast.

ConorDid you hear that she Okay, that's my cut of though. Okay, call me later? Sure. Do you want to say anything to uh all the listeners?

BryceNo. All right, we're moving on.

ConorAll right, I'll call you later.

BryceOkay. Okay. I will read you a little bit. You gotta move a little closer so I can read this from this uh document I've been working on. Move the mic a little closer. Stop texting your girlfriend. I'm texting Phineas. We're having dinner with him later.

ConorWe're having dinner with him later.

BryceI don't care whether you're texting Phineas, I don't care who you're text- you're texting. Okay. You and I, I don't know if we've talked about this before, but I think it's not particularly relevant. So this is for my little document on how we paralyze ranges and parallel algorithms. Can I ask a question? No.

ConorOkay.

BryceCertain range adapters group or combine elements in a way that cannot be trivially computed a priori. And that's how I think about chunk buy. Not as like I think about it as combining elements together. And that I think is the correct mindset to lead us to the parallel algorithm for chunk by. These adapters reduce the size of the input sequence. When considering how to parallelize them, we should think of them as both transforming and removing elements.

BryceA parallel implementation of these adapters must do two things. Also, is this your paper that's a parallel implementation of these adapters must do two things. Compute the groupings, which requires some form of summation. Discard whichever of the M initial elements per execution agent do not represent one of the groupings. So the computation of those groupings can be implemented by inserting some sort of in-place scan pre-processing pass.

BryceBecause as I don't know that we've talked about how you implement like copy if in parallel before in this podcast, have we?

ConorNope.

BryceOh, well, maybe we're gonna talk about that next. But just take it- We've only got 10 minutes left, so as a given that we can implement copy if in terms of scan. We have talked about that at least, that copy if is implemented in terms of scan has come up. So then my paper says, as discussed in the non-trivial removal section.

ConorWhat are you doing with the mic, man? What are you stop? You're making makeup.

BryceAs discussed in the non-trivial removal section, the removal of elements can be done by inserting an in-place copy if preprocessing pass. And copy if can be implemented. Stop squeezing the mic like that at the time. And copy if can be impl I'm starting this part over. As discussed in the non trivial removal section, the removal of elements can be done by inserting an in place copy if preprocessing pass. And copy if can be implemented with a scan. So, for our purposes which aren't particularly worried about ranges, what my point there is copy if can be implemented with a scan.

ConorSo wait.

BryceHang on, I'm not done yet. I'll tell you why you can talk. So filtering operations, removing operations like copy if can be implemented with a scan. Now, these two operations of needing to remove element of computing the groupings and needing to remove elements can be combined into a single scan-based pre-processing pass that both computes the groupings and removes all but one element port per grouping. Okay. Have we ever uh implement copy if in terms of scan?

ConorWait, can I ask a question? Can I ask questions now?

BryceNo, you can implement copy if in terms of scan.

ConorWhat is happening? Um I need to ask a question.

BryceYeah.

ConorOkay, can I ask one? Yeah. I'd like to ask two, but I'll I'll settle for one. It better be a time. Definitely about what you just said. So are you it it hurts my soul to hear that like the size of the input sequence is decreasing because in a sense that is true, because I remember you saying this in a meeting once that like when a range goes through a cut operation or a grouping operation as you call it, and it becomes a range of ranges, now the size of technically the outer range has decreased from whatever, 20 to 4.

BryceYeah.

ConorWe agree, but like to say that the size of the input is decreasing, like all those elements are still there. They're just like they're just being interrangified.

BryceBut this is this is a this is a mindset that represents how we f implement this physically in parallel on a massively parallel processor like a GPU?

ConorSo that's what that's what my question is. Is so when you're saying that you've got your 20, your 20 threads, yeah, and then you end up with only four threads doing work, is that because you gave all the data of the other 16 threads to each of those four threads?

BryceYeah.

ConorAnd how did you do that?

BryceBecause it's with a reduction. With like a reduced by key or a scan. That was my second question. Is how does reduce by key work? All right. We're we're gonna we're gonna get there. We're gonna get there. Are we? How do we implement copy if in parallel?

ConorCopy if in parallel. I would imagine, well, I wouldn't imagine, if I had to do it, I would so copy if, for those that don't know, is a algorithm similar to copy, but it takes a unary predicate and only copies the element uh if it satisfies that predicate. And there's actually a couple different overloads that we've talked about in past episodes. Anyways, how do we implement it? I would basically do a scan on a transformed sequence representing ones and zeros that are basically corresponding to whether each element uh returned true for the unary predicate.

ConorYou do a plus scan on that to get the resulting indices, and then you do a gather operation and you're done.

BryceYes. Um this is well, you can look at the code now. Um I will explain it in a slightly different way. To implement the naive way of implementing a scan in parallel, I'm gonna describe a three-pass approach which needs uh two ON uh uh vectors. So the first pass is we compute the flags. So we create a vector of flags, which are just booleans, except it can't be a vector bool because that's broken in C.

BryceBut we have a um a vector of bools or flags, and we do a transform where we run the predicate for each one of the input elements, and we assign the results of that into this flags vector. And so we have n flags, one for each of the input elements, and that flag is true if the predicate returned true and false otherwise.

ConorYou don't even need to do that.

BryceYou can but it's it for the purposes of explaining it, this is a bit the very simple, elegant version of this algorithm. Then we have to build our second vector of information, which is the indices of uh where elements are that are going to be copied are going to move to. And to do that, we scan the flags array, and we write the results of that scan into a vector of uh ints, one int for each input element.

BryceAnd that scan will build up the index that each element for which the predicate is true should be assigned to. And then that gather operation that Connor mentioned, in thrust we have a thing called thrust gather, but we don't in standard C, but it's pretty easy to implement. Um, the way I have it written here is I've got a for each over a zip of the original input, the flags array, and the indices array.

BryceAnd so this the the function uh that's passed to this for each, it's gonna take three inputs, the an element, a flag, and an index. And what that function does is if the flag is true, then it will assign to that that index in the output the uh uh the element's value.

BryceAnd then to compute the range of like how large the output that you've created is, um, you just take the the last index um uh from the uh uh from the uh scan that you did. And that is the size of the output.

ConorAnd after that explanation, I realized that the gather that I was referring to, I I was being a little laxadaisical, a little loose. I should have said what I specifically meant was a gather if, which is what you just described.

BryceYes.

ConorAll right, folks. Well, that's the end of the episode.

BryceUh it's not. It is not in no way, shape, or form the end of the episode.

ConorYou hear that, folks? That's the sound of Bryce's mic not next to his move.

BryceWell, because this thing is this is not the end of the episode. Okay, Connor.

ConorBe sure to check these show notes either in your podcast app or at adspthepodcast.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