Blueprint for Distributed Parallel Lisp

Blueprint for Distributed Parallel Lisp

Easy-ISLisp aims to add distributed parallel functionality in version 5.0. In version 4.20, basic communication between a parent Lisp and child Lisp has been achieved. We are currently considering additional functions to control parallel computation.

Ideas

Essentially, the parent Lisp instructs the child Lisp to start computations, and the child Lisp sends the results back to the parent Lisp upon completion. Separately, we are thinking about enabling control commands for interruption, pause, and resume from the parent Lisp. We plan to use a separate buffer for communication, which will be monitored by a thread. When a message is received, a corresponding flag will be set in a global variable based on the message content. The function checkgbc() will monitor the remaining cell count for garbage collection and also check these flags, thereby controlling the child Lisp. Additionally, the child Lisp will send messages to the parent Lisp regarding the progress of computations, which will be similarly monitored by a thread. This way, the parent Lisp can understand the status of the child Lisp.

Immutability

While global variables can be defined using defglobal, they will not be used in parallel computations. To modify global variables, information must be shared with other processes, which could complicate things. By restricting the use of global variables and modifications through setq, we aim to implement distributed parallel computing using functional programming.

Side Effects

There may be instances where we want to output intermediate values to the terminal from the child Lisp. The extended function (dp-report str) is used to transmit a string to the parent Lisp process. When outputting the calculation result to the parent terminal, you can output it to the string stream using format, and then use this dp-report to output it to the parent terminal.

Example:

(dp-report "message to parent terminal")

Communication Protocol

Child Lisp

When a computation request is received from the parent Lisp, the Busy flag is set to on and computation begins. During this time, if there are instructions from the parent Lisp, a separate thread will receive them. The instructions control stop, pause, and resume. Once the computation is finished and the response is sent back to the parent Lisp, the flag is set to off.

• stop: 0x11
• pause: 0x12
• resume: 0x13
• file transfer: private-function (dp-receive fn)

The pause and resume commands are intended to be used in the future when mutable data structures are introduced, allowing for temporary suspension during setq operations. The stop command is planned to be used in the parallel construct dp-part.

Parent Lisp

The parent Lisp receives messages from the child Lisp. In addition to computation results, it also receives messages to be output to the parent Lisp’s terminal, so a protocol is established.

• Message: 0x02, message, 0x03
• Error: 0x15
• Computation results: non

File Operations

• (dp-transfer fn) Transfers the file fn from the parent Lisp machine to all child Lisp machines.
• (dp-load fn) Loads the file fn on all child Lisp machines.
• (dp-compile fn) Compiles the file fn on all child Lisp machines.
• (dp-system n exp) Evaluates the S-expression exp on the nth child machine.

Error Handling

If an error occurs in the child Lisp, the child Lisp will wait in network mode for REPL. At the same time, it will send an error message to the parent Lisp. When the parent Lisp receives the error message, it will call the error handling routine in the parent Lisp.

Startup Options

To start as a distributed parallel child machine, use the -n option. This enables communication with the parent machine via TCP/IP.

eisl -n

Initial Setup

In the parent machine, provide the IP addresses of child machines as strings and establish TCP/IP communication. Child machines are identified by non-negative integers ranging from 0 to n.

Example

(dp-create "127.2.1.9" "127.3.1.10")

Parallel Syntax

I’m planning the following parallel syntax:

• (dp-let forms body): Distributed parallel version of the let syntax.
• (dp-call fun f0 f1 …fn): Computes f0 through fn in distributed parallel and passes them to the function fun.
• (dp-exec f0 f1 …fn): Computes f0 through fn in distributed parallel and returns the final value.
• (dp-part t f0 f1 … fn): Computes f0 through fn in distributed parallel; stops computation if any result is non-nil and returns that result.
• (dp-part nil f0 f1 … fn): Computes f0 through fn in distributed parallel; stops computation if any result is nil and returns nil.