# PARSAC: Fast, Human-quality Floorplanning for Modern SoCs with Complex
Design Constraints

Hesham Mostafa  Intel LabsUSA ,  Uday Mallappa  Intel LabsUSA ,  Mikhail
Galkin  Intel LabsUSA ,  Mariano Phielipp  Intel LabsUSA and  Somdeb Majumdar
Intel LabsUSA

###### Abstract.

The floorplanning of Systems-on-a-Chip (SoCs) and of chip sub-systems is a
crucial step in the physical design flow as it determines the optimal shapes
and locations of the blocks that make up the system. Simulated Annealing (SA)
has been the method of choice for tackling classical floorplanning problems
where the objective is to minimize wire-length and the total placement area.
The goal in industry-relevant floorplanning problems, however, is not only to
minimize area and wire-length, but to do that while respecting hard placement
constraints that specify the general area and/or the specific locations for
the placement of some blocks. We show that simply incorporating these
constraints into the SA objective function leads to sub-optimal, and often
illegal, solutions. We propose the Constraints-Aware Simulated Annealing (CA-
SA) method and show that it strongly outperforms vanilla SA in floorplanning
problems with hard placement constraints. We developed a new floorplanning
tool on top of CA-SA: PARSAC (Parallel Simulated Annealing with Constraints).
PARSAC is an efficient, easy-to-use, and massively parallel floorplanner.
Unlike current SA-based or learning-based floorplanning tools that cannot
effectively incorporate hard placement-constraints, PARSAC can quickly
construct the Pareto-optimal legal solutions front for constrained
floorplanning problems. PARSAC also outperforms traditional SA on legacy
floorplanning benchmarks. PARSAC is available as an open-source repository for
researchers to replicate and build on our
results111https://anonymous.4open.science/r/PARSAC-52CD.

Block-level Floorplanning, Parallel Search, Simulated Annealing

##  1\. Introduction

The design of integrated circuits (ICs) is divided into the front-end and
back-end design phases. The front-end phase focuses on system specifications,
architectural design choices and logic realization - in the form of gates and
registers- of the circuit. The resulting logic circuit from the front-end
phase is used as the starting point for the back-end design phase. The goal of
the back-end phase is to provide optimal shapes and locations of logic blocks
and to create interconnects. The back-end flow can be broadly divided into the
following steps: partitioning, physical mapping (floorplanning or chip
planning, placement, and routing), and sign-off (timing, power, and physical
verification).

Figure 1. The SoC and sub-system floorplanning task includes hierarchy-level
partition shaping, partition placement and pin placement on the partition. Our
work is applicable to both SoC and sub-system level partition placement and
partition shaping.

Motivation: In the back-end phase, before performing physical mapping of the
circuit, it is essential to partition larger flat circuit netlists into more
manageable circuits or blocks. This partitioning process is predominantly
influenced by factors such as the computational capabilities of Electronic
Design Automation (EDA) tools, the availability of tool licenses, the size of
the design team, and the time constraints for completion of the project.
Therefore, design methodology teams use a top-down hierarchical approach,
where the SoC is typically partitioned into smaller sub-systems, and sub-
systems are further partitioned into smaller functional modules, that can be
designed efficiently by the EDA tools. At each of these hierarchies (SoC and
sub-system), the floorplanning step aims to determine the optimal physical
locations and shapes of the individual blocks constituting the SoC or a
subsystem. The outputs from the partitioning step are partition-level area
budgets, partition-level connectivity information, connectivity to external
terminals, and the locations of external terminals. These serve as the input
to the floorplanning problem. In addition, the floorplanning problem typically
has several constraints that govern the legal positions of some of the blocks.
Floorplanning stands as a pivotal step in the IC design cycle, serving as a
crucial bridge connecting the front-end and back-end phases of the design
process. It gives early feedback on the architectural choices and the output
of the floorplanning phase, such as the placement of blocks and their shapes,
impacts downstream physical design targets.

At a high-level, the floorplanning formulation is a multi-objective
optimization problem involving assignment of locations and shapes to
individual blocks, while considering various design constraints. It is
typically characterized by the following inputs, constraints and outputs.

Inputs: Given:

  * •

a set $B=\\{b_{1},b_{2},...,b_{k}\\}$, comprising $k$ circuit blocks (we also
interchangeably refer to them as modules or blocks).

  * •

a set $A=\\{a_{1},a_{2},...,a_{k}\\}$, representing the estimated post-routed
layout area budgets of each partition.

  * •

a set $T=\\{t_{1},t_{2},...,t_{r}\\}$, representing $r$ terminals for external
interfacing of the floorplan system. Each terminal is a point in 2-D space
(typically on the periphery of the system).

  * •

a circuit hyper-graph $G$ that captures the connectivity information which is
comprised of hyper-edges $E=\\{e_{1},e_{2},...e_{n}\\}$, representing $n$
hyper-nets to capture block-to-block and block-to-terminal connections. Hyper-
edge $e_{i}$ is the set of blocks and/or terminals that are connected together
through net $i$.

Constraints:

  * •

Outline constraints: Modern ASIC design relies on a hierarchical (top-down)
floorplanning style, with a ”fixed-outline” or ”fixed-die” requirement for the
SoC and its sub-systems. A floorplan optimized for area without accounting for
the fixed-outline constraint may prove impractical, as it may fail to fit
within the specified outline.

  * •

Boundary constraints: These indicate that a partition must align with a
specific edge or corner of the floorplanning outline. This alignment is
necessitated by external interfacing requirements of the blocks or system-
level thermal considerations.

  * •

Grouping constraints: These require that some blocks must be physically
abutted. This is particularly pertinent for blocks operating on the same
voltage or those that need to be simultaneously powered off.

  * •

Pre-placement constraints: This captures previously-established optimal
placement locations of blocks that are reused from legacy designs.
Furthermore, throughout the physical design phase, as partition-level area
budgets become more refined due to stable RTLs and feedback from the physical
design flow, certain blocks may undergo reshaping, while stable blocks may
remain unaffected. Such stable blocks become part of the pre-placement
constraints.

Objective: Assignment of overlap-free block locations,
$L=\\{(x_{i},y_{i})|i=1,2,...k\\}$, and block aspect ratios,
$R=\\{ar_{1},ar_{2},...,ar_{k}\\}$, such that all constraints are satisfied
and the following multi-objective cost metric is minimized:

(1) $Cost=\alpha*HPWL+\beta*area.$

Here, $area$ is the area of the bounding box of all placed blocks and $HPWL$
is the half-perimeter wire-length. $\alpha$ and $\beta$ are the HPWL and area
cost weights, respectively. HPWL is defined as follows: let
$\\{(x_{i,1},y_{i,1}),\ldots,(x_{i,n_{i}},y_{i,n_{i}})\\}$ be the center
points of the blocks and/or the locations of the terminals that belong to net
$i$, HPWL is given by:

(2)
$HPWL=\frac{1}{2}\sum\limits_{i=1}^{n}\max\limits_{u,v<n_{i}}|x_{i,v}-x_{i,u}|+\max\limits_{u,v<n_{i}}|y_{i,v}-y_{i,u}|,$

i.e, the cost for each net is half the perimeter of the rectangle encompassing
the net’s endpoints.

##  2\. Related Work

Modern physical design flows solve the floorplanning problem using a top-down
fixed-outline (kahng20, 12) methodology, in which the outline of the floorplan
system is predetermined. A fixed-outline constraint (adya03, 2) is more
challenging than variable-die or outline-free floorplanning, due to a more
restrictive solution space. A good floorplan representation (fprep05, 4, 10)
is crucial to reduce the search space and enable faster convergence to an
optimal solution.The goal of a good representation is to encode the relative
positions and shapes in a way that is amenable to perturbation. Some popular
topological overlap-free floorplan representations are: Normalized Polish
Expression (npe86, 28), Corner Block List (cbl00, 8), O-tree (otree00, 23),
B*-tree (btree06, 5), Corner Sequence (cbl00, 8), Sequence Pair (spair98, 22),
Transitive Closure Graph (tcg01, 18), Transitive Closure Graph - Sequence Pair
(tcgs02, 17), and Adjacent Constraint Graph (acg04, 36). A comprehensive
summary of the trade-off between various representations are summarized in
(fprep05, 4). Computationally, floorplanning is an NP-hard problem. As the
number of blocks grows, the search space tends to grow exponentially. Prior
works for floorplan optimization can be categorized into analytical,
heuristics-based, and learning-based approaches.

Table 1. Summary of previous floorplanning formulations along with the constraints they support. Reference | Fixed-outline | Pre-placed | Boundary | Grouping | Comments
---|---|---|---|---|---
(adya01, 1, 2) | ✓ | ✗ | ✗ | ✗ | SA-based
(young98, 34) | ✓ | ✓ | ✗ | ✗ | SA-based
(young99, 33, 14, 21) | ✓ | ✗ | ✓ | ✗ | SA-based
(learnfp20, 7, 30, 3, 31) | ✓ | ✗ | ✗ | ✗ | Learning-based
(ga00, 27, 24) | ✓ | ✗ | ✗ | ✗ | GA-based
(ant09, 6, 9) | ✓ | ✗ | ✗ | ✗ | ACO-based
(antsa16, 29, 19) | ✓ | ✗ | ✗ | ✗ | Hybrid-based
(lp03, 13, 26) | ✓ | ✗ | ✗ | ✗ | LP-based analytical
(quasi21, 11, 15, 20, 25, 35) | ✓ | ✗ | ✗ | ✗ | Two-stage analytical
(btree06, 5, 16) | ✓ | ✓ | ✓ | ✗ | Sub-optimal packing and simpler testcases
(young04, 32)∗ | ✓ | ✓ | ✓ | ✓ | Soft-penalty and sub-optimal results
Our work | ✓ | ✓ | ✓ | ✓ | Hard constraints and Better results

Analytical & Heuristic Solvers: While analytical solvers that use linear
programming, (lp03, 13) and mixed-integer linear programming (milp91, 26) aim
to solve the exact floorplanning problem using a closed-form solution, such
methods are not scalable as the number of blocks grows. As an alternative,
two-stage analytical solutions (quasi21, 11, 15, 20, 25, 35) propose a
continuous-space coarse floorplanning in the first stage, followed by local
overlap removal and shape refinement in the second stage. Since the second
stage is usually limited to local refinement, the global constraint-awareness
needs to be incorporated into the coarse stage. Therefore, they suffer from
the inability to guarantee violations-free start points for the second stage,
particularly when dealing with complex pre-placed or boundary constraints. In
the class of heuristic optimization, the most common techniques are simulated
annealing (adya03, 2, 5, 16), genetic algorithms (ga12, 24, 27), ant-colony
optimization (ant09, 6, 9), and hybrid methods that combine multiple heuristic
approaches (antsa16, 29, 19).

