Chip Placement with Deep Reinforcement Learning | Paper Explained
❤️ Become The AI Epiphany Patreon ❤️ ► https://www.patreon.com/theaiepiphany
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

In this video I do a deep dive of the "Chip Placement with Deep Reinforcement Learning" paper. They devised a novel RL approach for an efficient and highly performant chip placement routine.

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ Paper: https://arxiv.org/abs/2004.10746
✅ Tesla's custom chip: https://www.youtube.com/watch?v=Ucp0TTmvqOE&ab_channel=Tesla
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 
00:00 Paper keypoints
01:21 Why do we need faster chip design?
05:30 High-level pipeline explained
09:20 RL agent explained
14:15 How are computers made
21:00 Assumptions
22:35 Wirelength and macro heuristic
24:55 Macro placement masking
27:50 Edge Graph Neural Network details
29:50 Results
32:25 Visualizations
34:25 Further research

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
💰 BECOME A PATREON OF THE AI EPIPHANY ❤️ 

If these videos, GitHub projects, and blogs help you,
consider helping me out by supporting me on Patreon! 

The AI Epiphany ► https://www.patreon.com/theaiepiphany
One-time donation: 
https://www.paypal.com/paypalme/theaiepiphany 

Much love! ❤️

Huge thank you to these AI Epiphany patreons:
Petar Veličković
Zvonimir Sabljic
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

💡 The AI Epiphany is a channel dedicated to simplifying the field of AI using creative visualizations and in general, a stronger focus on geometrical and visual intuition, rather than the algebraic and numerical "intuition". 

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
👋 CONNECT WITH ME ON SOCIAL 
LinkedIn ► https://www.linkedin.com/in/aleksagordic/ 
Twitter ► https://twitter.com/gordic_aleksa 

Instagram ► https://www.instagram.com/aiepiphany/ 
Facebook ► https://www.facebook.com/aiepiphany/ 

👨‍👩‍👧‍👦 JOIN OUR DISCORD COMMUNITY:
Discord ► https://discord.gg/peBrCpheKE

📢 SUBSCRIBE TO MY MONTHLY AI NEWSLETTER:
Substack ► https://aiepiphany.substack.com/

💻 FOLLOW ME ON GITHUB FOR COOL PROJECTS: 
GitHub ► https://github.com/gordicaleksa 

📚 FOLLOW ME ON MEDIUM:
Medium ► https://gordicaleksa.medium.com/
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

