Description
You are to write an implementation of a basic analytical placer (AP), with overlap removal (spreading). As described
in class, you will formulate the placement problem mathematically as a system of linear equations to be solved. You
will use an existing package (UMFPACK within SuiteSparse) to solve the linear system (see Piazza page). For
spreading, you will implement the flow-based approach, as described in class, and in the Darav et al. paper, “MultiCommodity Flow-Based Spreading in a Commercial Analytic Placer,” ACM FPGA 2019.
Your program should display its progress and results using the same graphics package as used in Assignment #1.
Your graphics should show the placement results and the connectivity between blocks (rat’s nest of wires). Blocks
(cells) should appear as squares in your placement and be labeled with block numbers (see below).
The netlist file input format has two sections. The two sections are separated from one another by a -1 appearing by
itself on a line. The first section specifies the blocks (cells) to be placed and the connectivity between them. Each
line has the following form:
blocknum blocktype netnum1 netnum2 netnum3 … netnumn -1
where blocknum is a positive integer giving the number of the cell, and blocktype is either 0 or 1. You will implement
two styles of AP: In the first style (homogeneous), cells of either type can be placed anywhere on the chip. In the
second style (heterogeneous), types 0 and 1 have restricted placement locations. Type 0 cells can be placed in any
placement column i, where i mod 4 = 0,1,2. Type 1 cells can be placed in any placement column i, where i mod 4 = 3.
The netnumi are the numbers of the nets that are attached to that block. Every block that has the same netnumi on its
description line is attached. Note that each block may have a different number of nets attached to it. Each line is
terminated by a -1.
Example input file:
1 0 2 3 4 -1
2 0 5 4 -1
3 0 5 6 2 -1
4 1 6 3 -1
-1
1 40 0
4 0 40
-1
In this example, block 1 is type 0 and is connected to nets 2, 3 and 4. Note that each net may be connected to more
than two blocks (that is, there are multi-fanout nets). Also, note that net numbers are not related to block numbers.
As discussed in class, the AP formulation requires there to be a set of pre-placed (fixed) objects, normally I/Os. The
second section of the netlist file specifies the placement of fixed objects. It has the following form:
blocknum x_position y_position
In the above example, block 1 is pre-placed at the position with x = 40, y = 0. The list of fixed objects is terminated
by a -1 by itself on a line. There may be multiple fixed objects placed at the same position (assume that is OK).
You should run your placer on the Assignment #2 test circuits provided on the course web page.
What to do and what to hand in?
Your placer must run on the ECF network. Instructions for electronic submission of your placer will be posted.
Your report should include a short description of the flow of your program, the main routines and what they do,
assuming that we have basic knowledge of analytical placement.
1. Do for all circuits: Formulate and solve the analytical placement problem assuming the clique net
model1
. Do not do any overlap removal in this step. Your program should display the placement and
rat’s nest (wires between cells) using graphics. Hand in a plot of the placement results. Your program
should also compute the half-perimeter bounding box wirelength (HPWL) of the placement. For
computing HPWL, assume that nets connect to the centre of each cell. Likewise, assume that the x,y
position of each cell corresponds to the cell’s centre. Use different colours in your graphics for the two
different cell types. In your report, include a table showing the HPWL for each placed test circuit.
2. Do for circuits 2 and 3 only for both the homogeneous and heterogeneous styles of AP: Assuming
that all bins are unit size (1´1), implement the flow-based spreading algorithm as described in class, and
in Darav’s 2019 paper. Assume that cell movements are quantized to multiples of 1 unit (meaning,
when a cell is moved between two bins, its relative position in the original bin is the same as its relative
position in the new bin). The placement area for all circuits is from 0,0 to 40,40 and as such, there are
40´40 = 1600 bins.
i) Experiment with different approaches for initializing and increasing the maximum-allowable cell
movement parameter, y, in the outer loop of the spreading algorithm. In your report, comment on the
approaches investigated and their impact on the total cell displacement between the solved and spread
placements for both styles of AP. By total cell displacement, I mean the sum of the displacements across
all cells between their original solved placement and their spread placement, see equation below. Report
the total cell displacement for the approaches attempted. Report HPWL for the spread placement for
both circuits, for both AP styles. In your report, explain how you handled the placement restrictions
arising from the two different cell types.
𝑇𝑜𝑡𝑎𝑙𝐶𝑒𝑙𝑙𝐷𝑖𝑠𝑝𝑙𝑎𝑐𝑒𝑚𝑒𝑛𝑡 = 1 2𝑥!,#$%&'( − 𝑥!,#)*’+(2 + |𝑦!,#$%&'( − 𝑦!,#)*’+(|
!∈-$&’+.%’/’%%#
ii) Introduce artificial fixed blocks (anchors), at each cell’s re-placed (spread) position for the spreading
approach you investigated in i) that provided the best (smallest) total cell displacement. Introduce an
artificial two-pin net from the anchor to the corresponding cell. Experiment with two different weight
choices for the artificial nets: weak and strong. The strong weight choice, for example, should be large
enough to cause a cell to be pulled sharply towards its anchor when the system is re-solved. Solve the
formulation corresponding to each of the two weight choices. Compute and report the half-perimeter
bounding-box wirelength (HPWL) of the placements, and display and plot the results (there should be 8
plots as there are 2 AP styles). Include the plots in your report. Remember that you should not include
the artificial nets in your HPWL calculation! Comment on what happens to HPWL when the new fixed
blocks are introduced and the impact of the two different weight strengths.
1 In the clique model, a net with p pins is represented as a complete graph (clique) with p*(p-1)/2 edges.
Each edge in the complete graph has weight of 2/p. For example, a net with 2 pins has 1 edge with edge
weight = 1. A net with 4 pins has 6 edges with edge weight = 2/4.