Learning-based solvers: One emerging category of floorplanning techniques are
learning-based algorithms. Efficient floorplan representations (fprep05, 4)
establish a foundation for formulating the floorplanning problem as a
learning-to-search mechanism. He et al. (learnfp20, 7) use sequence-pair
representations and iteratively search over these representations using a
deep-Q algorithm. GoodFloorplan (gfp22, 30) combines graph convolution and a
sequence-pair formulation to capture the connectivity and topological
information of the layout, and employs an actor-critic network to iteratively
search for better neighboring floorplans. Amini et al. (kdd22, 3) use a deep
reinforcement learning (RL) agent to perform floorplanning, using the corner-
block representation. They focus on wire-length optimization using RL-PPO for
one-shot optimal corner-block construction. However, the absence of
incremental floorplan refinement steps is a major weakness of such one-shot
floorplanners. Defer (defer08, 31) provides a non-stochastic method for
compacting a slicing floorplan, and generates a non-slicing floorplan. By
adopting the principle of Deferred Decision Making (DDM) during the node-
combining step in generalized slicing trees, the slicing tree in Defer
represents a large number of slicing floorplan solutions. Since deferring
ensures that all of these solutions are stored by a single shape curve, they
choose a good slicing floorplan that fits into the fixed outline. All of the
above methods, however, do not consider complex instances of the floorplanning
problem that include pre-placed blocks, boundary, and clustering constraints.
The lack of reproducible code and model architecture details makes it
difficult to validate the claim that these learning-based methods outperform
traditional methods like simulated annealing.

Modern Floorplanning Constraints: Modern industry-relevant floorplanning tasks
generally include some hard placement constraints (young04, 32) such as
boundary (edge and corner), pre-placed blocks, and grouping constraints. One
of the primary drawbacks of existing floorplanning methods is the absence of
mechanisms for automatically incorporating hard constraints. While these
constraints can be represented by extra terms in the cost function, we show
that this ’soft’ representation of the constraints does not work in practice.
(adya01, 1) proposed methods to improve the search efficiency, but that was
restricted to fixed-outline constraints alone. Chang et al. propose a pre-
placement-aware Btree formulation (btree06, 5). The proposed method, however,
leads to large white-space, thereby violating the fixed-outline constraint.
Young et al. handle pre-placement constraints (young98, 34) by focusing on
slicing representations but their approach also leads to sub-optimal white-
space. Murata et al. incorporate pre-placement constraints using a sequence-
pair representation, but also suffer from inefficient packing around the pre-
placed blocks. Although a number of previous works (jianbang01, 14, 21, 33)
include boundary constraints in their formulation, they either fix the
violations in a post-processing step or use a penalty term that makes it a
soft constraint. We could find only one work (young04, 32) that
comprehensively covers all placement constraints using a simulated annealing
approach on sequence-pair representations. They augment the constraint graphs
used in the traditional sequence-pair representation with constraining edges
that indicate placement constraints. This is done by incorporating an
additional penalty cost for infeasible solutions. Such an approach needs
careful balancing of the penalty cost and leads to sub-optimal white-space, as
indicated in their results.

##  3\. Methods

###  3.1. Preliminaries

Before introducing our proposed PARSAC framework in Section 3.2, we first
review the B*-tree representation, its benefits and its solution space.
B*-trees (btree06, 5) are ordered binary trees, augmented with rules that
allow them to model compact floorplans. By definition (btree06, 5), in a
compact floorplan, no block can be moved towards the bottom or to the left of
the floorplan without overlapping another block. This class of area-optimal
floorplans always has an equivalent B*-tree representation. B*-trees are easy
to implement and manipulate using primitive tree operations such as search,
insertion, and deletion which can be done in constant, constant, and linear
time, respectively.

Figure 2. An example of a compacted floorplan (left) and the corresponding
B*-tree (right) representation. Given a compact layout, a tree representation
can be obtained by traversing the blocks, starting from the lower-left module
$b1$. Likewise, given a B*Tree, layout can be obtained by a DFS traversal,
starting from the root node $b1$.

Layout-to-Tree Translation: As shown in Fig.2, the translation operation
between the floorplan layout and the B*-tree representation can be performed
in linear time by using a recursive procedure similar to the depth first
search (DFS) algorithm. In the B*-tree, each node denotes a module, with the
root representing the module on the bottom-left corner of the layout i.e.,
$(x_{1},y_{1})=(0,0)$. The edges of the tree denote a parent-child relation
that indicates the relative placement of two nodes. For example, the left
child $b_{j1}$ of a parent node $b_{i}$ denotes the module that is placed at
the lowest possible position immediately to the right of the parent node i.e.,
$x_{j1}=x_{i}+w_{i}$, where $w_{i}$ is the width of module $b_{i}$. The right
child $b_{j2}$ of a parent node $b_{i}$ denotes the module that is placed at
the lowest possible position above $b_{i}$ i.e., $x_{j2}=x_{i}$. The
$y$-coordinates of the modules can be computed in constant time, using a
doubly-linked horizontal contour data structure(btree06, 5). Similarly, given
a layout, the associated B*-tree can be obtained by traversing the layout
starting from the lower-left module.

Search Space: For a floorplan problem with $k$ modules, the size of the
solution space of possible B*-trees in an unconstrained settings is given by:

$O(k!*\frac{2^{2k}}{k^{1.5}})$

For an SoC with $120$ blocks (typical size of modern SoCs), there are
approximately $10^{250}$ possible solutions. Search methods traverse this
space by iteratively modifying the tree using the following three primitive
operations:

  * •

Swap two nodes.

  * •

Delete a node and insert it elsewhere.

  * •

