並列で8Queensを解いた話（１）

デバッグを兼ねて

Easy-ISLispはver5.30をもって一応の完成をみました。バグ発見のテストを兼ねて8Queensを並列で解くことに挑戦してみました。

ベースはM.Hiroiさんのコード

M.HiroiさんのISLisp入門の記事中のQueens問題のコードを使わせていただきました。これをベースにして逐次のものにプラス、マルチプロセス並列での8queensを書き加えました。コードは下記の通りです。

;;; originally written by M.Hiroi

(defun 8queens ()
    (mp-exec (81queens)
             (82queens)
             (83queens)
             (84queens)
             (85queens)
             (86queens)
             (87queens)
             (88queens)))


(defun 81queens ()
    (pqueens '(2 3 4 5 6 7 8) nil 1))

(defun 82queens ()
    (pqueens '(1 3 4 5 6 7 8) nil 2))

(defun 83queens ()
    (pqueens '(1 2 4 5 6 7 8) nil 3))

(defun 84queens ()
    (pqueens '(1 2 3 5 6 7 8) nil 4))

(defun 85queens ()
    (pqueens '(1 2 3 4 6 7 8) nil 5))

(defun 86queens ()
    (pqueens '(1 2 3 4 5 7 8) nil 6))

(defun 87queens ()
    (pqueens '(1 2 3 4 5 6 8) nil 7))

(defun 88queens ()
    (pqueens '(1 2 3 4 5 6 7) nil 8))



;; 衝突の検出
(defun attack (x xs)
    (labels ((attack-sub (x n ys)
                         (cond ((null ys) t)
                               ((or (= (+ (car ys) n) x)
                                    (= (- (car ys) n) x))
                                nil)
                               (t (attack-sub x (+ n 1) (cdr ys))))))
            (attack-sub x 1 xs)))


;; 解法（逐次　オリジナル）
(defun nqueens (nums board)
  (if (null nums)
      (format (standard-output) "~A~%" board)
    (for ((xs nums (cdr xs)))
         ((null xs))
         (if (attack (car xs) board)
             (nqueens (remove (car xs) nums)
                      (cons (car xs) board))))))


;; 解法(並列)
(defun pqueens (nums board n)
    (if (null nums)
        (pqueens1 board n)
        (for ((xs nums (cdr xs)))
             ((null xs))
             (if (attack (car xs) board)
                 (pqueens (remove (car xs) nums)
                          (cons (car xs) board)
                          n)))))


(defun pqueens1 (board n)
    (cond ((attack n board)
           (let ((stm (create-string-output-stream)))
               (format stm "~A~%" (cons n board))
               (mp-report  (get-output-stream-string stm))))
          (t nil)))


(defun remove (x ls)
    (cond ((null ls) nil)
          ((eq x (car ls)) (remove x (cdr ls)))
          (t (cons (car ls) (remove x (cdr ls))))))

mp-exec というのはEasy-ISLispの拡張関数です。マルチプロセス並列で各関数を実行します。

並列の計算においてはわざと１つ数が少ないものについて解を計算して、そこに抜けておいた数を当てはめてみてセーフならば解とするという方法をとっています。これにより8queensを８つの計算に分割しています。

(mp-create 8)により8個の子Lispを起動させるのですが、メモリ不足のようです。セルの数を半減させたら動作しました。

計測

逐次

並列

う～ん、おかしいですね。並列の方が遅いですね。なぜでしょう？　解の表示をしている部分が遅いのかもしれません。mp-reportという関数を使って子Lispからメインプロセスの端末に表示させているからです。改良の余地ありです。解を表示しないパターンで計測をしてみようと思います。（続く）

参考

M.HiroiさんのISLisp入門記事　http://www.nct9.ne.jp/m_hiroi/clisp/islisp02.html#chap10
Easy-ISLisp https://github.com/sasagawa888/eisl