In this episode, Conor and Bryce continue their conversation on parallel chunk_by. Link to Episode 175 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-29 C++23 std::views::chunk_by thrust::reduce J Folds thrust::inclusive_scan cub::DeviceSegmentedReduce NVIDIA AI Podcast 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.
BryceThe the thing with the scan is that a the decoupled look back is a clever way to do a scan, but there's still this serial dependence. So the like the decoupled look back lets everybody do their local scan and writing the the results of their local scan, like the sum of all the threads in their block to uh an aggregate that lets everybody do that in parallel. And that's all something that everybody's gonna do in roughly the same time.
ConorWelcome to ADSP the podcast, episode 175, recorded on March 6, 2024. My name is Connor, and today with my co-host Bryce, we continue our conversation on parallel chunk by as well as talk about a few random topics including stickers, the NVIDIA AI podcast, and more.
BryceLet's go back to the two-paths reduced by key. Um, I'm not convinced that works.
ConorWow.
BryceBecause um well, you explain to me how you think it would work.
ConorIs a reduce allowed to reduce a vector? Like imagine we're doing our uh reduce by key, but we know that we're gonna end up with a vector of reductions. Correct?
BryceYeah.
ConorAnd as long as I'm allowed to build up some kind of struct that handles, you know, it's one of those operator overloaded structs that knows how to combine a struct with the initial value, an initial value with a struct, a struct with a struct, as long as it's got all those things, at some points So for so for what it's worth, I have now started to prefer to not write those that way.
BryceWhat I prefer to do is what I did in the um chunk buy, where instead of m writing an operator that handles all the cases, I simply figure out how do I transform the sequence so that it's homogeneous. And so that's like, okay, if I have if I have Boolean flags, how do I turn a Boolean flag into one of my interval objects? And that just makes it a whole lot cleaner.
ConorRight. Yes, and that is that is like a classic thing in array programming where sometimes you need to do a scan, but a scan, you output the result of your operation, but you need to the stuff that you want to carry is different. So you kind of need these two pieces of information. What do you do there? And in J, uh, the APL 2.0, they actually have a special kind of algorithm and there's like six different flavors of it called fold, which is specifically for this. When you want to like carry state but output a different value at each index, uh, you can do that.
ConorBut anyways, same idea. And so like if you've got a block that is the chunk is bigger than the block on both sides, your result of that is is like your little you know reductions vector, it's gonna just have a single value in it uh because it's gonna get added with you know things on the left and things on the right. Uh but if you've got a bunch of chunks within your block, your reductions vector is gonna have a couple values in it because there's gonna be one for each chunk. And when you get to your second pass reduction, all it's doing is you're gonna have basically a vector of vectors that have got like some have got one reduction, some have got five reductions, and some of them but how do we how do we allocate the space for those?
BryceThat's the problem.
ConorYou can figure that out up front.
BryceHow can you figure that out?
ConorYou just do the chunk by, you do the uh pass, you don't even need to do a scan there. You can do a transform zip iterator trick to apply your uh binary predicate, and then you you're gonna get your flags. So basically you calculate your flags, and then you know what, because your size of your blocks, you can just look how many vectors are we gonna need in here. And if you see if you see no flags in your block, you know you just need one value.
BryceIf you see three flags, you know you're gonna need to but but but we can't um we can't do the allocation device size. We have to do it before we launch.
ConorThat's fine. We could do that.
BryceUm but that might require a first parallel pass to figure that out.
ConorSo and maybe this is why at the end of the day, like maybe the scan is more efficient.
BryceBut in my head, I I find I actually find it hard to believe the scan is more efficient. The the thing with the scan is that um the decoupled look back is a clever way to do a scan, but there's still this serial dependence. So the like the decoupled look back lets everybody do their local scan and writing the the results of their local scan, like the sum of all the threads in their block, to an aggregate that lets everybody do that in parallel. And that's all something that everybody's gonna do in roughly the same time. Um and then it paralyzes the computation of the the prefixes that every block needs.
BryceUm, but it still ultimately has a serial dependence that for given a block given a chunk of elements i um for you to complete the scan of those elements i all i minus one chunks must have completed. Um and that is that is that is a this monotonic uh requirement is tough, whereas the reduce is just strictly embarrassingly parallel.
BryceThere's no communication or contention outside of within these like local little um blocks. Or like another way to think about it, forget forget blocks, like delete blocks from your vocabulary for a minute, uh and think about it in terms of CPU parallelism. So GPU parallelism has this second layer of both, you know, there's thread blocks, um, which are kind of uh uh like the the basic the SIMPT execution environment where you have these threads that are all executing together.
BryceUm but if we think about it just in terms of like CPU parallelism, where we don't have that second layer and where it's just threads, um the the equivalent CPU parallel reduce would be a reduce where you just spin up in threads, have each one of them reduce some amount of elements, and then write the result for that thread into a vector. And then the second pass would be just you just have one thread sum up that vector. And that first pass is 100% embarrassing parallel.
BryceLike there's no communication at all, which is like the best type of parallel algorithm. Whereas the scan, any form of the scan algorithm, has threads talking to each other. So I do find it unless there is some structural reason for needing the scan for the bi-key algorithms, and there's a lot of people way smarter than me that work on Cubs, so you know that's probably the case. But then again, there's also some times when we do find things like this that could actually be faster. But I I do find it questionable.
BryceI do find it questionable, and I wonder whether a two-pass reduction would work. Yeah, the thing that Connor's describing, I think, is actually very tricky because I would hate to have to do a pre-pass to compute where the key chunks end.
ConorUm I guess yeah, that's what you're saying.
BryceYeah, you you do you do because we need to figure out where the storage goes. We need to know how many keys we end up with.
ConorUm, it's time to write down folks.
BryceOh, wait, wait, wait, okay, okay, okay, hang on. Future episode? No, no, no, hang on, hang on.
ConorUm It's an hour and forty minutes now. This is supposed to be three minutes.
BryceSo maybe maybe we talk about a three-pass thing where pass number one is just count how many you know, unique key segments we have. Count how many um uh chunks we have, um then allocate attempt storage for those chunks, then do pass two, which is the um uh which is the reduce uh the aggregate reduce, and then pass three is the um uh the summation of uh of the aggregates.
ConorWhat's the cost also of launching like another a possible implementation of reduce by key is you just launch one block for every chunk and every chunk is just arbitrarily sized. What's like over?
BryceThat's basic that's basically what that's basically how the reductions work. What do you mean that's how the redu the what is the reductions uh well they they the number of items per thread for reduction, or at least for reduce, I think the number of items per thread isn't uh fixed in the same way that it is for scan. Um it will it it picks a number of items per thread, but then it also it iterates so that it um I think that the number of blocks is fixed for reduce.
ConorSo for like for scan, because of like But like couldn't you implement a kernel that like launches a block with our arbitrary number of elements each like for every chunk you just launch a block?
BryceLike I don't uh it to me that obviously has some kind of overhead compared to just launching uh uh you're saying to launch a block for every chunk in the in, but then they may be they may be different.
ConorThey're definitely they're almost definitely gonna be different, and some of them are also gonna be very small, some of them are gonna be big.
BryceYeah, so you can't you can't have you can't have different block sizes. Um that is an interesting idea. Um, you know, we have this segmented reduced thing, which is when you have different actual inputs or like a uh scatter-gather thing that Georgie worked on. Um, yeah, it's one of our co-workers. He's very he's very smart. He's like if you like cloned Connor and I like he's like smarter than like ten uh of me and Connors.
BryceLike it's ten of me's and ten of Connors. Um he's very good. Um so for segment and reduce, I remember he there was some interesting thing about like sorting the size of the segments. Um and like I think it broke down to like having three phases where there's like big segments go first and then like medium segments and then small segments. I remember something about that. We should talk about the segmented reduce too, because those are the newer algorithms in Cub.
ConorI've not even when honestly, when you said segmented reduce, I was like, is my guy just referring to what we've been talking to about for like the last 45 minutes. Maybe we should have Georgie. Literally, also, too, when you just said he's he's worth 20 of you and I combined, I was like, well, why isn't he on the podcast? Here we are bumbling around for an hour and a half. I mean 30 minutes was your case.
BryceI think that I think that one of the nice things about the podcast is that um people most programmers can connect to the struggle. Yeah, and and the reality is that even for somebody like Georgie or Sean Parent, who are brilliant programmers who are far smarter than us, they like everybody's experience is um uh subjective.
BryceAnd so I'm sure that for like no matter what your intelligence level is, you can connect with the struggle. Right? Like that's that's one of the reasons why this podcast and this podcast format works, is because no matter what level you're at, no matter your your your skill set, your your learning, um regardless of how uh intelligent you may think you are, um everybody struggles. Even the people who are like who you look up to, they struggle too.
BryceAnd uh it's very uh therapeutic to see other people struggle and be like, oh yeah, it's not just me. Other people struggle too. And I think that's why people tolerate the pot the chaos of the podcast. Um, because there's something very human and uh the there's something very human about the struggle, and there's something very human about like us making mistakes and being okay with making mistakes and advertising those mistakes to the world.
ConorWell, I mean ideally, you know, we're not we're not here to advertise our mistakes, they just happen and people get to hear them.
BryceIdeally, we could that's that that like that's that's what that that's what people connect with, I think, in the podcast. Yeah. It's not like us just being like, oh, here's how, you know, like here's how this thing works. It's mostly like, oh well, we don't know, let's go find out. Okay, so I gotta add a new to-do list item, which is we need to figure out what's going on with reduced by key and whether we can do a better algorithm there, but that's gonna require some some thought.
ConorAnd we're gonna bring on Georgie. We should bring on Jake as well. We've mentioned Jake a couple times. We mentioned the CCCL, CCCL GitHub repo. He's in charge of all this stuff now. He should be on the pod. So there you have I actually don't know what's gonna happen now, folks. Maybe I'll put this at the beginning because this was an hour and twenty minutes after the 30-minute couch episode. I just said you'd hear the couch episode in like 20 episodes, but maybe I am gonna edit the couch episode.
BryceYou promised, Connor, you bastard! You promised.
ConorWhat?
BryceYou promised not to 10x me. No 10x.
ConorNo, no, no, no, no. I said me what I was saying is I was I said the couch episode would be in like 20 episodes because I wanted to edit this one for Friday and then leave the couch episode. But now this one is an hour and 20 minutes, which doesn't go into all one episode. So it's probably gonna get cut up into three parts or at least two parts. I have no idea what the one is. And so the problem, I don't mind editing the first part of this, but the problem is then I want to get Sean's episodes out uh right after we record them.
BryceWe didn't we didn't even talk about the fact that the Norwegian ambassador to the UN lives in the penthouse in my building.
ConorYeah, it's unimportant. Uh all right, folks. Uh we are gonna we're gonna wrap this up. Phineas has been waiting.
BryceOh god, there's somebody who's been waiting this whole time.
ConorThat's who you told me not to message while we were recording the pod.
BryceNo, I did tell you not to message.
ConorMaybe I'll cut all of this out.
BryceNot a chance.
ConorNot a chance. That's the guy that does none of the editing. And doesn't you know.
BryceI still haven't listened to the end of phone tag.
ConorYou're a terrible friend, bro.
BryceIt's been a while.
ConorYou're a great friend in some respects, and you're a terrible friend in other respects.
BryceI'm really interested to know, though. Maybe on my flight to Japan. All right, we should probably wrap it here.
ConorAlright, folks, this is probably this is like probably either one episode 176 or episode like 179. It's I'm curious just for myself. I'll be editing it at some point this like two months in the future, and I want to see how close I was to it, if I was right with 176 or 179. Woo, we're getting close to 200.
BryceYeah, what are we gonna do for episode 200?
ConorRemember, we recorded a special two uh uh two episode 200 back at like episode 40?
BryceI have no recollection of what I said. What did we say about episode 200?
ConorDo you even remember the topic?
BryceI don't.
ConorWow.
BryceI'm gonna I'm gonna Yep, you have to tell me because you know I won't listen to it.
ConorI'm gonna say I was literally about to say, you know, there's one way to guarantee that I can get Bryce to listen to at least one episode out of our first 200, and that'll be episode 200 when I air it without us recording, and he'll be like, wait, what? And I'll be like, Well, you're gonna have to listen.
BryceWait, did we record an entire episode?
ConorI think we record we recorded, oh yeah, actually, truth be told, I think we recorded half of an episode, and the idea was we made some predictions and we were gonna revisit them. Wait, wait, wait.
BryceWhen would we have recorded these predictions?
ConorUh I think it was around like episode 40 or something.
BryceWhat year would that have been?
ConorThat would have been we started in 2019, so 40 would have been in 2020.
BryceOkay. Would that have been in 2020 before I became jaded and salty about C?
ConorUh no, I think it was before.
BryceOh crap. Then most of those predictions are probably bad ones.
ConorThis this little bit right here, I'm gonna splice I gotta remember whatever episode this was. Hopefully it was 179. I'm gonna splice this little bit where Bryce is clearly has no idea what he said.
BryceI really have no idea.
ConorDoesn't know the topic, doesn't know what he said.
BryceI mean, that was pre-me moving to New York, even.
ConorYeah, yeah, it was just like mid-pandemic. Um actually, no, it was it was probably like the summer of 2020.
BryceWhy did I even record then? God, I just have no memory of what happened in life before the last like year or two.
ConorThis is good stuff too. Honestly, I've gotta start I've gotta start looking to see what other podcasts have gone weekly this long. Because I'm pretty sure uh we're getting I'm pretty sure there's a couple out there that have done a couple thousand that have never missed a missed a week. But uh as far as tech podcasts goes, I think I think we've We've come close to missing weeks.
BryceLike the pat the pat the past month or two has been week to week. It's been week to week.
ConorLet me rephrase what Bryce uh Bryce is incorrect. Bryce, what really happened is we got close to you not being on the podcast and me just recording separately for 30 minutes going blah, blah, blah, blah, blah. Guess what? This is episode 169. Bryce, uh, we weren't able to connect, and there's no way even if, even if, listeners, one day you get like a three-minute episode. I promise. I promise. I don't I'll need to be close to dead, you know, uh, in order for us. I shouldn't say that, because a knock on knock on walnut.
ConorThat was that was uh here. Let's get that walnut, that walnut ring just a little bit cleaner on the pod. Uh knock on wood, that won't happen. Um, anyways, any final words because we're now at an hour 53 minutes.
BryceNow I'm getting sentimental about my uh coffee table. I do have to get rid of it. We're gonna end it there, folks. If you live in New York City and you'd like uh Bryce's coffee table, uh DM me, I guess.
ConorWe should actually give it away. We should give it away as like a podcast. You know, that would actually it's a it's a decent honestly, Bryce is saying it's dinged up and whatnot, but like Bryce, right, like this is this is a very nice coffee table. I'm running my hands on it. Like, sure, there's a couple, there's a couple blemishes on the top of the city.
BryceI'm not getting I'm not getting rid of it because there's any problem of uh with it. I'm getting rid of it because not some of the furniture like my girlfriend and I are getting a larger place together this summer, and some of the furniture that is my furniture has to go away, and some of the furniture that is her furniture has to go away. And while I love this coffee table and it is my oldest piece of furniture, um it is one that is going away.
ConorAnd you know what we should do? We should get the ADSP logo like like etched into the corner, and we make it like an ADSP episode 200, because episode 200 is gonna be like September timeline.
BryceAre you telling me I have to figure out how to ship this coffee table?
ConorUh, I mean, uh, yeah, we'd have to, we'd uh we'd have to do that. But like I think it could be worth it, you know. We're at we might start a Patreon, folks. Listen, this is like episode 179 now. The Adobe C meetup, New York meetup people are not getting ADSP stickers tomorrow. That's because one, I forgot about it last week, but two, over the last two days, I've been looking into New York sticker options. I got quoted for I think it was 100 stickers,$329.
BryceConnor, they they pay us very well at the NVIDIA questions.
ConorI know, I know, I know. But I've there was other options that were less than 100 for like 200 stickers. Anyways, point is is that uh, and also two, I really what I want is I've I've learned they're called die-in stickers, and they have like the little white border around them. It needs to be rounded corners. I don't want, I don't want like because if they would have gotten stickers, they would have been like sheets of stickers where they were square with no border and no rounded edges. And like we want top-tier. We're not gonna give out some first draft kind of like, oh, these were last minute, but here you go.
BryceOh, this sticker's just gonna have the logo.
ConorJust the logo. We're starting off simple, and then we'll expand uh you know the merch and I do wonder whether we need a flashier logo. No, no, no, no. There's no way we're changing the logo. We I would like to change the array cast logo if you're listening, Bob. I don't like it.
BryceWhat talk do you like about it?
ConorUm, I like that I've got three podcasts, and two of them basically have the same kind of style. It's just a matte color, one's green, one's red, and then just kind of blocky text centered. It's simple, it's clean, and and like it's got equidistant, you know, bordering to the edge from all the text. Whereas a ray cast, it's got you know huge margins uh above and below the text, and it's got like negative margins on the left and right.
BryceSo that just like up you not, you would I do I do have to say one one interesting thing about this podcast name is that when we started this podcast, we picked a name that Was mostly for SEO, and I did not think that it was going to be an applicable name. And then we we went into a phase that was very heavily interview uh uh based, but then increasingly over the past year and a half, uh this podcast has become more and more like deeply algorithm focused.
ConorWell, it's also parallel, but like I I did notice a pattern that we've got an episode called Vectorizing Filter, and I think I'm gonna go back and remap rename that one parallel filter. And then since then we've had like parallel scan, I think we've had another parallel episode, but like we've had three now episodes, and this one is probably gonna be like parallel chunk by part one, two, and three.
BryceYeah.
ConorAnd uh I have no problem. I mean, I love talking about algorithms, you know. Sometimes we just get lost in the sauce.
BryceAnd when we get we never talk about the data structures.
ConorWell, I mean, every data structure is basically an algorithm anyway, is a quote I heard the other day. Um it's basically each of your operations is just a different type of algorithm. And uh we live in a GPU land where like the only data structure, not the only one, we care about graphs too. So calm down, calm down, folks.
BryceI have been thinking I have been thinking about another podcast project.
ConorWhat do you mean, like between us or just you on your own?
BryceWell, like, like shouldn't like NVIDIA have like a we do have a podcast.
ConorThere it's called the NVIDIA AI Podcast, hosted by Noah Kravitz. I listen. Is it good?
BryceIs it good?
ConorUh I listen every episode.
BryceWhat do they talk about?
ConorThey're roughly 20 to 30 minute episodes. Uh I'm am I allowed to give my honest opinion? I'm not gonna get in trouble, right?
BryceYou can give your honest opinion.
ConorYeah, it's not my favorite podcast. Um mostly what they do Is it like technical? Yeah, it's very technical, but what they do is they bring on uh representatives of companies and startups that are doing cool stuff with uh GPUs and like RTEC.
BryceAnd so it's like Okay, that is not what I had in mind.
ConorOne of the most recent ones. Um I think it was uh actually I can't remember. It was like it was like health related or something, but it's always like you know, some startup company and they're trying to figure out a way to use GPUs to affect like climate change or to do like genome sequencing or and so like you get to hear about all these stories, but like uh my favorite podcasts are one that they don't really have an ulterior motive. Like the motive there is to like highlight cool companies that are using our GPUs so you can figure out how you could use GPUs.
ConorThe motive there is to sell GPUs. Yeah, we'd and then like other podcasts, like people have courses, people have books, uh, people have like uh you know things that they're trying, it's like, oh, the bigger our audience, the more that we can sell this thing. And like uh podcasts that don't have like a goal, like Oxide and Friends, like I don't think even though Oxide and Friends, sure, maybe they get like a little bit of you know uh press or whatever, PR, like people hear about them more. Like, literally, that's just a bunch of nerds like that have a lot of seniority and have been in the industry for decades that are like talking about what's exciting to them, and like literally episode to episode, it completely changes, and it's literally just like passionate people sharing what they care about, which is what this podcast is.
ConorLike, we don't make money, we don't have sponsors, we don't really have a goal, which is very clear to the listener. Sometimes we choose a topic and then change like three minutes later. And it's the same thing with a ray cast, like it's literally like a ray cast, even more so. It's just like people talking about what they're excited about, and honestly, it's like far and fewer tweets.
BryceI want for an NVIDIA podcast, is I want a podcast where I can grill my coworkers about why CUDA is the way that it is.
ConorSo you should literally you should start a podcast because that is what I did with a ray cast. Arraycast, I honestly sometimes think of it as like my personal think tank. Like I'll come up with a question and then I'll be like, oh, look at that. Marshall Lockbaum, the creator of the language that I've been thinking about this problem in, BQN, is on the panel, and I'll just be like, all right, so today we're gonna talk about game programming, but first I've got a question for Marshall, and then the first 10 minutes of the podcast is him answering that question. It's fantastic. It's fantastic. You should call it like uh, you know, the NVIDIA think tank or the NVIDIA cab.
BryceI think.
ConorYeah, do it. And then that's the thing. You have to choose like a panel, it can even be a rotating panel, which is kind of what a ray cast is as well. So you just have four or five people, and uh the thing is you just gotta find someone to do the work similar to this podcast. Yeah, I know. That's the problem. All right, folks. It is two hours, one minute, eighteen seconds. We're signing off from Bryce's apartment.
BryceYeah, we're gonna go do a fun activity that Connor doesn't know about.
ConorAre we going to dinner first, though?
BryceOr no, I don't think you're allowed to have food.
ConorWe can't go to dinner? That's what Phineas thinks we're doing. Going to dinner.
BryceI have different plans.
ConorCan he come to the thing? He can come to the thing. Is it a thing he'd want to come to?
BryceI mean, he can come. He may not be able to leave, though.
ConorHe may not be able to leave. Is it a movie?
BryceI can't I really can't tell you any more details.
ConorAlright, we'll send Phineas a voice note, and uh, he may or may not come.
BryceYeah.
ConorAll right. Hope everybody enjoyed this. Be 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.
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:...
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:...
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...
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...
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:...