placementoptimizationwithdeepreinforcementlearning.pdf资源-CSDN文库

需积分: 12 123 浏览量 2020-04-01 23:33:40 上传评论收藏 1.64MB PDF 举报

资源推荐

资源详情

资源评论

Placement Optimization with Deep Reinforcement Learning

Anna Goldie and Azalia Mirhoseini

agoldie,azalia@google.com

Google Brain

ABSTRACT

Placement Optimization is an important problem in systems and

chip design, which consists of mapping the nodes of a graph onto

a limited set of resources to optimize for an objective, subject to

constraints. In this paper, we start by motivating reinforcement

learning as a solution to the placement problem. We then give an

overview of what deep reinforcement learning is. We next formu-

late the placement problem as a reinforcement learning problem,

and show how this problem can be solved with policy gradient

optimization. Finally, we describe lessons we have learned from

training deep reinforcement learning policies across a variety of

placement optimization problems.

KEYWORDS

Deep Learning, Reinforcement Learning, Placement Optimization,

Device Placement, RL for Combinatorial Optimization

ACM Reference Format:

Anna Goldie and Azalia Mirhoseini. 2020. Placement Optimization with

Deep Reinforcement Learning. In Proceedings of the 2020 International Sym-

posium on Physical Design (ISPD ’20), March 29-April 1, 2020, Taipei, Taiwan.

ACM, New York, NY, USA, 5 pages. https://doi.org/10.1145/3372780.3378174

1 INTRODUCTION

An important problem in systems and chip design is Placement

Optimization, which refers to the problem of mapping the nodes of

a graph onto a limited set of resources to optimize for an objective,

subject to constraints. Common examples of this class of problem

include placement of TensorFlow graphs onto hardware devices to

minimize training or inference time, or placement of an ASIC or

FPGA netlist onto a grid to optimize for power, performance, and

area.

Placement is a very challenging problem as several factors, in-

cluding the size and topology of the input graph, number and

properties of available resources, and the requirements and con-

straints of feasible placements all contribute to its complexity. There

are many approaches to the placement problem. A range of algo-

rithms including analytical approaches [

], genetic and

hill-climbing methods [

], Integer Linear Programming (ILP)

[2, 27], and problem-speciﬁc heuristics have been proposed.

More recently, a new type of approach to the placement prob-

lem based on deep Reinforcement Learning (RL) [

] has

Permission to make digital or hard copies of part or all of this work for personal or

classroom use is granted without fee provided that copies are not made or distributed

for proﬁt or commercial advantage and that copies bear this notice and the full citation

on the ﬁrst page. Copyrights for third-party components of this work must be honored.

For all other uses, contact the owner/author(s).

ISPD ’20, March 29-April 1, 2020, Taipei, Taiwan

ACM ISBN 978-1-4503-7091-2/20/03.

https://doi.org/10.1145/3372780.3378174

emerged. RL-based methods bring new challenges, such as inter-

pretability, brittleness of training to convergence, and unsafe ex-

ploration. However, they also oﬀer new opportunities, such as the

ability to leverage distributed computing, ease of problem formu-

lation, end-to-end optimization, and domain adaptation, meaning

that these methods can potentially transfer what they learn from

previous problems to new unseen instances.

In this paper, we start by motivating reinforcement learning as

a solution to the placement problem. We then give an overview

of what deep reinforcement learning is. We then formulate the

placement problem as an RL problem, and show how this problem

can be solved with p olicy gradient optimization. Finally, we describe

lessons we have learned from training deep RL policies across a

variety of placement optimization problems.

2 DEEP REINFORCEMENT LEARNING

Most successful applications of machine learning are examples of

supervise d learning, where a model is trained to approximate a

particular function, given many input-output examples (e.g. given

many images labeled as cat or dog, learn to predict whether a given

image is that of a cat or a dog). Today’s state-of-the-art super-

vised models are typically deep learning models, meaning that the

function approximation is achieved by updating the weights of a

multi-layered (deep) neural network via gradient descent against a

diﬀerentiable loss function.

Reinforcement learning, on the other hand, is a separate branch

of machine learning in which a model, or policy in RL parlance,

learns to take actions in an environment (either the real world or a

simulation) to maximize a given reward function. One well-known

example of reinforcement learning is AlphaGo [

], in which a pol-

icy learned to take actions (moves in the game of Go) to maximize

its reward function (number of winning games). Deep reinforce-

ment learning is simply reinforcement learning in which the p olicy

is a deep neural network.

RL problems can be reformulated as Markov Decision Processes

(MDPs). MDPs rely on the Markov assumption, meaning that the

next state

𝑠

𝑡+1

depends only on the current state

𝑠

𝑡

, and is condi-

tionally independent of the past.

𝑃 (𝑠

𝑡+1

|𝑠

...𝑠

𝑡

) = 𝑃 (𝑠

𝑡+1

|𝑠

𝑡

)

Like MDPs, RL problems are deﬁned by ﬁve key components:

•

states: the set of possible states of the world (e.g. the set of

valid board positions in Go)

•

actions: the set of actions that can be taken by the agent (e.g.

all valid moves in a game of Go)

•

state transition probabilities: the probability of transitioning

between any two given states.

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余4页未读，立即下载

评论收藏

内容反馈

每天一个小脚印

粉丝: 634
资源: 7

placement optimization with deep reinforcement learning.pdf

最新资源

placement optimization with deep reinforcement learning.pdf

deep reinforcement learning for nlp

deep reinforcement learning

deep learning.pdf

double_deep_reinforcement_learning.pdf

手机射频Placement的小结与心得.pdf

Python库 | osc-placement-1.5.0.tar.gz

Selection and Placement of Decoupling Capacitors.pdf

Grid Placement Error(解决方案).md

deep_reinforcement_learning

deep+learning.pdf.zip

deep learning with python pdf

udacity_deep_reinforcement_learning_project2

Grid Item Placement Error(解决方案).md

RTL Coding and Optimization Guide for use with Design Compiler.pdf

BGA Placement and Routing.pdf

GENERALIZED DEVICE PLACEMENT FOR DATAFLOW GRAPHS.pdf

UFLDL_deep learning.pdf

tensorflow for deep learning.pdf

deep learning in trading.pdf

cheatsheet-deep-learning.pdf

Oxford Online Placement Test 8doc资料.pdf

Digging into WordPress.pdf

新增 Wonders语言水平测试工具 Wonders Placement and Diagnostic Assessment.pdf

Physical-Design-Complete.pdf

Optimal Placement of Capacitors for Loss Reductio.zip

最新资源