Paper summary: geomertic deep learning in VLSI

Preliminaries

Geometric deep learning means the deep learning especially for geometric objects, such as graphs and point clouds. Recently, their applications in VLSI become more and more common and important for several reasons (from my naive perspectives):

1. most study objects in VLSI are natually geometcal. e.g. netlist -> graph, layout pins -> point cloud, …
2. there exist many heuristical algorithms in VLSI domain, whcih provides a vision for DL techniques to improve them
3. We have enough data in the industry, now-adays, the data scale is in a billion level.

This artical is a summray of all related papers I read.

GNN-RE: Graph Neural Networks for Reverse Engineering of Gate-Level Netlists

Task

1. identify the boundaries between the modules or sub-circuits implemented in netlists (still node-classification)
2. classify the sub-circuits based on their functionalities. (still node-classification, not a graph-classification, but use the node labeling results to vote for the graph labeling)

The two steps are in the flow of reverse engineering

reverse engineering is to obatin the circuit information (netlist, sub-circuit functions …) from the sold IC chip.

Methods

1. Netlist -> undirected graph.

2. Feature vectors (for each node):

   1. connectivity to PIs/POs
   2. Fan-in/fan-out degree
   3. gate’s + neighboring (2-hops) functionality (# of AND = 3, # of ORs = 2 (depth) … and so on)
   4. binary value: is sequential or combinational
   5. binary value: whether a gate is controlled by a KeyInput or not

   I doubt these feature vectors may represent the original netlist with some potential bias information. That is, two different netlists may generate the same graph with same feature vectors. (Especially their type c features)

3. graph sampling (a large netlist graph to many sub-graphs): GraphSAINT, random walk sampler (RWS).

   1. Basic idea, select $r$ roots (randomly), and start from these roots, randomly walk $w$ steps and sample these nodes.

4. Models: after experiments, RWS sampling + GAT is used

Result

• Hidden dim : 256 > 128,512
• depth: 2 > 1,4
• # of GNN layers? (it seems that they use depth as the neighborhood depth per layer…)
• GAT > GraphSAGE, GAAN… (they use GraphSAGE to determine the beset arguments, like depth, dim, but finally select a different model without changing these arguments??)

Boundary identification

given a certain design type, (like adder-mul,mix, results of two adders are fed into a multiplexer), generate a series of such designs, (by using different kinds of adders/multiplexers), see the node classification performance.

So the experiment for industrial design and even not for a general design.

Graph Learning-Based Arithmetic Block Identification

Done by my friend :)

Task

Arithmetic Block Identification: input-flatenned netlist graph; output-arithmatic block (the same with last paper)

flattened gate-level netlist, where only primitive gates are instanced, while the design hierarchy is unknown.

Method

ABGNN

1. Bidirectional: consider both message flow from predecessors(fanin) and successfulsors(fanout).
2. Asynchronous: At each step $d$ (or so-called depth of GNN), starting from those nodes whose distance is $k-d$ with the nodes (k is the total depth) and propagate through the signal direction.
3. input features: gate type
4. Output: predicts the input wires and the output wires of arithmetic blocks.

Input-output matching

we obtain an input set and an output set (by ABGNN), and we need to find the matching, i.e., a mapping from input set to output set. (formulate as a maximum flow problem)

Other techniques

• Two seperate models to predict input and output. (A node can be both input and output for different arithmatic blocks)
• Data imbalance (two many non-input and non-output)
  • oversampling (data-level)
  • Cost sensitive learning: new cost -> $C’{ij} = p(j|x)C{ij}$, the cost the cost for predicting x as class j when the actual class is i
  • penalty weight for two losses

It is intresting to see that the task is divided into two steps, where the first one is translated as a DL task while the second one is solved by some traditional beautiful algorithm.

Results

Just list some interesting parts:

• GraphSAGE is better than others, which aligns with my belief
• asynchronous is slightly better than a normal model, interesting to see why?

A graph placement methodology for fast chip design

A very famous but also controversial paper by Google

Task: floorplanning

placing netlists onto chip canvases (two-dimensional grids) so that performance metrics (for example, power consumption, timing, area and wirelength) are optimized, while adhering to hard constraints on density and routing congestion.

Basic Idea

Use GNN to obtain graph embedding, which is used to 1) generate next step instruction (as the encoder of the RL network) 2) predict the reward.

For the RL module, each action corresponds to selecting a macro and place it in the grid. Here, the macro order is determined heuristically.

Edge-GNN

• node feature: node type, width, height, x and y coordinates, and its connectivity to other nodes
• $e_{ij} = fc_e(v_i|v_j)$
• $v_i = mean_{j\in N(v_i)}(e_{ij})$
• according to the results, much better than GCN (how about bidirectional GCN?)