2011年7月11日月曜日

Scalaのアクターモデルでマンデルブロ集合を並列計算

このブログ記事をはてなブックマークに追加

最近、本格的にScalaを使用するつもりで環境を整えた。ビルドツールとしてSimple Build Tool (sbt)を利用し、エディタはensimeを入れたEmacsにしている。利用するに当たって.emacsに必要な記述を加えておくこと。初めてのプロジェクトの場合、適当に作成したディレクトリ内でsbtを起動してプロジェクトの雛形を作った後、Emacsを立ち上げて M-x ensime-config-gen で下準備をする。ここまでは初回のみの作業となる。その後は M-x ensime を実行して、src/main/scala/内でコードを書くだけ。これで、コーディング中にタブで補完してくれるし、文法などが間違っている場合に赤でハイライトもしてくれる。コンパイルや実行などは、C-c C-v s とすればsbtがEmacs上で立ち上がるので compile や run するだけ。簡単。

Scalaと言えばアクターでしょ、やっぱり。ということで今回はアクターモデルを使用したコードを書いてみた。自分はScalaをいじるよりも前にErlangをいじっていたので余計にそう考えてしまうのかもしれない。それでもマルチコアやらメニーコアが溢れているこの時代、並行処理の重要性は誰もが認識しているはず。

書いたコードはマンデルブロ集合の計算だ。毎回飽きもせずにまたそれかと思うかもしれないが、並列処理させるのが簡単だし、いつも同じ内容にしておけば比較も容易。なによりもマンデルブロ集合の画像はともて魅力的だと自分では思っているので、今回もマンデルブロ集合だ。冒頭に作成した画像を載せたけど、やっぱり美しいと思う。

今回のアクターモデルでは、scala.actors.Actorから派生させずに、scala.actors.Actor.actorを使用した。クラスを作るほど大行ではないし、その方がスッキリするからだ。そして、計算のループ部分は末尾再帰とパターンマッチを使っている。関数型言語として使うならやっぱりその方がしっくりくる。ただ、ちゃんと末尾再帰させるように、final修飾子をつけるなど、気をつけること。それと@tailrecアノテーション(scala.annotation.tailrec)は常に付けたほうが良い。@tailrecアノテーションを末尾再帰させたい関数につけておけば、末尾再帰としてコンパイルされなかった時にエラーを返してくれる。アクターを使用しないコードもついでに作成した。画像の色付け部分はScalaでMandelbrot、時間測定は関数の実行時間を計測するには?を参考にさせてもらった。

実行環境としてXeon X5650@2.67GHz * 2 (12コア/24スレッド; メモリ48GB)を使用した。マンデルブロ集合の条件としては、画像の大きさが4,800 x 4,800ピクセルで、(-0.005, -0.005)から(0.005, 0.005)を計算の範囲とし、繰り返し数10,000で10.0を閾値としている。因みにこの範囲は集合に含まれるので計算量としては最大となる(画像としては真っ黒なので面白くはないが)。実行すると最後に画像ファイル(mandelbrot.png)を出力して終了する。

実行した結果、アクターを使用しなかったコードの実行時間が1007.18秒だったのに対し、アクターを使用したコードでは51.636秒であった。約20倍の高速化である。コア数12・スレッド数24であることを考えても、この高速化は十分なのではないだろうか。ところで、アクターを使用しないシングルスレッドでのコードでも以前作成したC++のコード(1067.39秒)より速かった。それに、TBBを使用した並列化したコードでも56.8956秒の計算時間がかかっており、アクターを使用したScalaのコードはそれよりも速い。色の作成の部分など少し異なるところもあるのでそのまま比較することはできないかもしれないが、少なくとも今回の場合ではScalaで十分な速度を得られることは確認できた。余談だが、Telsaのボードを2枚挿ししたマシン上で実行したCUDAのコードでは3.73秒なので次元が違ったりする。

