Common Lisp Sampling in Parallel

Tag: lisp , common-lisp , parallel-processing , probability Author: xubing1973415 Date: 2012-02-18

Assume that I want to draw samples from some probability distribution. In the case below I draw some uniformly distributed rv's between 0 and 1 for 10000 times. I do not care about the ordering of the random samples in the vector, after all they are random.

(setf my-vec (make-sequence 'vector 10000 :initial-element 0))
(loop :for i :from 0 :to 9999 :do
   (setf (svref my-vec i) (random 1.0)))

I have a multicore machine and I want to implement the above code in parallel. (i.e. assuming I have 4 cores, sampling 2500 in one core and at the end appending all samples in to one single vector. I have asked before about Common Lisp Parallel Programming here. Assuming that I am a total newbie in CL and programming in general what should be my approach to this problem? I do not require advanced characteristics in parallelization, I just want to distribute the computational load of the sampling to machine cores equally. If you can point out some steps to do for parallelization or some online tutorial stuff that I can benefit from that would be really nice. Thanks a lot in advance.

Best Answer

You need a Common Lisp implementation which is multi-core capable. Examples are CCL, LispWorks and on some platforms (IIRC) SBCL.

A simple example using LispWorks 6.1 and its multiprocessing capabilities follows. It uses a construct called a barrier. Processes wait on a barrier until enough processes arrive. Here it means that enough threads have finished their vector initialization.

The typical function to start a thread is PROCESS-RUN-FUNCTION.

(defun make-random-vector (&key (size 10000) (n-threads 4))
  (let ((vector  (make-sequence 'vector size :initial-element 0))
        (barrier (mp:make-barrier (1+ n-threads)))
        (delta   (truncate size n-threads)))
    (loop for i below n-threads
          do (mp:process-run-function
              "init"
              nil
              (lambda (barrier vector start end)
                (loop for i from start below end do
                      (setf (svref vector i) (random 1.0)))
                (mp:barrier-wait barrier :pass-through t))
              barrier
              vector
              (* i delta)
              (+ delta (* i delta))))
    (mp:barrier-wait barrier)
    vector))

comments:

This is a great example. Question: Is there any slowdown b/c each thread is writing to the same array? Would it be any faster if separate arrays were created for each thread, and then joined at the end?
@claytontstanley: definitely, that makes sense to try. I thought about that, but I did not want to make the code too complicated for an example. The basic idea to partition the work, start threads for the work and to use a barrier for synchronization is already present in the example.
@RainerJoswig, I am using CCL. Will it have any specific disadvantages when compared to LispWorks? Will writing in CCL be as compact as above code? Thanks a lot.
@YBE: the main disadvantage of CCL compared to LispWorks might be that it provides less detailed built-in library support for multi-processing, IIRC.