## Description

You are to write an implementation of a basic analytical placer (AP), with overlap removal (spreading) and

fitting/snapping-to-grid. 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) to solve the linear system (see

announcement on Piazza page). Your placer will also handle heterogeneous block (cell) types, where there are

restrictions on where certain types of cells may be placed. Such heterogeneity arises in FPGA placement, where for

example, DSP and RAM blocks can only be placed in specific locations on the device.

Your program should display its progress and results using the same graphics package as used in Assignment #1

(available on course webpage). Your graphics should show the placement results and the connectivity between blocks

(rat’s nest of wires). Blocks (cells) should appear as points in your placement and be labeled with block numbers (see

below). There is an example executable from a prior year of ECE1387 on the Piazza site, if you’d like some

inspiration for how the placement may be displayed.

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 to be placed and the connectivity between them. Each line has

the following form:

blocknum type netnum1 netnum2 netnum3 … netnumn -1

Where blocknum is a positive integer giving the number of the cell, type is either 0 or 1 (the type of the block), and

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 1 5 4 -1

3 0 5 6 2 -1

4 0 6 3 -1

-1

1 50 0

4 0 50

-1

In this example, block 1 (of type 0) 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 = 50, y = 0. The list of fixed objects is terminated

by a –1 by itself on a line.

You should run your placer on the Assignment #2 test circuits provided on the course web page.

Each test circuit is to be placed on an NxN grid of slots (each slot is 1 area-unit wide and 1 area-unit tall),

where N = ceiling(sqrt(m)), and where m is the # of blocks. m = #fixed_blocks + #moveable_blocks. The idea

is that each cell/block is to eventually be fit into one such slot.

What to do and what to hand in?

Your placer must run on the ECF network. Instructions for electronic submission of your placer (including source

code) will be posted on the course’s Piazza page close to the assignment deadline.

Your report should include a short description of the flow of your program, the main routines and what they do,

assuming that I have basic knowledge of analytical placement.

1. 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 the graphics package. Hand in a plot of the placement results. Your program should also

compute the half-perimeter bounding box (BB) wirelength (WL) of the placement. Hand in a table

showing the half-perimeter BB WL for each placed test circuit.

2. For circuits 2-4 only: Implement a simple form of overlap removal. Given that the placement area

spans from (0,0) to (N,N), use the results of Step 1 to divide the non-fixed blocks into four groups of

roughly equal size. Each group will consist of the blocks closest to each quadrant of the placement area.

That is, one group will represent the ~n/4 blocks closest to the lower-left corner of the placement; a

second group will represent the ~n/4 blocks closest to the top-left corner of the placement, and so on.

Having divided the blocks, reformulate the placement problem as in Step 1, but with a modification: In

your reformulation, introduce 4 new (artificial) fixed blocks, placed at the four centres of the die

quadrants (i.e., one at (N/4, N/4), one at (N/4, 3N/4), etc.). Introduce (artificial) two-pin nets from each

new fixed block to each block in the group corresponding to the fixed block’s quadrant. Solve the

formulation, compute its BB wirelength, and display and plot the results. Describe how you partitioned

the blocks. Hand in a table showing the BB WLs. Do not include the WL of the artificial connections in

your WL numbers. What happens to WL when the new fixed blocks are introduced? Experiment with

changing (increasing/decreasing) the weights of the artificial two-pin nets; comment on the WL results

when different weights are used.

3. For circuits 2-4 only: Repeat step #2 recursively to perform further spreading by continuing to modify

the mathematical formulation. For example, take the group of blocks you assigned to the lower-left

quadrant in Step #2, and divide this group into four sub-groups, each corresponding to a sub-quadrant of

the lower-left quadrant. Introduce fixed blocks at the centers of the four sub-quadrants. Introduce

(artificial) two-pin nets from each new fixed block to each block in the corresponding sub-group. Do

the same for the other quadrants of the die. Solve the new placement formulation. Repeat the process

recursively, with successively smaller regions. I suggest you continue spreading until no more than 15%

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.

of 1×1 slots are overfilled. Provide a plot of the spread placement. In a table, report the BB WL when

your stopping criterion is met.

4. For circuits 2-4 only: “Snap”/legalize the placement produced by step #3 into the grid, where cells are

points placed at the centre of the 1×1 grid slots, and there is at most one cell placed in each such grid

slot.

You are to do this in two ways: 1) where any type of block can be placed anywhere, and 2) where type 1

blocks can only be placed in every fifth column (beginning from the second column from the left), as

illustrated in the 12×12 (N=12) example figure below.

For both fitting approaches, provide a plot of the “snapped” placement for each circuit. Likewise, for

both fitting approaches, report the BB WL after snapping and compare with the results for step #3. How

much did BB WL increase after snapping? How much is the BB WL affected by the placement

restrictions for type 1? Time permitting, you may consider innovative ideas to adjust your spreading in

steps 2 and 3 above to be “aware” of the block types and their potential placement locations. In class, I

will report on the results achieved by everybody and mention the best WL achieved.

OPTIONAL: Instead of applying step #3 recursively as above, you may use ANY spreading strategy you wish,

including SimPL, as described in class. If you decide to go this route, briefly describe your solution and

optimizations. Note that it is not my expectation (or a requirement for full marks) that everyone opt for this

route and implement SimPL or some other more advanced algorithm.