• Firstly, the packing of the blocks must be held within a given layout region.
• Secondly, the blocks must be placed in a manner such that the routing of nets between the blocks can be completed.
• Thirdly, for high performance circuits the blocks are to be placed such that all critical nets can be routed within their timing budgets.

• Soft blocks
  In the early stage of physical design, many of the circuit blocks are not yet designed and are thus flexible (soft) in shape. For these soft blocks, the block packing algorithm not only needs to determine their locations, but also needs to assign specific shapes to them.
• Rectilinear blocks
  As some of the circuit blocks come from design re-use, their shapes are not necessarily rectangle. Therefore, the block packing algorithm should be able to handle the arbitrarily shaped rectilinear blocks.
• Pre-placed blocks
  In some cases, the locations of some blocks may be fixed, or a region may be specified for their placement. For example, in high performance chips, the clock buffer may have to be located in the center of the chip to reduce the time difference between the clock signal arrival time at different blocks. The block packing algorithm should put these pre-placed blocks on their specified location or region without overlapping with other blocks.

II.1. The .blocks format

The .blocks file specifies the name and other optional information about each block/terminal node in the floorplan. Each line specifies a single block/terminal node. After the standard header, the format specifies:

NumSoftRectangularBlocks : number of soft rectangular block nodes
NumHardRectilinearBlocks : number of hard rectilinear block nodes
NumTerminals : number of terminal (pad etc.) nodes

Then, one line for each soft rectangular block node with format as follows:

nodeName softrectangular area minAspectRatio maxAspectRatio [ : symmetry (default none)]

Then, one line (or more if the vertex-list is too long) for each hard rectilinear block node with format as follows:

nodeName hardrectilinear vertexNumber vertex1, vertex2, ..., vertexN [ : symmetry (default none)]

(Note: this format can distribute over arbitrary number of lines, as long as ``nodeName hardrectilinear vertexNumber'' stay on the first line and each individual vertex stays on a same line)

Then, one line for each terminal node with format as follows (if NumTerminals is greater than 0):

nodeName [ nodeDimensions (default (0,0)] [ : symmetry (default none)] terminal

nodeName

is an arbitrary-length alpha-numeric string, which may include any number of characters from: {(a-z), (A-Z), (0-9), '_', '/', '\', '+' and '-'} node names are case-sensitive.

``softrectangular''

is a literal which declares that the node is a soft rectangular block.

area, minAspectRatio and maxAspectRatio

are all doubles which specify the area, minAspectRatio, or max aspect ratio of the soft rectangular block, respectively.

``hardrectilinear''

is a literal which declares that the node is a hard rectilinear block.

vertexNumber

is the number of vertices of the hard rectilinear block.

vertex1, vertex2, ..., vertexN

is a list of all vertices of the hard rectilinear block in a clockwise order, vertex1 != vertexN. Each vertex is a pair of parentheses enclosed and comma separated doubles indicating the X-, then Y- coordinate of the vertex, relative to the left-bottom corner of the hard rectilinear block's bounding box.

nodeDimensions

is a pair of parentheses enclosed and comma separated doubles indicating width, then height when in N orientation.

symmetry

specifies the axes about wihch the node may be flipped. Symmetry is given as any combination (in any order) of 'X', 'Y' and 'R90'. R90 means the node may be rotated 90 degrees. If no symmetry is present, the node is assumed to be not flippable.

``terminal''

is a literal which indicates that the node is a terminal.

II.2. The .spatialconstr format

The .spatialconstr file specifies relative and absolute spatial constraints for placed objects. After the standard header, the format specifies:

First, the global layout constraints: layout region and snapping constraint

layoutRegion vertex1, vertex2, ..., vertexN

every placed object must lie entirely within the rectilinear region defined by (in consecutive order) vertex1, vertex2, ..., vertexN (vertex1 != vertexN); each vertex is specified by a pair of doubles separated by a comma and enclosed by parentheses, e.g., (50.0 , 40.4)

snappingConstraint { y1, y2, ..., yN } | startAt, step, num

y1, ..., yN is an explicit list of allowed y-coordinates at which all horizontal object edges must be located. startAt, step, num give a shorthand notation for defining the minimum allowed y-coordinate (startAt), the interval between allowed y-coordinates (step), and the total number of distinct allowed y-coordinates (num).

Next, the fixed/onedim/region/grouping location constraints:

FixedConstraints
nodeName1 location orientation
nodeName2 location orientation
...
nodeNameN location orientation
EndFixedConstraints

location is the location of the origin of the placed object. it is a pair of parenthesis enclosed and white-space separated doubles indicating the X-, Y- coordinate of the block vertex. for a rectangular block, the origin is its left-bottom vertex; for a non-rectanglular block, the origin is its first vertex in its vertexList

OneDimConstraints
nodeName1 dim coordinate
nodeName2 dim coordinate
...
nodeNameN dim coordinate
EndOneDimConstraints

dim is either H or V, coordinate is the y-coord or x-coord, respectively, at which the origin of the object must be placed.

RegionConstraints
nodeName1 vertex1, vertex2, ..., vertexN1
nodeName2 vertex1, vertex2, ..., vertexN2
...
nodeNameN vertex1, vertex2, ..., vertexN3
EndRegionConstraints

placed object must lie entirely within the rectilinear region defined by (in consecutive order) vertex1, vertex2, ..., vertexN (vertex1 != vertexN); each vertex is specified by a pair of doubles separated by a comma and enclosed by parentheses, e.g., (50.0 , 40.4)

GroupingConstraints
GrConstraint1
xspan,yspan
nodeName1, nodeName2, ..., nodeNameN
GrConstraint2
xspan,yspan
nodeName1, nodeName2, ..., nodeNameN
...
GrConstraintM
xspan,yspan
nodeName1, nodeName2, ..., nodeNameN
EndGroupingConstraints

each grouping constraint GrConstraint specifies that the entire list of objects must be placed within some bounding box of width xspan and height yspan within the layout region.

Next, alignment/adjacency/pitchmatch constraints:

AlignmentConstraints
nodeName11 nodeName12 dim 00 | 01 | 10 | 11
nodeName21 nodeName22 dim 00 | 01 | 10 | 11
...
nodeNameN1 nodeNameN2 dim 00 | 01 | 10 | 11
EndAlignmentConstraints

If dim = H, then the two placed objects must have horizontal edges of their bounding boxes aligned at the same y-coordinate:
case 00: both top edges;
case 01: top edge of object1 aligned with bottom edge of object2;
case 10: bottom edge of object1 aligned with top edge of object2;
case 11: both bottom edges;
If dim = V, then the two placed objects must have vertical edges of their bounding boxes aligned at the same x-coordinate:
case 00: both left edges;
case 01: left edge of object1 aligned with right edge of object2;
case 10: right edge of object1 aligned with left edge of object2;
case 11: both right edges;

AdjacencyConstraints
nodeName11 nodeName22 dim minOverlap
nodeName21 nodeName22 dim minOverlap
...
nodeNameN1 nodeNameN2 dim minOverlap
EndAdjacencyConstraints

If dim = H, then the boundaries of the bounding boxes of the two placed objects must intersect in a horizontal segment of length at least minOverlap;
If dim = V, then the boundaries of the bounding boxes of the two placed objects must intersect in a vertical segment of length at least minOverlap.

PitchmatchConstraints
nodeName11 nodeName22 dim
nodeName21 nodeName22 dim
...
nodeNameN1 nodeNameN2 dim
EndPitchmatchConstraints

If dim = H, then the horizontal boundaries of the bounding boxes of the two placed objects must be of equal length;
If dim = V, then the vertical boundaries of the bounding boxes of the two placed objects must be of equal length.

IN the above, ``layoutRegion'', ``snappingConstraint'', ``FixedConstraints'', ``EndFixedConstraints'', ``OneDimConstraints'', ``EndOneDimConstraints'', ``RegionConstraints'', ``EndRegionConstraints'', ``GroupingConstraints'', ``GrConstraintM'', ``EndGroupingConstraints'', ``AlignmentConstraints'', ``EndAlignmentConstraints'', ``AdjacencyConstraints'', ``EndAdjacencyConstraints'', ``PitchmatchConstraints'', ``EndPitchmatchConstraints'' are all literals, each indicating the beginning / end of a spatial constraint.

Executable (Solaris) (Win95/98/NT)

This floorplanner reads and writes the new blocks/pl/nets format. For user's conveniency, all MCNC benchmarks and GSRC (level VI) benchmarks in this format are included in the package.

This floorplanner is based on simulated annealing. The data representation is Sequence Pair. It can pack both soft blocks and rectilinear blocks.

To run this floorplanner, either Java 2 Platform (v 1.2 or v 1.3) or JDK 1.1 + JFC/Swing Release is required. The running instruction is included in a README file in the floorplanner package.

In the floorplanner package given above, integer precision is used in calculating block positions/dimensions (and round-off is applied in shape optimization). If the user wants to be more precise at the price of slower speed, a double precision version is also provided below:
(Solaris) (Win95/98/NT)

Note: We updated the floorplanner on this page recently (Mid-June-01). The only difference between the old one and the new one is the wirelength calculation model. The old one used a simple steiner-tree model. The new one uses the half-perimeter of net bounding-box model, which is widely used for many floorplanning publications.

Benchmark Results

Source Code

The first part of source code is the interface part, which includes the GUI and the reader / writer of input / output files. It is written in Java, so it works the same on any platform.

The second part of source code is the core engine part, which implements the four block-packing-related methods declared in the interface part. It is written in C++, working on Unix operating system.

Here again, We give two sets for each part, one for integer precision and the other for double precision.