Macro Placement by Wire-Mask-Guided Black-Box Optimization
Authors: Yunqi Shi
Ke Xue
Lei Song
Chao Qian
Venue: NeurIPS 2023 poster (2023)
Keywords: Black Box Optimization
Macro Placement
Electronic Design Automation
Reinforcement Learning
Application
TL;DR: An efficient black-box optimization framework for macro placement in EDA is proposed.

Abstract: The development of very large-scale integration (VLSI) technology has posed new challenges for electronic design automation (EDA) techniques in chip floorplanning. During this process, macro placement is an important subproblem, which tries to determine the positions of all macros with the aim of minimizing half-perimeter wirelength (HPWL) and avoiding overlapping. Previous methods include packing-based, analytical and reinforcement learning methods. In this paper, we propose a new black-box optimization (BBO) framework (called WireMask-BBO) for macro placement, by using a wire-mask-guided greedy procedure for objective evaluation. Equipped with different BBO algorithms, WireMask-BBO empirically achieves significant improvements over previous methods, i.e., achieves significantly shorter HPWL by using much less time. Furthermore, it can fine-tune existing placements by treating them as initial solutions, which can bring up to 50% improvement in HPWL. WireMask-BBO has the potential to significantly improve the quality and efficiency of chip floorplanning, which makes it appealing to researchers and practitioners in EDA and will also promote the application of BBO. Our code is available at https://github.com/lamda-bbo/WireMask-BBO.

