Termination Detection

Here, we show that an automatic termination detection mechanism is implemented at the meta-level of ABCL/R3 using two layers of delegating evaluators. The first one defines each specific termination detection algorithm, and the second one defines the syntax commonly used in all termination detection algorithms. (Figure 12)

  

Figure 12: Delegation paths of evaluators for termination detection

At the syntax layer, we define an evaluator class TD-eval, which simply dispatches forms (fork/wait ...) and (fork ...) to the methods eval-fork/wait and eval-fork, respectively. At the leftmost layer, an evaluator class is defined for each termination detection algorithm. Here, we only present the simplest one in which an acknowledgment message is returned for each fork invocation. Other algorithms--e.g., the one using global weight[9,14]--can be implemented in similar ways. The overview of the algorithm is as follows (operations written in the slanted font are performed at the meta-level): (1) A method/function is invoked. (2) A reply box is created for each child. (3) A child (sub-computation) is forked. The reply box is passed onto the child along with the invocation. (4) It waits for acknowledgment messages from all of its children. (5) Each child returns an acknowledgment message when it finishes. (6) When all acknowledgment messages are collected, it returns an acknowledgment message to its own parent. The evaluator for this termination detection algorithm can be defined as follows. The method meta-args is customized to send a reply box along with base-level arguments; and the method eval-entry is customized to add special behavior at the beginning and the end of a base-level method/function execution.

(defmethod ack-TD-eval eval-entry (exp env)
;; create a location for created reply boxes
(let* ((new-env
(extend-env env :meta 'rboxes '()))
;; run the body of the method
(result
(eval-entry super exp new-env)))
;; wait for termination of children
(dolist (rbox (lookup-meta 'rboxes new-env))
(touch rbox)) ; (4)
;; notify its parent of the termination
(reply (lookup-meta env 'ack) t) ; (5,6)
result))

(defmethod ack-TD-eval meta-args
(type method target args options env)
(let ((margs (meta-args super type method
target args options env)))
(cond ((eq type 'fork)
;; create a reply box
(let ((rbox (make-reply-box))) ; (2)
;; and remember it in the environment
(push-meta-env env 'rboxes rbox)
(list* 'ack rbox margs))) ; (3)
(t margs)))) ; for the other forms

(defmethod ack-TD-eval eval-entry (exp env) ;; create a location for created reply boxes (let* ((new-env (extend-env env :meta 'rboxes '())) ;; run the body of the method (result (eval-entry super exp new-env))) ;; wait for termination of children (dolist (rbox (lookup-meta 'rboxes new-env)) (touch rbox)) ; (4) ;; notify its parent of the termination (reply (lookup-meta env 'ack) t) ; (5,6) result)) (defmethod ack-TD-eval meta-args (type method target args options env) (let ((margs (meta-args super type method target args options env))) (cond ((eq type 'fork) ;; create a reply box (let ((rbox (make-reply-box))) ; (2) ;; and remember it in the environment (push-meta-env env 'rboxes rbox) (list* 'ack rbox margs))) ; (3) (t margs)))) ; for the other forms