部分一致を含む文字列に対する探索のAVXによる高スループット化
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,多数の部分一致を含む文字列に対する高速な探索の実現を目的として,ベクトル命令 AVX (Advanced Vector Extensions) によるビット並列アルゴリズムの高スループット化手法を提案する.ビット並列アルゴリズムの特長は,部分一致する箇所の数や長さに実行時間が依存しないことである.提案手法は,探索の高スループット化を図るために,長さの異なる複数のパターンを同時に探索できるよう,ビット並列アルゴリズムを拡張する.具体的には,AVX 命令により CPU コアあたりの探索スループットを高め,OpenMP 指示文によるデータ並列処理を実現する.また,データ構造を工夫することにより,長さの異なる複数のパターンを効率よく同時に処理する.実験の結果,データ構造の工夫により探索スループットをおよそ 2 倍に向上できた.また,ゲノムデータのように多数の部分一致を含み,大きなテキストに対して提案手法が有用であることが分かった.
- 2014-02-24
著者
関連論文
- CUDAによる高速なコーンビーム再構成の実装と性能評価(プログラミング環境,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- D-11-80 GPUによるTotal Variation Minimization法の高速化(D-11.画像工学,一般セッション)
- GPUグリッドにおいて描画および科学計算を並行処理するための制御手法(カーネル)
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(夏のデータベースワークショップ2007(データ工学,一般))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(検索エンジン応用,夏のデータベースワークショップ2007(データ工学,一般))
- Webを対象としたロボット型住所関連情報検索システムの開発(Web検索,データ工学論文)
- GPUによるOSEM再構成の高速化及び精度評価(医用システム,システム開発論文)
- 大規模データセットを可視化するための効率の良い並列ボリュームレンダリング(並列処理応用)
- 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案
- GPUによるOSEM再構成の高速化および精度評価(基盤技術1)
- R3Qによる進化型計算の中粒度Gridスケジューリング(グリッド)
- 時系列ボリュームレンダリングの描画速度を調節するための非可逆圧縮手法
- GPUを用いたコーンビーム再構成の性能評価と精度検証(画像再構成)
- 複数のCUDA互換GPUによるストリーム処理のためのミドルウェア
- CUDAカーネルの性能を解析するための実行履歴生成ツール
- CUDAプログラムにおいてストリーム処理を支援するミドルウェア
- GPUクラスタによる高速なアミノ酸配列データベース検索
- CUDAによるパラメータ・スイープアプリケーションの高速化
- CUDAを用いた高速なモルフォロジー演算
- CUDAによる全点対最短経路問題の高速化(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- 統合開発環境CUDAを用いたGPUでの配列アライメントの高速化手法(メモリアクセス,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- CUDAによる全点対最短経路問題の高速化(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- CUDAによる高速なコーンビーム再構成の実装と性能評価(プログラミング環境,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- 統合開発環境CUDAを用いたGPUでの配列アライメントの高速化手法(メモリアクセス,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- GPU上での高速なブロック化フロイド・ワーシャル法
- 複数の並列計算環境に対応したMapReduceのPythonによる実装
- 術中における対話的な医用画像処理のための遠隔並列計算環境の構築 : 手術支援グリッドの実現に向けて
- 術中二次元/三次元剛体位置合せのための並列化手法(ディペンダブルコンピューティング)
- GPUを用いてコーンビームCTのボリューム再構成を高速化する手法(一般セッション,センシング技術とその応用)
- GPU内部におけるプロセッサ間の命令移動による高速化ツール
- GPUアプリケーションを高速化するための命令割当て方式(GPU応用)
- デスクトップ・ボリュームレンダリングのための解像度制御によるビデオメモリ使用量削減(ハードウエアによるCG処理およびCG一般)
- 並列再帰の実行方式をプログラマが指定可能なコンパイラの評価
- ベイジアンネットワークモデルを用いた衣服コーディネイト推薦システムの開発
- ベイジアンネットワークモデルを用いた衣服コーディネイト推薦システムの開発
- 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案
- デスクトップグリッド環境でのマルチジョブスケジューリングにおけるジョブの追い越しを防ぐジョブ優先度制御
- WWW画像検索における画像周辺のHTML構文構造を考慮した画像説明文の抽出手法(データ工学, ディペンダビリティ, 一般)
- WWW画像検索における画像周辺のHTML構文構造を考慮した画像説明文の抽出手法(データ工学, ディペンダビリティ, 一般)
- ウェブマルチメディア検索のためのパーソナルシステム(データ可視化, 夏のデータベースワークショップDBWS2005)
- ウェブマルチメディア検索のためのパーソナルシステム(データ可視化, 夏のデータベースワークショップ2005)
- グリッド上でのパラメータ・スウィープ計算を対象として消費余剰計算力の最小化をねらった動的タスクスケジューリングのための近似アルゴリズム(シンポジウム)
- PCクラスタを用いた並列非剛体位置合わせ手法の性能評価(可視化・レジストレーション)
- タスク複製率とプロセッサ***率に着目したBSPスケジュール生成手法の提案
- グリッド環境において計算結果を効率よく再利用するための通信量削減(HPC-2 : 通信方式)
- D-16-7 GPUを用いた逐次近似法によるコーンビーム再構成の高速化(D-16.医用画像,一般セッション)
- GPUを用いたアウトオブコアなコーンビーム再構成の高速化
- 検索可能な樹状ヒストリ機能を備えたホワイトボードシステム"S.W.ボード"の提案と実装
- 会合における備忘録をもとに一次記録を検索参照する会合情報記録検索システムReSPoM(:知識と情報の共有)
- 検索可能な樹状ヒストリ機能を備えたホワイトボ-ドシステム"S.W.ボ-ド"の提案と実装
- 会合記録の関連性に着目した会合記録検索支援システムの実装
- 会合における情報の関連性を記録するためのインタフェースの検討と評価
- 会合における情報の関連性を記録するためのインタフェースの検討と評価
- スケール不変な格子を生成する適応格子細分化法アプリケーションのための計算量予測手法(アルゴリズム理論)
- グリッドアプリケーションの実行時間を短縮するための計算結果再利用機構の評価
- 適応格子細分化法を用いる画像処理のための実行時間予測手法(ポスターセッション)
- 汎用グラフィクスハードウェアを用いた2次元/3次元剛体位置合わせの高速化(コンピュータグラフィックス)
- 汎用グラフィクスハードウェアを用いた2方向投影による2次元/3次元剛体位置合わせ(再構成他, 医用画像一般)
- 汎用グラフィクスハードウェアを用いた2次元/3次元剛体位置合わせの高速化(HPCシステム)
- フラクタル解析による適合格子細分化法の計算量予測
- 短時間処理向け資源管理を実現するためのGlobus Toolkitの性能評価(グリッド(2), 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- PCクラスタを用いた2次元/3次元剛体位置合わせの高速処理(レジストレーション・イメージマッチング)(関連学会との共催によるバイオメディカルイメージング連合フォーラム)
- MI-Cluster : 術中医用画像処理を実現するPCクラスタシステム
- 手術ロボットのための医用画像処理技術 : 最近の進展と将来の方向 : 日本学術振興会未来開拓学術推進事業「術中における多次元画像の獲得と利用」の成果を中心として
- GPUによる高速なコーンビーム再構成:円軌道装置のためのRGBAデータへの詰め込み
- GPUを用いてコーンビームCTのボリューム再構成を高速化する手法(一般セッション,センシング技術とその応用)
- B-007 実時間グリッド計算のための資源割当システムの設計(B.ソフトウェア)
- 分散メモリ型並列計算機を用いた非剛体レジストレーションの並列化
- プロセッサグループの動的分割による並列再帰プログラムの実現手法
- 並列型画像処理ライブラリの高効率化(JAMITセッション)
- 3次元並列型画像処理ライブラリ開発における基礎的検討(再構成他, 医用画像一般)
- アニメーションを用いた並列アルゴリズム学習支援環境の構築
- メッセージ通信並列プログラムの性能改善可能性を評価するための実行履歴の削減(コンピュータシステム)
- GPGPUアプリケーションの開発を支援するための性能モデル(GPU応用)
- スケーラビリティのあるWWW並列全文検索システム構築法の提案と評価
- スケーラビリティを考慮した並列再帰の実行方式の提案と評価
- プログラマブルGPUにおけるLU分解の設計と実装(GPU応用)
- D-11-90 大規模なマルチスケールボリュームレンダリングのための先読み手法の検討(D-11.画像工学D(画像処理・計測),一般講演)
- 計算グリッド上でのパラメータ・スウィープ計算を対象とした性能保証のある動的タスクスケジューリング
- 通信遅延を考慮した完全k分木の近似タスクスケジューリングアルゴリズム
- 通信遅延を考慮した完全k分木の近似タスクスケジューリングアルゴリズム
- 通信の一括化に適したタスクスケジューリングアルゴリズム
- 分散メモリ型並列計算機の通信特性を考慮したスケジューリングアルゴリズムの開発とその評価
- GPUを装備する計算機を計算資源とするグリッドにおける資源選択手法の検討
- メッセージ通信プログラムにおける性能解析のための大規模な実行履歴の生成(システム性能評価)
- 時系列ボリュームを高速レンダリングするための2段階データ圧縮方法の性能および画質評価(可視化の高速化, テーマ: 可視化のためのCGおよびCG一般)
- MPIプログラムにおける大規模な実行履歴生成の検討(アプリケーションとその並列化)
- (83)通常講義の中でのPBL演習の試み(第21セッション 創成教育(I))
- ボリュームレンダリングにおける効率的なテクスチャ参照
- インタプリタ型汎用生体シミュレータinsilicoSimのGPUによる高速化
- 系列パターン抽出のMapReduce実装におけるタスク分割方式の検討
- JPEGアルゴリズムにブロック比較法を適用した画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- 進化戦略のためのグリッド計算に関する一考察(進化・学習とロボティクス3)
- 共有した電子ノートにおけるビデオシーンの注目度を利用する学習支援システム
- 累積不透明度の伝搬による並列ボリュームレンダリングの計算量削減(2003年並列/分散/協調処理に関する「松江」サマーワークショップ(SWoPP松江2003))(CPSY-6並列分散ソフトウェア)