__Introduction__

__Introduction__

There are two main data models that can be used for representing ﬂoorplans: graph-based and placement based.

The graph-based approach includes constraint graphs, corner stitching, twin binary tree, and O-tree. They utilize constraint graphs or their simpliﬁed versions directly for the encoding. Constraint graphs are basic representations. The corner stitching simpliﬁes the constraint graph by recording only the four neighboring blocks to each block. The twin binary tree then reduces the recorded information to only two neighbors of each block, and organizes the neighborhood relations in a pair of binary trees. The O-tree is a further simpliﬁcation to the twin binary tree. It keeps only one tree for encoding.

The placement-based representations use the relative positions between blocks in a placement for encoding. This category includes sequence pair, bounded-sliceline grid, corner block list and slicing trees. The sequence pair and bounded-sliceline grid can be applied to general ﬂoorplan. The corner block list records only the relative position of adjacent blocks, and is available to mosaic ﬂoorplan only. The slicing trees are for slicing ﬂoorplan, which is a type of mosaic ﬂoorplan. The slicing ﬂoorplan can be constructed by hierarchical horizontal or vertical merges and thus can be captured by a binary tree structure known as the slicing tree.

The rest of this chapter is organized as follows. In Section 53.1, we give the introduction and the problem statement of ﬂoorplanning. In Section 53.2, we discuss the graph-based representations. In Section 53.3, we introduce the placement-based representations. We describe the relationship between diﬀerent representations in Section 53.4. We illustrate the shape handling of rectilinear blocks in Section 53.5 and summarize the chapter in Section 53.6.

**Statement of Floorplanning Problem**

Today’s complexity in circuitry design wants a hierarchical approach [26]. The entire circuit is partitioned into several sub-circuits, and the sub-circuits are further partitioned into smaller sub-circuits, until they are small enough to be handled. The relationship between the sub-circuits can be represented with a tree as shown in Fig. 53.1. Here every sub- circuit is called a block, and hence the entire circuit is called the top block. From the layout point of view, every block corresponds to a rectangle, which contains sub-blocks or directly standard cells. Among the decisions to be made is the determination of shape (aspect ratio) and the pin positions on the blocks. In the top-down hierarchical methodology, blocks are designed from the top block (the entire circuit) to the leaf blocks (small modules). The minimizations of chip area and wire length are the basic targets for any layout algorithm. In addition, there are case-dependent constraints that will inﬂuence the layouts, such as the performance, the upper or/and lower boundaries of aspect ratio, the directions of pins, etc.

Now we give the deﬁnition of ﬂoorplanning problem: Inputs:

1. the net-lists of the sub-circuits;

2. the area estimation of blocks and, if any, the aspect ratio constraints on the blocks;

3. the target area and shape of the entire chip.

**Outputs:**

1. the shapes and positions of blocks;

2. the pin positions on the blocks.

The objective functions involve: the chip area, the total wire length and, if any, the performances.

**Motivation of the Representation**

*Fl**o**o**rpla**n representation *becomes an important issue in ﬂoorplanning for the following reasons.

(1) The blocks may have arbitrary shapes and locations, while the size of memory used to represent a two-dimensional ﬂoorplan should be *O*(*n*).

(2) For the general ﬂoorplanning problem, iterative improvement is the commonly used approach. The search for the best solution has proven to be NP-complete, so many heuristic optimizing algorithms, such as dynamic programming, simulated annealing, zone reﬁne- ment, cluster reﬁnement, have been adopted. The representation should also facilitate the operations called by those optimizing algorithms.

(3) The storage resources requirement, the redundancy of the representation and the complexity of translating the representation into ﬂoorplan are always the concerns in ﬂoor- planning. Here redundancy refers to the situation that several diﬀerent expressions actually correspond to the same physical layout. Essentially, a heuristic algorithm searches part of the solution space to ﬁnd the local optimal solution, which is hopefully very close to the global optimal solution. Redundancy causes the optimizing algorithm evaluate the same ﬂoorplan repeatedly.

**Combinations and Complexities of the Various Representations**

The number of possible ﬂoorplan representations describes how large the searching space is. It also discloses the redundancy of the representation. For general ﬂoorplans with *n** *blocks, the combinations of the various representations are listed in Table 53.1. Note that the twin binary tree representation has a one to one relation with the mosaic ﬂoorplan, and the slicing tree has a one to one relation with the slicing ﬂoorplan [15]. In other words, for these two representations, the number of combinations is equal to the number of possible ﬂoorplan conﬁgurations and there is no redundancy.

The combination numbers of sequence pairs, mosaic ﬂoorplans, slicing ﬂoorplans, and O-trees are illustrated on a log scale in Fig. 53.2. The combination numbers are normalized by *n*!, which is the number of permutations of *n *blocks. The slopes of the lines for mosaic ﬂoorplans, slicing ﬂoorplans, and O-tree structures are the constants 0.89, 0.76, and 0.59, respectively. On the other hand, the slope of the line for sequence pair increases with a rate of *l**o**g n*.

Table 53.2 provides the exact numbers of the combinations for the ﬂoorplans or representations with the block number ranging from 1 to 17.

The time complexities of the operations transforming a representation to a ﬂoorplan are

very important, because they determine the eﬃciency of the ﬂoorplan optimizations. The complexities of the representations covered in this chapter are compared in Table 53.3, where *n *is the number of blocks in a ﬂoorplan.

For sequence-pair, the time complexity to derive a ﬂoorplan is *O(nloglogn) *due to a fast algorithm proposed in [8]. We will discuss more on this in Section 53.3.1 For bounded slicing grid, there is a trade oﬀ between the solution space and the time complexity of deriving a ﬂoorplan. To ensure that the solution space covers all the optimal solutions, we need the grid size to be at lease *n *by *n*. This results in an *O*(*n*2) time complexity in deriving a ﬂoorplan [6]. For the rest of the representations, there are algorithms with *O*(*n*) time complexity to convert them into constraint graphs. The time complexity to derive a ﬂoorplan is thus *O*(*n*).

**Slicing, Mosaic, LB Compact, and General Floorplans**

A layout can be classiﬁed as a slicing ﬂoorplan if we can partition the chip with recursive horizontal or vertical cut lines (Fig. 53.3(a)). In a mosaic ﬂoorplan, the chip is partitioned by horizontal and vertical segments into rectangular regions and each region corresponds to exactly one block (Fig. 53.3(b)). For a general ﬂoorplan, we may ﬁnd empty space outside rectangular block regions (Fig. 53.3(c)). An LB-compact ﬂoorplan is a restricted general ﬂoorplan in that all blocks are shifted to their left and bottom limits. In summary, the set of general ﬂoorplans covers the set of LB-compact ﬂoorplans, which covers the set of mosaic ﬂoorplans, and which covers the set of slicing ﬂoorplans (Fig. 53.4).

For slicing and mosaic ﬂoorplans, the vertical segments deﬁne the left-right relation among the separated regions, and the horizontal segments deﬁne the above-below relation. Suppose that we shift the segments to change the sizes of the regions, we view the new ﬂoorplan to be equivalent to the original ﬂoorplan in terms of their topologies[4][23][24]. Therefore, we can devise representations to deﬁne the topologies of slicing and mosaic ﬂoorplans independent of the sizes of the blocks (Fig. 53.3(a) and (b)). In contrast, for a general ﬂoorplan, it is rather diﬃcult to draw a meaningful layout (Fig. 53.3(c)) without the knowledge of the block dimensions. One approach is to extend the mosaic ﬂoorplans to general ﬂoorplans by adding empty blocks [16]. It is shown that to convert a mosaic ﬂoorplan with *n *blocks into a general ﬂoorplan, the upper bound on the number of empty blocks inserted is *n **− *2*√**n *+1. [16]

In a mosaic ﬂoorplan, two adjacent blocks meet at a T-junction by sharing the non- crossing edge of the junction. There are four directions of T-junctions as is illustrated in Fig. 53.5. In the case of Fig. 53.5(a) and (b), block B is termed the C-neighbor at the lower left corner of block A. In Fig. 53.5(c) and (d), block B is the C-neighbor at the upper right corner of block A. The C-neighbor is used to construct twin binary tree representation.

The degeneration of a mosaic ﬂoorplan refers to the phenomenon that two T-junctions meet together to make up a cross-junction, as illustrated in Fig. 53.6(a). Some representations forbid the occurrence of degeneration. One scheme to solve the problem is to break one of the intersecting lines and assume a slight shift between the two segments, as shown in Fig. 53.6(b). Thus the degeneration disappears.

We generate an LB compact ﬂoorplan by compacting all blocks toward left and bottom. For a placement, suppose no block can be moved left, the placement is called L-compact. Similarly, if no block can be moved down, the placement is called B-compact. A ﬂoorplan is LB-compact if it is both L-compact and B-compact (Fig. 53.7).

