サイトトップ
訪問者数 827      最終更新 2013-02-19 (火) 16:15:44

並列処理 アルゴリズムの並列化と並列処理性能

アルゴリズムの並列化

単純なデータ並列(それぞれが独立に処理できるようなデータに対して、並列に処理する)は広く実用化されているが、そうではないタイプの並列に興味がある。

今まで考案されてきた様々なアルゴリズムは、殆どが直列実行を前提としていた
 ⇒ たとえばソーティングアルゴリズムについてKnuthのバイブルを見ても、N個のデータを2つずつ比較するのにその順番を工夫して数を減らすことが焦点と言ってもよかろう。
並列環境で考えられたアルゴリズムは少ない(知らないだけかもしれないが)
 ⇒ 例としてBatcherのソーティングアルゴリズム
データ依存性があって順序を制限されているアルゴリズムを何とか組み替えて、並列実行が可能なアルゴリズムにできないか?

(例1)DPマッチング

DPマッチングは、表形式に表したときに左上から右下へ計算する依存性があり、要素ごとの並列処理はできない。

(例2)遺伝的アルゴリズム(GA)

一般に、直前の状態を参考にして改善を繰り返す最適化手法では、各改善ステージは前のステージに依存性があるため、並列に実行できない。遺伝的アルゴリズム(GA)は同様の最適化手法ではあるが、同時にいくつかの改善手法を施してその結果からよいものを選ぶ方式のため、ステージでの並列実行の可能性がある。

(例3)リンクリスト処理

リンクリスト(linked list)自体は並列処理と相反するものでないが、たとえばOpenMPによるforループの自動並列化機能では並列化することができない。なぜなら、リストを用いる理由がデータの個数を実行中に(動的に)変えたいということにあり、forループ並列化で見られるような、繰り返しの回数があらかじめ決まっていて繰り返し部分を回数分並列実行する、というスキームが成り立たなくなるからである。
この対策として、繰り返し回数(や繰り返しの構造)があらかじめ決まっている場合に限定すれば、たとえループがOpenMPの自動並列化の枠組みに適合しなくても、並列化することができる。第1ステップとして、性的な繰り返しの場合に限定して並列化を試みる。

当然第2ステップとして、ループの繰り返しが動的(ループのある回の実行によってそれ以降の繰り返し数が変化する)であっても一定の制約を満たせば並列化できるであろう。それを考える。

その他の例

GPGPU(汎用グラフィックプロセッサ)上での並列処理

その他


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-02-19 (火) 16:15:44 (1587d)