# XRoute Environment: A Novel Reinforcement Learning Environment for Routing

Zhanwen Zhou
School of Computer Science
Sun Yat-sen University
Guangzhou 510006, China
<EMAIL_ADDRESS>
Hankz Hankui Zhuo
School of Computer Science
Sun Yat-sen University
Guangzhou 510006, China
<EMAIL_ADDRESS>
Xiaowu Zhang
School of Computer Science
Sun Yat-sen University
Guangzhou 510006, China
<EMAIL_ADDRESS>
Qiyuan Deng
School of Computer Science
Sun Yat-sen University
Guangzhou 510006, China
<EMAIL_ADDRESS>

###### Abstract

Routing is a crucial and time-consuming stage in modern design automation flow
for advanced technology nodes. Great progress in the field of reinforcement
learning makes it possible to use those approaches to improve the routing
quality and efficiency. However, the scale of the routing problems solved by
reinforcement learning-based methods in recent studies is too small for these
methods to be used in commercial EDA tools. We introduce the XRoute
Environment, a new reinforcement learning environment where agents are trained
to select and route nets in an advanced, end-to-end routing framework. Novel
algorithms and ideas can be quickly tested in a safe and reproducible manner
in it. The resulting environment is challenging, easy to use, customize and
add additional scenarios, and it is available under a permissive open-source
license. In addition, it provides support for distributed deployment and
multi-instance experiments. We propose two tasks for learning and build a
full-chip test bed with routing benchmarks of various region sizes. We also
pre-define several static routing regions with different pin density and
number of nets for easier learning and testing. For net ordering task, we
report baseline results for two widely used reinforcement learning algorithms
(PPO and DQN) and one searching-based algorithm (TritonRoute). The XRoute
Environment will be available at https://github.com/xplanlab/xroute_env.

##  1 Introduction

In very large-scale integration (VLSI) design, routing is challenging and has
become a vital bottleneck in real world applications due to the complicated
design rules and large solution space (Chen et al., 2020b). In general, the
routing task is separated into global routing and detailed routing. The former
aims at partitioning the whole routing region into individual cells called
GCell and routing nets on GCell according to the prediction of congestion (Liu
et al., 2013), while the latter builds rectilinear wiring interconnects that
are consistent with design rules (Park et al., 2019). The detailed routing
attempts to realize the segments and vias according to the global routing
solution, and aims at minimizing design rule violations, wirelength and vias
used.

Maze-based and A*-based searching methods have enjoyed huge success in global
and detailed routing. Until now, they are still used in many commercial
electronic design automation (EDA) software. However, these methods tend to
analyze and simulate some specific characteristics in routing, and hardcode
them in the algorithm. They often explore a lot of unnecessary nodes during
searching for the target. They seldom take into account the entire routing
environment so as to bypass the obstacles as early as possible. What’s worse,
the current routing net based on these methods will not consider the
routability of the following nets, which causes lots of rip-up and rerouting.
As shown in Figure 1(a), $net_{1}$ and $net_{2}$ are routed sequentially by
maze routing, but these temporal optimal routed paths block the following
connections of $net_{3}$ and $net_{4}$. The general solution for this
situation is to ripup $net_{1}$ and $net_{2}$ and reroute $net_{3}$ and
$net_{4}$ first as in Figure 1(b). It shows that net ordering and net routing
are crucial to VLSI routing.

(a) Resource conflicts in routing

(b) Ripup and reroute conflicted nets

Figure 1: Sequential routing is sensitive to the net order.

The goal of reinforcement learning (RL) is to train smart agents that can
interact with their environment and solve complex tasks (Sutton and Barto,
2018). Great progress in the field of deep reinforcement learning (DRL) makes
it possible to use those methods to accelerate the routing process in net
ordering and routing. However, the scale of the routing problems solved by the
RL-based methods in recent studies is too small for those methods to be used
in the commercial VLSI EDA tools. In this paper, we propose a novel RL
environment, namely XRoute Environment, standing for self-learning (denoted by
X) for detailed routing (denoted by Route), to train agents to repeatedly
recommend routing actions (representing “net order” or “net edge”) in an end-
to-end routing framework for detailed routing. Our XRoute Environment is
composed of three components, as shown below:

  * •

The first component is a highly-customized routing engine that simulates the
detailed routing process. As far as we know, this is the first open-source
reinforcement learning environment available for detailed routing learning.

  * •

The second is a versatile set of benchmark tasks of varying size and
difficulties that can be used to compare different algorithms, based on
ISPD-2018 (Mantik et al., 2018) and ISPD-2019 (Liu et al., 2019) detailed
routing testcases in our first version. We also pre-define several static
regions with different pin density and number of nets for easier learning and
testing. We evaluate two widely used algorithms on these benchmarks, providing
a basic set of reference results for future comparison.

  * •

The third is a dashboard that is used to exhibit the detailed routing results
such as wirelength, vias used and design rule violations during model
validation. Users can observe the detailed routing process and optimize their
algorithms accordingly.

To help users utilizing our XRoute Environment, we present two example tasks
(net ordering and net routing) for learning to improve the quality and
efficient of detailed routing. Users can follow the same way to define more RL
tasks.

##  2 Motivation and related work

While there have been a variety of reinforcement learning algorithms for VLSI
routing, there still exist open issues as shown bellow:

Lack of benchmarks from real chips. Many routing problems proposed with their
RL-based algorithms are generated by a self-developed generator. It lacks of
benchmarks from real chips to verify the adaptability of the routing
approaches in industrial advanced technology nodes. For example,
DQN_GlobalRouting (Liao et al., 2019) model the global routing problem as a
Markov Decision Process (MDP) and uses deep Q-learning (DQN) to solve the
routing problem by leveraging the conjoint optimization mechanism of deep
reinforcement learning. A global routing problems generator is also developed
to automatically generate parameterized problems with different scales and
constraints. However, their nets are decomposed into a set of two-pin
connections, and the environment is only used for learning to route from one
source to one target. Alpha-PD-Router (Gandhi et al., 2019) is a data-
independent RL-based routing model, which learns to route a circuit and
correct short violations. It is trained and tested on the $1\times 5\times 5$
routing grid with 3 two-pin nets. He et al. (He et al., 2022) model circuit
routing as a sequential decision problem and solve it in Monte Carlo tree
search with DRL-guided rollout. In their environment, 100 randomly generated,
routable single-layer circuits on a grid of $30\times 30$ with less than 10
nets are used as the test bed for two-pin nets routing learning. Ju et al. (Ju
et al., 2021) propose a detailed router based on multi-agent reinforcement
learning for handling conflicting nets, whose size far smaller than real
chips.

Not for detailed routing. Circuit Training (Guadarrama et al., 2021) is an
open-source framework created by Google Brain team for generating chip floor
plans with distributed DRL (Mirhoseini et al., 2021). It can place netlists
with hundreds of macros and millions of standard cells. However, Circuit
Training employ the half-perimeter wirelength (HPWL), the half-perimeter of
the bounding box for all pins in a net, to approximate the wirelength of the
net and do not run the real routing. PRNet (Cheng et al., 2022) is an RL-based
model for mixed-size macro placement. A one-shot conditional generative
routing model is devised to perform one-shot global routing on sample grid
graph with size of $64\times 64$ or $128\times 128$. REST (Liu et al., 2021)
is a reinforcement learning framework for rectilinear Steiner minimum tree
construction. The model is trained with random generated point sets as pins
from degree 3 to 50. Those approaches and their environments focus on
placement or global routing, not on detailed routing.