Modify the shape (or aspect ratio) of a node.

###  3.2. Constraints-aware simulated annealing

Traditional SA seeks to minimize area and wire-length (the cost function
defined in Eq. 1). It does not consider hard placement constraints such as
boundary constraints (some blocks have to be placed at a particular edge or
corner of the floorplan), or pre-placement constraints (some blocks have to be
placed at a specific location). One straightforward way to make SA aware of
these constraints is to include them in the cost function by modifying Eq. 1
to be:

(3) $Cost=\alpha*HPWL+\beta*area+\gamma*number\\_of\\_violated\\_constraints,$

where $\gamma$ is the weight attached to violated constraints. We show,
however, that SA typically fails to satisfy boundary constraints and pre-
placement constraints, even for large values of $\gamma$. The failures of SA
to meet these constraints are typically because SA gets stuck in
configurations with violated placement constraints, but where there is no
single move that would decrease the number of violated constraints. This
situation is illustrated in Fig. 3. We call such a configuration a ‘hard
constraints local minimum’. Such local minima are even harder to escape for
large values of $\gamma$.

Figure 3. An example of a hard constraints local minimum. There is one
violating block (shown with a red outline) that should be placed on the bottom
boundary. The bottom boundary is already filled with constrained blocks.
Moving the violating block and placing it to the right of one of the bottom-
boundary blocks will increase the width of the bottom row and move the right
edge of the floorplan. This will result in constraint violations at all the
constrained right edge blocks (green blocks) because they will no longer be at
the right edge of the floorplan.

The ‘hard constraints local minimum’ problem cannot be solved by tuning
$\gamma$. A larger $\gamma$ would make the probability of escaping the local
minimum harder, while a smaller $\gamma$ would lead to final solutions where
SA decided to violate some hard constraints in favor of reducing $HPWL$ or
$area$. Our core observation is that we cannot depend on traditional SA
mechanisms alone to converge to configurations that satisfy the hard placement
constraints.

We augment SA with two novel techniques to allow it to perform well in the
presence of boundary and pre-placement constraints: constraints-fixing moves
and B*-tree with anchored blocks.

####  3.2.1. Constraints-fixing moves

To solve the ‘hard constraints local minimum’ issue, we augment the standard
SA move set (swapping or moving blocks in the B*-tree or aspect ratio
adjustment) with moves whose sole purpose is to fix violated boundary
constraints. We call these moves constraints-fixing moves. A constraints
fixing move is always accepted, irrespective of how it changes the cost
function. At every SA step, we either try a standard SA move and accept it or
reject it based on the resulting cost delta, or we make a constraints-fixing
move.

Constraints-fixing moves have a low probability of being applied at an SA step
($\approx 0.0005$). Algorithm 1 describes our modified SA move set. Most of
the time, we apply a standard SA move such as swapping, moving, or perturbing
the aspect ratio. Every once in a while, and if there are violated boundary
constraints, we explicitly pick a block that violates the boundary constraints
and fix its constraint violation. We do that in one of two ways:

  1. (1)

If there are blocks at the required boundary (for example left boundary) that
are unconstrained - i.e, these blocks do not have to be at that boundary -
then we swap the violating block with one of these unconstrained blocks.

  2. (2)

If all the blocks at the required boundary are constrained - i.e, they have to
be at that boundary - then we move the violating block and make it the right
child (to be placed on top) or the left child (to be placed to the right) of
one of the constrained blocks at the required boundary.

Algorithm 1 The CA-SA move set

Inputs: $B$: B*Tree

# $rand()$ produces random numbers uniformly in [0,1]

if rand() ¿ 0.0005 or boundary_constraints_satisfied() then

if rand() ¿ 0.333 then $\triangleright$ Aspect-ratio adjustment

$b_{1}\leftarrow pick\\_random\\_block()$

$Perturb\\_AR(b_{1})$

else$\triangleright$ Move or swap blocks

$b_{1},b_{2}\leftarrow pick\\_random\\_block\\_pair()$

if rand() ¿ 0.5 then $\triangleright$ Swap two blocks

$B.swap(b_{1},b_{2})$

else$\triangleright$ Move $b_{1}$ to be child of $b_{2}$

$B.remove(b_{1})$

if rand() ¿ 0.5 then

$B.add(b_{1},b_{2},LEFT)$$\triangleright$ make $b_{1}$ left child of $b_{2}$

else

$B.add(b_{1},b_{2},RIGHT)$$\triangleright$ make $b_{1}$ right child of $b_{2}$

end if

end if

end if

else$\triangleright$ move for fixing boundary constraints violations

$b\leftarrow pick\\_random\\_violating\\_block()$

$S_{u}\leftarrow unconstrained\\_blocks\\_at\\_loc(b.required\\_loc)$

if $S_{u}\neq\Phi$ then $\triangleright$ $S_{u}$ is not empty

$b_{s}\leftarrow random\\_sample(S_{u})$

$B.swap(b,b_{s})$ $\triangleright$ Swap with block at the required boundary

else$\triangleright$ all blocks at required boundary are constrained

$S_{c}\leftarrow constrained\\_blocks\\_at\\_loc(b.required\\_loc)$

$b_{s}\leftarrow random\\_sample(S_{c})$

$B.remove(b)$

if $b.required\\_loc\in\\{left,right\\}$ then

$B.add(b,b_{s},RIGHT)$ $\triangleright$ make $b$ right child of $b_{s}$

else$\triangleright$ $b.required\\_loc$ is top or bottom

$B.add(b,b_{s},LEFT)$ $\triangleright$ make $b$ left child of $b_{s}$

end if

end if

end if

####  3.2.2. B*-tree with anchored blocks

In the presence of pre-placed blocks that have to be placed at specific
$x$-$y$ locations, we can modify the SA cost function to penalize the
placement of these blocks away from the required $x$-$y$ locations. We show,
however, that this usually does not guarantee exact placements at the required
location. To tackle these pre-placement constraints, we modify the way the
B*-tree is represented and the way the floorplan is constructed from the
B*-tree.

We modify the B*-tree so that the blocks with pre-placement constraints ignore
the position dictated by the B*-tree. Instead, they are anchored to the pre-
placed positions. The children of these anchored blocks are still placed
relative to these anchored blocks according to the positions dictated by the
B*-tree. As shown in Fig. 2, the B*-tree is traversed in a left-first, depth-
first manner to sequentially place all the blocks. Algorithm 2 outlines the
steps for placing one block from the B*Tree. The pre-placed constraints are
thus satisfied by construction.

Algorithm 2 Block placement step

Inputs: $b$: block to be placed

if $is\\_preplaced(b)$ then $\triangleright$ Block has preplacement constraint

$b.x,b.y\leftarrow b.preplaced\\_x,b.preplaced\\_y$

else

if $b.parent==None$ then $\triangleright$ $b$ is root

$b.x,b.y\leftarrow 0,0$

else if $b.parent.left\\_child==b$ then

$b.x\leftarrow b.parent.x+b.parent.width$

else$\triangleright$ $b$ is a right child

$b.x\leftarrow b.parent.x$

end if

$b.y\leftarrow compact(b)$ $\triangleright$ Place $b$ at the lowest possible
position

end if

####  3.2.3. Fixed outline and grouping constraints

We incorporate these two constraint categories into our CA-SA pipeline in a
relatively straightforward manner. For the outline constraint, we simply add
an extra cost term in the CA-SA cost functions:

(4)
$cost_{outline}=\eta\left([bbox.W-outline.W]^{+}+[bbox.H-outline.H]^{+}\right),$

where $bbox.W$ and $bbox.H$ are the width and height of the bounding box of
the placed blocks. $outline.W$ and $outline.H$ are the width and height of the
fixed outline in which the blocks need to fit. $[x]^{+}\equiv max(0,x)$ is the
rectification function and $\eta$ is the fixed outline cost coefficient.

We also represent the grouping constraint as an extra term in the cost
function. Let $\\{g_{1},\ldots,g_{G}\\}$ be the required block groupings,
where $g_{i}$ is the set of blocks that belong to group $i$. In an actual
floorplan, the blocks in $g_{i}$ will form $z_{i}$ clusters. The grouping
constraint for $g_{i}$ is satisfied if $z_{i}=1$ The grouping cost is given
by:

(5) $cost_{grouping}=\zeta\sum\limits_{i=1}^{G}\frac{(z_{i}-1)}{|g_{i}|},$

where $\zeta$ is the grouping cost coefficient.

####  3.2.4. Multi-instantiation and shape constraints

Our CA-SA also supports multi-instantiation constraints. A multi-instantiation
constraint requires some blocks to always have the same aspect ratio since
these blocks are instances of the same master. We support these constraints by
always identically perturbing the aspect ratios of these blocks during the
search. Shape constraints limit the minimum and maximum aspect ratios of
blocks. We support them by always clamping aspect ratios back to these limits
if they are pushed beyond them in an SA step. We do not provide results for
these two constraint types as they are straightforward to support in a manner
that guarantees correctness.

###  3.3. PARSAC (Parallel Simulated Annealing with Constraints)

In order to improve the quality of the solutions produced by our constraints-
aware SA pipeline, we developed a parallelization framework that allows us to
effectively scale to an arbitrary number of machines and CPU cores. This
framework, PARSAC, is built on top of ‘PyTorch’ and ‘PyTorch Distributed’. The
general architecture of PARSAC is illustrated in Fig. 4. The core routines of
CA-SA are implemented in C++. We create a PyTorch-based Python API that
interfaces to the C++ code. There are two levels of parallelization: inter-
machine parallelization which is implemented using the PyTorch distributed
framework and intra-machine parallelization using the multiprocessing module.

We use a naive parallel search where we instantiate one CA-SA worker per each
CPU core. For $M$ machines with $C$ cores each, we will have $M*C$ workers.
Each CA-SA worker runs independently. We collect the final $M*C$ solutions and
use these to construct Pareto optimal fronts with trade-offs between area and
wire-length.

Figure 4. PARSAC architecture.

##  4\. Results

###  4.1. Legacy floorplan problems

We first test PARSAC on classical floorplanning problems from the literature
with no pre-placement constraints. We compare against prior work based on
simulated annealing as well as against more recent RL-based techniques. These
previous methods assumed hard blocks, i.e, they did not allow adjustments to
the blocks’ aspect ratios. We present two sets of PARSAC results: PARSAC(soft)
which performs aspect ratio adjustments and PARSAC(hard) which does not. In
the PARSAC(soft) results we only allow a block’s aspect ratio to vary in the
range $[\frac{1}{3},3]$.

We test on the n100, n200, and n300 floorplans which have $100$, $200$, and
$300$ blocks, respectively. These are fixed outline floorplanning problems
where the goal is to minimize wire-length while placing all blocks within the
outline. The outline is square and is $10\%$ larger than the total block area.
We do not scale the terminal locations but keep all the terminals at their
problem-defined positions, which is the convention adopted by prior work. We
run $112$ PARSAC workers in parallel across $112$ CPU cores. Each worker runs
for $10$ million SA steps. We report results from the two workers with the
best and worst wire-lengths. All workers are able to place the blocks to fit
within the fixed outline. The results are shown in table 2. PARSAC(hard)
outperforms previous baselines and achieves significantly lower wire-length.
PARSAC(soft) achieves even lower wire-length, which shows that PARSAC can
effectively exploit the extra degrees of freedom afforded by soft blocks. We
also report PARSAC’s run-time. The experiments were run on a $2$-socket fifth
generation Xeon Scalable server processor (Emerald Rapids) with 56 cores per
socket.

Table 2. Wire-length (mm) for fixed outline floorplanning. For PARSAC, we report the worst and best results across $112$ workers. Design |  | PARSAC
---
run-time(mins)
PARSAC(soft) | PARSAC(hard) | Parquet (parquet) | B*-FOPP (btree06, 5) | SP-FOPP (antsa16, 29) | GoodFloorPlan (gfp22, 30)
n100 | 9.3 |  288-301 |  291-310 | 344 | 323 | 319 | 309
n200 | 31.2 |  526-553 |  530-557 | 654 | 599 | 575 | 558
n300 | 67.8 |  627-663 |  628-673 | 799 | 757 | 705 | 691

###  4.2. Floorplan problems with placement constraints

The popular floorplanning benchmarks in the literature do not have hard
preplacement constraints. To evaluate the effectiveness of PARSAC, we extend
the n100, n200, and n300 problems with hard pre-placement constraints as
follows:

  1. (1)

Randomly pick 4 groups of 7 blocks each. Assign to each group a left boundary,
right boundary, top boundary, or bottom boundary constraint.

  2. (2)

Randomly pick 4 blocks. Assign to each block a bottom-right, bottom-left, top-
right, or top-left boundary constraint.

  3. (3)

Randomly pick 3 groups of 3 blocks each. Assign a grouping constraint to all
blocks within the same group.

  4. (4)

Randomly pick 10 blocks and assign to them a hard pre-placement constraint at
random $x$-$y$ locations within the fixed outline.

The random block picks are non-overlapping. We compare CA-SA against classical
SA. For classical SA, we support the different constraints through extra terms
in the cost function as illustrated in Eq. 3. For each augmented benchmark, we
run $336$ trials for CA-SA and for classical SA. We vary the cost coefficients
across trials. Fig 5 plots the frequency of boundary constraints violations
for CA-SA and classical SA. We see that without the constraints-fixing move in
SA, the resulting floorplan almost always has some boundary constraints
violation. CA-SA, with its constraints-fixing moves, virtually guarantees no
boundary constraints violations.

(a)

(b)

(c)

Figure 5. Histogram of boundary constraints violations for CA-SA and classical
SA for the constrained n100, n200, and n300 problems. The statistics for each
problem were collected from 336 trials.

Figure 6 shows two floorplans for the randomly constrained n100 problems. Both
CA-SA and classical SA are generally able to satisfy the grouping constraints
solely by including the number of violated grouping constraints in the cost
function. The floorplan found by classical SA, however, has five boundary
constraints violations while the floorplan from CA-SA has no boundary
constraints violations.

(a)

(b)

Figure 6. (6(a)) Sample floorplan from classical SA for the constrained n100
problem. There are five blocks that violate their boundary constraints. The
violating blocks have a red outline. Blocks that are part of the same grouping
constraint have the same fill pattern (circle, star, or cross-hatch patterns).
(6(b)) Sample floorplan from CA-SA for the same problem as 6(a). All blocks
satisfy the boundary constraints.

The inability of classical SA to reliably satisfy the hard boundary
constraints makes it very difficult to generate a rich legal Pareto front.
That is because most of the discovered floorplans would be illegal. Figure 7
illustrates this issue: Across 336 trials, classical SA mostly generates
illegal solutions for the constrained n100, n200, and n300 problems. A
floorplan can be illegal due to boundary constraints violations, grouping
constraints violations, or fixed outline violations. The pre-dominant type of
violations for classical SA is boundary constraints violations. For the same
number of trials, however, PARSAC can generate mostly legal floorplans leading
to a richer legal Pareto front. The pre-dominant violation types in PARSAC are
grouping and fixed outline violations. PARSAC is an ideal choice for exploring
the Pareto-optimal trade-offs between design metrics (such as area and wire-
length) for constrained floorplanning problems due to its massively parallel
nature and because it mostly generates legal floorplans.

Figure 7. The distribution of $336$ solution points for the constrained n100,
n200, and n300 problems for classical SA and PARSAC. We quantify the solution
quality using the HPWL and the percentage of white-space in the block’s
bounding box (the minimal box that contains all the blocks). The top rows
shows the results for classical SA. Most of the floorplans are illegal. The
bottom row shows the results for PARSAC which finds legal floorplans most of
the time.

The straightforward approach to handle hard pre-placement constraints in
classical SA is to modify the SA’s cost function to penalize placing pre-
placed blocks away from their target locations. Let $B={b_{1},\ldots,b_{P}}$
be the set of blocks with hard pre-placement constraints. We require block
$b_{i}$ to be placed at position $(x_{i},y_{i})$. The extra term in the
classical SA’s cost function has the form:

(6)
$cost_{preplaced}=\theta\sum\limits_{i=1}^{P}|(b_{i}.x-x_{i})|+|(b_{i}.y-y_{i})|,$

where $\theta$ is the pre-placed cost coefficient and $(b_{i}.x,b_{i}.y)$ is
the location of block $b_{i}$ found by SA. We observe that this additional
cost term does indeed move blocks with pre-placement constraints close to the
required location. However, the placement is practically never exact. Table 3
shows the mean deviations along the $x$ and $y$ dimensions for the pre-placed
blocks away from their pre-placed locations. For PARSAC, the deviations are
zero by construction since PARSAC uses a B*-tree with anchored blocks to
guarantee that pre-placed constraints are satisfied.

Table 3. Mean placement deviations for pre-placed blocks with classical SA. Design | x | y
---|---|---
n100 | 2.79 | 0.80
n200 | 3.29 | 0.37
n300 | 3.31 | 0.44

##  5\. Conclusions

Modern industrial-level floorplanning involves many placement constraints that
govern the legal locations of many blocks. We have shown that popular
floorplanning methods based on SA, however, typically fail to yield legal
solutions in the presence of hard placement constraints. Our modified SA
pipeline, CA-SA, introduces two novel mechanisms: constraints-fixing moves and
B*-trees with anchored blocks. The former greatly increases the probability of
finding solutions that satisfy boundary constraints while the later guarantees
that pre-placement constraints are always satisfied. We introduced PARSAC,
which is a parallel SA framework built on top of CA-SA. PARSAC can scale to
many CPU cores and machines and can utilize the distributed compute resources
to quickly find a rich Pareto front of legal floorplans for complex
floorplanning problems.

Prior floorplanning work often failed to provide an accessible and properly
documented code-base. This makes it hard, and sometimes impossible, to
reproduce this prior work. We open-source the PARSAC library to allow others
to reproduce our results. There is currently no easy-to-use open-source
library for solving the floorplanning problem. PARSAC fills this gap, and
introduces novel and effective mechanisms that allow users to move beyond toy
floorplanning problems to problems with more realistic constraints reflective
of modern SoC designs.

