[SOUND]. So, here in lecture 9.3, we're actually going to build a very simple placer. So what you know is that, to first order, what a placer does is arrange the gates on the surface of the chip. And try to optimize an estimate of the wirelength, and one of the estimators we now know how to do is the half-perimeter wirelength, or the bounding box wirelength. How do actually arrange the gates to make this number small? And an interesting idea is that we use randomness. We randomly place the gates We randomly pick a couple of the gates. We randomly exchange the gates. And we see if things got better, right? And then we just continue that process and go forward. It sound really simple minded. It actually works. And it is the basis for some real interesting commercial sorts of placement engines. So we're going to start by building a simple Randomized iterative improvement placer. So let's go see how that works. So the easiest way to show how a placer is put together is to build one. And so we're just going to build the world's simplest placer, because it illustrates a lot of the really core ideas. And after we go from this very simple foundation We'll add some sophistication. We'll add some, some more interesting and useful ideas. So to start, how are we going to start our placer? Well, there are really two big ideas and this is an iterative improvement placer and so there's a, two important ideas. The first is you start with a random placement. You just randomly assign each gate to a grid location. Only one gate per grid please. And if you're thinking to yourself, wow, that has got to be just a terrible, terrible placement, because if I take all of the gates and I just throw them at the surface of the chip and they land where they may. And I take a step back and use my Wirelength estimation techniques as I can estimate the half perimeter wirelength for all of those nets and I can add that number up and I can get a measure of the quality of this placement. This is probably a terrible placement and the answer is, yes, it is. But it's a real placement, and it is a complete placement. And that is essential because what we're actually going to do Is iteratively improve it. So the idea is as follows, I don't know how to just get, in one step, a good placement. But I know how to get any placement. It's a random placement. It's a bad placement. And it's not that hard to improve a placement a little bit. And the idea is that you pick a random pair of gates in the grid, And you exchange their locations, that's really the key step. You exchange their locations, and then you evaluate whether things got better. So, what do you compute? You compute the change in the wire length, you compute the new total half perimeter wire length, subtract the old half perimeter wire length delta L. And delta L is an indication as to whether the exchange of those 2 gates, the swap of those 2 gates. Made the placement better, or made the placement work. If delta L is less than 0, the new total wire length got smaller. That's good. That's an improvement. You just made the placement better. Keep it. If delta L is bigger than zero, the new total wire length is bigger. That's bad. You just made the placement worse. Undo it. You just keep doing this for many many random swaps. Literally millions and millions and millions, maybe more, random swaps. How long do you do this? Well, you can do this until the Quality of the placement stops improving until L stops getting smaller, or if you have a CPU time limit, you know, you can do this for an hour or you can do this for a day or you can do this for a weekend or you can do this for a week. You can do this as long as you like. But at some point, L is going to stop improving, the placement is done and you look and you see how good it is. That sounds tremendously simple, and it is, but it actually works. So, here's a high level Pseudo-code for an, a random iterative improvement placement. And it's just got a couple of parts, alright? So, the first part, up at the top, says, random initial placement for each gate G in the netlist place Gi in a random location in the grid, alright? So that's just this, this initial placement. You gotta get the random initial placement before you can improve it. And then the next thing you have to do, is you have to calculate the initial wire length. So L equals zero for each net N. And the net list L equals L plus the HPWL, the half perimeter wire length estimator for that net. You just gotta add up all the lengths of the nets. And then there is an improvement loop. Right, and the improvement loop just says, while the overall wire length L is improving, pick a random gate GI, and random gate GJ, swap the gates, evaluate the change in the wire length delta L. And then, there's just the two key parts here. If delta L is less than 0, oh, I have just improved the quality of my placement, because I swapped two gates and the wire length got better, please keep that. And so what you see here is it says if delta L is less than 0, L equals L plus delta L. I update the wire length to res, to res, to remember the fact that I, I improve things. Else if delta L is greater than 0, I just made a worse placement, right? And in that case, what you do is you undo the swap. And you just keep doing this until the wire length is falling. That sounds incredibly simple, but you know that works. SO this is an Iterative Improvement Placer where we in a very long sequence of very small steps, iteratively improve the placement. And how do we do that iteration? Random. Random gate swaps. Now, one thing that I have to mention is that it is imperative that you try to calculate the delta L efficiently. And what that means is that you have to calculate it incrementally. And what that means is if you are taking two gates and exchanging them, it is extremely inefficient and extremely stupid to go measure again the half-perimeter wire length for all 10 million wires in your layout. Look, you have two gates, and you exchange them. They're probably connected to five other wires, ten other wires; y'know, depends on what they are, 20 other wires, whatever. Trust me; they're not connected to 10 million other wires. Do not go back and reevaluate the half-perimeter wire length for all the nets in the layout. Just evaluate the change on the nets that could themselves change. That is said to be an incremental evaluation. And so on the left I've got a little picture. Again, my four by my five by six grid, x goes from 0 to 4, y goes from 0 to 5. There's a gate in (1,4) There's a gate in 2,1. There's a gate in 3,3. And there is a gate in 4,5. The top two gates, or the top two rows, are black. The bottom two gates are red. There's a net called Net I that connects the top three gates, two blacks and a red. There's a blue net. There's a net that's kind of purple called Net K that connects the topmost gate and the bottommost gate. and then there is a Net J, that's orange, that connects the bottommost gates. And the gate at three three is called one, and the gate at two one is called two. And what I want to do is Exchange them. I'm going to swap Gates 1 and 2. And so, I'm going to swap the two red gates. And when I swap them, now Gate 2 is on the top and Gate 1 is on the bottom. So, there are still gates in 2 1 in the grid and 3 3 in the grid, but they're different gates. And what we see is now Net i is now longer. The blue net, the net that takes the top two gates and now connects to the bottommost gate. Net j, which connected the two red gates, has not changed, because it was just connecting the gates that were swapped, and so there's still gates in the same place. Its half-perimeter wire length isn't changed. Net k appears to be much shorter, because it used to connect the topmost gate and the bottommost gate. And we swap the bottom-most gate to be somewhere in the middle of the layout. Did the overall wire length go up as a result of this, or did it go down as a result of this? I don't know, right. I, I, you know, I don't, I don't know. I actually have to go calculate this. Right, and I calculate this incrementally, and so incrementally means that Delta l is the sum of the half perimeter wire lengths for nets I, J and K after the swap. I add those things together and then I subtract from that the sum of the half perimeter wire lengths of I, J and K before the swap. And so you just have to arrange your data structures, and you know, your, your internal organization of your code so that you can do this easily. So you have 10,000,000 gates that you're trying to work with, a 1,000,000 gates you're trying to work with, a 100,000 gates that you're trying to work with you take 2 of those gates and you swap their locations. Do not go reevaluate the half perimeter wire length estimator for another million or ten million nets, just evaluate it for the ones that could have changed their length. Which ones are those? Those are the ones connected to the things that you've moved. It sounds simple but it's a really important concept. So, how does that work? It works okay... And if I sound less than enthusiastic, it's because okay is the best thing I can say. This is not a good placement. And I'm going to show you techniques that give you dramatically better placements. But this is the right Starting point. This is sort of the historical origins of placement. You want to talk about how people were doing placement in the 1970's? This is how. So, this is a small benchmark. It's about 2500 gates and 5000 pins. It's being placed in a 50 by 50 grid. The graph shows progress. So the horizontal axis goes from zero to ten e6, which means ten million swaps. And it's labeled zero, two million, four million, six million, and eight million. The vertical axis is the sum of the half perimeter wire lengths. Right? So that's actually the thing we're optimizing. And there's a, basically a blue curve that's has a nice sort of exponential kind of fall-off. It starts up around oh, call it 42,000, and it falls off to something that looks to be maybe 26,000 or 27,000 in the total wire length. So you know, that's a pretty significant improvement. And you can just see that it sort of, you know, it falls really fast at the start because you started with a bad random placement. And everything you do is useful. And then, you know, once you start to go out there, honestly, most of the swaps you try are unsuccessful because they make the placement worse. So it takes longer and longer to find something that actually improves things, and the rate at which the improvement happens is falling off pretty dramatically. So this particular swap particular design actually ran you know, something like you know, about eight million swaps to actually get this result, and this is okay. This is not great, trust me, this is not great, but this is okay. So what can I say about random iterative improvement placement? Well the first is that it's easy to understand and it's easy to implement. and you know, that code that I actually showed. that example is actually a place where I wrote, gosh, 25 years ago. and that one of my enterprising TA's tweaked a little bit to to get this graph. So, big idea, you start with a random placement, you randomly improve it. You can optimize what we care about, which is the total estimated wire-length. The sum over all the nets of the half-perimeter wire length. Please remember to do this incrementally, don't be stupid. the wire length will improve, it will sometimes improve a lot. But the still, the overall result is just not very good. Compared to what we know how to do today, not very good. We can do better. We can do really a lot better. So let's go talk about adding some Interesting sophistication to this, to get a much better answer for a placement[SOUND].