#hardware #reinforcementlearning #ai
 What's up? In this video I'm covering this paper called chip placement with deep reinforcement learning. Basically, yesterday I saw this tweet from Anna Goldie where they've just published the nature version of this work and I thought covering it because it's a really interesting piece of work. It combines both like the electronics, which is something I have some background in as well as machine learning more concretely like reinforcement learning and graph ML. So it's exciting combination and super super impactful work. So I thought covering it and basically what they achieved is they managed to train an RL agent combined with some graph ML for learning like nice representations in order to do displacement much faster than what previously was necessary. So like they needed like humans usually need like multiple weeks to do this and now it's like less than six hours and it's achieving even superhuman performance looking just at the metrics like the area. So basically, yeah, we want to minimize the area because we can cram more transistors inside of it and more compute us and also they want to minimize other things like power consumption as well and under certain constraints like density congestion like you don't want to have too much too many wires overlapping on a single like on a certain piece of like on a certain surface of the chip. So that's a high level overview. Now let me let's dig into the paper and yeah, see what they did. So in this work we present a learning based a learning based approach to chip placement one of the most complex and time consuming stages of the chip design process. Unlike prior methods our approach has the ability to learn from past experience and improve over time. So yeah, that's the main thing basically obviously like prior to this work there were many other approaches mainly some optimization based approaches like simulated annealing and some more like heuristics and yeah a bunch of different theory was developed, but none of those were actually deep learning algorithms. And they say here our objective is to minimize the PPA. So as I mentioned so the power consumption the performance whereas they mean basically timing and we'll see what that exactly is like you basically want to make sure that certain like logic gates in your like flip-flops in your in your like circuit get certain signals on time. So there are these like timing constraints you have to obey and we'll see more details a bit later. And obviously the area again like more transistors you can cram into the chip the more compute you get and that's better. So and we showed that in under six hours our method can generate placements that are super human or comparable on modern accelerator netlists where netlist is just a fancy way of saying like a graph that basically tells you how each of the components on the chip are are connected together. So whereas existing baselines require human experts in the loop and take several weeks. So that's the the main like the the main like point they're driving here. They automate this they make it even superhuman and they make it faster, which is huge. And so why do we care about this? Like basically well they say it here the world is moving towards specialized hardware to meet AI's expectations and to meet AI's exponentially growing demand for compute. However today today's chip take years to design leaving us with a speculative task of optimizing them for the machine learning models of two to five years from now. And the logic is pretty simple if you can cut down the time you need to to loop over different designs you can experiment much faster. And it's the same thing as in deep learning where you want to make sure that your training length is like yeah shorter obviously like the same thing that happened with image net training for example there we needed like multiple weeks and then finally there was a paper like a couple of years ago where they've trained like image net like a vision model classifier in like half an hour or something. It's probably even better today. So basically when you short those you can iterate much faster obviously and that's that's really really precious. So one one nice example of these custom chips is maybe Tesla. That's the first thing that popped onto my mind. They have a customly designed computer vision chip set on their vehicles and it's not just computer vision. They're also using like different sensors not just the RGB cameras. They're also using radars etc. So the only thing they're not using and that's slider because Elon Musk as you probably know rants about those all the time and says that we only need to use RGB cameras. But that's a topic for another for another video. Okay so the objective is to place a netlist graph of macros for example static RAM which is basically you probably know of DRAM. That's Dynamic Random Access Memory. These are S-RAMs are usually non-volatile so they are even more expensive and they are they are more performant than DRAMs. But they do take more area so that's a trade-off. Standard cells logic gates such as NANDs, NORs and XORs. You probably heard of XOR if you did did anything related to cryptography. Onto a chip canvas such that power performance and area are optimized while adhering to constraints on placement density and routing congestion. Yeah for the time being like you can just have an intuitive understanding of these and I guess you already have like basically you don't want to have multiple wires too many wires going over a certain cross section of the certain grid cell on your like canvas. That's the high level overview. Now let's dig into the architecture. Let me show you the high level like pipeline how this looks like. So basically what they do is the following. So they treat this they pose this as a reinforcement learning problem. And as you can see here the state is modeled like you have this chip canvas so currently you don't have anything on it. And basically as I already mentioned you can treat your chip as a hypergraph and that means the following. So let's assume I'll just draw macros as these squares. So we'll have a couple of macros and macros can be as you saw like SRAM or it can be memory control or whatever. So these are somehow connected like this and then you have these standard cells. I'll just denote them as circles. And basically what was it's a hypergraph. So that means basically the single edge can connect to multiple nodes. That's the definition of the hypergraph. And now so imagine you have a bunch of these you have hundreds of macros you have millions of standard cells and you want to somehow place them onto this fixed size chip canvas. OK. And so what you do is you somehow and we'll see the details a bit later using this graph neural network you kind of embed this information about the connectivity. And that will be your state. And then you're doing the following. So the agent takes that state and outputs an action and an action is just take a macro. So we'll be just focusing on placing these macros as we'll soon see these will be handled by some forced direct method which is some heuristic that was previously devised. So they're just kind of piggybacking on certain other methods to do that part. So they place the macro here and after that you get a new state and then you just output the new action where you place another macro onto the chip canvas. And you do so until you've placed all of the macros as you can see here. And then from that point on you use this force directed method to place the standard cells. So you will just take those cluster clusters of standard cells and will place them somehow onto your chip canvas. And finally you get the reward. And as you can see immediately the problem is pretty hard because it's you get zero rewards all the way down and only at the end do you receive the actual reward. So it means the credit assignment problem is going to be pretty tough. I mean the horizon is not that big. They won't have more than let's say thousand macros. But like still it's a tough problem. And this reward as you can see let me just decrypt this for you. So this is a half perimeter wire length. We'll see what that exactly is. But it's a roughly it kind of takes into account the length of wires you have in your chip. And that kind of correlates positively with power consumption and with area and we'll see those a bit later. OK. So that's a that's a high level overview. And I mentioned it here. So our our true reward is the output of a commercial electronic design automation tool including wire length routing congestion density power timing in an area. However RL policies require hundreds of thousands of examples to learn effectively as you already know. And so it is critical that the reward function be fast evaluated ideally running in a few milliseconds. So in order to be effective these approximate reward functions must also be positively correlated with the true reward. So the point the whole point is they can evaluate the real reward the true reward. But that's super slow. So you have to use these EDA tools. And so they decided to just take something as a proxy which is fast to compute a and B positively correlates with the things they care about. And we mentioned those already. So that's the PPA stuff. OK. So while we treat congestion as a soft constraint so lower congestion improves the reward function we treat density as a hard constraint masking out actions grid cells to place nodes onto whose density exceeds the target density. So in order to understand this part we should go and see how the policy network looks like. Let me scroll down here. I'll skip some stuff and then I later return. OK. So this is how the model looks like. And to end basically we have two portions here. The first part is the representation learning part. So we have something called edge graph neural network some graph neural network data device specifically for this work. And then we have your basic value net and basically policy network. So this is your actor critic RL agent. They're using PPO that's proximal policy optimization algorithm published by opening a couple of years ago. So that part is pretty standard. Now let's see. This part is pretty interesting and novel. So let's see how they manage to parse the netlist. So the hyper graph of your components into something into some representation that contains valuable information that can be used to figure out where to place the next components. So the way they train this whole pipeline is using supervised learning and the whole goal is to learn how to predict the reward. So that's how they train this part. So they take this part in isolation and they trained the following way. So again you have this hyper graph. So you have macros. You have some like standard cells. They are somehow connected. It's not that important. OK like this and what to do as you can see here. So if you're familiar with graph ML if you're not I made a whole playlist and I'll link it somewhere here. You should check it out. But like I'll try to explain it on a high level and basically it's pretty simple. So every single node in your graph has a feature vector associated with it. So whoops let me delete that. OK so you have a feature vector like this. You have a feature vector here. Every single node will have a feature vector associated with it. The second thing is in this paper actually even the edges have feature vectors associated with them. So you have something like this. So every edge and every node has a feature vector. So what I do is as you can see here the graph neural network takes in the connectivity information and all of those feature vectors. And it kind of it somehow processes these. So what graph we'll see the exact equations here a bit later. But like basically you just somehow combine those. You manipulate them using fully connected neural networks. You aggregate the neighbor the neighbors. So for example this one will somehow take all of its neighbors. So this is the neighbor and this is the neighbor. So we will take those feature vectors like this one and this one and it will somehow combine them with this one. So it's a it's it's using this relational inductive bias of connectivity and it's accumulating those feature vectors to create a novel representation. So this is going to be something maybe of a smaller dimension. Let's call it V prime. If this was vector V this is V prime. And they are going to output that as the output of of of GNN. So as you can see here edge edge embeddings. So that's a set that's that's a matrix that's of dimension E times basically D sub E. So E is the number of edges in your graph and D sub E is just the like feature vector dimension. So once you have the matrix what I do as you can see here they do this reduce mean operation. So they just take a mean over like element wise mean over all of these feature vectors. And they get the single feature vector. That's the graph embedding. OK. That somehow roughly captures the dynamics the information about this graph. And the second thing they do is they take the current macro ID. So there's the current macro you want to place into the chip canvas. And they so again here you have a table that's N times D sub V. So N is the number of nodes. This V is the dimension of your node feature vector. And they just take a single one. So they just take a DV vector here. OK. And extract it. And finally they have some metadata information like the like the length of the wire on your chip etc. So they have some metadata information and they concatenate all those they feed it through the fully connected layer. And that's it. So now as I already told you they're going to train this thing to to kind of understand to predict the reward of the of the placement. And I'll get into details a bit later. But that's that's that's it in a nutshell. So once you train that you use your presentations it learned to basically as a Kickstarter for these policy and value networks and they are trained as I said using PPO. So that's it. And now I'm going to slowly start digging into the details and later we'll see the experiments and the results they got. OK. Before I do that I think it will be quite useful for you to maybe understand a little bit about some electronics one on one and you'll hopefully have an epiphany moment. OK. So as software the same thing goes with hardware. Basically you have a bunch of abstraction layers. So in software we have like on the lower lowest layer you have firmware you have something like what called hardware abstraction layer. You have drivers and you have operating systems and you have compilers and you have all of those systems that translate the higher level languages into like something that your computer can parse and understand. And finally you have the application layer. So obviously a bunch of abstractions and the same thing goes for hardware. So you have like you have on a really high level you have like you have a CPU and you have maybe like the direct memory controller. So that's just a device that can do whom CPU can just delegate basically certain memory intensive operations. And then you have memory like you have a memory block here and let's say both are connected to memory both the CPU and the M are connected to memory. So if you zoom in into any of these components like take maybe direct memory controller you'll end up with two types of circuits. So basically you have combination logic and you have these circuits which are called sequential logic which contain the memory in the system. So they are stateful. So if you take a look at this one. So what's the main difference. The main difference is the following. If you have this record this is called inverter. Basically if you feed it zero it will output one and if you feed it one it will output the logic value of zero. And the thing is if the thing is with these combination logic gates is that as soon as you change the input. So if you go from zero to one the output will go from one to zero really quick like maybe in 20 picoseconds or something. Now the trick with these flip flops with these memory circuits is so this is a deep flip flop. It's a simple one of the simplest flip flops out there. So basically what happens here you can change this as much as you want like from zero to one. Nothing will change here is going to keep one here until you have the clock. So the uptick of the clock or the down tick of the clock. And basically so hopefully you know what like a clock signal is. It's something that drives your computer. It's a basically digital signal that goes from zero to one with a certain frequency and on each of these upticks or downticks something is going to happen. So on each tick the sequential logic gates so these these gates like flip flops will change their state. So if you keep one here and then the uptick comes at that point the one will propagate here on the net. And if you change it now to zero and the down tick comes for example then this will go to zero. So these are keeping that they have the memory. That's that's that's that's the main trick. So having said that let me go even even deeper. So let's take one specific gate like NAND. And what NAND does is the following. Yeah you've seen these if you've ever done any programming so you know about the NAND operator. This is how you write it down in Python. And basically this is the opposite of an AND gate. So you just are not AND. And basically as you can see here looking at the table you know that AND gates give you one only when you have one and one as the input. And all of the other values will be zero. And NAND is just the opposite of that. As you can see it's inverted AND gate. And now this is the like abstracted view of this gate. And if you dig a bit deeper and take a certain implementation which is called CMOS implementation of the NAND gate which is basically complementary metal oxide semiconductor doesn't matter. But basically there are different ways you can implement these abstract logic gates. The same thing as you can do with if you have like an image classifier you can implement it using a neural network using SVM using I don't know like even like k-nearest neighbors whatever your favorite classifier is. The same thing goes here. You have a bunch of different ways how you can implement the very same thing and that is the NAND gate. So here we have a specific logic you can use TTL. There are many different logics you can implement. Now let me show you why this works. So basically let's take as an input one and one. And when I say one you again have to implement one somehow on your system. So let's say for example that we have a voltage supply that's maybe I don't know like 0.9 volts. And so on this system one will be defined as something close to 0.9 volts and zero will be defined as something close to zero volts. So that's how you implement zero and that's how you implement one. And so if I feed once here for example and so that's 0.9 volts. And if you feed one here as well and as you can see this small circle again that means it's inverted. So we'll be adding zero onto this gate and zero onto this gate. And what happens is because you brought a huge voltage here you're going to toggle on this transistor. And so the current will start to flow here and here and you're going to block these two because you brought zero voltage here. And so as you can see you're basically making a direct connection to the output to this thing here. And let's say this is ground so it's zero volts and basically that means your output is zero volts which is zero. And let's see so one one you get zero. The same thing goes for zero zero. So if you have if you have if you bring zero zero you're going to basically turn off these two and you're going to turn on these two. And so you're basically bringing the voltage supply directly to the output which is 0.9 volts which basically translates into logic one. And yeah so that's that's how it works. That's how your computer computers basically work. And going even deeper like people have to design these and you can see here so this is how you basically place these metal wires. And this is how you implement a NAND gate. And finally you have the last step and that's the production. You actually do some like photo lithography using like light waves you engrave these into a silicon. And this is how a NAND gate multiple NAND gates look like actually manufactured. And yeah I had some prior experience myself. I was studying electronics and computer science. And so this was one of the radio frequency circuits I designed which just takes your signal like maybe your audio and basically modulates it. So it's on a higher frequency and then you can send it over the wire like a radio signal. And yeah so that was the basically one of one of how computers work. You have these logic gates you have these sequential gates and everything is made out of them. So now you know how those macros are all built and hopefully like if you found this useful please comment down so that I know for future videos whether this is interesting or not. Okay let's see some of the simplifications they are making to make this thing work and make it like computationally tractable because the problem is huge as you can imagine. Because of the like millions of standard cells and hundreds of macros. So first things first they group millions of standard cells into a few thousand clusters using this tool HMEDIS. So that way they basically make it easier for those force direct methods to do the placement like themselves. And second thing they do they discretize the grid so the chip canvas to a few thousand grid cells. Okay so that means they won't have obviously so you have your chip and it will be super super hard and probably wouldn't be any like meaningful to just make it continuous or to make it really like small resolution. So what I do is they kind of divide these into I think it was 128 by 128 cells so they have something like this and they can only place macros on a specific grid cell. So that's the second simplification they make. The third one is when calculating wire length we make the simplifying assumption that the wire starts from the standard cell blah blah blah that's not important. And finally to calculate the routing congestion cost we only consider the average congestion of the top 10% most congested grid cells. So again certain heuristic which makes it a bit more feasible to calculate this congestion which is used later on in the reward function. So this part the half perimeter wire length is something they use as a proxy as I mentioned for training the RL agent and it positively correlates as they show with area and other metrics of interest. So let me just explain you briefly how it works and the formula is pretty simple as you can see. So imagine you have a wire like this and this is your wire and basically what I do is they for this particular wire the this number will be equal to this thing here plus so that's called the height and this will be with. So that's the half perimeter right. So the perimeter would be two times that and you can see here so max over the basically x axis and minus mean over the x axis same thing for the y axis. And if you had something a bit more complex somewhere that goes like this maybe like this and finally ends up like this did again do the following. So they would find the max x value. So for this particular wire so that will be maybe this and they subtract this thing and they would do the same thing for why. So it's a kind of you find a bounding box and you find the half perimeter of the bounding box that's it and then they just kind of combine all of those across different wires. Okay. That's that that's that part. Okay. So certain heuristic additional heuristic and you can immediately see because and I forgot to mention that this work was actually used to design the newest TPUs in Google. So that's the version five if I'm not wrong. And so you can immediately see this is this is in production already. So there are lots of details but like the high level picture you already got it pretty much hopefully. And yeah let's see some additional details. So to select the order in which the macros are placed we sort macros by descending size and break ties using topological sort. So that's additional heuristic they use in order to make the action space smaller and to make this problem computationally tractable. So they just sort the macros so those blocks in your chip by size and then the policy will just take the next one and then learn how it just needs to decide where to place it. It doesn't need to learn which one to pick in each step. Okay. So I forgot to mention one detail here. Hopefully you already understood it but like if you have this policy and the output is hundred twenty eight by hundred twenty eight. So those are the grid cells I mentioned previously. And so it just outputs a distribution across all of the grid cells and where the distribution is where the probability is highest. So we just take ARGMAX that's where you're going to place the macro. So it would be really simple if but like additionally you need to mask certain areas. And so for example if you have your your your chip canvas and you've already placed the chip the macro here. So let's say that's this part and let's say that's this part. Then what will happen is they'll have this density this mask which will be used to kind of messed out certain like let's call them pixels basically to zero. So for example if if now the if the network if the policy network outputs I don't know maybe zero point zero two here and we already have that part occupied this mask will just zero it out to zero. And you'll just distribute the probability across the other valid cells. So that's that part. And yeah that's what I mentioned here. So basically to meet this constraint during each RL step we calculate the current density mask a binary M times N matrix that represents grid cells onto which we can place the center of the current node without violating the density threshold criteria. Before choosing an action from the policy network output we first take the dot product of the mask and the policy network output and then take the ARGMAX over feasible locations. So that's the process I just explained. So we also enable blockage aware placement such as clock straps by setting the density function of the blocked areas to one. So block it just means that basically you explicitly say hey I don't want to have anything placed around this macro for example or around this wire and you explicitly encode that into that mask and then you can't place macros on top of that location. Okay. That's just minor detail. Finally the loss function here is the wire length. I already explained the half perimeter wire length calculation. They have the congestion and the density constraint and they'll just include this density part while Lagrangian so you'll just have a weighted sum of congestion density and wire length. So as for the loss they are just summing over all of the net lists in the data set and they just want to maximize the expected cumulative reward. That was the reward part. Let's now jump into explaining the graph neural network. So our intuition was that a policy network architecture capable of transferring placement optimization across chips should be able to encode the state associated with a new unseen chip into a meaningful signal at inference time. We therefore propose training a neural network architecture capable of predicting reward on new net lists with the ultimate goal of using this architecture as the encoder layer of our policy network. So that was the part I explained here the encoder part and now they see here we therefore created a data set of 10,000 chip placements where the input is a state associated with a given placement and the label is a reward for that placement. So basically they used for example like those EDA tools and they found the ground truth reward and so they basically had a simple supervised regression task of on this with this graph neural network called the edge graph neural network. For the computation itself it's fairly simple. So let's say you have two components here. You have a macro here and it's connected to this macro here. You have a feature vector here and you have a feature vector here as well as here. OK. So what I do is the kind of so the process using a neural network feed like a simple fully connected layer. They process these vectors and then they just concatenate those and they place it again. They just feed it through in other in other fully connected layer. I'm not quite sure what this part means here because like he doesn't make any sense to concatenate the learnable weights with your with the output here. But yeah basically yeah you somehow combine them and then what you do to calculate the node feature is for example if you had multiple edges going into this node you just take all of those edge features. So you take this edge you take this edge and you just aggregate those and do a mean across those feature vectors. So the computation is pretty simple. Again check out my graph ML videos. This will be pretty self explanatory. OK. This is just your PPO objective function and I won't go to go into details there. Let's see the final results. So on the X axis we have different TPU blocks. So they have block one through four and this open source risk five CPU chip. And you can see here the placement cost. You want to have as low of a cost as possible. So using zero shot basically means that they don't fine tune that. So basically what I do is they take the whole system you saw with the policy network value network and graph graph neural network and they train it on maybe for example 20 20 different chips. And now they take that network and just apply it into a new chip like this TPU block one. And if they don't fine tune it on the block itself it's just zero shot. So as you can see zero shot is pretty decent and then if you fine tune it for two hours you get even better performance in 12 hours you get even better performance. But the point is if they train it from scratch so without that previous information from those other 20 chips. So it takes after 24 hours it still sucks pretty much. It's still much much worse than compared to this this one that's fine tuned for 12 hours. So this means it generalizes to new never before seen chips. So that's the benefit of a learning system. OK. Here what they show is again training from scratch versus fine tuning. As you can see basically only after a couple of hours the pre-trained one gets a really low loss whereas you need much more time to train. I mean this is pretty pretty obvious bottom line you want to pre train these are all agents and then later just fine tune them onto the new chip you're trying to place. OK. That's the whole point there. Here they compare. So I mentioned data sets. So I mentioned the largest one the one that has 20 blocks but they also train them on the medium one which is a subset of this one. And they also train it on the small one which is a subset of the medium one. So again you can see that going to more data gain gives you like lower placement costs. And looking at this curve here they are basically what you see here is the RL cost on an unseen chip. And you can see that with the big data set you get to overfitting much much slower and you get better performance than than basically using medium or smaller data sets. So it's both harder to overfit and you get you get lower costs. So again more data nothing new there but yeah these are the placements they get. So here you can see these purplish blocks are macros and here in the middle this like a blob of nothingness is a bunch of basically those standard cells. And here here is the zero shot placement and here is after you fine tune them you can see there is much less congestion congestion. You can see so basically these red and orange colors you know that there is a huge overlap across those layers and here it's much better place and you can also see much more regular structure here compared to the zero shot one. But this is still fairly fairly good for something that's that's working on a chip never before seen. Here are some results who here they blurred this because of the confidentiality. But again you can you can see the main thing is that humans when they when humans design chips you can see there is a lot of structure you can you can see some regular shapes here. Whereas this RL agent just outputs this blob and this donut shaped thing here it outperforms the human design on many different metrics and that's cool. And they mentioned here like the wire length and the congestion and you can see that it's both everything is lower using this RL agent approach. Okay. Last table and I think we're done here is this one. So they compare it with this replace method from 2019 is one of the state of the art placement methods and again looking at different metrics like timing area power wire length congestion. It outperforms replace which not only has lower performance it also like higher cost. It also many times just creates invalid placements because there was too many like either too many like the congestion was too big or there was some invalid placement was made. And so it's it's harder to to to to get it to work as a summary they mentioned here. So for example the process of standard cell partitioning row and column selection as well as selecting the order in which the macros are placed all can be further optimized. In addition we would also benefit from more optimized approach to standard cell placement. So what I see here is potential future work. The first thing first is that the heuristic I just mentioned was that they are using the biggest macro first and then the smaller one blah blah blah. So they argue that basically that process can also be learned and they can squeeze out more performance by doing that. The second thing is instead of using those force directed method that can also be kind of thrown into the RL framework approach. And yeah that's pretty much it. So great results super impactful work. So A.I. is building chips which make A.I. more powerful so we have a pretty pretty nice loop here and it will be exciting to see what else is there to come. So if you found this video useful subscribe share it out and until next time bye bye.
