2009年12月20日

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

セミコロン少なめだし，カッコ少なめだし，型を書くのも少なめだし，タプルあるし，型システム単純だし，例外ないし，オーバーロードないし，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=1７）．C++ はg++4.5.0 (exeperimental) に -O3，Go は 6g/6l でコンパイル．OMP_NUM_THREADS と GOMAXPROCS でスレッド数を指定．speedup は C++ の１スレッドに対する速度比．

スレッド数	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=1７）．C++ はg++4.3.2 に -O3，Go は 6g/6l でコンパイル．OMP_NUM_THREADS と GOMAXPROCS でスレッド数を指定．speedup は C++ の１スレッドに対する速度比．

スレッド数	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もラウンドロビンとかにすれば改善するかも？

---

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

#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++の方が速い結果になったので問題なし．スケジューリングのオーバヘッドが無視出来る問題だから，スケジューリングの柔軟さがやっぱ効いてくるねと．