• MEMO
• SYMBOL
• FOLDER_NAME

The type MEMO is a pointer to a block of dynamic storage.
A SYMBOL is an unsigned long integer which is intended to be unique over the execution of the program. It is used to represent the name of a data structure and forms part of a folder name.
The type FOLDER_NAME is a fixed sized folder name. It is a C structure:

typedef struct Folder_Name {
SYMBOL S;
unsigned long int X[NUM_X];
} FOLDER_NAME;

The S member represents the name of the data structure that this folder is part of, e.g. the name of an array. For an array, the X member contains the indices. The system includes a definition for NUM_X in the header file. We provide NUM_X equal to three, but it can be changed if the application demands it.

SYMBOL memo_symbol()
Memo_symbol generates a unique SYMBOL. It will not be the same as the value returned by any other call to memo_symbol(\or to any "small" integer (unless the system has run for a very long time). Small integers are available for predefined symbols.

FOLDER_NAME key; char *block_addr; int len;
MEMO memo_get(key)

FOLDER_NAME key;
MEMO memo_get_copy(key)

FOLDER_NAME key;
MEMO memo_get_skip(key)

FOLDER_NAME key;
MEMO memo_get_copy_skip(key)

FOLDER_NAME key;
void memo_free(memo)

MEMO memo;
int memo_len(memo)

MEMO memo;

Memo_write puts a memo into a folder named by the key. If a folder by that name does not already exist, one is created. The contents of the memo are the len bytes beginning at address block_addr.
Memo_get returns a pointer to a memo removed from the folder named by key. The length of the body of the memo m can be found by calling memo_len(m). Memo_get blocks until there is a memo present in the folder. (If the folder does not already exist, it is created.)
Memo_get_copy is the same as memo_get except that the memo is not removed from the folder; it is copied and the copy is returned. If there is more than one memo in the folder, a copy of one of them is returned.
Memo_get_skip is a non-blocking version of memo_get. If there is no memo immediately available, memo_get_skip returns NULL. And memo_get_copy_skip is the same as memo_get_copy except that if there is no memo immediately available, memo_get_copy_skip does not block but returns a NULL pointer.
All forms of memo_get return a pointer to a block of dynamic storage. The contents of the memo are accessed through the pointer. For example:

struct something{int member;} *p;

FOLDER_NAME whatever;

...

p = (struct something *) memo_get(whatever);

... p->member ...

Memo_free frees the dynamic storage that a memo occupies.

FOLDER_NAME key_list[]; int len_key_list, *one_found;
MEMO memo_alt_skip(key_list,len_key_list,one_found)

FOLDER_NAME key_list[]; int len_key_list, *one_found;
MEMO memo_strict_alt_skip(key_list,len_key_list,one_found)

FOLDER_NAME key_list[]; int len_key_list, *one_found;

Memo_alt is a version of memo_get that returns a memo taken from one of a list of alternative folders. Parameter key_list points to an array keys, the names of the folders to be examined. The length of the list of keys is len_key_list. As with memo_get, memo_alt blocks until a memo can be returned.
Memo_alt_skip will return NULL if no memo was found in any of the specified folders. Result parameter one_found will give the index in key_list of the name of the folder from which the memo was taken, or minus one (-1) if no memo was found (by memo_alt_skip).

Memo_strict_alt_skip is a variant of memo_alt_skip. The distinction is this: alt_skip will not return NULL if one of the folders named has a a memo in it from the time alt_skip is called until it returns; that is, alt_skip is required to look in each folder before returning NULL, and if one of the folders has a memo in it when alt_skip looks, alt_skip is not allowed to return NULL. Memo_strict_alt_skip will not return NULL unless there is some instant of time between its call and return when none of the folders contains a memo; that is, strict_alt_skip behaves as if it looks in all folders simultaneously.

FOLDER_NAME key1, key2; char *block_addr; int len;
Memo_write_delayed behaves like memo_write(key2, block_addr, len) with the following difference: although memo_write_delayed returns immediately, the memo is not actually delivered until one or more memos are present in the folder named key1.

int len;
void memo_put(key,memo)

FOLDER_NAME key; MEMO memo;
void memo_put_delayed(key1,key2,memo)

FOLDER_NAME key1, key2; MEMO memo;
void memo_replace(memo)

MEMO memo;
FOLDER_NAME *memo_key(memo)

MEMO memo;

These procedures will link a memo into the system queues that a user program retains a pointer to. In shared memory implementations, the system may deliver the memo to another user. These routines are therefore not safe - the sender can easily cause mischief to the system or the receiver; they are provided to increase efficiency.
Memo_put is the same as memo_write, except \ that the already existing memo data structure is used, rather than a new one being created.
Memo_put_delayed behaves like memo_put(key2,memo) with the following difference: although memo_put_delayed returns immediately, the memo is not actually delivered until one or more memos are present in the folder named key1.
Memo_alloc allocates a Memo structure of the specified length. It can be used to avoid double copying, first into a user buffer and then into a memo. It should be placed in a folder by calling memo_put or memo_put_delayed.
Memo_replace replaces the memo in the folder it was taken from. It is undefined if the memo was created by memo_alloc.

Memo_key returns a pointer to the name of the folder a memo was removed or copied from by memo_get... or memo_alt.... This will be a field of the memo's header; the pointer should not be used after the memo has been freed, replaced, or put. Assigning indirectly through this pointer may make memo_replace malfunction.
For example:

FOLDER_NAME keys[2],from;

MEMO m;

...

m = memo_alt(keys,2,&i);

from = *memo_key(m);

/*although from = keys[i] would work as well*/

...

int num_workers, argc; char **argv;
int memo_get_my_id()
int memo_num_workers()
Memo_init initializes the memo system. It should be called first in main()
Memo_exec forks num_workers+1 processes. The main process, which executed this procedure, is assigned the number 0 and executes the procedure "boss(argc,argv)". The worker processes are assigned the numbers 1 through num_workers and execute procedure "worker()". Memo_exec only returns when the boss and all worker subroutines have returned. Memo_get_my_id returns the number assigned the process by the memo system.
Memo_num_workers returns the total number of workers started by memo_init()

Named Objects. A folder that holds at most one memo can represent a dynamically allocated object on a heap. Instead of pointers to the objects, we use folder names.

Arrays. Arrays of shared objects may be created similarly. The element a[i,j] can be stored in a folder whose name, key, is constructed thus:

FOLDER_NAME key;
SYMBOL a;
...
a = memo_symbol(\
key.S = a;
key.X[0] = i;
key.X[1] = j;
key.X[2] = 0;

Locked data structures. Shared records are accessed by getting them from their folders, examining and updating them, and putting them back. While the record is being updated, its folder is empty, and any other process trying to access it will have to wait; the records are implicitly locked. The following exemplifies operations on shared records:
FOLDER_NAME obj_name;
OBJECT *p;
...
p = (OBJECT *) memo_get(obj_name);
... /* operate the object p */
memo_replace(p);

Locks. Naturally, an explicit lock can simply be represented by an empty memo in a folder.

FOLDER_NAME lock;
MEMO q;
...
memo_write(lock,"",0);
...
q = memo_get(lock);
... /* perform critical section */
memo_replace(q);

Semaphores. The simplest implementation of a counting semaphore is identical to a lock, except that to initialize the semaphore, a process places as many empty memos in the semaphore's folder as initial count.
Unordered queues. A folder is an unordered queue, so if order is not vitally important, processes can communicate simply by passing memos through a folder.

Job Jar. An important use of an unordered queue is as a job jar. The memos in the job jar indicate tasks to perform. Whenever a process requires more work to do, it pulls a memo out of the job jar. Whenever a process creates more work to do, it drops memos in the job jar. It is often convenient to have one job jar for each process and one common jar for all. The individual job jars are used for operations that must be performed by a particular process, e.g. file I/O - a file is typically open in only one particular process.
Memo_alt can be used to get a memo from either the local job jar or the common one.

Futures and I-Structures. A future is an assign-once variable used to communicate between a producer (typically a subroutine) and a consumer (its caller). Both the producer and consumer may run in parallel, with the consumer only being delayed if it attempts to fetch from the variable before it has been assigned. An I-structure (an "incremental structure") is a collection (e.g. an array) of futures. I-structures were invented for dataflow hardware [ARVI80].
In Memo, any folder that will have only one memo ever placed in it may correspond to a future. The consumer executing a memo_get, memo_get_copy, or memo_alt fetching from that folder will be delayed until the value has been produced. The folder will vanish once the memo is removed.
Since it is usually better not to block an entire process, the consumer can delay a memo for the job jar in the future's folder which will trigger the desired computation when the data becomes available:
FOLDER_NAME future,job_jar;
...
memo_write_delayed(future,
job_jar,operation,sizeof(operation)\

Dataflow. Dataflow programming triggers execution of code when its operands become available [ACKE82] [ARVI86] [DAVI82] [DENN80] [TREL82] [VEEN86]. The Memo system facilitates dataflow programming by providing the memo_write_delayed procedure. Assume the operands are futures. One simply arranges to have an operation dropped into a job jar when an operand memo arrives in a folder, thus:
FOLDER_NAME operand,job_jar;
...
memo_write_delayed(operand,
job_jar,operation,sizeof(operation))

If the operation requires more than one operand, then the operation can poll for each of the operands (e.g. by memo_present) and delay itself in absent operands' folders until all are available.

Reactive Objects. A reactive object is an object that executes only in response to messages it receives. Reactive objects are central to the Actors model of parallel computation [AGHA86] [ATHA86] [ATHA87] [ATHA88] [BODE88]. A reactive object can be implemented with a job jar folder plus one input folder per object. A memo containing the object is delayed on its input folder. When an input memo arrives, the object is placed in the job jar. Eventually some process fetches the object from the job jar and executes its code, which reads an input message and responds to it. (For efficiency, it is better to loop reading all available input messages with memo_get_skip, rather than delaying the object after processing each one.)

Ordered queues.The simplest implementation of an ordered queue is an array of futures. For example, the producer can write memos into folders thus:
#define QUEUE ...
...
FOLDER_NAME dest;
int outpos = 0;
dest.S = QUEUE;
dest.X[1] = dest.X[2] = 0;
...
while (1) {
... produce item M ...
dest.X[0] = outpos++;
memo_write(dest,&M,sizeof(M)\
}
And the consumer can remove them similarly:
mine.X[0] = inpos++;
p = memo_get(mine);

Barriers. In parallelizing a loop, it is often important to synchronize the processes executing the loop at one or more points within it using a barrier. If a barrier is initialized with a count N, then N processes must wait at the barrier before any of them are allowed to proceed. The barrier is automatically reinitialized so that they can synchronize over and over again at the same barrier. In Memo, a barrier can be implemented with two folders and a single memo containing an integer count. The presence of the memo in a folder allows the processes to proceed past the barrier.

The processes alternate which folder they look for the memo in. When a process comes to a barrier, it gets the memo and decrements the count in it. If the count is greater than zero, this is not the last process to arrive, so it puts the memo back and tries to get a copy of the memo in the other folder, which is not present yet.

If the process decrements the count to zero, then this is the last process to arrive. It puts a memo with the full count of the number of processes to synchronize into the other folder and continues executing.

Code for this follows:

FOLDER_NAME barrier[2] = {{BARR0,0,0,0},{BARR1,0,0,0}};
int which=0,num_at_barrier=NUM_TO_SYNCHRONIZE;
...
/* initialize the barrier*/
memo_write(barrier[0],&num_at_barrier,sizeof(int)\;
...
while (TRUE) {
int *p;
...
/* synchronize at the barrier: */
p = (int *) memo_get(barrier[which]);
(*p)--;
if (*p==0) {
/* I'm the last to arrive */
which = 1-which;
memo_write(barrier[which],&num_at_barrier,
sizeof(int)\
} else {
/* I am not the last to arrive */
memo_put(barrier[which],p);
which = 1-which;
p = (int*) memo_get_copy(barrier[which]);
}
memo_free(p);
...
}

The two shared memory versions both allocate memos in shared memory and both use a hash table to look up folders. One version locks the entire memo package to achieve mutual exclusion; the other locks individual hash table buckets.

A memo_get is handled by linking a "get structure" in a folder telling which process to deliver the memo to. Memo_get will wait for one to be delivered. Memo_get_skip will check to see if a memo was found while the get structure was being installed. Memo_alt is handled like memo_get: it simply installs get structures in the listed folders.

Memo_alt_skip and memo_strict_alt_skip are identical; they install get structures in all named folders and check if a memo was latched during the installation.

All the three distributed memory versions have used servers to handle the directory of folders. The simplest distributed implementation uses a single server; the Memo procedures are replaced with stubs that pass messages to the server to invoke the operations.

Two distributed memory implementations use multiple servers. Folder names are hashed to determine which server is handling the folder. For both, the implementation of the varieties of memo_alt is difficult. For memo_alt itself, messages are sent to all servers containing any of the folders listed. Servers that find memos must latch one of the memos and respond. It must not remove the memo from its folder unless its memo is the one chosen - other servers can also have memos. A latched memo may delay other get_skip operations: if it is not chosen, the memo will be logically present to a get_skip or alt_skip, even though it cannot be immediately returned.

The implementation of memo_strict_alt_skip is particularly problematic; before it can return NULL, the system has to guarantee that there is an instant of time across the entire machine during which no memos are present in any of the folders. In one implementation, the process executing the strict_alt_skip potentially communicates with the servers three times: the first time to install the get structures; the second time, after the servers respond, to remove the get structures; and the third time to accept one latched memo and unlatch the others. (It can communicate only twice if the first communication finds and latches a memo immediately.)
In the other multi-server distributed memory implementation, the servers involved chain together, locking out other operations, until the strict_alt_skip is complete.

The vast majority of the published Linda algorithms are simple directory-of-queues algorithms. In most Linda algorithms, the first several fields of a tuple, which we will call the key fields, are specified explicitly in both out and in operations. The remaining fields, the entry fields, are all given values by an out and are all assigned to variables by an in. Hence the key fields correspond to the name of a queue, and the entry fields correspond to the structure written into it. Translated into Memo, out corresponds to memo_write; in, to memo_get; and rd, to memo_get_copy.

There are a few other usages of Linda that require slightly more work than simple transliteration. For the same keys, there may be several different numbers and types of non-key fields. Linda provides further matching on their number and types. This can easily be encoded in Memo by using multiple folders, or by writing and reading discriminated unions.

The realities of Linda usage must have been apparent to the implementers of Kernel Linda [LELE90], since they provided tuple spaces called dictionaries and limited tuples to a single key field and a single entry field.

The existence of tuples containing variables has no direct equivalent in Memo, but the examples of their use are infrequent. One published use [GELE85] is to provide an alternate, asynchronous write: server processes wait for tuples specifying their individual names. A request for service by a particular server specifies the server's name. A request for service by any server specifies a variable in the name field, so that any server can pick it up. It is probably much cleaner to have one queue for all servers in addition to an individual queue for each and to have the servers wait for commands with a memo_alt. Linda lacks a read with alternatives, so this solution is unavailable to it.

Linda does try to integrate process creation and termination by eval creating active tuples. The ability to create many processes does make the lack of analogues to memo_alt and memo_write_delayed less serious. However, eval has been difficult to implement in portable forms, and the many small processes it creates are expensive to run, especially on RISC processors. The assumption in Memo is that one either will write data-parallel programs or will simulate macro-dataflow, reactive objects, or multiple small tasks using memos for state vectors and scheduling via job jars. In any case, a limited number of large processes is adequate.

The vast bulk of Linda research shows the usefulness of directories and queues. Linda implementations do show that unordered queues can be as useful as strictly FIFO queues and are considerably easier to implement on distributed-memory machines. The most original aspect of Linda, tuple space, appears to be an obfuscation; Linda research does not seem to support the idea that tuple space has many uses beyond its ability to simulate directories of queues.

Memo offers a number of advances over Linda (in addition to clarifying the abstraction). The memo_alt function allows the implementation of an analogue of a guarded input command. The memo_write_delayed procedure facilitates dataflow and reactive object programming.

We are currently implementing macro-dataflow and reactive object algorithms in Memo to compare its performance to other systems (including MDC90, our distributed-memory/pattern-driven control based language). More programming experience is needed to find the best collection of operations for Memo.

We compared Memo to Linda and suggested that Linda is successful not because of its tuple space abstraction, but rather that tuple space is valuable primarily because it allows the simulation of a directory of queues.

• ACKE82 Ackerman, W. B., "Data Flow Languages," Computer, Feb. 1982, pp. 15-25.
• AGHA86 Agha, G. A.; Actors: A Model of Concurrent Computation in Distributed Systems, MIT Press, Cambridge, MA., 1986.
• AHUJ86 Ahuja, Sudhir, Nicholas Carriero, and David Gelernter, "Linda and Friends," IEEE Computer, Aug. 1986.
• ARVI80 Arvind, Thomas, R. E., I-structures: An Efficient Data Type For Functional Languages. Technical Report LCS/TM-178, MIT, 1980.
• ARVI86 Arvind, Culler, D. E., "Dataflow architectures," Annual Reviews in Computer Science, 1986, Vol. 1, pp. 225-253.
• ATHA86 Athas, W. C., and Seitz, C. L., Cantor User Report, Version 2.0, 5232:TR:86, Computer Science Department, California Institute of Technology, Pasadena, CA, 91125, January, 1987.
• ATHA87 Athas, William C., Fine Grain Concurrent Computations, Ph. D. Dissertation, 5242:TR:87, California Institute of Technology, Pasadena, California, May, 1987.
• ATHA88 Athas, William C. and Charles L. Seitz, "Multicomputers: Message-Passing Concurrent Computers," IEEE Computer, Aug. 1988.
• BODE88 Boden, Nanette J., A Study in Fine-Grain Programming Using Cantor, Caltech CS-TR-88-11, Computer Science Department, California Institute of Technology, Pasadena, CA, 91125, 1988.
• CARR89a Carriero, Nicholas, and David Gelernter, "Linda in Context," CACM, 32:4, Apr. 1989.
• CARR89b Carriero, Nicholas, and David Gelernter, "How To Write Parallel Programs: A Guide to the Perplexed," ACM Computing Surveys, 21:3, Sep. 1989.
• CHRI92 Christopher, T. W., and Freitag, Gregory A. MDC90 Language Description, Version 2.0, Technical Report, Computer Science Department, Illinois Institute of Technology, Chicago, IL 60616.
• DAVI82 Davis, A. L., Keller, R. M., "Data Flow Program Graphs," Computer, Feb. 82, pp. 26-41.
• DENN80 Dennis, J. B., "Data Flow Architectures," Computer, Nov. 1980, pp. 48-56.
• GELE85 Gelernter, David, "Generative Communication in Linda," ACM TOPLAS, 7:1, Jan. 1985.
• LELE90 Leler, Wm, "Linda Meets Unix," IEEE Computer, Feb. 1990.
• TREL82 Treleaven, P. C., Brownbridge, D. R., and Hopkins, R. P. "Data-Driven and Demand-Driven Computer Architecture," ACM Computing Surveys, 14:1, Mar. 1982.
• VEEN86 Veen, A. H.; "Data Flow Machine Architecture," ACM Computing Surveys, 18,4, Dec. 1986, pp. 365-396.