3D Floorplan Representations: Corner Links and Partial order Fang Qiao1, Ilgweon Kang1, Daniel Kane1, Fung-Yu Young2, Chung-Kuan Cheng1, Ronald Graham1 University of California, San Diego, La Jolla, CA 92093 2 The Chinese University of Hong Kong, Shatin, Hong Kong 1 Email: 1 {faqiao, i1kang, dakane, ckcheng, graham}@ucsd.edu, 1 Overview Floorplanning background Corner links and partial ordering

4 properties: Reduction of corner links to partial order Four trees (special case of corner links) is sufficient to represent non-degenerate floorplans Characterization of valid floorplans in the partial order representation Partial order representation can give absolute coordinates and dimensions of all blocks in a floorplan 2 Floorplan - Introduction Floorplan Given a fixed number of blocks and their dimensions Describe the blocks spatial position and orientation Significance Foundation for communication and analysis in VLSI circuit design Enables us to study theoretical properties

3 General Floorplan (cont.) Mosaic General Slicing 3 classes of floorplan General Mosaic non-slicing floorplans without empty space Slicing recursively subdividing blocks with new boundaries perpendicular to a dimensional axis General Floorplan Mosaic Floorplan Slicing Floorplan 4

Blue: vertical Red: horizontal Slicing Floorplan A B E D D E F C A B F C Slicing Ordered Tree Slicing floorplan Slicing ordered tree #slicing floorplan is 2 Schrder number.

T 00 900 T T 1800 C+-neighbor: 00 T-junction, block on right 2700 T-junction, block on top B 00 2700 A A B C--neighbor: 900 T-junction, block on top 1800 T-junction, block on left A 900 B

A B 1800 T Mosaic Floorplan Twin Binary Trees 2700 Twin Binary Trees F C B A D F E B

C 1 A E A D 0 X X X D E X 1 F 0 (1)=11001 0

1 B 1 C 0 (2)=00110 order(1)=order(2)=ABCDFE 0 1 Mosaic Floorplan Terminologies Non-degenerate: blocks cannot shift against each other T-junctions: Two block corners meeting the edge/face of a third block Non-Degenerate & T-junctions

8 Floorplan (cont.) Simple Examples of Representations Examples Absolute coordinates and dimensions Corner-Stitching (Ousterhout et. al., 84, 85) Twin Binary Trees (Yao et. al., 03; Young et. al., 03) Corner-Stitching bloc k x y z widt h leng

th heig ht a 0 0 0 2 2 1 b 0 0 1 2

2 1 Absolute Coordinates Twin Binary Trees 9 3D Floorplan Much more recent compared to 2D Floorplanning Increasing interests dynamically reconfigurable FPGA design 3D integrated circuits Example 3D Floorplan 10

3D Floorplan Representations Partial Order (Yuh et. al., 07) Describes a 3D floorplan topology with three transitive closure graphs Transitive closure relation example, x-dimension Equality: any two touching yz faces Order: yz-faces of the same cube are ordered by x Partial Order Representation of the Example 11 3D Floorplan Representations (cont.) Corner Links Describes all sets of neighboring corners of blocks in a fixed floorplan. Definitions

Neighboring corners: all 1/8th corners that are pair-wise equal by the corner equations Corner equations: means the corner of block touches the corner of block Neighboring corners: 1/8th corner and 1/8th corner 1/8th corner and 1/4th corner 1/8th corner and 1-half corner 12 3D Floorplan Representations (cont.) Corner Links 36 such sets in our example Inspired by corner-stitching

Neighboring corners in our example: , etc. 13 3D Floorplan Representations (cont.) Four Trees Special case of Corner Links when the floorplan is non-degenerate Neighboring corner information as a tree structure Rooted at four opposite corners of the floorplan space Each outgoing edge begins at one of the opposite corners

Example opposite corners: (+++, -+-, - -+, +- -) Four Trees Representation of the Example Opposite Corners 14 3D Floorplan Representations Properties 1. Corner Links to Partial Order Given a floorplan in the corner links representation, we can enumerate all cutting planes, and generate the partial order representation Cutting Planes - a plane characterized by the transitive closure of face equalities coming from faces that touch at a corner A cutting plane in the z dimension of our

example. Highlighted corners gives equal faces across the cutting plane with respect to their color code. 15 3D Floorplan Representations Properties 1. Corner Links to Partial Order (Cont.) For each corner in a corner links representation, we can: Take the aforementioned transitive closure Obtain two sets of blocks, one above the plane, one below the plane Footprint Shape of the outer contour of the set that touches the cutting plane Key idea - footprints of any such two sets from Corner Links match 16 Right: footprints above and below the cutting plane 3D Floorplan Representations

Properties 1. Corner Links to Partial Order (Cont.) Lemma 1: every corner in the floorplan has an odd number of neighbors that touches it at their corner Lemma 2: the footprints of the two sets of blocks on the plane should match, or Lemma 1 would be violated Take the symmetric difference of the footprints above and below the cutting plane, if they do not match, theres some lower-left most corner to the symmetric difference. This would mean that theres an odd number of neighbors in the neighborhood Therefor, corner links gives all cutting planes at every corner. Symmetric difference of two footprint that supposedly do not match. This would mean that has an even number of corner neighbors.

17 3D Floorplan Representations Properties 2. Four Trees as a Special Case of Corner Links For non-degenerate, mosaic, floorplans, four directed trees is sufficient for unique representation Nodes represent blocks, edges represent touching corners Suppose the four trees are rooted at the , , and (red) corners; the outgoing edges are also sourced at red corners of blocks Every two neighboring black corners requires red corner(s). Looking under the green block, a black corner of the grey block neighbors the red corner of the blue block.

Key idea - at any block intersection in the floorplan, there must be at least one red corner 18 3D Floorplan Representations Properties 3. Valid Floorplans in Partial Order Given any two blocks in a valid mosaic floorplan, they must be related in at least one of the three partial orders Valid floorplan: no two blocks overlap in the topology Illustration: consider two blocks and , with the corner of greater or equal to the corner of Illustration of block relations. 19 3D Floorplan Representations Properties 3. Valid Floorplans

in Partial Order (cont.) Note that every corner touches 3 cutting planes Starting from the corner of , one can trace edges and corners of blocks until reaching a cutting plane of the corner of Repeat operation in 2D if necessary. Lemma 3: If two blocks meet at a corner, then the corresponding faces at that corner are related in all three of the face partial orders Lemma 4: If two rectangles meet at a corner in 2D, then the corresponding faces at that corner are related in both face partial order of the 2D plane. Note this is the 2D case of Lemma 3

Red block and pink block related in all three dimensions Therefore and are related in at least one Red block and pink block related in x and y 20 3D Floorplan Representations Properties 4. Partial Order Yields 3D Absolute Coordinates Partial order gives relative order of blocks start and end in each dimension. This is analogous to the cutting planes For each dimension go through each cutting plane while keeping a counter, this generates the start and end coordinates of each block in that dimension

Generating z-dimension coordinates of our example from partial order. 21 Conclusion In this study, we presented: Preliminary results on a novel 3D floorplan presentation Analyzed its relationship to existing 3D floorplan representations Future work: Formally bounding the complexity of the representations Graph embedding Higher dimension floorplan beyond 2D and 3D Research 3D representation is still new, we hope to stimulate interest and encourage collaboration 22