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

摘要

集積回路のレイアウト設計でのバス配置を考慮したフロアプラン設計の間題において、ある一つのバスが実現できるか否かの判定は順列を増加列と減少列に分解する問題に定式化できることを見い出し、折れ曲がりと分岐が2回でバスが実現できるか否かを、長さnの順列を減少列と増加列2つもしくは増加列と減少列2つに分解することにより判定するというO（n~5）時間のアルゴリズムを我々は以前に提案した。しかし、このアルゴリズムの計算複雑度は大きいので、本稿ではこれをO（n~2）時間で実行するアルゴリズムを提案し、計算機実験によりその効果を確かめた。%In Bus Driven Floorplanning problem, problem to judge that a given bus can be realized with two bends or branches was shown to be equivalent to divide the corresponding permutation into a decreasing subsequence and two increasing subsequences or into an increasing subsequence and two decreasing subsequence. We proposed an algorithm for such division, whose time complexity is O(n~5). In this paper, we propose a fast algorithm for such division, whose time complexity is O(n~2). Experimental comparisons with the conventional algorithms indicate that our proposed algorithm is fast and effective.