Conor

We're gonna now call Bright's Dr.

Bryce

Doolittle here, cuz uh I like like like I legitimately would like to own a horse now and go riding on said horse.

Conor

Welcome to AD SP the podcast, episode 82, recorded on June 4th, 2022. My name is Connor, and today with my co-host Bryce, we respond to Reddit comments on episode 80, where we talked about GPUs and multidimensional iterators.

Bryce

So so my so so my uh my girlfriend's dog we we got uh spayed yesterday. Um prayers go out to the dog. Um and uh one of the dogs' rewards for being a trooper during during the Spain was that we got her a dog bed for my apartment, um, which I'm very excited about because the spot she likes in my apartment is right under my uh my desk, and that dog bed is just very comfortable for my feet, right? Like I'm very, very happy with this setup. Um, you know, having like like a warm dog there to keep my feet warm is like also a benefit. Yeah.

Conor

I didn't think that was where that was going, but uh where did you think that was going? I thought you were going to say that you were unhappy. Um, because uh this is gonna uh we could lose a couple listeners here, but I am not the biggest dog fan.

Bryce

I I I I do know this based upon some past conversations you and I have had.

Conor

And to redeem myself a little bit, I actually do love dogs. I just don't like untrained dogs, which happens to be the majority of dogs. And uh I if you're a dog owner and you're like, well, my dog's trained, if for instance, I'm in an elevator and you are also in that elevator with your dog, and you think that we're losing a couple listeners here, and you think that, oh, everyone loves dogs. I'll just let my job dog jump all over this person and start licking his pants and blah, blah, blah. Um, to me, that is an untrained dog, or maybe an untrained owner that thinks that like their dog is the world's greatest gift, etc., etc.

Bryce

I I love all dogs, and I am completely fine with your dogs jumping on me in elevators and other places. I'm also very good with dogs. Um, yeah, like like Olivier Gore's dogs love me. Those dogs love me because I give the best belly rubs. Like we go, we go, we go months without seeing each other, but then I see his dogs again, and they remember me because they remember how much I love them.

Conor

This is this is extremely true because one time the both of us went over to um Olivier's house for dinner, and though yeah, those dogs absolutely they were like, oh, uh our our kindred spirit has arrived. Um and like the dogs were just laying their lap in or their heads in your lap. Yeah. Yeah. So yeah, definitely Bryce is the dog person of the two of us.

Bryce

I'm I'm good, I'm great with cats too. Don't tell the girlfriend that she does not like cats. Um, but uh yeah, I'm I'm just I'm just an animal whisperer. I'm good, I'm good with horses too, apparently, because when we were in Utah we did horseback riding, which I've never done before, and I thought it was gonna be scary, but no, apparently I am a natural with horses too, and I now love horses.

Conor

We're gonna we're gonna now call Bryce Dr.

Bryce

Doolittle here because uh I like like like I legitimately would like to own a horse now and go riding on said horse.

Conor

I mean, I could see that for you. I could see you having like a ranch that you visit on weekends or like live on a house on the ranch and have people to look after the horses and then visiting that part of your property on the weekends.

Bryce

Yeah. Did you did you see these pictures of the dog mugging that I oh yeah, yeah, those were great.

Conor

Those were great. Um I thought that really added a lot a lot of color to um to the story.

Bryce

There were there were a few that were even better, which was my girlfriend like trying to shoe them out out of, but I could not um tweet those because she was in her pajamas and I determined that she would murder me if I if I tweeted those pictures.

Conor

Well, maybe on maybe if we ever start like a uh Patreon podcast model where we charge our listeners for the the juiciest content, which don't worry, listener, we're never gonna do that. It's you mean an OnlyFans.

Bryce

What you're describing is an OnlyFans.

Conor

I mean, that's not what all the other podcasts call it, but sure. I mean, it is kind of the same transactional model. Um yeah, where you're paying money for a certain type of content. Um but uh anyways, to to bring it back to where I thought your story was going, because that's where this all started. I'm not a big fan of dogs. So when you were talking about the dog being under your desk, my first thought was obviously Bryce does not want that dog there. Um and so that he's happy that he's getting this bed so that he can put the bed somewhere else so the dog will no longer want to go under the desk, you know, win-win. Um, and then when you said uh, and it's fantastic because it's very fluffy and it makes my feet comfortable, I was like, damn, I got that one wrong.

