Slicing Trees and Polish Expressions
The idea
A slicing floorplan is one that can be built by recursive guillotine cuts: each cut runs straight across the whole current rectangle, splitting it into two, and each piece is cut again. That recursion is a binary tree: leaves are blocks, and every internal node is one cut, horizontal (H, top and bottom) or vertical (V, left and right).
Write the tree in postorder, children before their node, and you get
a Polish expression: a string like 12H3V, read "1 above 2, that
group beside 3". The string and the tree hold the same information,
but the string is a compact encoding a search can edit directly.
Wong and Liu's method runs simulated annealing on that string. Its two structural properties keep the search clean:
- Normalized: no two identical cut operators appear in a row, so each normalized expression encodes exactly one floorplan with no redundant encodings of the same layout.
- Balloting property: every prefix of the string has more operands than operators, which is exactly the condition for the string to decode to a valid binary tree.
The recipe
Step 1 (encode). Represent the current floorplan as a normalized Polish expression.
Step 2 (perturb). Apply one of three moves, each designed to keep the expression normalized and valid:
- M1: swap two adjacent operands (blocks).
- M2: invert a chain of cut operators (H becomes V and back).
- M3: swap an adjacent operand and operator, with a legality check that preserves normalization and the balloting property.
Step 3 (evaluate). Decode the expression to a floorplan in one tree walk and compute its cost, area plus weighted wirelength.
Step 4 (accept or reject). Apply the simulated-annealing acceptance rule, and repeat from Step 2 while cooling.
Watch it work: floorplan, tree, expression
The running example through all three views: a slicing floorplan, its slicing tree, the Polish expression as the tree's postorder, an annealing move editing the string, the properties that keep it valid, and the pinwheel that no slicing floorplan can produce.
Pros, cons, and the trade-off
Strengths
- Compact, complete encoding: every normalized expression is one floorplan and every move stays valid, so the search space is closed under the moves.
- Cheap evaluation: decoding and cost are a single linear tree walk.
- Exact sizing and soft blocks: block areas and flexible aspect ratios are handled exactly inside the slicing structure (see the Stockmeyer page).
Weaknesses
- Not every packing is slicing: the pinwheel and other arrangements cannot be produced by guillotine cuts, so the space excludes some optimal packings.
- Density gap: on hard-block problems that need those non-slicing packings, slicing solutions can trail in area.
- Annealing cost: many moves and a cooling schedule, with the usual tuning.
The trade-off
Slicing restricts the floorplan space to what guillotine cuts can produce. That restriction excludes some optimal packings, but it buys a compact and complete encoding, cheap evaluation, exact sizing, and clean handling of soft blocks. For problems dominated by soft macros, where area planning matters more than the last percent of packing density, slicing solutions are provably close to optimal, which is why the method remained competitive after non-slicing representations arrived.
Is it actually used today?
The evidence for slicing and Polish expressions is in teaching, hierarchical planning, and soft-macro area planning.
- Teaching: the standard first floorplanning algorithm in physical-design courses, for its clean encoding and moves.
- Hierarchical planning: the top levels of many hierarchical planners, where the block count is small and slicing structure is natural.
- Soft-macro area planning: problems where flexible block shapes and area budgets matter more than dense hard-block packing.