分割統治法アルゴリズムの効率的な並列化手法とそのコンパイラの実装
スポンサーリンク
概要
- 論文の詳細を見る
並列再帰呼出を用いた分割統治法アルゴリズムを並列計算機上で実行する場合, そのアルゴリズムの動きや計算量, 計算機の通信性能などにより, 性能が大きく左右される.このため全ての分割統治法アルゴリズムに対してただ1つの並列実行方式を適用しても十分な性能は得られない.その一方で, それぞれの分割統治法アルゴリズムのソースコード記述から, コンパイラがアルゴリズムの特徴を機械的に解析するのは極めて困難である.本稿では, 各アルゴリズムの適切な並列実行に必要な情報をプログラマが明示的に指定することによりコンパイラに効率良い並列プログラムを生成させる手法を提案する.そして, 特徴の異なる分割統治法アルゴリズムを提案手法に基づいて実際にコンパイルし, 生成された並列プログラムの性能を測定した結果を示す.
- 一般社団法人情報処理学会の論文
- 2000-01-17
著者
-
中島 大輔
マイクロソフトプロダクトディベロップメントリミテッドインプットメソッドテクノロジー開発統括部
-
藤本 典幸
大阪大学大学院情報科学研究科
-
藤本 典幸
大阪府立大学 大学院 理学系研究科
-
中島 大輔
大阪大学 大学院基礎工学研究科 情報数理系専攻
-
藤本 典幸
大阪大学 大学院基礎工学研究科 情報数理系専攻
-
萩原 兼一
大阪大学 大学院基礎工学研究科
関連論文
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(夏のデータベースワークショップ2007(データ工学,一般))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(検索エンジン応用,夏のデータベースワークショップ2007(データ工学,一般))
- Webを対象としたロボット型住所関連情報検索システムの開発(Web検索,データ工学論文)
- 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案
- R3Qによる進化型計算の中粒度Gridスケジューリング(グリッド)
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- 術中における対話的な医用画像処理のための遠隔並列計算環境の構築 : 手術支援グリッドの実現に向けて
- 進化計算のためのグリッドコンピューティング
- 並列再帰の実行方式をプログラマが指定可能なコンパイラの評価
- 分割統治法アルゴリズムの効率的な並列化手法とそのコンパイラの実装
- 分割統治法プログラムを並列実行するコンパイル手法の提案と評価
- λコンピューティング環境におけるOpenMPアプリケーションによる共有メモリシステムの評価
- λコンピューティング環境におけるOpenMPライブラリの設計と実装(フォトニックネットワークシステム,光ルーチング,ブロードバンドアプリケーション,一般)
- ベイジアンネットワークモデルを用いた衣服コーディネイト推薦システムの開発
- ベイジアンネットワークモデルを用いた衣服コーディネイト推薦システムの開発
- 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案
- デスクトップグリッド環境におけるタスクスケジューリングアルゴリズムRR理論の実証と進化戦略の同期待ち時間削減について
- デスクトップグリッド環境でのマルチジョブスケジューリングにおけるジョブの追い越しを防ぐジョブ優先度制御
- 余剰計算力を用いるグリッドのジョブスケジューリングにおける優先度制御の一手法(セッション2)
- A_002 企業イントラグリッドでのジョブ割当てアルゴリズムの比較評価(A分野:モデル・アルゴリズム・プログラミング)
- WWW画像検索における画像周辺のHTML構文構造を考慮した画像説明文の抽出手法(データ工学, ディペンダビリティ, 一般)
- WWW画像検索における画像周辺のHTML構文構造を考慮した画像説明文の抽出手法(データ工学, ディペンダビリティ, 一般)
- ウェブマルチメディア検索のためのパーソナルシステム(データ可視化, 夏のデータベースワークショップDBWS2005)
- ウェブマルチメディア検索のためのパーソナルシステム(データ可視化, 夏のデータベースワークショップ2005)
- グリッド上でのパラメータ・スウィープ計算を対象として消費余剰計算力の最小化をねらった動的タスクスケジューリングのための近似アルゴリズム(シンポジウム)
- タスクスケジューリングを用いた並列プログラム生成におけるタスク粒度の調整とその評価
- タスク複製率とプロセッサ***率に着目したBSPスケジュール生成手法の提案
- 検索可能な樹状ヒストリ機能を備えたホワイトボードシステム"S.W.ボード"の提案と実装
- 会合における備忘録をもとに一次記録を検索参照する会合情報記録検索システムReSPoM(:知識と情報の共有)
- 検索可能な樹状ヒストリ機能を備えたホワイトボ-ドシステム"S.W.ボ-ド"の提案と実装
- 会合記録の関連性に着目した会合記録検索支援システムの実装
- 会合における情報の関連性を記録するためのインタフェースの検討と評価
- 会合における情報の関連性を記録するためのインタフェースの検討と評価
- MI-Cluster : 術中医用画像処理を実現するPCクラスタシステム
- 共有メモリ式SIMD型並列アルゴリズム解析ツール
- プロセッサグループの動的分割による並列再帰プログラムの実現手法
- アニメーションを用いた並列アルゴリズム学習支援環境の構築
- スケーラビリティのあるWWW並列全文検索システム構築法の提案と評価
- 並列型全文検索システム構築のための手法の提案とその評価
- スケーラビリティを考慮した並列再帰の実行方式の提案と評価
- 計算グリッド上でのパラメータ・スウィープ計算を対象とした性能保証のある動的タスクスケジューリング
- 通信遅延を考慮した完全k分木の近似タスクスケジューリングアルゴリズム
- 通信遅延を考慮した完全k分木の近似タスクスケジューリングアルゴリズム
- 通信の一括化に適したタスクスケジューリングアルゴリズム
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリングアルゴリズム
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリング手法
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリング手法
- 分散メモリ型並列計算機の通信特性を考慮したスケジューリングアルゴリズムの開発とその評価
- JPEGアルゴリズムにブロック比較法を適用した画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- 進化戦略のためのグリッド計算に関する一考察(進化・学習とロボティクス3)
- 分散メモリ型並列計算機による高解像度ボリュームレンダリング(バイオメトリクスシステムおよび一般)
- グリッド環境における独立粗粒度タスク集合の動的スケジューリングアルゴリズムの性能評価
- タスクグラフ分割を用いた並列処理によるスケジューリングアルゴリズムBCSHの大規模細粒度グラフへの適用
- ビデオアーカイブを利用した学習を支援するシステムの提案
- ビデオアーカイブを利用した学習を支援するシステムの提案
- SPMD プログラムを生成する Work-Time C 処理系の実現
- 並列プログラムの性能改善支援機能を持つ性能解析システム : Gordini(並列処理)
- 並列プログラムの改善支援機能を持つ性能解析システムの開発
- 1対1プロセッサ間通信の一括化を考慮したタスクスケジューリングアルゴリズム
- 一対一プロセッサ間通信の一括化を考慮したタスクスケジューリングアルゴリズム
- 最小値関数を用いて適合度を算出するNRA検索アルゴリズムの改善
- 最小値関数により適合度を算出するNRA検索アルゴリズムの改善
- グリッド環境における計算ノードの故障を考慮した独立タスクのスケジューリングアルゴリズム
- MPI-PreDebugger : 通信依存解析に基づくメッセージ通信並列プログラム向けデバッグ支援ツール
- LogGPS : メッセージ通信プロトコルの切替えを考慮した高水準通信ライブラリ向けの並列計算モデル
- 平衡2分探索木に対する並列オンライン操作
- D-6-6 並列生体シミュレータinsilicoSimにおけるエージェント割当手法(D-6.コンピュータシステムA(アーキテクチャ),一般セッション)
- パイプライン化による平衡2分探索木に対する並列操作