[{"start": 0.0, "end": 4.0, "text": " What's up? In this video I'm covering this paper called chip placement with deep reinforcement learning."}, {"start": 4.88, "end": 11.120000000000001, "text": " Basically, yesterday I saw this tweet from Anna Goldie where they've just published the nature version of this work"}, {"start": 11.36, "end": 14.72, "text": " and I thought covering it because it's a really interesting piece of work. It combines both"}, {"start": 15.200000000000001, "end": 19.12, "text": " like the electronics, which is something I have some background in as well as machine learning"}, {"start": 19.68, "end": 25.92, "text": " more concretely like reinforcement learning and graph ML. So it's exciting combination and super super impactful work."}, {"start": 25.92, "end": 30.720000000000002, "text": " So I thought covering it and basically what they achieved is they managed to train an RL agent"}, {"start": 31.28, "end": 34.88, "text": " combined with some graph ML for learning like nice representations"}, {"start": 35.28, "end": 40.0, "text": " in order to do displacement much faster than what previously was necessary."}, {"start": 40.0, "end": 45.84, "text": " So like they needed like humans usually need like multiple weeks to do this and now it's like less than six hours"}, {"start": 45.92, "end": 48.8, "text": " and it's achieving even superhuman performance looking just at the"}, {"start": 49.28, "end": 52.0, "text": " metrics like the area. So basically, yeah,"}, {"start": 52.0, "end": 59.92, "text": " we want to minimize the area because we can cram more transistors inside of it and more compute us and also they want to minimize"}, {"start": 60.8, "end": 63.84, "text": " other things like power consumption as well and"}, {"start": 64.16, "end": 70.16, "text": " under certain constraints like density congestion like you don't want to have too much too many wires overlapping on a single"}, {"start": 70.32, "end": 76.32, "text": " like on a certain piece of like on a certain surface of the chip. So that's a high level overview."}, {"start": 76.32, "end": 80.08, "text": " Now let me let's dig into the paper and yeah, see what they did."}, {"start": 80.08, "end": 83.28, "text": " So in this work we present a learning based"}, {"start": 84.64, "end": 89.52, "text": " a learning based approach to chip placement one of the most complex and time consuming"}, {"start": 90.16, "end": 97.68, "text": " stages of the chip design process. Unlike prior methods our approach has the ability to learn from past experience and improve over time."}, {"start": 98.24, "end": 101.03999999999999, "text": " So yeah, that's the main thing basically"}, {"start": 101.68, "end": 103.03999999999999, "text": " obviously"}, {"start": 103.03999999999999, "end": 105.28, "text": " like prior to this work there were many other approaches"}, {"start": 105.28, "end": 112.48, "text": " mainly some optimization based approaches like simulated annealing and some more like heuristics and yeah"}, {"start": 112.56, "end": 116.72, "text": " a bunch of different theory was developed, but none of those were actually deep learning algorithms."}, {"start": 117.52, "end": 123.04, "text": " And they say here our objective is to minimize the PPA. So as I mentioned so the power consumption the performance"}, {"start": 123.36, "end": 129.36, "text": " whereas they mean basically timing and we'll see what that exactly is like you basically want to make sure that certain"}, {"start": 129.76, "end": 131.36, "text": " like"}, {"start": 131.36, "end": 134.08, "text": " logic gates in your like flip-flops in your in your"}, {"start": 134.08, "end": 135.68, "text": " like circuit"}, {"start": 135.68, "end": 139.68, "text": " get certain signals on time. So there are these like timing"}, {"start": 140.48000000000002, "end": 143.68, "text": " constraints you have to obey and we'll see more details a bit later."}, {"start": 143.68, "end": 149.60000000000002, "text": " And obviously the area again like more transistors you can cram into the chip the more compute you get and that's better."}, {"start": 149.92000000000002, "end": 155.12, "text": " So and we showed that in under six hours our method can generate placements that are super human"}, {"start": 155.68, "end": 162.08, "text": " or comparable on modern accelerator netlists where netlist is just a fancy way of saying like a graph that basically"}, {"start": 162.08, "end": 165.84, "text": " tells you how each of the components on the chip are are connected together."}, {"start": 166.64000000000001, "end": 174.16000000000003, "text": " So whereas existing baselines require human experts in the loop and take several weeks. So that's the the main like the the main like"}, {"start": 175.44, "end": 181.60000000000002, "text": " point they're driving here. They automate this they make it even superhuman and they make it faster, which is huge."}, {"start": 182.72000000000003, "end": 190.72000000000003, "text": " And so why do we care about this? Like basically well they say it here the world is moving towards specialized hardware to meet AI's expectations"}, {"start": 190.72, "end": 193.6, "text": " and to meet AI's exponentially growing demand for compute."}, {"start": 193.84, "end": 200.56, "text": " However today today's chip take years to design leaving us with a speculative task of optimizing them for the machine learning models"}, {"start": 200.96, "end": 205.44, "text": " of two to five years from now. And the logic is pretty simple if you can cut down the time"}, {"start": 205.84, "end": 210.16, "text": " you need to to loop over different designs you can experiment much faster."}, {"start": 210.24, "end": 214.32, "text": " And it's the same thing as in deep learning where you want to make sure that your training"}, {"start": 214.88, "end": 219.76, "text": " length is like yeah shorter obviously like the same thing that happened with image net training for example"}, {"start": 219.76, "end": 225.51999999999998, "text": " there we needed like multiple weeks and then finally there was a paper like a couple of years ago where they've"}, {"start": 225.92, "end": 230.48, "text": " trained like image net like a vision model classifier in like half an hour or something."}, {"start": 231.12, "end": 237.92, "text": " It's probably even better today. So basically when you short those you can iterate much faster obviously and that's that's really really precious."}, {"start": 239.76, "end": 246.39999999999998, "text": " So one one nice example of these custom chips is maybe Tesla. That's the first thing that popped onto my mind. They have a"}, {"start": 246.4, "end": 252.56, "text": " customly designed computer vision chip set on their vehicles and it's not just computer vision."}, {"start": 252.56, "end": 258.56, "text": " They're also using like different sensors not just the RGB cameras. They're also using radars etc."}, {"start": 258.56, "end": 262.56, "text": " So the only thing they're not using and that's slider because Elon Musk as you probably know"}, {"start": 262.56, "end": 266.56, "text": " rants about those all the time and says that we only need to use RGB cameras."}, {"start": 267.36, "end": 274.56, "text": " But that's a topic for another for another video. Okay so the objective is to place a netlist"}, {"start": 274.56, "end": 282.56, "text": " graph of macros for example static RAM which is basically you probably know of DRAM. That's Dynamic Random Access Memory."}, {"start": 282.56, "end": 290.56, "text": " These are S-RAMs are usually non-volatile so they are even more expensive and they are they are more performant than DRAMs."}, {"start": 290.56, "end": 298.56, "text": " But they do take more area so that's a trade-off. Standard cells logic gates such as NANDs, NORs and XORs."}, {"start": 298.56, "end": 312.56, "text": " You probably heard of XOR if you did did anything related to cryptography. Onto a chip canvas such that power performance and area are optimized while adhering to constraints on placement density and routing congestion."}, {"start": 312.56, "end": 326.56, "text": " Yeah for the time being like you can just have an intuitive understanding of these and I guess you already have like basically you don't want to have multiple wires too many wires going over a certain cross section of the certain grid cell on your like canvas."}, {"start": 326.56, "end": 334.56, "text": " That's the high level overview. Now let's dig into the architecture. Let me show you the high level like pipeline how this looks like."}, {"start": 334.56, "end": 341.56, "text": " So basically what they do is the following. So they treat this they pose this as a reinforcement learning problem."}, {"start": 341.56, "end": 347.56, "text": " And as you can see here the state is modeled like you have this chip canvas so currently you don't have anything on it."}, {"start": 347.56, "end": 358.56, "text": " And basically as I already mentioned you can treat your chip as a hypergraph and that means the following. So let's assume I'll just draw macros as these squares."}, {"start": 358.56, "end": 364.56, "text": " So we'll have a couple of macros and macros can be as you saw like SRAM or it can be memory control or whatever."}, {"start": 364.56, "end": 369.56, "text": " So these are somehow connected like this and then you have these standard cells. I'll just denote them as circles."}, {"start": 369.56, "end": 378.56, "text": " And basically what was it's a hypergraph. So that means basically the single edge can connect to multiple nodes. That's the definition of the hypergraph."}, {"start": 378.56, "end": 390.56, "text": " And now so imagine you have a bunch of these you have hundreds of macros you have millions of standard cells and you want to somehow place them onto this fixed size chip canvas."}, {"start": 390.56, "end": 401.56, "text": " OK. And so what you do is you somehow and we'll see the details a bit later using this graph neural network you kind of embed this information about the connectivity."}, {"start": 401.56, "end": 411.56, "text": " And that will be your state. And then you're doing the following. So the agent takes that state and outputs an action and an action is just take a macro."}, {"start": 411.56, "end": 420.56, "text": " So we'll be just focusing on placing these macros as we'll soon see these will be handled by some forced direct method which is some heuristic that was previously devised."}, {"start": 420.56, "end": 435.56, "text": " So they're just kind of piggybacking on certain other methods to do that part. So they place the macro here and after that you get a new state and then you just output the new action where you place another macro onto the chip canvas."}, {"start": 435.56, "end": 444.56, "text": " And you do so until you've placed all of the macros as you can see here. And then from that point on you use this force directed method to place the standard cells."}, {"start": 444.56, "end": 452.56, "text": " So you will just take those cluster clusters of standard cells and will place them somehow onto your chip canvas. And finally you get the reward."}, {"start": 452.56, "end": 461.56, "text": " And as you can see immediately the problem is pretty hard because it's you get zero rewards all the way down and only at the end do you receive the actual reward."}, {"start": 461.56, "end": 468.56, "text": " So it means the credit assignment problem is going to be pretty tough. I mean the horizon is not that big. They won't have more than let's say thousand macros."}, {"start": 468.56, "end": 476.56, "text": " But like still it's a tough problem. And this reward as you can see let me just decrypt this for you. So this is a half perimeter wire length."}, {"start": 476.56, "end": 484.56, "text": " We'll see what that exactly is. But it's a roughly it kind of takes into account the length of wires you have in your chip."}, {"start": 484.56, "end": 491.56, "text": " And that kind of correlates positively with power consumption and with area and we'll see those a bit later."}, {"start": 491.56, "end": 496.56, "text": " OK. So that's a that's a high level overview. And I mentioned it here."}, {"start": 496.56, "end": 506.56, "text": " So our our true reward is the output of a commercial electronic design automation tool including wire length routing congestion density power timing in an area."}, {"start": 506.56, "end": 519.56, "text": " However RL policies require hundreds of thousands of examples to learn effectively as you already know. And so it is critical that the reward function be fast evaluated ideally running in a few milliseconds."}, {"start": 519.56, "end": 525.56, "text": " So in order to be effective these approximate reward functions must also be positively correlated with the true reward."}, {"start": 525.56, "end": 532.56, "text": " So the point the whole point is they can evaluate the real reward the true reward. But that's super slow."}, {"start": 532.56, "end": 542.56, "text": " So you have to use these EDA tools. And so they decided to just take something as a proxy which is fast to compute a and B positively correlates with the things they care about."}, {"start": 542.56, "end": 560.56, "text": " And we mentioned those already. So that's the PPA stuff. OK. So while we treat congestion as a soft constraint so lower congestion improves the reward function we treat density as a hard constraint masking out actions grid cells to place nodes onto whose density exceeds the target density."}, {"start": 560.56, "end": 569.56, "text": " So in order to understand this part we should go and see how the policy network looks like. Let me scroll down here. I'll skip some stuff and then I later return."}, {"start": 569.56, "end": 578.56, "text": " OK. So this is how the model looks like. And to end basically we have two portions here. The first part is the representation learning part."}, {"start": 578.56, "end": 584.56, "text": " So we have something called edge graph neural network some graph neural network data device specifically for this work."}, {"start": 584.56, "end": 592.56, "text": " And then we have your basic value net and basically policy network. So this is your actor critic RL agent."}, {"start": 592.56, "end": 600.56, "text": " They're using PPO that's proximal policy optimization algorithm published by opening a couple of years ago. So that part is pretty standard."}, {"start": 600.56, "end": 608.56, "text": " Now let's see. This part is pretty interesting and novel. So let's see how they manage to parse the netlist."}, {"start": 608.56, "end": 620.56, "text": " So the hyper graph of your components into something into some representation that contains valuable information that can be used to figure out where to place the next components."}, {"start": 620.56, "end": 628.56, "text": " So the way they train this whole pipeline is using supervised learning and the whole goal is to learn how to predict the reward."}, {"start": 628.56, "end": 634.56, "text": " So that's how they train this part. So they take this part in isolation and they trained the following way."}, {"start": 634.56, "end": 644.56, "text": " So again you have this hyper graph. So you have macros. You have some like standard cells. They are somehow connected. It's not that important."}, {"start": 644.56, "end": 653.56, "text": " OK like this and what to do as you can see here. So if you're familiar with graph ML if you're not I made a whole playlist and I'll link it somewhere here."}, {"start": 653.56, "end": 658.56, "text": " You should check it out. But like I'll try to explain it on a high level and basically it's pretty simple."}, {"start": 658.56, "end": 665.56, "text": " So every single node in your graph has a feature vector associated with it. So whoops let me delete that."}, {"start": 665.56, "end": 672.56, "text": " OK so you have a feature vector like this. You have a feature vector here. Every single node will have a feature vector associated with it."}, {"start": 672.56, "end": 680.56, "text": " The second thing is in this paper actually even the edges have feature vectors associated with them. So you have something like this."}, {"start": 680.56, "end": 690.56, "text": " So every edge and every node has a feature vector. So what I do is as you can see here the graph neural network takes in the connectivity information and all of those feature vectors."}, {"start": 690.56, "end": 697.56, "text": " And it kind of it somehow processes these. So what graph we'll see the exact equations here a bit later."}, {"start": 697.56, "end": 705.56, "text": " But like basically you just somehow combine those. You manipulate them using fully connected neural networks. You aggregate the neighbor the neighbors."}, {"start": 705.56, "end": 711.56, "text": " So for example this one will somehow take all of its neighbors. So this is the neighbor and this is the neighbor."}, {"start": 711.56, "end": 718.56, "text": " So we will take those feature vectors like this one and this one and it will somehow combine them with this one."}, {"start": 718.56, "end": 726.56, "text": " So it's a it's it's using this relational inductive bias of connectivity and it's accumulating those feature vectors to create a novel representation."}, {"start": 726.56, "end": 734.56, "text": " So this is going to be something maybe of a smaller dimension. Let's call it V prime. If this was vector V this is V prime."}, {"start": 734.56, "end": 742.56, "text": " And they are going to output that as the output of of of GNN. So as you can see here edge edge embeddings."}, {"start": 742.56, "end": 750.56, "text": " So that's a set that's that's a matrix that's of dimension E times basically D sub E."}, {"start": 750.56, "end": 756.56, "text": " So E is the number of edges in your graph and D sub E is just the like feature vector dimension."}, {"start": 756.56, "end": 766.56, "text": " So once you have the matrix what I do as you can see here they do this reduce mean operation. So they just take a mean over like element wise mean over all of these feature vectors."}, {"start": 766.56, "end": 776.56, "text": " And they get the single feature vector. That's the graph embedding. OK. That somehow roughly captures the dynamics the information about this graph."}, {"start": 776.56, "end": 782.56, "text": " And the second thing they do is they take the current macro ID. So there's the current macro you want to place into the chip canvas."}, {"start": 782.56, "end": 791.56, "text": " And they so again here you have a table that's N times D sub V. So N is the number of nodes."}, {"start": 791.56, "end": 796.56, "text": " This V is the dimension of your node feature vector. And they just take a single one."}, {"start": 796.56, "end": 806.56, "text": " So they just take a DV vector here. OK. And extract it. And finally they have some metadata information like the like the length of the wire on your chip etc."}, {"start": 806.56, "end": 813.56, "text": " So they have some metadata information and they concatenate all those they feed it through the fully connected layer. And that's it."}, {"start": 813.56, "end": 822.56, "text": " So now as I already told you they're going to train this thing to to kind of understand to predict the reward of the of the placement."}, {"start": 822.56, "end": 827.56, "text": " And I'll get into details a bit later. But that's that's that's it in a nutshell."}, {"start": 827.56, "end": 840.56, "text": " So once you train that you use your presentations it learned to basically as a Kickstarter for these policy and value networks and they are trained as I said using PPO."}, {"start": 840.56, "end": 847.56, "text": " So that's it. And now I'm going to slowly start digging into the details and later we'll see the experiments and the results they got."}, {"start": 847.56, "end": 860.56, "text": " OK. Before I do that I think it will be quite useful for you to maybe understand a little bit about some electronics one on one and you'll hopefully have an epiphany moment."}, {"start": 860.56, "end": 866.56, "text": " OK. So as software the same thing goes with hardware. Basically you have a bunch of abstraction layers."}, {"start": 866.56, "end": 873.56, "text": " So in software we have like on the lower lowest layer you have firmware you have something like what called hardware abstraction layer."}, {"start": 873.56, "end": 884.56, "text": " You have drivers and you have operating systems and you have compilers and you have all of those systems that translate the higher level languages into like something that your computer can parse and understand."}, {"start": 884.56, "end": 890.56, "text": " And finally you have the application layer. So obviously a bunch of abstractions and the same thing goes for hardware."}, {"start": 890.56, "end": 908.56, "text": " So you have like you have on a really high level you have like you have a CPU and you have maybe like the direct memory controller. So that's just a device that can do whom CPU can just delegate basically certain memory intensive operations."}, {"start": 908.56, "end": 917.56, "text": " And then you have memory like you have a memory block here and let's say both are connected to memory both the CPU and the M are connected to memory."}, {"start": 917.56, "end": 924.56, "text": " So if you zoom in into any of these components like take maybe direct memory controller you'll end up with two types of circuits."}, {"start": 924.56, "end": 932.56, "text": " So basically you have combination logic and you have these circuits which are called sequential logic which contain the memory in the system."}, {"start": 932.56, "end": 937.56, "text": " So they are stateful. So if you take a look at this one. So what's the main difference. The main difference is the following."}, {"start": 937.56, "end": 945.56, "text": " If you have this record this is called inverter. Basically if you feed it zero it will output one and if you feed it one it will output the logic value of zero."}, {"start": 945.56, "end": 953.56, "text": " And the thing is if the thing is with these combination logic gates is that as soon as you change the input."}, {"start": 953.56, "end": 961.56, "text": " So if you go from zero to one the output will go from one to zero really quick like maybe in 20 picoseconds or something."}, {"start": 961.56, "end": 967.56, "text": " Now the trick with these flip flops with these memory circuits is so this is a deep flip flop."}, {"start": 967.56, "end": 975.56, "text": " It's a simple one of the simplest flip flops out there. So basically what happens here you can change this as much as you want like from zero to one."}, {"start": 975.56, "end": 984.56, "text": " Nothing will change here is going to keep one here until you have the clock. So the uptick of the clock or the down tick of the clock."}, {"start": 984.56, "end": 988.56, "text": " And basically so hopefully you know what like a clock signal is. It's something that drives your computer."}, {"start": 988.56, "end": 998.56, "text": " It's a basically digital signal that goes from zero to one with a certain frequency and on each of these upticks or downticks something is going to happen."}, {"start": 998.56, "end": 1004.56, "text": " So on each tick the sequential logic gates so these these gates like flip flops will change their state."}, {"start": 1004.56, "end": 1011.56, "text": " So if you keep one here and then the uptick comes at that point the one will propagate here on the net."}, {"start": 1011.56, "end": 1018.56, "text": " And if you change it now to zero and the down tick comes for example then this will go to zero."}, {"start": 1018.56, "end": 1022.56, "text": " So these are keeping that they have the memory. That's that's that's that's the main trick."}, {"start": 1022.56, "end": 1029.56, "text": " So having said that let me go even even deeper. So let's take one specific gate like NAND."}, {"start": 1029.56, "end": 1036.56, "text": " And what NAND does is the following. Yeah you've seen these if you've ever done any programming so you know about the NAND operator."}, {"start": 1036.56, "end": 1041.56, "text": " This is how you write it down in Python. And basically this is the opposite of an AND gate."}, {"start": 1041.56, "end": 1051.56, "text": " So you just are not AND. And basically as you can see here looking at the table you know that AND gates give you one only when you have one and one as the input."}, {"start": 1051.56, "end": 1058.56, "text": " And all of the other values will be zero. And NAND is just the opposite of that. As you can see it's inverted AND gate."}, {"start": 1058.56, "end": 1074.56, "text": " And now this is the like abstracted view of this gate. And if you dig a bit deeper and take a certain implementation which is called CMOS implementation of the NAND gate which is basically complementary metal oxide semiconductor doesn't matter."}, {"start": 1074.56, "end": 1079.56, "text": " But basically there are different ways you can implement these abstract logic gates."}, {"start": 1079.56, "end": 1091.56, "text": " The same thing as you can do with if you have like an image classifier you can implement it using a neural network using SVM using I don't know like even like k-nearest neighbors whatever your favorite classifier is."}, {"start": 1091.56, "end": 1096.56, "text": " The same thing goes here. You have a bunch of different ways how you can implement the very same thing and that is the NAND gate."}, {"start": 1096.56, "end": 1102.56, "text": " So here we have a specific logic you can use TTL. There are many different logics you can implement."}, {"start": 1102.56, "end": 1112.56, "text": " Now let me show you why this works. So basically let's take as an input one and one. And when I say one you again have to implement one somehow on your system."}, {"start": 1112.56, "end": 1120.56, "text": " So let's say for example that we have a voltage supply that's maybe I don't know like 0.9 volts."}, {"start": 1120.56, "end": 1130.56, "text": " And so on this system one will be defined as something close to 0.9 volts and zero will be defined as something close to zero volts."}, {"start": 1130.56, "end": 1138.56, "text": " So that's how you implement zero and that's how you implement one. And so if I feed once here for example and so that's 0.9 volts."}, {"start": 1138.56, "end": 1144.56, "text": " And if you feed one here as well and as you can see this small circle again that means it's inverted."}, {"start": 1144.56, "end": 1154.56, "text": " So we'll be adding zero onto this gate and zero onto this gate. And what happens is because you brought a huge voltage here you're going to toggle on this transistor."}, {"start": 1154.56, "end": 1160.56, "text": " And so the current will start to flow here and here and you're going to block these two because you brought zero voltage here."}, {"start": 1160.56, "end": 1166.56, "text": " And so as you can see you're basically making a direct connection to the output to this thing here."}, {"start": 1166.56, "end": 1172.56, "text": " And let's say this is ground so it's zero volts and basically that means your output is zero volts which is zero."}, {"start": 1172.56, "end": 1176.56, "text": " And let's see so one one you get zero. The same thing goes for zero zero."}, {"start": 1176.56, "end": 1185.56, "text": " So if you have if you have if you bring zero zero you're going to basically turn off these two and you're going to turn on these two."}, {"start": 1185.56, "end": 1193.56, "text": " And so you're basically bringing the voltage supply directly to the output which is 0.9 volts which basically translates into logic one."}, {"start": 1193.56, "end": 1198.56, "text": " And yeah so that's that's how it works. That's how your computer computers basically work."}, {"start": 1198.56, "end": 1206.56, "text": " And going even deeper like people have to design these and you can see here so this is how you basically place these metal wires."}, {"start": 1206.56, "end": 1211.56, "text": " And this is how you implement a NAND gate. And finally you have the last step and that's the production."}, {"start": 1211.56, "end": 1219.56, "text": " You actually do some like photo lithography using like light waves you engrave these into a silicon."}, {"start": 1219.56, "end": 1225.56, "text": " And this is how a NAND gate multiple NAND gates look like actually manufactured."}, {"start": 1225.56, "end": 1231.56, "text": " And yeah I had some prior experience myself. I was studying electronics and computer science."}, {"start": 1231.56, "end": 1239.56, "text": " And so this was one of the radio frequency circuits I designed which just takes your signal like maybe your audio and basically modulates it."}, {"start": 1239.56, "end": 1243.56, "text": " So it's on a higher frequency and then you can send it over the wire like a radio signal."}, {"start": 1243.56, "end": 1249.56, "text": " And yeah so that was the basically one of one of how computers work."}, {"start": 1249.56, "end": 1253.56, "text": " You have these logic gates you have these sequential gates and everything is made out of them."}, {"start": 1253.56, "end": 1263.56, "text": " So now you know how those macros are all built and hopefully like if you found this useful please comment down so that I know for future videos whether this is interesting or not."}, {"start": 1263.56, "end": 1272.56, "text": " Okay let's see some of the simplifications they are making to make this thing work and make it like computationally tractable because the problem is huge as you can imagine."}, {"start": 1272.56, "end": 1277.56, "text": " Because of the like millions of standard cells and hundreds of macros."}, {"start": 1277.56, "end": 1284.56, "text": " So first things first they group millions of standard cells into a few thousand clusters using this tool HMEDIS."}, {"start": 1284.56, "end": 1292.56, "text": " So that way they basically make it easier for those force direct methods to do the placement like themselves."}, {"start": 1292.56, "end": 1298.56, "text": " And second thing they do they discretize the grid so the chip canvas to a few thousand grid cells."}, {"start": 1298.56, "end": 1313.56, "text": " Okay so that means they won't have obviously so you have your chip and it will be super super hard and probably wouldn't be any like meaningful to just make it continuous or to make it really like small resolution."}, {"start": 1313.56, "end": 1326.56, "text": " So what I do is they kind of divide these into I think it was 128 by 128 cells so they have something like this and they can only place macros on a specific grid cell."}, {"start": 1326.56, "end": 1336.56, "text": " So that's the second simplification they make. The third one is when calculating wire length we make the simplifying assumption that the wire starts from the standard cell blah blah blah that's not important."}, {"start": 1336.56, "end": 1343.56, "text": " And finally to calculate the routing congestion cost we only consider the average congestion of the top 10% most congested grid cells."}, {"start": 1343.56, "end": 1351.56, "text": " So again certain heuristic which makes it a bit more feasible to calculate this congestion which is used later on in the reward function."}, {"start": 1351.56, "end": 1365.56, "text": " So this part the half perimeter wire length is something they use as a proxy as I mentioned for training the RL agent and it positively correlates as they show with area and other metrics of interest."}, {"start": 1365.56, "end": 1369.56, "text": " So let me just explain you briefly how it works and the formula is pretty simple as you can see."}, {"start": 1369.56, "end": 1385.56, "text": " So imagine you have a wire like this and this is your wire and basically what I do is they for this particular wire the this number will be equal to this thing here plus so that's called the height and this will be with."}, {"start": 1385.56, "end": 1397.56, "text": " So that's the half perimeter right. So the perimeter would be two times that and you can see here so max over the basically x axis and minus mean over the x axis same thing for the y axis."}, {"start": 1397.56, "end": 1408.56, "text": " And if you had something a bit more complex somewhere that goes like this maybe like this and finally ends up like this did again do the following."}, {"start": 1408.56, "end": 1414.56, "text": " So they would find the max x value."}, {"start": 1414.56, "end": 1422.56, "text": " So for this particular wire so that will be maybe this and they subtract this thing and they would do the same thing for why."}, {"start": 1422.56, "end": 1433.56, "text": " So it's a kind of you find a bounding box and you find the half perimeter of the bounding box that's it and then they just kind of combine all of those across different wires."}, {"start": 1433.56, "end": 1436.56, "text": " Okay. That's that that's that part. Okay."}, {"start": 1436.56, "end": 1449.56, "text": " So certain heuristic additional heuristic and you can immediately see because and I forgot to mention that this work was actually used to design the newest TPUs in Google."}, {"start": 1449.56, "end": 1455.56, "text": " So that's the version five if I'm not wrong. And so you can immediately see this is this is in production already."}, {"start": 1455.56, "end": 1460.56, "text": " So there are lots of details but like the high level picture you already got it pretty much hopefully."}, {"start": 1460.56, "end": 1470.56, "text": " And yeah let's see some additional details. So to select the order in which the macros are placed we sort macros by descending size and break ties using topological sort."}, {"start": 1470.56, "end": 1478.56, "text": " So that's additional heuristic they use in order to make the action space smaller and to make this problem computationally tractable."}, {"start": 1478.56, "end": 1491.56, "text": " So they just sort the macros so those blocks in your chip by size and then the policy will just take the next one and then learn how it just needs to decide where to place it."}, {"start": 1491.56, "end": 1494.56, "text": " It doesn't need to learn which one to pick in each step."}, {"start": 1494.56, "end": 1498.56, "text": " Okay. So I forgot to mention one detail here."}, {"start": 1498.56, "end": 1504.56, "text": " Hopefully you already understood it but like if you have this policy and the output is hundred twenty eight by hundred twenty eight."}, {"start": 1504.56, "end": 1513.56, "text": " So those are the grid cells I mentioned previously. And so it just outputs a distribution across all of the grid cells and where the distribution is where the probability is highest."}, {"start": 1513.56, "end": 1517.56, "text": " So we just take ARGMAX that's where you're going to place the macro."}, {"start": 1517.56, "end": 1523.56, "text": " So it would be really simple if but like additionally you need to mask certain areas."}, {"start": 1523.56, "end": 1530.56, "text": " And so for example if you have your your your chip canvas and you've already placed the chip the macro here."}, {"start": 1530.56, "end": 1546.56, "text": " So let's say that's this part and let's say that's this part. Then what will happen is they'll have this density this mask which will be used to kind of messed out certain like let's call them pixels basically to zero."}, {"start": 1546.56, "end": 1562.56, "text": " So for example if if now the if the network if the policy network outputs I don't know maybe zero point zero two here and we already have that part occupied this mask will just zero it out to zero."}, {"start": 1562.56, "end": 1568.56, "text": " And you'll just distribute the probability across the other valid cells."}, {"start": 1568.56, "end": 1571.56, "text": " So that's that part. And yeah that's what I mentioned here."}, {"start": 1571.56, "end": 1586.56, "text": " So basically to meet this constraint during each RL step we calculate the current density mask a binary M times N matrix that represents grid cells onto which we can place the center of the current node without violating the density threshold criteria."}, {"start": 1586.56, "end": 1596.56, "text": " Before choosing an action from the policy network output we first take the dot product of the mask and the policy network output and then take the ARGMAX over feasible locations."}, {"start": 1596.56, "end": 1604.56, "text": " So that's the process I just explained. So we also enable blockage aware placement such as clock straps by setting the density function of the blocked areas to one."}, {"start": 1604.56, "end": 1619.56, "text": " So block it just means that basically you explicitly say hey I don't want to have anything placed around this macro for example or around this wire and you explicitly encode that into that mask and then you can't place macros on top of that location."}, {"start": 1619.56, "end": 1628.56, "text": " Okay. That's just minor detail. Finally the loss function here is the wire length. I already explained the half perimeter wire length calculation."}, {"start": 1628.56, "end": 1639.56, "text": " They have the congestion and the density constraint and they'll just include this density part while Lagrangian so you'll just have a weighted sum of congestion density and wire length."}, {"start": 1639.56, "end": 1650.56, "text": " So as for the loss they are just summing over all of the net lists in the data set and they just want to maximize the expected cumulative reward. That was the reward part."}, {"start": 1650.56, "end": 1666.56, "text": " Let's now jump into explaining the graph neural network. So our intuition was that a policy network architecture capable of transferring placement optimization across chips should be able to encode the state associated with a new unseen chip into a meaningful signal at inference time."}, {"start": 1666.56, "end": 1676.56, "text": " We therefore propose training a neural network architecture capable of predicting reward on new net lists with the ultimate goal of using this architecture as the encoder layer of our policy network."}, {"start": 1676.56, "end": 1689.56, "text": " So that was the part I explained here the encoder part and now they see here we therefore created a data set of 10,000 chip placements where the input is a state associated with a given placement and the label is a reward for that placement."}, {"start": 1689.56, "end": 1706.56, "text": " So basically they used for example like those EDA tools and they found the ground truth reward and so they basically had a simple supervised regression task of on this with this graph neural network called the edge graph neural network."}, {"start": 1706.56, "end": 1722.56, "text": " For the computation itself it's fairly simple. So let's say you have two components here. You have a macro here and it's connected to this macro here. You have a feature vector here and you have a feature vector here as well as here."}, {"start": 1722.56, "end": 1740.56, "text": " OK. So what I do is the kind of so the process using a neural network feed like a simple fully connected layer. They process these vectors and then they just concatenate those and they place it again."}, {"start": 1740.56, "end": 1753.56, "text": " They just feed it through in other in other fully connected layer. I'm not quite sure what this part means here because like he doesn't make any sense to concatenate the learnable weights with your with the output here."}, {"start": 1753.56, "end": 1767.56, "text": " But yeah basically yeah you somehow combine them and then what you do to calculate the node feature is for example if you had multiple edges going into this node you just take all of those edge features."}, {"start": 1767.56, "end": 1776.56, "text": " So you take this edge you take this edge and you just aggregate those and do a mean across those feature vectors. So the computation is pretty simple."}, {"start": 1776.56, "end": 1789.56, "text": " Again check out my graph ML videos. This will be pretty self explanatory. OK. This is just your PPO objective function and I won't go to go into details there."}, {"start": 1789.56, "end": 1801.56, "text": " Let's see the final results. So on the X axis we have different TPU blocks. So they have block one through four and this open source risk five CPU chip."}, {"start": 1801.56, "end": 1813.56, "text": " And you can see here the placement cost. You want to have as low of a cost as possible. So using zero shot basically means that they don't fine tune that."}, {"start": 1813.56, "end": 1825.56, "text": " So basically what I do is they take the whole system you saw with the policy network value network and graph graph neural network and they train it on maybe for example 20 20 different chips."}, {"start": 1825.56, "end": 1836.56, "text": " And now they take that network and just apply it into a new chip like this TPU block one. And if they don't fine tune it on the block itself it's just zero shot."}, {"start": 1836.56, "end": 1846.56, "text": " So as you can see zero shot is pretty decent and then if you fine tune it for two hours you get even better performance in 12 hours you get even better performance."}, {"start": 1846.56, "end": 1857.56, "text": " But the point is if they train it from scratch so without that previous information from those other 20 chips. So it takes after 24 hours it still sucks pretty much."}, {"start": 1857.56, "end": 1867.56, "text": " It's still much much worse than compared to this this one that's fine tuned for 12 hours. So this means it generalizes to new never before seen chips."}, {"start": 1867.56, "end": 1874.56, "text": " So that's the benefit of a learning system. OK. Here what they show is again training from scratch versus fine tuning."}, {"start": 1874.56, "end": 1885.56, "text": " As you can see basically only after a couple of hours the pre-trained one gets a really low loss whereas you need much more time to train."}, {"start": 1885.56, "end": 1894.56, "text": " I mean this is pretty pretty obvious bottom line you want to pre train these are all agents and then later just fine tune them onto the new chip you're trying to place."}, {"start": 1894.56, "end": 1906.56, "text": " OK. That's the whole point there. Here they compare. So I mentioned data sets. So I mentioned the largest one the one that has 20 blocks but they also train them on the medium one which is a subset of this one."}, {"start": 1906.56, "end": 1918.56, "text": " And they also train it on the small one which is a subset of the medium one. So again you can see that going to more data gain gives you like lower placement costs."}, {"start": 1918.56, "end": 1926.56, "text": " And looking at this curve here they are basically what you see here is the RL cost on an unseen chip."}, {"start": 1926.56, "end": 1937.56, "text": " And you can see that with the big data set you get to overfitting much much slower and you get better performance than than basically using medium or smaller data sets."}, {"start": 1937.56, "end": 1948.56, "text": " So it's both harder to overfit and you get you get lower costs. So again more data nothing new there but yeah these are the placements they get."}, {"start": 1948.56, "end": 1961.56, "text": " So here you can see these purplish blocks are macros and here in the middle this like a blob of nothingness is a bunch of basically those standard cells."}, {"start": 1961.56, "end": 1967.56, "text": " And here here is the zero shot placement and here is after you fine tune them you can see there is much less congestion congestion."}, {"start": 1967.56, "end": 1983.56, "text": " You can see so basically these red and orange colors you know that there is a huge overlap across those layers and here it's much better place and you can also see much more regular structure here compared to the zero shot one."}, {"start": 1983.56, "end": 1991.56, "text": " But this is still fairly fairly good for something that's that's working on a chip never before seen."}, {"start": 1991.56, "end": 2005.56, "text": " Here are some results who here they blurred this because of the confidentiality. But again you can you can see the main thing is that humans when they when humans design chips you can see there is a lot of structure you can you can see some regular shapes here."}, {"start": 2005.56, "end": 2015.56, "text": " Whereas this RL agent just outputs this blob and this donut shaped thing here it outperforms the human design on many different metrics and that's cool."}, {"start": 2015.56, "end": 2024.56, "text": " And they mentioned here like the wire length and the congestion and you can see that it's both everything is lower using this RL agent approach."}, {"start": 2024.56, "end": 2025.56, "text": " Okay."}, {"start": 2025.56, "end": 2041.56, "text": " Last table and I think we're done here is this one. So they compare it with this replace method from 2019 is one of the state of the art placement methods and again looking at different metrics like timing area power wire length congestion."}, {"start": 2041.56, "end": 2047.56, "text": " It outperforms replace which not only has lower performance it also like higher cost."}, {"start": 2047.56, "end": 2060.56, "text": " It also many times just creates invalid placements because there was too many like either too many like the congestion was too big or there was some invalid placement was made."}, {"start": 2060.56, "end": 2066.56, "text": " And so it's it's harder to to to to get it to work as a summary they mentioned here."}, {"start": 2066.56, "end": 2076.56, "text": " So for example the process of standard cell partitioning row and column selection as well as selecting the order in which the macros are placed all can be further optimized."}, {"start": 2076.56, "end": 2080.56, "text": " In addition we would also benefit from more optimized approach to standard cell placement."}, {"start": 2080.56, "end": 2082.56, "text": " So what I see here is potential future work."}, {"start": 2082.56, "end": 2090.56, "text": " The first thing first is that the heuristic I just mentioned was that they are using the biggest macro first and then the smaller one blah blah blah."}, {"start": 2090.56, "end": 2098.56, "text": " So they argue that basically that process can also be learned and they can squeeze out more performance by doing that."}, {"start": 2098.56, "end": 2105.56, "text": " The second thing is instead of using those force directed method that can also be kind of thrown into the RL framework approach."}, {"start": 2105.56, "end": 2108.56, "text": " And yeah that's pretty much it."}, {"start": 2108.56, "end": 2112.56, "text": " So great results super impactful work."}, {"start": 2112.56, "end": 2122.56, "text": " So A.I. is building chips which make A.I. more powerful so we have a pretty pretty nice loop here and it will be exciting to see what else is there to come."}, {"start": 2122.56, "end": 2142.56, "text": " So if you found this video useful subscribe share it out and until next time bye bye."}]