Chip Placement with Deep Reinforcement Learning (Paper Explained)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper reinforcement learning deep reinforcement learning gans gan deconvolution computer chip gpu tpu fpga netlist constrained google
The AI Singularity is here! Computers designing new computers! It takes human experts multiple weeks to design new computer chips. What looks like a large game of Tetris is actually a very complex optimization problem. This paper uses Deep Reinforcement Learning to solve this optimization both faster and better than humans.

https://arxiv.org/abs/2004.10746

Abstract:
In this work, we present 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. In particular, as we train over a greater number of chip blocks, our method becomes better at rapidly generating optimized placements for previously unseen chip blocks. To achieve these results, we pose placement as a Reinforcement Learning (RL) problem and train an agent to place the nodes of a chip netlist onto a chip canvas. To enable our RL policy to generalize to unseen blocks, we ground representation learning in the supervised task of predicting placement quality. By designing a neural architecture that can accurately predict reward across a wide variety of netlists and their placements, we are able to generate rich feature embeddings of the input netlists. We then use this architecture as the encoder of our policy and value networks to enable transfer learning. Our objective is to minimize PPA (power, performance, and area), and we show that, in under 6 hours, our method can generate placements that are superhuman or comparable on modern accelerator netlists, whereas existing baselines require human experts in the loop and take several weeks.

Authors: Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Sungmin Bae, Azade Nazi, Jiwoo Pak, Andy Tong, Kavya Srinivasa, William Hang, Emre Tuncer, Anand Babu, Quoc V. Le, James Laudon, Richard Ho, Roger Carpenter, Jeff Dean

Links:
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
BitChute: https://www.bitchute.com/channel/yannic-kilcher
Minds: https://www.minds.com/ykilcher
 Hi there! Today we're looking at Chip Placement with Deep Reinforcement Learning by Azalia Miroszajny, Anna Goldi and a long list of authors that I have no stamina to read down. I'm sorry. So this work is a cool application of reinforcement learning to the real world. And we're gonna go through it and the cool thing about it is it pulls together parts from so many different areas of machine learning and also here chip engineering. So what's the fundamental problem? The fundamental problem of chip design is this. You have a canvas, an empty chip and you want to build a computer chip. Now what you have given is a so-called netlist. So your netlist is any parts that you want on that computer chip and their shape or their size. So you can imagine this like a bit of a Tetris game. So here's this netlist. There's this part and then this part and then there's maybe this part and also this part. Many many parts. Now these as I understand it can be thousands of parts but you can sort of group them together but still there are a lot of these parts. And the netlist also contains information about how they're connected. So for each of these parts you would have a list of which other ones of these parts they must be connected to. So maybe it says okay this part here needs to be connected to those three parts and for each of those you'd also have like a list of how they must be connected. You can represent this as an adjacency matrix right? But ultimately this is a graph of these nodes. Now your goal is to place those things on this board. So for example we're gonna place this right here and we're gonna place the second one maybe here and the third one maybe here. So you can imagine if this is a CPU maybe look I have no clue of chip design but I imagine it like this. This is your clock that you need on there. This is your NAND gates right? NAND gates pretty important for a CPU and this is your floating point unit also pretty important and so on. So I need to place these things and then you need to connect them using these using wires. Now wires are of course etched into the board but you need to connect them according to the maybe there is a component right here. According to the netlist right they need to be connected like that. Maybe the algorithm that came up with the chip told you they need to be connected like this and if you lay them out like this you can draw the wires. So this is your finished you you want to go from the thing on the right to the thing on the left and your goal here in order to get the fastest possible computer chip is three things. First of all you want first of all the density is important. By density it basically just means you can't place stuff on top of other stuff so you could not place a block right here. Not possible because the clock is already there. So that's first thing you can't place stuff on top of other stuff. Then the second thing is the wires and specifically the length of the wires. So you see for example this thing here is a pretty short wire that means the signal travels fast. This thing here is a long wire so the signal travels more slowly. Now the lower sorry the the faster you want your signal to go that means you have to make your wires as short as possible. So you want to keep the total amount of wire length as short as possible. Then third is what's called congestion. So congestion is when for example okay I actually don't know what it is but maybe it is when two wires cross like somewhere here there might be congestion or maybe some parts actually share their wires. I can imagine sorry I'm gonna draw this again I can imagine maybe there's a part here that wants to go up and then it maybe shares sorry shares this part of the wire here with the other one and so there's congestion like it's roads or something. In any case you can measure congestion it's a bad thing and you want to lay out your components basically in order to minimize congestion and also minimize the length of the wires and not have them on top of one another. Easy enough right? It takes human experts and combined with state-of-the-art algorithms multiple weeks to design chips like this and that's the fundamental problem and this paper takes reinforcement learning in order to solve this problem in a few hours. So how does it do this? The reinforcement learning is basically a sequential measure method so you want to do one action at a time. So you start off with what they call the chip canvas which is just empty. This is your state and then the agent here it gets to decide where to place the next thing. Now how do you decide what the next thing is? I believe they simply go by size so they take the largest component first of the netlist first and they just go down the netlist like this. So you tell the agent hey agent I want you to place this this thing here I want you to place this next and the agent will tell you I will place it right here and then again you tell the agent agent I have this this thing here where do you want to place it and along with sorry along with all the connections right along with everything that it needs to be connected to and also the entire list so the agent must also think of what what is to come yet what it hasn't placed yet. So it everything goes into this decision and it tells you okay I want to place this here and then at the end you end up with this filled board. Now this isn't actually the end. After you have placed all your things there is another method coming in this is called this force directed method placing yet more things so what you actually place with this agent is only the things called macros. I have no idea what those are or how these are different from these standard cells but apparently you must use a force directed method which you can think of just just an algorithm you run to place the standard cells and these are these these gray blobs here and at the end of all of this you can finally evaluate how good your design is. So at the end of all your of this you get a reward that is a mixture of wire length and congestion. Now this is actually an approximation to wire length and this is an approximation to congestion that they use because they need to evaluate it quickly but in essentially it's highly correlated with wire length and congestion so the negative of that is going to be your reward. So in terms of a reinforcement learning problem this is pretty nasty right because as you can see here you get basically a reward of zero for every step until the very end you get your true reward and it is actually worse than that because so from here to here your agent gets to perform actions right this is action time but usually when you have these sparse reward tasks you'll get your reward at the end of that action time but not here at the end of the action time there is an algorithm over which the agent basically has no control that comes in and does a bunch of things this force directed method and only then do you get your reward right so the agent must purposefully sort of leave room here for what this algorithm is going to do so it needs to learn that as well this is a as far as reinforcement learning goes this is a pretty good reinforcement learning problem right so now we have an environment which is the canvas here and also this you can you can consider this force directed method to be part of the environment and of course the reward giver and you have also the netlist as part of the environment and you have the agent that can do actions now we have to go into how does the agent perform actions on this so by the way maybe a bit confusing because it was a bit confusing for me for a given reinforcement learning problem we'll just start out by saying that the netlist is always the same right if you might be coming from a deep learning framework where you're used to many many different training samples in this case basically the netlist the goal is always the same you can think of it like a reinforcement learning agent for the game of chess where it's always the same chess game that you're trying to optimize this is the difference to let's say supervised learning if you have a label in supervised learning if you know the solution to a particular data point you're happy right you that data point is no longer interesting you want to generalize here even though they generalize later here you can give it a single problem right and it will already a solution to that problem will be valuable because it can be a better solution that humanity has come up with until this point so always think that we're now just working on one single netlist one problem to optimally place this netlist and an episode is simply to place these things until here and then you get a reward and then you go back to the beginning and just do it all over again but just try to do better and then you go back to the beginning and you do it all over again the same problem right okay so how does this work by the way that the paper has great technical detail on chip engineering and how the reward function exactly works and so on I have not the expertise to go into this with you beyond what I just described alright so here is how the model looks from a deep RL perspective now there's two parts to this model you can divide it about here so on the right you would have what is your policy and value networks and on the left the feature embeddings so in reinforcement learning and we won't go much into reinforcement learning now but what you need are basically a way to encode the state this is the encoder so all the information of the observation they might be in different modalities and so on you need to encode this into but in for simplicity let's say a single vector that's thing that this thing here this is the state encoding and then you can employ a policy and a value network in order to do reinforcement learning so the side on the right this comes from standard RL you have a policy network and a value network and they do I believe PPO with it this is a standard reinforcement learning architecture it's an actor critic architecture so the value net is simply telling you what's the value of the state that you're in now given that you have a state embedding it simply takes a fully connected layer to transform this into a single float that is the value network the policy is a bit different because usually in reinforcement learning you just have a list of actions right you just say I have these 16 buttons on my controller you compress them here we if you run if you look at this chip from above we have a question where do you want to place the next thing so in order to do that we take this embedding of the state and they run it through a series of D convolutions and the D convolutions they have the ability to basically up sample an image so you see here you transform this vector into a 4 by 4 by 32 tensor and that gets D convolved into more and more though less and less channels but more and more height and width images so it kind of from a vector it produces an image right here you might recognize this from a lot of generator architectures for when you make GANs for images have exactly this D convolution architecture so as I said pretty cool it pulls in kind of architectures and methods from different fields we already have reinforcement learning now we have generators for images now so you come up with an image and basically this image if you can imagine this from above is discretized so you can place the thing you have to place pretty much every single nanometer but they discretize this into a grid and for each point in the grid the network outputs a number so the number maybe nine here three four and so on eight right here so for each of these they it outputs a number where it would or how much it would like to place the next thing at this particular location so this is a distribution over locations so the first thing you have to do is you have to mask out where there are already things we said the first condition is things cannot be on top of other things so maybe you already have placed something here so you ignore those numbers and you have already placed something here so you ignore those numbers as well this is this masking operation right here and then you simply look at where is your highest number and maybe there's maybe there's an 11 down here somewhere say ah this is my highest number okay cool and you look at what you need to place maybe the thing you need to place looks like this and you say all right I will place maybe the 11 marks the top left corner I will place it right here okay and then you do the same thing again for the next piece so the next piece you would simply also mark this to be blue so you can't place here you evaluate your network again of course you'll have a new shape something like this and then you ask the network where would you like to place this and you do this step by step by step until the entire netlist is empty so this is how we do the reinforcement learning this is how we decide on an action but how do we actually put the state into this encoding now this pulls in yet another framework from another field of deep learning namely graph convolutional neural networks so since the netlist is a graph right the netlist is again if you have your wow this is slow today if you have your netlist right here with the part right the shape or size whatever and the list of things it needs to be connected to then this forms naturally a graph so you can transform this into a graph with the things that need to be connected connected by an edge and they run a graph convolutional network across that now in a graph convolutional network you're trying to take a graph like this and have embeddings for the edges and the vertices so ultimately you want what's called a graph embedding in order to do that you need to propagate information along the graph usually as we said this is done during a graph convolution if you are in machine learning for a while longer you might remember also things like conditional random fields or generally graphical methods that were once popular and are kind of a precursor to this so the way they do it is they do it in an iterative fashion they have multiple so they say this right here so how do they embed a graph they have nodes in the graph as we saw before I'm going to draw this one again so this is maybe vi vj and vk now these represent the pieces in the netlist that you have to place so for each of those it has a bunch of features right so the features might be its size it's I believe they they have them somewhere here its size maybe how much power it uses and also its x and y coordinates if it is already placed right so you start with a vector like this and then you iteratively do the following thing you compute edge edge features by running first these things so this is vi and vj for an for each edge you take its nodes run them through this fully connected layer so you embed the features of the nodes you concatenate them and you run it through another neural network layer and that's how you get embeddings for edges and then you update the embeddings for the nodes again by taking the mean embeddings of the edges so you do this in an iterative fashion first you compute the edges from the nodes and then you compute the nodes from the edges and so on right so this means that information can now propagate through the graph so information from this thing propagates into this edge embedding and then in the next step that will propagate into this and then that can propagate into this EJK and this is the same as if you're used to yeah something like a conditional random fields over time if you have a big graph like this the information from any particular node will kind of propagate out throughout the graph and at some point you can sort of reach an equilibrium where everyone everyone in the graph knows about everyone else I have not found how many times they do it they simply say we repeatedly perform the following updates maybe that's somewhere and I just haven't read it closely enough but also I don't haven't seen whether or not they then back propagate through this through these multiple updates or whether they just back prop through one of them not entirely sure but ultimately they get embeddings these edge embeddings out of this graph and they simply take the mean to get the graph embeddings and that goes into their state embeddings right along with that they also have the macro embeddings which are the nodes here the things to be placed along with the current macro ID this is which one do you need to place right now so this comes out of these are the two things out of graphs vertices and edges and then which one you need to place right now it's pretty important right so you take the ones the one that you need to place this also goes into your embedding and then you have some metadata about the netlist like how many things there are and so on and this is also embedded using a fully connected layer all of that goes into your embedding right so your embedding will contain all of this information if you've done a good job and if you train it correctly so this is the model now they do pre train this encoder part right here and the encoder part it's also kind of circular first of all they just generate a giant list so they take this chip here and they just run a policy network that is maybe not super optimal but they just run it a bunch of times in intermediate states and they pre train the encoder to predict the final reward for each of these placements or sorry the the the wire length and congestion and so on and that pre trains the encoder but ultimately you can train this with reinforcement learning you can now let it try to solve this board over and over and over and over and it will get better over time all right the last thing they do is they do transfer learning now finding a better architecture for a single board is already better and faster than the humans but what is cool is that if you have now trained on this one particular board sorry with one particular netlist where was it right we've we've now trained on this particular netlist this was this was our problem and we've solved that we have a great solution can we now when we get a netlist another netlist so here is netlist 2 right it's maybe a bit different so this one is more longer and this one is here and so on what if so we would have to start again from scratch a training reinforcement learning agent on the netlist too so maybe a RL agent trained on chess if we now wanted to play go you know we need to start over again but they try to just transfer this to the new one and astonishingly enough if you train the same RL agent not only on one netlist but on a set of netlists and the biggest set they have is 20 so their data set size is 20 imagine how small this is compared to supervised learning but maybe think of this like you train on 20 Atari games and then it will play the 21st one much better than if you started from scratch interestingly though even zero shot embeddings tend to be pretty good so they don't optimize for the new thing at all and it's already better you can see that here so if you train a policy from scratch then you this here then it takes a long time but if you fine-tune a pre-trained policy it's much shorter and interestingly enough at the beginning it is already better than the policy from scratch that means the knowledge from one chip transfers over to the other chip so the problems are sufficiently close and that basically means that if we now want to design a new AI chip not only are we better because of RL we're also faster because we can transfer learn and they show here that this effect basically appears when you have a large enough data set and again large here is just 20 blocks here you see one of these placements on the left the zero shot placement on the right and fine-tuned on that particular architecture obviously me being an expert in chip placement is it clearly obvious that both are extremely good and yes though actually more funny I find this one where they compare human experts to what their approach is and it says the figures are intentionally blurred as the designs are provided like why do you put them that clearly I can't even couldn't even judge if they're super crisp I yeah all right I guess it's their trade secret so they compare this with the standard algorithms for these things and not only are they faster they are they also better on the metrics yeah overall as I said I find this to be a pretty cool work that pulls in a lot of things from a lot of different fields at one point they say we propose a novel graph convolutional architecture I'm not sure that it is novel maybe it's novel for this problem but I'm pretty sure graph convolutional networks and things like this have been around for a while but again it pulls together things from many different fields and applies them very well very well engineered paper and a step towards the singularity as now AI can design AI accelerators how amazing yeah humanity is doomed all right I invite you to check out this paper if you're still here please subscribe leave a like and a comment and I'll see you next time bye bye
 Hi there! Today we're looking at Chip Placement with Deep Reinforcement Learning
 by Azalia Miroszajny, Anna Goldi and a long list of authors that I have no
 stamina to read down. I'm sorry. So this work is a cool application of
 reinforcement learning to the real world. And we're gonna go through it and the
 cool thing about it is it pulls together parts from so many different areas of
 machine learning and also here chip engineering. So what's the fundamental
 problem? The fundamental problem of chip design is this. You have a canvas, an
 empty chip and you want to build a computer chip. Now what you have given is
 a so-called netlist. So your netlist is any parts that you want on that computer
 chip and their shape or their size. So you can imagine this like a bit of a
 Tetris game. So here's this netlist. There's this part and then this part and
 then there's maybe this part and also this part. Many many parts. Now these as I
 understand it can be thousands of parts but you can sort of group them together
 but still there are a lot of these parts. And the netlist also contains
 information about how they're connected. So for each of these parts you would
 have a list of which other ones of these parts they must be connected to. So
 maybe it says okay this part here needs to be connected to those three parts and
 for each of those you'd also have like a list of how they must be connected.
 You can represent this as an adjacency matrix right? But ultimately this is a
 graph of these nodes. Now your goal is to place those things on this board. So for
 example we're gonna place this right here and we're gonna place the second
 one maybe here and the third one maybe here. So you can imagine if this is a
 CPU maybe look I have no clue of chip design but I imagine it like this. This
 is your clock that you need on there. This is your NAND gates right? NAND gates
 pretty important for a CPU and this is your floating point unit also pretty
 important and so on. So I need to place these things and then you need to
 connect them using these using wires. Now wires are of course etched into the
 board but you need to connect them according to the maybe there is a
 component right here. According to the netlist right they need to be connected
 like that. Maybe the algorithm that came up with the chip told you they need to
 be connected like this and if you lay them out like this you can draw the
 wires. So this is your finished you you want to go from the thing on the right
 to the thing on the left and your goal here in order to get the fastest
 possible computer chip is three things. First of all you want first of all the
 density is important. By density it basically just means you can't place
 stuff on top of other stuff so you could not place a block right here. Not possible
 because the clock is already there. So that's first thing you can't place
 stuff on top of other stuff. Then the second thing is the wires and
 specifically the length of the wires. So you see for example this thing here is a
 pretty short wire that means the signal travels fast. This thing here is a long
 wire so the signal travels more slowly. Now the lower sorry the the faster you
 want your signal to go that means you have to make your wires as short as
 possible. So you want to keep the total amount of wire length as short as
 possible. Then third is what's called congestion. So congestion is when for
 example okay I actually don't know what it is but maybe it is when two wires
 cross like somewhere here there might be congestion or maybe some parts
 actually share their wires. I can imagine sorry I'm gonna draw this again I can
 imagine maybe there's a part here that wants to go up and then it maybe shares
 sorry shares this part of the wire here with the other one and so there's
 congestion like it's roads or something. In any case you can measure congestion
 it's a bad thing and you want to lay out your components basically in order to
 minimize congestion and also minimize the length of the wires and not have
 them on top of one another. Easy enough right? It takes human experts and
 combined with state-of-the-art algorithms multiple weeks to design chips like this
 and that's the fundamental problem and this paper takes reinforcement learning
 in order to solve this problem in a few hours. So how does it do this? The
 reinforcement learning is basically a sequential measure method so you want to
 do one action at a time. So you start off with what they call the chip canvas
 which is just empty. This is your state and then the agent here it gets to
 decide where to place the next thing. Now how do you decide what the next thing is?
 I believe they simply go by size so they take the largest component first of
 the netlist first and they just go down the netlist like this. So you tell the
 agent hey agent I want you to place this this thing here I want you to place this
 next and the agent will tell you I will place it right here and then again you
 tell the agent agent I have this this thing here where do you want to place it
 and along with sorry along with all the connections right along with everything
 that it needs to be connected to and also the entire list so the agent must
 also think of what what is to come yet what it hasn't placed yet. So it
 everything goes into this decision and it tells you okay I want to place this
 here and then at the end you end up with this filled board. Now this isn't
 actually the end. After you have placed all your things there is another method
 coming in this is called this force directed method placing yet more things
 so what you actually place with this agent is only the things called macros. I
 have no idea what those are or how these are different from these standard cells
 but apparently you must use a force directed method which you can think of
 just just an algorithm you run to place the standard cells and these are these
 these gray blobs here and at the end of all of this you can finally evaluate how
 good your design is. So at the end of all your of this you get a reward that is a
 mixture of wire length and congestion. Now this is actually an approximation to
 wire length and this is an approximation to congestion that they use because they
 need to evaluate it quickly but in essentially it's highly correlated
 with wire length and congestion so the negative of that is going to be your
 reward. So in terms of a reinforcement learning problem this is pretty nasty
 right because as you can see here you get basically a reward of zero for every
 step until the very end you get your true reward and it is actually worse
 than that because so from here to here your agent gets to perform actions
 right this is action time but usually when you have these sparse reward tasks
 you'll get your reward at the end of that action time but not here at the end
 of the action time there is an algorithm over which the agent basically has no
 control that comes in and does a bunch of things this force directed method and
 only then do you get your reward right so the agent must purposefully sort of
 leave room here for what this algorithm is going to do so it needs to learn that
 as well this is a as far as reinforcement learning goes this is a
 pretty good reinforcement learning problem right so now we have an
 environment which is the canvas here and also this you can you can consider this
 force directed method to be part of the environment and of course the reward
 giver and you have also the netlist as part of the environment and you have the
 agent that can do actions now we have to go into how does the agent perform
 actions on this so by the way maybe a bit confusing because it was a bit
 confusing for me for a given reinforcement learning problem we'll
 just start out by saying that the netlist is always the same right if you
 might be coming from a deep learning framework where you're used to many many
 different training samples in this case basically the netlist the goal is always
 the same you can think of it like a reinforcement learning agent for the
 game of chess where it's always the same chess game that you're trying to
 optimize this is the difference to let's say supervised learning if you have a
 label in supervised learning if you know the solution to a particular data point
 you're happy right you that data point is no longer interesting you want to
 generalize here even though they generalize later here you can give it a
 single problem right and it will already a solution to that problem will be
 valuable because it can be a better solution that humanity has come up with
 until this point so always think that we're now just working on one single
 netlist one problem to optimally place this netlist and an episode is simply to
 place these things until here and then you get a reward and then you go back to
 the beginning and just do it all over again but just try to do better and then
 you go back to the beginning and you do it all over again the same problem right
 okay so how does this work by the way that the paper has great technical
 detail on chip engineering and how the reward function exactly works and so on
 I have not the expertise to go into this with you beyond what I just described
 alright so here is how the model looks from a deep RL perspective now there's
 two parts to this model you can divide it about here so on the right you would
 have what is your policy and value networks and on the left the feature
 embeddings so in reinforcement learning and we won't go much into reinforcement
 learning now but what you need are basically a way to encode the state this
 is the encoder so all the information of the observation they might be in
 different modalities and so on you need to encode this into but in for
 simplicity let's say a single vector that's thing that this thing here this
 is the state encoding and then you can employ a policy and a value network in
 order to do reinforcement learning so the side on the right this comes from
 standard RL you have a policy network and a value network and they do I
 believe PPO with it this is a standard reinforcement learning architecture
 it's an actor critic architecture so the value net is simply telling you what's
 the value of the state that you're in now given that you have a state embedding
 it simply takes a fully connected layer to transform this into a single float
 that is the value network the policy is a bit different because usually in
 reinforcement learning you just have a list of actions right you just say I
 have these 16 buttons on my controller you compress them here we if you run if
 you look at this chip from above we have a question where do you want to place
 the next thing so in order to do that we take this embedding of the state and
 they run it through a series of D convolutions and the D convolutions they
 have the ability to basically up sample an image so you see here you transform
 this vector into a 4 by 4 by 32 tensor and that gets D convolved into more and
 more though less and less channels but more and more height and width images so
 it kind of from a vector it produces an image right here you might recognize
 this from a lot of generator architectures for when you make GANs for
 images have exactly this D convolution architecture so as I said pretty cool
 it pulls in kind of architectures and methods from different fields we already
 have reinforcement learning now we have generators for images now so you come up
 with an image and basically this image if you can imagine this from above is
 discretized so you can place the thing you have to place pretty much every
 single nanometer but they discretize this into a grid and for each point in
 the grid the network outputs a number so the number maybe nine here three four
 and so on eight right here so for each of these they it outputs a number where
 it would or how much it would like to place the next thing at this particular
 location so this is a distribution over locations so the first thing you have to
 do is you have to mask out where there are already things we said the first
 condition is things cannot be on top of other things so maybe you already have
 placed something here so you ignore those numbers and you have already
 placed something here so you ignore those numbers as well this is this
 masking operation right here and then you simply look at where is your highest
 number and maybe there's maybe there's an 11 down here somewhere say ah this is
 my highest number okay cool and you look at what you need to place maybe the
 thing you need to place looks like this and you say all right I will place maybe
 the 11 marks the top left corner I will place it right here okay and then you do
 the same thing again for the next piece so the next piece you would simply also
 mark this to be blue so you can't place here you evaluate your network again of
 course you'll have a new shape something like this and then you ask the network
 where would you like to place this and you do this step by step by step until
 the entire netlist is empty so this is how we do the reinforcement learning
 this is how we decide on an action but how do we actually put the state into
 this encoding now this pulls in yet another framework from another field of
 deep learning namely graph convolutional neural networks so since the netlist is
 a graph right the netlist is again if you have your wow this is slow today if
 you have your netlist right here with the part right the shape or size
 whatever and the list of things it needs to be connected to then this forms
 naturally a graph so you can transform this into a graph with the things that
 need to be connected connected by an edge and they run a graph convolutional
 network across that now in a graph convolutional network you're trying to
 take a graph like this and have embeddings for the edges and the
 vertices so ultimately you want what's called a graph embedding in order to do
 that you need to propagate information along the graph usually as we said this
 is done during a graph convolution if you are in machine learning for a while
 longer you might remember also things like conditional random fields or
 generally graphical methods that were once popular and are kind of a precursor
 to this so the way they do it is they do it in an iterative fashion they have
 multiple so they say this right here so how do they embed a graph they have
 nodes in the graph as we saw before I'm going to draw this one again so this is
 maybe vi vj and vk now these represent the pieces in the netlist that you have
 to place so for each of those it has a bunch of features right so the features
 might be its size it's I believe they they have them somewhere here its size
 maybe how much power it uses and also its x and y coordinates if it is already
 placed right so you start with a vector like this and then you iteratively do
 the following thing you compute edge edge features by running first these
 things so this is vi and vj for an for each edge you take its nodes run them
 through this fully connected layer so you embed the features of the nodes you
 concatenate them and you run it through another neural network layer and that's
 how you get embeddings for edges and then you update the embeddings for the
 nodes again by taking the mean embeddings of the edges so you do this
 in an iterative fashion first you compute the edges from the nodes and
 then you compute the nodes from the edges and so on right so this means that
 information can now propagate through the graph so information from this thing
 propagates into this edge embedding and then in the next step that will
 propagate into this and then that can propagate into this EJK and this is the
 same as if you're used to yeah something like a conditional random fields over
 time if you have a big graph like this the information from any particular node
 will kind of propagate out throughout the graph and at some point you can sort
 of reach an equilibrium where everyone everyone in the graph knows about
 everyone else I have not found how many times they do it they simply say we
 repeatedly perform the following updates maybe that's somewhere and I just
 haven't read it closely enough but also I don't haven't seen whether or not they
 then back propagate through this through these multiple updates or whether they
 just back prop through one of them not entirely sure but ultimately they get
 embeddings these edge embeddings out of this graph and they simply take the mean
 to get the graph embeddings and that goes into their state embeddings right
 along with that they also have the macro embeddings which are the nodes here the
 things to be placed along with the current macro ID this is which one do you
 need to place right now so this comes out of these are the two things out of
 graphs vertices and edges and then which one you need to place right now it's
 pretty important right so you take the ones the one that you need to place
 this also goes into your embedding and then you have some metadata about the
 netlist like how many things there are and so on and this is also embedded
 using a fully connected layer all of that goes into your embedding right so
 your embedding will contain all of this information if you've done a good job
 and if you train it correctly so this is the model now they do pre train this
 encoder part right here and the encoder part it's also kind of circular first of
 all they just generate a giant list so they take this chip here and they just
 run a policy network that is maybe not super optimal but they just run it a
 bunch of times in intermediate states and they pre train the encoder to
 predict the final reward for each of these placements or sorry the the the
 wire length and congestion and so on and that pre trains the encoder but
 ultimately you can train this with reinforcement learning you can now let
 it try to solve this board over and over and over and over and it will get better
 over time all right the last thing they do is they do transfer learning now
 finding a better architecture for a single board is already better and
 faster than the humans but what is cool is that if you have now trained on this
 one particular board sorry with one particular netlist where was it right
 we've we've now trained on this particular netlist this was this was our
 problem and we've solved that we have a great solution can we now when we get a
 netlist another netlist so here is netlist 2 right it's maybe a bit
 different so this one is more longer and this one is here and so on what if so we
 would have to start again from scratch a training reinforcement learning
 agent on the netlist too so maybe a RL agent trained on chess if we now wanted
 to play go you know we need to start over again but they try to just
 transfer this to the new one and astonishingly enough if you train the
 same RL agent not only on one netlist but on a set of netlists and the biggest
 set they have is 20 so their data set size is 20 imagine how small this is
 compared to supervised learning but maybe think of this like you train on
 20 Atari games and then it will play the 21st one much better than if you started
 from scratch interestingly though even zero shot embeddings tend to be pretty
 good so they don't optimize for the new thing at all and it's already better you
 can see that here so if you train a policy from scratch then you this here
 then it takes a long time but if you fine-tune a pre-trained policy it's much
 shorter and interestingly enough at the beginning it is already better than the
 policy from scratch that means the knowledge from one chip transfers over
 to the other chip so the problems are sufficiently close and that basically
 means that if we now want to design a new AI chip not only are we better
 because of RL we're also faster because we can transfer learn and they show here
 that this effect basically appears when you have a large enough data set and
 again large here is just 20 blocks here you see one of these placements on the
 left the zero shot placement on the right and fine-tuned on that particular
 architecture obviously me being an expert in chip placement is it clearly
 obvious that both are extremely good and yes though actually more funny I find
 this one where they compare human experts to what their approach is and it
 says the figures are intentionally blurred as the designs are provided like
 why do you put them that clearly I can't even couldn't even judge if they're
 super crisp I yeah all right I guess it's their trade secret so they compare
 this with the standard algorithms for these things and not only are they
 faster they are they also better on the metrics yeah overall as I said I find
 this to be a pretty cool work that pulls in a lot of things from a lot of
 different fields at one point they say we propose a novel graph convolutional
 architecture I'm not sure that it is novel maybe it's novel for this problem
 but I'm pretty sure graph convolutional networks and things like this have been
 around for a while but again it pulls together things from many different
 fields and applies them very well very well engineered paper and a step towards
 the singularity as now AI can design AI accelerators how amazing yeah humanity
 is doomed all right I invite you to check out this paper if you're still
 here please subscribe leave a like and a comment and I'll see you next time bye
 bye