You should complete the VLSI CAD Part I: Logic course before beginning this course. A modern VLSI chip is a remarkably complex beast: billions of transistors, millions of logic gates deployed for computation and control, big blocks of memory, embedded blocks of pre-designed functions designed by third parties (called “intellectual property” or IP blocks). How do people manage to design these complicated chips? Answer: a sequence of computer aided design (CAD) tools takes an abstract description of the chip, and refines it step-wise to a final design. This class focuses on the major design tools used in the creation of an Application Specific Integrated Circuit (ASIC) or System on Chip (SoC) design. Our focus in this part of the course is on the key logical and geometric representations that make it possible to map from logic to layout, and in particular, to place, route, and evaluate the timing of large logic networks. Our goal is for students to understand how the tools themselves work, at the level of their fundamental algorithms and data structures. Topics covered will include: technology mapping, timing analysis, and ASIC placement and routing. Recommended Background: Programming experience (C, C++, Java, Python, etc.) and basic knowledge of data structures and algorithms (especially recursive algorithms). An understanding of basic digital design: Boolean algebra, Kmaps, gates and flip flops, finite state machine design. Linear algebra and calculus at the level of a junior or senior in engineering. Elementary knowledge of RC linear circuits (at the level of an introductory physics class).
Technology Mapping—Recursive Matching
Loading...
From the course by University of Illinois at Urbana-Champaign
VLSI CAD Part II: Layout
8 ratings
University of Illinois at Urbana-Champaign
VLSI CAD Part II: Layout
8 ratings
From the lesson
Technology Mapping
Technology Mapping! We omitted one critical step between logic and layout, the process of translating the output of synthesis -- which is NOT real gates in your technology library -- into real logic gates. The Tech Mapper performs this important step, and it is a surprisingly elegant algorithm involving recursive covering of a tree. Another place where knowing some practical computer science comes to the rescue in VLSI CAD.
Meet the Instructors
Rob A. RutenbarAdjunct Professor
Department of Computer Science
[SOUND]. So here in Lecture 10.4, we're going to continue our exploration of technology mapping. We know that we have to require that the output of logic synthesis is a set of trees, and we now know how to tree-ify it. And we know that we require that the gates in our standard cell technology library are themselves little trees. The next problem we have is which gate that we have available in our technology library fits where in the output of logic synthesis? And because of the way we've now modeled this is a very stylized node matching problem in sort of Computer Science, we have a very simple set of structural matching problems to solve. Where do these little gates fit in the big net list? So this is matching. And so, let's go show how the matching process works to figure out where the gate library is used in the technology mapping process. So, where are we in our discussion of technology mapping as tree covering? We showed that the, is possible and pretty straightforward to take the output of multilevel synthesis. After it's been converted in simple nand not form and make sure that it's a set of trees. we, we split things on fan out nodes. And we're going to map each tree individually. And we also showed that it's pretty easy to make sure that the pattern library, the gates in your technology library, are themselves trees. And imposes to some interesting kind of surprising little restrictions. Like you can't use x or gates. But, but that's not too big a deal. And, and honestly there are some ways around that. The next step in the process is, how do I figure out where and how the elements in my technology library actually match inside my larger subject tree? So let's go talk about that. That's the tree matching problem. So, what's the goal? The goal is to determine, for every node in the subject tree. What library gate or gates. Can match there. Structurally again, black circles on black circles, white circles on white circles, input boxes anywhere. There is a, a very strict forward approach here called recursive matching. The simple idea is just to try every library gate. And every note of the subject tree. The library gates, you know the elements in your technology library. They're small patterns. Right? They're not, you know, thousands and thousands and thousands of nodes. They're you know like five or six or eight or ten nodes in the graphs, so this is just not too much work. And the notion of a recursive matching, means, basically, you match the root of the subject, where you're trying to map this little logic gate, with the root of the pattern. And if those things match, then you recursively match the children. And it's much easier to see as a little illustrative diagram, so let's just go do that. So how does recursive tree matching work? Recursive tree matching is answering this question, does the library pattern, p, which is itself a little tree, match node s inside our subject tree? So I've got a picture here, I've got a great big gray triangle which is the subject tree and I've got a little black node, that says node s, a node internal to our subject tree. And then I've got a little pink triangle with a p in it that says oh, I'm pattern tree p and I have a node at the top of me, which is node r. And there's a question, a little arrow between node s and node r that says match question mark. So, this is the question, if I take this pattern tree out of my library, maybe this is an end or invert22, and I say, hey can I put this gate here in the subject tree? what do you actually have to do? Well, the first thing you have to check is if node s matches the root r of pattern p. And then you have to recursively ask if the stuff on the left side matches and the stuff on the right side matches. And that's easy to sort of draw schematically. So, what does recursive matching do? Right? So again, I've got a great big gray triangle, which is the subject tree with a big black circle in the middle of it, that's node s. And we've got a little pick dotted triangle, which is the pattern tree with a black circle at the top of it. And so the first thing you ask is, does note s internal to my subject tree match the pattern root r. Are they both black circles? Are they both white circles? Okay? Or is one of them actually a square box because it's an input? And then if that's true, then you say, so does the left child of node s inside the subject tree match the left child of pattern p from my library? And you can see why this is a recursive algorithm. You know what does the recursive algorithm say? It, you know, you call it on node s right with pattern r and you say oh, do the roots match? Yes. Oh, well then, go down one node. Go look at the top of the sub tree which is the left child and recursively call the algorithm on that. And when you recursively call it on that it's again going to ask, so do the roots match? And it's just going to kind of walk down like that. So the first thing you do is you check if the pattern root matches the subject root. And then you recursively check if the left child matches, and then you recursively check if the right child matches. I'm not showing a little dotted line like I, I did before. And, you know, that's it. It's and it's not that complicated, because the patterns are themselves not very big trees, and you just apply it. Now the one subtletly here I will again remind you of is that you have to be careful with matching assymetric library patterns. The and or invert to one that I'm showing here is assymetric. Right? It has an inverter on the top and then a nand gate. But the nand gate is fed by one inverter and one, not one nand gate. So it has one side where you can go down and find a white bubble with two children. And another side where you can go down and find a black bubble with one child. And you actually have to match it both ways. Which requires for asymmetric patterns asking the question, does the left child of the subject match the left child of the pattern? No. Does the left child of the subject match the right child of the pattern? Maybe. Right. So, you have to do these complicated left left, left right, right left, right right, kind of matches. it's just some more case analysis. It's not particularly complicated. But I'm, I'm, I'm just sort of warning you that you actually have to do that. What do you get after recursive matching? The answer is, for every gate-type node in the subject tree, for every black node or white node, a node that's a nand gate or a node that's an inverter, you get a list of the pattern trees that match at that node. Which is to say, you get a lsit of gates that have the property that you could put them there. And their output could make the, the output that that gate makes, right? So every one of these nodes has a wire going into it from the top, with a label on it. What that means is that you could actually put the ga, the pattern gate there. And make the wire with that output in the final logic. And so, we annotate each such node in the tree with this matching information. So I can just, you know, illustrate that here, by saying, what do we get in my little z tree that we've seen many times here, which has ABCD as inputs, Z as output and 3 black nodes and 3 white nodes, PQRST. Well, what do you get? You get for the black node that makes output z, a little list that says patterns p2 p5 p78 match. And for the white node that makes output t, you get two patterns; p6 and p11 match. And for the black node that makes output S, p8 matches. And for the white node, that makes output r, p6 and p7 match. And for the black node that makes output P match. That makes output p, you get p8 matches. And for the white node that makes out, put q andyou get p5 that matches. So, for every internal node that's like a gate of some kind, you have a list of gates from your technology library that have the property that you could line up their root right there. And the output would make the name of the wire that comes into the top of that node. So, this is the sort of structural part of the mapping. Now, we get to what's actually the really interesting part of this algorithm. What's the best cover? There's many ways of actually choosing from all of the gates that can be located and matched inside the subject tree. How do you actually pick the one that has the least total cost that's still structurally correct? That's where we get another, very pretty, recursive algorhythm. So let's go talk about that. [SOUND].
Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.
© 2017 Coursera Inc. All rights reserved.
