[MUSIC]. So here in lecture 12.7, we're actually going to get the delay result that we want. And so, what we did in the previous lecture is we said, you have a routed wire. It's got a complicated geometric shape. The only way to really analyze that is to turn it into a circuit. We turn it into a special kind of a circuit called an RC Tree, it's a tree made of resistors. And at every intermediate node, there's a capacitor hanging off. What we're going to show you is that there is a very special formula, it has a famous name. It's called the Elmore delay. and the Elmore delay is, a number, it's a time, it's a delay which we can calculate through one walk from the root of the tree, to the leaf of the tree that's the gate. The driven gate to which you want to know the delay. There's a very simple walk from the top of the tree to the bottom of the tree. Using the resistor and capacitor values we calculated for the geometric wire, that will get us a delay. So what we're going to do in this lecture is we're going to show you how to take the RC tree use it to do something interesting to calculate the Elmore delay for the wire. So, once we have the definition of the RC tree, we can actually do a lot of interesting analysis. One of the things we could do is, we could do some electrical engineering kind of detail and I could actually derive at the circuits level, the very interesting delay result we're going to show. but, since not everybody in the class necessarily has a circuits oriented background, I'm just not going to do that. So, the really nice thing about the RC tree model is that even though it starts as a circuit it turns into a simple tree object, I mean it's really a data structure. And there's a special computational walk on the tree that gives us all the delay information we need. So it is fair to say that there is almost no circuits for us. There's just the computational recipe for how you use the tree. So let's go see how that works. So here's the RC Tree in it's general form. It's a tree of resistors, and, and so I'm showing you the tree again. But now I'm actually labeling the nodes so we can actually talk about it. So, you know, there's a resistor from a to b, b to c, and c to e, a resistor from b to d, and d to f, it's a tree. and there are capacitors hanging off all the intermediate tree nodes at a, b, c, d, e and f and what hanging off means to a circuits person is disconnecting the node to ground. The Root of the tree is where the signal is input, and so that's the A node. The Leaves of the tree are the driven outputs, and so those are e and f respectively. And, you know, for a second we might just redraw this like a graph, so that, you know, to just take away this sort of the circuits feel of it. And so it's again, it's the same tree. There's resistors, there's a box labeled R and there's a capacitor, a box labeled C. And there's a tree of resistors from a to b, b to c and c to e, b to d and d to f. And at a, b, c, d, e and f. There's a c box hanging to the ground. So this looks a little less like a circuit and a little more like a graph, if that makes you feel more comfortable. there's two missing pieces of detail on the circuit side, which is that you have to model the driver and you have to model the driven gate. So the thing that I'm showing, you know the thing in the middle of this diagram, a, b, c, d, e, f, nodes in it, resistors and capacitors, that's the wire. You still need to model the gate that drives the wire, that's the driving input, and that turns out to be modeled as, as basically a battery, a voltage source that turns on at time zero. With a voltage of 1, through a driving resistance. I'm just going to put a star by the resistance. and, you have to model that gates that are being driven, and each of those things actually just gets modeled as a capacitor. So, you build the RC tree for the wire, you need one more resistor to model the source gate. You need, two, a capacitor for each of the target driven gates. And then, you can actually do the analysis on this thing. So, just to sort of, you know, summarize in a sort of a cartoon. I've got a wire, i've got a, a gate driving a wire, driving another couple of gates. I turn that into a tree, it's a tree of resistors. In this case, a, b, c, d, e, f is the nodes. And at every intermediate node, a capacitor hanging off of it. I add to that another resistor and a voltage source. That models the gate that's driving things. I add to that also, another capacitor for every gate that is, being driven by this wire. And what I'm actually going to be bale to do is a very simple computation on the tree to calculate a delay number for each output of the tree. And one of the things that's really great is I'm going to get a unique number for every output. So I'm going to really physically model the shape of the wire. And so I'm going to get maybe a long delay to some outputs, and a short delay to other outputs, depending on what is correct and physical for the shape of the wire. So this is this sort of very famous result, we're heading toward and this has a name. It's called the Elmore delay. So it's named after a physicist, famous Physicist Elmore. this was derived, amazingly, way back in the 1940's for certain kinds of circuit applications. And then it was sort of resurrected, like 40 years later, by Penfield, Rubinstein, and Horowitz for these RC trees because it turns out to be useful for, for you know designing modern integrated circuits. It's famous enough that if you type Elmore delay into Wikipedia, you will get an article on it and you can see all the original references and things like that. For our purposes, what's wonderful is that it's very simple and very useful and has a very easy computational recipe. So, here's the tree again, and I've got the input driven gate modeled by the resistor with a 5 on it. And I've also got the 2 capacitors at nodes e and f at the output added. So I've got the driving gate and the driven gates and it's, again, a little tree of resistors with nodes a, b, c, d and e. There is a resistor of size 2 which we know is a and b resistor 4 between b and c resistor 1 between c and e resistor 1 between b and d resistor 3 between d and f. And there's a capacitor of size 1 at node a, 2 and node b, 1 at node c, 1 at node d, 3 and node d, and 1 at node f. So, this is the example, we're going to see this several times and there's a very simple computations, so the Elmore delay is tau to time. We said tau is to be 0 and you walk down the path of resistors from the root to the leaf where you want to calculate the delay. And at every resistor you do the following, you take the resistor value, you are on and you[COUGH] multiply it by a number. And that number is the sum of all the capacitors you can see downstream. And we are going to talk about what this means. what's a downstream capacitor? it's any capacitor reachable in the tree below this resistor. So if current is going through this resistor and heading to the bottom of the tree it's any capacitor that can take that current. Alright, so let's be concrete on this example. I've got resistor Ri equals 2 between nodes a and b. Alright, what are the downstream resistors for node Ri? And the answer is, the capacitors at node b, c, d, e, and f. So, the resistors at node is between nodes a and b, what is the downstream capacitance? Alright, any current going through node through resistor Ri equals 2 could end up on capacitors at nodes b, c, d, e or f. So you're going to take Ri is 2, and you're going to multiply it by 2 plus 1 plus 1 plus 1 plus 3. You're going to add that term and you're going to keep doing this computation. So, simple as that. So this is just a version in words. You know, Ri is equal to Ri is to the resistor in the tree. The term we would add to the Elmore delay is 2 times 2, plus 1, plus 1, plus 1, plus 3, okay? So let's just take a look at it. So here's the tree again, a, b, c, d, e, f, is the nodes. we want to calculate the delay to a particular point in this tree. So, where do we, where are we looking? we want to go down the resistor, the 5, the resistor that goes into node a, a to b, b to c, c to e. We want to calculate the delay for the capacitor that's at node e, alright? and so we just use the formula. And the formula says you set tau to be equal to zero and then, you start walking down the resistors. So you walk down the resistor that's a value five. And you add together all the capacitors down stream, which in this case is all the capacitors, 1 plus 2, plus 1, plus 1, plus 3, plus 1, okay? And then you go further, and you go to the resistor with a value of 2 between a and b, and you add all those resistors down stream, 2 plus 1, plus 1, plus 3, plus 1. and then you keep going, so we're going to go down the resistor of value 4, between b and c. While the resistor, the capacitors you see now in front of you are 1 and 3, so 4 times 1 plus 3. And then you get the resistor of value 1 between c and d, multiply that by the capacitor 3. 45 plus 16, plus 16, plus 3, if I did it right, it's 80, 80 is the delay to that note, it's as simple as that. if you're not, very knowledgeable about the circuits let me offer you an alternative analogy. So this is like a, like a branching stream. So I've got a little picture of a stream here, sort of dividing, and dividing, and dividing. An the goal is that you are downstream, and you are trying to fill your bucket, okay? And what you care about, is how fast you can fill your bucket. Now unfortunately, at every branch point, somebody else has a bucket, and so the farther you are downstream, the less water you can get. Alright, so just to sort of draw this, there's water going in, it's a fixed supply up at the you know mouth of the river, the source of the river. And there you are with your bucket way, way down at the, one of the ends of the branch points of the river. And unfortunately, everybody else at each one of those branch points has a bucket and so the water that's going in that's a fixed limited supply is filling up everybody's bucket. What you want to know is how fast you can fill your bucket. All right, how fast can you do that? So what matters? What matters is the width of the upstream branches, because that's going to tell sort of like how much water can go down those branches. And the size of everybody else's bucket. Alright, so you know, how does this relate? Well you know, there's water going in, and there's all these branching and branching things in this tree and there's a bucket at every node at every place the tree branches. And there's your bucket which is one of the buckets at the very end. And the answer obviously is that the water going in is like the electrical current that is being driven from the driving gate. Alright, so the gate is the thing that is sort of supplying that current. Okay, everyone one of those buckets is like the capacitor that the wire, the straight line wire segment presents that you can't ignore. So as well as each of those wires being a resistor, they're a capacitor. They're like a bucket. The width of those wires is like the width of the stream. Either there's a lot of water, current, flowing through the branch, or there's not a lot of water flowing through the branch, and so it depends on it, it determines how fast your bucket can be filled. You know, how much current is coming down the branch. And y'know your bucket is the gate that is being driven. How fast you can fill your bucket is how fast the signal will lets say rise, going from a logic 0 to a logic 1, is how fast you can get a 1 from the source, to the sink in this design. So, the analogy is, you know kind of soft, but it's actually surprisingly good for this particular example. So, a little bit of a circuits aside, if you actually care about this you know, what exactly is the Elmore Delay Modeling? imagine that you could model the path from the input to the output of this particular circuit, so here's my tree again and I'm modeling the path From the driver, through a, b, c, d, e. Imagine that you could actually model that path with a circuit that had exactly one resister and exactly one capacitor. It would be a so called equivalent circuit, you know what I mean? The real circuits got lots of resistors and lots of capacitors. But suppose you decided to model that, you know, the, the path from the input to this one output, with everything else in the tree accounted for, with a single resister and a single capacitor. any circuit that has a single resister and a single capacitor, has a, a response when you sort of you know, close the switch, current flows, you charge the capacitor. You get a, you get a mathematical form that looks like you know, the voltage asymptote that it's going to go 2 times 1 minus e to the minus t over tau. Right, and that tau is basically you know, one resistor, one capacitor circuit, the resistor times the capacitor, okay? if you were to model the input to the output with everything else in the tree accounted for as a single R and a single C and you get a single so called Time Constant, tau, what tau would that be? And the answer is, it would be the Elmore Delay. That's exactly what this thing is. If you want to model this thing as the best approximating circuit that is pretending to have one resistor and one capacitor that circuit has a time constant, that's the Elmore delay. So it's a real interesting circuits derivation which unfortunately we don't have time to do. But if you don't know any circuits you don't need to know any circuits. All you need to know is that you can walk the tree. Multiply resistors by sums of capacitors in front, downstream. And you can get a real delay to any given point on the wire. So that's a wonderful and useful thing. Let's go see what we can do with it. [SOUND].
