講演名 | 1998/7/31 リソース制約付き回路分割問題に関する一考察 片渕 啓太郎, 泉 知諭, 高橋 篤司, 梶谷 洋司, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 本稿では, 多種多様な論理リソースを持つFPGAチップで回路を実現する際に必要とされる回路分割について考察を行う.様々な基本機能とそれを実現可能な論理リソースに関する制約, および同一分割内に割り当てられなければならない基本機能の集合に関する制約が与えられたとき, それらの制約を満足する分割が存在するか否かの判定問題はNP-完全であることを示す.また特定の場合について, この判定問題を解く多項式時間アルゴリズムを提案する. |
抄録(英) | In this paper, we consider the circuit partitioning for FPGAs with heterogeneous logic resources. For each basic function of a circuit, the set of resources of an FPGA in which the function can be realized is given. A composite function is a set of basic functions that should be assigned to the resources in a same part of FPGA resource partitioning. We show that the decision problem whether there is a partition of circuit functions that satisfies the above constraints is NP-Complete, and give a polynomial time algorithm for particular cases. |
キーワード(和) | FPGA / 回路分割 / リソース制約 / NP-完全 / アルゴリズム |
キーワード(英) | FPGA / Circuit Partitioning / Resources Constraints / NP-Complete / Algorithm |
資料番号 | VLD98-35 |
発行日 |
研究会情報 | |
研究会 | VLD |
---|---|
開催期間 | 1998/7/31(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | VLSI Design Technologies (VLD) |
---|---|
本文の言語 | JPN |
タイトル(和) | リソース制約付き回路分割問題に関する一考察 |
サブタイトル(和) | |
タイトル(英) | On the Circuit Partitioning for FPGAs with Heterogeneous Resources |
サブタイトル(和) | |
キーワード(1)(和/英) | FPGA / FPGA |
キーワード(2)(和/英) | 回路分割 / Circuit Partitioning |
キーワード(3)(和/英) | リソース制約 / Resources Constraints |
キーワード(4)(和/英) | NP-完全 / NP-Complete |
キーワード(5)(和/英) | アルゴリズム / Algorithm |
第 1 著者 氏名(和/英) | 片渕 啓太郎 / Keitaro Katabuchi |
第 1 著者 所属(和/英) | 東京工業大学大学院情報理工学研究科 Graduate School of Information Science and Engrg., Tokyo Inst. of Tech. |
第 2 著者 氏名(和/英) | 泉 知諭 / Tomonori Izumi |
第 2 著者 所属(和/英) | 京都大学大学院情報学研究科 Dept. of Communications and Computer Engrg., Graduate School of Informatics. Kyoto University |
第 3 著者 氏名(和/英) | 高橋 篤司 / Atsushi Takahashi |
第 3 著者 所属(和/英) | 東京工業大学工学部電気電子工学科 Dept. of Electrical and Electronic Engrg., Tokyo Inst. of Tech. |
第 4 著者 氏名(和/英) | 梶谷 洋司 / Yoji Kajitani |
第 4 著者 所属(和/英) | 東京工業大学工学部電気電子工学科 Dept. of electrical and Electronic Engrg., Tokyo Inst. of Tech. |
発表年月日 | 1998/7/31 |
資料番号 | VLD98-35 |
巻番号(vol) | vol.98 |
号番号(no) | 232 |
ページ範囲 | pp.- |
ページ数 | 6 |
発行日 |