| 講演名 | 2003/11/21 Selected Sequence-Pairを用いたレクトリニア多角形パッキングの高速化(VLSIの設計/検証/テスト及び一般 配置配線)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-) 池田 顕, 児玉 親亮, 中込 明広, 藤吉 邦洋, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | VLSIレイアウト設計の自動化では、過去に設計されたレイアウト資産を再利用するため、垂直また水平線分だけからなるレクトリニア多角形(多角形)形状のモジュールを扱えることが望まれる。本稿では、部分矩形集合に分けられた多角形の配置を矩形配置表現であるselected sequence-pair(SSP)により表し、SSPから部分矩形数(n)の線形時間で矩形パッキングを得る従来手法を用いることで、与えられたSSPに基づく多角形パッキングをO((p+1)n)時間で得る手法を提案する(pは単純な矩形を除く多角形の数)。そして計算機実験によりその有効性を示す。 |
| 抄録(英) | In this paper, we propose a method to represent rectilinear block packing based on a selected sequence-pair (SSP). SSP can represent an arbitrary rectangle packing and it is decodable in linear time of its size. Here, each rectilinear block is partitioned into rectangle sub-blocks. Also, we propose an algorithm to obtain a rectilinear block packing in O((p+1)n) time (n and p each is the number of rectangle sub-blocks and rectilinear blocks without simple rectangles) keeping all the constrains imposed by a given SSP. The proposed algorithm requires O(n) time if p is constant. The effectiveness of the proposed method was confirmed by the experimental comparison. |
| キーワード(和) | Sequence-pair / Selected Sequence-pair / レクトリニア多角形 / パッキング |
| キーワード(英) | Sequence-pair / Selected Sequence-pair / rectilinear block / packing |
| 資料番号 | VLD2003-103 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2003/11/21(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Selected Sequence-Pairを用いたレクトリニア多角形パッキングの高速化(VLSIの設計/検証/テスト及び一般 配置配線)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-) |
| サブタイトル（和） | |
| タイトル（英） | A Fast Algorithm for Rectilinear Block Packing Using SSP |
| サブタイトル（和） | |
| キーワード(1)（和/英） | Sequence-pair / Sequence-pair |
| キーワード(2)（和/英） | Selected Sequence-pair / Selected Sequence-pair |
| キーワード(3)（和/英） | レクトリニア多角形 / rectilinear block |
| キーワード(4)（和/英） | パッキング / packing |
| 第 1 著者 氏名（和/英） | 池田 顕 / Akira IKEDA |
| 第 1 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 第 2 著者 氏名（和/英） | 児玉 親亮 / Chikaaki KODAMA |
| 第 2 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 第 3 著者 氏名（和/英） | 中込 明広 / Akihiro NAKAGOMI |
| 第 3 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 第 4 著者 氏名（和/英） | 藤吉 邦洋 / Kunihiro FUJIYOSHI |
| 第 4 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 発表年月日 | 2003/11/21 |
| 資料番号 | VLD2003-103 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 476 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |