No Such Blog or Diary

OpenMPのreductionで||とか使ったら評価はどうなるんだ？　||でのリダクションって並列化するとまずいんじゃないだろうか？

やってみた．関数fは引数がtrueならtrueを返して即座に抜け，それ以外は重たい処理をしてからfalseを返す．配列bsはbs[0]のみtrueで他はfalse．これで，逐次実行時にはi=0でrにtrueが入り以降はfの処理をしないので即座に計算が終わる．一方，並列実行時にi=0を含まない反復範囲の計算が行われるとしたら，その部分の計算では重たいfの処理が大量に行われ，計算時間がかさむはず．

#include<iostream>
#include<vector>
 
bool f(bool b)
{
  unsigned int u = 0; 
  if(!b) {
    for(int k = 0; k < 100000; k++) {
      u = (u + 2) % 7;
    }
    u = u ^ (((u/4)<<2) | (u&3));
  }
  return b ^ (u!=0);
}
int k = 2;
int main(int argc, char *argv[])
{
  int n = 10000000;
  std::vector<bool> bs(n);
  for(int i = 0; i < n; i++) {
    bs[i] = i == 0;
  }
  bool r = false;
#pragma omp parallel for reduction(||:r)
  for(int i = 0; i < n; i++) {
    r = r || f(bs[i]);
  }
  int res = r;
  std::cout << res << std::endl;
}

結果：逐次は一瞬，並列だと遅すぎて時間計るのも馬鹿らしい．

ということで，||でのリダクションを並列化するのはあまり意味がない気がする．さらに，本来評価されないものが評価される可能性が出てくるので，セグフォって落ちるプログラムが出来上がるかもしれない．なぜにOpenMPは||もリダクションに使えるようにしているのだろう？

商品のレビューとかで「難しい」とか「ルービックキューブでは起こらないことが起こってしまう」とか言っているけど…，本当に難しいのだろうか？　ツクダ式でやる分にはただのルービックキューブと同じに解けると思うのだけど．

唯一の落とし穴は，一番最後にエッジキューブ二つが通常の手順で揃えられなくなるということだろうけど…．これってセンターキューブが存在していればセンターキューブがずれている状態なので，センターのずれを直すような手順を踏めば直る．

ツクダ式だと見かけ上の不思議パターンは一つのみで，最後に中間層をそろえるときに，対面になっているエッジキューブが共通の面を完成させつつ入れ替わっている状態のはず．この状態は，そろっているように見える残りのエッジキューブ２個とを巻き込んでエッジキューブを入れ替えた後にルービックス・マヌーバー２回で直る．

足りないなぁと思われていた長袖の服がこの度スーツケースの中から数枚発掘された．誰だ片付けてなかったのは…．また仕舞いどころに悩みそう．

C++のOpenMPでは最大値が取れないと言ったら，「boolなら+で最大値取れるじゃん，嘘言うな．」と返ってきた．意味があるかどうかはさておき，確かに出来ることなので実際にやってみた．

ソースは次のとおり．bsにbool値を適当に入れて，それの和をbool変数rに得る計算をreduction(+:r)で並列化する．最後に結果の出力として r を吐き出す．コンパイルはg++に-fopenmpo付けてやった．

#include<iostream>
#include<vector>
 
int k = 2;
int main(int argc, char *argv[])
{
  int n = 10000000;
  std::vector<bool> bs(n);
  for(int i = 0; i < n; i++) {
    bs[i] = i % k;
  }
  bool r = false;
#pragma omp parallel for reduction(+:r)
  for(int i = 0; i < n; i++) {
    r += bs[i];
  }
  int res = r;
  std::cout << res << std::endl;
}

結果：逐次で動かすと1が返ってくるが，OpenMPで並列化したら8コア（スレッド）で8が返ってきた．

普通に考えればrはboolなのでintへの変換時に0か1にしかならないと思うのだけど…，なぜに8？ そもそも逐次と結果違うってのもどうかと．なんとなくreductionの結果をとるときにrの型がboolでなくintとかにされている気がする．ま，詳しくはまた今度調べよう．

このタイミングで人に移すのもあれなので家で大量のしょうがを入れたスープを飲みながら寝る．

風邪引いた．咽ががが…