##### Graph Based Representations

Graph based representations include constraint graphs, corner stitching, twin binary trees, and O-tree. They all utilize the constraint graphs or their simpliﬁed version for ﬂoorplan encoding.

Constraint graphs are directed acyclic graphs representing the adjacency relations between the blocks in a ﬂoorplan. In this subsection, we ﬁrst deﬁne the constraint graphs for general ﬂoorplans. We then show that for mosaic ﬂoorplan, the constraint graphs have nice properties of triangulation and duality.

**Th****e generation of constraint graphs**

Constraint graphs reﬂect the relative positions between blocks [12]. Constraint graphs can be applied to general ﬂoorplans, as is shown in Fig.53.8. A node in the constraint graph represents a block. A directed edge denotes the location relationship between two blocks. For example, A*→*B means block A is to the left of B in a horizontal constraint graph (Fig. 53.8(b)). A*→*E means block A is on top of E in a vertical constraint graph (Fig. 53.8(c)).

Here we imply that if A*→*B and B*→*C, then A*→*C. Thus even though block *A *stands to the left of *C*, the edge between *A *and *C *is not necessarily shown. To mark the four sides of the chip, we add the nodes labeled with “left”, “right”, “top” and “down”. A pair of horizontal and vertical constraints graphs can represent a ﬂoorplan. Every constraint graph, whether it is a horizontal one or a vertical one, is plan r and acyclic. Fig. 53.9 shows an example of the constraint graphs to a mosaic ﬂoorplan. Fig 53.9(a) is the mosaic ﬂoorplan. Fig 53.9(b) and (c) are the corresponding horizontal and vertical constraint graphs, respectively.

**T****r****iangulation**

For a mosaic ﬂoorplan without degeneration, if its horizontal and vertical constraint graphs are merged together, then we have the following conclusions [12]:

1. Every face is a triangle.

2. All internal nodes have a degree of at least 4.

3. All cycles, if not faces, have the length of at least 4.

Shown in Fig. 53.10(a) is the result of merging the pair of constraint graphs in Fig. 53.9. In fact, the merged constraint graph is a dual graph of its original ﬂoorplan (Fig. 53.9(b)).

**T****utt****e’s duality[27]**

We can also build an edge-based constraint graph for a mosaic ﬂoorplan, where the nodes denote the lines separating the blocks while the edges denote the blocks. Labeling the lines with numbers (Fig. 53.11(a)), we build a vertical constraint graph (Fig. 53.11 (b))

and a horizontal constraint graph (Fig. 53.11(c)). Fig. 53.11(d) demonstrates the result of merging the vertical and horizontal constraint graphs. Here, to make the merged graph clear, the edges representing horizontal constraints are drawn with dotted lines, and a letter at the intersection of a solid edge and a dotted edge denotes the two edges simultaneously. It is very interesting that, for mosaic ﬂoorplans, the vertical and horizontal constraint graphs are dual, as is called Tutte’s duality.

Let’s see how Tutte’s duality is used to solve the sizing problem in ﬂoorplanning. We map the constraint graphs into circuit diagrams by replacing the edges in the vertical constraint graph with resistors, as illustrated in Fig. 53.12.

The circuit is subject to Kirchoﬀ voltage law. As a result, taking Fig. 53.12 as an

By comparing the above two equation arrays, we can ﬁnd that there is a perfect correspondence between the solutions of the circuit and the ﬂoorplan. Let us set the following assumptions: (only two of the three equations are independent)

Thus the theories dealing with large circuits can be borrowed to solve the sizing problem in ﬂoorplanning.

Constraint graphs have the advantages of being able to cope with any types of ﬂoorplans. However, it would be rather diﬃcult to shift to a new ﬂoorplan with just a few simple operations on the graph. The eﬃciency is greatly discounted for the iteratively improving algorithms. Thus in [25], a transitive closure graph (TCG) was proposed to simplify the rules of the operations. The relation of each pair of blocks is prescribed in either horizontal or vertical constraint graph via transitive closure, but not in both graphs.

**Corner Stitching**

Corner stitching is used to represent the topology of a mosaic ﬂoorplan. Simpliﬁed from constraint graphs, corner stitching [17] keeps only four pointers at the two opposite corners for every block. All the operations on a constraint graph can also be fulﬁlled on a corner stitching representation with acceptable increases in time complexity, while the storage for corner stitching becomes easier since the number of pointers attached to every block is ﬁxed (equals to 4). Readers are referred to Chapter 52 for detailed descriptions and analyses of corner stitching.