しかし、実際にコードを書くときは注意深くなる必要があるかもしれない。例えば以下のコードがある。

i match { case MAX_LOOP => -1 case _ if zr2 + zi2 >= TH => i case _ => { val zrzi = zr * zi calcLoop(i + 1, cr, ci, zr2 - zi2 + cr, zrzi + zrzi + ci) } }

これを以下のように変更する。

(i, zr2 + zi2) match { case (MAX_LOOP, _) => -1 case (_, z) if z >= TH => i case _ => { val zrzi = zr * zi calcLoop(i + 1, cr, ci, zr2 - zi2 + cr, zrzi + zrzi + ci) } }

これだけのことで実行速度が6倍程遅くなる。これに気付かずにいると本来のパフォーマンスを出すことができない。予想よりもプログラムが遅いと感じた場合は再度コードを確認したほうがいいだろう。

自分は普段は主にC++とPythonを使っていて、目的によって使い分けている。ある程度しっかりした作りで高速に動作させたい場合はC++だし、プロトタイプとして作ったり、結果の解析用コードをサクっと作りたい場合はPythonを使う。Scalaはどのような用途に使えるのか。まず、Javaの資産を使えるのは大きい。ネットワーク処理や画像処理などをある程度本格的につくろうとしたときに便利そうだ。あとは言語の仕様として処理を簡潔に書き表せるという点が良い。ライブラリが強力で簡潔に書ける。この点だけで十分に利用する価値があるだろう。

最後に自分の持っているScalaの書籍を2つ挙げておく。Scalaプログラミング入門は実践的だし、Scalaスケーラブルプログラミングは網羅的なので、どちらも持っていて損はないと思う。

作成したコードを以下に示しておく。

mandelbrot.scala (アクターあり; 並行処理)

// mandelbrot.scala with actor by nox, 2011.07.09 import scala.actors._, Actor._ import scala.annotation.tailrec import java.io.FileOutputStream import java.awt.image.BufferedImage import java.awt.Color import javax.imageio.ImageIO import scala.testing.Benchmark /** * マンデルブロ集合. * SW : 画像の幅. * SH : 画像の高さ. * T : 集合の上の位置. * L : 集合の左の位置. * W : 集合の幅. * H : 集合の高さ. * MAX_LOOP : イテレーションの最大回数. * TH : 閾値. */ final class Mandelbrot(SW: Int, SH: Int, T: Double, L: Double, W: Double, H: Double, MAX_LOOP: Int, TH: Double) { /** * イテレーションの回数から色を決定して任意のピクセルにセットする. */ def setPixel(x: Int, y: Int, a: Any, image: BufferedImage) = a match { case -1 => image setRGB(x, y, 0) case i: Int => image setRGB(x, y, Color HSBtoRGB(i / 100.0f, 1.0f, 1.0f)) } /** * マンデルブロ集合の計算部分. */ @tailrec def calcLoop(i: Int, cr: Double, ci: Double, zr: Double, zi: Double): Int = { val zr2 = zr * zr val zi2 = zi * zi i match { case MAX_LOOP => -1 case _ if zr2 + zi2 >= TH => i case _ => { val zrzi = zr * zi calcLoop(i + 1, cr, ci, zr2 - zi2 + cr, zrzi + zrzi + ci) } } } /** * アクター. * ある幅に存在するピクセルの計算を受け持つ. */ def calc = actor { react { case (ix: Int, image: BufferedImage) => { for (iy <- 0 until SH) setPixel(ix, iy, calcLoop(0, L + (ix.toDouble / SW) * W, T + (iy.toDouble / SH) * H, 0.0, 0.0), image) reply(ix) } } } /** * 幅のピクセル数分だけアクターにメッセージを送る. */ @tailrec def runLoop(ix: Int, results: Array[Future[Any]], image: BufferedImage): Unit = ix match { case SW => results foreach(_ apply) case _ => { results(ix) = calc !! ((ix, image)) runLoop(ix + 1, results, image) } } /** * 実行. * 計算部分の処理時間計測および画像ファイルの書き出し. */ def run = { val results = new Array[Future[Any]](SW) val image = new BufferedImage(SW, SH, BufferedImage TYPE_3BYTE_BGR) val t = (new Benchmark { def run = runLoop(0, results, image) } runBenchmark 1)(0) / 1000.0 println("Time: " + t + " s") val out = new FileOutputStream("mandelbrot.png") ImageIO write(image, "png", out) out close } } object MandelbrotMain { def main(args: Array[String]) = new Mandelbrot(4800, 4800, -0.005, -0.005, 0.01, 0.01, 10000, 10.0) run //new Mandelbrot(640, 480, -1.0, -2.0, 2.6666667, 2.0, 1000, 10.0) run //new Mandelbrot(800, 800, 0.025185, -1.401565, 0.0005, 0.0005, 10000, 10.0) run }

mandelbrot.scala (アクターなし; 逐次処理)

// mandelbrot.scala without actor by nox, 2011.07.09 import scala.annotation.tailrec import java.io.FileOutputStream import java.awt.image.BufferedImage import java.awt.Color import javax.imageio.ImageIO import scala.testing.Benchmark /** * マンデルブロ集合. * SW : 画像の幅. * SH : 画像の高さ. * T : 集合の上の位置. * L : 集合の左の位置. * W : 集合の幅. * H : 集合の高さ. * MAX_LOOP : イテレーションの最大回数. * TH : 閾値. */ final class Mandelbrot(SW: Int, SH: Int, T: Double, L: Double, W: Double, H: Double, MAX_LOOP: Int, TH: Double) { /** * イテレーションの回数から色を決定して任意のピクセルにセットする. */ def setPixel(x: Int, y: Int, a: Any, image: BufferedImage) = a match { case -1 => image setRGB(x, y, 0) case i: Int => image setRGB(x, y, Color HSBtoRGB(i / 100.0f, 1.0f, 1.0f)) } /** * マンデルブロ集合の計算部分. */ @tailrec def calcLoop(i: Int, cr: Double, ci: Double, zr: Double, zi: Double): Int = { val zr2 = zr * zr val zi2 = zi * zi i match { case MAX_LOOP => i case _ if zr2 + zi2 >= TH => i case _ => { val zrzi = zr * zi calcLoop(i + 1, cr, ci, zr2 - zi2 + cr, zrzi + zrzi + ci) } } } def calc(cr: Double, ci: Double): Int = calcLoop(0, cr, ci, 0.0, 0.0) /** * 画像のピクセル数分だけループする. */ @tailrec def runLoop(ix: Int, iy: Int, image: BufferedImage): Unit = (ix, iy) match { case (SW, _) => None case (_, SH) => runLoop(ix + 1, 0, image) case (_, _) => { setPixel(ix, iy, calc(L + (ix.toDouble / SW) * W, T + (iy.toDouble / SH) * H), image) runLoop(ix, iy + 1, image) } } /** * 実行. * 計算部分の処理時間計測および画像ファイルの書き出し. */ def run = { val image = new BufferedImage(SW, SH, BufferedImage TYPE_3BYTE_BGR) val t = (new Benchmark { def run = runLoop(0, 0, image) } runBenchmark 1)(0) / 1000.0 println("Time: " + t + " s") val out = new FileOutputStream("mandelbrot.png") ImageIO write(image, "png", out) out close } } object MandelbrotMain { def main(args: Array[String]) = new Mandelbrot(4800, 4800, -0.005, -0.005, 0.01, 0.01, 10000, 10.0) run //new Mandelbrot(640, 480, -1.0, -2.0, 2.6666667, 2.0, 1000, 10.0) run //new Mandelbrot(800, 800, 0.025185, -1.401565, 0.0005, 0.0005, 10000, 10.0) run }

0 コメント: