基本アルゴリズム

  これまで述べたアルゴリズムの, ABCL/fにおける表現は以下のようにな る. まず, 各集合 に対し並列オブジェクトを一つ生成する. 各オブジェ クトは, 求まった集合 の要素を格納するのに加えて, ※で述べた依 存から来る同期を実現するのにも用いる.

インタフェースとしては, そのオブジェクトは, methodとして, 「 が求まったらそれをlistとして返す」というmethod:

(sync-get! s)

と, 「求まった (list)をオブジェクトに格納するmethod:

(sync-put! s v)

を持っている. sync-get!は, synt-put!が実行されるま で値を返さない. このオブジェクトの実現はABCL/fの特徴を活かした記 述を行なっており, 詳細は5.6.6 (2)節で触れる.

さて, そのようなオブジェクトの記述(cky-matrix-element クラス)が あったとする. 実際にアルゴリズムを実行する前に, cky-matrix-elementオブジェクトを各(i,j)の組に対して生成し, 2 次元配列として格納する. 配列はグローバル変数の*cky-matrix*によっ てアクセスされる(すなわち, 配列そのものは各プロセッサにコピーされる. そしてその要素であるオブジェクトは先に述べた方法(D(i,j))で分散配置さ れる). なお, この配列はあらかじめ可能な入力文の最大の長さの分だけ確保 しておき, 各文ごとに作り直すことはしない.

本体の記述は,「各k (i < k < j)に対して, と を sync-get!により取り寄せ, それをもとに を求め, それら を全てmergeして, 求まった値をsync-get! する」というメソッド(※) を書いて, それらを, i,jの全ての組合せに対して並列に(futureという primitiveを使って)実行する.

まず全てのkに対する処理を逐次的に行なう方式を示す. 先に述べたように, kを(i + j)/2に近いものから順に求めていくべきであり, 以下では k0およびk1という二つのパラメータを用意して, それぞれルー プ中でincrement/decrementしていく.

;; Ｓi,j を求めるメソッド (n は入力文の長さ)
;; ただし, 各 Ｔi,k,j (i < k < j)を順に行なう
(defmethod cky-matrix-element non-leaf-process (i j n)
  (declare (fixnum i j n) (reply-type unit))
  (let* ((sij '()))
    (declare ((list fixnum) pij))
    ;; foreach k s.t. (i $<$ k $<$ j)
    ;; k1は (i + j)/2 から1ずつ増やす.
    ;; k0は (i + j)/2 -1 から1 ずつ減らす.
    (do ((k1 (/ (+ i j) 2)       (+ k1 1))
         (k0 (- (/ (+ i j) 2) 1) (- k0 1)))
         ((= k1 j))
         ;; Ｓi,k と Ｓk,j が求まるのを待って取り寄せる.
         (let* ((sik (sync-get! (mref *cky-matrix* i k1 n)))
                (skj (sync-get! (mref *cky-matrix* k1 j n))))
           ;; Ｔi,k,j を求めて Ｓi,j に マージする
           (setq sij (apply-binary-rules sik skj k1 sij gen-edges)))
         (when (> k0 i)
           (let* ((sik (sync-get! (mref *cky-matrix* i k0 n)))
                  (skj (sync-get! (mref *cky-matrix* k0 j n))))
             ;; Ｔi,k,j を求めて Ｓi,j に マージする
             (setq sij (apply-binary-rules sik skj k0 sij gen-edges)))))
    ;; Ｓi,j が求まった(待ってる人たちに通知)
    (sync-put! self sij)))

     図5.7: Ｓi,jを求めるメソッド. 
            Ｓi,jを表すクラス cky-matrix-element に対する
            メソッドとして実現されている.

上で, パラメータi, jは, 求めるべき のi, jを与えている. パラメータnは入力文の長さで, 配列*cky-matrix*にアクセス するために必要である. マクロ:

(mref *cky-matrix* i j n)

によって, を格納するオブジェクト(への参照)を取り出す. したがって, (sync-get! (mref *cky-matrix* i k n))および (sync-get! (mref *cky-matrix* k j n))により, それぞれ , が求まるまで待った 上で, 求まった集合をリストとして取り出す. それらは, sikとskjにbindされる. (apply-binary-rules sik skj k sij gen-edges)は, sikの要素とskjの要素のあらゆる組合せ に 対して, なるsを, 文法表から求め, それがすでに生 成されていなければ, それを に加えて返す. gen-edgesは生成 されたエッジを全て貯めておくためのリストを, ただ一つの要素とするベクタ であり, apply-binary-rulesの副作用として更新される.

これができれば後は, 全てのi, jに対してこれらをfutureを用いて 起動すれば良い. 以下のプログラムでは, タスクを生成する側のボトルネック を避けるために, j - i = gとなるものに対して を求める処理を起 動する, (cky-parse-non-leaves-line g n)という副関数 を書いて, 各g ( )に対して並列に起動するという 2段のタスク生成を行なっている. またcky-parse-leavesは, j - i = 1なる を求める処理を全て並列に起動する副関数である.

(defun cky-parse (sentence)
  (declare ((list fixnum) sentence) (reply-type unit))
  (let* ((n (length sentence)))
    ;; Ｓi-1,i を全て求める処理を
    (future (cky-parse-leaves sentence n) :on (random-pe))
    ;; 上と並行に, Ｓi,i+g, を全て求める処理を, 各gに対して
    ;; 並列に起動する
    (do ((g 2 (+ g 1)))
        ((>= g n))
      (future (cky-parse-non-leaves-line g n) :on (random-pe)))
    ;; 最後に, Ｓ0,n を求めて, 終了をここで待つ.
    (non-leaf-process (mref *cky-matrix* 0 n n) 0 n n)))

(cky-parse-non-leaves-line g n)の定義は以下のようになっている.

(defun cky-parse-non-leaves-line (g n)
  (declare (fixnum g n) (reply-type unit))
  ;; 各 iの組に対し, Ｓi,i+g を求める処理を並列に起動する
  (do* ((i 0 (+ i 1))
        (j (+ i g) (+ j 1)))
       ((> j n))
    (future (non-leaf-process (mref *cky-matrix* i j n) i j n))))

メインルーチンcky-parseにおいて, method起動の返事は, に対してのみ行なっており, それ以外は以下なる場所でも終了待ちをしていな い. これは, を求める処理が終了するためには, 他の全ての を求める処理が終了していなくてはならないため, 明示的に各々に 終了待ちをする必要がないことによる.

一般には, このようにして, method起動の返事に対してどこでも 終了待ち(touch)をしないのは危険なプログラミングスタイルで, 特に理由がない限り, 全ての method起動に対してどこかでtouchを行なうべきである. 今回は, 正しいことが簡単に証明でき, かつ効率改善に寄与することから採用した.