Explore / Methods & Algorithms / Floorplanning / Cluster Growth

Cluster Growth

Floorplanning foundational 1970s folk method, many variants simplest possible greedy, no lookahead

The idea

Cluster growth builds a floorplan one block at a time. Pick a seed block, place it, then repeat a greedy loop: score every unplaced block by its connectivity to the blocks already placed, attach the highest-scoring block in the best open position next to the growing cluster, and continue until every block is placed.

Each unplaced block gets a connectivity score: its total connection to the blocks already placed.

score(u) = sum over placed blocks p of weight(u, p)
  • u an unplaced block being considered
  • weight(u, p) the connectivity between u and an already-placed block p (number of shared nets, or a net-weighted count)
  • the block with the highest connectivity score is the most tied to the current cluster, so attaching it next keeps strongly connected blocks close; ties are broken toward the higher-degree block

The chosen block is then placed in the open slot next to the cluster with the least added-wire cost: the wire that slot would add.

added-wire cost(s) = sum over placed blocks p of weight(u, p) × distance(s, p)
  • s an empty grid slot next to a block already placed
  • weight(u, p) the connectivity between the chosen block u and placed block p
  • distance(s, p) the Manhattan distance from slot s to placed block p

The block is placed in the slot with the lowest added-wire cost.

A linear-ordering refinement improves the seed-and-grow behavior: first compute a good one-dimensional order of all blocks (repeatedly append the block with the most connections to the ordered prefix and the fewest to the rest), then fold that order into rows on the die.

The recipe

Step 1 (seed). Choose a seed, usually the highest-degree block or one tied to fixed pins, and place it.

Step 2 (score). Compute each unplaced block's connectivity score, its total connection to the placed set.

Step 3 (attach). Take the block with the highest connectivity score and place it in the open adjacent slot with the lowest added-wire cost.

Step 4 (repeat). Return to Step 2 until every block is placed.

Watch it work: seed and grow

Nine blocks with weighted connections. The walkthrough picks the seed by degree, then attaches blocks one at a time with the score arithmetic shown at each step, and ends on the role the result plays in a real flow.

Pros, cons, and the trade-off

Strengths

  • Linear and simple: one greedy pass, trivial to implement, fast on any block count.
  • Legal from nothing: produces a complete, legal floorplan without a starting solution.
  • Good starting point: an annealer seeded from a cluster-growth floorplan needs far less cooling than one seeded from a random scatter.

Weaknesses

  • Greedy and final: every choice is committed with no global view and no backtracking, so quality trails search-based methods on hard instances.
  • Seed-sensitive: a poor seed or an early misplacement propagates through the rest of the growth.
  • Shape-agnostic: the basic method treats blocks as slots and does not reason about differing block shapes.

The trade-off

Cluster growth trades solution quality for speed and simplicity. It cannot search or reconsider, so it will not find a strong floorplan on its own. What it does provide is a legal, connectivity-aware starting point in linear time, which is exactly what an iterative method needs before it begins. That role, not standalone quality, is why the method persists.

Is it actually used today?

The evidence for cluster growth is as a construction step and a baseline, not as a standalone floorplanner.

  • Initial construction: iterative floorplanners and placers use a greedy constructive pass to build the starting solution before search begins.
  • Fast prototyping: quick-estimate modes that need a legal floorplan without the cost of search.
  • Teaching and baselines: the standard first comparison point against which search-based floorplanners are measured.

References and further reading