MacroPlacement

Proxy Cost Computation in Circuit Training

In this documentation, we use gridcell and grid interchangeably. They both mean the grid system induced by the gridding process.

In Circuit Training, proxy cost is the weighted sum of wirelength, density, and congestion costs. It is used to determine the overall quality of the macro placement solution.

Proxy Cost = W_wirelength × Cost_wirelength + W_density × Cost_density + W_congestion × Cost_congestion

Where W_wirelength, W_density and W_congestion are the weights. From the Circuit Training repo, we found that W_wirelength = 1, W_density = 1, and W_congestion = 0.5. From communication with Google engineers, we learned that in their internal flow, they use W_wirelength = 1, W_density = 0.5, and W_congestion = 0.5.

Circuit Training repo provides the plc_wrapper_main binary to compute these cost functions. There is no available detailed description, or open-source implementation, of these cost functions. With feedback and confirmations from Google engineers, we have implemented all three cost functions; the source code is available here. In the following, we provide a detailed description of the implementation of these cost functions.

Comparison with Google’s Plc_client

Testcase	Method	HPWL Cost	Density Cost	Congestion Cost
Google's Ariane	Google	0.050186608	0.756401122	0.984565650
	Our	0.050186604	0.756401122	0.984565675
Ariane-NanGate45	Google	0.387988658	0.500452106	2.448659090
	Our	0.387988659	0.500452101	2.448659182

Table of Contents

• Wirelength cost computation
• Density cost computation
• Congestion cost computation

Wirelength cost computation

The wirelength cost function depends on the net (bounding box) half-perimeter wirelength (HPWL). So, first we describe steps to compute HPWL of a net – and then we compute the wirelength cost.

Procedure to compute net HPWL

1. Initialize x_min = float_max, y_min = float_max, x_max = 0, y_max = 0
2. For each node in net
   1. x_min = min(x_min, node→x), y_min = min(y_min, node→y)
   2. x_max = max(x_max, node→x), y_max = max(y_max, node→y)
3. net_hpwl = (x_max - x_min) + (y_max - y_min)

A protobuf netlist consists of different types of nodes. Different possible types of nodes are macro, standard cell, macro pin and port. A net consists of one source node and one or more sink nodes. A net can have only standard cell, macro pin and port as its source or sink nodes. In the following wirelength cost computation procedure, we use the term net weight, which is the weight of the source node of the net. This weight indicates the total number of connections between the source and each sink node.

Procedure to compute wirelength cost

1. hpwl = 0, net_count = 0
2. For each net
   1. Compute net_hpwl using the previous procedure
   2. hpwl += net→weight × net_hpwl
   3. net_count += net→weight
3. Cost_wirelength = hpwl ⁄ [net_count × (canvas_height + canvas_width)]

In the above procedure, canvas_height is the height of the canvas and canvas_width is the width of the canvas.

Density cost computation

Density cost function depends on the gridcell density. So, first we describe the steps to compute gridcell density – and then we compute the density cost.

The gridcell density of grid (i, j) is the ratio of the summation of all the overlapped areas (the common area between the node and the grid) of standard cell and macro nodes with the grid (i, j) to the total gridcell area.

Procedure to compute density cost

1. n = number of rows × number of columns
2. k = floor(n × 0.1)
3. if k == 0
   1. k = 1
4. Cost_density = (average density of top k densest gridcells) × 0.5

Notice that 0.5 is not the “weight” of this cost function, but simply another factor applied besides the weight factor from the cost function. Google engineers informed us “ the 0.5 is there to correct the bloating of the std cell clusters”.

Congestion cost computation

We divide the congestion cost computation into six sub-stages:

1. Compute horizontal and vertical congestion of each grid due to net routing.
2. Apply smoothing only to grid congestion due to net routing.
3. Compute congestion of each grid due to macros.
4. Grid horizontal congestion = horizontal congestion due to macros + horizontal congestion due to net routing after smoothing.
5. Grid vertical congestion = vertical congestion due to macros + vertical congestion due to net routing after smoothing.
6. Finally, we concatenate the Grid horizontal congestion array and the Grid vertical congestion array and take the average of the top 5% of the concatenated list.

Computation of grid congestion due to net routing

