Floorplan Optimization

Imagine designing a bustling metropolis, complete with power stations, residential blocks, and intricate transport networks, all on a canvas the size of a fingernail. This is the fundamental challenge of floorplan optimization in modern integrated circuit (IC) design. The core problem extends beyond simply packing components; it involves arranging millions of functional units to ensure the final chip is not only compact but also fast, power-efficient, and manufacturable. A suboptimal layout can lead to signal delays, overheating, and catastrophic failure, making floorplanning one of the most critical stages in physical design. This article provides a comprehensive overview of this complex field. We will begin our journey in the ​​Principles and Mechanisms​​ chapter by exploring the foundational concepts, from simple 'slicing' layouts represented by binary trees and Polish expressions to the powerful search algorithms like simulated annealing that navigate the immense design space. From there, the ​​Applications and Interdisciplinary Connections​​ chapter will bridge theory and practice, revealing how floorplanners contend with the laws of physics—timing, heat, and congestion—and how these same optimization principles are applied in fields as diverse as 3D ICs and hospital architecture.

Imagine you are packing for a trip. You have a collection of items—books, clothes, boxes—and a single suitcase with a fixed size. Your task is to fit everything inside. This is a familiar challenge, a geometric puzzle we solve intuitively. You might place the large, rectangular books first, perhaps arranging them to form a stable base. You might then fill the gaps with smaller, more flexible items. You are, in essence, performing ​​floorplanning​​. In the world of computer chip design, this everyday puzzle is elevated to a science of staggering complexity and elegance. The "suitcase" is a thin wafer of silicon, and the "items" are millions of functional units called ​​macros​​—the memory banks, processing cores, and communication hubs that form the chip's brain. The goal is not just to fit everything, but to arrange them in a way that is small, fast, and efficient. This is the art and science of floorplan optimization.

How can we begin to describe an arrangement of millions of blocks? We need a language, a systematic way to encode a layout. Let's start with the simplest possible idea. Imagine our silicon die is a blank rectangle. We can take a blade and make a single, straight cut all the way across, either vertically or horizontally. This is a ​​guillotine cut​​. We now have two smaller rectangles, which we can partition further. Any layout that can be created entirely through a sequence of such cuts is called a ​​slicing floorplan​​.

This process has a beautifully simple structure that we can capture with a picture. Think of a family tree. At the very top, the root represents the entire chip. The first cut splits it into two children. If the cut is vertical ($V$), one child is the left region and the other is the right. If it's horizontal ($H$), one is the top and the other is the bottom. We continue this down the line until the final rectangles—the leaves of our tree—are the individual macros themselves. This structure is a ​​binary slicing tree​​.

What's truly remarkable is how this simple tree representation allows us to compute the size of the entire floorplan. Let's say a vertical cut ($V$) splits a region for two child blocks, one of size $(w_1, h_1)$ and the other of size $(w_2, h_2)$. To place them side-by-side, the total width is simply the sum of their individual widths, $w = w_1 + w_2$. The total height, however, must be large enough to accommodate the taller of the two, so $h = \max(h_1, h_2)$. Conversely, for a horizontal cut ($H$) that stacks them, the total height is the sum, $h = h_1 + h_2$, while the total width is governed by the wider of the two, $w = \max(w_1, w_2)$. By applying these simple rules recursively from the leaves up to the root, we can instantly calculate the total area of any slicing floorplan described by such a tree.

While a tree is a fine visual representation, computers often prefer a simple string of text. We can "linearize" our slicing tree into what's known as a ​​Polish expression​​, a notation familiar from old calculators. The rule is to visit the children first, then the parent (a postfix traversal). A layout where block A is to the left of block B would be written A B V. A layout where that combination is placed below block C would be A B V C H. This compact string is a complete blueprint for constructing the floorplan.

However, a subtle but profound problem emerges: redundancy. The geometric operation of stacking three blocks, A, B, and C, is a single idea. But our binary language forces us to break it into two steps. We could stack A and B, then add C on top (A B H C H), or we could stack B and C, and place A on top of that (A B C H H). Geometrically, these are equivalent arrangements (a tall, skinny stack), but to the computer, they are two different strings. This redundancy arises from the ​​associativity​​ of the cuts. A similar issue, ​​commutativity​​, arises because placing A next to B (A B V) is just a mirror image of placing B next to A (B A V).

For an automated search, this redundancy is a curse. The optimizer might waste its time exploring different strings that all lead to the same physical layout. The solution is to create a "canonical" form, a single, official representation for each unique layout. This is achieved by defining a ​​Normalized Polish Expression (NPE)​​. We enforce two simple rules:

1. ​​No consecutive identical operators​​: Substrings like HH or VV are forbidden. This resolves the associativity problem by forcing a single, standard way of representing a chain of identical cuts.
2. ​​Fixed operand order​​: For any set of blocks being combined by identical cuts, we enforce a fixed order based on their names (e.g., alphabetical). This resolves the commutativity problem.

With these rules, we establish a perfect one-to-one correspondence between the set of unique slicing layouts and the set of valid NPEs, creating a clean and efficient space for exploration.

We now have a language—the NPE—to describe any slicing floorplan. But how do we find the best one? The number of possible arrangements is astronomically large, far too vast to check one by one. We need a clever search strategy. Enter ​​simulated annealing (SA)​​.

The name comes from metallurgy, from the process of forging a metal by heating it, shaping it, and then cooling it very slowly. This "annealing" allows the atoms to settle into a strong, low-energy crystal lattice. Cooling too quickly ("quenching") traps defects and makes the metal brittle. We can apply the same principle to our optimization problem.

The "temperature" ($T$) is a control parameter in our algorithm. The "energy" of the system is our ​​cost function​​ ($C$), a single number that tells us how "good" a given floorplan is. A simple but effective cost function might be a weighted sum of the total chip area ($A$) and an estimate of the total wire length: $C = \alpha A + \beta \text{HPWL}$. Wire length is critical because shorter wires mean signals travel faster and consume less power. At the floorplanning stage, we don't know the exact wire paths, so we use a clever proxy called the ​​Half-Perimeter Wirelength (HPWL)​​. For each set of pins that need to be connected (a "net"), we simply draw the smallest possible bounding box around them and calculate half of its perimeter. Summing this over all nets gives a surprisingly good estimate of the final wirelength.

The SA process works as follows:

1. Start with a random NPE and a high "temperature".
2. Make a small, random change to the NPE. This "move" could be swapping two blocks (... A B ... $\leftrightarrow$ ... B A ...), flipping a cut type (... H ... $\leftrightarrow$ ... V ...), or rotating a piece of the slicing tree.
3. Calculate the cost of the new layout. If the cost is lower ($\Delta C \leq 0$), the move is good, and we always accept it.
4. If the cost is higher ($\Delta C > 0$), the move is bad. Here's the magic: we might still accept it. The probability of accepting a bad move is given by the Metropolis criterion, $p = \exp(-\Delta C / T)$.

At high temperatures, we are very liberal, frequently accepting even bad moves. This allows the search to jump out of mediocre solutions ("local minima") and explore the search space broadly. As we gradually lower the temperature, we become more and more selective, only accepting good moves and settling into a high-quality, low-cost final configuration. This elegant dance between exploration and exploitation is what makes simulated annealing so powerful.

Our slicing model is powerful and elegant. But does it cover all possibilities? Is every conceivable packing of rectangles a slicing floorplan? The answer, discovered in the 1980s, is a surprising "no."

Consider the classic counterexample: a central block X surrounded on all four sides by blocks N, S, E, and W. This "pinwheel" configuration is impossible to create with guillotine cuts. Try to make a vertical cut anywhere—if you go between W and X, you must slice through N and S. A horizontal cut is likewise foiled. This is a ​​non-slicing floorplan​​.

This is not just a mathematical curiosity. For complex chips, the optimal arrangement of blocks to minimize wirelength and meet timing goals often requires these intricate, non-slicing adjacencies. By limiting ourselves to a slicing representation, we might be throwing away the best possible solution before we even start looking. The ​​expressiveness​​ of our representation matters. A more expressive language can describe a richer world of possibilities.

To capture these general packings, we need more advanced representations like ​​Sequence Pairs​​ or ​​B*-trees​​. These do not encode cuts directly. Instead, they encode relative placement rules. For example, a ​​B*-tree​​ has simple semantics: a left child is placed to the right of its parent, and a right child is placed above its parent. To turn these abstract rules into a physical layout with coordinates, a beautifully efficient algorithm called ​​contour packing​​ is used. Imagine building the layout one block at a time. The first block is placed at the origin. To place the next, the algorithm identifies its target x-coordinate based on the B*-tree rules and then "drops" the block vertically until it settles on the "skyline" formed by the already-placed blocks. This process is not only general enough to create any non-slicing layout, but it's also incredibly fast—it runs in time proportional to the number of blocks, making it perfect for the inner loop of an optimizer.

As our understanding deepens, so too must our definition of a "good" chip. Minimizing just area and wirelength is a good start, but modern designs have a far more sophisticated set of goals, captured in a ​​composite objective function​​.

