図4. チェス盤
Sequence Pair(以下SP)についてご紹介します。SPは元UCBの客員研究員の村田博士が考案された、ブロックプレースメントアルゴリズムで、図4のような"チェス盤"がベースになっています。
チェス盤に駒を並べる規則は同じ斜め線上に他の駒をおけないというルールです。Sequence Pairの意味は、モジュール名の左上辺への射影(nlhkfjoedmbgaicp)と、右上辺への射影(djmegbphfnlcoika)の2つの順序対によってこのチェス盤が一意的に記述されるためです。
さて、これに対応するのが図5のモジュール配置になります。
どのような規則でこれが生成されるかといえば、例えば図4において、モジュールfから斜め線を引くと盤面を4つに分離することができます。
次に、それら分離された4半面をそれぞれ、モジュールfに対して上、右、下、左と呼べば、その4半面に属するモジュールの集合が得られます。これをそれぞれのモジュールに対して行なえば、モジュール相互に関して例えばfに対してo, c, i, aは必ず右に配置しなければいけないという制約が得られます。
全てのモジュールに関してこのような位置関係の制約条件を設定した上で、制約条件をもとに高速に図5のようなモジュール配置を行なうことが可能です。以上に基づき、乱数によって様々なチェス盤を発生し、それに基づいた配置を行ない、その中で最小のものを選択することになります。
LSIのフロアプランにおいてはこの他に配線の可能性も考慮する必要がありますが、これはSP Place(SPベースのブロックプレースメント)で様々な配置を生成しておき、その一つひとつに対して配線長を計算することで行なうことができます。