| 講演名 | 2000/11/23 関数分解を用いたLUT型FPGA用ブーリアンマッチングアルゴリズムについて 松永 裕介, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿ではXilinx社のXC4000シリーズの様に複数のLUTから構成された回路を基本ブロックとするFPGA用のブーリアンマッチングアルゴリズムについて述べる.このアルゴリズムは, 二分決定グラフを用いた高速な単純な直交分解アルゴリズムを応用したもので, マッチングパタンが直交分解の形をしている場合には直接, 適用し, 直交分解でない場合には, 直交するように重複した変数でコファクタリングしてから直交分解を行なうものである.XC4000シリーズの場合, コファクタリングを試すための変数の選択方法は高々30通りであり, 全ての変数分割を列挙して分解が存在するか調べるCongとHwangのアルゴリズムと比べて極めて効率的である. |
| 抄録(英) | This paper describes on Boolean matching algorithm for FPGA's whose basic block consists of LUT's like Xilinx XC4000. The proposed algorithm is based on an efficient implementation of simple disjunctive decomposition algorithm using binary decision diagrams. In the case that the pattern to be matched can be decomposed disjunctively, the decomposition algorithm is applied directly. Otherwise, the subject function is cofactered until the cofactored functions have disjunctive decompositions. The number of choices of variables for cofactoring is no more than 30 in the case of XC4000. Comparing with the algorithm proposed by Cong and Hwang, which enumerates all the variable splitting in order to check if a decomposition exists, the proposed algorithm is very efficient. |
| キーワード(和) | 論理合成 / 関数分解 / 二分決定グラフ / FPGA / テクノロジマッピング |
| キーワード(英) | logic synthesis / functional decomposition / binary decision diagrams / FPGA / technology mapping |
| 資料番号 | VLD2000-96,ICD2000-153,FTS2000-61 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2000/11/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 関数分解を用いたLUT型FPGA用ブーリアンマッチングアルゴリズムについて |
| サブタイトル（和） | |
| タイトル（英） | On Boolean Matching Algorithm for LUT-type FPGA Using Functional Decomposition |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 論理合成 / logic synthesis |
| キーワード(2)（和/英） | 関数分解 / functional decomposition |
| キーワード(3)（和/英） | 二分決定グラフ / binary decision diagrams |
| キーワード(4)（和/英） | FPGA / FPGA |
| キーワード(5)（和/英） | テクノロジマッピング / technology mapping |
| 第 1 著者 氏名（和/英） | 松永 裕介 / Yusuke Matsunaga |
| 第 1 著者 所属（和/英） | (株)富士通研究所 Fujitsu Laboratories LTD. |
| 発表年月日 | 2000/11/23 |
| 資料番号 | VLD2000-96,ICD2000-153,FTS2000-61 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 473 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |