[SOUND]. So, here in Lecture 9.2, we're going to start talking about the real technical part of ASIC placement. And to first order any placer for logic gates optimizes things. And what it optimizes is an estimate of the amount of wire it's going to take to connect all those gates. That estimate is usually called the Wirelength, right? And the reason we estimate it is because the actual physical act of connecting those wires, which is called routing those wires, is computationally pretty complicated. So, we actually have to build some appropriate mathematical estimators that our optimization algorithms can use. So, to start things off, talking about the technology of ASIC placers, we're going to start with some classical forms of wirelength estimation. So, let's go see how that works. The easiest way to talk about how a placer works is to build, so let's build a very simple basic placer to start. And so, we need to start with a simple model of the chip surface itself, and so the simplest thing is to just use a grid. So, think of this as like a chessboard. there is a set of slots, or cells that we can use. And the gates, which are the cells from our standard-cell libraries can go in the grid slots. And any gate can go in any slot. You're allowed to put exactly one gate in each one of those slots, and it's okay if the slots are empty. This is a very simple model of the gates because it assumes that the gates are all exactly the same size. And that is extremely unrealistic. But it dramatically simplifies things. And so, we're just going to go with that in order to get started on, on looking how we, how we deal with a real placer. So, a grid. Every slot can hold exactly one gate or exactly zero gates. It's not okay to put more than one gate in a slot. All of the gates are the same size. So, we know what the representation is. What are we trying to do? What does a placer do? A placer optimizes the ability of the router to connect all the nets. That's the first thing a placer does. But, the router, which is the tool that actually puts the wires down and finds paths to make all the wires, you know, possible. Routers are computationally expensive things. You can't run one inside the placer. I need a simplifying approximation. And so, what every real placer does, and this is no exaggeration, what every real placer does is it minimizes an appropriate mathematical model of the expected wirelength. And, to be more precise about that, for each wire in the design, there is an estimate, an approximation of the expected length of the routed wire. And we add all of those expected lengths together, those estimated lengths together for every single wire. So, we sum over all of the wires in the design, the estimated length of the wire, we add them up and we minimize that. That is what a placer does. A placer optimizes the estimated lengths of the wires and solves for locations for the gates that minimize that estimated wirelength. That's what a placer does. And, you know, to first order, you could actually categorize the very many different kinds of placers that there are by the mathematical model they choose to use for the wirelength. Now, we need a little terminology so that we can all talk about these things the way people who really do ASIC layout talk about them. So, the first common term is that the term for a wire in a layout is a net. So, we call them nets. And the whole set of gates and wires together is called the netlist. So, the thing that comes out of multi-level logic synthesis, and then followed with technology mapping is a netlist. The thing that goes into your placer is a netlist. And nets are actually categorized by how many things it connects, and we tend to call these points. So, I've got a nice simple little example on the left. I've got a grid that goes from 0 to 4, it's got five columns on the x direction and the y vertical direction, it goes from 0 to 5. It's got, you've got six rows and I've got a two-point net, so I've got a gate at x,y, 1,4, and I've got a gate at 3,1, and I've got a little blue wire connecting them. And so, it's really clear that this is a two-point net because there's two gates that it's connecting. and if everything in every netlist looked like this, we probably wouldn't be talking about this and we wouldn't be giving it special terminology. But the problem is they don't look like this. They also look like this. So, on the right-hand side, I'm showing you a four-point net. And so, again, the x grid goes from 0 to 4. The y grid goes from 0 to 5. There's a gate at 1,4, there's also two gates at 3,1 and 3,3, and another gate at 4,5. This is a four-point net because there is a wire connecting four separate points. This is, in some sense, why we don't just call it a wire. Because there's a lot of wires that are going to get created to actually route this thing and connect this thing all together. And in answer to the first maybe obvious question, which is how is it the case that there are actually things like wires that have more than two things that they connect? the obvious answer is, there's fanout. And I've even got it drawn with the gates sort of showing their directions as though. There's a little AND gate at each one of these grid cells, and the inputs appear to be coming from the left. And the output appears to be going to the right. And so, there's a gate in the 1,4 location in this grid that appears to be driving the inputs to three other gates. The ones at 3,1, 3,3, and 4,5. So, how is it possible to have things with more than two pins, two points? The answer is fanout. And in modern[UNKNOWN] there are lots of things that happen to connect to many things at the same time. So some, some elements of scan chains and the testability components of logic you know, there are things in the clocks that actually synchronize all the flip-flops. There's some very, very high fanout nets. In fact, there are often special kinds of routing technologies to connect those things. So, it's not just like you can have K.net where K is 4 or 5, you can have K be hundreds. So, about the wirelength estimation, there are many, many different kinds of estimators. And in fact different placers depend for their foundational methods to a large degree on the kind of wirelength estimator that you pick. So, why is it hard to estimate the length of wire that's going to be used to connect the nets? And the answer is that multi-point nets can be routed in many different paths. And in a dense layout, nets do not all get routed in their shortest path. I mean, the inside of an ASIC and the inside of a 20 million or 50 million gate ASIC, it's a very crowded place. Even with lots of physical layers for wiring, it's a very crowded place. Nets just don't get to go in at their minimum possible length. So, a concrete example here. I've got the same diagram that I had on the previous slide. a grid. x goes from 0 to 4 on the bottom. y goes from 0 to 5 on the top. There's a gate at 1,4. Gates at 3,1, 3,3, and 4,5. And there's a very straight little wire connecting them. You know, this is basically about the best I can do to wire this, this particular design. I can't really probably do better than this than this, this little example here. But in the middle, I'm showing something that you know, it's a kind of a different looking wire. Now does this have a little more wire? Yeah, this is, this is just a slightly longer than the, you know, than the previous wire is just because of the way things escape from the, from the topmost gate. But, you know, this is still okay. I, I would even say maybe this is good. You know, this is a particular, this is a good path. You know, it's just a little bit worse than the previous path. But now on the right-hand side, I'm showing an appallingly bad gate wirelength. it's again, the same example you know, x is you know, 0 to 4, and y is 0 to 5. but the, the wires are snarled all over the place. They seem to go way out of their way to connect things. And, and there's nothing else to say other than, you know, this is pretty bad. And the reason this is pretty bad is probably there's 20 million other wires that are trying to get routed, and this one just didn't get able to be routed short. And in real designs, that just happens. So, estimating what the length of the wire is, is actually quite challenging. We have to estimate something that is a reasonable model of what the wire might actually be. And so, what we tend to do is, is estimate a best wirelength. We tend to estimate the best and then we, we do some other techniques to sort of deal with the fact that they're not always going to come out this good. So, the most famous estimation for a wire is called the Half-Perimeter Wirelength, and sometimes abbreviated HPWL. But it's also called the Bounding Box Wirelength, usually BBOX, BBOX. And you'll see us using them interchangeably in this lecture. The idea is pretty simple. I'm going to describe it in words first. You put the smallest bounding box you can around all the gates. So, let's assume in the little grid things that I'm showing you. The gate lives in the center of the grid slot. And the coordinates that are labeling x equals 0, 1, 2, 3, 4 in the example I'm showing on the bottom left, y equals 0, 1, 2, 3, 4, 5. Let's assume the xy coordinates are the center of the cell, the grid. And that the gate lives on that, that coordinate. And so, what we do is we put the smallest possible box around all of the gates. And then, we measure the width of the box, delta x, and the height of the box, delta y, and we add them together, and that's our wirelength estimate. So, for this little example where there's a gate at 1,4 and a gate at 3,1, the first thing we do is we put a bounding box. And so, the box goes from x equals 1 to 3 and y equals 1 to 4. And then, we simply we do the math. Delta x is 3 minus 1, that's 2. Delta y is 4 minus 1, that's 3. We add them together, 3 plus 2 is 5. The half-perimeter wirelength is 5. And one of the great things about the half-perimeter wirelength is that it's easy to do a multi-point net. So, here's a four-point net again on the x equals 0 to 4, y equals 0 to 5 grid gates at 1,4, 3,3 3,1, 3,3, and 4,5. We again put the smallest bounding box, and that goes from x equals 1 to 4 and y equals 1 to 5. And then, we again, we can do the math. Delta x is 4 minus 1, that's 3. Delta y is 5 minus 1, that's 4. The half-perimeter wirelength estimate for this gate is 3 plus 4, is 7. So, the great thing about the half-perimeter wirelength, it's easy and it works for multi-point nets. So, more generally, the half-perimeter wirelength, the general formula that I'm showing here is, you look at all of the x-coordinates of all your gates, you take the max. You look at all the x-coordinates of your gates and you take the min and you take the max minus the min. Then, you look at all the y-coordinates for your gates, you take the max. You look at all the y-coordinates for gates, you take the min. You take the max minus the min, and that's what you add together. The maximum, the x-coordinates for the gates minus the min of the x-coordinates for the gates plus the max of the y-coordinates for the gates minus the min of the y-coordinates for the gates, that's the half-perimeter wirelength. One of the important things to note is that this is always a lower bound on the real wirelength. Which is to say, it is always less than or equal to the real wirelength no matter how complex the final routed path is. You need at least this much wire. And look, this just makes sense. You need to go from the gate on the far left to the gate on the far right. That's delta x amount of wire from the previous diagram. And you need to go from the bottom most gate to the top most gate, and that's delta y amount of wire. And no matter how you route this path, you need delta x plus delta y amount of wire. So an important aside to note is that, all of the wiring on big chips and most of the wiring on big printed circuit boards is strictly horizontal and vertical. There's no arbitrary angles for manufacturing reasons. That's rigidly true for integrated circuits these days, big modern digital SOC designs. there is some funny all angle wiring to, to do things like get out of complicated pin arrangements underneath the big chips. But once you escape from the pins near the chip then you know, it already actually go across the board strictly horizontal and strictly vertical. So that's just another reason the HPWL is a good estimator because it just does a nice job of estimating the lower bound on the amount of wire. No matter how many points you have, no matter how many pins you have, no matter how many gates you have on your net. this is just interesting, this is what the actual half-perimeter wirelength estimation distribution looks like for a little design. So this is old data. So this is 165,000 gate ASIC from the late 1990s from Jens Vygen's group at Bond/g. this is 181,000 net. So you know, call it about 200,000 nets. I'm showing you this because it's just sort of an, an interesting piece of data. the horizontal axis here shows a histogram buckets for the wirelength. So, 0 to 0.5, 0.5 to 1, 1 to 1.5, 1.5 to 2, 2 to 2.5, 2.5 to 3, 3 to 3.5, etc., up to 4, 4.5, 5, 6, 7, 8, 9, 10. And then, note at the end the buckets get bigger, 10 to 15, 15 to 20. this is actually in millimeters, this is a really old chip. So, it's one of the things to be aware of is that this is a really old chip. so don't think about this as being anything other than a a normalized number. And note that the vertical scale is a log scale, right? So, the vertical scale is a log scale. The vertical scale says, how many nets have this length? So, you know, question. How many nets are the shortest possible length between 0 and 0.5 in whatever units are appropriate? And the answer is 100,000 of almost 200,000 nets. How many nets are between 0.5 and 1? and the answer is, as far as I can tell, probably about 30 or 40,000. Remember, this is a log scale, maybe 20,000. the idea is that most nets are short, most nets are very short. But unfortunately, there's a really long tail, and there are nets out here that are you know, 40 times longer than the shortest net, and those nets are not zero in number. So, real routers deal with the fact that most of the nets are short but there's a non-trivial number of nets that are long. And so, is just an interesting data that shows you that in a concrete way. [MUSIC]
