大規模グラフの最大クリーク問題に対する部分再構成可能FPGAを用いたハードウェア解法(リコンフィギャラブル応用,デザインガイア2012-VLSI設計の新しい大地-)
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,大規模グラフに対する最大クリークを求めるハードウェア解法を提案し,提案解法を部分再構成可能FPGA上に実装した結果を報告する.提案解法は,従来手法では1つのFPGAで解くことができない大規模グラフに対しても,部分グラフを複数生成し,FPGAの部分再構成機能を用いることにより,1つのFPGAで解を得ることができる.提案するハードウェアアルゴリズムは分枝限定法に基づいているため,解空間を効率良く探索できるだけでなく,FPGAの部分再構成回数も削減することができる.提案手法を部分再構成機能を用いてFPGA上に実装し,既存手法では得られなかった大規模グラフに対する解か高速に得られることを確認した.
- 一般社団法人電子情報通信学会の論文
- 2012-11-20
著者
-
稲木 雅人
東京工業大学理工学研究科集積システム専攻
-
若林 真一
広島市立大学大学院情報科学研究科
-
永山 忍
広島市立大学大学院 情報科学研究科 情報工学専攻
-
稲木 雅人
広島市立大学大学院 情報科学研究科
-
三浦 智香子
広島市立大学大学院情報科学研究科
-
若林 真一
広島市立大学大学院 情報科学研究科
-
永山 忍
広島市立大学大学院 情報科学研究科
関連論文
- 時間多重I/Oを考慮した回路分割手法(FPGA実装設計,FPGA応用及び一般)
- マルチFPGA実装における時間多重化I/O割り当て最適化手法(信号処理,LSI,及び一般)
- ポテンシャル法を用いたBGA配線手法(配置配線,システムオンシリコン設計技術並びにこれを活用したVLSI)
- ピン集合間の引き出し順を考慮した配線手法(配置配線,システムオンシリコン設計技術並びにこれを活用したVLSI)
- 時間多重化I/Oを用いたマルチFPGAシステムのための回路分割アルゴリズム
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア (リコンフィギャラブルシステム)
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア (VLSI設計技術)
- パターン非依存型正規表現ストリングマッチングマシンとそのFPGA実装(応用技術,リコンフィギャラブルシステムとその応用論文)
- 3L-1 マルチスレッディングに基づく並列フロアプランニング手法の開発と評価(論理・物理設計技術,学生セッション,アーキテクチャ)
- 2L-5 FPGA実装に適した離散データの多項式近似法(上流設計技術,学生セッション,アーキテクチャ)
- 4K-6 Snortルールを入力とするネットワーク侵入検知ハードウェアの開発(HPCと高速化,学生セッション,アーキテクチャ)
- AP-1-2 並列メタヒューリスティクスとLSI CADへの応用(AP-1.回路とシステム領域におけるメニコア計算機の活用,パネルセッション,ソサイエティ企画)
- NIDS専用正規表現マッチングマシンの構成とそのFPGA実装(アプリケーション2,FPGA応用及び一般)
- パターンを実行時に設定可能な正規表現ストリングマッチングマシンとFPGAによる実現(FPGAの応用)
- 2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法(FPGAの応用)
- 配線長を考慮したクラスタリングに基づくスタンダードセル階層配置手法(VLSIの設計/検証/テスト及び一般配置配線)
- 配線長を考慮したクラスタリングに基づくスタンダードセル階層配置手法(VLSIの設計/検証/テスト及び一般 配置配線)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- 配線長を考慮したクラスタリングに基づくスタンダードセル階層配置手法
- 匿名データ収集におけるプロトコルからの逸脱防止法の効率化 (データ工学)
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア(アプリケーション2,FPGA応用及び一般)
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア(アプリケーション2,FPGA応用及び一般)
- 論理・配線資源を共用するMPLDのためのセルの過剰接近を抑えるレイアウト手法(ツール)
- 時間多重I/Oを考慮した回路分割手法(FPGA実装設計,FPGA応用及び一般)
- 時間多重I/Oを考慮した回路分割手法(FPGA実装設計,FPGA応用及び一般)
- 時間多重I/Oを考慮した回路分割手法(FPGA実装設計,FPGA応用及び一般)
- 信号経路に対するタイミング制約を考慮した回路分割手法
- タイミング制約を考慮した分割手法
- MPLDアーキテクチャのための配置配線支援ツール(ツール)
- RC-003 高速なテキスト検索のための近似正規表現マッチングアルゴリズムとそのFPGA実装(C分野:ハードウェア・アーキテクチャ,査読付き論文)
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア(アプリケーション2,FPGA応用及び一般)
- 非公開データベース間における機密性の高い情報共有の検討
- NIDS専用正規表現マッチングマシンの構成とそのFPGA実装(アプリケーション2,FPGA応用及び一般)
- NIDS専用正規表現マッチングマシンの構成とそのFPGA実装(アプリケーション2,FPGA応用及び一般)
- NIDS専用正規表現マッチングマシンの構成とそのFPGA実装(アプリケーション2,FPGA応用及び一般)
- パターンを実行時に設定可能な正規表現ストリングマッチングマシンとFPGAによる実現(FPGAの応用)
- 2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法(FPGAの応用)
- パターンを実行時に設定可能な正規表現ストリングマッチングマシンとFPGAによる実現(FPGAの応用)
- 2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法(FPGAの応用)
- コールアドミッションアルゴリズムに適した経路探索法の提案
- A-1-30 コールアドミッションに適した効率的な経路探索法の提案(A-1.回路とシステム,一般講演)
- クラスタリング結果の特徴抽出を用いる高次元データの対話的クラスタリング
- FlexDice: 高次元な大規模データセットに対する高速クラスタリング手法
- 多次元データ空間に対する高速クラスタリングと実験的評価
- 大規模論理回路分割に関する一手法
- 大規模論理回路分割に関する一手法
- システムオンシリコン時代を支えるCAD技術(新しい知能化へ向けたLSIシステム技術)
- パターンを実行時に設定可能な正規表現ストリングマッチングマシンとFPGAによる実現(FPGAの応用)
- ポテンシャル法を用いたBGA配線手法(配置配線,システムオンシリコン設計技術並びにこれを活用したVLSI)
- ピン集合間の引き出し順を考慮した配線手法(配置配線,システムオンシリコン設計技術並びにこれを活用したVLSI)
- 最小支配集合問題に対する分枝限定アルゴリズムとFPGA上でのハードウェアによる実現(グラフ, ペトリ, ニューラルネット及び一般)
- 最小支配集合問題に対する分枝限定アルゴリズムとFPGA上でのハードウェアによる実現(グラフ, ペトリ, ニューラルネット及び一般)
- A-3-1 近接度に着目した入出力ピン配置アルゴリズム
- 回路遅延を考慮した最小カット法に基づく回路分割アルゴリズム
- 回路遅延を考慮した最小カット法に基づく回路分割アルゴリズム
- 共有変数へのアクセス競合の回避を目的とする同時実行可能で拡張可能なハッシュアルゴリズムの改良
- タイミングを考慮したフロアプランニングと動作合成の統合化の一手法
- タイミングを考慮したフロアプランニングと動作合成の統合化の一手法
- マルチFPGA実装における時間多重化I/O割り当て最適化手法(信号処理,LSI,及び一般)
- マルチFPGA実装における時間多重化I/O割り当て最適化手法(信号処理,LSI,及び一般)
- 交差手法の適応的選択機能を組み込んだ遺伝的アルゴリズムのLSIチップによる実現
- 遺伝的アルゴリズムにおける個体のエリート度に基づく遺伝オペレータとGAパラメータの適応的調整
- 遺伝的アルゴリズムにおける交差手法の適応的選択の一手法
- 適応的交差選択手法を組み込んだ遺伝的アルゴリズムのLSIチップによる実現とその評価
- 個体の優劣度に基づいて適応的にパラメータを調整する遺伝的アルゴリズム
- 遺伝的アルゴリズムにおける個体の優劣度に基づく適応的パラメータ値設定手法
- パラメータの適応的調整を伴う遺伝的アルゴリズムのハードウェア化
- スタイナ木生成問題に対する遺伝的アルゴリズムを統合的に開発するフレームワーク
- スタイナ木生成問題に対する遺伝的アルゴリズムを統合的に開発するフレームワーク
- 近似正規表現マッチングのためのシストリックアルゴリズムとそのFPGA実装
- 2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法(FPGAの応用)
- 2次割当問題に対するタブー探索法に基づくFPGAを用いたハードウェア解法(FPGAとその応用及び一般)
- LSIフロアプランニングに対する遺伝的アルゴリズムとタブー探索に基づく並列アルゴリズムとそのPCクラスタ上での実現(FPGAとその応用及び一般)
- 2次割当問題に対するタブー探索法に基づくFPGAを用いたハードウェア解法(FPGAとその応用及び一般)
- LSIフロアプランニングに対する遺伝的アルゴリズムとタブー探索に基づく並列アルゴリズムとそのPCクラスタ上での実現(FPGAとその応用及び一般)
- 2次割当問題に対するタブー探索法に基づくFPGAを用いたハードウェア解法(FPGAとその応用及び一般)
- LSIフロアプランニングに対する遺伝的アルゴリズムとタブー探索に基づく並列アルゴリズムとそのPCクラスタ上での実現(FPGAとその応用及び一般)
- 2次割当問題に対するタブー探索法に基づくFPGAを用いたハードウェア解法(FPGAとその応用及び一般)
- LSIフロアプランニングに対する遺伝的アルゴリズムとタブー探索に基づく並列アルゴリズムとそのPCクラスタ上での実現(FPGAとその応用及び一般)
- LSIフロアプランニングに対する遺伝的アルゴリズムとタブー探索に基づく並列アルゴリズムとそのPCクラスタ上での実現
- LSIフロアプランニングに対する遺伝的アルゴリズムとタブー探索に基づく並列アルゴリズムとそのPCクラスタ上での実現
- C_006 2次割当問題に対するタブー探索法に基づくハードウェア解法(C分野:ハードウェア)
- タイミング制約を伴う概略配線問題に対するバッファ挿入と配線幅の選択を許したスタイナ木構成手法
- タイミング制約を考慮した概略配線手法
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア
- LC-002 最小支配集合問題を解くインスタンス依存ハードウェア解法(C分野:アーキテクチャ・ハードウェア)
- グラフ最小節点被覆問題に対するFPGAを用いたインスタンス依存ハードウェア解法(応用1, FRGAとその応用及び一般)
- グラフ最小節点被覆問題に対するFPGAを用いたインスタンス依存ハードウェア解法(応用1, FRGAとその応用及び一般)
- 再構成可能デバイスMPLD^の配置設計におけるネット単位ムーブ手法の検討と評価(再構成回路,物理設計及び一般)
- パターン非依存正規表現マッチングエンジンに対する先読み演算の実現(回路/システム設計,システムオンシリコンを支える設計技術)
- 近似正規表現マッチングアルゴリズムのGPGPU実装およびFPGA実装と比較(再構成回路,システムオンシリコンを支える設計技術)
- RC-006 ネットワーク侵入検知のためのパターン非依存NFAとシストリックアルゴリズムを組み合わせた正規表現マッチングエンジン(リコンフィギャラブルシステムと応用,C分野:ハードウェア・アーキテクチャ)
- プログラマブル論理デバイスを対象とした配置配線問題の整数計画法に基づく定式化(最適化,デザインガイア2012-VLSI設計の新しい大地-)
- プログラマブル論理デバイスを対象とした配置配線問題の整数計画法に基づく定式化(最適化,デザインガイア2012-VLSI設計の新しい大地-)
- 大規模グラフの最大クリーク問題に対する部分再構成可能FPGAを用いたハードウェア解法(リコンフィギャラブル応用,デザインガイア2012-VLSI設計の新しい大地-)
- シストリックアルゴリズムとNFAに基づくパターン非依存正規表現マッチングハードウェア(計算機システム,システム開発論文)
- 再構成可能デバイスMPLDのアーキテクチャ評価(FPGAアーキテクチャー, FPGA応用及び一般)
- 再構成可能デバイスMPLDのアーキテクチャ評価(FPGAアーキテクチャー, FPGA応用及び一般)
- 再構成可能デバイスMPLDのアーキテクチャ評価(FPGAアーキテクチャー, FPGA応用及び一般)
- マルチコアプロセッサのための配線領域共有並列概略配線手法(配線設計,システムオンシリコンを支える設計技術)