| 講演名 | 2008-03-07 折れ曲がりと分岐を許容したバスドリブンフロアプラン設計手法の効率化(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般) 平良 洋祐, 藤吉 邦洋, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 集積回路のレイアウト設計でのバス配置を考慮したフロアプラン設計の問題において、ある一つのバスが実現できるか否かの判定は順列を増加列と減少列に分解する問題に定式化できることを見い出し、折れ曲がりと分岐が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. |
| キーワード(和) | sequence-pair / バスドリブン / フロアプラン設計 / 増加部分列 / 減少部分列 |
| キーワード(英) | sequence-pair / Bus-driven / floorplanning / increasing subsequence / decreasing subsequence |
| 資料番号 | CAS2007-132,SIP2007-207,CS2007-97 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CS |
|---|---|
| 開催期間 | 2008/2/29(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Communication Systems (CS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 折れ曲がりと分岐を許容したバスドリブンフロアプラン設計手法の効率化(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般) |
| サブタイトル（和） | |
| タイトル（英） | Improved Method of Bus Driven Floorplanning |
| サブタイトル（和） | |
| キーワード(1)（和/英） | sequence-pair / sequence-pair |
| キーワード(2)（和/英） | バスドリブン / Bus-driven |
| キーワード(3)（和/英） | フロアプラン設計 / floorplanning |
| キーワード(4)（和/英） | 増加部分列 / increasing subsequence |
| キーワード(5)（和/英） | 減少部分列 / decreasing subsequence |
| 第 1 著者 氏名（和/英） | 平良 洋祐 / Yosuke TAIRA |
| 第 1 著者 所属（和/英） | 東京農工大学工学府電気電子工学専攻 Tokyo University of Agriculture and Technology |
| 第 2 著者 氏名（和/英） | 藤吉 邦洋 / Kunihiro FUJIYOSHI |
| 第 2 著者 所属（和/英） | 東京農工大学工学府電気電子工学専攻 Tokyo University of Agriculture and Technology |
| 発表年月日 | 2008-03-07 |
| 資料番号 | CAS2007-132,SIP2007-207,CS2007-97 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 531 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |