Explore / Methods & Algorithms / Floorplanning / Bounded-Sliceline Grid

Bounded-Sliceline Grid

Floorplanning research 1996 Nakatake, Fujiyoshi, Murata, Kajitani grid-based meta-grid states

The idea

The Bounded-Sliceline Grid (BSG) abstracts the die into an n-by-n grid of rooms separated by horizontal and vertical sliceline segments, and assigns the n blocks to distinct rooms, leaving the rest empty. Room adjacency defines the relations: a block whose room is west of another's is to the left of it, and a block whose room is north of another's is above it.

Decoding runs longest-path on the induced horizontal and vertical constraint graphs to produce coordinates, the same packing step used for the sequence pair. Unlike a literal grid, the slicelines are elastic: each room stretches to fit its block and empty rooms collapse, so the grid encodes topology and the packing supplies geometry.

The recipe

Step 1 (assign). Place the n blocks into n distinct rooms of an n-by-n grid, leaving the rest empty.

Step 2 (relate). Read a left-of relation from each west-east room adjacency and an above relation from each north-south adjacency.

Step 3 (pack). Longest paths on the horizontal and vertical constraint graphs give each block's coordinates; elastic rooms stretch to fit and empty rooms collapse.

Step 4 (perturb). For annealing, swap two blocks' rooms, move a block to an empty room, or rotate a block. Only local relations change, which the incremental evaluator exploits.

Watch it work: rooms to floorplan

Four blocks in a 3-by-3 room grid. The walkthrough assigns blocks to rooms, reads the relations off the grid, packs them into a floorplan by longest path, and shows a room-swap move re-decoding to a new layout.

Pros, cons, and the trade-off

Strengths

  • Complete: with a large enough grid, every packing is representable.
  • Local moves: a room operation changes only a few relations, so incremental re-evaluation is cheap.
  • Explicit rooms: the room structure makes symmetry and matching constraints easy to state, which suits analog placement.

Weaknesses

  • Emptiness: an n-by-n grid has n squared rooms for n blocks, so the state carries a large amount of empty space.
  • Grid size is a knob: too small excludes solutions, too large bloats the search space.
  • Overshadowed: the sequence pair, from the same lab a year earlier, encodes the same generality with no empty rooms.

The trade-off

The BSG (Bounded-Sliceline Grid) trades a larger, sparser state for local moves and an explicit room structure. The room viewpoint makes constraints easy to express and each move cheap to evaluate, but the n-by-n grid for n blocks carries much emptiness, and its size must be tuned. Against its sibling the sequence pair, which represents the same set of packings with no empty rooms, that overhead is why it saw less adoption.

Is it actually used today?

The evidence for the BSG (Bounded-Sliceline Grid) is mostly in the literature and in constraint-driven placement.

  • Literature: one pole of the representation-design space, and a standard comparison point in floorplan-representation studies.
  • Constraint-driven placement: the room and relation viewpoint resurfaces where explicit rooms make constraints natural.
  • Analog floorplanning: some analog placers use room-based structures because symmetry and matching constraints are easy to state on rooms.

References and further reading