重矩形分割の探索のための一考察

摘要

近年、複数の能動層を積層し、複数層に渡る配線のためにTSV(Through Silicon Via) により層間を貫通配線した三次元LSI の研究が盛んに行われている。そのフロアプラン設計のための配置の表現として、複数の矩形分割を重ねた重矩形分割[2] と、それの容易な探索のためにそれを上から透かして見た単層重矩形分割[3] が提案された。単層重矩形分割に探索のための局所的な変更を加えた場合、これが単層重矩形分割とならない、つまり、重矩形分割に対応しないことがあるので判別する必要があるが、局所的な計算のみでの判別が望まれる。そこで、単層重矩形分割の局所的な変更時に単層重矩形分割であるかの効率的な判定を目的として、本稿では分割線同士の交差が許容された矩形分割が単層重矩形分割であることの必要十分条件を明らかにする。