**Twin Binary Tree**

Twin binary tree [15] representation applies to mosaic ﬂoorplans without degeneration. The twin binary tree is constructed as follows, every block takes its C-neighbor (Fig. 53.5) as its parent. In the ﬁrst tree, only the C-neighbors in lower left corners (Fig. 53.5 (a) and (b)) are taken into account. If the related T-junction is of type (a), then the block is a left child of its parent, and if the T-junction is of type (b), then the block is a right child. The most bottom-left block in the ﬂoorplan acts as the root of the tree. Similarly, in the second tree, the C-neighbors in upper right corners (Fig. 53.12(c) and (d)) are used, and the most upper-right block becomes the tree’s root.

tree.Fig.53.13 gives an example of a twin binary The pointers of twin binary trees are in fact a subset of those in corner stitching. Besides, It has been proved that twin binary tree is a non-redundant representation. In other words, every pair of trees corresponds to a unique mosaic ﬂoorplan.

The twin properties of binary trees can be illustrated with Fig. 53.14. Consider the trees shown in Fig. 53.13, we add a left child labeled ‘0’ to every node without left child except the most left node, and a right child labeled ‘1’ to every node without right child except the most right node. The resultant trees are the so-called extended trees (Fig. 53.14). The sequences of the in-order traverse of the two extended trees shown in Fig. 53.14 are “A0B1C1F0D1E” and “A1B0C0F1D0E” respectively. If we separate them into the label parts and the bit parts, we have *π*1*=ABCFDE*, *α*1*=01101 **π*2*= ABCFDE *and *α*2 = 10010. It is interesting to ﬁnd that *π*1*=**π*2 and *α*1 = *α*2. So rather than store the two binary trees, we only keep the linear lists*π *and*α*in memory.

However, it is insuﬃcient to recover the two binary trees just from *π *and *α*, so we need two more lists, *β *and *β**I **. *If the *i**–**th *element in*π *is the left child of its parent in the ﬁrst tree or the root of the tree, we set the *i**–**th *element in *β *to be ‘0’, otherwise we set it ‘1’. In the

similar way *β**I *is constructed according to the second tree. Thus we use a group of linear lists *{**π**,**α**, **β*,*β**I **}*, called the twin binary sequence [16], to express the twin binary tree, and equivalently the ﬂoorplan.

Finally, we give the main properties of twin binary tree representation:

1.The memory required for storing the twin binary sequence is

log2n+3n-1, because|π|=log2n,|α|=n-1,and|β|=|β|=n.2. Twin binary tree is a non-redundancy ﬂoorplan representation.

3. The complexity of the translation between twin binary sequence and ﬂoorplan is

O(n).

**Single Tree Representations**

An ordered-tree (O-tree) [2][3], or equivalently the B*∗ *tree [1] representation uses a spanning tree of the constraint graph and the dimensions of the blocks. Because the widths and heights of the blocks are given, the representation can describe one kind of general ﬂoorplan termed LB-compact. With a proper encoding, a great enhancement on the storage eﬃciency and the perturbation easiness is obtained.

A horizontal O-tree is derived with the following rules:

1. If block A lies adjacent to the left side of block

B, or,Xa+Wa=Xb(hereXais the coordinate of blockAon the X-axis andWais the width of block A), then on the O-tree,BisA’s child. If there happens to exist more than one block adjacent to the left side of blockB(satisfying the requirementXi+Wi=Xb), one of them is assigned to be the parent of blockB.2. If block

Alies on top of blockBand the two blocks have the same parents on the O-tree, thenBisA’s elder brother.3. A virtual block is presumed to have the left most position, and therefore serves as the root of the O-tree.

Fig. 53.15 shows an example of an O-tree representation for the same mosaic ﬂoorplan shown in Fig. 53.13.

If we show the pointer of every block pointing to its parent in the O-tree (Fig. 53.15(b)), we can ﬁnd that the pointers are in fact a subset of those in twin binary tree. Similarly a vertical O-tree can be built up. Without the loss of generality, hereafter we only discuss the horizontal O-tree.

