Sequence Pair
The idea
Write the block names down twice, in two different orders: a pair of permutations (P+, P-). That pair, with no coordinates at all, encodes the relative position of every pair of blocks, through one rule comparing how the two blocks are ordered in the two sequences:
| order of a and b | relation |
|---|---|
| a before b in both P+ and P- | a is to the left of b |
| a before b in P+, after b in P- | a is above b |
(The other two cases are the mirror images: b left of a, or b above a.) Every pair of blocks gets exactly one horizontal or vertical relation, so a sequence pair fixes a complete arrangement, a floorplan topology with no geometry yet.
Decoding turns those relations into coordinates. The left-of relations form a horizontal constraint graph and the above relations a vertical one; the longest path to each block gives its x and y, and the longest overall paths give the chip's width and height. Naively that is quadratic per evaluation. The FAST-SP refinement computes it in O(n log log n) time by way of a longest common subsequence, which made sequence pairs fast enough for serious annealing.
The recipe
Step 1 (encode). Represent the arrangement as a sequence pair (P+, P-).
Step 2 (relate). For every pair of blocks, apply the rule above to get one left-of or above relation.
Step 3 (build graphs). Collect the left-of relations into a horizontal constraint graph and the above relations into a vertical one.
Step 4 (pack). Longest paths in the two graphs give every block's coordinates, an overlap-free packing, plus the chip dimensions.
Step 5 (perturb). For annealing, swap two names in one sequence, in both, or rotate a block, then decode and evaluate.
Watch it work: two orderings become a floorplan
Four blocks and a sequence pair. The walkthrough states the rule with a worked case, derives every pairwise relation, packs the relations into coordinates by longest path, shows the resulting floorplan, and ends on a move.
Pros, cons, and the trade-off
Strengths
- Complete: every arrangement of blocks, slicing or not, has a sequence pair, so non-slicing packings like the pinwheel are representable.
- Sound: every pair decodes to a legal, overlap-free packing.
- Ergonomic: moves are simple name swaps, and fixed-block, abutment, and symmetry constraints map to restrictions on the sequences.
Weaknesses
- Redundant search space: (n!) squared encodings, far more than the number of distinct packings, so annealing revisits many encodings of the same floorplan.
- Decode cost: the naive longest-path decode is quadratic; fast decoding (FAST-SP) is needed for large instances.
- Encoding, not an optimizer: it represents floorplans; a separate search chooses among them.
The trade-off
Sequence pairs trade a large, redundant search space for completeness and simplicity. Unlike slicing trees, they can represent any packing, and their moves and constraint handling are straightforward, which is why they became the default representation for two decades. The price is that (n!) squared encodings collapse onto far fewer distinct floorplans, so the search wanders, and fast decoding is required to make each step cheap.
Is it actually used today?
The evidence for sequence pairs is broad: macro placement, analog layout, and as the standard research baseline.
- Macro placement: a common representation in macro placers and floorplanners, research and industrial.
- Analog layout: symmetry and matching constraints map to restrictions on the sequences, which suits analog placement.
- Baseline: the representation every new floorplan encoding is compared against, and a standard teaching example of non-slicing floorplanning.