CUDAでの配列の最大値について

質問

質問です。
GPUを用いて配列の最大値を求める処理について
1，隣の要素と比較する。
2，スレッド数だけ離れた要素と比較する。
例えば，配列の要素数16、スレッド数8の場合
1，スレッド0は0番目と1番目の要素を比較
2，スレッド0は0番目と8番目の要素を比較
どちらが高速になると思われますか？

自分は、バンクコンフリクトが少ない2番の方が高速になると思います。
皆様の回答お待ちしております。

回答No.1

rabbit_cat

それは、配列の要素数と、スレッド数と、バンク数との兼ね合いで決まるので、場合によります。

バンク数が８個だとして、配列の要素数16の場合
・バンク１に、０番目と８番目の要素
・バンク２に、１番目と９番目の要素
・バンク３に、２番目と１０番目の要素
…
と割り付けられた場合なら、
たしかに、
方法１が、２回バンクコンフリクトがおこる（全スレッドの処理官僚まで合計４回のメモリアクセスが必要）
なのに対して、
方法２は、バンクコンフリクトが全くおきないので、合計２回のメモリアクセスで、全スレッドの処理が終わる
ということは確かです。本当の最良ケースです。

ただ、一般的には、配列の要素数（より正確には、各スレッドが興味をもつ要素の番号）と、バンク数・スレッド数が、倍数の関係になっているのは、あまり良くないとされます。（できれば、互いに素な値になるようにしておくほうがよい）

なぜなら、配列の要素数がバンク数やスレッド数の倍数になっていると、配列の要素が各バンクに周期的に配置されるために、たしかに、最良の場合には、上の例の方法ようにバンクコンフリクトがうまいこと避けられて高速、という場合もあるのですが、
よほど注意深くプログラミングしていないと、逆に、上の例の方法１のように、各スレッドが常に同じバンクにアクセスするようになる最悪の場合が起こることもよくあります。
通常、こういうメモリアクセス時間というのは、
・平均ケースにくらべて、最良ケースはわずかに速い
・平均ケースにくらべて、最悪ケースはものすごく遅い
という関係になっているので、配列の要素数がバンク数やスレッド数の倍数になっていると、平均的には遅くなる場合が多いです。

なんで、この場合で言えば、
3，（スレッド数＋１）だけ離れた要素と比較する。
ということをよくやります。

・スレッド0は0番目と9番目の要素を比較
・スレッド1は1番目と10番目の要素を比較
…
・スレッド6は6番目と15番目の要素を比較
・スレッド7は7番目と8番目の要素を比較

というように、あえて、要素番号が８ではなくて９ずれた要素と比較するようにしておくと、ものすごく精密にプログラミングしなくても、（最悪ケースの発生率が大幅に減るので）、平均的には速くなることが多いです。

Wikipediaのバンクコンフリクトのページにのっている、２次元配列で中身のない列を加える、とかはまさにこれです。
http://ja.wikipedia.org/wiki/%E3%83%90%E3%83%B3%E3%82%AF%E3%82%B3%E3%83%B3%E3%83%95%E3%83%AA%E3%82%AF%E3%83%88

お礼

回答あるがとうございます。
返信が遅れてしまい、申し訳ございません。

なるほど。
最悪のケースのことを考えていませんでした。
大変勉強になりました。