Erlang Performance
出典: KLablabWiki
目次 |
概要
並列処理に適したプログラミング言語 Erlang は、マルチプロセッサの環境で 効率よくパフォーマンスが向上すると言われています。そこで実際のマルチプ ロセッサ環境で様々な Erlang プログラムを走らせる検証を行ってみました。
行った検証の内容は以下の通りです
- 並列ソート
- N-Queen 問題
検証環境
- ハードウェア
- Sun Fire T1000
- CPU
- UltraSPARC T1
- メモリ
- 16G
- OS
- Solaris 10 8/07
- Erlang 実行環境
- OTP 12B-0(hipe 有効)
今回使用した UltraSPARC T1 プロセッサ は 8つのコア×4スレッド(CoolThreads)という構成 で合計 32個の並列処理が可能となっています。なお、検証に使用した Sun Fire T1000 はサン・マイクロシステムズ（株）様よりごお貸し頂きました。
ソースコード
今回の実験で使用したプログラムのソースコード全て公開しています。
ビルドのための Makefile を用意してありますが、Erlang の実行環境が hipe に対応していない場合、コンパイルオプションから +native を外す必要があることと、 実行環境のバージョンが OTP 12B-0 より古い場合でマルチCPUを使用する際には -smp オプション を付ける必要があります。
検証内容
並列ソート
単一CPUを使用する普通のクイックソート(sort:qsort/1)、マージソート (sort:msort/1)と複数CPU を使用する並列クイックソート(sort:pqsort/4)、並 列マージソート(sort:pmsort/4) の速度を比較してみます。
この検証に使用したランダムデータは前記したソースコードの rnd/ ディレクト リに置いてあります。
アルゴリズム
並列ソートのクイックソートとマージソートのアルゴリズムは両方とも要素を ２分割した後に別のプロセスを立ち上げて再帰処理を行います、ある程度の深 さ(今回は深さ8)まで分割が進んだら、プロセスの生成を止め通常のソートに切 り替えるという単純なものです。例えば、並列マージソートの場合 2^8=256 個 要素列に分割され、並列ソートが行われます。
実行例
普通のクイックソートで要素数が 1000個のデータをソートします。
% erl -noshell -run sort start qsort rnd/1000.txt -run erlang halt Time: 2913(usec)
並列クイックソートで要素数が 1000個のデータをソートします。
% erl -noshell -run sort start pqsort rnd/1000.txt -run erlang halt Time: 5580(usec)
高々 1000 個程度の要素数であれば、並列処理の方が遅くなってしまうようです。
結果
単位はミリ秒
| 要素数 | 1万 | 10万 | 100万 |
| クイックソート(1CPU) | 41.794 | 737.209 | 8909.677 |
| 並列クイックソート(32CPU) | 33.426 | 590.770 | 5402.714 |
| マージソート(1CPU) | 94.112 | 1201.185 | 14764.758 |
| 並列マージソート(32CPU) | 44.284 | 377.994 | 3672.162 |
1CPU の時はマージソートよりクイックソートの方が早かったのですが、32CPU を使用した並列ソートでは、マージソートの方が早くなるという結果になりま した。これはマージソートが単純に 2分割するのに比べ、クイックソートは分 割自体にコストが掛かってしまうため 32CPU をフルに使用出来る時間が短くなっ てしまう為と思われます。
N-Queen問題
並列に N-Queen 問題を解く Erlang のプログラムを実行し、CPU を増やしていっ た際に処理速度がどのように向上するかを計測してみます。
アルゴリズム
最初の 2 駒目まで進めた譜面まで分割し、別プロセスを立ち上げ、続きを単純 なアルゴリズム(nq:nq/1) で並列に解き、解の数をメッセージで返します。例 えば N=14 の場合、14^2 - (置けないパターン) = 156 の盤面から並列に解い ていきます。
実行例
CPU を 8個使用して N=14 Queen 問題を解きます。
% erl -noshell +S 8 -run nq start 14 -run erlang halt Num: 365596 Time: 65006641(usec)
N=14 Queen 問題の解の数が 365596 であることと処理時間が表示されます。
結果
| CPU数 | 処理時間(秒) |
| 1 | 522.048 |
| 2 | 260.400 |
| 4 | 129.477 |
| 8 | 65.006 |
| 16 | 37.581 |
| 32 | 30.678 |
CPUが倍になると処理時間が約半分になり、比例とまでは行きませんがマルチプ ロセッサを効率よく使用出来ているようです。
参考文献
更新履歴
- 2007/01/15 公開しました
- 2007/01/16 幾つかの誤字を修正しました。
RSS Feed