Not open-source. There indeed are some RL-based detailed routing algorithms.
For example, Lin et al. (Lin et al., 2022) propose an asynchronous RL
framework using Dr.CU (Chen et al., 2020a) as router to automatically search
for optimal ordering strategies. The model is trained and tested on several
dense clips with around 500 nets, which is selected from ISPD-2018 (Mantik et
al., 2018) and ISPD-2019 (Liu et al., 2019) benchmarks. Ren and Fojtik (Ren
and Fojtik, 2021) applies genetic algorithm to create initial routing
candidates and uses RL to fix the design rule violations incrementally on
their developed program called Sticks. Unfortunately, there is no open-source
license for those algorithms, which makes it hard to control over the
environment dynamics and generate realistic evaluation scenarios to
comprehensively test generalization in different chips with varying sizes and
complexities.

##  3 XRoute Environment

###  3.1 Routing as a RL problem

The background introduction of detailed routing is described in Appendix.
Detailed Routing can be formulated as the MDP tuple
$\langle\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma\rangle$. Each
state $s$ in the state space $\mathcal{S}$ consist of 3D grid graph routing
environment information, netlist, pin position, routed paths for the current
routing net. The action space $\mathcal{A}(s)$ is the set of available state-
dependent actions, which represent the next net (or path) to be routed in the
grid based on a given routing strategy. The transition model
$\mathcal{P}(s^{\prime}|s,a)$ transitions to a new state
$s^{\prime}\in\mathcal{S}$ given that action $a\in\mathcal{A}$ was executed
from state $s$. The bound reward function
$\mathcal{R}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is defined as
the reward returned by the routing environment after routing a net (or path)
in the grid. It is determined by the wirelength of the routed path, the number
of vias used, and the design rule violations occurred after routing.
$\gamma\in[0,1]$ is the discount factor. A policy
$\pi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ is a mapping from a state
to a distribution over actions where $\pi(a|s)$ denotes the probability of
taking action $a$ in state $s$. The goal of detailed routing is to obtain a
policy which maximizes the expected sum of discounted rewards
($\mathcal{J}_{\pi}^{\mathcal{R}}$ in Equation 1). That is to minimize the
overall wirelength, via count and design rule violations of the routing
solution on the basis of all nets are routed successfully.

$\mathop{max}\limits_{\pi}\mathcal{J}_{\pi}^{\mathcal{R}}(s):=\mathop{\mathbb{E}}\limits_{a\sim\pi,s\sim\mathcal{P}}\left[\sum\limits_{t}\gamma^{t}\mathcal{R}(s_{t},a_{t})]\right]$
(1)

###  3.2 Routing architecture

The overview of the XRoute architecture is showed in Figure 2. It is divided
into two modules: XRoute Environment and XRoute Training. The XRoute
Environment is based on the XRoute Engine, an advanced routing simulator built
around a heavily customized version of the publicly available TritonRoute
(Kahng et al., 2021) (Kahng et al., 2022). The engine simulates a complete
routing procedure from reading in the LEF, DEF and global routing guide files
of a chip design, routing data preparation, region partition and
initialization, net routing, design rules checking, rip-up and reroute, to
outputting the final detailed routing results. Based on the routing simulator,
XRoute Engine provides two modes with similar API for RL-based algorithms’
development. Trainer mode is used for model training. It can generate full-
chip test beds of varying region size and dynamically movable routing regions
with various layouts and netlists based on XRoute Benchmarks. Different
regions can be seen as different routing problems for RL-based algorithms and
the trainer can define the number of training interactions in each region.
According to the researcher’s requirements, trainer mode can also define
specific static regions with different pin density and number of nets for
model training. Validator mode is used for model validation. It goes through
all benchmarks with the well trained model and evaluate the routing results on
wirelength, vias count and design rule violations.

Figure 2: XRoute architecture overview.

Both trainer mode and validator mode employ similar reinforcement learning
APIs compatible with the OpenAI Gym API (Brockman et al., 2016) to interact
with the XRoute Training module. The interaction supports distributed
deployment and multi-instance experiments. In distributed deployment, a ZeroMQ
broker is created in between XRoute Environment and XRoute Training module for
data transmission and protobuf mechanism is used for serializing structured
data. XRoute Benchmarks is a versatile set of benchmark tasks of varying size
and difficulties that can be used to compare different algorithms, including
ISPD-2018 and ISPD-2019 detailed routing testcases. A chip can be partitioned
into regions with varying sizes, or user-defined width. RL-based algorithms is
then trained and tested on this regions and the well trained model is
validated by various benchmarks from XRoute Benchmarks. XRoute Dashboard is
another key component of XRoute Environment, which collect the routing logs
and results and present those data in a dashboard. It provides summary tables
and trend graphs to show the variation of wirelength, vias used, design rule
violations and many other routing evaluation indicators.

In XRoute Environment, We design two RL-based tasks in our first version to
improve the quality and efficient of detailed routing. One is net ordering,
the other is net routing. They are the most crucial steps of detailed routing.
We can follow the same way to define more routing RL tasks.

The XRoute Training contains four components: self routing, replay buffer,
learner and new model. The workers in self routing component read in the state
of routing instances generated by the Routing Simulator, and make use of RL-
based planning methods Jin et al. (2022b) to produce a routing action. The
self routing worker pass the routing action to the Routing Simulator and get
back the new state and routing cost, which is used to calculate the reward for
the action. This procedure runs recurrently until the end of routing. Then a
routing trajectory is generated and save in the replay buffer for later
training in learner. Finally, new model generated by continuous training and
optimizing are used for next self routing. The well trained model will be
validated and compared with XRoute benchmarks.

###  3.3 XRoute Engine

In this section, two RL-based tasks of net ordering and net routing available
in the first version of XRoute Engine are presented. The detailed usage of
these two tasks and the corresponding API and parameters are described in
Appendix.

####  3.3.1 Task 1: net ordering

##### State and observations

We define as state the complete set of data that is returned by the
environment after actions are performed. On the other hand, we define as
observation or representation any transformation of the state that is provided
as input to the routing algorithms. At every step in the routing process, a RL
agent receives an observation of the state of the routing region, which is
viewed as a 3D grid graph. The grid graph is an essential part of detailed
routing because the path search algorithm works directly on the grid graph,
and various costs and properties are associated with the grid vertices and
edges in the grid graph. Specifically, we follow (Kahng et al., 2021) to
partition the design into non-overlapping GCell-aligned regions, each of which
has $C\times C$ GCells in one layer, where $C$ is a hyperparameter (e.g.,
$C=3$, which means there are 9 GCells in each layer of the region). For each
region, A nonregular-spaced 3D grid graph supporting irregular tracks and off-
track routing is built. The terminal state is reached when all nets have been
routed in the region.

While routing, we organize the environment state data as _Dimension_ , _Nodes_
and _Nets_ for each net.

  * •

_Dimension_. The dimension of each region is represented by ($D_{x}$, $D_{y}$,
$D_{z}$), which respectively indicate the number of lines (on-track line, off-
track line, boundary line) in the vertical and horizontal directions of all
routing layers, as well as the number of routing layers.

  * •

_Nodes_. The nodes are formed by all orthogonal lines, thus, there are
$D_{x}\times D_{y}\times D_{z}$ nodes in the region. Each node is composed of
7 attributes: 1) maze index, the relative coordinates that all axes start from
zero; 2) point, the absolute position of the node in the region; 3) type,
being one of four values: _NOTEXIST_ if the intersection point is not exist in
that layer, _BLOCKAGE_ for obstacle points, _NORMAL_ for normal line
intersection points, and _ACCESS_ for access point (Kahng et al., 2020) of a
certain net; 4) usage, a Boolean to indicate whether the node is used; 5) net,
represents the net number to which the access point belongs; 6) pin,
represents the pin number of the access point in the corresponding net; 7)
cost, the edge cost in six direction (_UP_ , _DOWN_ , _NORTH_ , _SOUTH_ ,
_EAST_ , _WEST_).

  * •

_Nets_. The set of the net numbers to be routed is designated as _Nets_.

We propose a representation for the state in our baseline algorithms. We
simply divide the points contained in the environmental state data into pin
points, obstacle points, and empty points. When the environment is
initialized, the pin point is the above-mentioned node of type=ACCESS.
Obstacle points correspond to nodes of type=BLOCKAGE, and others are empty
points. We set the access points and path points of prior routed nets into
obstacle points before the next interaction. We construct the representation
of the state from the perspectives of obstacles and nets in the 3D grid graph
with dimension ($D_{x}$, $D_{y}$, $D_{z}$). For obstacles, we use a simple 0-1
feature. For nets, in addition to the basic 0-1 feature, we add six 0-1
features of each point to describe whether neighboring points belong to the
same pin of the net. Our baseline model was trained with above representation,
but researchers can easily do more feature mining and define their own
representations based on the environment state. Here we provide some further
references:

  * •

_Scale feature_. The size of each net.

  * •

_Cross-layer feature_. The distribution of pins and access points of a net in
the multi-layer routing environment.

  * •

_Boundary feature_. More resource conflicts and design rule violations in the
boundary of the routing environment.

  * •

_Spatial feature_. The overlaps area of one net with other nets.

##### Action

The action is represented by the number of a net chosen for subsequent
routing, and the action space consists of all unrouted nets. At each step,
XRoute Engine will route the net that is selected by RL agent with a pre-
defined path search routing algorithm.

##### Reward

A well-performing routing solution is expected to exhibit reduced numbers of
specified metrics such as wirelength, vias used, design rule violations. We
define the reward function 2 as below:

$R(s,a,s^{\prime})=cost(s)-cost(s^{\prime})$ (2) $cost(s)=0.5\times
wirelength+4\times via(s)+500\times drv(s)$ (3)

XRoute Engine returns the total number of wirelength, vias used and design
rules violations in state $s^{\prime}$ after performing a action $a$ in state
$s$. The cost function can be defined as a weighted sum of the increment of
these metrics (Liu et al., 2019). Function 3 is the cost function used in our
baseline algorithms. We apply lower penalties to the agent for the action that
results in smaller increments, ensuring that the agent learns a better net
ordering strategy. It also allows researchers to add custom reward functions
using wrappers which can be used to investigate reward shaping approaches.

####  3.3.2 Task 2: net routing

##### State and observations

The state of routing environment in net routing include data of _Dimension_ ,
_Nodes_ , _Nets_ in net ordering task, with additional data as below:

  * •

_Net_. The current routing net is represented by the serial number of the net.

  * •

_Head_. The current head of the routed path of the routing net.

The state representation can be defined as a 12-dimensional vector. The first
three elements are the $(x,y,z)$ coordinates of the current agent position in
the environment. The fourth through the sixth elements encode the distance in
the $x$, $y$, and $z$ directions from the current agent location to the target
pin location. The remaining six dimensions encode the usage or cost
information of all the edges the agent is able to cross. This encoding scheme
can be seen as a mix of the current state, the navigation, and the local
capacity information. If the agent takes an illegal action or a connection to
the final pin of the net from current state $s_{t}$, then the next state
$s_{t+1}$ is the terminal state. Researchers can easily define their own
representations based on the environment state by creating wrappers similarly.

##### Action

The actions are represented with the coordinate of the start point $(x,y,z)$
defaulted to be the current head location, an integer $d$ from 0 to 5
corresponding to the direction of move from the start point, and an integer
$s$ corresponding to the number to step to move, with a default value as 1.

##### Reward

The reward is defined as a function of the selected action $a$, the current
state $s$ and the next state $s^{\prime}$, as shown in Function 4.

$R(s,a,s^{\prime})=\begin{cases}HPWL(net)&\text{if all pins are connected}\\\
cost(s)-cost(s^{\prime})&\text{otherwise}\\\ \end{cases}$ (4)

$HPWL(net)$ is the half-perimeter wirelength, the half-perimeter of the
bounding box for all pins of the current routing $net$. This design encourages
the agent to learn a path as short as possible since any unfruitful action
will cause a decrement in the cumulative reward. Additionally, we limit the
minimum total reward the agent can get when routing each net to be greater
than a minimum threshold $T_{min}=-HPWL(net)*pin\\_count(net)$. This scheme is
a useful indicator to distinguish if the overall routing problem was
successfully solved, or no feasible solution was found.

###  3.4 XRoute Benchmarks and Dashboard

The XRoute Engine is an end-to-end and flexible RL environment for detailed
routing with many features that lets researchers try a broad range of new
ideas. To facilitate fair comparisons of different algorithms and approaches
in this environment, we also provide a set of pre-defined benchmark tasks that
we call XRoute Benchmarks. The routing results are shown on XRoute Dashboard.

##### Benchmarks and metrics

XRoute Benchmarks are a versatile set of benchmark tasks of varying size and
difficulties that can be used to compare different algorithms, based on
ISPD-2018 (Mantik et al., 2018) and ISPD-2019 (Liu et al., 2019) detailed
routing testcases in our first version. These two benchmark suites have
totally 20 testcases in 65nm, 45nm, and 32nm technology nodes. The size is up
to 899404 standard cells and 895253 nets. The ISPD-2019 benchmark suite
includes more realistic routing rules compared to the ISPD-2018 benchmark
suite, which makes the testcases more challenging and closer to industrial
routing problems. Experiments are performed on these benchmark tasks with
self-defined region size. When training, the environment can be dynamically
moved to next region after pre-defined iterations.

Training agents on dynamic regions in benchmark suite can be challenging. To
allow researchers to quickly iterate on new research ideas, we provide several
static regions with various size, pin density and number of nets for routing
learning and testing. Learning converges faster in these regions. They can be
considered as “unit tests” for RL-based algorithms where one can obtain
reasonable results within minutes or hours instead of days or even weeks.
Table 1 shows the characteristics of the pre-defined static regions. We employ
a method that involves dividing the total number of nodes in each region by
the number of networks to be routed. This yields a value that describes the
sparsity of each region, which serves as one of several metrics used to
measure the difficulty of routing. Figure 3 illustrates the layout details of
the corresponding region through OpenROAD’s debugging capabilities (Ajayi et
al., 2019). We also provide APIs to define new static region according to the
requirements of researchers (See Appendix for more details).