Macro Placement by Wire-Mask-Guided Black-Box Optimization
Yunqi Shi, Ke Xue, Lei Song, Chao Qian"
National Key Laboratory for Novel Software Technology. Nanjing University, China School of Artificial Intelligence, Nanjing University, China {shiyq, xuek, songl, gianch@lamda. nju. edu.
Abstract
The development of very large-scale integration (VLSI) technology has posed new challenges for electronic design automation (EDA) techniques in chip floorplanning. During this process, macro placement is an important subproblem, which tries to determine the positions of all macros with the aim of minimizing half-perimeter wirelength (HPWL) and avoiding overlapping. Previous methods include packing- based, analytical and reinforcement learning methods. In this paper, we propose a new black-box optimization (BBO) framework (called WireMask-BBOO for macro placement, by using a wire-mask tas--mmak---edede greedy procedure for objective evaluation. Equipped with different BBO algorithms,, WireMask-BBi empirically achieves significant improvements over previous methods, i.c., achieves significantly shorter HPWL by using much less time. Furthermore, it can tun-tune existing placements by treating them as initial solutions, which can bring up to 50% improvement in HPWL. WireMask-BBi and efficiency of chip floorplanning, which makes appealing to researchers and practitioners in EDA and will also promote the application of BBO. Our code is available https: //g thub. com/ lamda wwtp://eeaaakk...........aaaa... BBO
has the potential to significantly improve the quality
Introduction
EDA techniques have been widely employed assist engineers in designing chips [30 31), while the rapid advancement of VLSI technology has led to an exponential growth in chip scale, posing significant challenges. Particularly, for the important chip floorplanning stage EDA, which strives to optimize power, performance, and area metrics while adhering to constraints such as congestion and density [45), the number of cells to be placed on the chip canvas increases rapidly and their routing relationships also become more complex, requiring innovative and efficient methods.
During the floorplanning placement stage, the position of each cell the chip canvas is established. modern chip typically comprises thousands macros (i.e., individual building blocks such as memories) and millions of standard cells (i.e., smaller basic components like logic gates). The designer provides netlist, which outlines the design requirements and serves as large-scale hyper- graph containing numerous hyper-edges (also called nets) that represent the routing relationships among macros and standard cells. Traditionally, the placement problem is divided into two successive stages [4] macro placement, which is usually addressed by heuristic or learning methods [42] and standard cell placement, which is usually addressed by analytical solvers [13] 28). After placing all the cells (including macros and standard cells). a routing stage performed. The general flow
of chip floorplanning and routing is illustrated in Figure []] In this work, we concentrate on macro placement due its greater impact on placement quality: Macros are often larger and more crucial
for achieving optimal placement 4 47
"ooresponding Author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Canvas
Macro Placement Result
Full Placement Result
Cell Routing Result
Macro Placement
Standard Cell Placement
Cell Routing
Macros
Cell Placement
Standard Cells
Figure 1: General flow of chip floorplanning and routing, where the routing stage basically relies the placement result. We focus on the macro placement task in this paper.
Earlier methods often formulate macro placement as a rectangular packing problem, where solutions represented by sequence pair (SP) [33] 3 -tree III corner block list (CBL) [19] other data
structures [3 27]. and solve by simulated annealing (SA) [ 18 24 40). This kind of method suffers from the poor scalability due to the quadratic complexity of decoding genotype solution
to a phenotype placement. Analytical methods [12 13 28 29 place macros and standard cells simultancously, and relax the task to mathematical programming problem, which can be solved efficiently. However, they cannot guarantee the non-overlapping between cells, which is a hard constraint of cell placement. More recently, by dividing the chip canvas into discrete grids and formulating the task of placing macros onto grids step by step as a Markov decision process (MDP), reinforcement learning (RL) methods have been applied, showing promising performance [14] 15 26 (2). But their fast convergence (after only few hundred evaluations) observed in experiments may imply that the huge search space of placement is still underexplored, and further improvement expected. A detailed review of these existing methods is provided in Section 2
In this paper, we propose a solution directly represented by the coordinates of all macros on the chip canvas. HPWL is used the minimization objective function. The key of our framework is that in order improve efficiency, we use an elaborate evaluation procedure, which greedily improves a solution (with the goal of minimizing HPWL while avoiding overlapping) before evaluation. Concretely, using the wire mask (26) to record the increment of HPWL by moving a macro to each candidate grid on the chip canvas, the macros in the solution sequentially adjusted the nearest best grid. This framework is briefly called WireMask-BBO which can use any BBO algorithm to solve the resulting problem.
BBO framework for macro placement. To allow better exploration,
Experimental results multiple popular benchmarks demonstrate that WireMask-BBBO when equipped with different BBO algorithms such as random search (RS), Bayesian optimization (BO), and evolutionary algorithms (EA), significantly outperforms the compared representative methods, in- cluding traditional BBO methods based on packing formulation, analytical methods, and RL methods. Especially, WireMask-EA (i.e., WireMask- BBO equipped with EA) generates the highest-quality placement out of 7 different chip benchmarks, and surpasses the state-of-the-an MaskPlace [26 in minutes on average. Besides, an optimization-basee method, WireMask-Di any existing placement, regardless of how it was generated. That is, WireMask-BBi can be combined with any existing macro placement method as post-processing. Our experiments show that such fine-tuning can lead to an improvement of up to 50% in the objective HPWL.
can fine-tune
Our main contribution is introducing the general framework WireMask-BBi while not developing new BBO algorithms. In fact, our experiments show that even employing simple BBO techniques has previous methods. We will open-source WireMask-BBB3 and use
led superior performance as an optimization benchmark to encourage the invention of more efficient BBO algorithms for solving macro placement problems, well broaden the application scenario of BBO.
2 Background
In this section, we introduce the macro placement problem, the existing methods which can be generally categorized into packing-basse analytical, and grid-based RL methods.

---

2.1 Macro Placement
The input for macro placement problem constitutes netlist EV, where V denotes the information (i.e., height and width) about all cells designated for placement on the chip, and E is hyper-graph comprised of hyper-edges e E E, which encompasses multiple cells (including both macros and standard cells) and signifies their interconnectivity during the routing phase. A macro placement solution consists of the positions of all macros {o;) with the coordinates of each macro V E V on the chip canvas expressed as (I; Vs), where k denotes the total number of marcros. To facilitate comprehensive understanding of the macro placement problem, we present several key metrics for evaluating placement outcomes.
HPWL is the predominant metric for gauging placement quality, as offers a precise estimation of A shorter wirelength decreases delay and power
the wirelength necessary for routing [9] 22 38 consumption, enhancing overall performance [36]. To calculate HPWL of macro placement solution s, each hyper-edge ej E E corresponds to rectangle area characterized by its lower-left endpoint, with coordinates (min,,ee, It, min,,e,, yi), and upper-right endpoint, with coordinates (max.,ee; Vi, Ea; Vt). That is, the rectangle is the smallest one bounding all cells within ej. Let w/ = maxoçee, 24 ming,ee, Iy and h = maxoree Yi ming,ees Y: denote the width and height of the rectangle, respectively. Then,
HPWL(s, H) E (w, + hz).
(I)
Congestion serves vital metric in determining the routability of given placement, exerting a direct influence on the manufacturing process. widely-adopted approach for approximating congestion is rectangular uniform wire density (RUDY) [4]. The congestion of a grid on the canvas can be represented as the cumulative impact of all hyper-edge rectangle areas encompassing the grid. By selecting the top 10% congested grids (denoted as G*) and computing the mean of their congestion, wy wythy the RUDY value of macro placement solution is calculated as [ En.oo- Ee wy-hy
where |G* is the size of G", E(g)) denotes the set of hyper-edges whose rectangle areas cover gi. and (wey + h2)/(w; hT) measures the impact of the rectangle area of hyper-edge ej.
Density measures the overlap degree between cells by employing an electrostatic analogy [29]. It is often treated penalty to diminish overlap, yiclding a more uniform distribution of cells across the chip area 4 13 28 22]. Further discussion will not be provided here, as our formulation ensures non-overlapping, which is hard constraint of macro placement.
Area denotes the area of the minimum bounding rectangle that encloses all the macros. It was prevalent when the focus was on tightly packing macros and minimizing the area they occupied [10] 42]. However, when considering fixed-area chips as in [15 26 28 32 and our work, the placement of cells optimized is to reduce wirelength and congestion rather than minimize the area.
2.2 Packing-based Methods
As the focus was once minimizing the bounding area of given macros, which can lead to a higher chip area utilization ratio [1), the packing formulation emerged as a natural and straightforward approach for the macro placement problem. Each macro, represented as rectangle, has to be packed within a specified chip canvas, with the objective being to optimize the weighted sum of the area metric and HPWL metrie. Several solution representation methods have been proposed, such as SP [33] -tree [1] CBL [19], etc. These genotype solutions will be mapped to concrete macro placement (phenotype) solutions for evaluation. SA is often employed [8 24 40 to solve such BBO problems by perturbing the genotype to generate new offspring solutions and evaluating the corresponding phenotype to determine whether to accept the perturbation.
To handle both macros and standard cells, a divide-andd-onquee standard cells are first clustered into blocks using either the logical hierarchy or min-cut-based partitioning algorithms 23 37]. Placement is then performed on the mix of macro blocks and clustered standard cell blocks, often by SA using packing formulation 2 Finally, the standard cells are re- alloocaee by detailed placement. While reducing the problem size, clustering standard cells into rectangular blocks may eut some connections and hinder finding an optimal solution.
idea is introduced 39 43 The
Recently, RL has been introduced to decide which perturbation operator should selected and which macro should be perturbed by SA (46). Moreover, (5) formulates the CBL establishment as
3

---

(a) SP-SA [33] HPWL = 1.22 x 10"
(b) DREAMPlace (28]: HPWL= 9.88 x 10 Congestion 0.83
MaskPlace [26]:
(d) WireMask-EA (ours):
HPWL= 7.93 10
HPWL= 5.66 x 10 Congestion 0.53
Congestion = 1.07
Congestion 0.66
Figure 2: Visualization of macro placement on the circuit benchmark adaptec3 using the proposed WireMask-EAA and three representative methods. The macros are represented by yellow rectangles. The performance is evaluated in terms of HPWL and congestion; the lower the value, the better.
MDP and constructs a CBL genotype step by step. These advancements continue to grapple with the drawbacks of packing, such poor scalability, which cannot be solved fundamentally because the drawbacks come from the quadratic complexity of mapping from genotype to phenotype [33]. Besides, at least one edge of each macro under the packing setting must be attached to another macro or the canvas's 's edge, making the placement quite congested, as visualized in Figure [[ Note that the congested macro placement will limit the space for subsequent standard cell placement, and lead
to the bad performance of full placement, which will be shown in Table 3
2.3 Analytical Methods
Analytical methods 12 28 29 place macros and standard cells simultaneously, and relax the full placement task to mathematical programming problem, which can be solved efficiently. For example, DREAMPlace (28), a sfate-of-the-art and highly efficient analytical placement method, recasts the full placement task as min WA(s, H) + X Density(s. H), where WA represents the smooth weighted-average wirelength (originally proposed by (20 for approximating HPWI., Density denotes a differentiable density metric for penalizing overlapping, and À is trade-off factor. This problem is then solved numerically using classical mathematical optimization techniques (c.g.. gradient descent), to rapidly generate high-quality full placement. Figure 2(b) shows macro placement generated by DREAMPlace, which is better than that generated by packing in Figure ((a) However, analytical methods cannot guarantee the overllallg between cells. Even employing macro placement legalization techniques, numerous overlaps may persist
2.4 Grid-based RL Methods
As the number of macros increases, packing- maseedg-based methods encounter scalability challenges, while analytical methods may produce overlapping placements that are impractical for manufacturing [4] To meet the demands of modern chip design and fully leverage RL, the Graph placement published in Nature [32) divides the chip canvas into discrete grids, with each macro assigned discrete coordinates of grids, and formulates the placement problem as MDP, wherein the agent decides the placement of the next macro at each step. Notably, no reward is given until the final step, when all macros are placed. The ultimate reward is the weighted sum of HPWL and congestion. Compared with packing- based methods, the grid-based design eliminates edge attachment and provides room for standard cell placement while offering improved scalability. The length of the MDP grows linearly with the number of macros, opposed to the quadratic complexity of packing formulation [33]. DeepPR [5] integrates convolutional and graph neural networks during the embedding stage, and introduces intrinsic reward to promote exploration. However, DeepPR brings overlaps. Though PRNet [1] incorporates the overlap area into the reward function as a penalty, the non-overlapping issue still exists observed in their experiments.
key limitation of the above-mentionel methods is the absence of extrinsic rewards until the final step, Icading to sub-optimal performance for a long MDP with over one thousand steps. To

---

address this issue, MaskPlace [26] introduces a dense reward RL pipeline, incorporating view mask for gathering global information, a position mask to ensure non-overlapping, and wire mask to evaluate the placement of the current macro. Notably, the wire mask offers an immediate reward, calculated as the increase in HPWI. after placing the current macro. These three masks are processed by convolutional neural network and serve as input features for both the value and policy networks. MaskPlace can generate high-quality non-overlapping placement results in an affordable time. Figure 2(c) gives placement example, which is better than that generated by packing and analytical methods as shown in Figures 2(a) and 2(b) From the experiments in [26] we can also observe that MaskPlace converges after only few hundred evaluations, implying that the huge search space of placement may be still underexplored. The experimental results in Section 4 will confirm this conjecture, showing that our proposed framework will bring significant improvement.
3 Proposed Framework WireMassk-BBO
This section is devoted to our proposed WircMask-BBB, where Section 3.1 introduces the problem formulation and Section 3.2 is concerned with optimization methods to solve the resulting problem.
3.1 Wire-Mask-Guided Problem Formulation
Solution representation. To allow better exploration, macro placement solution is directly repre- sented by the coordinates of all macros {er Je i.e., s = (21, Vi........ Ike yk), where (Ig, 34) denotes the coordinates of the macro et on the chip canvas. For example, there are three macros A, B and C for the placement task in Figure 3 and thus a solution is represented by (#1, 11, Z2, 1/2 T3, U/)).
Objective evaluation. The metric HPWL in Eq. (1) is used the objective function to be minimized. But if optimizing in the solution space directly, it is difficult to efficiently find a solution that has a small HPWL value and satisfies the non-overlapping constraint. To improve the efficiency, a greedy improvement strategy is applied to a solution before evaluating it.
As in 32). the chip canvas is first divided into discrete grids. In the process of improving solution greedily, each macro is moved to a grid by letting the macro's 's bottom-left corner situate at the bottom-left corner of the grid. The order of adjusting the position of macro iN is determined by the area of all the cells connected with U, i.c., all the cells in the hyper-edges containing iy. Note that each hyper-edge contains set of connected cells. The positions of all macros will be adjusted sequentially in the decreasing order of their corresponding computed areas, because a macro with a larger computed area implies connecting with more large cells and thus is intuitively more important.
Let .i...., og denote the ordered macros. Assume that the positions of vi...., v/-1 have been adjusted. When considering vf, a wire mask W; introduced in (26) is first computed, which records the increase of HPWI. by placing v." to each candidate grid, given vi,..., 16- already adjusted. Note that those grids that will lead to overlap exceeding the canvas boundary after placing vf excluded. Then, 2," is moved to the grid with the least increment of HPWL. If such a grid is not unique, v is moved to the nearest one among them. This is actually greedy step that moves v to the grid with the least increment on HPWL given the placement of .f..... - until the positions of all the macros have been adjusted. The HPWL of the resulting solution with all the adjusted macros is treated as the objective value of the original solution. Thus, a solution and its improved version in objective evaluation can be viewed as the genotype and phenotype representation of a macro placement. The detailed process of objective evalution is presented in Algorithm []
1i--1-Thee This process is repeated
Figure gives an example illustration of objective evaluation. For the input netlist H (V. F), V contains three macros A, B and C, and the hyper-graph E contains two hyper-edges: one encompasses macros A and B. and the other encompasses A and C. Each hyper-edge signifies the interconnectivity of the macros contained by it. The chip canvas is partitioned into x 5 grids. Assume that the width and height of each grid is both 1. The solution to be evaluated (as shown in Figure a())) consists of the positions of macros A, B and C. According to the hyper-graph E, we know that during the routing phase, macro A is connected with B and C, while macro B and C are both connected with only A. Thus, the corresponding areas computed in line of Algorithm [ are decreasingly ordered as A, B and C, which is just the order in line adjust the positions of macros sequentially.
When trying to adjust the position of macro A, a wire mask is first computed as in line of Algorithm I which is shown in Figure 3 where the number in each grid is the increment of HPWL
5

---

Algorithm Objective evaluation of WireMask-BBO
Input:
solution netlist (V, E), and number m of partitions
Output:
improved solution s', and the corresponding objective (i.e., HPWL) value
Process:
1: For each macro 2y E V, compute the area of all the cells connected with it, i.c., Ee, eş;
2: Order all macros decreasingly, denoted vi ...... Vg.. according their corresponding areas;
3: Initialize the canvas as m m grids, and let = 0;
4: for each macro 0g do
5: Generate wire mask W; according to the updated positions .i...., 8 (see Algorithm in (261), which records the increment of HPWL by moving of to each candidate grid;
6: Q - the set of grids that has the minimum increment of HPWL (denoted as ft) in W;;
7: Select the grid from Q, which has the smallest Euclidean distance the macro uf;
8:
Update the position of of to be that of the grid g;
9: J+
10: end for
s' < the updated positions of all the macros
12: return s',
Solutions
(a)
(e)
Improved solution (Phenotype representation)
Solution be evaluated
(Genotype representation)
HPWL = 11
:Coordinate in the original placement
Place
+
(b)
(c)
(d)
WireMask Guidance
3
Place
Place
Netlist input
2
6
2
Hyper-edge (A,
6
HPWL
HPWL
3
2
2
3
Hyper-edge 2: (A, c)
6
6
6
6
Adjustment Order
A
Next
macro
C
Figure 3: An example illustration of objective evaluation of WireMask-BBB.
led by placing macro A in that grid. For example, if placing macro A in the center grid as shown in Figure 3), both the hyper-edges correspond to the smallest rectangle bounding macro A (i.e., the red and black dotted square in Figure 3()) for computing HPWI. in Eq. (T. and thus the corresponding HPWL is which is the sum of half perimeters of these two rectangles. As the initial HPWL before placing macro A is O, the increment of HPWL is 6. Note that when adjusting the position of a macro, its bottom-left corner must be situated the bottom-left corner of grid, and grids without numbers in the wire mask indicate that the current macro should not be placed there due overlap
exceeding the canvas boundary. The underlined italic number the wire mask denotes the least HPWL increment, representing the locally optimal choice, i.e., the set Q in line 6 of Algorithm| T Then, as shown in lines 7-8 of Algorithm I macro A is placed at the local optimal grid, which has the smallest Euclidean distance to it. The coordinate of macro A in the original placement denoted by the red star Figure (b), and thus is adjusted to situated the grid closest to shown in Figure 3 c).

---

The positions of macros B and C are adjusted similarly. Figure ((c) shows the adjusted placement of macro A, and also the wire mask when trying to place macro B. Figure (d) shows the adjusted placement of macros A and B, and also the wire mask when trying to place macro C. Figure ( gives the final improved placement after adjusting the positions of all macros. As HPWI. is the sum of all hyper-edges" bounding rectangles' half perimeters, these rectangles can be updated each time a macro is placed, as shown by the red and black dotted squares in Figure 3 That is, for any individual macro, it is only necessary to update the bounding rectangles of its associated hyper-edges and compute the increase in their half perimeters. Thus, the calculation of HPWL can be performed incrementally,
in line 9 of Algorithm [ In Figure 3 the increment of HPWL after placing macros A, B and C is 6, 3 and 2. respectively, leading to the HPWL value 11 of the final improved placement. Note that the red and black dotted bounding rectangles in Figure 3 are shown for illustrative purposes, while the actual HPWI. calculation in our experiments is based on pin information.
Therefore, we have formulated macro placement as black-box optimization problem, where the eenotype-phenotype mapping is greedily guided by wire mask. Figures and (e) give an example of genotype and phenotype representation. An algorithm for solving this problem will search in the genotype space, where the goodness of a genotype solution estimated by the objective value of its corresponding phenotype. When an algorithm terminates, the corresponding phenotype of the generated genotype solution will be output as the final macro placement. Note that by the wire-mask- -uiided mapping process, the phenotype solution is guaranteed to have no overlap, and thus an algorithm can search in the genotype space without considering constraints.
3.2 Black-Box Optimization
The above formulated problem can be solved by any BBO algorithm. In our experiments, we employ three simple ones, random search (RS), Bayesian optimization (BO) [17] and evolutionary algorithm (EA) [7]. RS randomly allocates all macros in a solution and evaluates it, recording the historical best. For BO, we adopt the efficient TuRBO approach [16) to directly optimize the continuous coordinates (x1. Vi...., T2. Mks)
of all macros, resulting in a dimension of 2k, where is the number of macros. For EA, we choose the simple (1+1)-EA 16 49 which maintains only one solution and iteratively improves it by mutation. We design the mutation operator by randomly selecting two macros and exchanging their coordinates in solution. Our experiments will show that using these three simple BBO algorithms has been sufficient for the superior performance over previous methods. It is expected to design better BBO algorithms for the proposed formulation of macro placement.
By adopting the grid-based discretization and designing the wire-mask-guider greedy genotype- phenotype mapping. the proposed framework WireMask- -BOO can efficiently generate a non- overlapping high-quality placement, addressing the poor scalability issue of packing- based methods as well as the overlapping issue of analytical methods. The use of black-box optimization enhances the exploration ability, making WireMask BBO able to surpass the sfate-of-the-ard RL-based method MaskPlace (26). Figure 2(d) visualizes a placement generated by WireMask-BBB BBO equipped with EA, which is better than that by SP-SA (a representative packing- based method) (33, DREAMPlace (a
representative analytical method) (28 and MaskPlace (26), as shown in Figures ( 2 and 2(c)
4 Experiments
We mainly empirically test our method on the ISPD2005 benchmark 335. which was originally proposed as standard cell placement benchmark with fixed macros. Following conventional practice [15] 14 (6). we modify all macros to be movable for the macro placement problem. The ISPD2005 benchmark contains eight chips, i.c., adaptecl-4 and bigbluel-4. Note that for the bigblue2 chip, which has over 20,000 macros and 30,000 macro-related hyper-edges, single objective evaluation by step-by-step placement costs more than an hour. Thus, we do not include this chip in our experiments [26]. For each chip, the canvas is partitioned into approximately 150x 150 grids heuristically. The detailed statistics (e.g., the number of macros, partitions, etc.) of the chips are provided in Appendix A
We compare WireMask- -BO with several representative macro placement methods, including the packing-based SP-SA [33 three analytical methods NTUPlace3 12], RePlace 133 DREAM-
Place (28), and three Rl--based methods Graph placement 32, DeepPR [15), MaskPlace 26 As
introduced in Section 3.2 equip the proposed WireMask-BBB framework with RS, BO and EA.
7

---

Table 1: HPWL values (x109) obtained by ten compared methods on seven chips. Each result consists of the mean and standard deviation of five runs. The best (smallest) mean value on each chip is bolded. The symbols '+' and 'z' indicate the number of chips where the result is significantly superior to, inferior to, and almost equivalent to WireMask-EA, respectively, according to the Wilcoxon rank- test with significance level 0.05.
Michhdd
Type
adapee)
adaptec2
wlagrec3
adagteed
Nighiccl
bighluct
Nightued (xx10")
+:/ - 00
Aug. Rask
SP-SA [33
Packing
2.642
a
7.56
120.03
5.12
164.70 19.55
25.49 2.73
0/7/0
NTUPluee3
Anditica
321:17
22:85
0/7/0
RePlace
Analstiaal
26.1922.10
a
11,69
37.64 1.05
2
119.44 54.43
11.50
1/6/0
2.44
12.20
Graph 13
50.10
98.20 203.51
10.58 1:20
157.48
53.35
0/7/0
RL.
10.01
4.7.16
311.66
3665
450.48
12.18
68.30
MoskPlace
RL
6.38 0..3
64.44 3.00
20.0
0:59
91.11
11.07 =0.90
07720
WireMank-
Ours
6.13=0005
59.28 1.48
00:00:0.:5
6..22
2.19:4001
62.58 2.07
8.30=0..7
0/3/2
WiroMase-110 HO
Ours
6/0 4.014
59.17 4:394
61:00
65.86 1.01
2.14:40.0
67.48 67.48-6-49
8.67-00:6
0/3/4
WireMask-EA
Ours
5.91=1007
$2.63
57.
2..79
2.12
0.22
1.43
denoted as Wire-as,- WireMask-BO and WireMask-EA, respectively. For the employed method TuRBO [16] for BO, we use the common hyper-parameters. For the EA, its initial solution is set as the best among 100 random solutions. All experiments are run on two Intel Xeon Platinum 817IM CPUs, each with 26 cores and 52 threads.
Main results. Table T gives the detailed results of running each method using five random seeds. The runtime for each run of WireMask-BBOO is set 1,000 minutes. The results of analytical and RL-based methods are directly from [26] Note that the analytical method NTUPlace3 is deterministic, and thus has standard deviation. We compute the rank of each method each chip as in [21], which are averaged in the last column of [ WireMask-RS, WireMask--O and WireMask-EA achieve the three highest ranks, disclosing the effectiveness of the proposed general framework WireMask-BBO. Among these three variants, WireMask-EA performs the best, which has the highest rank 1.43 and achieves the smallest HPWL value on 5 out of the 7 chips. RS relies solely on random sampling without leveraging any search history. BO performs well in many low- -ww-dmensiionl tasks (typically when the dimension d < 20 (77). but suffers from the curse of dimensionality due the time-consuming cost of updating the Gaussian process surrogate model and optimizing the acquisition function [ For example, in our experiments where d (i.e., 2 times the number of macros) is always larger than 1000, EA can sample much more solutions (about 2-7 times as shown in Table [9] of Appendix B) than BO during the 1000-minutes running. Compared with any previous method, WareMask-EA is significantly better on at least 6 out of the 7 chips, by the Wilcoxon rank-sum test with significance level 0.05. It is outperformed by RePlace and DREAMPlace on the chip adaptec4, implying the suitability of analytical methods for this particular problem.
Running time analysis. As shown in Table any variant of WireMask- BBO always performs better than the state-of-the-a MaskPlace 26). which ranks the highest among the compared previous methods. While (26 did not offer explicit training time details, the authors state 200-minute convergence time in response to our inquiry. Next, we examine the efficiency of WireMask-BBi when compared with MaskPlace. Taking MaskPlace as the baseline, we plot the curve of HPWL over the wall clock time for WireMask -BOO in Figure E Each variant of WireMask-BBa
surpasses
MaskPlace very quickly. Particularly, WireMask-EA requires only 39, 8, 0.37, 0.62, 0.15, and minutes, respectively, with an average of 8 minutes to surpass MaskPlace across six benchmark chips. This notably faster than the 200-minute convergence time reported for MaskPlace. We have excluded the bigblue4 chip in Figure 4 because the 1,000-minute search for WireMask-EA only completes its initialization on this large-scale chip. On the chips adaptec3 and adaptec4, WireMask- EA actually outperforms MaskPlace after only single greedy placement guided by wire mask, implying that MaskPlace fails to balance exploration and exploitation.
Performance on congestion metric. Aside from HPWL, congestion and density are also vital metrics as introduced in Section 2.1 As our framework WireMask- -BOO maintains the non-overlapping property, density constraint does not need to be considered. Here, we evaluate placement congestion and compare it to the results of MaskPlace (26) and SP-SA [3] in Table 2 We normalize the congestion values by setting WireMask-FAt congestion to 1.00. The MaskPlace placements are provided by its authors? 2 while the SP-SA and WireMask-BBB placement results are obtained from a
'All the MaskPlace evaluations are based upon the placement file provided by its authors. Note that the authors provided only one placement on each benchmark chip, and did not provide the results on bigblue4. which are marked by a ' symbol in the following tables.
8

---

adaptec1
adaptec2
adaptec3
70-
6.-
94.1
HPW/
75-
6.--
250
400
aco
1000
250
400
1003
Wall Clock Time (min)
Wall Clock Time (min)
Wall Clock Time (min)
adaptec4
bigbluel
bigblue3
10
2.40
120
75
HPW/L
2.30
HPWL
60-
2:15
300
2.00
1000
400
660
Clock (min)
Time (min)
Time (min)
MaskPlace
WireMask-RS
WireMask-80
WireMask-EA
Figure HPWL (x10*) vs. wall clock time of WireMask-BBi where the shaded region represents the standard error derived from 5 independent runs.
Table 2: Comparison on HPWL (x 10%) and Congestion (Cong.).
Benchmark Mierios
adaptec] HPWI.
adaptes2
Idlaptoc3 HPWI.
adaptec4
hiphlue]
lighluel
Cong.
HPWL.
Cong
Cong
HPWL
Cong.
HPWT.
Cong:
HPWL
Cong
HPWT.
Cong
HPWI.
Cong.
SP-SA [3
18:77
4.21
117.63
1.34
122.30
2.03
102.54
2.08
136.16
1.50
19.00
2.72
4.85
4.71
MaskPlace 26
6.36
1.22
79.98
1.63
79.32
1.25
75.75
1.17
2.42
1.63
K2.61
0.86
4.00
3.67
Wir
6.09
1.01
57.31
1.04
60.91
1.04
60.07
0.98
2.18
1.09
63.86
1.01
8,21
1.10
2.29
2,43
WireMaak- B0
6.14
1.02
55.31
0.99
58.67
1.06
61.67
1.06
2.10
0.94
63.88
1.19
5.39
1.07
2.29
2.43
WineMack-FE EA
5.81
1.00
49.32
1.00
56.56
1.00
58.79
1.00
2.12
1.00
68.88
1.00
3.45
1.00
1.43
1.57
1,000-minute search using the same random seed. The results show that though optimizing HPWL, WireMask-BBO can also achieve smaller congestion. The reason is that the RUDY approximation of congestion is sometimes positively related to the HPWL metric. Given a macro placement solution, the HPWL in Eq. (L) is computed as the sum of the rectangle's half- perimeer of hyper-edge, i.c., Ecyer(w) wy h2). where e, denotes a hyper-edge. E' denotes the typer-graph comprised of all hyper-edges, wy and hy denote the width and height of the rectangle corresponding to e,, respectively, The RUDY measures the overall congestion on the canvas, and the congestion of each grid yi on the canvas is calculated by the cumulative impact of all hyper-edges encompassing the grid. Note that a hyper-edge e, will add an impact to each of its covered grids by wi h5 h, Euyer(ur +hy) = HPWL,
1. Then, the overall congestion
of all grids is Eg. EcjeFla) w, where E(gi) denotes the set of hyper-edges whose corresponding rectangle covers the grid g,- The first equality holds because the number of times of a hyper-edge Ej E enumerated in LHS is equal the number of grids covered by it, which wy-hj. Thus, we can observe a positive relation between RUDY and HPWL. Besides our results, Table 4 in MaskPlace (26) and Table 4 in ChiPFormer [25 have also shown that the best HPWL can lead to the best congestion. However, a lower HPWL does not necessarily lead to lower RUDY, because RUDY only considers the top-10% congested grids as introduced in Section 2.1
+ h ΣeSer Wy h
Full placement results. Table shows the results of different methods on the full placement task involving both macros and standard cells. We utilize PRNet [4] and DREAMPlace 28 as baselines, because both of them are designed to handle mixed-size placement tasks. The other five macro placement methods first optimize the macro placement, fix the maero positions, and then employ DREAMPlace to optimize the standard cell placement exclusively. The mean values are derived from DREAMPlace standard cell placement using five different random seeds. The results of PRNet are directly from [1]. Although WireMask-FA achieves the best performance on only one chip, i.e., adaptec4, it attains the highest average rank. Compared with the mixed-size placement optimization methods PRNet and DREAMPlace. WireMask-EA EA does not explicitly optimize the full

---

Table 3: Comparison of HPWL values (x10") on the full placement task involving both macros and standard cells. The best (smallest) mean value on each chip is bolded. The symbols '+', and 'z' indicate the number of chips where the result significantly superior to, inferior to, and almost equivalent to WireMask-EA-DREAAN EAADRAMMPlace, respectively, according to the Wilcoxon rank-sum test with significance level 0.05.
benchmark
adaptec1
odagtec2
odaglee3
adigiee4
highluc
bighlae3
Nighluck
+ /
Arg. Rank
PRNce [1]
8.28
12:33
23.24
23.40
14.10
46.56
100.13
2/5/0
3:29
DREAMPlee 28
11.10=1.3 1:31
12.84 1.74
27.03
24.37 +
00.25
36.51 +0.56
2.223
2/4/1
3.57
SP SA [55) DREAMMPaee
1018
2:01
30.63
0.82
20.02
10.70
63.00:0..12
203.79 = 0.36
0/7/0
6.29
Macc [6 DREMMMEE
1086=0001
12.98 0.55
26. 06.14+00077
+.052
10.64+0.01
54.08
1.06
0/6:40
5,00
KiccMtsk-RS-DRRE -S---EA
940=0.02
9.07 0.02
22.76+0001
22.09:00001
+0.31
42.58 0.220
262
16 1.08
2/4/1
3.00
WieMMak-BOaDDa
9.9200.6
12 0:01
0:04
26.70
20.36.20.01
3.55
122
22228820 11006
1/6,00
4,43
WirMast-FA--RRAMMPE
8.93
9.20
21,72+0001
20.51 a 0.01
10.35 0.00
4.152
171.25 0:48
2.14
placement wirelength; thus, its best overall performance confirms the contribution of high-quality macro placement to an overall superior final placement.
Fine-tuning results. In fact, WireMask-BBBO can be combined with any existing macro placement method for post-processing. The placement generated by any existing method can be treated as the initial solution of WireMask-BBO and then further improved. Table T shows the HPWL results of SP-SA and MaskPlace before and after 1,000 minutes of fine-tuning by WireMask-EA, with the average improvement ratio of 53.93% and 17. 17.06%, respectively. Compared to Table I fine-tuning the placement of MaskPlace leads to the best HPWL value on the two chips adaptecl and bigblue
Table 4: HPWL (x 10a) values obtained after fine-tuning existing placements by running WireMask- EA for 1,000 minutes. The last column, Avg. Imp., denotes the average improvement ratio across six chips, obtained by comparing the HPWL values before and after fine-tuning.
Method
adaptec1
adaptec2
aduptec3
adaptec4
bigbluel
bigbluc3
Avg. Imp.
SP-SA [3
18.84
117.36
115.48
120.03
5.12
164.70 82.68 = 18.17
53.98%
-WireMask-EA (1000min)
6.02 0.11
60.35 + 4.41
57.88 + 0.62
59.50 0.92
2.21 0.00
MaskPlace
6.56
79.98
79.32
75.75
2.42
82.61 74.93 # 7.79
17.06%
+asneMask EA (1000min)
5.84 a 0.10
61.43 + 1,23
59.24 2.71
60.35 1,38
2.10 0.01
Additional results. We propose a post local search procedure to further improve final placement results. We investigate the influence of the two typer-parameters of WireMask-BBCC i.c., number of partitions in chip canvas discretization, and adjustment order of macros in objective evaluation. For WireMask-EAN the best-performed variant of WireMask-BBir operators is also examined. We compare the number of evaluations of WireMask MBrO methods in 1000 minutes. Furthermore, we test on the ariane RISC-V CPU design benchmark 48), still showing the clear superiority of WireMask-BBB over previous methods. We finally include comparisons with two concurrent advanced methods, i.e., ChiPFormer (25 and AutoDMP 4 and our WireMask-EA still maintains the superior performance. These results are provided in Appendix B
the influence of different mutation
5 Conclusion
This paper proposes the general framework WireMask-BBi -BO for macro placement, which adopts a vire-mask-guider greedy mmnoyye--peenoyye mapping and can be equipped with any BBO algorithm. Extensive experimental results show that -ireMask-BBBO is clearly superior to previous packing- based, analytical, and RL-based methods. Furthermore, it can be combined with any existing macro placement method to further improve the final placement. Though showing significant potential, WireMask- also has some limitations. First, it can only deal with macro placement, leaving standard cells for analytical placers. Second, its performance is limited for chips with a large number of macros due to the expensive objective evaluation. This, however, can be alleviated by equipping with high- sich-dimnnsional BBO algorithms [8] or designing specific efficient BBO algorithms for macro placement, which a very interesting future work. Our method does not have negative social impacts.
10

---

Acknowledgement
We would like to thank Yao Lai from The University of Hong Kong for his generous help and valuable discussions, and the anonymous reviewers for their helpful comments. This work supported by the National Key R&D Program of China (2022ZD01 16600) and National Science Foundation of China (62022039). Chao Qian is the corresponding author.
References
[1] Saurabh N Adya and Igor L Markov. Fixed-outinee floorplanning through better local search. In Proceedings of the 19th IEEE International Conference on Computer Design: VLSI in Computers and Processors, pages 328-334, Austin, TX, 2001.
[2] Saurabh N Adya and Igor L Markov. Fixed-outine floorplanning: Enabling hierarchical design. IEEE Transactions on Very Large Scale Integration Systems, 11(6):1100-111 2003.
[3] SN Adya, Chaturvedi, JA Roy, D Papa, and IL Markov. Unification of partitioning, floorplan- ning and placement. In Proceedings of the 17th International Conference Computer-Aides Design, pages 550-557, San Jose, CA, 2004.
[4] Anthony Agnesina, Puranjay Rajvanshi, Tian Yang. Geraldo Pradipta, Austin Jiao, Ben Keller, Brucek Khailany, and Haoxing Ren. AutoDMP: Automated DREAMPlace- based macro placement. Proceedings of the 27th International Symposium on Physical Design, pages 149-157, Virtual, 2023.
[5] Mohammad Amini, Zhanguang Zhang, Surya Penmetsa, Yingxue Zhang, Jianye Hao, and Wulong Liu. Generalizable floorplanner through corner block list representation and hypergraph embedding. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2692-2702, Washington, DC, 2022.
[6] Auger Anne and Benjamin Doerr. Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific, 2011.
[7] Thomas Bäck. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolu- tionary Programming, Genetic Algorithms. Oxford University Press, 1996.
[8] Mickael Binois and Nathan Wycoff. survey on high-dimensional Gaussian process modeling with application to Bayesian optimization. ACM Transactions Evolutionary Learning and Optimization, 2(2): 2022.
[9] Andrew E Caldwell, Andrew B Kahng, Stefanus Mantik, Igor Markov, and Alexander Zelikovsky. On wirelength estimations for row-based placement. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 18(9): 1999.
[10] Heming Chan, Pinaki Mazumder, and Khushro Shahookar. Macro-cell and module placement by genetic adaptive search with ritmap-represented chromosome. Integration, 12(():49-77, 1991.
[11) Yun-Chih Chang, Yao-Wen Chang, Guang-Ming Wu, and Shu Wu. B*-trees: A new representation for non-slicing floorplans. In Proceedings of the 37th Annual Design Automation Conference, pages 458 463, Los Angeles, CA, 2000.
[12] Tung-Chied Chen, Zhe- Wei Jiang, Tien-Chang Hsu, Hsin-Chen Chen, and Yao-Wen Chang. Ntuplace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1228)))222-12422 2008
[13] Chung-Kuan Cheng, Andrew B Kahng, Ilgweon Kang, and Lutong Wang. Replace: Advancing solution quality and routability validation global placement. IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 1717777777 2018.

---

[14] 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 Advances in Neural Information Processing Systems 35, New Orleans, I.A, 2022.
[15] Ruoyu Cheng and Junchi Yan. On joint learning for solving placement and routing in chip design. In Advances in Neural Information Processing Systems 34, pages 16508-16519, Virtual, 2021.
[16] David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local Bayesian optimization. Advances neural information processing systems 32, Vancouver, Canada, 2019.
[17] Peter Frazier. tutorial on Bayesian optimization. arXiv preprint urXiv:1807.000 2018.
[18] Shinn- Ying Ho, Shinn-Jang Ho, Yi-Kuang Lin, and WC-C Chu. An orthogonal simulated annealing algorithm for large floorplanning problems. IEEE Transactions on Very Large Scale Integration Systems, 12(8):874-8777 877, 2004.
[19] Xianlong Hong, Gang Huang, Yici Cai, Jiangchun Gu, Sheqin Dong, Chung- Kuang Cheng, and Jun Gu. Corner block list: An effective and efficient topological representation of non-slicing floorplan. In Proceedings of the 13th IEEE/ACM International Conference on Computer Aided Design, pages 8-12, San Jose, CA, 2000.
[20] Meng-Kal Kai Hsu, Yao-Wen Chang, and Valeriy Balabanov. TaV-aware analytical placement for 3D IC designs. In Proceedings of the 48th Design Automation Conference, pages 664 669, San Diego, CA, 2011.
[21] Demšar Janez. Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7:1-30, 2006.
[22] Andrew B Kahng and Sherief Reda. A tale of two nets: Studies of wirelength progression in physical design. In Proceedings of the 7th International Workshop on System-level Interconnect Prediction, pages 17-24, Munich, Germany, 2006.
[23] George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. Multilevel hypergraph partitioning: Application in VLSI domain. In Proceedings of the 34th annual Design Automation Conference, pages 526-529, Anaheim, CA, 1997.
[24] Scott Kirkpatrick, C Daniel Gelatt Jr, and Mario P Vecchi. Optimization by simulated annealing. Science, 220(4598):671-68)) 1983.
[25] Yao Lai, Jinxin Liu, Zhentao Tang, Bin Wang, Jianye Hao, and Ping Luo. Chipformer: Transferable chip placement via offline decision transformer. Proceedings of the 40th International Conference on Machine Learning, pages 18346,18364, Honolulu, HA, 2023.
[26] Yao Lai, Yao Mu, and Ping Luo. Maskplace: Fast chip placement via reinforced visual representation learning. In Advances in Neural Information Processing Systems 35, New Orleans, LA, 2022.
[27] Jai-Ming Lin and Yao-Wen Chang. TCG-S: Orthogonal coupling of pddadiissible representa- tions for general floorplans. In Proceedings of the 39th Annual Design Automation Conference, page 842-847, New Orleans, LA, 2002.
[28] Yibo Lin, Zixuan Jiang, Jiaqi Gu, Wuxi Li, Shounak Dhar, Haoxing Ren, Brucek Khailany, and David Z Pan. DREAMPlace: Deep learning toolkit-enables gpu acceleration for modern VLSI placement. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 40(4):748-761, 2020.
[29] Jingwei Lu, Pengwen Chen, Chin-Chih Chang, Lu Sha, Dennis Jen-Hsin Huang, Chin-Chi Teng, and Chung- Kuan Cheng. ePlace: Electrostatics-baset placement using fast Fourier transform and Nesterov's method. ACM Transactions on Design Automation of Electronic Systems, 20(2): 2015.
12

---

[30] Done MacMillen, Raul Camposano, D. Hill, and Thomas W. Williams. An industrial view of electronic design automation. IEEE Transactions on Computer-Aided Design of Integrated Circuils and Systems, (9(12): 1448, 2000.
[31] Igor L Markov, Jin Hu, and Myung-Chul Kim. Progress and challenges in VLSI placement research. In Proceedings of the 25th International Conference on Computer-Aided Design, pages 275-282, San Jose, CA, 2012.
[32] Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, et al. A graph placement methodology for fast chip design. Nature, 594((862):207-222 2021.
[33] Hiroshi Murata, Kunihiro Fujiyoshi, Shigetoshi Nakatake, and Yoji Kajitani. VLSI module placement based on rectangle- packing by the sequence-pair IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 15(12):1188-1544 1996.
rectangle-packing
[34] Shigetoshi Nakatake, Kunihiro Fujiyoshi, Hiroshi Murata, and Yoji Kajitani. Module packing based on the BSG-structure and IC layout applications. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 17(6):519-530, 1998.
[35] Gi-Joon Nam, Charles J Alpert, Paul Villarrubia, Bruce Winter, and Mehmet Yildiz. The ISPD2005 placement contest and benchmark suite. In Proceedings of the 9th International Symposium on Physical Design, pages 216-220, San Francisco, CA, 2005.
[36] Jan M Rabaey, Anantha P Chandrakasan, and Borivoje Nikolic. Digital Integrated Circuits. Pearson, 2002.
[37] Jarrod A Roy, Saurabh N Adya, David A Papa, and Igor L Markov. Min-cut floorplacement. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(7):1313 1326, 2006.
[38] Khushro Shahookar and Pinaki Mazumder. VLSI cell placement techniques. ACM Computing Surveys, 23(2):143 1991.
[39] Arun Shanbhag, S Danda, and Naveed Sherwani. Floorplanning for mixed macro block and standard cell designs. In Proceedings of 4th Great Lakes Symposium on VLSI, pages 26-29, Notre Dame, IN, 1994.
[40] M Shunmugathammal. C Christopher Columbus, and S Anand. A novel b*- crossover- -baed simulated annealing algorithm for combinatorial optimization in VI.SI fixed-outline floorplans. Circuits, Systems, and Signal Processing, 39(2):900 918, 2020.
[41] Peter Spindler and Frank M Johannes. Fast and accurate routing demand estimation for efficient routability-driven placement. In Proceedings of the 14th Conference on Design, Automation & Test in Europe, pages 1-6, Nice, France, 2007.
[42] Maolin Tang and Xin Yao. A memetic algorithm for VLSI floorplanning. IEEE Transactions on Systems, Man, and Cybernetics, 37(1):62-69, 2007.
[43] Michael Upton, Khosrow Samii, and Stephen Sugiyama. Integrated placement for mixed macro cell and standard cell designs. In Proceedings of the 27th ACM/IEEE Design Automation Conference, pages 32-35, San Francisco, CA, 1991.
[44] Dhruv Vashisht. Harshit Rampal, Haiguang Liao, Yang Lu, Devika Shanbhag, Elias Fallon, and Levent Burak Kara. Placement in integrated circuits using cyclic reinforcement learning and simulated annealing, arXiv preprint arXiv:2011. 1.0757777 2020.
[45] Laung-Teree Wang. Yao-Wen Chang, and Kwang- Kwang-Ting Tim Cheng. Electronic Design Automa- tion: Synthesis, Verification, and Test. Morgan Kaufmann, 2009.
[46] Qi Xu, Hao Geng, Song Chen, Bo Yuan, Cheng Zhuo, Yi Kang, and Xiaoqing Wen. Good- floorplan: Graph convolutional network and reinforcement leasning-based floorplanning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 41(10):442--302, 2021.
13

---

[47] Junchi Yan, Xianglong Lyu, Ruoyu Cheng, and Yibo Lin. Towards machine learning for place- ment and routing in chip design: methodological overview. arXiv preprint arXiv:2202.13560 2022.
[48] Florian Zaruba and Luca Benini. The cost of application-class processing: Energy and per- formance analysis of a linux-ready 1.7-ghz 64-bit RISC-V core in 22-nm FDSOI technology. IEEE Transactions Very Large Scale Integration Systems, (7(1)) 2640, 2019.
[49] Zhi-Hua Zhou, Yang Yu, and Chao Qian. Evolutionary Learning: Advances in Theories and Algorithms. Springer, 2019.
14

---

A
Experimental Settings
The detailed statistics of benchmarks are in Table Each column in the table represents the following:
#Macros: the number of macros.
#Standard cells: the number of standard cells.
#Hyper-edges: the number of hyper-edges.
#Macro-related Hyper-edges: the number of hyper-edges that are related to Marco, which is used in the objective evaluation process of WireMask-BBil
Area Utilization Ratio: the proportion of the total area of the chip canvas that is occupied by the macros, calculated by dividing the area of the macros by the total area of the chip canvas. A higher Area Utilization Ratio to some extent indicates a harder placement problem, because we have maintain the non-overlapping property.
#Partitions: the number of partitions when discretizing the chip canvas into grids.
Table 5: Detailed statistics of different benchmarks.
Benehmark
#Macros
#Standard cells
#Hyper-ddges
#Macro-related Hyper-edges
Area Utilization Ratio
#Partitions
Idaptec1
543
210,904
3,709
693
0.48
160
udapiec2
566
254,457
266,0009
4,201
0.63
158
udaptec3
723
450,927
466,758
3,259
0.55
113
adaptec4
1,329
494,716
2,949
108
bigbluel
560
277.604
284,479
409
0.27
160
bigblue2
23,084
534,782
577,235
33,223
0.38
/
highlue3
1,298
1,095.514
1,123,170
3,937
234
bigblued
8.170
28196,183
2,229.886
22,223
0.37
273
ariane
932
0
12,404
12,404
0.78
357
All columns, except for #Partitions, are predetermined and unalterable in the benchmark g The #Partitions, however, constitutes crucial hyperparameter, which is determined heuristically based on the heights and widths of the macros and the canvas. To elaborate, in the case where multiple macros of identical size, e.g., 30 x 20, are present value of #Partitions would be set to 300, thereby resulting a grid size 30 x 30 for each grid. The influence of #Partitions is discussed in Table 7 of Appendix B.2
given chip, with the canvas size 9000 x 9000, the
B
Additional Results
B.1
Post local search
As the genotype-phenotyy mapping in the objective evaluation of WireMask--BB is performed greedily, guided by wire mask, propose post local search procedure modify the final generated macro placement, which will probably bring further improvement. For final generated macro placement, the positions of all macros are sequentially adjusted; the position of each macro is adjusted the best grid (ties are broken randomly) which reduces the current HPWL value most. Note that when adjusting the position of one macro, all the other macros fixed, which is different from that in the objective evaluation of WireMask-BBa -BOO which is only based on the positions of those macros that have been adjusted. We have applied this post local search procedure to the final placements generated by SP-SA 333, MaskPlace (66 and WireMask- BBO. The macros are adjusted sequentially according to the order employed by WireMask-BBO (i.e., lines 1-2 in Algorithm [[] this process is performed twice. Note that the adjustment order of macros can be arbitrary when applying this post local search process. The results in Table T show that the final placements be further improved, which is expected because both MaskPTace and WireMask involve (probabilistically) greedy incremental placement guided by wire mask.
"Note that for the bigblue2 chip. which has over 20,000 macros and 30,000 macro- related hyper-edges. a single objective evaluation by step-by seep-by-step placement costs more than an hour. Thus, we do not include this chip experiments as 226] and its #Partitions is denoted as /.
15

---

Table 6: HPWL values (x10²) obtained by post local search on existing placements. The last column, Avg. Imp., denotes the average improvement ratio across seven chips, obtained by comparing the HPWL values before and after post local search.
benchmark
adaptec
adaptec2
aduptec
adaptec4
bighluel
highlue3
bighloo4
Avg. Imp.
SP-SA [33]
18.84
117.36
115.48 = 7.56
120.03 a: 4.25
5.12 1.43
164,70 19.55
25.49 2.73
25.62%
after_ socalssaarchh
12:52 1.59
97,22 =
104.46
102.17 55.0
0.10
138.85 = 14.53
1.84
MaskPlace [26]
6.56
79,98
79.33
75.75
2.42
82.61
9.69%
after_ Loc__oocllssce seurch
12.46 6.05
74.18 0.68
67.99 1.13
77,87
1.54
WireMask- RS
0.05
59.28 = 1.48
60.60 + 0.45
62.06 + 0.22
2.19
62.58 1:8:2000 2.07
8.20 0.17
3.57%
after locallocal_eee seurch
5.99 0.06
57.23 1.75
59.22 0.40
60.99 a 0.82
0.07
7.64
WireMask-RO RO
6.07
59.17 3.94
61.00 + 2.08
63.36 1.01
2.14
67.48 17,486640 6.49
8.62 0.18
after_loee secr_lo
54,24 0.12
2.92
60.29 + 2.29
62.96 1.16
63.87 0.01
7.86 7.86
3.77%
WireMask EA
5.91
=2.6322222
57.75 # 1.16
58.79 1.02
59.87 2.12
8.28 a 0.25
3.32%
after search
0.09
49.04 2.35
57.41 a 1.04
0..76
2.01
a..29
7.66 0.266
B.2 Hyper-parameter analysis
We empirically investigate the influence of the the prper-parameters of WireMask-EA. EA, i.e., the number of partitions when discretizing the chip canvas into grids, the order of adjusting the positions of macros in objective evaluation, and the mutation operator.
Number of partitions. In our main experiments, the number of partitions is heuristically determined based on detailed macro statistics and varies across different chips, ranging from 108 for adaptec4 to 273 for bigblue4, as shown in Table[5] The first two rows of Table the results of WireMask-Ea after increasing and decreasing the number of partitions by 100, respectively. The last row gives the results of the default WireMask-EA, achieving the highest average rank.
Table 7: HPWL values (x109) obtained by WireMask EA under different grid partition numbers. The symbol x denotes that the method fails to generate non-overlapping placements. The best (smallest) mean value on each chip is bolded. The symbols '+', '_', and "z" indicate that the number of chips where the result is significantly superior to, inferior to, and almost equivalent to the default setting, respectively, according to the Wilcoxon rank-sum test with significance level 0.05.
Method
adoptcc1
adaptec2
aliptee3
anlpptee4
highluel
highlue3
highlue4
+/- 5///*
Avg. Rank
+ +100 gridl mmm
5,88 a 0.89
56.97 + 2.16
59.36 1.10
0.00
62.93 a 3.36
0.22
0/3/4
1.71
100 grid nom
7.07 0.18
x
-
84.37 + 4.14
10.14+0..0
0/4/0
3.00
defanlt setting
5.007
22.63
$7,75
5 1.22
0.11
59,87 3,40
0.28
1.28
By increasing the grid partition number, more fine-grained renotype-phenotyy mapping guided by wire mask can be achieved, but the computational overhead is also increased. the grid partition number is too small, the mapping may even not lead non-overlapping placements, as observed on the chips adaptec2, adaptec3 and adaptec4 after decreasing the grid partition number by 100. Thus, good balance needs to be considered, when determining the grid partition number in practice.
Order of adjusting the positions of macros. In the objective evaluation of WireMask-BBi -BBB, the positions of macros are adjusted sequentially, in the decreasing order of the sum of area of each macro's 's connected cells, as shown in lines 1-2 of Algorithm [ Here, we also test the random adjustment order and the order only considering the area of each macro itself, the results of which are shown in the first two rows, respectively, of Table
Table 8: HPWL values (x10²) obtained by WireMask-EA using different orders to adjust the positions of macros in objective evaluation. The symbol x denotes that the method fails to generate non-overlapping placements. The best (smallest) mean value on each chip is bolded. The symbols "+', and 'z" indicate that the number of chips where the result is significantly superior to, inferior to, and almost equivalent to default setting, respectively, according to the Wilcoxon rank sum test with significance level 0.05.
Benchmark
adaptoel
adoptec2
adaptec3
adaptecd
bighluel
highlue!
bighlued
+/-/x //
Avg. Rank
random order
12.65 0.68
X
X
93.25 2 4.66
3.40 4
x
x
0/3/0
3.00
size only_order order
0.13
47.39 1.02
61.18 1.03
54.57 a 1.69
2.16 0.01
102.99 :: 7.69
10.50 0.24 8,28 0.25
2/5/0
1.71
default setting
5.91 0.07
52.63 2.233
57.75 2 1.16
58.79 1.02
2.12 0.01
59,87 3,40
1.28
16

---

The random order always leads to the worst result, and may even fail to generate oonoolllapping placements. Compared with using the order only considering each macro's area, the original WireMaskk-A performs significantly better on five chips, and worse the other two chips. Its best overall performance is expected, because the order considering the sum of area of each macro's connected cells is more closely related to the performance metric HPWI.
Mutation operator. For WireMask-EA. which performs the best among the three variants of WireMask-BBO. we also examine the influence of its mutation operator. We employed the swap mutation operator in experiments, which randomly selects two macros and interchanges their coordinates. To further investigate, we implement the uniform mutation operator as well, which selects macro random and uniformly reallocates these two mutation operators, with each being executed with a probability of 1/2. As shown in Figure [ the utilization of the swap mutation operator alone (i.e., Swap_only performs better than using the uniform mutation operator alone (i.e., Uniform_only) or their combination (i.e., Mix).
combine the chip canvas. Moreover,
adaptec1
adaptec2
adaptec3
5.8
155
6.6-
HPWL
5.4
75
65
6.0-
3.5
55
Wall Clock Time (min)
Wall Clock (min)
Wall Clock Time (min)
adaptec4
bigbluel
bigblue3
2.45
2.35
00
2.30
HPWL
70
80
2:25
70-
80-
2:15
60
200
600
850
1000
200
402
600
800
1000
200
400
600
800
1000
Wall Clock Time (min)
Wall Clock Time (min)
Wall Clock Time (min)
MaskPlace
Mix
Uniformoony
Swap_only
Figure 5: HPWL (x10)) vs. wall clock time of WireMask-EA using different mutation operators, where the shaded region represents the standard error derived from 5 independent runs.
B.3 Number of evaluations
Table lists the number of evaluations used by WireMask-RS. WireMask-Bol and WareMask-EA in Table 1 each of which runs for 1000 minutes. The number of evaluations of RS and EA is rather close, indicating that our EA operator quite efficient. Besides, BO uses fewer evaluations than RS and EA, owing to the time-consuming cost of updating the Gaussian process model and optimizing the acquisition function.
Table 9: Number of evaluations of WireMask-RS, WireMask-BO and WireMask-EA in Table
1000 min
adaptec1
adaptec2
adaptec3
adaptec4
bigbluel
bigblue3
bigblue4
WireMask-RS RS
3610
3689
5257
2791
7367
976
106
WiOeMask-BO
820
655
810
600
1580
540
59
WireMask-EA
3526
3540
5179
2685
7217
877
17

---

B.4 Results on the ariane benchmark
We evaluate the performance of our WireMask-BBa framework on another benchmark, the ariane RISC-V CPU design [48]. which has been previously studied in works such as [32 [26]. Our evaluation involves a comparison with three analytical methods and three RL methods, and the results are summarized in Table T0 The results of analytical and RI methods are directly from [26] The
analytical methods all fail to generate non-overlapping placement results on ariane, likely due to its high macro area utilization ratio of 0.78, which is the largest among all the benchmarks in Table The overlapping issue is consistent with our discussion presented in Section 2.3 The RL--based methods show significantly worse performance compared to our proposed WireMask-BBO methods. The three different variants of WireMask-BBO are comparable based on the statistical test, with WireMask-EA demonstrating the lowest mean HPWL value.
Table 10: Comparison of HPWL values (x10* the ariane benchmark 48
"x" symbol
means that the method fails the legalization and thus cannot generate non-overlapping placement results. The best (smallest) mean value is bolded. The symbols '+', '-' and "z" indicate that the result is significantly superior to, inferior to, and almost equivalent to WireMask-EA respectively, according the Wilcoxon rank-sum with significance level 0.05.
Method
Type
ariane
+/-/2
NTUPlace3 12
Analytical
X
RePlace
3
Analytical
X
DREAMPlace 28
Analytical
X
Graph 32
RL
1..8
DeepPR [15
RL
52.20 0.89
MaskPlace 26
RI.
14.63 = 0.20
WireMask-RS
Ours
9.90 0.18
22 22
WireMasO-BO
Ours
9.71 + 0.46
WireMask-EA
Ours
9.68 0.61
B.5 Comparison with concurrent works
Recently, ChiPFormer 25 and AutoDMP 4 are proposed as new state-of-the methods in macro
placement. For a comprehensive comparison, we conduct experiments with these two concurrent works here.
incorporates an offline learning decision transformer improve the generalizability. The pre-trained model provides placement results with acceptable quality within minutes, and converges to better results than MaskPlace (26) using fewer evaluations. We have compared our proposed WireMask-EA with ChiPFormer ten chips, outlined in Table The experimental results show that our WireMask-EA clearly outperforms ChiPFormer on circuits out of 10, matter the number of evaluations is 1, 300 or 2k.
ChiPFormer. ChiPFormer 25
AutODMP. AutoDMP [ improves the efficient DREAMPlace 288 using Bayesian optimization to explore the configuration space and showing potential in real EDA application. We have included running time comparison between the state-of-the-arr method AutoDMP [ and our proposed WireMask-EA as shown in Figure The results of MaskPlace (3k evaluations) and ChiPFormer (2k evaluations) are ploted by dotted lines in the figure. We can observe that on the two chip benchmarks, adaptecl and bigbluel, AutoDMP and WireMask-EA quickly, and WireMask-FAA performs the best.
surpass MaskPlace and ChiPFormer
18

---

Table 11: HPWL values (x109) obtained by the recent proposed state-of-the-art method ChiP- Former [25 and proposed WarkMas
chips, including adaptec and bigblue from ISPD2005 benchmark [5] and ibm from ICCAD2004 benchmark [3. The number in () denotes the number of evaluations used. Each result consists of the mean and standard deviation of five runs. The best (smallest) mean value on each chip is bolded.
Benchmark
(1)
(1)
(0.3k)
(0.3k)
ChiPTormer (2k)
adaptecl
8.87 + 0.98
7.20 0.34
7.02 0.11
6.29 + 0.07
6.62 + 0.05
5.96 + 0.08
adaptec2
22.61
61.25
adaptec3
107. à 8.84
75.37 + 2.93
78.32 2.03
64.49 1.69
76.70 1.15
59.26 + 1.30
adaptec4
bigblucl
3.11 + 0.03
2,31 0.06
2.96 = 0.04
2.18
2.95
2.14 0.01
highlue3
131.78 17.36
99.20 24.69
81,48 4.8.3
6..51
72.92.2.566
56.65 2.81
ibm01
4.57 0.27
3.76 0.36
3.61 0.08
2.97
3.05
2.39 0.07
ibm02
6.01 0.441
5.13 0.16
4.84 0.17
3.86
4.24
3,56 1 0.05
jbm03
0.15
3,10 0.12
2.20
1.4 0.06
1.69 0.11
ibm04
0,00
3.60 0.17
0.11
2.93
4.06
2.62 0.04
adaptec1
bigblue1
7.50
3.0
7.25
HPWL
HPWL
2.6
6.50
6.25
2,4
6.00
2.2
5.75
200
400
600
800
1000
0
200
400
600
800
1000
Wall Clock Time (min)
Wall Clock Time (min)
MaskPlace (3k)
ChiPFormer (2k)
AutoDMP
WireMask-EA
Figure 6: HPWL (x10s) vs. wall clock time of WireMask -EA and AutoDMP where the shaded region represents the standard error derived from 5 independent runs.
19


Reviews:
[{"review_id": "fJ6OEHVylj", "reviewer": "Reviewer_3gz2", "summary": "This paper proposes a novel black-box optimization (BBO) framework, namely WireMask-BBO, for macro placement in chip design. Specifically, it devises a post-processing technique that legalizes any searched placement solution while optimizing the half-perimeter wirelength (HPWL). The post-processing technique allows us to perform BBO algorithms to search for solutions with better HPWL. Experiments demonstrate that WireMask-BBO outperforms previous state-of-the-art (SOTA) methods, achieving better HPWL performance in less time.", "questions": "1.\tSince only HPWL is considered as the objective, why does WireMask-BBO also outperforms MaskPlace in congestion?\n2.\tWhat are the results of routing wirelengths?\n3.\tUnder this framework, how to take cell placement or some important yet computationally insufficient metrics into consideration?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThis paper explores BBO methods for macro placement, which may provide a new insight for the research community.\n2.\tThe proposed post-processing technique is simple yet effective. It also has a good versatility because it can be combined with other placement methods and BBO methods.", "weaknesses": "1.\tThe propose of the post-processing is purely heuristic. The motivation is unclear and intuitive explanation for the advances is insufficient.\n2.\tThe proposed method only targets on optimizing HPWL, without explicitly considering other important metrics like routing wirelength or congestion. It does not consider cells and routing either. Moreover, the framework can be hardly transferred to tasks with those metrics under consideration, which limits its real application in EDA.\n3.\tBecause introducing BBO-based methods is one of the core contributions of this paper, the authors may want to illustrate the implementation of BBO algorithms for macro placement more detailly.\n4.\tIn Algorithm 1, the macros are ordered decreasingly according to areas, while in Figure 3, the smaller macro-A is considered first.\n5.\tA recent related work [1] is missing.\n[1] Lai Y, Liu J, Tang Z, et al. Chipformer: Transferable chip placement via offline decision transformer. ICML 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments. Below please find our response.\n\n### Q1 The proposed method is heuristic; insufficient intuitive explanations.\n\nWe want to clarify our motivation of designing the proposed framework. To efficiently improve the HPWL of a solution and guarantee non-overlapping, we first design a greedy procedure guided by wire mask, which sequentially adjusts each macro of the solution to a position with the minimum marginal increment on HPWL. The adjustment order of each macro is determined by the area of all the cells connected with it, and all macros will be adjusted sequentially in the decreasing order of their corresponding computed areas, which is because a macro with a larger computed area implies connecting with more large cells and thus is intuitively more important. In the adjustment of each macro, if the position with the minimum marginal increment on HPWL is not unique, the one closest to its original position is selected, which can utilize some global information of the original placement to reduce the risk of getting trapped in local optima due to the greedy nature. Based on this greedy procedure, we further apply BBO algorithms for exploration, to search for solutions with better HPWL. We believe our proposed framework is intuitive and reasonable. We will add more explanations in the paper. Thank you.\n\nQ2 Optimize HPWL of macros only; how to take cell placement or more metrics into consideration? \n\nThanks for your question, which is indeed a challenge faced by the area of macro placement. Following previous works (Graph Placement, DeepPR and ChiPFormer), we selected HPWL as the objective to be optimized, because it is a good approximation for wirelength and is also efficient to compute. Meanwhile, more metrics can be considered in our proposed BBO framework by directly treating them as the optimization objective. But there are two issues to be tackled before application. Firstly, as you indicated, the metric may involve cell placement and can be computationally expensive. To address this issue, one possible way is to employ advanced BBO techniques such as SAASBO [1] and Guided-ES [2], which can efficiently optimize expensive functions. Note that our framework is general and can be equipped with any BBO algorithm. For example, we only employed simple BBO techniques in the paper, which, however, has led to superior performance over previous methods. Secondly, our greedy procedure requires a criterion (e.g., HPWL used in the paper) which can guide the improvement of a solution and can also be computed step by step. For this issue, we may design a surrogate metric to approximate the true one, e.g., we can use RUDY to approximate the congestion. We will revise to add some discussion, and treat it as an important future work to explore. Thank you. \n\n### Q3 More details of the implementation of BBO algorithms.\n\nWireMask-BBO employs a wire-mask-guided greedy adjustment procedure (generating feasible solutions with high quality efficiently), to serve as a black-box function, and adopts RS, BO and EA for optimization. To be specific, RS generates solutions by allocating all macros' positions randomly, and records the historical best. BO establishes a surrogate model, and samples a new solution by optimizing an acquisition function based on the surrogate model. We used the specific BO, TuRBO, in the paper. EA maintains a population of solutions, and iteratively improves the population by recombination and mutation. In the paper, we used a simple EA which maintains only one solution and uses mutation only. We designed the mutation operator by randomly selecting two macros and exchanging their coordinates in a solution. We are sorry for not illustrating them detailly enough, and will add more discussions in the paper. Thank you for your suggestion.\n\n### Q4 Macro-A considered first in Figure 3? \n\nAs described in line 188, Page 5, the placement order of a macro is determined by the sum of area of all its connected macros (including itself), instead of the macro's own area. In Figure 3, the macro A is connected to both B and C, which has the largest connected area, and thus is adjusted first. We will revise to make it clearer.\n \n### Q5 Comparison with ChiPFormer.\n\nPlease refer to Q1 in general response. \n\n### Q6 Why congestion better? \n\nPlease refer to Q2 in general response.\n\n### Q7 Routing wirelengths? \n\nYes, routing wirelength is a critical metric, whose evaluation is, however, expensive because it must be evaluated after standard cell placement and routing, and the evaluation itself is time-consuming. This is the motivation that we use HPWL as a surrogate, as also did in many previous works. Thanks to your suggestion, we have tried to report the routing wirelengths.\n\nFor the routing task, our currently adopted benchmarks (i.e. ISPD05 and ICCAD04) are not supported by open source router OpenROAD or NCTU-GR 2.0. Thus, we turn to the DAC2012 benchmark [3] for routing wirelength evaluation with DREAMPlace for standard cell placement and NCTU-GR 2.0 for routing. For the proposed algorithm WireMask-EA, we first use it to generate a macro placement, and then adopt DREAMPlace for the subsequent standard cell placement. For DREAMPlace, we set all macros to be movable, and optimize macros and standard cells together. The full placement HPWL and the total wirelength results reported by NCTU-GR 2.0 are shown in Table 2 in the PDF. Due to time limitation, we select superblue19 with 286 macros for test. The results show that WireMask-EA achieves both better HPWL and routing wirelength. We will run the experiments on more benchmark chips from DAC2012, and add them into the final version. Thank you.\n\nReferences\n\n[1] High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces. UAI'21.\n\n[2] Guided Evolutionary Strategies: Augmenting Random Search with Surrogate Gradients. ICML'19.\n\n[3] The DAC 2012 Routability-Driven Placement Contest and Benchmark Suite. DAC'12."}, {"review_id": "Nnk09lcBQl", "reviewer": "Reviewer_nUfA", "summary": "The authors propose a new placement method that is based on the black-box framework. The framework leverages the wire mask-guided information and can achieve significant placement results compared with the state-of-the-art methods.", "questions": "1. Have you tested the effect of the number of initial states on the final results?\n\n2. Why your method can get better congestion results when you do not consider it in your method.\n\n3. The efficient comparison only provides the clock time. However, the number of search steps is also substantial. Could you provide how many steps you use for each circuit (or how much clock time is consumed to perform a step)?\n", "limitations": "Yes.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The novel method is based on black-box optimization, which has not been implemented on the placement task before. Although many RL methods have been proposed, they are not very efficient enough. Black-box optimization might be a viable direction. \n\n2. The wire mask as the guide for generating phenotype representation is also very novel. It can quickly render a suitable solution based on the initial representation, improving efficiency. \n\n3. The experiments are very comprehensive and solid, showing that the performance of the proposed method can consistently outperform existing methods.\n\n4. The paper writing is well-written and easy to understand.\n\n5. The code is open-source, improving reproducibility.\n", "weaknesses": "1. The full placement cannot surpass the DREAMPlace, which means the proposed method can only work well in macro placement.\n\n2. The reasons for the improvement in the congestion metric are not clear. The method does not consider the congestion metric in its search process.\n\n3. The recent work [1] based on Maskplace should also be discussed in the related work part.\n\n[1] Lai Y, Liu J, Tang Z, et al. Chipformer: Transferable chip placement via offline decision transformer.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable and positive comments. Below please find our response.\n\n### Q1 The full placement cannot surpass DREAMPlace.\n\nIn Table 6 of Appendix B.2, though DREAMPlace achieves the best HPWL in 3 out of 7 tested chips, our proposed WireMask-EA has significant improvements in four chips, significant disadvantages in two chips, and no significant difference in one chip, according to the Wilcoxon rank-sum test with significance level 0.05. This indicates an overall superiority of our proposed method. However, we cannot guarantee consistent superiority over DREAMPlace in all data sets. This is because for the full placement task, WireMask-EA first conducts macro placement and then uses DREAMPlace for standard cell placement, while DREAMPlace considers the placement of macros and standard cells simultaneously, which may lead to favorable results. One of our future work is to consider standard cell placement in our framework, as stated in the limitation part. Thank you.\n\n\n### Q2 Why congestion better?\n\nPlease refer to Q2 in general response.\n\n### Q3 Discussion on ChiPFormer [1].\n\nPlease refer to Q1 in general response. \n\n### Q4 Influence of the number of initial states?\n\nThe Evolutionary Algorithm (EA) adopted in our paper starts from one single initial solution, and iteratively improves it by mutation and selection. The initial solution is generated by selecting the best from a pool of 100 random solutions. We guess that you may wonder the influence of the pool size here. Thanks to your suggestion, we have tested WireMask-EA on the chip adaptec1 using the pool size of 1, 10, 20, 50, 200, and 2000. For each run of WireMask-EA, the total number of evaluations used is set to 2000, which has included the number of evaluations (i.e., the pool size) for initialization. Note that WireMask-EA with the pool size of 2000 is just WireMask-RS which performs random search. The final HPWL values are shown below. We can observe that as the pool size increases gradually, which will lead to a better initial solution, WireMask-EA achieves better (smaller) HPWL. However, when the pool size is large enough (e.g., 200 here), the performance of WireMask-EA starts to degrade, which is expected because too many evaluations are used for initialization (which performs random search) and the following exploration by EA tends to be insufficient. We used the pool size 100 in our experiments. Meanwhile, we can observe that WireMask-EA with any pool size can surpass the state-of-the-art method ChiPFormer, which achieves the HPWL value 6.62 ± 0.05 after using 2000 evaluations, as shown in the first line of Table 1 of the accompanying PDF file.\n\n| Pool size for initialization | 1           | 10          | 20          | 50          | 100         | 200         | 2000        |\n| ---                          | ---         | ---         | ---         | ---         | ---         | ---         | ---         |\n| adaptec1                     | 6.50 ± 0.34 | 6.22 ± 0.10 | 6.14 ± 0.06 | 6.11 ± 0.09 | 5.96 ± 0.08 | 5.98 ± 0.06 | 6.13 ± 0.05 |\n\n### Q5 How many steps used for each circuit?\n\nThanks for indicating this issue. In the experiments, our method is run for 1000 minutes on each chip. The number of search steps used for each chip is shown below, which will be included in the revised version. Thanks to your suggestion in Q3, we have compared WireMask-EA with ChipFormer under the same number of search steps, as shown in Table 1 of PDF file. We can observe that using 1, 300 or 2k steps, WireMask-EA outperforms ChipFormer in 9 out of 10 chips. We will revise to add some discussion. Thank you.\n\n| 1000 min    | adaptec1 | adaptec2 | adaptec3 | adaptec4 | bigblue1 | bigblue3 | bigblue4 |\n| ----------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |\n| WireMask-RS | 3610     | 3689     | 5257     | 2791     | 7367     | 976      | 106      |\n| WireMask-BO | 820      | 655      | 810      | 600      | 1580     | 540      | 59       |\n| WireMask-EA | 3526     | 3540     | 5179     | 2685     | 7217     | 877      | 97       |\n\n\nReferences\n\n[1] ChiPFormer: Transferable Chip Placement via Offline Decision Transformer. ICML'23."}, {"review_id": "ntO0I1YdxW", "reviewer": "Reviewer_KNNs", "summary": "This paper presents a framework using BBO for macro placement in VLSI designs. Any placement solution for a set of macros can be optimized using the wire masks (presented in a prior work using RL) where the optimization goal is to minimize the HPWL of the output. In addition to random inputs, the framework can also be used for further enhancement of any existing solutions.", "questions": "Why is EA-based framework better than the other two BBO algorithms?\n\nWhy cannot the proposed framework used for standard cell placement? Can't you use a more fine-grained canvas for the problem, where the standard cells are larger than the grid size?", "limitations": "The computational time for the proposed work seems to be high. Therefore, in the experimental section, the paper does not include the complex benchmark that has thousands of macros to be placed. This contradicts with the claim the paper that this approach is scalable.\n\nThe evaluation of the proposed method only uses 5 random seeds. It would be more convincing if the paper includes more experimental data.\n\nThe proposed framework cannot place the standard cells in the design. Therefore, the comparison between this work and the existing methods seems to be unfair.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The work tackles a critical problem in VLSI designs. \n\nThe idea of casting the placement problem to a BBO is interesting and novel.\n\nThis framework can be used to further improve any existing solutions for the macros. This can be used as another step in PnR with reasonable runtime.\n\nOverall, the paper explains the problem, the existing solutions, and the proposed work clearly.", "weaknesses": "The idea of casting the placement problem to a BBO is interesting and novel. However, as the authors admit in Section 1 that this work does not develop any new BBO algorithm. To the reviewer, the experimental results are not extensive and convincing; this is described in the limitation section. \n\nThe paper also states in the conclusion that it can only place macros but not standard cells without explanation, which limits the application of the proposed work to the actual VLSI problem. On the other hand, this framework can be used to further improve any existing solutions for the macros. This can be used as another step in PnR with reasonable runtime.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments. Below please find our response.\n\n### Q1 Does not develop any new BBO algorithm.\n\nWe want to emphasize that our main contribution is introducing the general framework WireMask-BBO for macro placement, while not developing new BBO algorithms. WireMask-BBO can be equipped with any BBO algorithm. Our experiments show that even employing simple BBO techniques has led to superior performance over previous methods, suggesting that WireMask-BBO may be a new viable direction for macro placement. We agree that developing new efficient BBO algorithms under the framework WireMask-BBO is important for handling very large-scale circuits, as stated in our limitation part. But we believe that the contribution of proposing WireMask-BBO is significant enough. In fact, we plan to open-source WireMask-BBO and use it as an optimization benchmark to encourage the invention of more efficient BBO algorithms for solving macro placement problems, as well as broaden the application scenario of BBO.\n\n### Q2 Why cannot be used for standard cell placement?\n\nAs you indicated, the proposed framework can be naturally applied to standard cell placement by using a fine-grained canvas where the number of grids is larger than that of standard cells. However, the number of standard cells can be million, resulting in a very large search space. Furthermore, the wire-mask-guided greedy procedure for objective evaluation will be very expensive, which requires the calculation of wire mask for each cell. A more fine-grained canvas will also increase the wire mask computation time. Thus, our proposed WireMask-BBO currently cannot deal with standard cells. In fact, the limitation is shared with those methods based on step-by-step placement formulation, including Graph Placement, DeepPR, MaskPlace and ChiPFormer. We will revise to add some discussion. Thank you.\n\n### Q3 Why is EA better than the other two BBO algorithms?  \n\nRS relies solely on random sampling without leveraging any search history. BO performs well in many low-dimensional tasks (typically when the dimension $d \\leq 20$ [1]), but suffers from the curse of dimensionality due to the time-consuming cost of updating the Gaussian process surrogate model and optimizing the acquisition function [2]. For example, in our experiments where $d$ (i.e., 2 times the number of macros) is always larger than 1000, EA can sample much more solutions (about 2--7 times) than BO during the 1000-minutes running. For the EA, we designed a specific mutation operator, which may also contribute its efficiency. We will revise to add more explanation. Thank you.\n\n### Q4 Computational time high? Scalability? \n\nPlease refer to Q1 in the response to Reviewer n9zj due to space limitation.\n\n### Q5 More random seeds? \n\nFive random seeds are commonly used in previous works, e.g., MaskPlace and the recently proposed ChiPFormer [3]. However, we agree that using more random seeds would be better. Thanks to your suggestion, we have conducted additional experiments with 30 random seeds, testing WireMask-EA using 2000 evaluations on ibm01 and ibm02 benchmark. The obtained HPWL values (mean ± std.) are 2.48 ± 0.13 and 3.60 ± 0.11, respectively. When using 5 random seeds, they are 2.39 ± 0.07 and 3.56 ± 0.05, respectively. We believe that the slight difference will not affect the conclusions. For example, the results of the state-of-the-art method ChipFormer using 5 random seeds are 3.05 ± 0.01 and 4.24 ± 0.25, respectively, as shown in Table 1 of the PDF file; we can observe that they have clear gaps with the results of WireMask-EA. Due to time and computational resource limit, we were only able to run more random seeds on these two tasks. We will cover a wider range of tasks in the revised version. Thank you for your suggestion. \n\n### Q6 The proposed framework cannot place the standard cells in the design. Therefore, the comparison between this work and the existing methods seems to be unfair.\n\nThe previous methods SP-SA, Graph Placement, DeepPR+, MaskPlace, ChiPFormer, and the proposed WireMask-BBO all concentrate on macro placement. When comparing the results of full placement, the same DREAMPlace is applied to the macro placement generated by each method for the subsequent standard cell placement. Thus, the comparison is fair. In fact, such a flow has also been adopted in previous works, e.g., MaskPlace and ChiPFormer. We will revise to make it clearer.\n\n\nReferences\n\n[1] A Tutorial on Bayesian Optimization. 2018.\n\n[2] A Survey on High-dimensional Gaussian Process Modeling with Application to Bayesian Optimization. ACM TELO'22. \n\n[3] ChiPFormer: Transferable Chip Placement via Offline Decision Transformer. ICML'23."}, {"review_id": "fInsOL4FDg", "reviewer": "Reviewer_n9zj", "summary": "This paper proposes a new black-box optimization framework, called WireMask-BBO, for macro placement, which is an important problem in the electronic design automation (EDA) community. By using different black-box optimization algorithms, The experiments show it can achieve improvements (shorter half-perimeter wirelength (HPWL)) over previous methods.", "questions": "(1)\tHow about the performance comparison with the state-of-the-art macro placement method in the experiments?\n(2)\tHow about the runtime of the proposed method and compare it with other methods?\n(3)\tIs it necessary to tune hyperparameters extensively to achieve good results in the experiments?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The general framework WireMask-BBO proposed by this paper somewhat provides new angle for macro placement problem. The paper is well-written and it is easy to follow.", "weaknesses": "The scalability of the proposed method is doubtful because Bayesian optimization and evolutionary algorithm may not be suitable for large-scale problems.\nThe experiments are insufficient. The experiments don’t compare with the state-of-the-art macro placement method. The experiments don’t compare the runtime of the proposed method with other methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and suggestions. Below please find our response.\n\n### Q1 Runtime comparison; scalability of WireMask-BBO; BO and EA not suitable for large-scale problems?\n\nIn our experiments, both the packing-based method SP-SA and our proposed WireMask-EA run for 1000 minutes. The results in Table 1 in the paper show that WireMask-EA achieves much better HPWL than SP-SA, implying that WireMask-EA is more efficient. The three analytical methods, NTUPlace3, RePlace and DREAMPlace, are very efficient, because the original complex problem is solved by relaxing to a mathematical programming problem. Compared with the state-of-the-art RL-based method MaskPlace, the results in Figure 4 in the paper have shown that WireMask-EA is much more efficient, which takes an average of 8 minutes to surpass the 200-minutes converged result of MaskPlace across six benchmark chips. Thanks to the suggestion of Reviewers 3gz2 and nUfA, we have compared the ChiPFormer method [1], recently published at ICML 2023. The results are shown in Table 1 of the accompanying PDF file. We can observe that after using the same number of evaluations, WireMask-EA outperforms ChiPFormer clearly on 9 out of 10 circuits. That is, WireMask-EA is more efficient than ChiPFormer. Thanks to your suggestion, we have implemented the AutoDMP method, recently published at ISPD 2023. The results in Figure 1 of the accompanying PDF file show that after using the same runtime, WireMask-EA achieves better HPWL than AutoDMP.\n\nBased on the above comparison, we can find that WireMask-EA has better scalability than previous methods except analytical ones. This can also be validated by the chip scales used in the experiments of these works. For example, only 3 data sets in ChiPFormer [1] contain more than 1000 macros (1329, 1293 and 1024, respectively); only two data sets in DeepPR+ [2] have over 1000 macros (1309 and 1227, respectively). When facing large data sets like bigblue4 with 8170 macros, these two works selected only hundreds of macros manually for placement. In the experiments of AutoDMP [3], only at most 320 macros are to be placed. Note that in our work, we have run the proposed framework WireMask-BBO on the full bigblue4 benchmark with 8170 macros, which is the largest scale reported so far, to the best of our knowledge.\n\nHowever, it must be acknowledged that our framework WireMask-BBO still struggle with very large-scale data sets, e.g., bigblue2 with 23084 macros. As WireMask-BBO can be equipped with any black-box optimization (BBO) algorithm, one direct way is to employ efficient Bayesian Optimization (BO) or Evolutionary Algorithm (EA) for high-dimensional scenario. Note that we only employed simple BBO techniques in the paper, which has led to superior performance over previous methods. Though BO and EA are traditionally inefficient for high-dimensional problems, many efforts have been put into this topic, generating many efficient BBO algorithms, e.g., RDHEBO [4] based on decomposition [4], ALEBO based on embbeding [5], MCTS-VS-BO based on variable selection [6], and self-guided evolutionary strategy [7]. We will revise to include the runtime comparison and add more discussion. Thank you.\n\n\n### Q2 Comparison with AutoDMP [3].\n\nThank you for pointing out this related method AutoDMP, which is recently published at ISPD'23. It is built mainly upon the efficient DREAMPlace, using BO to explore the configure space and showing potential in real EDA application. We have revised to add the comparison with AutoDMP. Due to time and computational resource limit, we were only able to run on the two chips, adaptec1 and biglue1. The results are shown in Figure 1 of the PDF file. We can observe that WireMask-EA outperforms AutoDMP. We will run AutoDMP on all the tasks, and include it in the final version. Thank you for your suggestion. \n\n\n\n### Q3 Is it necessary to tune hyperparameters extensively to achieve good results in the experiments?\n\nWe did not tune hyperparameters extensively. When applying the general framework WireMask-BBO, there are only two hyperparameters to be set, i.e., the number of partitions of the chip canvas and the employed BBO algorithm. In our experiments, the number of partitions is heuristically determined based on detailed macro statistics and varies across different chips, as shown in Table 4 of Appendix. Thanks to your suggestion, we have run the proposed WireMask-EA with 224 partitions for all the chips, which is consistent with the setting of MaskPlace. The results are shown in Table 3 of the PDF file. We can observe that WireMask-EA is still always better than MaskPlace and ChiPFormer, implying its robustness to the number of partitions of the chip canvas. Regarding the employed BBO algorithm, our experiments have shown that employing random search, a simple EA or the BO algorithm TurBO can all lead to superior performance over previous methods, implying the robustness of WireMask-BBO to the employed BBO algorithm. Note that for each employed BBO algorithm itself, we used its default hyperparameters for all chips. Thus, we believe our proposed framework WireMask-BBO is easy to use in practice. We hope our explanation can address your concerns. Thank you.\n\n\nReferences\n\n[1] ChiPFormer: Transferable Chip Placement via Offline Decision Transformer. ICML'23.\n\n[2] The Policy-Gradient Placement and Generative Routing Neural Networks for Chip Design. NeurIPS'22.\n\n[3] AutoDMP: Automated DREAMPlace-based Macro Placement. ISPD'23.\n\n[4] Are Random Decompositions all we need in High Dimensional Bayesian Optimisation? ICML'23.\n\n[5] Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization. NeurIPS'20.\n\n[6] Monte Carlo Tree Search based Variable Selection for High Dimensional Bayesian Optimization. NeurIPS'22.\n\n[7] Self-Guided Evolution Strategies with Historical Estimated Gradients. IJCAI'20."}]

Author rebuttal:
## General response

We are very grateful to the reviewers for carefully reviewing our paper and providing constructive comments and suggestions. We have revised the paper carefully according to the comments and suggestions, but we cannot upload the paper due to the NeurIPS' rule this year. Our response to individual reviewers can be found in the personal replies, but we also would like to make a brief summary of revisions about experiments for your convenience.

- We add the comparison with two important state-of-the-art methods, ChiPFormer [1] and AutoDMP [2]. 

- We add more benchmarks to test different methods, i.e., ibm series from ICCAD'04 benchmark [3].

- We add some results of routing wirelength.

- We add the analysis of the initial pool size and the partition number of the canvas for WireMask-EA.

- We add more random seeds (from 5 to 30) on some benchmarks.

- We add the details of the number of search steps during the 1000-minutes optimization of the proposed WireMask-BBO.

Below are responses to some common questions.

### Q1 Why not consider ChiPFormer [1]?

ChiPFormer, a recent paper published at ICML 2023 and initially released on arXiv on June 26, 2023, has gained our attention when it was published. However, due to its release date falling after the NeurIPS 2023 submission deadline, we were unable to include it in our manuscript.

ChiPFormer adopts an offline RL method, focusing on the HPWL metric of macro placement during optimization, and is equipped with a mixed-size placement workflow. The method demonstrates remarkable performance on various chip placement tasks. We acknowledge that incorporating a comparison with ChiPFormer would enhance the comprehensiveness of our work.

To ensure a fair evaluation, we promptly reached out to the authors of ChiPFormer upon reading their paper and obtained a standardized processed dataset (named ibm01--ibm04). We compared our proposed WireMask-EA with ChiPFormer on ten chips, as outlined in Table 1 of the accompanying PDF file. Notably, WireMask-EA outperforms ChiPFormer clearly on 9 out of 10 circuits, regardless of the number of evaluations employed (1, 300, or 2k).

We will discuss ChiPFormer in our paper, as well as include experimental comparisons. Thank you for your valuable feedback. 

### Q2 Why congestion is better when only HPWL is optimized?  

We feel sorry that we did not provide a persuasive explanation for such an important scenario in our paper, but we try to explain it here. We choose the widely adopted RUDY (Rectangular Uniform wire DensitY) to approximate congestion. Our conclusion is that the RUDY approximation of congestion is sometimes positively related to the HPWL metric, by analyzing the computation of HPWL and RUDY. Given a macro placement solution, the HPWL is computed as the sum of the rectangle's half-perimeter of each net (hyper-edge), i.e., $\sum_{e_j \in E} (w_j+h_j)$, where $e_j$ denotes a net, $E$ denotes the hyper-graph comprised of all nets, $w_j$ and $h_j$ denote the width and height of the rectangle corresponding to $e_j$, respectively. The RUDY measures the overall congestion on the canvas, and the congestion of each grid $g_i$ on the canvas is calculated by the cumulative impact of all nets encompassing the grid. Note that a net $e_j$ will add an impact to each of its covered grids by $\frac{1}{w_j} + \frac{1}{h_j}$. Then, the overall congestion of all grids is $\sum_{g_i} \sum_{e_j \in E(g_i)} \frac{1}{w_j} + \frac{1}{h_j}=\sum_{e_j \in E} w_j\cdot h_j\cdot (\frac{1}{w_j} + \frac{1}{h_j})=\sum_{e_j \in E} (w_j+h_j)=\mathrm{HPWL}$, where $E(g_i)$ denotes the set of nets whose corresponding rectangle covers the grid $g_i$. Note that the first equality holds because the number of times of a net $e_j \in E$ enumerated in LHS is equal to the number of grids covered by it, which is $w_j \cdot h_j$. Thus, we can observe a positive relation between RUDY and HPWL. Besides our empirical results, Table 4 in MaskPlace [4] and Table 4 in ChiPFormer [1] have also shown that the best HPWL can lead to the best congestion. However, we should also note that a lower HPWL does not necessarily lead to a lower RUDY, because RUDY only considers top-10\% congested grids. We will revise to add more discussion. Thank you.


References


[1] ChiPFormer: Transferable Chip Placement via Offline Decision Transformer. ICML'23.

[2] AutoDMP: Automated DREAMPlace-based Macro Placement. ISPD'23.

[3] ICCAD’04 Mixed-size Placement Benchmarks. 2009.

[4] MaskPlace: Fast Chip Placement via Reinforced Visual Representation Learning. NeurIPS'22.

Meta-review: This paper proposes a general learning framework based on black-box optimization (BBO) methods for macro placement in very large-scale integration (VLSI) design. Experiments demonstrate that the proposed method significantly outperforms previous state-of-the-art (SOTA) methods.

All the reviewers agree that the investigated problem is important, the proposed approach provides a new research direction for macro placement problem, and experiments show good improvements. Overall, the paper is valuable for this community. The reviewers provided some constructive suggestions and asked clarifying questions. The authors have done a very good job in answering the questions during the rebuttal phase.

Overall, I recommend accepting the paper and strongly encourage the authors to revise the paper to reflect the reviewer-author discussion for the final submission.
Decision: Accept (poster)