Deep reinforcement learning on 1-layer circuit routing problem

In VLSI design, routing is the step that determines the paths for circuit nets and interconnections. While routing can be a very complex process involving time, congestion and space information, the problem can be modelled as a maze routing problem. In specific, given a 2d array and a set of start nodes and end nodes, the agent is trying to optimize the solution by connectivity and path length. Traditionally, the routing problem is solved using graph search techniques such as Lee’s algorithm. The result produced by graph search algorithms relies heavily on the order of routing. While some simple heuristics are available, the result is not stable because simple heuristics take greedy approaches and neglect the long-term reward. The recent development of deep learning, especially deep reinforcement learning, can be a good approach to finding better ordering on attacking the routing problem. We introduce a reinforcement learning approach to the traditional 2-point nets in 1-layer maze routing problem.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2019

Author dc:creator

• Zhang, Yihao

Contributors dc:contributor

• Wong, Martin D.F.

• Maze routing
• Reinforcement Learning

Statement dc:rights

• Copyright 2018 Yihao Zhang

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/102796

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/102796