• ​​Routability​​: After the blocks are placed, we must physically route tens of millions of tiny wires between them. If our placement creates a "traffic jam" where too many wires must pass through a narrow channel, we have ​​congestion​​. The floorplan is unroutable. Our cost function must include penalties for predicted congestion to produce a placement that is not just dense, but also wireable.
• ​​Timing​​: A chip is a symphony of signals racing along wires to meet deadlines measured in trillionths of a second. Using ​​Static Timing Analysis (STA)​​, we can calculate the ​​slack​​ for critical signal paths—the difference between when a signal is required to arrive and when it actually does. ​​Negative slack​​ means a timing violation; the chip is too slow. The cost function must severely penalize these violations to guide the optimizer toward a design that meets its performance target.

The final cost function is a carefully tuned, weighted sum of all these competing factors. The art of floorplanning is the art of navigating the complex trade-offs between area, wirelength, routability, and timing to find a balanced and superior solution.

Looking back, we can see the floorplanning problem from several perspectives. From a formal mathematical viewpoint, the simple constraint of "no overlap" for any two blocks $i$ and $j$ is a disjunction: block $i$ is left of $j$, OR right of $j$, OR below $j$, OR above $j$. This can be translated into a system of linear inequalities, providing a very general but often computationally intensive formulation.

And what happens when a design has not thousands, but hundreds of millions of components? We cannot optimize everything at once. We must use ​​hierarchy​​. Much like an army has squads, platoons, and companies, we group related macros into clusters. We first solve the floorplanning problem for the blocks inside each cluster. Then, to the top-level optimizer, this entire cluster is abstracted away and presented as a single "soft block." It's soft because it doesn't have a fixed shape; it has a ​​shape curve​​—a menu of possible width-for-height trade-offs. The top-level optimizer can then choose a shape from this menu that best serves the global layout, without needing to worry about the cluster's internal details. This divide-and-conquer strategy is the only way to manage the breathtaking complexity of modern chip design, turning an intractable global puzzle into a series of manageable local ones.

From the simple idea of a guillotine cut to the sophisticated machinery of hierarchical, non-slicing optimization, the principles of floorplanning reveal a deep interplay between geometry, combinatorics, and heuristic search. It is this beautiful and practical science that allows us to arrange the atomic-scale cities etched onto silicon, the very foundation of our digital world.

Imagine you are an architect, but not for a building of steel and glass. Your task is to design a city—a bustling metropolis with billions of inhabitants—all crammed onto a canvas the size of your thumbnail. This is the world of modern integrated circuit (IC) design, and the art of arranging this microscopic city is called ​​floorplan optimization​​.

Having journeyed through the core principles and mechanisms of floorplanning, we now broaden our horizons. We will see how these ideas are not just abstract puzzles but the essential tools for solving real, complex engineering challenges. We will discover how the simple act of arranging rectangles on a plane becomes a delicate dance with the fundamental laws of physics. And finally, we will see this dance performed on entirely different stages, revealing the universal beauty of the underlying principles.

The primary and most critical application of floorplanning is, of course, the physical design of the very chips that power our world. The journey from a software algorithm to a tangible piece of silicon is a long one, involving many stages of transformation. Floorplanning is arguably the most pivotal of these steps; it is the moment when an abstract blueprint of logic gates and connections first takes on a physical form.

The most basic question a designer faces is almost child-like in its simplicity: "Can we make it all fit?" Given a set of rectangular modules, each a self-contained functional unit, can we arrange them within a prescribed boundary? This is the essence of the packing problem. Yet, the simplicity is deceptive. The number of ways to arrange even a few dozen blocks is astronomical, greater than the number of atoms in the known universe. A brute-force search is utterly hopeless.

This is where we see the first glimpse of the field's deep elegance. We don't have to check every single possibility. We can be clever. Using techniques like dynamic programming, we can build up solutions for larger groups of blocks from the optimal solutions for smaller subgroups. And what does "optimal" mean here? We employ the beautiful concept of Pareto optimality. A layout $(w_1, h_1)$ is better than $(w_2, h_2)$ only if it is smaller in at least one dimension and no larger in the other. We only keep the "champion" arrangements—those that are not dominated by any other—and discard the rest. This set of non-dominated champions forms a curve of possibilities, the Pareto front, a concept we will meet again.

Of course, just fitting is not enough. The components of our silicon city must communicate. The total length of the "wires" connecting them is a crucial factor. Longer wires consume more power and introduce delays. So, the problem evolves from finding a feasible layout to finding a good layout. This is a formidable optimization task, where the objective is to minimize a cost function, often a weighted sum of the chip's total area and its total wirelength. To navigate the colossal search space, designers employ powerful metaheuristic algorithms like Tabu Search or Simulated Annealing. These methods intelligently explore different arrangements—swapping modules, changing the cutting pattern—in a guided search for ever-better solutions. To grant even more flexibility, designers have also developed more advanced representations beyond simple recursive slices, such as the B*-tree, which can describe any possible arrangement of non-overlapping rectangles.

A well-arranged city is more than just compact. Its citizens must be able to travel efficiently, and the city itself must not become a crippling "heat island." Our silicon metropolis is no different. Just as our layout begins to take shape, the fundamental laws of physics reassert themselves with a vengeance. The simple geometric puzzle now collides with electromagnetism and thermodynamics.

First, there is the tyranny of the clock. A chip's value lies not just in what it can do, but how fast it can do it. The time it takes for an electrical signal to travel between two blocks is directly related to the length of the wire connecting them. For most connections, a small change in length is inconsequential. But for some, the connection is part of a "critical path"—a chain of logic where every picosecond counts. The time budget is so tight that any extra delay could cause the entire chip to fail at its target speed.

This reality forces our floorplanning objective to become much smarter. We can no longer treat all wires equally. Using Static Timing Analysis, we can calculate the "slack" for each connection—the temporal wiggle room it has before it jeopardizes the chip's timing. Our cost function now becomes a sum of weighted wirelengths, where the weight for each wire is derived from its slack. A wire on a critical path (low slack) gets a huge penalty for being stretched, while a wire on a non-critical path (high slack) can be lengthened with little consequence. The floorplanner is now juggling not just space, but also time.

As if that weren't enough, there is the issue of heat. Every active transistor is a tiny heater. Billions of them, switching billions of times per second, generate an enormous amount of heat in a tiny area. If this heat isn't managed, "hotspots" can form, where the temperature soars. These hotspots degrade the chip's performance, reduce its lifespan, and can even cause it to fail catastrophically. The floorplanner must become a thermal engineer. By applying Fourier's law of heat conduction, we can create a thermal map of the chip and build a predictive model. The optimization objective gains new terms: we must now also minimize the peak temperature and the thermal gradients across the chip. This might mean spreading out power-hungry blocks or moving them closer to on-chip heat sinks.

And here we face a classic engineering dilemma. To cool the chip down, we might want to spread the hot components far apart. But doing so makes the wires between them longer, potentially creating a new timing problem! This is the great trade-off. There is no free lunch. Improving one metric often degrades another. This is where the concept of the Pareto front returns with full force. Instead of a single "best" solution, the designer is presented with a frontier of optimal compromises: one design that is very fast but runs hot, another that is very cool but runs slower, and a range of balanced options in between. The final choice becomes an act of engineering judgment, informed by the elegant mathematics of multi-objective optimization.

Having seemingly mastered the two-dimensional plane, the relentless drive for more computational power pushes designers to conquer a new dimension: the vertical. If you can't build out, you build up. This leads to the fascinating world of Three-Dimensional Integrated Circuits (3D ICs).

This is not merely stacking two separate chips; it is a truly monolithic creation where a single system is partitioned across multiple layers, or "tiers," of silicon, fabricated one on top of the other. The layers are connected by ultra-dense vertical wires called Monolithic Inter-tier Vias (MIVs). The floorplanner's job just became exponentially more complex. They must now perform 3D partitioning, deciding not only where a block goes on a floor, but which floor it belongs on. The goals now include minimizing the number of costly inter-tier connections, managing the heat that gets trapped between layers, and respecting the unique manufacturing constraints of each tier. The silicon city has become a skyscraper.

We have been on a journey deep inside the computer, exploring a problem that seems esoteric and specific to the world of electronics. But what if I told you that the very same principles you've just learned are being used to design... hospitals?

Consider the layout of a hospital floor. The "modules" are the departments: the Emergency Room, Radiology, the ICU, the surgical suites. The "wires" are the paths taken by nurses, doctors, and patients. The "flow" between modules is the frequency of trips between departments. The objective? To arrange the hospital to minimize the total daily walking distance for the staff, thus reducing fatigue and improving efficiency, while ensuring that functionally related departments (like the ER and Radiology) are adjacent to each other.

The problem is identical in its mathematical structure to chip floorplanning. We are placing blocks (departments) on a grid to minimize a cost function based on weighted distances (flow-weighted walking distance) and adjacency constraints (workflow efficiency). The same algorithmic tools, like Genetic Algorithms, can be used to find optimal layouts.

This is the profound and beautiful unity of scientific and engineering principles. The mathematics doesn't care if it's minimizing electron travel time or nurse fatigue. The underlying structure of the optimization problem—of arranging interconnected entities in a space to optimize for flow and proximity—is universal. From the infinitesimal world of the microchip to the human scale of architecture, factory layout, and urban planning, the principles of floorplan optimization provide a powerful and elegant language for designing the complex systems that shape our lives.