| 講演名 | 2007-11-22 O-Treeを拡張したレクトリニア多角形パッキングの高速化(論理・レイアウト最適化,デザインガイア2007-VLSI設計の新しい大地を考える研究会-) 浮邉 英彦, 藤吉 邦洋, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | レイアウトの再利用のため、レクトリニア多角形をパッキングできることが望まれている。そこで、矩形だけのパッキングを効率よく表現するO-Treeの制約を拡張することで、レクトリニア多角形パッキングを表現する方法が提案され、その拡張された制約に基づいたO-Treeから、部分矩形数をn、単純な矩形を含む多角形数をmとして、O(nm)時間でレクトリニア多角形パッキングを得るデコード手法が提案された。本稿ではこのデコード手法を改良し、部分矩形数をn、凹多角形数をcとして、計算複雑度をO(n(c+1))に高速化したデコード手法を提案する。そして計算機実験により、その有効性を示す。 |
| 抄録(英) | In this paper, we propose an improved method to represent rectilinear block packing based on an expanded O-Tree. Here, each rectilinear block is partitioned into rectangle sub-blocks. Also, we propose a decode algorithm to obtain a rectilinear block packing in O((c+1)n) time, where n and c each is the number of rectangle sub-blocks and concave blocks. The proposed algorithm requires O(n) time if c is constant. The effectiveness of the proposed method was confirmed by the experimental comparison. |
| キーワード(和) | O-Tree / レクトリニア多角形 / パッキング / 凸多角形 / 凹多角形 |
| キーワード(英) | O-Tree / rectilinear block / packing / convex block / concave block |
| 資料番号 | VLD2007-96,DC2007-51 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2007/11/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | O-Treeを拡張したレクトリニア多角形パッキングの高速化(論理・レイアウト最適化,デザインガイア2007-VLSI設計の新しい大地を考える研究会-) |
| サブタイトル（和） | |
| タイトル（英） | Improved Method of Rectilinear Block Packing Based on O-Tree Representation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | O-Tree / O-Tree |
| キーワード(2)（和/英） | レクトリニア多角形 / rectilinear block |
| キーワード(3)（和/英） | パッキング / packing |
| キーワード(4)（和/英） | 凸多角形 / convex block |
| キーワード(5)（和/英） | 凹多角形 / concave block |
| 第 1 著者 氏名（和/英） | 浮邉 英彦 / Hidehiko UKIBE |
| 第 1 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 第 2 著者 氏名（和/英） | 藤吉 邦洋 / Kunihiro FUJIYOSHI |
| 第 2 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 発表年月日 | 2007-11-22 |
| 資料番号 | VLD2007-96,DC2007-51 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 336 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |