Description
You are to write an implementation of the branch-and-bound partitioning algorithm described in class. It is to take
netlist of (equal-sized) blocks and divide it into two equal-sized partitions (bi-partitioning) with the goal to
minimize the number of nets that connect blocks in the two partitions. In addition, the input file will specify pairs of
blocks that form “communities”. It is desirable if such pairs of blocks are assigned to the same partition.
As in the previous assignments, your program should display its progress and results using the same graphics
package. Illustrate, as best you can, the state of the decision tree, and the pruning.
The netlist format is similar to that of Assignment #2. The first part of the file specifies the blocks (cells) and the
connectivity between them. Each line has the following form:
blocknum netnum1 netnum2 netnum3 … netnumn -1
Where blocknum is a positive integer giving the number 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. The list of nets is terminated by a –1. The first part of the
file is terminated by a -1 by itself on a line.
The second part of the file is a list of pairs of blocks, forming a “community list” in the following format:
blocknumi blocknumj
The second part of the file is likewise terminated by a -1 by itself on a line.
Example input file:
1 2 3 4 -1
2 5 4 -1
3 5 6 2 -1
4 6 3 -1
-1
1 3
-1
In this example, block 1 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. In the second part,
observe that it is desirable that blocks 1 and 3 be assigned to the same partition. Blocks 1 and 3 form a “community”
of blocks.
Test your program on the four test circuits provided on the course web page.
Your partitioner must use branch and bound techniques to find the partitioning having the optimal cost, where
cost = crossing count + community cost. Crossing count is the number of nets spanning between the two partitions.
This means that each net (even a multi-fanout net) contributes either 0 or 1 to the total crossing count, and never more
than this. A net contributes 1 to the crossing count if it connects cells that reside in two partitions. Community cost
is computed as follows: for each pair of blocks in the community list, cost is increased by 1 if the blocks are in
different partitions; otherwise, cost is 0 for that pair.
What to do and what to hand in?
Your partitioner must run on the ECF network. Instructions for electronic submission of your partitioner (including
source code) will be posted on the course’s Piazza page.
1. A report with short description of the flow of your program. You should describe:
• The branching structure (that is, how you designed your decision tree).
• How you determine the initial “best” solution.
• The bounding function(s) that you use and any that you experimented with.
2. Provide the following:
• A plot of the results from the test circuits.
• A count of the number of tree nodes that are visited. There will be a prize for the smallest number of nodes
traversed on cct4. NOTE: Tuning to the algorithm to the exact problem is not allowed. Regarding the
definition of “visited”, if you are calling your bounding function for a node, that should count as “visiting”
the node. Likewise, if a node is disqualified owing to balance constraints, the node should still count as
“visited”.
• The run-time for each of the test circuits.
• The value of the total cost, crossing count, and community cost that you achieved on each test circuit.
3. Summarize and discuss your results. How did the community block pairs affect your bounding function?
HINT for A3: Sorting the nodes based on fanout can have a significant impact on the branch-and-bound
solution space explored.
