[Gcl-devel] Re: Parallel GCL

[Camm Maguire]

Greetings, and thanks for this.

Thought of one other major snag regardless of fork/thread approach:
non-local flow control.  What can be done with

(block foo
        (let ((x (block bar 
                        (if (< (random 10) 5) 
                                (return-from bar 1)
                        (return-from foo 2))))
              (y (random 10))) ...))

other than to put an unwind-protect around the let ensuring
thread/process cleanup, devising some signal that the return value is
to be interpreted as a non-local exit, then passing the frame address
through the pipe to the parent?  How utterly awful. :-)



"Warren A. Hunt Jr." <address@hidden> writes:

> Hi Camm,
> 
> I'm glad to hear you thinking about threads.  The multiprocess (fork)
> approach seems like it may work for course parallelism, but not the
> kind of parallelism David Rager (a student of mine) and I have been
> working on a bit.
> 
> David has been attempting to parallelize ACL2 computations using
> OpenMCL.  After various conversations with Gary Byers (the "Camm
> Maguire" of OpenMCL), we learned that Gary had to very carefully
> protect a number of internal data structures for use within a parallel
> Lisp environment.  In OpenMCL, since even a hashtable read may trigger
> a GC, it has to be protected with a lock.  Gary said he had to think
> carefully about every Lisp structure and how threading might cause
> interference.  We have also been working with Gary for a procedure
> that permits killing a thread we no longer need.  This can occur in a
> parallel AND operation when one of the AND argument evaluated to NIL,
> in which case we would to stop the evaluation of the other arguments
> to the AND.  I'm sure that you have already thought of this and many
> other things.
> 

My very crude understanding here is that writes to any global
structure (which in the case of lisp is the entire heap as well as the
lisp stacks (in GCL)) must be locked to ensure correct functioning,
but that we may be able to assert correct functioning only when the
code in question is well-defined.  "Well-defined" here means that the
branches of the let only write to the heap via binding variables with
local scope, or special variables, otherwise the results of the code
as written are unspecified as the definition of let explicitly does
not determine the order of branch binding.

A few examples:

Well-defined:

(defvar *foo*)
(let ((x (let ((*foo* 3)(x 4)(z (make-list 10)) (setq x 5) 
                                (* x (setf (nth 5 z) 2) *foo*)))
      (y (let ((*foo* 6)(x 2)(z (make-list 10))) (setq x 7) 
                                (* x (setf (nth 5 z) 3) *foo*)))))
 (values (x y)))

Ill-defined:

(defvar *foo*)
(let ((z 2) (zz (make-list 10)))
        (let ((x (let ((*foo* 3)(x 4)) (setq z 5) (* z 
                                                     (setf (nth 5 zz) x)
                                                      *foo*)))
              (y (let ((*foo* 6)(x 7)) (setq z 10) (* z 
                                                     (setf (nth 5 zz) x)
                                                      *foo*))))
 (values (x y))))

So in sum what I'm suggesting is that we don't even try to protect the
latter, as it is ill-defined to begin with, we only need to guarantee
that the former will work correctly under parallelism.  If this
assumption is correct, then we only need to lock gc (or just the
sweep), and the effects on the global structures normally induced by
let bindings (i.e. value stack increments for lexicals, something more
complicated for specials), modulo the flow control issue I mention above.
(Now that I think about it, perhaps the non-local flow control or some
subset thereof might fall into the 'ill-defined' category too.)
        
> I would like to point out that within a few years, you can expect to
> have four to sixteen way processors with shared memory in a deskside
> or desktop computer.  With that in mind, I hope GCL will eventually
> offer some kind of native thread support.
> 

Sure would be a lot easier if we could magically define a purely
functional subset of lisp to support in this regard.  The intention of
setq and go did not appear designed with the hardware capabilities
you mention above being even remotely feasible.  

BTW, looked at the SBCL page on this:

=============================================================================
Special Variables

The interaction of special variables with multiple threads is mostly as one 
would expect, with behaviour very similar to other implementations.

    * global special values are visible across all threads;
    * bindings (e.g. using LET) are local to the thread;
* threads do not inherit dynamic bindings from the parent thread

The last point means that

     (defparameter *x* 0)
     (let ((*x* 1))
       (sb-thread:make-thread (lambda () (print *x*))))
     

prints 0 and not 1 as of 0.9.6. 
=============================================================================

This appears to arise because each special has its own binding, and a
super global binding area, as opposed to the spaghetti-stack concept.
This appears quite undesirable from what I can see.

Finally, your idea of parallelizing AND is quite interesting, but I
think it makes even stronger no-side effect assumptions than I
proposed above in the 'well-defined' paragraph.  I.e., the code below
is perfectly well-defined lisp as far as I can see

(let ((x 2)) (and (= (incf x) 3) (= (incf x) 4)) x)

but cannot be parallelized to my limited understanding.  So it appears
that you might already be working with a functional subset of lisp in
mind, which is not surprising knowing as I do that you are using
ACL2.  The question is, can a general common lisp system like GCL
support language subsets in a meaningful and useful way?

Take care,


> Cheers,
> 
> Warren
> 
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah