Arranging blocks on a die is packing, sizing, and wirelength optimization all at once, and it is NP-hard (Non-deterministic Polynomial hard) even in toy forms. Fifty years of answers: recursive partitioning, slicing trees, a zoo of non-slicing representations searched by annealing, exact mathematical programming, and lately machine learning.
The oldest school: build the floorplan directly from the netlist's structure, cutting or growing your way to a layout instead of searching a space of candidates.
Recursively bipartition the netlist while bipartitioning the die: blocks that talk end up near each other because cutting their connection would have been expensive.
Seed the layout with one block, then repeatedly attach the unplaced block with the strongest connection to what is already placed. Greedy, linear, and a surprisingly good baseline.
Start from the desired adjacency graph (which blocks should touch which), and construct a floorplan that realizes it as a rectangular dissection, using planar graph theory.
Restrict floorplans to recursive horizontal and vertical cuts and the problem gains beautiful structure: a binary tree, a compact algebra, and exact sizing algorithms.
Represent a floorplan as recursive cuts encoded in a normalized Polish expression, and let simulated annealing perturb the expression. The single most taught floorplanning algorithm ever.
Given a slicing tree, choose every block's orientation (and shape, for soft blocks) to minimize total area, exactly, in polynomial time, by merging shape curves up the tree.
From 1995 to 2004 the field raced to encode arbitrary block arrangements as small combinatorial objects that a search engine can perturb. Each entry here is one such encoding, with its own trade-off between expressiveness, solution-space size, and decode cost.
Two permutations of the block names encode, for every pair of blocks, whether one is left of or below the other. The first practical encoding of arbitrary (non-slicing) floorplans, and still the most cited.
Place blocks into cells of an abstract n-by-n grid of 'slicelines'; relative order between grid cells defines the geometry. From the same lab as the sequence pair, one year later.
An ordered tree encodes left-edge abutment: each block leans against its parent, and a depth-first traversal with a contour structure decodes the packing in linear time.
A binary tree where left child means 'adjacent to my right' and right child means 'above me, same x'. Decodes by preorder traversal against a contour. The practical favorite for hard-block packing ever since.
Describe a mosaic floorplan by repeatedly deleting the top-right corner block and recording how it was attached: orientation bit, insertion list, junction count.
Keep the horizontal and vertical constraint graphs themselves, transitively closed, as the representation; moves edit the graphs directly with geometric meaning.
A pair of binary sequences with a twin property gives a one-to-one, no-waste encoding of mosaic floorplans, fixing the redundancy and dummy-block issues of earlier mosaic codes.
Encode a packing as the order in which blocks are pushed into the bottom-left corner region, enabling constant-time incremental updates during annealing moves.
Keep constraint graphs like the Transitive Closure Graph, but store only adjacency-level edges, keeping the structure sparse while remaining a complete representation.
A representation only defines the space; something has to search it. These are the optimizers that drive the representations above.
Accept worse solutions with probability exp(-Δcost / T) and cool T slowly: the metaheuristic that powered every representation on this page for forty years.
Evolve a population of floorplans with selection, mutation, and crossover. Attractive in principle, tricky in practice: recombining two floorplans meaningfully is the eternal obstacle.
Write non-overlap as big-M constraints with binary left/right/above/below choices and let a solver find the provably optimal floorplan - for small instances.
Modern chips give you a fixed die and macros mixed with millions of cells. The problem statement changed, and the algorithms changed with it.
Modern floorplanning is not 'minimize area' but 'fit inside this exact rectangle'. Parquet reframed annealing around outline-violation penalties and slack-driven moves.
Treat block positions as continuous variables: minimize smooth wirelength with attractive forces, push overlap out with repulsive or density terms, then legalize. The bridge between floorplanning and modern placement.
Cluster the netlist by RTL (Register Transfer Level) hierarchy and dataflow, anneal clusters hierarchically with guidance costs, and pin macros to sensible edges: the practical open-source answer for macro-heavy chips.
A neural policy places macros one at a time on a grid, trained by reinforcement learning against a wirelength-and-congestion reward, transferring experience between chips. Famous, deployed, and vigorously debated.