並行コンピューティング技法2章

Shinichi Tokunaga @deepneko

タスク分解では粒度(タスクの処理量)に注目したと思うけど、それとは別にデータ分解ではチャンクの形状に注意しなければいけない。

Shinichi Tokunaga @deepneko

1要素ごとに分割、行で分割、列で分割、ブロックで分割。

Shinichi Tokunaga @deepneko

何を気にしてるかっていうと、チャンク同士の境界面が多いか少ないか。データ更新が起きるとチャンク同士でデータ交換を行うことがあるから、境界面は少ないほうがオーバーヘッドは少ない。

Shinichi Tokunaga @deepneko

隣接したチャンク間でデータを交換するには2つの方法がとりあえず思いつく。

Shinichi Tokunaga @deepneko

タスク(スレッド)専用の領域にデータをコピーしておくか、必要になった時点で隣接チャンクへアクセスするか。

Shinichi Tokunaga @deepneko

データのコピーで不利な点はタスクそれぞれに追加のローカルメモリ(ゴーストセル)が必要になること。

Shinichi Tokunaga @deepneko

もちろんコピー回数が増えたり、コピーするデータ量が増えるとオーバーヘッドが増えます。

Shinichi Tokunaga @deepneko

必要に応じて隣接チャンクにアクセスする方式は、共有メモリ通信の恩恵を最大限に受けられるし、データが必要になるまでスレッド間の連携を遅らせることができる。

Shinichi Tokunaga @deepneko

ただし必要なときにデータが正しい値になっていることが保証されていなければならない。

Shinichi Tokunaga @deepneko

データが更新処理中だったり古いデータだったりすると意味ないからね。

Shinichi Tokunaga @deepneko

なんかこの本、サンプルを載せてくれるのはいいんだが、最終的にスレッド化したものを書いてくれてないんだが。今のところ。

Shinichi Tokunaga @deepneko

解説だけ載ってるからあとは自分で書いてみろってことなんだろうけど。

Shinichi Tokunaga @deepneko

並列化できない(しづらい)アルゴリズム

Shinichi Tokunaga @deepneko

状態を持つもの。次の処理へ進む際に何かしらの情報を維持するもの。乱数生成のseed、ファイルI/Oのseek位置など。

Shinichi Tokunaga @deepneko

漸化式。ただしprefix sumは可能。