Next, let’s describe the O-tree with linear lists: a bit string (denoted with *T *) and a label string (denoted with *π*). The bit string records the structure of an O-tree. We make a depth-ﬁrst traverse on the O-tree. A “0” is inserted into *T *for descending an edge while a “1” for ascending an edge. For example, the O-tree in Fig. 53.16 corresponds to the bit string *T**=“001100011011”*. Inversely, given the bit string, the structure of the O-tree is solely determined. To get the complete description of an O-tree, we need a second linear list, the label string, to record the labels of the tree’s nodes. Not only should the label string include all the labels of the tree’s nodes, but also reﬂect the labels’ positions on the tree. A depth-ﬁrst traverse generates such a linear list. For the example in Fig. 53.16, we have *π**= ‘FEACDB’*.

Given a horizontal O-tree, or *{**T**, **π**}*, and the dimensions of blocks, the positions of blocks can be derived with the following rules:

1. Each block has to be placed to the left of its children.

2. If two blocks overlap along their x-coordinate projection, then the block having a higher index in

πmust be placed on top of the other one.

In fact the second rule applies to the situation in which none of the two blocks is a descendant of the other, like blocks ‘*f **! *and “*a*”, or “*b*” and “*d*”, in Fig. 53.16. The way we derive *π *indicates that the block with higher index always stands “higher”. To get to a placement, we need to locate all the blocks. The following operation is executed on blocks according to their orders in *π*. Here *B**i *refers to the *i**–**th *block, and (*x**i**, y**i*) refers to the coordinate of *B**i*’s left-bottom corner.

1. Find

Bi’s parent,Bj, and then we havexi=xj+wj, herewjis the width of blockBj.2. Let

ψbe a set of blocks who have a lower index thanBiinπand have an projection overlap withBiin the X-axis, ﬁnd the maximumyk+wkforBk∈ψ, then we haveyi=max(yk+wk).

**Now we analyze the performance of O-tree:**

1. The bit string has a length of 2

nfor an O-tree ofnblocks, because each node except the root has an edge towards its parents and each edge is traversed twice during the construction of the bit string. The label string takesnlog2nbits for we have to use log2nbits to distinguish thenblocks. So the total memory occupied by an O-tree isn(2 + log2n). By comparison, a sequence pair takes 2nlog2nbits and a slicing structure takesn(6 + log2n) bits.2. The time needed to transform

{T,π}to a placement is linear to the number of blocks, or we can say the complexity of transforming{T,π}to a placement isO(n). For a sequence pair or a slicing structure, the complexity isO(nlog2log2n) orO(n) respectively. Upon this point, O-tree has the same performance as the slicing structure but is more powerful for representing a placement.3. The number of combinations is

O(n!·22n−2/n1.5), which is smaller than any other representation that has ever been discussed.

The ﬂoorplan of an arbitrarily given O-tree is not necessarily LB-compact. Yet in this case, we can compact the ﬂoorplan to reduce the chip area. Notice that an O-tree-to- placement transform tightens the blocks, with one direction having the priority. For ex- ample, in a placement transformed from a horizontal O-tree, the blocks are placed tighter along the X-axis than along the Y-axis. It would be undoubted that a placement trans- formed from a vertical O-tree will give Y-axis the priority. Thus, by iteratively making the transforms between horizontal O-trees and vertical O-trees via placements, we can ﬁnally reach an LB-compact ﬂoorplan (Fig. 53.17).

On the other hand, given an LB-compact ﬂoor plan, we can always derive an O-tree representation. For example, Figure 53.18 illustrates a general ﬂoor plan with seven blocks and the corresponding O-tree. O-tree is able to cover LB-compact ﬂoor plan with the smallest number of combinations in Table 53.1 and Fig. 53.2 because the O-tree structure avoids redundancy and screens improper ﬂoor plans by taking advantage of the knowledge of the block dimensions. For example, given an O-tree, we can convert it to a binary tree and ﬁnd many other possible trees to pair up as twin binary trees, which correspond to many diﬀerent mosaic ﬂoorplans. In the perspective of O-tree representation, these ﬂoorplans are the variations due to the diﬀerences of the block sizes.

The B*∗ *tree and the O-tree are equivalent because the transformation between the two is one to one mapping. The merit of the B tree is a diﬀerent data structure and implementation.

In summary, among the constraint-graphs based representations, from the point of view of the pointers necessary for representing the ﬂoor plans, O-tree is a subset of twin binary tree; twin binary is a subset of corner stitching; and corner stitching is a subset of constraint graphs, as demonstrated in Fig. 53.19.