Table 1: Static region benchmarks characteristics Benchmark | From |  | Size
---
(# GCells)
# Nets | # Pins | Sparsity |  | Position
---
(Lower-left to upper-right)
Region1 | ISPD-2018 test1 | 1x1 | 36 | 30 | 1628.40 | (199500, 245100), (205200, 250800)
Region2 | ISPD-2018 test1 | 1x1 | 49 | 51 | 1104.48 | (142500, 233700), (148200, 239400)
Region3 | ISPD-2018 test1 | 1x1 | 49 | 66 | 394.88 | (148200, 210900), (153900, 216600)
Region4 | ISPD-2019 test3 | 2x2 | 58 | 75 | 3663.60 | (138000, 132000), (144000, 138000)
Region5 | ISPD-2019 test3 | 2x2 | 67 | 101 | 2484.00 | (96000, 186000), (102000, 192000)
Region6 | ISPD-2019 test3 | 2x2 | 73 | 122 | 1994.33 | (108000, 186000), (114000, 192000)
Region7 | ISPD-2018 test5 | 3x3 | 63 | 124 | 1245.56 | (1566000, 639000), (1575000, 648000)
Region8 | ISPD-2018 test5 | 3x3 | 55 | 127 | 846.82 | (1332000, 1224000), (1341000, 1233000)
Region9 | ISPD-2019 test7 | 3x3 | 133 | 285 | 765.74 | (612000, 1314000), (621000, 1323000)
Region10 | ISPD-2019 test7 | 3x3 | 137 | 281 | 651.61 | (648000, 1386000), (657000, 1395000)
Figure 3: Detailed layout of pre-defined static regions.

We evaluate two widely used RL algorithms on part of the XRoute Benchmarks,
providing a set of reference results for future comparison. We follow the
ISPD-2019 detailed routing contest (Liu et al., 2019) to evaluate the
performance of different routers by total wirelength, vias used, design rule
violations, and runtime.

##### Dashboard

XRoute Dashboard is designed to visually present the detailed routing results
such as wirelength, vias used, design rule violations and many other routing
evaluation indicators in a dashboard during model validation. It collect the
routing logs and results and present those data with summary tables and trend
graphs as Figure 4 shows. We also integrate the results from a commercial
routing tools.

(a) Summary table of routing results

(b) Trend graph of routing metrics

Figure 4: A summary table and a trend graph in XRoute Dashboard

##  4 Experiment and results

###  4.1 Environment setup and baseline

We separate the XRoute Environment and XRoute Training (or RL-based agent)
into different processes in a Linux server. Researchers can distribute these
processes into separate servers. For net ordering task, A*-search algorithm is
used for routing a net in Routing Simulator after the net is recommended by
the RL agent. We partition the chip into regions with different sizes such as
$1\times 1$, $2\times 2$, or $3\times 3$ GCells. A 3D grid graph of the region
is created based on the previous routed environment before routing each net in
the region. We then route the nets on this grid during training and
evaluation. During training, the hyperparameters (See Appendix for more
details) of net ordering task is defined and the network is trained by
processing the same region several times. Then the training dynamically switch
to a next region with different layouts and netlists in the same testcase. We
use the final network checkpoint generated by the training process for
evaluation. We evaluate the agent on part of XRoute Benchmarks. The baselines
for comparison include TritonRoute, DQN (Mnih et al., 2015) and PPO (Schulman
et al., 2017). TritonRoute is the known-best academic routers for detailed
routing, while DQN and PPO are widely used RL algorithms.

We conduct all experiments on a Linux server with a 40-core Intel Xeon CPU
E5-2650 at 2.3 GHz and 240 GB shared memory, equipped with 2 NVIDIA GeForce
GTX Titan XP GPU with totally 24 GB video memory.

###  4.2 Agent architecture

We modify the state transformation of PPO and DQN to address the challenge of
inconsistent dimensions of the 3D grid state. We transform the original 3D
grid state and each action to a fixed vector with $s$ dimensions (we use 64 in
our experiments) by 3D convolution. For DQN implementation, we set the $Q$
function as a 2-layer fully connected network, with 128 and 64 hidden units in
each layer. Each layer is followed by an exponential linear unit function. The
input size of the $Q$ function is $s*2$, and the output size is 1. For actor-
critic style PPO, our actor function has the same parameter architecture as
the above $Q$ function. While the critic function consists of 2 fully
connected layers with 64 hidden units in each layer. Each layer is followed by
a hyperbolic tangent function. The input size of the critic function is $s$,
and the output size is 1.

Detailed architecture and hyperparameters of DQN and PPO is presented in
Appendix.

###  4.3 Experimental results

We trained the PPO and DQN model on every $1\times 1$ GCell region of test1 in
ISPD-2018 benchmark suite. There are totally 4556 different $1\times 1$ GCell
regions in the testcase and both of the self-routing process of PPO and DQN
traversed all regions. After 4600 training episodes, we use the trained model
to route ISPD-2018 test1 with region size of $1\times 1$. We compare the
performance of TritonRoute (with queue-based ripup and reroute in each
region), PPO, and DQN on wirelength, vias used, design rule violations in
Table 2. We find that the well trained PPO has less design rule violations
than TritonRoute after 40 routing iterations. We also use the trained model of
PPO and DQN to route the 10 pre-defined static regions and the results are
shown in Figure 5. It shows that TritonRoute (with queue-based ripup and
reroute in static regions) performs best in most of the static regions.
However, the well trained PPO in Region5 and Region7 and DQN in Region5
perform better for almost all metrics except the runtime. It means RL-based
algorithms may be used in detailed routing for large scale chips if we have
proper training environments. More experimental results are shown in Appendix.

Table 2: Comparison of metrics for ISPD-2018 test1 with region size of $1\times 1$ GCell between TritonRoute (TR), PPO and DQN Iteration |  Wirelength $(DBU)$ |  | Vias used |  | DRV count |  |  Runtime $(s)$
---|---|---|---|---|---|---|---
TR | PPO | DQN |  | TR | PPO | DQN |  | TR | PPO | DQN |  | TR | PPO | DQN
0th | 92689 | 92820 | 92842 |  | 41254 | 40372 | 40365 |  | 3162 | 5027 | 5057 |  | 28 | 1539 | 12806
10th | 92378 | 92351 | 92356 |  | 42175 | 42691 | 42433 |  | 206 | 240 | 261 |  | 7 | 321 | 2029
20th | 92344 | 92372 | 92357 |  | 42253 | 42792 | 42517 |  | 169 | 182 | 196 |  | 5 | 259 | 1707
30th | 92347 | 92379 | 92369 |  | 42223 | 42801 | 42497 |  | 158 | 163 | 163 |  | 5 | 220 | 1478
40th | 92346 | 92381 | 92370 |  | 42215 | 42792 | 42506 |  | 157 | 156 | 157 |  | 5 | 186 | 1330
50th | 92349 | 92388 | 92375 |  | 42209 | 42829 | 42504 |  | 150 | 143 | 145 |  | 16 | 175 | 1258
60th | 92353 | 92387 | 92378 |  | 42205 | 42800 | 42475 |  | 125 | 122 | 126 |  | 26 | 132 | 1026
final | 92353 | 92387 | 92378 |  | 42205 | 42800 | 42475 |  | 125 | 121 | 126 |  | 26 | 125 | 993
Figure 5: Comparison of metrics for ten static regions between TritonRoute
(TR), PPO and DQN

##  5 Conclusion and future work

In this paper, we presented the XRoute Environment, a novel open-source
reinforcement learning environment for VLSI detailed routing. It is
challenging, easy to use, customize and add additional scenarios, and it has
specific functionality geared towards research in reinforcement learning. We
provided the XRoute Engine, a highly optimized C++ routing simulator; the
XRoute Benchmarks, a set of reference tasks to compare different reinforcement
learning algorithms; the XRoute Dashboard, a dashboard to present the detailed
routing results such as wirelength, vias used and design rule violations
during model validation. We expect that these components will be useful for
investigating current scientific challenges in VLSI detailed routing. We
present two tasks for learning to improve the quality and efficient of
detailed routing. One is net ordering, the other is net routing. We can follow
the same way to define new more routing reinforcement learning tasks.

In the future, it would be interesting to investigate: 1) adding more RL tasks
such as pin access analysis, design rules violation prediction and fixing, net
ordering and net routing for global routing; 2) building more planning-based
learning approaches Shen et al. (2020); Zhuo and Kambhampati (2017); Zhuo and
Yang (2014); Zhuo et al. (2014, 2010) to further help routing with novel
planning techniques Jin et al. (2022a); 3) adding more benchmarks from
industrial chips and RL baseline algorithms for performance comparison; 4)
accelerating the training and validating process in our routing environment.

