PLISP Users' Manual

Arzit Yannai

Courant Institute, N.Y.U.

251 Mercer Street

New York, N.Y. 10012

Ultracomputer Note #75

November, 1984

ABSTRACT

This report describes an experimental implementation of PLISP, a parallel
version of LISP. The implementation is written in YLISP, a dialect of
LISP, which can simulate multiple processors on the VAX.
Commimication between parallel processors is via common structures and
message queues

1. Introduction

The PLISP system described here is an expansion of the YLISP written by
Isaac Dimitrovsky. It is a parallel language that allows the user to create
processes at any point in the program, and to set them up to evaluate LISP forms.
The processes can commimicate with each other using slots, which are argtmaents
that belong to the processes. Here are some helpful instructions about how to use
the PLISP simulator.

1.1. Running the PLISP simulator

The PLISP simulator is run in the YLISP environment. Therefore, one must
first enter the YLISP, using:

/a/lisp/dimitrov/sl/lnoc

When this is done a * % ' sign appears, and so the user can load the compiled
PLISP simulator. This can be done using:

(iload "7a/ultra/yannai/sim.o")

Both files are on ACF4. A complete description of PLISP can be foimd in
/a/ultra/yannai/th/thesis append. a append. b append. c append. d.



In order to run the simulator, one must call its main function "simulator",
with the form he wishes to evaluate and some other pairameters:

(1) Processor-no: the number of processors that are available.

(2) Hash-size: the number of entries that the Waiting hash table will have. (This
number is a function of the number of expected processes).

(3) Step-size: the nimiber of execution steps given to a process.

(4) Context-switch-delay: the estimated number of steps required to do a context
switch.

(5) Form: the form to be evaluated, a quoted YLISP expression.
A typical call to the simulator will be:

(simulator 10 10 100 '(myprog varl .... vam))

2. THE PLISP PRIMITIVES

The PLISP primitives are divided into several groups, Each of which are
treated in a separate subsection below.

2.1. Checking primitives

( me-p )

Returns the process in which it is evaluated.

( status proc)

RetiuTis the status of process proc: dead, executing or waiting.

2.2. Functions on process definitions

( newproc name n prio)

When there is a need to create a new process, this function is used:

(1) name will be the name of the process for further reference to this process. It
must be a string.

(2) n indicates that the process will have n+1 slots (this number can be
expanded later on in the program), numbered 0..n. n must be an integer,

(3) prio is the priority of the process. The priority is determined here for the
whole life of the process, according to any decision of the user. It must be an
integer.

( setup-p proc form blink ((procl slotl)(proc2 slot2) ..(prod sloti)))

Sets up the given process to evaluate the given form. The process
immediately starts executing. The blink argument allows the process to look for

Page 2



bindings of nonlocal variables in other process. The effect of the ((proc slot) ..)
arguments is to execute (sendval val ((procl slotl)(proc2 slot2) ..) when the
process completes the evaluation of form. The blink will usually be (me-p) and
the form will be quoted.

Important: when setting up a process to evaluate a form, the user must make
sure that the process is dead.

( allocslots proc n)

Causes the allocation of n more slots to proc. This function can be used in
any point in the program, and every process can allocate slots to any other
process, proc must be already created when this function takes place, and n must
be an integer.

2.3. Commiinication and Synchronization primitives

As mentioned above, the various processes can communicate via slots. The
slots are arguments that belong to the processes.

The communication rules are: each process can send a message to all other
processes, and can read only the messages that were sent to his slots. Moreover,
a process must make sure that a slot is not empty before he attempts to read a
message sent to him.

( sendval value ((procl slotl)(proc2 slot2) ..)) _

Attaches value to the end of the slots in the given processes. A process can
send a message to every existing process at any point in its code evaluation.

Before a process is allowed to read a message from one of his slots, he must
make sure that a message was really sent to him . If the slots he wished to read do
contain a message, he can go on and read them. Otherwise he must wait until a
the messages are sent:

( updatevals (slotl slot2 .. sloti))

Waits for all the given slots in the process in which it is evaluated to be
filled. If the slots are empty, the process will wait until some other process fills
them. When all the slots get a value, the execution will continue.

( apdateoneval (slotl slot2 . . sloti))

Waits for one of the given slots in the process in which it is evaluated to be
filled. If all slots are empty the process will wait until at least one slot is filled.
This primitive returns one of the slots which was updated.

( getval slotno)

After either an (updatevals..) or (updateoneval ..) functions were
performed, it is clear that the slots are not empty, so the process can read the

Page 3



messages sent to him. This function returns the first value of the given slot and
removes it from the slot.

( isempty slotno)

Allows to a process to enquire whether a certain slot is empty or not. In
case it is empty - it returns true, nil otherwise.

2.4. Completion of processes

There are two ways to finish/abort the execution of a process:

( complete proc value)

Aborts the process proc, and removes it from the system, value is sent to the
processes indicated when proc was set up (using setup-p). A process can complete
any other process in the system, including itself. When a process is completed it
can be set up again to evaluate another (or the same) LISP form.

( kill-p proc)

Aborts the execution of process proc, sets it to dead, and does the same
recursively to all processes created by proc. A process can kill any other process
in the system, exclusively himself (cannot commit suicide). When a process is
killed it cannot be set up again to evaluate another form.

3. ERROR HANDLING

The PLISP simulator provides checking of the validity of the actual
parameters given to any one of the PLISP primitives described above.
When an error occurs, the evaluation of the form will not be aborted, but a
proper message will tell the user what was wrong in his parameters. It might
happen that the evaluation will abort at a later stage because of that wrong
parcuneter.

When there is a mistake that the simulator can not detect (in the YOSP
code), the execution might abort, with a message telling in what process
happened the error, what was the form and parameters evaluated by this process,
and where this error occurred.

Another source of error that is not detected by the simulator is a cycle of
blinks : the blink of PI is P2, and the blink of P2 is PI. In this case, there will be
an infinite search for a nonlocal variable that is not in either PI or P2.

4. STATISTICS

The simulator provides a small statistics system that can give the user an idea
of what was going on in the simulator during the last session. A detailed
information about the computation of those figures are available in section 2 of
the paper. We will list here only the titles:



Page 4



1) Number of processes generated in the session.

2) Number of times processes entered a waiting state.

3) Maximum number of processes in the system at the same time.

4) Number of messages that were sent.

5) Number of groups of messages that were sent.

6) Number of messages that were read.

7) Number of swaps between two prrocesses (when all processors are busy) .

8) Toteil number of steps used to swap processes.

9) Number of processors in the system.

10) Number of steps used in the session.

11) Processor utilization.

12) Termination time - single processor.

13) Termination time - multiple processors.

14) Speed-up factor.

The statistics shown at the end of each session might change slightly due to
changes in the number of steps given to each process. The reason for that is: the
change in the number of the steps might affect the order of the execution of the
various processes, which will affect the overall number of steps used, the number
of swaps between two processes, number of times processes entered a waiting
state, etc.

5. SUGGESTIONS TO THE USER

A good suggestion to the user will be to have a look at the examples of
PLISP programs given in section 3 of this paper. This will provide the user with a
better feeling of how to write programs in PLISP and nm them in the simulator.

In order to be able to keep track of the computation, it is recommended to
give a big Step-size (say 100000). In this situation, the execution is sequential.

A very small step (e.g. between 1 and 50) will cause thrashing of the
simulator, and so the execution will be inefficient. Therefore, it is most
recommended that the user will not give the processes such a small steps number,
unless he has a special purpose for doing that.



Page 5