We first want to address that the following computation is “grid-based” (not to be confused with the conventional n-pin net) derived from gridding. The main differences are instead of looking at each pin location, we only look at grid cells subject to pin locations. This implies that if all net entities (source pin and sink pins) are within the same grid cell, no routing congestion will be computed (except for macro congestions). More formally, we define a n-grid net as a net whose pins occupy n different grids. We also define the grid occupied by the source pin of a net as the source grid of the net, and remaining grids occupied by other pins of the net as sink grids. In other words, if a three-pin net has a source pin in grid g_i and two sink pins in the same grid g_j, we would consider this as a two-grid net.

Given the above grid-base routing setting, we divide this problem into three sub-problems.

1. Congestion due to two-grid nets.
2. Congestion due to three-grid nets.
3. Congestion due to multi-grid nets where the number of grids is greater than three.

A grid location (i, j) is the intersection of the i^th column with the j^th row.

For these three problems we consider that the horizontal routing cost due to a net-segment from (i, j) grid to (i+1, j) grid applies only to the grid (i, j). Similarly the vertical routing cost due to a net-segment from (i, j) grid to (i, j+1) grid applies only to the grid (i, j). Here the direction of the net does not matter.

Now we compute the congestion due to different nets:

Congestion due to two-grid nets

Two-grid net routing depends on the source and sink node. Consider

1. Source node is (i₁, j₁)
2. Sink node is (i₂, j₂)

Procedure for congestion computation due to two-grid nets

1. i_min = min(i₁, i₂), i_max = max(i₁, i₂)
2. w = net→weight
3. Add horizontal congestion cost (considering weight w) due this grid from (i_min, j₁) to (i_max-1, j₁).
4. j_min = min(j₁, j₂), j_max = max(j₁, j₂)
5. Add vertical congestion cost (considering weight w) due to this grid from (i₂, j_min) to (i₂, j_max - 1).

In the following figure P2 is the source grid and P1 is the sink grid of the net. When the arrow crosses the top edge of the grid cell it contributes to the vertical congestion cost of the grid cell and when it crosses the right edge of the grid cell it contributes to the horizontal congestion cost of the grid cell.

Congestion due to three-grid nets

The Congestion cost of three-grid nets does not change when the locations of the grids are interchanged.

In the following figure, P3 is the source and P1 and P2 are the sinks. We see that interchanging the position does not change the route.

Consider the three grid locations are (i₁, j₁), (i₂, j₂) and (i₃, j₃). We compute congestion due to three-grids using two functions:

1. L_routing
2. T_routing

In the below function all congestion cost computation takes into account the weight.

First we describe these two functions and then we describe how the congestion due to three grid nets are computed.

Congestion cost update using L_routing:

The inputs are three grid id and net weight. We consider the following grids are (i₁, j₁), (i₂, j₂) and (i₃, j₃) where i₁ < i₂ < i₃ and (j₁ < j₂ < j₃) or (j₁ > j₂ > j₃).

1. Add horizontal congestion cost due to grids from (i₁, j₁) to (i₂-1, j₁)
2. Add horizontal congestion cost due to grids from (i₂, j₂) to (i₃-1, j₂)
3. Add vertical congestion cost due to grids from (i₂, min(j₁, j₂)) to (i₂, max(j₁, j₂) - 1).
4. Add vertical congestion cost due to grids from (i₃, min(j₂, j₃)) to (i₃, max(j₂, j₃) - 1).

Congestion cost update using T_routing:

The inputs are three grid id and net weight. We consider the following grids as (i₁, j₁), (i₂, j₂) and (i₃, j₃) where (j₁ <= j₂ <= j₃ ) or (j₁ >= j₂ >= j₃).

1. i_min = min(i₁, i₂, i₃), i_max = max(i₁, i₂, i₃)
2. Add horizontal congestion cost due to grids from (i_min, j₂) to (i_max - 1, j₂).
3. Add vertical congestion cost due to grids from (i₁, min(j₁, j₂)) to (i₁, max(j₁, j₂) - 1).
4. Add vertical congestion cost due to grids from (i₃, min(j₂, j₃)) to (i₃, max(j₂, j₃) - 1).

Procedure congestion cost computation due to three-grid nets:

The inputs are three grid locations and the net weight.

1. Sort the grid based on the column. After sorting grid locations are (i₁, j₁), (i₂, j₂) and (i₃, j₃). As it is sorted based on column i₁ <= i₂ <= i₃.
2. If i₁ < i₂ and i₂ < i₃ and min(j₁, j₃) < j₂ and max(j₁, j₃) > j₂:
   1. Update congestion cost using L_routing.
   2. Return.
3. If i₂ == i₃ and i₁ < i₂ and j₁ < min(j₂, j₃):
   1. Add horizontal congestion cost due to grids from (i₁, j₁) to (i₂-1, j₁)
   2. Add vertical congestion cost due to grids from (i₂, j₁) to (i₂, max(j₂, j₃) -1)
   3. Return.
4. If j₂ == j₃:
   1. Add horizontal congestion cost due to grids from (i₁, j₁) to (i₂ -1, j₁)
   2. Add horizontal congestion cost due to grids from (i₂, j₂) to (i₃ -1, j₂)
   3. Add vertical congestion cost due to grids from (i₂, min(j₁, j₂)) to (i₂, max(j₁, j₂) - 1).
   4. Return
5. Update congestion cost using T_routing.

The following four figures represent the four cases mentioned in the above procedure from point two to point five.

Figure corresponding to point two.

Figure corresponding to point three.

Figure corresponding to point four.

Figure corresponding to point five.

Congestion due to multi-grid nets where the number of grids is greater than three

1. Consider the net is a n-grid net where n > 3.
2. We break this net using the star model into n-1 two-grid nets where the source grid is the common node.
3. For each two-grid nets we update congestion values.

Computation for Smoothing:

1. Congestion smoothing = 0.0
   1. Return the grid congestion that is due to net routing: no smoothing is applied.
2. Congestion smoothing > 0.0 = k (k is an integer; both CT and our code appear to use the floor of any non-integer smoothing value)
   1. Take grid congestion due to net routing
   2. For horizontal grid congestion
      1. For each gridcell
         1. If not out-of-bound, take k gridcells on each side (left/right), divide the current cell entry by the total number of gridcells taken and add the value to the corresponding gridcell.
   3. For vertical grid congestion
      1. For each gridcell
         1. If not out-of-bound, take k gridcells on each side (up/down), divide the current cell entry by the total number of gridcells taken and add the value to the corresponding gridcell.
   4. For example, suppose that smoothing = 2 (default value), and we apply it to horizontal grid congestion in four rows of gridcells with respect to the red gridcell highlighted in each row. Then, the blue gridcells in each row show the numbers of gridcells that we divide by (respectively from the top row to the bottom row: 3, 4, 5, 4) when smoothing congestion.

Computation for Macro Congestion:

Macro congestion is induced by the location of hard macros over the grid cells. For each hard macro, we need to consider its dimension of overlapping over the grid cells and the macro routing resources given. The computation of macro congestion is quite straightforward. We just need to add the rout- ing resources blocked by the macros to the corresponding boundaries of the gridcells.

When a macro overlaps with multiple gridcells, if any part of the module partially overlaps with the grid cell (either vertically, or horizontally), we set the top row (if vertical) or right column (if horizontal) to 0. We define partially overlaps as when a hard macro does not fully cover a grid cell.

Vertical Partial Overlap is when in vertical direction, a macro (purple) is not entirely all covering the grid cells it overlaps with. Shown in the picture below. In this case, we set the macro congestion of grid cells from the top row (red) to 0.

Horizontal Partial Overlap is when in horizontal direction, a macro (purple) is not entirely all covering the grid cells it overlaps with. Shown in the picture below. In this case, we set the macro congestion of grid cells from the right column (red) to 0.

Note that these two situations are mutually inclusive.

Finally, we provide our computation steps below:

• For each hard MACRO:
  • For each gridcell it overlaps with:
    • For both horizontal and vertical macro routing congestion map:
      1. Find the dimension of overlap, multiply by macro routing allocation
      2. Divide by (the grid_cell dimension multiplied by routing per micron)
      3. Add to the corresponding gridcell

Computation of the final congestion cost:

• Adding the Macro allocation congestion and Net routing congestion together for both Vertical and Horizontal congestion map
• Concat both vertical and horizontal congestion maps together.
• Take the top 5% of the most congested gridcells in the concatenation, and average them out to get the final congestion cost.

This site is open source. Improve this page.