No |
187631 |
標題(和) |
折れ曲がりと分岐を許容したバスドリブンフロアプラン設計手法の効率化 |
標題(英) |
Improved Method of Multi-Branched Bus Driven Floorplanning |
研究会名(和) |
通信方式, 信号処理, 回路とシステム |
研究会名(英) |
Communication Systems, Signal Processing, Circuits and Systems |
開催年月日 |
2008-03-06 |
終了年月日 |
2008-03-07 |
会議種別コード |
5 |
共催団体名(和) |
|
資料番号 |
CAS2007-132, SIP2007-207, CS2007-97 |
抄録(和) |
集積回路のレイアウト設計でのバス配置を考慮したフロアプラン設計の問題において、\r\nある一つのバスが実現できるか否かの判定は\r\n順列を増加列と減少列に分解する問題に定式化できることを見い出し、\r\n折れ曲がりと分岐が2回でバスが実現できるか否かを、\r\n長さ$n$の順列を減少列と増加列2つもしくは\r\n増加列と減少列2つに分解することにより判定するという\r\n$O(n^5)$時間のアルゴリズムを我々は以前に提案した。\r\nしかし、このアルゴリズムの計算複雑度は大きいので、\r\n本稿ではこれを$O(n^2)$時間で実行するアルゴリズムを提案し、\r\n計算機実験によりその効果を確かめた。 |
抄録(英) |
sequence-pair, バスドリブン, フロアプラン設計, 増加部分列, 減少部分列\r\n\r\nsequence-pair, Bus-driven, floorplanning, increasing subsequence, decreasing subsequence |
収録資料名(和) |
電子情報通信学会技術研究報告 |
収録資料の巻号 |
Vol.107, No.527,529,531 |
ページ開始 |
41 |
ページ終了 |
46 |
キーワード(和) |
sequence-pair,バスドリブン,フロアプラン設計,増加部分列,減少部分列 |
キーワード(英) |
sequence-pair,Bus-driven,floorplanning,increasing subsequence,decreasing subsequence |
本文の言語 |
JPN |
著者(和) |
平良洋祐 |
著者(ヨミ) |
タイラ ヨウスケ |
著者(英) |
Yosuke Taira |
所属機関(和) |
東京農工大学 |
所属機関(英) |
Tokyo University of Agriculture and Technology |
著者(和) |
藤吉邦洋 |
著者(ヨミ) |
フジヨシ クニヒロ |
著者(英) |
Kunihiro Fujiyoshi |
所属機関(和) |
東京農工大学 |
所属機関(英) |
Tokyo University of Agriculture and Technology |