## References

  * Ajayi et al. [2019] Tutu Ajayi, Vidya A. Chhabria, Mateus Fogaça, Soheil Hashemi, Abdelrahman Hosny, Andrew B. Kahng, Minsoo Kim, Jeongsup Lee, Uday Mallappa, Marina Neseem, Geraldo Pradipta, Sherief Reda, Mehdi Saligane, Sachin S. Sapatnekar, Carl Sechen, Mohamed Shalan, William Swartz, Lutong Wang, Zhehong Wang, Mingyu Woo, and Bangqi Xu.  Toward an open-source digital flow: First learnings from the openroad project.  In _Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019, Las Vegas, NV, USA, June 02-06, 2019_ , page 76. ACM, 2019\.  doi: 10.1145/3316781.3326334.  URL https://doi.org/10.1145/3316781.3326334.
  * Brockman et al. [2016] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  Openai gym, 2016.
  * Chen et al. [2020a] Gengjie Chen, Chak-Wa Pui, Haocheng Li, and Evangeline F. Y. Young.  Dr. cu: Detailed routing by sparse grid graph and minimum-area-captured path search.  _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 39(9):1902–1915, 2020a.  doi: 10.1109/TCAD.2019.2927542.
  * Chen et al. [2020b] Gengjie Chen, Chak-Wa Pui, Haocheng Li, and Evangeline F. Y. Young.  Dr. CU: detailed routing by sparse grid graph and minimum-area-captured path search.  _IEEE Trans. Comput. Aided Des. Integr. Circuits Syst._ , 39(9):1902–1915, 2020b.  doi: 10.1109/TCAD.2019.2927542.  URL https://doi.org/10.1109/TCAD.2019.2927542.
  * Cheng et al. [2022] Ruoyu Cheng, Xianglong Lyu, Yang Li, Junjie Ye, Jianye Hao, and Junchi Yan.  The policy-gradient placement and generative routing neural networks for chip design.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 26350–26362. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/a8b8c1ad51df1b93d9e3d1fca75debbf-Paper-Conference.pdf.
  * Gandhi et al. [2019] Upma Gandhi, Ismail Bustany, William Swartz, and Laleh Behjat.  A reinforcement learning-based framework for solving physical design routing problem in the absence of large test sets.  In _2019 ACM/IEEE 1st Workshop on Machine Learning for CAD (MLCAD)_ , pages 1–6, 2019.  doi: 10.1109/MLCAD48534.2019.9142109.
  * Guadarrama et al. [2021] Sergio Guadarrama, Summer Yue, Toby Boyd, Joe Wenjie Jiang, Ebrahim Songhori, Terence Tam, and Azalia Mirhoseini.  Circuit Training: An open-source framework for generating chip floor plans with distributed deep reinforcement learning.  https://github.com/google_research/circuit_training, 2021.  URL https://github.com/google_research/circuit_training.  [Online; accessed 21-December-2021].
  * He et al. [2022] Youbiao He, Hebi Li, Tian Jin, and Forrest Sheng Bao.  Circuit routing using monte carlo tree search and deep reinforcement learning.  In _2022 International Symposium on VLSI Design, Automation and Test (VLSI-DAT)_ , pages 1–5, 2022.  doi: 10.1109/VLSI-DAT54769.2022.9768074.
  * Jin et al. [2022a] Kebing Jin, Hankz Hankui Zhuo, Zhanhao Xiao, Hai Wan, and Subbarao Kambhampati.  Gradient-based mixed planning with symbolic and numeric action parameters.  _Artif. Intell._ , 313:103789, 2022a.  doi: 10.1016/j.artint.2022.103789.  URL https://doi.org/10.1016/j.artint.2022.103789.
  * Jin et al. [2022b] Mu Jin, Zhihao Ma, Kebing Jin, Hankz Hankui Zhuo, Chen Chen, and Chao Yu.  Creativity of AI: automatic symbolic option discovery for facilitating deep reinforcement learning.  In _Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022_ , pages 7042–7050. AAAI Press, 2022b.  URL https://ojs.aaai.org/index.php/AAAI/article/view/20663.
  * Ju et al. [2021] Xuhua Ju, Konglin Zhu, Yibo Lin, and Lin Zhang.  Asynchronous multi-nets detailed routing in vlsi using multi-agent reinforcement learning.  In _2021 7th IEEE International Conference on Network Intelligence and Digital Content (IC-NIDC)_ , pages 250–254, 2021.  doi: 10.1109/IC-NIDC54101.2021.9660569.
  * Kahng et al. [2020] Andrew B. Kahng, Lutong Wang, and Bangqi Xu.  The tao of PAO: anatomy of a pin access oracle for detailed routing.  In _57th ACM/IEEE Design Automation Conference, DAC 2020, San Francisco, CA, USA, July 20-24, 2020_ , pages 1–6. IEEE, 2020.  doi: 10.1109/DAC18072.2020.9218532.  URL https://doi.org/10.1109/DAC18072.2020.9218532.
  * Kahng et al. [2021] Andrew B. Kahng, Lutong Wang, and Bangqi Xu.  Tritonroute: The open-source detailed router.  _IEEE Trans. Comput. Aided Des. Integr. Circuits Syst._ , 40(3):547–559, 2021.  doi: 10.1109/TCAD.2020.3003234.  URL https://doi.org/10.1109/TCAD.2020.3003234.
  * Kahng et al. [2022] Andrew B. Kahng, Lutong Wang, and Bangqi Xu.  Tritonroute-WXL: The Open-Source Router With Integrated DRC Engine.  _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 41(4):1076–1089, 4 2022.
  * Liao et al. [2019] Haiguang Liao, Wentai Zhang, Xuliang Dong, Barnabas Poczos, Kenji Shimada, and Levent Burak Kara.  A Deep Reinforcement Learning Approach for Global Routing.  _Journal of Mechanical Design_ , 142(6), 11 2019.  ISSN 1050-0472.  doi: 10.1115/1.4045044.  URL https://doi.org/10.1115/1.4045044.  061701\.
  * Lin et al. [2022] Yibo Lin, Tong Qu, Zongqing Lu, Yajuan Su, and Yayi Wei.  Asynchronous reinforcement learning framework and knowledge transfer for net-order exploration in detailed routing.  _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 41(9):3132–3142, 2022.  doi: 10.1109/TCAD.2021.3117505.
  * Liu et al. [2021] Jinwei Liu, Gengjie Chen, and Evangeline F. Y. Young.  REST: constructing rectilinear steiner minimum tree via reinforcement learning.  In _58th ACM/IEEE Design Automation Conference, DAC 2021, San Francisco, CA, USA, December 5-9, 2021_ , pages 1135–1140. IEEE, 2021.  doi: 10.1109/DAC18074.2021.9586209.  URL https://doi.org/10.1109/DAC18074.2021.9586209.
  * Liu et al. [2013] Wen-Hao Liu, Wei-Chun Kao, Yih-Lang Li, and Kai-Yuan Chao.  NCTU-GR 2.0: Multithreaded collision-aware global routing with bounded-length maze routing.  _IEEE Trans. Comput. Aided Des. Integr. Circuits Syst._ , 32(5):709–722, 2013.  doi: 10.1109/TCAD.2012.2235124.  URL https://doi.org/10.1109/TCAD.2012.2235124.
  * Liu et al. [2019] Wen-Hao Liu, Stefanus Mantik, Wing-Kai Chow, Yixiao Ding, Amin Farshidi, and Gracieli Posser.  Ispd 2019 initial detailed routing contest and benchmark with advanced routing rules.  ISPD ’19, page 147–151, New York, NY, USA, 2019. Association for Computing Machinery.  ISBN 9781450362535.  doi: 10.1145/3299902.3311067.  URL https://doi.org/10.1145/3299902.3311067.
  * Mantik et al. [2018] Stefanus Mantik, Gracieli Posser, Wing-Kai Chow, Yixiao Ding, and Wen-Hao Liu.  Ispd 2018 initial detailed routing contest and benchmarks.  ISPD ’18, page 140–143, New York, NY, USA, 2018. Association for Computing Machinery.  ISBN 9781450356268.  doi: 10.1145/3177540.3177562.  URL https://doi.org/10.1145/3177540.3177562.
  * Mirhoseini et al. [2021] Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, Jiwoo Pak, Andy Tong, Kavya Srinivasa, William Hang, Emre Tuncer, Quoc V. Le, James Laudon, Richard Ho, Roger Carpenter, and Jeff Dean.  A graph placement methodology for fast chip design.  _Nature_ , 594(7862):207–212, June 2021.  ISSN 1476-4687.  doi: 10.1038/s41586-021-03544-w.  URL https://doi.org/10.1038/s41586-021-03544-w.
  * Mnih et al. [2015] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, February 2015.  ISSN 1476-4687.  doi: 10.1038/nature14236.  URL https://doi.org/10.1038/nature14236.
  * Park et al. [2019] Dongwon Park, Ilgweon Kang, Yeseong Kim, Sicun Gao, Bill Lin, and Chung-Kuan Cheng.  ROAD: routability analysis and diagnosis framework based on SAT techniques.  In Ismail Bustany and William Swartz, editors, _Proceedings of the 2019 International Symposium on Physical Design, ISPD 2019, San Francisco, CA, USA, April 14-17, 2019_ , pages 65–72. ACM, 2019.  doi: 10.1145/3299902.3309752.  URL https://doi.org/10.1145/3299902.3309752.
  * Ren and Fojtik [2021] Haoxing Ren and Matthew Fojtik.  Standard cell routing with reinforcement learning and genetic algorithm in advanced technology nodes.  In _2021 26th Asia and South Pacific Design Automation Conference (ASP-DAC)_ , pages 684–689, 2021.
  * Schulman et al. [2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms, 2017.
  * Shen et al. [2020] Junyi Shen, Hankz Hankui Zhuo, Jin Xu, Bin Zhong, and Sinno Jialin Pan.  Transfer value iteration networks.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pages 5676–5683. AAAI Press, 2020.  URL https://ojs.aaai.org/index.php/AAAI/article/view/6022.
  * Sutton and Barto [2018] Richard S. Sutton and Andrew G. Barto.  _Reinforcement Learning: An Introduction. second edition_.  A Bradford Book, Cambridge, MA, USA, 2018.  ISBN 0262039249.
  * Zhuo and Kambhampati [2017] Hankz Hankui Zhuo and Subbarao Kambhampati.  Model-lite planning: Case-based vs. model-based approaches.  _Artif. Intell._ , 246:1–21, 2017.  doi: 10.1016/j.artint.2017.01.004.  URL https://doi.org/10.1016/j.artint.2017.01.004.
  * Zhuo and Yang [2014] Hankz Hankui Zhuo and Qiang Yang.  Action-model acquisition for planning via transfer learning.  _Artif. Intell._ , 212:80–103, 2014.  doi: 10.1016/j.artint.2014.03.004.  URL https://doi.org/10.1016/j.artint.2014.03.004.
  * Zhuo et al. [2010] Hankz Hankui Zhuo, Qiang Yang, Derek Hao Hu, and Lei Li.  Learning complex action models with quantifiers and logical implications.  _Artif. Intell._ , 174(18):1540–1569, 2010.  doi: 10.1016/j.artint.2010.09.007.  URL https://doi.org/10.1016/j.artint.2010.09.007.
  * Zhuo et al. [2014] Hankz Hankui Zhuo, Héctor Muñoz-Avila, and Qiang Yang.  Learning hierarchical task network domains from partially observed plan traces.  _Artif. Intell._ , 212:134–157, 2014.  doi: 10.1016/j.artint.2014.04.003.  URL https://doi.org/10.1016/j.artint.2014.04.003.


* [101] M. Lu, J. Liang, Y. Zhang, G. Li, S. Chen, Z. Li, and X. Yuan, ‘‘Interaction+: Interaction enhancement for web-based visualizations,’’ in _Proc. of the IEEE Pacific Visualization Symposium (PacificVis)_. IEEE, 2017, pp. 61--70.
  * [102] W. Huang, R. Liu, and C.-L. Tan, ‘‘Extraction of vectorized graphical information from scientific chart images,’’ in _Proc. of the International Conference on Document Analysis and Recognition (ICDAR)_ , vol. 1. IEEE, 2007, pp. 521--525.
  * [103] J. Poco, A. Mayhua, and J. Heer, ‘‘Extracting and retargeting color mappings from bitmap images of visualizations,’’ _IEEE Transactions on Visualization and Computer Graphics_ , vol. 24, no. 1, pp. 637--646, 2017.
  * [104] W. Browuer, S. Kataria, S. Das, P. Mitra, and C. L. Giles, ‘‘Segregating and extracting overlapping data points in two-dimensional plots,’’ in _Proc. of the ACM/IEEE-CS joint conference on Digital libraries_ , 2008, pp. 276--279.
  * [105] S. Ray Choudhury, S. Wang, and C. L. Giles, ‘‘Curve separation for line graphs in scholarly documents,’’ in _Proc. of the ACM/IEEE-CS on Joint Conference on Digital Libraries_ , 2016, pp. 277--278.
  * [106] C. Bryan, K.-L. Ma, and J. Woodring, ‘‘Temporal summary images: An approach to narrative visualization via interactive annotation generation and placement,’’ _IEEE Transactions on Visualization and Computer Graphics_ , vol. 23, no. 1, pp. 511--520, 2016.
  * [107] R. Savvides, A. Henelius, E. Oikarinen, and K. Puolamäki, ‘‘Significance of patterns in data visualisations,’’ in _Proc. of the ACM International Conference on Knowledge Discovery & Data Mining (KDD)_, 2019, pp. 1509--1517.
  * [108] D. J.-L. Lee, H. Dev, H. Hu, H. Elmeleegy, and A. Parameswaran, ‘‘Avoiding drill-down fallacies with vispilot: assisted exploration of data subsets,’’ in _Proc. of the International Conference on Intelligent User Interfaces (IUI)_ , 2019, pp. 186--196.
  * [109] J. Gao, Y. Zhou, and K. E. Barner, ‘‘View: Visual information extraction widget for improving chart images accessibility,’’ in _Proc. of the International Conference on Image Processing_. IEEE, 2012, pp. 2865--2868.
  * [110] Z. Chen, Y. Wang, Q. Wang, Y. Wang, and H. Qu, ‘‘Towards automated infographic design: Deep learning-based auto-extraction of extensible timeline,’’ _IEEE Transactions on Visualization and Computer Graphics_ , vol. 26, no. 1, pp. 917--926, 2019.
  * [111] R. A. Al-Zaidy and C. L. Giles, ‘‘A machine learning approach for semantic structuring of scientific charts in scholarly documents.’’ in _Proc. of the Conference on Artificial Intelligence (AAAI)_ , 2017, pp. 4644--4649.
  * [112] V. S. N. Prasad, B. Siddiquie, J. Golbeck, and L. S. Davis, ‘‘Classifying computer generated charts,’’ in _Proc. of the International Workshop on Content-Based Multimedia Indexing_. IEEE, 2007, pp. 85--92.
  * [113] R. A. Al-Zaidy, S. R. Choudhury, and C. L. Giles, ‘‘Automatic summary generation for scientific data charts,’’ in _Proc. of the Conference on Artificial Intelligence (AAAI)_. AI Access Foundation, 2016, pp. 658--663.
  * [114] G. G. Méndez, M. A. Nacenta, and S. Vandenheste, ‘‘ivolver: Interactive visual language for visualization extraction and reconstruction,’’ in _Proc. of the ACM Conference on Human Factors in Computing Systems (CHI)_ , 2016, pp. 4073--4085.
  * [115] D. Jung, W. Kim, H. Song, J.-i. Hwang, B. Lee, B. Kim, and J. Seo, ‘‘Chartsense: Interactive data extraction from chart images,’’ in _Proc. of the ACM Conference on Human Factors in Computing Systems (CHI)_ , 2017, pp. 6706--6717.
  * [116] D. McCandless, _Information is Beautiful_. Scotland, UK: Collins, 2009.
  * [117] S. Kandel, R. Parikh, A. Paepcke, J. M. Hellerstein, and J. Heer, ‘‘Profiler: Integrated statistical analysis and visualization for data quality assessment,’’ in _Proc. of the International Working Conference on Advanced Visual Interfaces (AVI)_ , 2012, pp. 547--554.
  * [118] P.-M. Law, R. C. Basole, and Y. Wu, ‘‘Duet: Helping data analysis novices conduct pairwise comparisons by minimal specification,’’ _IEEE Transactions on Visualization and Computer Graphics_ , vol. 25, no. 1, pp. 427--437, 2018.
  * [119] Y. Kim, K. Wongsuphasawat, J. Hullman, and J. Heer, ‘‘Graphscape: A model for automated reasoning about visualization similarity and sequencing,’’ in _Proc. of the ACM Conference on Human Factors in Computing Systems (CHI)_ , 2017, pp. 2628--2638.
  * [120] Y. Ma, A. K. Tung, W. Wang, X. Gao, Z. Pan, and W. Chen, ‘‘Scatternet: A deep subjective similarity model for visual analysis of scatterplots,’’ _IEEE Transactions on Visualization and Computer Graphics_ , vol. 26, no. 3, pp. 1562--1576, 2018.
  * [121] L. Cerulo and G. Canfora, ‘‘A taxonomy of information retrieval models and tools,’’ _Journal of Computing and Information Technology_ , vol. 12, no. 3, pp. 175--194, 2004.
  * [122] A. Srinivasan, S. M. Drucker, A. Endert, and J. Stasko, ‘‘Augmenting visualizations with interactive data facts to facilitate interpretation and communication,’’ _IEEE Transactions on Visualization and Computer Graphics_ , vol. 25, no. 1, pp. 672--681, 2018.
  * [123] Z. Li, S. Carberry, H. Fang, K. F. McCoy, and K. Peterson, ‘‘Infographics retrieval: A new methodology,’’ in _Proc. of the International Conference on Applications of Natural Language to Data Bases/Information Systems_. Springer, 2014, pp. 101--113.
  * [124] Z. Li, S. Carberry, H. Fang, K. F. McCoy, K. Peterson, and M. Stagitis, ‘‘A novel methodology for retrieving infographics utilizing structure and message content,’’ _Data & Knowledge Engineering_, vol. 100, pp. 191--210, 2015\.
  * [125] M. Wattenberg, ‘‘Sketching a graph to query a time-series database,’’ in _Proc. of the Extended Abstracts on Human factors in Computing Systems_ , 2001, pp. 381--382.
  * [126] C. Fan, K. Matkovic, and H. Hauser, ‘‘Sketch-based fast and accurate querying of time series using parameter-sharing lstm networks,’’ _IEEE Transactions on Visualization and Computer Graphics_ , 2020 (Early Access).
  * [127] V. O. Mittal, J. D. Moore, G. Carenini, and S. Roth, ‘‘Describing complex charts in natural language: A caption generation system,’’ _Computational Linguistics_ , vol. 24, no. 3, pp. 431--467, 1998.
  * [128] Z. Cui, S. K. Badam, M. A. Yalçin, and N. Elmqvist, ‘‘Datasite: Proactive visual data exploration with computation of insight-based recommendations,’’ _Information Visualization_ , vol. 18, no. 2, pp. 251--267, 2019.
  * [129] S. Demir, S. Carberry, and K. F. McCoy, ‘‘Summarizing information graphics textually,’’ _Computational Linguistics_ , vol. 38, no. 3, pp. 527--574, 2012\.
  * [130] C. Liu, L. Xie, Y. Han, , D. Wei, and X. Yuan, ‘‘Autocaption: An approach to generate natural language description from visualization automatically,’’ in _Proc. of the IEEE Pacific Visualization Symposium (PacificVis)_. IEEE, 2020, pp. 191--195.
  * [131] W. S. Cleveland and R. McGill, ‘‘Graphical perception: Theory, experimentation, and application to the development of graphical methods,’’ _Journal of the American Statistical Association_ , vol. 79, no. 387, pp. 531--554, 1984.
  * [132] C. Demiralp, P. J. Haas, S. Parthasarathy, and T. Pedapati, ‘‘Foresight: Recommending visual insights,’’ _Proc. of the VLDB Endowment_ , vol. 10, no. 12, 2017.
  * [133] R. Ding, S. Han, Y. Xu, H. Zhang, and D. Zhang, ‘‘Quickinsights: Quick and automatic discovery of insights from multi-dimensional data,’’ in _Proc. of the International Conference on Management of Data (SIGMOD)_ , 2019, pp. 317--332.
  * [134] J. Mackinlay, P. Hanrahan, and C. Stolte, ‘‘Show me: Automatic presentation for visual analysis,’’ _IEEE Transactions on Visualization and Computer Graphics_ , vol. 13, no. 6, pp. 1137--1144, 2007.
  * [135] R. Ananthanarayanan, P. K. Lohia, and S. Bedathur, ‘‘Datavizard: Recommending visual presentations for structured data,’’ in _Proc. of the International Workshop on the Web and Databases_ , 2018, pp. 1--6.
  * [136] A. Narechania, A. Srinivasan, and J. Stasko, ‘‘Nl4dv: A toolkit for generating analytic specifications for data visualization from natural language queries,’’ _IEEE Transactions on Visualization and Computer Graphics_ , 2020 (Early Access).
  * [137] F. Bouali, A. Guettala, and G. Venturini, ‘‘Vizassist: an interactive user assistant for visual data mining,’’ _The Visual Computer_ , vol. 32, no. 11, pp. 1447--1463, 2016.
  * [138] Z. Chen, W. Tong, Q. Wang, B. Bach, and H. Qu, ‘‘Augmenting static visualizations with paparvis designer,’’ in _Proc. of the ACM Conference on Human Factors in Computing Systems (CHI)_ , 2020, pp. 1--12.
  * [139] B. Yu and C. T. Silva, ‘‘Flowsense: A natural language interface for visual data exploration within a dataflow system,’’ _IEEE Transactions on Visualization and Computer Graphics_ , vol. 26, no. 1, pp. 1--11, 2019.
  * [140] T. N. Dang and L. Wilkinson, ‘‘Scagexplorer: Exploring scatterplots by their scagnostics,’’ in _Proc. of the IEEE Pacific Visualization Symposium (PacificVis)_. IEEE, 2014, pp. 73--80.
  * [141] T. N. Dang, A. Anand, and L. Wilkinson, ‘‘Timeseer: Scagnostics for high-dimensional time series,’’ _IEEE Transactions on Visualization and Computer Graphics_ , vol. 19, no. 3, pp. 470--483, 2012.
  * [142] A. Wu, L. Xie, B. Lee, Y. Wang, W. Cui, and H. Qu, ‘‘Learning to automate chart layout configurations using crowdsourced paired comparison,’’ _arXiv preprint arXiv:2101.03680_ , 2021.
  * [143] L.-P. Yuan, Z. Zhou, J. Zhao, Y. Guo, F. Du, and H. Qu, ‘‘Infocolorizer: Interactive recommendation of color palettes for infographics,’’ _arXiv preprint arXiv:2102.02041_ , 2021.
  * [144] C. Fan and H. Hauser, ‘‘Fast and accurate cnn-based brushing in scatterplots,’’ in _Computer Graphics Forum_ , vol. 37, no. 3. Wiley Online Library, 2018, pp. 111--120.
  * [145] S. Lallé, D. Toker, C. Conati, and G. Carenini, ‘‘Prediction of users’ learning curves for adaptation while using an information visualization,’’ in _Proc. of the International Conference on Intelligent User Interfaces (IUI)_ , 2015, pp. 357--368.
  * [146] Z. Chen, W. Zeng, Z. Yang, L. Yu, C.-W. Fu, and H. Qu, ‘‘Lassonet: Deep lasso-selection of 3d point clouds,’’ _IEEE Transactions on Visualization and Computer Graphics_ , vol. 26, no. 1, pp. 195--204, 2019.
  * [147] Y. Wang, Z. Jin, Q. Wang, W. Cui, T. Ma, and H. Qu, ‘‘Deepdrawing: A deep learning approach to graph drawing,’’ _IEEE transactions on visualization and computer graphics_ , vol. 26, no. 1, pp. 676--686, 2019.

Aoyu Wu is a Ph.D. student in the Department of Computer Science and
Engineering at the Hong Kong University of Science and Technology (HKUST). He
received his B.E. and M.E. degrees from HKUST. His research interests include
data visualization and human-computer interaction. For more details, please
refer to http://awuac.student.ust.hk/.
---
Yun Wang received the BEng degree from Fudan University, and the PhD degree in
computer science and engineering from the Hong Kong University of Science and
Technology. She is a senior researcher at Microsoft Research. Her research
interests are in data storytelling and visual data analytics. She has
published papers extensively in IEEE VIS, the IEEE Transactions on
Visualization and Computer Graphics, ACM CHI, etc. For more information,
please visit https://www.microsoft.com/en-us/research/people/wangyun/.
---
Xinhuan Shu is currently a Ph.D. candidate in the Department of Computer
Science and Engineering at the Hong Kong University of Science and Technology
(HKUST). She received her B.E.degree in Computer Science and Technology from
Zhejiang University, China in 2017. Her research interests include data-driven
storytelling, animated visualization, and visual analytics. For more details,
please visit https://shuxinhuan.github.io/.
---
Dominik Moritz is a professor at Carnegie Mellon University’s Human-Computer
Interaction Institute and a researcher at Apple. He has a PhD in Computer
Science from the University of Washington. At CMU, he co-leads the Data
Interaction Group. Dominik enhances people’s ability to understand and
communicate large and complex data with methods that integrate the
capabilities of both people and machines. His website is at
https://www.domoritz.de/.
---
Weiwei Cui received the BS degree in computer science and technology from
Tsinghua University, China, and the PhD degree in computer science and
engineering from the Hong Kong University of Science and Technology, Hong
Kong. He is a principal researcher at Microsoft Research Asia, China. His
primary research interest is visualization, with the focuses on democratizing
visualization and AI-assisted design. For more information, please visit
https://www.microsoft.com/en-us/research/people/weiweicu/.
---
Haidong Zhang received the PhD degree in Computer Science from Peking
University, China. He is a Principal Architect at Microsoft Research Asia. His
research interests include visualization and human-computer interaction.
---
Dongmei Zhang received the BE degree and ME degree from Tsinghua University,
and PhD degree in Robotics from the School of Computer Science at Carnegie
Mellon University. She is a Distinguished Scientist and Assistant Managing
Director at Microsoft Research Asia, leading research in the area of Data,
Knowledge, and Intelligence with research directions in data intelligence,
knowledge computing, information visualization, and software engineering. For
more information, please visit https://www.microsoft.com/en-
us/research/people/dongmeiz/.
---
Huamin Qu is a professor in the Department of Computer Science and Engineering
(CSE) at the Hong Kong University of Science and Technology (HKUST) and also
the director of the interdisciplinary program office (IPO) of HKUST. He
obtained a BS in Mathematics from Xi’an Jiaotong University, China, an MS and
a PhD in Computer Science from the Stony Brook University. His main research
interests are in visualization and human-computer interaction, with focuses on
urban informatics, social network analysis, E-learning, text visualization,
and explainable artificial intelligence (XAI).
---