折れ曲がりと分岐を許容したバスドリブンフロアプラン設計手法の効率化

摘要

集積回路のレイアウト設計でのバス配置を考慮したフロアプラン設計の問題において、ある一つのバスが実現できるか否かの判定は順列を増加列と減少列に分解する問題に定式化できることを見い出し、折れ曲がりと分岐が2回でバスが実現できるか否かを、長さnの順列を減少列と増加列2つもしくは増加列と減少列2つに分解することにより判定するというO(n{sup}5)時間のアルゴリズムを我々は以前に提案した。 しかし、このアルゴリズムの計算複雑度は大きいので、本稿ではこれをO(n{sup}2)時間で実行するアルゴリズムを提案し、計算機実験によりその効果を確かめた。