.NET4.0 の並列処理を試してみた その1 : Parallel.For, ConcurrentQueue
.NET4.0 から従来よりも抽象的で簡単に使える並列ライブラリがどさっと追加されます。おもしろそうなので VisualStudio2010 のベータ1で試してみました。
結論から書くと
- Parallel.For すばらしい！
- Concurrent なコレクションはロックなしで複数タスクからデータの追加ができた
- 今回は約1.4倍しか速くならなかった。不本意。きっと次回に続く
並列？並行？ Parallel? Concurrent?
ちょっと名前に混乱があるのでまずはここから。
Parallel は並列、Concurrent は並行。
増補改訂版 Java言語で学ぶデザインパターン入門 マルチスレッド編
- 作者: 結城浩
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2006/03/21
- メディア: 大型本
- 購入: 15人 クリック: 287回
- この商品を含むブログ (206件) を見る
結城さんのすばらしいマルチスレッドの本によると、
- 逐次(sequential)は複数の仕事を順番に処理
- 並列は複数の仕事を同時に処理
- 並行は逐次・並列に対して抽象度の高い表現で、1つの仕事を「どんな順序で処理してもよい複数の作業」に分割する様子を表現した言葉
- 作業者が一人なら並行処理できるように作業を分割しても逐次的に実行されるし、二人いれば並列に実行される
だそうです。ガッテン、ガッテン。
Java の本だけど、アトミックって何？みたいなことをきっちりわかりやすく書いてあるのでとてもオススメ。並列はしっかりした理解なしだと怖いから、もう一度ちゃんと勉強しなおしたいな。
参考資料
このあたりはまだろくにドキュメントがないし、今後も変更がありそうですが、とりあえず。
参考資料は前回のメモに書いたけど特にオススメなのが MSDN magazine OCTOBER 2008 。日本語だし、blog より詳しくまとまってます。はじめに英語 blog 読んだ自分は涙目…
最初の記事は難しすぎるのでさらっと流し読み推奨。でも書いてる人がクレイからMSに移ってきて並列処理に取り組んでるってのが、そういう時代なんだなーって感慨深い。
特に 次期バージョンの Visual Studio で強化される並列処理のサポート って記事は .NET の並列に興味がある人は必読！TPL (Task Parallel Library), PLINQ (Parallel LINQ), LazyInit
もうひとつ、Windows と C++ にある、「アルゴリズムの効率は、皆さんが考えるほど簡単ではありません。シングルプロセッサ上の適切にデザインされたアルゴリズムは、複数プロセッサ上の不十分な実装よりもパフォーマンスが高い場合がよくあります。」「問題をさらに複雑にするのは、シングルプロセッサ用に最適化されたアルゴリズムは並列化が難しいことが多く、若干効率の劣るアルゴリズムの方が複数プロセッサ上で高いパフォーマンスを示す可能性があることです。」ってところはへぇへぇへぇ。
並列化すれば速くなるってわけじゃないんですね…。
また、データ競合、デッドロックなどの問題は TPL を使ってもあいかわらず「ある」そうです。まあそうだよね。
Parallel.For と ConcurrentQueue で挑戦
id:siokoshou:20090715 の De Bruijn Sequence を求めるプログラムを並列化してみました(De Bruijn Sequence がわからなくても OK)。De Bruijn Sequence B(4,2) のとき、解が20736個あります。このとき、7/15の逐次的なコードの実行時間はx86版でピー秒程度でした(自主規制w)。Output() でコンソールに出力しているところはコメントアウトして、リリース版をVisualStudioなしでエクスプローラーからダブルクリックで起動したときの時間です。
深さ優先探索で木をたどって行くバックトラックによる探索プログラムです。
逐次→並列で変えたところ
- 並列化のため、一つの配列をひっぱりまわすのをやめ、新しい配列を作って再帰先に渡すようにした
- for 文は Parallel クラスの Parallel.For() を使って並列化した
- Parallel.For( 0, this.k, i => SearchCore( ... ) )
- とても簡単に並列化できる。スレッドを扱うごちゃごちゃした部分がライブラリの奥にいったので、従来の(抽象度が低かった)スレッドを扱ったコードより見通しがよいコードになる
- しかもよいハードに変えればコードはそのままでさらに並列化される。次のフリーランチはこちら。
- ConcurrentQueue
を使ってロックなしでデータを追加するようにした - 本当にロックなしで正しく動いた。なにこれスゴイ
- ほかの Concurrent なコレクションもロックいらずで使えた
- このコードではデータを追加するだけで、生産者/消費者型の使い方をしてないので、どの Concurrent なコレクションでも動く
- Concurrent なコレクションはどれを使ってもこの使い方では実行時間はほぼ同じ
- ConcurrentLinkedList は削除予定らしい
- タスク(分割した仕事を今後タスクと呼ぶっぽい。TPL の T)の粒度が小さすぎ(処理が少ない)、かつ、タスクを作りすぎるので、逐次的な SearchCoreSequential と SearchCore を交互に呼ぶようにしてやっと逐次版より速くなった
- SearchCore だけを呼び続けた場合の実行時間は逐次版と同じくらい。配列のコピーで遅くなった分を取り返した程度。意味ない…
- ぼこぼことタスクを増やすのはやはりよくないっぽい。for を Parallel.For に変えただけで速くなるってほど甘くないみたい
実行時間はx86版で約 1.4 速くなりました。実行環境は Core i7 920 実4コア 仮想8コア、メモリ6G、Windows7RC x64。ちなみにx64版はx86よりちょっと遅い…。
今回は約1.4倍速くなっただけ。これじゃあまだまだ全然なので、もっと速くできないかいろいろ試してみます。
並列化したコード。
using System; using System.Collections.Concurrent; using System.Diagnostics; using System.Linq; using System.Threading; namespace DeBruijnSequence { public class SearchDeBruijnSequenceConcurrentCollection { private readonly int k, n, max; //private ConcurrentBag<string> results = new ConcurrentBag<string>(); //private ConcurrentStack<string> results = new ConcurrentStack<string>(); //private ConcurrentDictionary<string, string> results = new ConcurrentDictionary<string, string>(); private ConcurrentQueue<string> results = new ConcurrentQueue<string>(); public SearchDeBruijnSequenceConcurrentCollection( int k, int n ) { if ( k < 2 || 10 < k ) throw new ArgumentOutOfRangeException( "k" ); if ( n < 1 ) throw new ArgumentOutOfRangeException( "n" ); this.k = k; this.n = n; double pow = Math.Pow( k, n ); if ( ( double ) int.MaxValue < pow ) throw new ArgumentOutOfRangeException( "k, n" ); this.max = ( int ) pow; } public ConcurrentQueue<string> Search() { int[] array = new int[ this.n ]; SearchCore( array ); return this.results; } private void SearchCore( int[] array ) { // 重複判定 if ( !IsUnique( array ) ) return; // 完成判定 if ( IsComplete( array ) ) { Output( array ); return; } // 次の反復へ //Parallel.For( 0, this.k, i => SearchCore( array.Concat( new int[] { i } ).ToArray() ) ); Parallel.For( 0, this.k, i => SearchCoreSequential( array.Concat( new int[] { i } ).ToArray() ) ); } private void SearchCoreSequential( int[] array ) { // 重複判定 if ( !IsUnique( array ) ) return; // 完成判定 if ( IsComplete( array ) ) { Output( array ); return; } // 次の反復へ for ( int i = 0; i < this.k; i++ ) { SearchCore( array.Concat( new int[] { i } ).ToArray() ); } } private bool IsUnique( int[] array ) { if ( array.Length <= this.n ) return true; int pos = array.Length - this.n; int[] last = array.Skip( pos ).Take( this.n ).ToArray(); for ( int i = 0; i < pos; i++ ) { if ( array.Skip( i ).Take( this.n ).SequenceEqual( last ) ) return false; } return true; } private bool IsComplete( int[] array ) { if ( array.Length != this.max ) return false; for ( int i = 0; i < this.n - 1; i++ ) { array = array.Concat( new int[] { array[ i ] } ).ToArray(); if ( !IsUnique( array ) ) return false; } return true; } private string Output( int[] array ) { string str = string.Join( "", array.Select( m => m.ToString() ).ToArray() ); //this.results.Add( str ); //this.results.Push( str ); //this.results.TryAdd( str, str ); this.results.Enqueue( str ); return str; } static void Main() { var searcher = new SearchDeBruijnSequenceConcurrentCollection( 4, 2 ); var sw = Stopwatch.StartNew(); var result = searcher.Search(); int count = result.Count; sw.Stop(); Console.WriteLine(); Console.WriteLine( count ); Console.WriteLine( sw.Elapsed ); Console.ReadKey(); } } }
