Realization of Parallel Lisp using Multiprocessing

Challenge

Last year, I was immersed in implementing parallel Lisp using multithreading. While it did work, its speed was disappointing. The parallel features implemented using Pthreads could not fully exploit the capabilities of multi-core CPUs due to memory contention. This time, I decided to tackle parallel Lisp using multiprocessing. The basic parts are functioning, and it seems that the benefits of parallelism can be realized.

Idea

I’m considering the following syntax:

;; idea memo

(mp-create 3)

(defun tarai (x y z)
    (if (<= x y)
        y
        (mp-call tarai (tarai (- x 1) y z) 
                       (tarai (- y 1) z x)
                       (tarai (- z 1) x y))))

(mp-close)

(mp-create n) — Launches n child Lisps in separate processes.

(mp-call fun arg1 arg2 … argn) — Computes arg1 to argn in n child Lisps and passes the results to fun for computation.

(mp-close) — Terminates n child Lisps.

The Tarai function (a recursive function) performs extensive recursion. Processing it in parallel should lead to considerable speedup. When operated in multiprocessing mode, the execution speed remains the same as when executed individually. This is because memory spaces are independent, thus avoiding memory contention, and the performance of multi-core CPUs is utilized.

fork, exec, pipe

The launch of child Lisps employs Unix’s fork. Communication between child and parent Lisps utilizes pipes. Child Lisps connect standard input/output to pipes. Exec is used to launch child Lisps, ensuring separate memory spaces.

The main challenge was communication via pipes. It was discovered that stdio has buffering constraints. Therefore, child Lisps are launched with a custom -p option, managing input buffering independently. The (mp-call) function passes this data to the extension function (mp-exec). This function converts S-expression data into strings, dividing them to fit within buffering constraints, and sends them to child Lisps.

The parent Lisp receives the computation results from child Lisps via pipes as strings, which is done asynchronously.

Computational Experiment

The following code demonstrates the experiment of dividing ‘(tarai 12 6 0)’ into strings of 7 characters each and passing them to child Lisps for computation.

Child Lisps perform computations at a speed comparable to that of the parent Lisp.

Refinement

It seems that the basic idea worked well. Mechanisms for properly converting S-expressions into strings for transmission to child Lisps, and aggregating results to convert them back into S-expressions are necessary.

The (load fn) function ensures that if child Lisps are running, they also load the same file, allowing parent and child Lisps to share the same code.

Recollection

In the 1980s and 1990s, I admired the parallel Lisp machine developed by NTT, TAO/ELIS. Today’s general-purpose CPUs are very powerful. With them, it should be possible to create parallel machines that far surpass those of that era. I’m very excited about this prospect.