双子素数を計算するプログラムをMPIを用いた並列プログラミングで実現する。
その実行にはfolon4を使用した。
双子素数：pとp+2が共に素数であるとき、それらを双子素数と呼ぶ。例えば、3と5、5と7などがそうである。
folonに触れる事で、並列効果の凄さを知る。
双子素数を探し出す方法はいくつか存在する。
１つ目は素数を求めてから、その＋２の数が素数かどうかを判定していく方法である。
この方法だと、素数を求めるアルゴリズムとして何を使うかが問題となる。
２つ目は公式を使う方法である。
ある整数n,n+2が双子素数を成すかどうかを確かめる公式がある。
自然数n(≧2)に対して整数n,n+2が双子素数の組を成す必要十分条件は、
4[(n-1)!+1]+n≡0(mod.n(n+2))
というものである。
これを使うと、並列演算としてはnの範囲で各ノードに仕事を割り振れるので一見よさそうに見える。しかし、これには致命的な問題点があるため使わない。（詳しくは後の計算量の部分で述べる）
ということで、素数を求めてから判定する方法で双子素数を発見していく。
エラトステネスのふるい法を使い、素数を見つけ出す。
そして、その素数＋２の数が素数であれば、それらは双子素数となる。
エラトステネスのふるいの部分を並列として実装する。
具体的には次のようになる。
・PE0で３以上の奇数を生成し、次のPEへその数を渡す
- 1.
- 最初に渡された数を素数(prime)として保存する。
- 2.
- primeの次から渡された数を見る。
- 2.1
- prime+2だったら、それがprimeとprime+2は双子素数なので、表示する。
- 2.2
- 素数(prime)の倍数が来たら、その数は次のPEへ渡さない。
- 2.3
- 番兵(0)が来たら隣のPEに番兵(0)を渡し、自分は4.へ行く
- 2.4
- それ以外(prime+2を含む)だったら次のPEに数を渡す
- 3.
- 2.の繰り返し
- 4.
- 番兵(0)の次に渡された数が番兵(0)だったら、次のPEに番兵(0)を渡し、作業を終える。違ったら1.へ行く
プログラム
パワーポイント
プログラムを見ると
while(1){
MPI_Recv(&x, 1, MPI_INT, np-1, 1000, MPI_COMM_WORLD, &st);
省略
/* 最初に受け取った数が番兵(0)だったらループから出る */
if(x == 0){
MPI_Send(&zero, 1 ,MPI_INT, 1, 1000, MPI_COMM_WORLD);
break;
}
while(1){
MPI_Recv(&x, 1, MPI_INT, np-1, 1000, MPI_COMM_WORLD, &st);
省略
/* 番兵(0)が来たらループから出る */
if(x == 0) {
MPI_Send(&zero, 1 ,MPI_INT, 1, 1000, MPI_COMM_WORLD);
break;
}
省略
}
}
２重ループになっていて、停止条件が番兵となっている。
番兵は数列の最後につく。
数列はnに比例するので、停止条件までたどり着くのもnに比例する。
すると計算量は
となることが分かる。
世の中のすべての素数を探そうとするなら、この方法が最速だろう。
さてここで、さっき残っていたなぜ双子素数の判定公式を使ってはいけないのかを考えてみる。
この公式の中にある(n-1)!という部分に注目する。
うまくプログラムを書くとこれの計算量はたいしたことない。
(n-2)!の値をキャッシュしておいて、それに(n-1)をかけてやれば出てくるからだ。
こう考えてみると、エラトステネスのふるい法に比べて大分良いアルゴリズムと思うかもしれない。
しかし、nの値が大きくなるとlongでも保持しておけなくなるので、その部分を自分で工夫しなければならない。
また、値を格納しておけたとしてもものすごい桁の計算となるが、それも大変である。
最終的にはメモリが足りなくなってしまうだろう。
なので、エラトステネスのふるいを採用した。
数が来たらすぐ次にまわすというアルゴリズムを採用しているため、通信回数が問題となってくる。
通信回数もとなる為、通信に問題があると、とても効率が悪くなる。
これを解決するためには、ある程度データが溜まるまで待ってからまとめて送るという方法がある。
これによって通信のオーバーヘッドを減らす事が出来る。
しかし、通信がもの凄くいい場合と、送られてくる数が少ない場合には1個ずつ送ったほうが良いというのは自明の話だ。
それらを調節するのは難しい。
結局、すべての素数の倍数を排除したものを次に送るという形では、並列効果が出てこない。
かといって通信がもの凄く遅い場合には、通信部分でのオーバーヘッドが大きいため、並列化しないほうが早くなるという事がある。
そういった意味で非常に興味深いものだといえるだろう。
パワーポイント2