Home > プログラミング > Go に手を出す(並列計算)

Go に手を出す(並列計算)

並列に動くっぽいけど本当にそうなのか気になったので,色々書けるようにと勉強してみた.

セミコロン少なめだし,カッコ少なめだし,型を書くのも少なめだし,タプルあるし,型システム単純だし,例外ないし,オーバーロードないし,generics 入ってないし,GCだし,メソッド定義にはレシーバ書くし,継承ないし,interface とかメソッドさえ揃っていれば継承したことになるし,embedded types とか楽すぎだし,宣言したのに使ってない変数があるとコンパイルしてくれないし,スコープ上書きしたときに何も言ってくれないし,速度も十分速いし.スクリプト言語の気分で速いプログラムが書けるような気がする.一方で,generic types がないので高レベルな汎用ルーチンが書きづらい.

で,そんなことはさておきとりあえずベンチマークということで,n-queen問題のプログラムを書いてみた:

package main
import ("fmt"; "flag")
 
func nqueen(n, i, u, l, r int) int {
  if i==n { return 1 } 
  nl := (l << 1) | 1;
  nr := ((r|(1<<uint(n))) >> 1);
  ni := i + 1;
  p := u & nl & nr;
  c := 0;
  for p!=0 {
    lb := (-p) & p;
    p ^= lb;
    c += nqueen(n, ni, u ^ lb, nl ^ lb, nr ^ lb)
  }
  return c
}
 
type State struct { n, i, u, l, r int }
func nqueenRes(ch chan int, n, i, u, l, r int) { 
  ch <- nqueen(n, i, u, l, r)
 }
 
func gentasks(cs *[] chan int, lim, n, i, u, l, r int) {
  if i==lim {
    lx := len(*cs);
    *cs = (*cs)[0:lx+1];
    (*cs)[lx] = make (chan int);
    go nqueenRes((*cs)[lx], n, i, u, l, r);    
    return;
  }
  nl := (l << 1) | 1;
  nr := ((r|(1<<uint(n))) >> 1);
  ni := i + 1;
  p := u & nl & nr;
  for p!=0 {
    lb := (-p) & p;
    p ^= lb;
    gentasks(cs, lim, n, ni, u ^ lb, nl ^ lb, nr ^ lb)
  }
}
 
func nqueensGo(n int) int {
  b := (1<<uint(n)) - 1;
  cs := make( [] chan int, 0, n * n * n);
  gentasks(&cs, 3, n, 0, b, b, b);
 
  sum := 0;
  for _, c := range cs { sum += <- c }
 
  return sum;
}
 
var n = flag.Int("n", 16, "n")
 
func main() {
  flag.Parse();
  fmt.Println(nqueensGo(*n));
}

ついでに比較対象のC++プログラム(OpenMP使用):

#include<iostream>
#include<vector>
#include<omp.h>
#include<stdlib.h>
 
using namespace std;
 
int nqueen(int n, int i, int u, int l, int r) 
{
  if(i==n) return 1; 
  const int nl = (l << 1) | 1;
  const int nr = ((r|(1<<n)) >> 1);
  const int ni = i + 1;
  int p = u & nl & nr;
  int c = 0;
  while(p!=0) {
    const int lb = (-p)&p;
    p ^= lb;
    c += nqueen(n, ni, u ^ lb, nl ^ lb, nr ^ lb);
  }
  return c;
}
struct state {
  int n, i, u, l, r;
  state(int n, int i, int u, int l, int r) : n(n), i(i), u(u), l(l), r(r) {}
};
int nqueen_res(const state &st) { return nqueen(st.n, st.i, st.u, st.l, st.r); }
 
void gentasks(vector<state> &xs, int lim, int n, int i, int u, int l, int r) 
{
  if(i==lim) {
    xs.push_back(state(n, i, u, l, r));
    return;
  }
  const int nl = (l << 1) | 1;
  const int nr = ((r|(1<<n)) >> 1);
  const int ni = i + 1;
  int p = u & nl & nr;
  int c = 0;
  while(p!=0) {
    const int lb = (-p)&p;
    p ^= lb;
    gentasks(xs, lim, n, ni, u ^ lb, nl ^ lb, nr ^ lb);
  }
}
 
int nqueensOMP(int n)
{
  int b = (1<<n) - 1;
  vector<state> xs;
  gentasks(xs, 3, n, 0, b, b, b);
 
  int nx = xs.size();
  int sum = 0;
#pragma omp parallel for reduction(+:sum)
  for(int i = 0; i < nx; i++) {
    sum = sum + nqueen_res(xs[i]);
  }
  return sum;
 
}
 
int main(int argc, char *argv[])
{
  int n = argc > 1 ? atoi(argv[1]) : 16;
  int c = nqueensOMP(n);
  std::cout << n << " " << c << std::endl;
  return 0;
}

とりあえず実験結果.OpenMPのスケジューリングを変更して性能を改善したものの結果は下のほう.

8コアのマシン(Xeon E5430 @ 2.66GHz x2)での実験結果(n=17).C++ はg++4.5.0 (exeperimental) に -O3,Go は 6g/6l でコンパイル.OMP_NUM_THREADS と GOMAXPROCS でスレッド数を指定.speedup は C++ の1スレッドに対する速度比.

スレッド数C++ [秒]C++ [speedup] Go [秒] Go [speedup]
1 105.594 1.00000 140.792 0.75
2 52.717 2.00304 70.811 1.49121
3 40.357 2.61650 47.447 2.22551
4 29.754 3.54890 35.652 2.9618
5 24.524 4.30574 28.414 3.71627
6 20.513 5.14766 23.712 4.45319
7 17.643 5.98504 20.349 5.18915
8 15.398 6.85764 17.929 5.88956

どうやらC++の1.3倍程度の遅さらしい.問題が問題だけに台数効果はほぼリニアに出ている(スレッド数増やした時のC++の伸び具合が今ひとつだが… スケジューリング変えるべきか?).Goは性能的に何の問題もなく優秀だねぇ.まあ,この手の極単純なループの並列化に関してはOpenMPの方が楽ではあるけれど.

ついでに,24コア(Xeon X7460 @ 2.66GHz x4)のマシンでの実験結果(n=17).C++ はg++4.3.2 に -O3,Go は 6g/6l でコンパイル.OMP_NUM_THREADS と GOMAXPROCS でスレッド数を指定.speedup は C++ の1スレッドに対する速度比.
スレッド数C++ [秒]C++ [speedup] Go [秒] Go [speedup]
1 123.353 1.00000 144.181 0.85554
2 61.897 1.99288 71.764 1.71887
3 47.255 2.61037 47.722 2.58482
4 35.073 3.51704 35.823 3.4434
5 28.474 4.33213 28.741 4.29188
6 23.761 5.19141 23.846 5.1729
7 20.539 6.00579 20.491 6.01986
8 18.019 6.84572 17.954 6.8705
9 16.112 7.65597 15.965 7.72646
10 14.372 8.58287 14.394 8.56975
11 13.065 9.44148 13.109 9.40979
12 12.051 10.2359 12.007 10.2734
13 11.322 10.8950 11.091 11.1219
14 10.270 12.0110 10.299 11.9772
15 9.579 12.8774 9.619 12.8239
16 9.055 13.6226 9.014 13.6846
17 8.440 14.6153 8.500 14.5121
18 8.081 15.2646 8.014 15.3922
19 7.652 16.1204 7.611 16.2072
20 7.333 16.8216 7.225 17.0731
21 7.025 17.5591 6.904 17.8669
22 6.646 18.5605 6.587 18.7267
23 6.419 19.2169 6.296 19.5923
24 6.359 19.3982 6.274 19.661

スレッド数増やしたときにGoの方が速くなっているのはスケジューリングがうまいからだろうなぁ.OpenMPもラウンドロビンとかにすれば改善するかも?


ということで,サイズ1でラウンドロビンするように

#pragma omp parallel for reduction(+:sum) schedule(dynamic)

に変えてC++の実験を取り直した.

8コアマシンで.

スレッド数C++ [秒]C++ [speedup] Go [秒] Go [speedup]
1 106.079 1.00000 140.792 0.75344
2 53.386 1.98702 70.811 1.49806
3 35.603 2.97950 47.447 2.23574
4 26.741 3.96690 35.652 2.97540
5 21.373 4.96322 28.414 3.73334
6 17.901 5.92587 23.712 4.47364
7 15.329 6.92015 20.349 5.21298
8 13.513 7.85014 17.929 5.91662

24コアマシンで.

スレッド数C++ [秒]C++ [speedup] Go [秒] Go [speedup]
1 123.471 1.00000 144.181 0.85636
2 62.137 1.98708 71.764 1.72051
3 41.452 2.97865 47.722 2.58730
4 31.043 3.97742 35.823 3.44670
5 24.837 4.97125 28.741 4.29599
6 20.711 5.96161 23.846 5.17785
7 17.849 6.91753 20.491 6.02562
8 15.546 7.94230 17.954 6.87707
9 13.785 8.95691 15.965 7.73386
10 12.434 9.93011 14.394 8.57795
11 11.309 10.9179 13.109 9.41880
12 10.360 11.9181 12.007 10.2833
13 9.562 12.9127 11.091 11.1325
14 8.882 13.9013 10.299 11.9886
15 8.302 14.8724 9.619 12.8362
16 7.772 15.8866 9.014 13.6977
17 7.317 16.8745 8.500 14.5260
18 6.914 17.8581 8.014 15.4069
19 6.552 18.8448 7.611 16.2227
20 6.227 19.8283 7.225 17.0894
21 5.923 20.8460 6.904 17.8840
22 5.663 21.8031 6.587 18.7446
23 5.431 22.7345 6.296 19.6110
24 5.474 22.5559 6.274 19.6798

うん,常にC++の方が速い結果になったので問題なし.スケジューリングのオーバヘッドが無視出来る問題だから,スケジューリングの柔軟さがやっぱ効いてくるねと.

★下記に2つの英単語をスペースで区切って入力してください

Home > プログラミング > Go に手を出す(並列計算)

Search
Feeds

Page Top