## References

  * (1) S.N. Adya and I.L. Markov  “Fixed-outline floorplanning through better local search”  In _Proceedings 2001 IEEE International Conference on Computer Design: VLSI in Computers and Processors. ICCD 2001_ , 2001, pp. 328–334
  * (2) S.N. Adya and I.L. Markov  “Fixed-outline floorplanning: enabling hierarchical design”  In _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ 11.6, 2003, pp. 1120–1135
  * (3) Mohammad Amini et al.  “Generalizable Floorplanner through Corner Block List Representation and Hypergraph Embedding”  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , KDD ’22  Washington DC, USA: Association for Computing Machinery, 2022, pp. 2692–2702
  * (4) Hayward H. Chan, Saurabh N. Adya and Igor L. Markov  “Are floorplan representations important in digital design?”  In _Proceedings of the 2005 International Symposium on Physical Design_ , ISPD ’05  San Francisco, California, USA: Association for Computing Machinery, 2005, pp. 129–136
  * (5) Yun-Chih Chang, Yao-Wen Chang, Guang-Ming Wu and Shu-Wei Wu  “B*-trees: a new representation for non-slicing floorplans”  In _Proceedings 37th Design Automation Conference_ , 2000, pp. 458–463
  * (6) Chuan-Wen Chiang  “ANT COLONY OPTIMIZATION FOR VLSI FLOORPLANNING WITH CLUSTERING CONSTRAINTS”  In _Journal of the Chinese Institute of Industrial Engineers_ 26.6 Taylor & Francis, 2009, pp. 440–448
  * (7) Zhuolun He et al.  “Learn to Floorplan through Acquisition of Effective Local Search Heuristics”  In _2020 IEEE 38th International Conference on Computer Design (ICCD)_ , 2020, pp. 324–331
  * (8) Xianlong Hong et al.  “Corner block list: an effective and efficient topological representation of non-slicing floorplan”  In _IEEE/ACM International Conference on Computer Aided Design. ICCAD - 2000. IEEE/ACM Digest of Technical Papers (Cat. No.00CH37140)_ , 2000, pp. 8–12
  * (9) Chyi-Shiang Hoo, Kanesan Jeevan, Velappa Ganapathy and Harikrishnan Ramiah  “Variable-Order Ant System for VLSI multiobjective floorplanning”  In _Applied Soft Computing_ 13.7, 2013, pp. 3285–3297
  * (10) R. Jeyarohini, K.. Britto and M.. Ramkumar  “Optimization and Representation of Non-Slicing VLSI Floorplanning”  In _2023 4th International Conference on Smart Electronics and Communication (ICOSEC)_ , 2023, pp. 26–31
  * (11) Pengli Ji et al.  “A Quasi-Newton-based Floorplanner for fixed-outline floorplanning”  In _Computers & Operations Research_ 129, 2021, pp. 105225
  * (12) Andrew B. Kahng  “Classical floorplanning harmful?”  In _Proceedings of the 2000 International Symposium on Physical Design_ , ISPD ’00, 2000, pp. 207–213
  * (13) Jae-Gon Kim and Yeong-Dae Kim  “A linear programming-based algorithm for floorplanning in VLSI design”  In _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ 22.5, 2003, pp. 584–592
  * (14) Jianbang Lai, Ming-Shiun Lin, Ting-Chi Wang and L.-C. Wang  “Module placement with boundary constraints using the sequence-pair representation”  In _Proceedings of the ASP-DAC 2001. Asia and South Pacific Design Automation Conference 2001 (Cat. No.01EX455)_ , 2001, pp. 515–520
  * (15) Ximeng Li, Keyu Peng, Fuxing Huang and Wenxing Zhu  “PeF: Poisson’s Equation-Based Large-Scale Fixed-Outline Floorplanning”  In _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ 42.6, 2023, pp. 2002–2015
  * (16) Zhu Lichen et al.  “An Efficient Simulated Annealing Based VLSI Floorplanning Algorithm for Slicing Structure”  In _2012 International Conference on Computer Science and Service System_ , 2012, pp. 326–330
  * (17) Jai-Ming Lin and Yao-Wen Chang  “TCG-S: orthogonal coupling of P*-admissible representations for general floorplans”  In _Proceedings 2002 Design Automation Conference (IEEE Cat. No.02CH37324)_ , 2002, pp. 842–847
  * (18) Jai-Ming Lin and Yao-Wen Chang  “TCG: a transitive closure graph-based representation for non-slicing floorplans”  In _Proceedings of the 38th Design Automation Conference (IEEE Cat. No.01CH37232)_ , 2001, pp. 764–769
  * (19) Ke Liu, Jian Gu, Hao Gu and Ziran Zhu  “A Hybrid Reinforcement Learning and Genetic Algorithm for VLSI Floorplanning”  In _Proceedings of the 2023 15th International Conference on Machine Learning and Computing_ , ICMLC ’23  New York, NY, USA: Association for Computing Machinery, 2023, pp. 412–418
  * (20) Chaomin Luo, Miguel F. Anjos and Anthony Vannelli  “Large-scale fixed-outline floorplanning design using convex optimization techniques”  In _Proceedings of the 2008 Asia and South Pacific Design Automation Conference_ , ASP-DAC ’08  Seoul, Korea: IEEE Computer Society Press, 2008, pp. 198–203
  * (21) Yuchun Ma et al.  “VLSI floorplanning with boundary constraints based on corner block list”  In _Proceedings of the ASP-DAC 2001. Asia and South Pacific Design Automation Conference 2001 (Cat. No.01EX455)_ , 2001, pp. 509–514
  * (22) Hiroshi Murata and Ernest S. Kuh  “Sequence-pair based placement method for hard/soft/pre-placed modules”, ISPD ’98  Monterey, California, USA: Association for Computing Machinery, 1998, pp. 167–172
  * (23) Yingxin Pang, Chung-Kuan Cheng and Takeshi Yoshimura  “An enhanced perturbing algorithm for floorplan design using the O-tree representation”  In _Proceedings of the 2000 International Symposium on Physical Design_ , ISPD ’00  San Diego, California, USA: Association for Computing Machinery, 2000, pp. 168–173
  * (24) T. Singha, H.S. Dutta and M. De  “Optimization of Floor-Planning using Genetic Algorithm” 2nd International Conference on Computer, Communication, Control and Information Technology( C3IT-2012) on February 25 - 26, 2012  In _Procedia Technology_ 4, 2012, pp. 825–829
  * (25) Jian Sun et al.  “Floorplanning of VLSI by Mixed-Variable Optimization”, 2024  arXiv:2401.15317 [cs.NE]
  * (26) S. Sutanthavibul, E. Shragowitz and J.B. Rosen  “An analytical approach to floorplan design and optimization”  In _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ 10.6, 1991, pp. 761–769
  * (27) Christine L. Valenzuela and Pearl Y. Wang  “A Genetic Algorithm for VLSI Floorplanning”  In _Parallel Problem Solving from Nature PPSN VI_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2000, pp. 671–680
  * (28) D.F. Wong and C.L. Liu  “A New Algorithm for Floorplan Design”  In _23rd ACM/IEEE Design Automation Conference_ , 1986, pp. 101–107
  * (29) Qi Xu, Song Chen and Bin Li  “Combining the ant system algorithm and simulated annealing for 3D/2D fixed-outline floorplanning”  In _Appl. Soft Comput._ 40.C NLD: Elsevier Science Publishers B. V., 2016, pp. 150–160
  * (30) Qi Xu et al.  “GoodFloorplan: Graph Convolutional Network and Reinforcement Learning-Based Floorplanning”  In _Trans. Comp.-Aided Des. Integ. Cir. Sys._ 41.10 IEEE Press, 2022, pp. 3492–3502
  * (31) Jackey Z. Yan and Chris Chu  “DeFer: Deferred decision making enabled fixed-outline floorplanner”  In _2008 45th ACM/IEEE Design Automation Conference_ , 2008, pp. 161–166
  * (32) E.F.Y. Young, C.C.N. Chu and M.L. Ho  “Placement constraints in floorplan design”  In _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ 12.7, 2004, pp. 735–745
  * (33) F.Y. Young and D.F. Wong  “Slicing floorplans with boundary constraint”  In _Proceedings of the ASP-DAC ’99 Asia and South Pacific Design Automation Conference 1999 (Cat. No.99EX198)_ , 1999, pp. 17–20 vol.1
  * (34) F.Y. Young and D.F. Wong  “Slicing floorplans with pre-placed modules”  In _1998 IEEE/ACM International Conference on Computer-Aided Design. Digest of Technical Papers (IEEE Cat. No.98CB36287)_ , 1998, pp. 252–258
  * (35) Yong Zhan, Yan Feng and S.S. Sapatnekar  “A fixed-die floorplanning algorithm using an analytical approach”  In _Asia and South Pacific Conference on Design Automation, 2006._ , 2006, pp. 6 pp.-
  * (36) Hai Zhou and Jia Wang  “ACG-adjacent constraint graph for general floorplans”  In _IEEE International Conference on Computer Design: VLSI in Computers and Processors, 2004. ICCD 2004. Proceedings._ , 2004, pp. 572–575