Name the algorithm that you can solve this sequentially, not in parallel, that exists in the standard algorithm. And I actually don't think this exists, this algorithm exists as a thrust algorithm. I could be wrong about that. Welcome to ADSP the podcast, episode 185, recorded on June 5th, 6th, and 7th. My name is Connor, and today with my co-host Bryce, we do phone tag episode number two. And in the episode, we chat about what we've been up to and an algorithm to solve how to find the top K elements in a sequence.
BryceI I don't even know. It's probably been like four or five, maybe even six weeks. Um I know you're traveling right now. I have no idea where you are, but I know you've been very busy, so I just figured I would uh give you a call and uh leave you a message. So uh I'm pretty busy too because uh we are moving apartments in about two weeks. It's a very big move. Moving to a completely different area, which is exactly three blocks north of where we currently live, but on the other side of 2nd Avenue. So that's a that's a that's a big move for me. I can actually see the new apartment building from our current apartment building. But uh we're getting a bigger place on a higher floor, and uh some some big and sad news, which is that the famed Bryce Coffee Table is not going to be uh coming to the new apartment. Uh it is the one piece of furniture that uh that we are saying goodbye to. It is actually my oldest piece of furniture. When I started working at NVIDIA, I bought myself that coffee table as the first nice piece of furniture that I would own. So uh if anybody, if any listeners are interested in acquiring Bryce's coffee table, you can get it for free. If you can figure out how to get it from here in New York to wherever you are, you can have my coffee table. Anyways, um I've been working on some cool and interesting stuff recently, but one thing that's come across my desk um that I've been meaning to ask you about is uh selection algorithms or uh like finding the top K of some you know set of data. Like I don't want to sort the entire set of data, I just want like the top 10 things or the top you know five things. Um and this is a pretty useful algorithm. It gets used in a bunch of places, apparently it gets used a lot in uh machine learning. Um obviously you can imagine if you're if like you're making a website and you want to um uh you know show people the the top X results that match some search criteria, you'd probably use some algorithm similar to this. Um and maybe maybe there's like a related algorithm of finding not just the top 10, but like the what if I wanted to find like the 11th through the 20th? Um but I I I was sort of thinking about this algorithm because I was thinking about uh uh whether there's any sort of scan-based approach to implementing this. Um I mean, obviously you have to do some sort of sorting here, uh, but uh there's sort of a different trade-off than the trade-off that you have with typical sorting algorithms because, especially in the case where the number of things that you're looking to pick is much smaller than the entire data set, some sorting algorithms like botonic sort that um may not be efficient as you scale up um uh can actually be a win for this sort of uh this sort of problem. So um I was just wondering uh if you were familiar with uh this problem um and if you had any thoughts about it. Hope to hear from you soon.
ConorHey Bryce, good to hear from you. I apologize for not being able to do this recording in person. I have indeed been incredibly busy over the last two to three weeks, and you are correct. It has been I think five or six weeks since we've talked, because the last time we chatted was when we were interviewing Doug Greger, which our listeners know was the last five episodes. Fantastic episodes. I hope all the listeners enjoyed. And currently I am in Pacific Grove, which is right next to Monterey, which is probably more familiar to the listeners. And if you aren't familiar with Monterey, it's at the top of Highway One on the Pacific coast in California. It's a couple hours away from San Jose, or I guess actually an hour and a half. And I'm here at the NVIDIA research off site. Technically, it's an on-site for me because I work remotely from Toronto, Canada. And it's been absolutely awesome so far. It's the first time, to be honest, I've been able to meet my coworkers in NVIDIA research since I joined just under two years ago. And getting to meet your coworkers is quite nice in the post-COVID pandemic days. And yeah, so that's what I'm doing here. We're staying at the Asilomar Conference Center right next to the Pebble Beach, the famous Pebble Beach golf course. And it's absolutely gorgeous. A little bit cold to be honest. But, anyways, that's what I'm doing right now. Last week I was at the KraftConf 2024 conference in Budapest. Not for the full week, just for a couple days. And that was awesome as well. A couple really good talks I saw. Got to meet, probably the highlight was getting to meet folks that I hadn't met before. Uh got to meet Richard Feldman, who we've had on the podcast before, link in the show notes. Also got to meet Kevin Henney for the first time. He's probably one of my favorite speakers of all time. I will link in the show notes, probably my favorite talk of his, which is declarative thinking, declarative practice. And who else did I meet? Jessica Kerr was there who keynote keynoted at CPP North, C North 2023, uh where we we will be both at the 2024 edition of that honestly in like just a month. And there was a couple other folks, oh yeah, Dave Thomas, who used to work at KX, which is the company that uh sells the uh Q and KDB plus executable. And he's given a really good talk in the past at a Yao conference on vector thinking, which I will also link in the show notes. And I didn't actually realize this, but he's the individual that organizes the GoTo conferences and the Yao conferences. So, anyways, got to meet a bunch of people and now I'm at the NVIDIA research offsite. So, yeah, just incredibly busy. I've also been preparing because I've got a poster that I'll be presenting on this evening. Anyways, that's what I've been up to. And to answer your question, have I thought about the top K problem? I am shocked. You actually told me about this probably like a month and a half ago, right before we interviewed Doug. And I wish we were recording this in person because this like this is an algorithm that we have talked about. There might even be an episode of ADSP that is named the name of the algorithm that is used for solving this. I have talked about it in my better algorithm intuition talk, which is the follow-up to the original algorithm intuition talk. Kate Gregory has talked about uh this. There's tons of people that have talked about this algorithm, and it's a standard library algorithm. Now you're talking about it from a parallel, you know, is this implementable in terms of a scam perspective? But we gotta out of the gate, out of the gate, folks, we gotta we gotta talk about how you can solve this in a with a sequential algorithm that exists. It exists in the algorithm standard library. So I'm gonna throw this back over to you, Bryce. Name the algorithm that you can solve this sequentially, not in parallel, that exists in the standard algorithm. And I actually don't think this exists, this algorithm exists as a thrust algorithm. I could be wrong about that, but I don't think it actually so it exists in the uh C algorithm header, but I don't think it exist exists as a thrust parallel algorithm. Anyways, excited to hear back from you. It'll be nice to record, hopefully in person. I'm also traveling next week en route to uh NDC Oslo. So we're gonna we're gonna have to find some time to record because then I'm going on vacation for a couple weeks, so and I need to edit these before I go on vacation. Anyways, hope to talk in person soon. Looking forward to hearing back from you.
BryceOkay, yes, Connor. I I know that you can do these with either nth element or partial sort. Um like what the question is, is how do you efficiently implement uh nth element or partial sort um in parallel? And you are correct that uh thrust does not have any um of these algorithms. There's no uh nth element, uh partial sort, uh, etc. in thrust. It's been like a long-standing uh uh feature request. Um uh what people today do when they want to do this in parallel with Thrust is uh like a lot of people just sort the entire sequence. So I was actually talking to one of our coworkers, Elias, uh, about this the other day, who's looked into um these algorithms more than me. Um and his belief is that the best way to implement these in parallel um is with partitioning. Um and uh he feels that this is a good approach in particular because partitioning um uh it's applicable to like a lot of different problems. So if we add the partitioning primitives that we need um to solve, uh selection and top hand partial sorting um uh to thrust and cob, then there will be a bunch of other things we can do with them. So the basic idea with partitioning approach is that you do like either a radix select or sample select to put everything into n buckets, and you're gonna do multiple rounds of putting things into buckets. Um and then so you know like you want the you know tenth element, or you want like the the the tenth to the twentieth elements, or you want like the zero to the like the top 10 elements, the zero to the tenth element. Um and uh uh after you have the things into buckets, you can figure out based on what things you want, which of these buckets you can get rid of. Um now in in Thrust and Cup today, we do have a uh a partitioning primitive, but it's a um uh a uh two-way partitioning, a binary partitioning. So you have a partition function and you are either in the group or out of the group. So it splits the the input into two different groups. But what we need is we need a multi-way partitioning primitive that instead of a function that takes you know an element and returns a bool of whether or not it passes the predicate, you need a function that takes an item and returns an index into you know which bucket does this belong into, and then the partitioning, the multi-way partitioning will uh split the input up into n buckets. Um and then uh uh you know you do this process iteratively. Uh you you continue doing selection down. So in the case of like radix selection, you're going through the actual bits of the number. Now, the one of the challenges here, um we use Radix selection for uh parallel sort of things that that are radix selectable. So things like ints, you know, things that like we can go through and like like um uh look at each one of their bits um to sort them. Um but uh for radix sort, it's a least significant bit radix sort. So we start from the the low bit um and uh then we do some uh uh some like black magic. And and one of the reasons why this is significant is that when you start with the low bit, imagine like sorting ints and you're starting with the low bit. Um uh you like how much bias do you have in your data for this selection mechanism? How likely is it that like everything is gonna end up in one bucket? Um well, if everything, if all your numbers are even, then you might end up in one bucket. Um uh, but like if you know you've got you've got like a variety of numbers like you know, of different orders of magnitude, you're you're you're fine. Um and uh then you move on to the next uh highest uh bit, the next highest, the next highest, etc. Um now the the one of the big advantages of doing this least significant bit radix sorting um uh is that if you have uh a set of numbers that you know like maybe you've got like a million ints from like zero to ten thousand, um, or even if you've got like a million ints from like zero to uh like you know a billion or or a million. Um in either case, there, um if even with that huge range of numbers for what your possible values are, um you end up with a lot of unused bits on on the significant side of things. And so if you start your selection on the significant side, um uh then you'd end up with a lot of bias, right? That if if like if you've got only small numbers and you're starting on the left side, then everything's gonna end up in the same bucket because those first few bits are gonna be zero for everybody. Um so for rate exort, we're able to get around this because we start from the other side. But for reasons that I don't fully understand yet, for um uh like partial sort, selection and top K, we can't do that um because uh basically for like RAID exort, we we uh we end up going through all the bits anyways. Um and so like it doesn't matter which direction we start from, but when you're doing some selection problem, you you have to start from the left. Um again for reasons I don't fully understand. But the implication of this is that um you can end up uh with like we're like bias in your your uh in your selection uh function, where you can end up with like, you know, you you you wanted to sort things into a hundred buckets, but you you ended up actually putting everything into one or two buckets, um uh something like that. Um and so that's that's one of the challenges uh with this problem space, doing this in parallel. Um and then for things that are not radix selectable, you need to do some sort of sample select, which is sort of like the the the basis of like uh something like sample sorts. So the idea here is that you're gonna just pick some pivot elements arbitrarily um randomly from within the data set, and then you're gonna say, like, okay, we're like we're gonna we're gonna um select based on these, we're gonna partition into buckets based on these things. Um and uh you know figuring out how to get pick good like samples is also I think a little bit uh tricky. Um yeah, so uh uh you know the other thing that I've been thinking about a bit too is if you like if you just want to find so this the case of selection is like an interesting one where it's like I just want like the you know the 50th or the 500th element or just like the medium and median element, and it just feels to me like you should be able to do something better than having to do any form of like partial sorting or partial partitioning of the sequence. It it feels to me, and I know I'm almost certain it's not the case, but it feels to me like it should be something that should you should be able to do by reduction. You know, you can do a max reduction to find the maximum. Um, if you wanted to find the second from maximum, you could also do a reduction to to find that. You would have to, you know, store the whatever the maximum is and then also store the second from the maximum. And if you want to find like the you know, the tenth max element, if you're willing to store, you know, uh uh a buffer of 10 elements and in and copy that around with your like a state that's copied with your reduction element, your reduction operator, um, uh and then you'd have to have some way of combining it, presumably, but it's not a not not, I think, an issue. Um uh then you could do that without having to like do a full sort. Um and uh you know, I think essentially what I'm getting at is that in the case where like your your K is small, um like you have like you want to do top K with a small K, or you want to do selection with like uh with uh where you want like a small like something near the front of the end, um you can do more efficient uh uh reduction or or maybe even scan-based um algorithms. Anyways, I'm just rambling now a little bit at this point. Um I uh I will send you this message and then I gotta go because uh it's just just like now hitting me that like I'm moving next week and now I gotta leave to go to Albany to pick up the girlfriend on Sunday instead of uh like Tuesday like I planned. So I basically got like three days left in this apartment and a lot of stuff to do. So well uh I will uh talk to you soon, buddy, once you uh stop all your traveling. It sounds like you're uh you're you're having a great time. Uh uh. I hope you've got some beautiful weather down there. And uh yeah, it's uh I'm really glad that you're getting to go to all these conferences. Uh I know how much you uh enjoying Thrive on that energy. Um so uh so yeah, next time we talk, I should be in the new apartment. Um, and hopefully it'll have uh better acoustics, uh a little bit less background noise. It's on the 37th floor as opposed to the 11th floor where we're at right now, so we're uh moving on up in the world, and that means it's uh a little bit quieter. Anyways, uh enjoy the rest of your travels, and I will talk to you soon.
ConorHey Bryce, just got your message, and yeah, good luck with all the moving. It sounds like you're gonna have an incredibly busy weekend, which also probably means we're not gonna be able to record episodes 186 through 188. So we will we will have to figure out what we're gonna do for the rest of the month. But that is a problem for future us. And I it is Thursday. I think we exchanged messages yesterday, or potentially, I think it was yesterday, while we were mid-NVIDIA research offsite. I am now back in Santa Clara, just uh like five minutes away from the NVIDIA headquarters where I'll be working for a half a day tomorrow before I fly back to Toronto. And yeah, the research offsite's over. It was a blast. Awesome to meet, you know, coworkers, folks, and other research teams that I don't really interact with much. Uh lots of awesome ideas. And yeah, looking forward to I'm not sure if there's going to be one next year, but I think they're definitely doing one once every two years. I think maybe the on-site one will be every two years, and there's a virtual one, but I'm not actually entirely sure. Anyways, also looking forward to hearing if the coffee table finds a home, because I'm not sure if any listeners have reached out as uh as you mentioned in your last message, or was it two messages ago? If someone is looking to acquire Bryce's coffee table, uh it is theirs for the taking. It is a rather large coffee table, though, so I'm not sure how if they're not in New York, how they're gonna get it. Anyways, back to the topic of the parallel nth element. So you didn't mention it in your first message, but you did answer my question. The name of the algorithm, probably most of the listeners were thinking about it, is nth element in C, which gets you the nth element if it were in a sorted sequence. Uh so you can think of this as kind of um if you need to find the median or a percentile, this is the exact uh algorithm that you need. And also one of the properties of the nth element is that it will partition all the values that are less than the element and greater than the element on the left and right sides for the default binary operation. I'm pretty sure you can customize the binary operation on nth element. And you also mentioned you could solve this with partial sort. Uh however, you said that your goal was to solve this in parallel, and as you mentioned, there is no thrust nth element. So the question is what to do. While you were explaining the different partitioning and radix sort solutions, I was thinking in my head, how large is k, or or more precisely, how small is k? Because if it's small enough, you could just do a reduction and then store all the values. And that is actually what you said at the end of your message. So I was while you were mentioning the partitioning and radix sorting, uh, I was thinking if k is small enough, just do a reduce, and then if k is large enough, just do a sort. So yeah, the question is if k is not small enough to do a reduction and not large enough to just sort the whole thing, what do you do? I don't actually know off the top of my head. So uh maybe we will discuss this in a follow-up episode. Because yeah, I don't have any great ideas off the top of my head. A partition takes a unary predicate and kind of does what nth element does, but it doesn't guarantee you that at the nth spot you have the value that would be there if the data was sorted. It just basically does a predicate sort. Everything that passes the predicate goes at the front, and everything that fails the predicate goes at the back, but you don't have any other guarantees other than that, so that doesn't really help you much. Yeah, I'll think about this because I think this is bringing us to about the 30 minute mark. And uh we'll revisit this problem in a future episode, so you're probably not gonna hear this because you don't listen to the episodes, but good luck moving. Hopefully we'll find some time to chat. If we don't, I'm not exactly sure what's gonna happen for episode 186, but the listeners, I promise there'll be something. I promise there'll be something. Anyways, good luck with the move uh to both you and Ramona. Um I'm happy you're moving to uh a higher floor and that it'll be quieter. And I'm looking forward to chatting uh once you've moved and I'm done traveling. And uh yeah, we'll talk to you then. 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.