PICT LANG の並列化

SICP の Picture language を Kent Dybvig の THE SCHEME PROGRAMMING LANGUAGE SECOND EDITION の 3.8 章に載っている lwp (Light Weight Process) を利用して並列化してみました.

準備

lwp については別に説明します.

線を引くたびに, プロセスの切替が起こるように draw-line の適当な場所に (lwp-pause) を挿入します.


(define (draw-line w p1 p2)
  (let* ((x1 (xcor-vect p1))
         (y1 (ycor-vect p1))
         (x2 (xcor-vect p2))
         (y2 (ycor-vect p2)))
    (lwp-pause)                    ; ここでプロセスが切り替わる
    (gplt-draw-line w
                    (inexact->exact x1)
                    (inexact->exact y1)
                    (inexact->exact x2)
                    (inexact->exact y2))))

(define (apply-painter win painter width height)
  (let ((frame  (make-frame win (make-vect 0.0 0.0)
			    (make-vect width 0.0)
			    (make-vect 0.0 height))))
    (painter frame)))

リスト: 並列版 draw-line と apply-painter

apply-painter は画板に合わせたフレーム(frame)を作って paiter に渡します. (そして painter は frame を受けとるとそこに描画します.)

今回は次の 3 つのペインタに頑張ってもらいましょう.


(define clw (cross-limit (compose-painter border wave) 3))
(define csw (corner-split wave 3))
(define sqx (square-limit x-mark 4))

3 つのウィンドウに同時に描画

まず手始めに 3 つのウィンドウにそれぞれペインタを割り当てて実行してみましょう.


(lwp (lambda () (apply-painter 1 clw 4096 4096) (lwp-exit)))
(lwp (lambda () (apply-painter 2 csx 4096 4096) (lwp-exit)))
(lwp (lambda () (apply-painter 3 sqw 4096 4096) (lwp-exit)))
(lwp-start)

リスト: 3 つのウィンドウに同時描画.

上のリストを実行してみると次の図のようになります.

20%
50%
完成！
図: 描画の様子. 左から, clw, csw, sqx. 上から下へ時間が流れてます.

ペインタを並列化する

ここからが本番です.

順番に依存しないて手続呼び出しは並列化できるわけですが pict-lang を詳しく調べてゆくと beside 手続と below 手続が並列化できるのがわかります. これらの手続はそれぞれフレームを左右/上下に二分割して引数に与えられた二つのペインタを割り当てるペインタを生成しますが, この分割されたフレームに対するベインタは並列に呼び出すことができます.


  (define (beside painter1 painter2)
    (let ((split-point (make-vect 0.5 0.0)))
      (let ((paint-left
             (transform-painter painter1
                                (make-vect 0.0 0.0)
                                split-point
                                (make-vect 0.0 1.0)))
            (paint-right
             (transform-painter painter2
                                split-point
                                (make-vect 1.0 0.0)
                                (make-vect 0.5 1.0))))
        (lambda (frame)
          ; 二つのぺインタを同時に起動
          (lwp (lambda () (paint-left  frame) (lwp-exit))) 
          (lwp (lambda () (paint-right frame) (lwp-exit)))
        ))))

  (define (below painter1 painter2)
    (let ((split-point (make-vect 0.0 0.5)))
      (let ((paint-below
             (transform-painter painter1
                                (make-vect 0.0 0.0)
                                (make-vect 1.0 0.0)
                                split-point))
            (paint-above
             (transform-painter painter2
                                split-point
                                (make-vect 1.0 0.5)
                                (make-vect 0.0 1.0))))
        (lambda (frame)
          ; 二つのぺインタを同時に起動
          (lwp (lambda () (paint-below frame) (lwp-exit)))
          (lwp (lambda () (paint-above frame) (lwp-exit)))
        ))))

リスト: 並列化 beside と並列化 below

さて, ここで cross-limit をよく見てみると,


(define (cross-limit painter n)
  (if (= n 0)
      painter
      (let ((top    (beside painter (cross-limit painter (- n 1))))
            (bottom (beside (cross-limit painter (- n 1)) painter)))
         (below bottom top))))

リスト: Picture language の corss-limit の定義

この手続は再帰的に beside と below を呼び出してゆきます. beside と below が上の様に並列化したものであれば, この cross-limit は再帰的に呼ばれるたびに次々とプロセスを生成するペインタを生成します.

それでは clw = (cross-limit (compose-painter border wave) 3) が描かれてゆく過程をお楽しみ下さい.

20%
40%
60%
完成！
図: 描画の様子. 左が通常版. 右が並列版. 上から下へ時間が流れてます.

まとめ

ここで取り上げたlwpはそれぞれのプロセスが自分で lwp-pause を呼び出すことによって制御を他のプロセスに移す方式(non-preemptive multi process)ですが, このような簡単な仕組みでも有効に活用すれば便利なこともある. (描画の全体像をいちはやく見ることができたりなど)

また, プリエンプティブマルチプロセスと違ってプロセスの切替えが完全に自分のコントロールの下におかれるので排他処理/同期などの問題が自然と解決する.... かな.

lwp

最後にこの例題で用いた lwp のリストをつけます.


(define lwp-list '())
(define lwp-tail '())
(define lwp-max 0)

(define (lwp-init)
  (set! lwp-list '())
  (set! lwp-tail '())
  (set! lwp-max 0))

(define (addq e)
  (if (null? lwp-tail)
      (begin
        (set! lwp-tail (cons e '()))
        (set! lwp-list lwp-tail))
      (begin
        (set-cdr! lwp-tail (cons e '()))
        (set! lwp-tail (cdr lwp-tail))))
  (set! lwp-max (max lwp-max (length lwp-list))))

(define (headq)
  (let ((e (car lwp-list)))
    (set! lwp-list (cdr lwp-list))
    (if (null? lwp-list)
        (set! lwp-tail '()))
    e))

(define (lwp thunk)
  (addq thunk))

(define (start)
  (wait))

(define (wait)
  (pause)
  (if (not (null? lwp-list))
      (wait)))

(define (restart)
  (let ((next (headq)))
    (next)))

(define (pause)
  (call/cc (lambda (k)
             (lwp (lambda () (k #f)))
             (restart))))

(define lwp-start start)
(define lwp-pause pause)
(define lwp-exit  restart)

リスト: lwp システム. Kent Dybvig の THE SCHEME PROGRAM LANGUAGE から拝借.

動かしてみたい？

ここに示したものはすべて R5RS 準拠なのでどの処理系でも変更なく動くと思いますが (call/cc は長い名前にする必要があるかも知れません), 表示のヘルパプログラムも含めた Gauche 用のモジュールを GGC 内の ggc/lwp と ggc/gnuplot に入れといたのでアーカイブをダウンロードしてみて下さい. この例題は ggc/gnuplot/example.scm です. 質問/突っ込みなどはメールか WiLiKi でお願いします.

skimu@mac.com

; $Id: parallel-pict.html,v 1.8 2003/03/22 05:26:43 skimu Exp $