Bryce

Um look, regardless of whether or not you own a dog, I I highly recommend that everybody go get a dog bed to put your feet on when you're sitting at your work desk because it's amazing. And then once you've got the dog bed, you may as well get a dog too. So yeah, but if you thought that I was if I was unhappy with anything that my girlfriend's dog was doing, do you think that I would mention it here in a place that she could theoretically have access to?

Conor

I mean, you did say last episode that uh, or is it two episodes ago that she neither she nor your mother listens, so yes, yes.

Bryce

Um those are both true points. But I'm I'm I'm well I guess we're on Apple Podcasts, so my mother could get access. Yeah. She she doesn't my my mother does not have the attention span to put up with all of the the the tech nonsense and random weird tangents that we have to get far enough to to to hear any of the things that she may take offense at.

Conor

It's true, it's true. Even when even when there's like non-technical episodes, sometimes I'll send them to my family and and you know no one listens because they don't they just don't care. Yeah, they're like Connor, we hear your voice enough when you come back, when you come by like one week out of the year, yeah, that's way too much already.

Bryce

Um it's not actually entirely true about my mother. Throughout my cr my career, my mother has tried very hard to understand what is what it is exactly that I do. So she might she might have the stand, but I just I just don't I think that if she did, she would start at episode zero. I don't think she would start at the latest episodes. Or like even if she did, like like like she's in Italy right now, so I wouldn't need to worry about her listening to like like this particular episode. But I she might get through some of them. I do not think she would get through any episodes.

Conor

That's true. Maybe one day wrong, mom. Maybe wrong. Maybe one day we'll release like the most technically titled episode, and then we'll just talk about like the juiciest gossip, like family gossip, and uh hope that no one none of our families listen to it. Anyways, we need to get back to uh back to these. So you've been waiting for a week for us to talk about these Reddit comments. And uh I'm gonna read the first one.

Bryce

Hopefully, Connor edited this together in a way that did not like I did not.

Conor

I just cut it straight in half.

Bryce

I read some other Reddit comments where people were talking about what podcasts would replace CVP cast, and there were some people who suggested ours, and then there were some people like, yeah, but like half the time they just go off on tangents. That's true. Um, and and Bryce is too oh god, what was the word? Wasn't demour, it was another word. Nonchalant. Bryce is too nonchalant on the podcast. Nonchalant? Yes, which is a very, a very true uh assessment, I think.

Conor

But we're supposed to be, I don't know what the opposite of nonchalant. I know what nonchalant means, but like I don't think chalant is a word. Um, but like this is listen, listen, I'm all about constructive criticism, whoever made that comment, but this is our podcast.

Bryce

No, challant is uh is a word. But w w wiction well, no, no, no, I don't think it's a real word. Wiktionary defines it as not nonchalant, which is about the dumbest definition I've ever heard.

Conor

I mean, um I think that's the that's the beauty of uh our podcast. I mean, that's the thing, is I kind of thought that like it's a real shame that CPP cast disappeared because they're kind of in my mind, like this kind of like voice or like core where you know, a couple couple news articles.

Bryce

Yeah, the good C podcast, you know, the what the one that like the actual the actual quality podcast.

Conor

Yeah, yeah. They they they have like a format to whatever this is. Yeah, we are not that, and that's the thing. I was like, should we start doing like a couple news articles? And then my first thought was just like, no, like that's I don't want to do that.

Bryce

Uh we we if we did, we'd have to start another podcast for that purpose, not this one.

Conor

I like the fact that we got three minutes into our last episode 81, and we were like, all right, we're gonna talk about topic X. And then I was like, oh, wait a second, we gotta do some corrections. And now that I've said that, yeah, I was gonna stop you.

Bryce

I was like, what are you doing?

Conor

Like technically, I won't go read the other one, but that was not that was only one thing I had needed to mention. There's a list of them, but we'll do that on another episode. Bryce still has to go to the gym, and Bryce still has to go to the gym.

Bryce

Um so you eat food, but anyways, go on.

Conor

Listen, the nonchalant list is here to stay, even though I don't think that's the right word.

Bryce

Like, nonchalant is kind of like they didn't say you were nonchalant, they said I was nonchalant.

Conor

But doesn't nonchalant it's I I think it's adjacent to like apathetic.

Bryce

It's like you know, you're not you know, yeah.

Conor

Yeah, I don't you think you're nonchalant on this?

Bryce

I think you get overwhelmingly excited and blow people's eardrums out with your I am sufficiently seasoned that I have learned to not care about a number of things that are um that I deem not sufficiently important. Um whereas you maybe it's not seasons enough, it's um I'm uh uh traumatized enough. No, no, no, that's not the right word. I'm uh uh I've just I've seen enough things. I've seen enough things that like I have learned to be like, yeah, you know, I don't really care about that that particular thing. Whereas you, you're just like you're like uh a young schoolgirl, you're just always so excited by the world and the the the singing of the birds, the blossoming flowers, you gotta stop to smell every rose, and I'm just like, yeah, whatever, like let's get to the important things here. So, yes, I think it's a fair criticism.

Conor

I don't I don't know how to take being called a young schoolgirl, but um sure. I'll I'll take it as a compliment. Anyways, we're like 20 minutes into our 30-minute episode talking about comments on episode 80 in episode 82. Here's our first comment from James Barrow. Hopefully I'm pronouncing that correctly. The discussion around GPU iteration order feels a little like some things being lost in translation. If you have a 2D array in row major order and you want it to sum column-wise, each thread will be assigned to one element in a row and then iterate down columns. So if you consider the thread index to be your loop variable, it's not that it's not all that different. The mismatch here, I suspect, is actually in the definition of a thread. GPU threads are essentially one lane in a SIMD architecture. That's SIMD. Uh so I think the mix-up here is essentially definition in nature. In a CPU architecture, you'd give each thread a chunk of data to process, loading rightwards slash contiguously slash row wise with SIMD, and then summing downwards, which isn't different to a GPU. It's just a terminological, it's terminological at that point. In a language like OpenCL, running on a CPU, each thread maps to one SIMD lane, and it's very much like programming a GPU.

Bryce

He's absolutely right, but it does change how you write the code. In in the in the GPU model, um uh, you know, the SIMPD model, um we, you know, every every lane is an independent thread. And now with modern NVIDIA GPUs, truly an independent threat. Um and uh what while they do have this um sort of joined uh vector style execution for for um uh for operations where all the threads are at the same place and doing the same thing, um the way that you write the code is different from how you'd write the code on the CPU. Um and you know, the the the as Olivia used to describe it, you know, the the GPU compiler in the GPU compiler, we vectorize so late we vectorize in the hardware. Um and you know, the this different and the difference in the programming model does change how you write the code. Like under the hood, yeah, like the the code is you know the don't the way that uh you optimally process things may be the same, but the way that you write the code and the way that you logically move through the data and the code in each thread is a bit different.

Conor

Awesome. Well, James Barrow, you heard it here, you're 100% correct, but that doesn't mean uh programming to each of these a GPU and a CPU is the same. Moving on to comment number two. I think James was the best comment, but uh yeah, we will uh move on to comment number two. Really enjoyed this is from Kemonacci. Um don't know who that is, because it's Reddit. Uh really enjoyed this episode. A lot of the multidimensional reordering just sounded like flattening a matrix, quote unquote, to me. I believe APL calls it raising a matrix. I think raising is J terminology. APL calls it raveling, but um, same difference. Um also the way Bryce described how GPUs work sounded pretty intuitive. I think a great diagram or animated visual might help clearing that up within the array language community. This episode has me even more interested in seeing how MD span and multidimensional iterators will work on GPUs in the future. Comments.

Bryce

Or do you um not sure I understand the flattening part. I mean, it is certainly true that um uh I think almost all ways of performing operations on uh multidimensional structures do tend to lead to some flattening. Um uh you know, at at in some way, shape, or form. Um and and and by that I mean that sort of um we you know, you you you you move through in some sequence in time through through through the the data. Um and like that is that is like a linear thing um that you do. Um but I'm not sure that I understand the flatten where what he's talking about with the flattening in this context.

Conor

So flattening, I mean I think what he's probably referring to is when you describe the two different um ways you can index when dealing with the 2D matrix. The first one was just uh, or I can't remember if it was first or second, but one of them was just flattening, yeah. Yeah, it was just you know looping from zero to uh your dimensions time your dimensions, and then doing some modulus arithmetic. That in a sense is basically just looping from if you're if you're storing your array contiguously in memory, just like from the beginning to the end, and then behind the scenes uh you're doing some modulus arithmetic to get I and J. Yeah, exactly.

Bryce

Yeah. Um and like as we discussed in that episode, that approach is usually not the right way to do things. Um, because that the the the there's information loss when you go from a from you know a multidimensional position to a linear index into storage. Um there's information loss. You can reconstruct the multidimensional index from the linear location in storage, but that's often an expensive operation. And and that's maybe something that we didn't get into in the last time. Um and this is sort of something that's uh core to the md span model. An md span uh this is core to a lot of like matrix models, but md span illustrates it particularly well because an md span is a non-owning view into something. So when you construct an MD span, you give it a pointer to some data somewhere. Um in the MD span model, you know, that data is just a linear, you know, uh data. It's not inherently multidimensional. You give it some layout that maps from multidimensional indices, from some multidimensional space into single-dimensional indices into that storage. Um and that that storage array, it may be contiguous, it may not be contiguous. Um you know, in a lot of the simple cases you can think of it being contiguous, but if you're um or you you can think of the let me rephrase that the the backing storage is contiguous, but the the elements that the the order of the elements that you might access may not be contiguous, and it may not also be one-to-one. There may not be a um a mapping from from not every element in that contiguous block of storage may be mapped to from one of the multidimensional indices. Um but so you have this this operation in md span that's defined by the layout, which is the operation where you give it a multidimensional index and it gives you back a single-dimensional index, which is the location in storage. Um and so when you're when you're iterating, um, your iterator can choose to store one of those two things, either the multidimensional index, the thing that you would give to this layout function, or the um the storage index. And the problem is that the layout function um that that does this mapping um is usually pretty quick. There are some cases like sparse where it may be more expensive, but let's like just assume that it's pretty quick. Especially in dense cases, it's almost always pretty clean pretty quick. Um but the inverse operation of that, going from uh uh storage index to multi-dimensional index, that's almost always slow. And um at the very least, it's almost always slower than uh the other way around. And so it's almost always wrong to uh uh to store the storage index in discard the multidimensional index if you ever think that you're gonna need to reconstruct and and reuse that multidimensional index.

Conor

Yeah, this is um we're probably gonna end up having a a bunch of conversations around this topic based on where my career's going. Uh because I've been sp I've been thinking about this ever since starting to work at NVIDIA, which was now back in 2019. Is that we have a like and this is getting very NVIDIA specific, so you know, I apologize to the listener if if you care less about this topic, but there's a bunch of different, and some of it is C ⁇ , but like so C ⁇ , MD Span, and MD Array are coming. And in terms of the libraries that NVIDIA offers, there's like a a bunch of different, like we've got Kublas, we've got MatX, we've got you know, Python frontends to C backends that are sort of you know NumPy copies. And I've always wondered uh like what's actually like the most efficient backend to a kind of like array language, because you know, all the indexing that you're talking about, it only it doesn't actually matter all the time. Like for scalar operations is what they call in array languages, like when you are just adding a scalar to your matrix. Or elements. Exactly. Um it actually has it has no it makes no difference how you're if you're storing it linearly in memory or structurally in memory, because if it's stored linearly, you're just basically doing a transform, a C stood transform on every single element.

Bryce

And so I just there's another aspect here which is quite significant. Um when you're iterating through multidimensional data, you're usually either doing something element-wise or the second case. I'm just gonna call it the second case for right now. Let's focus on the element-wise case. That's the case of like you're adding a scalar to every element, or um, you know, you wanted to do something like a std reduce on every element. That's something we talked about the last time.

Conor

Now wait, pause. What do you mean by a std reduce? Because every assuming every element is like a an integer, how do you do what does a reduction on a single integer do?

Bryce

Um I'm like if I have a multidimensional, if I have a 2D matrix and I want to sum up, you know, all of the all all of the elements of the matrix.

Conor

Oh, so you mean you mean regardless of the rank of your matrix, if you want to perform a reduction across every single rank down into a single scale single scale.

Bryce

Or a count if you want to count all the non-zeros in your own. Okay, okay.

Conor

So basically any operation that the structure, the rank, or the shape doesn't impact if you're reducing down to a single element or you're doing an element-wise operation on every element. Okay, gotcha.

Bryce

And and and importantly, you know, um importantly, I think these operations, they almost only make sense if they're all independent of each other. Like, I can't you can imagine a std reduce, right? Being like that, that being a useful thing. Like I want to sum up all of the values in this matrix, or I want to count all the non-zeros in this matrix. How about adjacent difference?

Conor

Yeah, you basically basically you're saying you need a monoidal binary operation where you can do it in any order and adjust.

Bryce

Yeah, now the reason the reason that adjacent difference isn't like a particularly useful operation to apply is because like you're you're taking the difference between you know two adjacent elements, but what does adjacent here mean in this context?

Conor

Right.

Bryce

Now, and so so this first class of things you'd of iterations you want to do to a multidimensional um uh uh uh object is this element-wise class where you want to do something to every one of the elements, and that thing is you know kind of independent of other elements, and or but at the very least, it doesn't care about like the position of one element relative to another. Um the key thing here, the key insight is these are operations on elements. The other class of of things that you want to do to a matrix, I will pause it. You don't really want to do them, you're not don't really want to iterate through elements. If you're interested in iterating through indexes. Because you're if you're doing something where you um need to consider multiple elements that have some relation to each other, then you're gonna care about indexes, not about the particular elements. And so, and and so like like like the example of this, like you know, adjacent difference is basically for the 1D case, it's a simple like stencil operator. Um, but anybody who's who's done any amount of like numerical programming knows that if I'm if I'm writing some sort of you know stencil loop um uh that's doing some numeric computation, I want to be dealing with indexes because I want to be able to say, you know, something like I want to do, you know, uh ij plus um, or you know, I want to be able to do like the value at like ij plus the value at um you know i plus one j plus the value at i minus one j, you know, something like that. Um now the in the distinction here is in the septic second case of things, you care about iterating indexes. So I I will posit that that that the um the two different uh categories of iteration that you might want to do over a multidimensional uh structure is one um uh element-wise, and by that I mean iterating over all of the elements, um uh or two, something where you're iterating through an index space, not particular elements.

Conor

So the couple translations that I would give for the array language listener is that your sort of your element-wise operations we would separate into two different categories. So only the shape preserving ones, that basically like the reduction version in an array language. What you would do is uh we heard the word raise earlier, which is the J term, or RAVEL, which is the APL term, which when you ravel, say, uh a matrix that has two dimensions, uh, so a shape of length two, you know, a two by three matrix, when you ravel that, it actually, to my knowledge, doesn't change anything in memory. It just destroys the shape because everything's stored linearly in a raveled form, anyway. So actually a ravel, which you might think is an expensive operation, the way that they're stored, you basically just change the shape to the product of all your elements of your shape, your dimensions, and then you don't actually have to change anything in memory, and then you perform a reduction. And then I think when you say indexes, I typically think more of like subshapes, but it's the same ideas like where I'm you know performing something on a certain rank, um, that equates to just uh you know an IJ index.

Bryce

Um but so was there was there a follow-up point to like the the point I was getting at is that in a very concrete C space, I think there are two categories of useful iterators that you would have to a multidimensional structure. The first category of iterator is an iterator that um gives you values um and does not tell you what index the things live at. And there is no way to get the index out from it. But that doesn't matter because the way that you want to use this is to do something element-wise to each one of the elements of it. And then there is a second class of index, which is not an index over elements, but uh sorry, not not there's a second class of iterator, which is not um an iterator over elements, um, returning you the elements of the matrix, but it's an iterator that produces indexes that you would then use to index into the um matrix. And that there is there is a both programming model difference here and also a significant performance uh difference because if the if we only have to solve the um if we only have to build efficient index iterators, that's a much more tractable problem than building efficient element iterators from which we can recover the multidimensional index for a variety of reasons that have to do with how compiler vectorizers work that um I do not remember all the details of, and even if I could, would not get into in-depth uh on this podcast, because that would be that would be hairy, even for us.

Conor

Well, I have more questions, but we're gonna let Bryce go exercise and eat food.

Bryce

Oh, there were two more comments. There were two more comments.

Conor

Oh, there was only one more comment. We were at comment number two, and very quickly, the last comment was a response to the previous one by Kemonacci. Greg CPP was responding to a sentence in the last comment, which was I think a great diagram or animated visual might help clearing that up with the array language community. And Greg CPP responded to that. Yes, exclamation mark. I'm not a GPU programmer, but I would really appreciate a good reference for how GPU programming works at a conceptual level. Not how to program in CUDA or with any other tools, but how they work generally. For example, I believe that most GPUs have a CPU user space quote unquote driver, a CPU kernel space driver, and code on the GPU proper, but I have no idea what the responsibilities of each are. Uh for example, when you dynamically allocate GPU memory, where does the allocation algorithm run? Or when the vendors talk about GPU cores, what do that what does that really mean? Is that answerable in a couple minutes?

Bryce

Well, I'm gonna work backwards. Um so GPU cores um like often as a marketing term. Um there's uh you know, on NVIDIA GPUs, we have an actual execution unit called an SM. Um and I think of that as being the closest analogy to a core. Um on GPUs, we virtualize a whole lot of threads, and SMs can be heavily oversc subscribed with threads, and in fact that's how they like to operate, because you know, while the way that the GPU SMs are signed to work, while they are low waiting for data for one, you know uh uh group of threads, um uh they can go and execute for the next group of threads. Um and you know, this is very heavily pipelined. So you know, you you you want to do what's called latency hiding, um, where you never actually have to wait for something because there's always more work available. Um so you know, you maybe have one group of active threads and then you have, you know, 30 or 60. Um those may be slightly excessive numbers, um, you know, four or sixteen other groups of threads which um uh you've initiated loads on or stores on or some some operation that needs to wait um on um memory traffic. Um and uh you know, you those are sort of pipeline. And so as as one of those loads comes in, then that group of threads becomes available, and then you go and you execute the compute code until um it hits the next, you know, memory load. Um, and then by that time somebody else has become available to start computing. Um so they are sort of designed for this barrel threading, the these SM cores. Um uh I don't remember what the rest of that question was. It seemed like it was more, you know, the this plea for a desire to understand the basics of the GPU compute model, which is something that I too uh have a desire for, as I we talked about in the last time. I'm by no means a GPU expert. I will say, time permitting, it is likely that I will uh scrap my original plan for my array 2022 keynote, which was just to recycle my um uh a good chunk of my existing slide deck on C standard parallelism. Um, but I'm thinking about just scrapping that plan and instead just solely talking about MD span and talking in greater detail about uh the problems related to multidimensional iteration um in uh in C and in compilers. Um however that will require the the time that I have between now and the start of that keynote is quite limited and is made more limited by the fact that um I I have lots of other things going on. And uh I have a friend coming into town to visit. Well, I can say it's Han is coming to visit next week, and um yeah, we'll see whether I have time to do that.

Conor

Um I do also technically have a day job where I have to do things, so I mean you could make a strong argument that uh giving a talk about multi-dimensional iterators and empty span to the academic community of array language and uh multi-dimensional array libraries could be of immense value, especially if you're focusing on how it it impacts programming to a GPU um to NVIDIA. So, you know, could be a part could be a part of your J job.

Bryce

Yeah, yeah, yeah. But it requires more work than I may have time to do. So we'll see. We'll see. If you get a bunch of meeting cancellation uh notices from me um in the next 24 hours, it's because I've decided to execute on this and have decided that uh that uh we are postponing all meetings until post Q.

Conor

I assume you're talking to me and not the listener.

Bryce

No, I mean some of the listeners uh are on you know meetings that I would send the cancellation notices for.

Conor

Gotcha, gotcha.

Bryce

And if I send those meeting cancellation notices, I'm gonna put in the note, listen to ADSP for details.

Conor

I mean, this won't be out until after. Right.

Bryce

So people will have to wait a week or two to find out why they didn't.

Conor

Listen to episode 82, which will be released on June 17th or something like that. All right, we'll wrap it up here. Thanks for listening. We hope you enjoyed and have a great day.