パラレルマンデルブロ

risupu - notes on Lisp and programming: Parallel Mandelbrot computation in Lisp on a cluster に触発されて自前の Erlang まねっこライブラリでちょっとやってみた。

(declaim (optimize (speed 3) (safety 0)))

(defconstant +resolution+ 5000)
(defconstant +iterations+ 100)

(declaim (inline iters))

(defun iters (max xc yc)
  (declare (double-float xc yc))
  (let ((x xc)
        (y yc))
    (declare (double-float x y)
             (fixnum max))
    (loop for count from 0 below max
          do (when (>= (+ (* x x) (* y y)) 4.0d0)
               (return-from iters count))
             (let ((tmp (+ (- (* x x) (* y y)) xc)))
               (setf y (+ (* 2.0d0 x y) yc)
                     x tmp)))
    max))

;; http://random-state.net/files/mandelbench.lisp
;; シングルスレッドバージョン
(defun main ()
  (let* ((max (truncate +resolution+ 2))
         (min (- max))
         (mul (/ 2.0d0 max))
         (count 0))
    (declare (fixnum count))
    (loop for i from min upto max
          do (loop for j from min upto max
                   do (incf count (iters +iterations+ (* mul i) (* mul j)))))
    (format t "result ~d~%" count)))


;; 50 スレッドバージョン
(eval-when (:compile-toplevel :load-toplevel :execute)
  (require :quek))

(defun pmain ()
  (let* ((max (truncate +resolution+ 2))
         (min (- max))
         (mul (/ 2.0d0 max))
         (count 0)
         (num-procs 50)                 ; 50 スレッド使う
         (rows-pre-proc (/ +resolution+ num-procs))
         (parent quek:*current-thread*))
    (declare (fixnum count))
    (loop for proc from 0 below num-procs do
      (let* ((my-rank proc)
             (local-min (+ min (* my-rank rows-pre-proc)))
             (local-max (1- (+ local-min rows-pre-proc)))
             (local-count 0))
        (declare (fixnum local-min local-max local-count))
        (quek:spawn
          (loop for i from local-min upto local-max do
            (loop for j from min upto max do
              (incf local-count (iters +iterations+ (* mul i) (* mul j)))))
          (quek:send parent local-count))))
    (loop repeat num-procs do
      (quek:receive ()
        (x (locally (declare (fixnum x)) (incf count x)))))
    (format t "result ~d~%" count)))

main の方はオリジナルのコード。 pmain の方は CL-MPI から翻訳。

CL-USER> (time (main))                  ; シングル thread
result 290068052
Evaluation took:
  4.830 seconds of real time
  4.764298 seconds of total run time (4.740296 user, 0.024002 system)
  98.63% CPU
  8,672,484,384 processor cycles
  387,408 bytes consed

NIL
CL-USER> (time (pmain))                 ; 50 thread
result 290068052
Evaluation took:
  2.752 seconds of real time
  5.064316 seconds of total run time (4.872304 user, 0.192012 system)
  184.01% CPU
  4,940,713,287 processor cycles
  302,368 bytes consed

NIL

うん。速くなった。単純に満足する。

ところで CL-MPI の作者は、東京工業大学の先生のもよう。どうりでブログのタイトルが「risupu」だったりするわけだ。

CL-MPI を使えば Common Lisp で分散並列処理が可能になるのかな。いいな。おもしろそうだ。