Transcript RLCR
Applying Machine Learning to Circuit Design David Hettlinger Amy Kerr Todd Neller Channel Routing Problems (CRPs) Chip Design Each silicon wafer contains hundreds of chips. Chip components, specifically transistors, are etched into the silicon. Often groups of components need to be wired together. A Simple CRP Instance 3 4 1 0 2 4 1 2 Net number 4 Silicon Channel 4 2 0 3 One Possible Solution 3 4 1 0 2 4 0 1 2 3 4 5 4 2 0 3 1 Goal: Decrease the number of horizontal tracks. 2 CRPs: Constraints Horizontal: Horizontal segments cannot overlap. Vertical : If subnet x has a pin at the top of column a, and subnet y has a pin at the bottom of column a, then subnet x must be placed above subnet y. Simulated Annealing (SA) Background “Annealing” came from a process blacksmiths use. Metal is heated then cooled slowly to make it as malleable as possible. Statistical physicists developed SA. SA Problem Components Definable states: The current configuration (state) of a problem instance must be describable. New state generation: A way to generate new states. Energy function: A formula for the relative desirability of a given state. Temperature and annealing schedule: A temperature value and a function for changing it over time. A Visual Example Local Minimum Global Minimum Applying Simulated Annealing to CRPs Definable states: The partitioning of subnets into groups. New states generation: Change the grouping of the subnets. Energy function: The number of horizontal tracks needed to implement a given partition. Temperature and annealing schedule: Start the temperature just high enough to accept any new configuration. As for the annealing schedule, reinforcement learning can help find that. A Simple CRP Example Start State of a CRP Instance Partition Graph of this State A Simple CRP Example States 1 and 2 Partition Graphs of theses States A Simple CRP Example States 1, 2 and 3 Partition Graphs of these States A Simple CRP Example Starting through Ending States Partition Graphs of these States A Generated CRP Instance Start State A Solution 12 Horizontal Tracks 15 Horizontal Tracks SA Problem Components Definable states: The current configuration (state) of a problem instance must be describable. New state generation: A way to generate new states. Energy function: A formula for the relative desirability of a given state. Temperature and annealing schedule: A temperature value and a function for changing it over time. The Drunken Topographer Imagine an extremely hilly landscape with many hills and valleys high and low Goal: find lowest spot Means: airlift a drunk! Starts at random spot Staggers randomly More tired rejects more uphill steps Super-Drunks, Dead-Drunks, and Those In-Between The Super-Drunk never tires Never rejects uphill steps How well will the Super-Drunk search? The Dead-Drunk is absolutely tired Always rejects uphill steps How well will the Dead-Drunk search? Now imagine a drunk that starts in fine condition and very gradually tires. Traveling Salesman Problem Have to travel a circuit around n cities (n = 400) Different costs to travel between different cities (assume cost = distance) State: ordering of cities (> 810865 orderings for 400 cities) Energy: cost of all travel Step: select a portion of the circuit and reverse the ordering Determining the Annealing Schedule The schedule of the “cooling” is critical Determining this schedule by hand takes days Takes a computer mere hours to compute! Reinforcement Learning Example Goal: Ace a class Need to learn how long we need to study to get an A Trial & Error: study for various amts. of time Short term reward: exam grades, amt free time Long term rewards: Grade affects future opportunities: i.e. whether we can slack off later Our semester grades (goal is to max. this!) Reinforcement Learning (RL) Learns completely by trial & error No preprogrammed knowledge No human supervision/mentorship Receives rewards for each action 1. Immediate reward (numerical) 2. Delayed reward: actions affect future situations & opportunities for future rewards Goal: maximize long-term numerical reward RL: The Details Agent Sensation Reward Action Environment Agent = the learner (i.e. the student) Environment = everything the agent cannot completely control. Includes reward functions (i.e. grade scale) Descript. of current state (i.e. current average) Call this description a “Sensation” RL: Value Functions Use immediate & delayed rewards to evaluate desirability of actions/learn task Value function of a state-action pair, Q(s,a) The expected reward for taking action a from state s Includes immediate & delayed reward Strategy: Most of the time, choose the action that corresponds to the maximal Q(s,a) value for the state. Remember, must explore sometimes! RL: Q-Functions We must learn Q(s,a) To start, set Q(s,a) = 0 for all s, a. Agent tries various actions. Each time experiences action a from state s, updates estimate of Q(s,a) towards the actual reward experienced If usually pick the action a’ that has the maximal Q-value for that state max. total reward optimal performance Example: Grid World Can always move up, down, right, left Board wraps around Goa Get to goal in as few steps as possible. Reward = ? Star Meaning of Q? What are the optimal paths? Applying RL to CRP Can learn an approx. optimal annealing schedule using RL Reward function: Rewarded for reaching better configuration Penalized for the amount of time used to find this better configuration Computer learns to find an approx optimal annealing schedule in a time-efficient manner. Program self-terminates! Conclusions CRP is an interesting but complex problem Simulated Annealing helps us solve CRPs Simulated Annealing requires annealing schedule (how to change temperature over time) Reinforcement learning – which is just learning through trial & error – lets a computer learn an annealing schedule in hours instead of days. Any Questions?