Linda (coordination language)

From Bauman National Library
This page was last modified on 1 June 2016, at 17:08.
Linda
Designed by David Gelernter, Nicholas Carriero
First appeared 1985
Website None

Linda is a parallel programming language based on C programming language (C-Linda) and Fortran (Fortran-Linda), which combines coordination language of Linda with programming languages of C and Fortran. It enables users to create parallel programs that perform on wide range of computing platforms, including supercomputers.The program is seen as a set of processes that can communicate through the space of tuples. In its pure form practically does not occur, is most often used in conjunction with other high-level languages as means of communication of parallel processes.

Model

This model is implemented as a "coordination language" in which several primitives operating on ordered sequence of typed data objects, "tuples," are added to a sequential language, such as C, and a logically global associative memory, called a tuplespace, in which processes store and retrieve tuples.

The original Linda model requires four operations that individual workers perform on the tuples and the tuplespace:

  • in atomically reads and removes a tuple from tuplespace
  • rd non-destructively reads a tuplespace
  • out produces a tuple, writing it into tuplespace (tuple may be duplicated in tuplespace)
  • eval creates new processes to evaluate tuples, writing the result into tuplespace

Evaluation

Compared to other parallel-processing models, Linda is more orthogonal in treating process coordination as a separate activity from computation, and it is more general in being able to subsume various levels of concurrency—uniprocessor, multi-threaded multiprocessor, or networked—under a single model. Its orthogonality allows processes computing in different languages and platforms to interoperate using the same primitives. Its generality allows a multi-threaded Linda system to be distributed across multiple computers without change.

Whereas message-passing models require tightly-coupled processes sending messages to each other in some sequence or protocol, Linda processes are decoupled from other processes, communicating only through the tuplespace; a process need have no notion of other processes except for the kinds of tuples consumed or produced.

Researchers have proposed more primitives to support different types of communication and co-ordination between (open distributed) computer systems, and to solve particular problems arising from various uses of the model. Researchers have also experimented with various means of implementing the virtual shared memory for this model. Many of these researchers proposed larger modifications to the original Linda model, developing a family of systems known as Linda-like systems. An example of this is the language Ease designed by Steven Ericsson-Zenith.

Description

Cortege

Cortege - an ordered sequence of values/

( "Hello", 42, 3.14 ),   ( "P", 5, FALSE, 97, 1024, 2),   ( "worker", 5 ) .

The first element of the tuple is always a character string and acts as the name of the tuple. So the first tuple previous example consists of a name ( "Hello"), an element of type integer (42) and a real number (3.14). In the second tuple except the name "P" is an element of a type (5), a boolean element (FALSE) and three integers. Last motorcade consists of two elements: the name ( "worker") and an integer (5). The number of elements in the tuple can be anything.


The OUT function

OUT function puts a cortege in the cortege space.

out ( "GoProcess", 5);

OUT puts tuples in cortege space ( "GoProcess", 5). If this cortege is already in the space of tuples, then the second will. With out function can not change the cortege already in space. For this cortege must first be removed from there, and then modified and then put back.

The EVAL function

EVAL function is similar to the OUT function. The only difference is that an additional element in the tuple is a user eval function. To calculate the value of this function, the system generates the Linda parallel process, based on the work of which it forms a tuple and places it into the tuple space.

	eval ("hello", funct( z ), TRUE, 3.1415);

In the treatment of the call, the system will create a new process for calculating function funct (z). When the process is finished and will receive the value of w = funct (z), tuple ( "hello", w, TRUE, 3.1415) is added to the space of tuples. Function that caused the eval, does not expect to complete the generated parallel process and continues to work on. It should be noted also that the user can not explicitly control the placement of parallel processes generated on the processor devices available to him - it makes Linda yourself.

Synchronization processes

Linda system has no obvious means for synchronization of processes, but synchronization can write yourself. Suppose that at some point need to perform barrier synchronization N processes. Some single process in advance puts in a tuple space ( "ForBarrier", N). Coming to the point of synchronization, each process performs the following fragment, which will perform the barrier function:

	in( "ForBarrier", formal Bar);
	Bar = Bar - 1;
	if( Bar != 0 ) {
		out( "ForBarrier", Bar);
		read( "Barrier" );
	} else 
		out( "Barrier" );

If a tuple named "ForBarrier" there in space, the process removes it, otherwise blocked until it arrives. Analyzing the second element of the tuple, the process performs one of two actions. If there are processes that have not yet reached this point, then it returns a tuple in the space reduced by one second element and stands waiting motorcade "Barrier". Otherwise, it puts a tuple "Barrier" himself in space, which is a signal for all further work.

References

  • Gelernter, David; Carriero, Nicholas (1992). "Coordination Languages and their Significance". Communications of the ACM. doi:10.1145/129630.129635. 
  • Carriero, Nicholas; Gelernter, David; Mattson, Timothy; Sherman, Andrew (1994). "The Linda Alternative to Message-Passing systems". Parallel Computing. doi:10.1016/0167-8191(94)90032-9. 
  • Wells, George. "Coordination Languages: Back to the Future with Linda" (PDF). Rhodes University. 
  • Sluga, Thomas Arkadius. "Modern C++ Implementation of the LINDA coordination language". University of Hannover. 

External links