Go言語の並列性については次を参照。並列性
測定にはそれなりに時間がかかる処理で並列化出来る問題が必要です。ということで「任意の大きさのライツアウトの答えを求める」プログラムにしました。
入力は整数二つ横幅と縦幅、出力は0,1で押すボタン。範囲は矩形で初期状態は全点灯。 アルゴリズムは最上段を全通り試して二段目以降は上段から確定していって、全消灯できたときそれを解とします。全通りの解を全て求めてもいいけど、話の都合上見つかった1つの特解のみ出力します。
GoとC++/OpenMPで実装しました。両方取り敢えず並列化しています。
package main
import "fmt"
import "runtime"
const NCPU = 4 // 実行するスレッド数
func main() {
runtime.GOMAXPROCS(NCPU) // 今後いずれ不要になる
var w, h uint
fmt.Scan(&w, &h)
var m uint64 = 1 << w - 1
cans := make(chan []uint64)
go func() {
for i := uint64(0); i <= m; i++ {
go func(p uint64) { // 最上段の値毎の処理をgoroutineに
d := make([]uint64, h)
d[0] = p
f := p << 1 ^ p ^ p >> 1
for i := uint(1); i < h; i++ {
d[i] = ^f & m
f = d[i-1] ^ d[i] << 1 ^ d[i] ^ d[i] >> 1
}
if f & m == m {
cans <- d // cansはクロージャ
}
}(i)
}
}()
format := fmt.Sprintf("%%0%vb\n", w)
for _, e := range <- cans {
fmt.Printf(format, e)
}
}
#include <iostream>
#include <vector>
#include <bitset>
#include <omp.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
size_t w, h;
cin >> w >> h;
vector<ull> ans;
ull m = (1ull << w) - 1;
#pragma omp parallel for schedule(dynamic, 1)
for(ll p = 0; p <= m; ++p) // omp forの要求でsigned
{
if(!ans.empty()) continue; // omp parallel中はbreak不可
vector<ull> d(h, 0);
d[0] = p;
ull f = p << 1 ^ p ^ p >> 1;
for(size_t i = 1; i < h; ++i)
{
d[i] = ~f & m;
f = d[i-1] ^ d[i] << 1 ^ d[i] ^ d[i] >> 1;
}
if((f & m) == m)
#pragma omp critical
ans = d;
}
for(size_t i = 0; i < h; ++i)
cout << bitset<64>(ans[i]).to_string().substr(64ull - w) << endl;
return 0;
}
goroutine間では共有変数は極力使用せず、チャネルを使って通信します。L14でcansは解を得るためのチャネルです。L33で解を求めて処理をブロックします。またL28でiをクロージャにしないのは参照型だからです→詳しく。 L15をgoする理由は、mが大きい時cansを要求するまでに時間が掛かるのを防ぐためです。もしgoしないと、L17のgoroutineがmだけ大量に生成されます。またgoしておくことでcansの要求に応じてL17の方が優先的に実行され、goroutineが減ったときに勝手に増やしてくれるようになります。実行中のメモリ使用量を見ると一目瞭然です。
mainが返るとgoroutineが残っていてもプログラムは終了します。このプログラムではcansは一回しか要求していませんが、もう一度要求すると次の解が出てきます。
2つのプログラムを実行時間を測定しました。共に4並列で、入力は20×20です。厳密な比較にはなりませんが、参考にはなると思います。因みにgcのスケジューリングは不完全だそうなので、今後改善されるかもしれません。C++のomp forでschedule(dynamic, 1)としているのは、Goのスケジュールと近似するためですが、実際はstaticの方が速いです。
Atom D510; C++:1.30[s] Go:6.88[s]
Core i7 860; C++:0.22[s] Go:2.16[s]
ざっと5～10倍程度の差でしょうか。まあ十分速い部類だと思いますが、どうでしょう？ｗ
改善の余地もあるそうなので今後にも期待したいです。
