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 171: Thinking Parallel & C++ Forward Progress

Mar 1, 202424 minAudio

In this episode, Conor and Bryce chat about Bryce's upcoming talk Thinking Parallel. Link to Episode 171 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-02-22 Date Released: 2024-03-01 Thrust Library CUB Library Single-pass Parallel Prefix Scan with Decoupled Look-back Forward Progress in C++ - Olivier Giroux - CppNorth 2022 C++ Forward Progress ADSP Episode 25: The Lost Reduction GitHub CCCL Issue #774: Add non-commutative reduction ACCU Conference C++Now Conference Upcoming C++ Conferences (from Reddit) Thinking Parallel ACCU Talk 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.

BryceSo the talk's called Think Parallel, and it is a talk where I really just deep dive on how to implement a variety of different parallel algorithms and data structures, all of which sort of build on each other and sort of try to instill upon people the mindset that you and I take when trying to craft parallel code.

ConorWelcome to ADSP the podcast, episode 171, recorded on February 22nd, 2024. My name is Connor, and today my co-host Bryce previews his upcoming talk, Thinking Parallel.

BryceSo I've been working on making this new talk that I'm gonna give some part of today, assuming that I'm able to make slides in the three hours, two hours that I have. And uh it's uh the talk's called Think Parallel, and it is um a talk where I really just deep dive on how to implement a variety of different parallel algorithms and data structures, all of which sort of build on each other and sort of try to instill upon people the mindset that you and I take when trying to craft parallel code.

BryceAnd so one of the storylines that I'm um likely going to include in this talk is um uh okay, how do we implement a parallel scan? How do we implement a better parallel scan? And then what can we do with a parallel scan? And uh the first of those, what can we do with a parallel scan is how can we implement a parallel copy if with a parallel scan. So um I've I've given a lot of talks where I've shown the sort of two-pass upsweep-downsweep um implementation of parallel scan.

BryceBut I wanted to uh implement um the more clever single pass decoupled look back technique that's used in um in Cub and Thrust. And uh the the the essentially the the secret behind that decoupled look back is that when you do this upsweep-downsweep pass, basically, uh the two-pass approach, you do something in parallel where you split up the problem into chunks, and for every chunk you do a local scan, and then every chunk can communicates some aggregate, uh, the the aggregate sum from its chunk into some array somewhere.

BryceAnd then you scan that array. Um, and then that scanned array of aggregates, you you use that to um update all of the original chunks. But the scan of that array of aggregates happens in serial. You do that by one thread in the sort of traditional approach. And what decoupled look back does is it replicates and pair and uh parallelizes the scan of that aggregates array. So it says, okay, we're going to do some redundant work in the interest of avoiding the global barrier between this upsweep pass and this downsweep pass.

BryceAnd so the way that you do that is that um if you're uh you know a chunk in this parallel scan, um, you will look at all of the previous chunks that are before you that are to the left of you in the sequence. You'll you'll look and see have they written their aggregate yet? And if they have, you add it into some local temporary that you're accumulating. Um, and if they they haven't, um you you wait for them to finish.

BryceUm and if you ever encounter that that one of the previous chunks has not only written its aggregate, but it's also summed all of the aggregates from all the chunks before us, then you can be like, great, I don't have to keep looking further into the past. Um and this this trick lets uh lets you uh uh avoid having everybody waiting on um just the the predecessor that's directly before them. Um uh and it allows you to uh uh to to decrease the contention um on uh predecessors when you're doing this scan.

BryceUm so it's a pretty clever technique, but um one thing I started thinking about um when I was looking at this is how does this algorithm relate to or what are the forward progress guarantees of this algorithm? And one of the first things that I realized is that um I don't think that with just the C parallel algorithms that we have today that we can actually write this code um because we don't have a way to request the type of uh uh uh forward progress guarantee that we need.

BryceHow familiar are you with forward progress guarantees?

ConorI watched Olivier, um Olivier's talk that I'm pretty sure is called forward progress demystified or something like that. And I've read the uh CPP reference stuff, but I am by no means an expert.

BryceSo concurrent forward progress is the strongest form of current uh forward progress, and concurrent forward progress means that the system will ensure that your thread or your work will make forward progress. So like if you're on Linux or um Windows and you spin up a std thread, um that std thread will uh uh will get scheduled and will run. And that'll happen regardless of how many other std threads there are.

BryceAnd if um uh if that thread blocks, um uh like that's okay. And essentially the way that operating systems will do this is that they will um at some point, you know, they'll preempt your thread. They'll be like, okay, like, you know, it's time for me to preempt you so that some other thread can run. And that means that uh you can't end up in a situation where um you've got, you know, your thread is using some parallel resource and all it's doing is waiting for some other thing to happen.

BryceAnd the thing that it's waiting to happen can't happen because the it doesn't have a parallel, it doesn't have a resource to run on, um, because the the resource that it would run on is being used by the thread that's blocking on it. So uh uh an example of well, I'll I'll I'll get back to the example after I explain parallel uh forward progress. So parallel forward progress is a little bit weaker. Parallel forward progress says um uh once your task or piece of work starts executing, the system guarantees that it will run to completion.

BryceBut if it hasn't started started executing, there's no guarantee that it will. So an example of something that would give you parallel forward progress would be a bounded thread pool. So you have a thread pool that has eight worker threads on it, and you can feed tasks into this thread pool. And those eight worker threads are OS threads, um, so they have concurrent progress uh guarantees themselves. And all of those eight threads in the thread pool are gonna do is they're gonna pull queues out of the task and run those tasks.

BryceAnd so once one of those worker threads pulls one of your tasks out of the queue and starts running it, it's guaranteed that that task is gonna run to completion. But let's say that you enqueued a hundred tasks to this thread pool, and 99 of those tasks were gonna wait on one of those tasks. Well, if the first eight tasks that get pulled out by those eight worker threads are tasks that wait on that one other task, then you're gonna have a deadlock because each one of your worker threads is gonna be running a task that is gonna be waiting for a thing, for another task to run, and there's not gonna be any any thread to run that task that everybody's waiting on.

BryceSo a concur uh a thread pool that would provide concurrent forward progress instead of parallel forward progress would either be an unbounded thread pool, so a thread pool that will add additional threads if needed, um, you know, if things are taking too long or if there's too many tasks in the in the queue. Um, or it would be a thread pool and a system that would ensure that would that would require you to block in a certain way that would defer um uh uh control back to the thread uh uh pool.

BryceSo if your thread pool, if instead of waiting by you know um uh using a condition variable or spinning on an atomic or a mutex, if your tasks instead waited by calling some uh some function on your thread pool that was called wait, and that function could wait, but it would also, if the thing that it was waiting for had not been satisfied yet, it might go and execute another task. It might go and pull another task out of the queue and then go run that additional task and only come back to your task once uh it's uh uh run that other task.

BryceAnd then in that sort of system where all the blocking defers to the scheduler, um, you will eventually make forward progress because uh eventually you'll get through all 100 of those tasks until you get to that one task that um uh that will unblock everything else. And then once that one's run, then all the other ones that have been deferred um uh by this uh boost blocking mechanism is what it's called, would eventually get run.

BryceSo that's that's parallel and concurrent forward progress. There's also a weaker form of forward progress called weekly parallel forward progress, which essentially says, like, hey, you have no guarantees that execution will um uh will run to completion. Um so so weekly parallel, not particularly interesting for what I want to talk about today. And what I want to talk about today is in the case of our scan algorithm, um we sort of need a concurrent progress guarantee today.

BryceBecause um if if I'm doing a scan with n chunks, um the i-th chunk depends upon all of the chunks before it. And so if you if you were to use a system that has parallel forward progress and it was going to run, again, let's use that example of a worker thread pool with eight worker threads, um, and you enqueue up in chunks of your scan there. Well, if if it decides that it's gonna run the last eight chunks of the scan first, then you're gonna have a problem, because those last eight chunks are gonna depend upon all of the chunks before it.

BryceUm so you'd get a deadlock with that parallel forward progress guarantee thread pull system. However, if you ran the first eight scan chunks first, and if you guaranteed that you only would run a scan chunk if all of the scan chunks that were encued before it have been run first, then you'd be fine. So if your system has this sort of monotonically increasing guarantee where it says like, hey, if you enqueue n tasks, I will run those tasks, I will not start um running task I until all of the tasks before I have either started running or have completed running.

BryceSo if you have a system that makes that guarantee, which is weaker than concurrent forward progress, um then you can implement something like scan. And that sort of uh monotonically increasing uh you know forward progress thing, um it's actually common to a lot of different problems. Um uh you know, you need that guarantee for something like a scan, you need that guarantee for something like the what we've called the lost reduction or the fold left type reduction here, where it's a reduction that uh guarantees that things will be reduced um sort of left to right.

BryceUm and there's a few other um uh important algorithms that that sort of could rely upon that property. And on CUDA, um we don't explicitly guarantee this. Um uh it's very much like uh uh uh undefined behavior, but it has happened to be the case since the start of CUDA that CUDA thread blocks um are executed in monotonically increasing order. That if you're executing CUDA thread block I, you know that all thread blocks before I are either currently running or have run to completion.

BryceSo it's a it's a very this is a very interesting property, and I've been thinking about is this property something that should be another forward progress guarantee category in C? But I don't think that that's necessarily how it would work because this isn't a property about the execution of one thread in isolation. It's a property about I've enqueued in chunks of threads or in threads or in chunks of work. Um, and I want some guarantee about the order in which they are all executed.

BryceUm but I do think it's an important guarantee for us to some in some way, shape, or form codify. Uh because if we can't codify it in some way, shape, or form, then the only way to spell these algorithms in standard C would be to require concurrent forward progress, um, which could be restrictive because some platforms can't guarantee concurrent forward progress while they can guarantee this monotonically increasing thing.

ConorYeah, I recall we've had a version of this conversation because I think we talked about this at one point, maybe even on the pod when we did the loss reduction series. And I think the there's even a pull request open right now on the thrust inside of CCCL saying having like a little chart that points out that we're missing an associative only reduction. And then I think we were talking about that there's a way to implement this kind of currently if you just call the inclusive scan and then take the last element.

ConorBut I can't I can't remember if this was on pod or off pod, but you said that the way that the scan actually works is kind of relies on this implicit, not explicitly stated behavior.

BryceUh same same thing is true of reduction. The reduction today will guarantee ordering in in thrust and cub. Because of the or sorry, rather, let me let me rephrase that. When you're using a thrust reduction with the CUDA backend, or when you're using a COB reduction, it's guaranteed that it's going to be left to right, that it's going to be that it that it won't commute, it won't change the order of arguments. Uh, because all it does is it enqueues a CUDA kernel that does the reduction.

BryceAnd we, as I just said, since the beginning of CUDA, there has been, it has been the case that CUDA thread blocks execute in monotonically increasing order. And so the, you know, if you think about it, like the way the reduction works, it it's it's guaranteed that this will happen. Like each each thread block um will break up the input into uh uh a series, uh into a series of chunks, and each thread will handle that chunk.

BryceAnd then there's a uh uh uh a warp-wide primitive that they'll use to do the reduction across the chunk, and that guarantees the the left-to-right ordering too. And then the block level primitive to do that, I believe also guarantees the ordering as well. Um and then because all the blocks happen in monotonically increasing order, the the sort of the grid-wide reduction should also give you that guarantee. I'm like, now that I say it out loud, I'm I'm only 90% sure that that's the case, um, or that that will always be the case, because I don't know how the warp level reduction primitive works, but I'm pretty certain that it'll do things left to right.

BryceUm I think we've I think we rely upon that in in some of our examples and some of the code that that you and I have written. Um it'd be interesting to actually go and see whether that's that's true, but I'm fairly certain that it's true today.

ConorSo how does this all tie back, because you started saying at the beginning of this episode that you've got this new talk coming up, think parallel, and you're gonna start from you know showing how to implement a scan using a copy if and how to build things out of scans, etc. Yeah. How does this all tie into like what's the ultimate goal of the talk? Is is uh are you gonna be and also to I I said uh Olivier, who's a former NVIDIA employee, now works at Apple last time I checked.

ConorUm he he gave a talk at CPP North 2022, and that talk was called uh forward progress in C. So if you were uh intrigued by Bryce's explanation of forward progress or confused, and either way you want to learn more, go check that talk out. So is that stuff gonna be covered in your talk? Or like what's the I think I'll have to I think I'll have to cover it a little bit.

BryceUm but um uh I mean I I I think that that I'm most likely to cover it by just using a stdd C-O-N uh execution policy, which we don't have today. We don't actually have an execution policy that guarantees you concurrent um uh forward progress. We just have stdd par, which gives guarantees you parallel. We have stdd par and seek which guarantees you weekly parallel, um, and then we have stdd.unseq, which doesn't give you parallelism at all. But so so like we could theoretically we could add a uh a stddcon that would guarantee you concurrent forward uh uh uh progress.

BryceUm and then I could use that for my examples, and that would be like sufficient, but again, it it would be too strong of a requirement because there's certain platforms that um uh uh can't uh uh promise concurrent uh execution, but can't implement these algorithms. So I'll probably just do that because I don't want my talk to turn into like a massive tangent on uh concurrent progress guarantees and uh this monotonically increasing execution property.

ConorSounds like a very, very cool talk. Uh where are you hoping to debut this talk?

BryceAt ACCU um and I think uh C now.

ConorIsn't the ACCU like right around the corner and already submissions have been Oh, so you've already proposed this talk and it's been accepted? Yes. Gotcha. I was I thought that this was the uh you know, you just had this, you know, talk idea in the last week and you were starting to pontificate about it. This has been in the pipeline for for months now.

BryceYes, I did.

ConorYes, it's been in the pipeline for a while. Interesting. So ACCU, that means that folks, when is when is ACCU? It's in March, right? Yeah. ACCU. Let's do a little let's do a little not accueather, ACCU C. We will do a little plug for if I don't need to click 17 links in order to conferences. There we go. And now I click another one. 17th of April, not in March then. 17th to 20th of April in Bristol.

ConorTickets are available. Bryce will be there. Uh uh. Giving his talk. He uh we can I guess we have to figure out our our sticker situation because we made promises. Oh yeah, we did make promises. And we will have those stickers. My first conference isn't probably gonna be until June. And you're thinking about going to C now.

BryceYeah.

ConorI am C now, folks, is April 29th to May 3rd. April, that is earlier than typically.

BryceOh, it's April 29th? Oh, that is earlier. I don't uh I didn't realize it was that much earlier. That may be I don't know. It's gonna be a question of whether uh whether Ramona's gonna come with me. Um, because I'm gonna be at ACCU. Like I I may not see her for a couple weeks before then because I'm I'm going to uh ACCU and my mom's actually coming with me. Um and so uh it is possible if she's gonna come, I'll probably go. Um but uh I suppose I suppose this is not of particul the logistics of this are not of particular interest to our podcast uh audience.

ConorOh, that's alright. You you know it's like I said, I I no longer have my finger on the pulse of what the listener finds interesting because they love that credit card ever so C the ISO site no longer lists the conferences, um, but there was I did see in the last couple months here. How do I tools? We need to put tools anytime. No, we need past month? Was it news from upcoming conferences? Yeah, so let's uh this was posted 16 days ago. So seeing as we've plugged ACCU, we've plugged C now.

ConorLet's plug them all. C online is February 28th. Oh no, those are workshops, sorry. Thursday, 29th of February. Woo! Leap leap year, folks. To Saturday, 2nd of March. Uh we talked about ACCU, we talked about C now. Using std CPP. That's in Spain, I think. Yeah, Madrid, Spain. Uh is the 24th to the 26th of April, so right before C now. Uh and I got these in the wrong order. C on C, that's in Folkestone, UK.

ConorThat is 3rd to the 5th of July. C North is the 21st to the 24th of July. Yep. Lots of C conferences. There's also some Rust conferences. I know that there is a Rust fest in Zurich, Switzerland, in June. And then I you said you were thinking about speaking at Rust.com. Yeah. But that's not until later in the year.

BryceAnyways, lots of conferences. Yeah. I should we should probably wrap up because I gotta shower and get into the office.

ConorYep, and I also need to go and watch the quarterly meeting. This has been our lunchtime, technically our breakfast. Yep. And I think the way they let it w let us watch it too, one of the platforms, you can pause it and then put it at 2x speed, just like YouTube, which I love, folks. Which I love because it means I can even I can sp, you know, be even more productive today. Links in the show notes for all this stuff. And uh yeah, if it's at ACCU, which is in April, that means you should be able to watch this talk on the YouTubes.

ConorProbably within, you know, a month of that, two months ago or so. So we will update to retrospectively a link in this show notes when that becomes available. So 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.

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