MATH Seminar

Title: 3D Floorplanning and Tree Representations
Seminar: Combinatorics
Speaker: Paul Horn of Harvard University
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2012-11-02 at 4:00PM
Venue: MSC W303
Download Flyer
Abstract: A (2D) mosaic floorplan is a partitioning of a square into $n$ rectangles. Schemes which can be used to represent and count these floorplans, under a suitable topological equivalence, have applications in chip design. A 3D mosaic floorplan is a partitioning of a box into $n$ smaller boxes. Modern chip construction techniques, allowing chips with multiple layers, have fueled the desire to understand the number of 3D mosaic floorplans and how to represent them. For the 2D case, the number of unlabeled floorplans with $n$ rectangles, up to topological equivalence, is exponential in $n$. For many classes of 3D floorplans the number of floorplans is also exponential. Notable among these are 'slicing' floorplans, where to obtain an $n$ box floorplan one starts with an $n-1$ box floorplan and divides a box in two. In this talk, we discuss some of the difficulties with more general 3D floorplans, even with only two layers. In particular, if $F_n$ denotes the number of 3D floorplans with two levels, we show that $\log F_n \sim \frac{1}{3}n \log n$, and hence $F_n$ grows superexponentially in $n$. The upper bound comes from a representation scheme using trees, while the lower bound comes from a random construction.