LINDA INTRODUCTION

Overview
Linda Basics
Example Code
Linda Programming Environment
Using Linda Code Development System
Exercise 1
Arrays in C-Linda
Arrays in Fortran-Linda
Hints and Miscellaneous
Exercise 2,3,4...
Acknowledgements and References


Overview:
What is Linda?

Parallel programming language based on C (C-Linda) and Fortran (Fortran-Linda)
Combines coordination language of Linda with programming languages of C and Fortran
Enables users to create parallel programs that perform on wide range of computing platforms
Easy to use
Based on logically global, associative object memory called tuple space
Tuple space provides interprocess communication and synchronization logically independent of the underlying computer or network
Implements parallelism with a small number of simple operations on tuple space to create and coordinate parallel processes
Commercially available from Scientific Computing Associates Inc.


Overview:
The Linda Model

Virtual Shared Memory
- Different parts of the data can reside on different processors.
- Looks like one single global memory space to component processes.
Linda's Virtual Shared Memory is known as tuple space
Can be used to implement many different types of algorithms
Lends itself well to master/worker distributed data structure algorithms


Overview:

Master/Worker Model using Virtual Shared Memory

Task and workers are independent of each other
Master divides work into discrete tasks and puts into global space
Workers repeatedly retrieve tasks and put results back into global space
Workers notified of work completion by having met some condition, receiving a "poison pill" or terminated by some other means
Master gathers results from global space
Possible ways that tasks can be distributed:
- Bag of tasks (unordered)
- Ordered tasks by using a shared counter in tuple space along with task identifiers.
- Tasks identifiers used to find related data.


Linda Basics:
Definitions

Tuple Space
- Linda's name for its shared data space. Tuple space contains tuples.
Tuples
- The fundamental data structure of tuple space.
- Tuples are represented by a list of up to 16 fields, separated by commas and enclosed in parentheses.
- Examples:
```
   ('arraydata', dim1, 13, 2)
   (var1, var2)
   ('common block', /datacom/)
   ('array sections', a_array(2:10, 4:8))
```
Associative Memory Model
- A tuple is accessed by specifying its contents.
- From the programmer's point of view, there is no address associated with a tuple.


Linda Basics:
Operations

There are four basic operations

Tuple Generation
- out
  - Generates a data (passive) tuple
  - Each field is evaluated and put into tuple space
  - Control is then returned to the invoking program
  - Example:
```
   out ('array data', dim1, dim2)
```
- eval
  - Generates process (active) tuple
  - Control is immediately returned to invoking program
  - Logically, each field is evaluated concurrently, by a separate process and then placed into tuple space
  - In current implementation, only fields containing function (or subroutine) references result in new processes being created
  - Example:
```
   eval ("test", i, f(i));
```
Tuple Extraction
- in
  - Uses a template to retrieve tuple from tuple space.
  - Once retrieved, it is taken out of tuple space and no longer available for other retrievals.
  - If no matching tuple is found process will block. Provides for synchronization between processes.
  - Example:
```
   in ("arraydata", ?dim1, ?dim2);
```
- rd
  - Uses a template to copy data without removing it from tuple space.
  - Once read it is still available for others.
  - If no matching tuple is found process will block.
  - Example:
```
   rd("arraydata", ?dim1, ?dim2);
```


Linda Basics:
Templates

Specifies tuple to retrieve
Consists of sequence of typed fields
Two kinds of fields
- Actuals
  - Variables, constants or expression that resolve to constant
- Formals
  - Holders for data to retrieve.
  - Preceded by a question mark.
  - Assigned values of corresponding fields in matched tuple.

Example:


  in("arraydata", ?dim1, ?dim2, ?dim3);

  in ("arraydata", 4, ?dim2, ?dim3);

Both examples will match the tuple put into tuple space with the following out operation:
```
  out("arraydata", 4, 6, 8); 
```


Linda Basics:
Template Matching Rules

In order for a template to match a tuple:
- Have to have the same number of fields.
- Actuals must have same type, length and values as those in corresponding tuple fields.
- Formals in template must match type and length of corresponding fields in tuple.
If several tuples match the template, impossible to predict which will be selected.
The order of evaluation of fields within a tuple or template is undefined. Therefore, the following constructs should be avoided:
- out ("string", i++, i);
  Can't predict whether i will be incremented before or after it is evaluated for the third field.
- in("string2", ?j, ?a[j]);
  Can't predict whether j (in third field) will have value set by ?j (second field) or value before statement was executed.
- out('string', x, f(x))
  In this Fortran example, if the function f() modifies the value of x, we can't predict whether the second field will have the original or the modified value of x.

Examples:

  out ('testdata', i, 3, 4+6)


  integer cnt, var, sum
  character*8 string
   .
   .
  in ('testdata', ?cnt, ?var, ?sum)

  in ('testdata', ?cnt, ?var, 10)

  in (?string, ?cnt, ?var, ?sum)


Example Code

Below is a simple example in the use of C and Fortran Linda. In this example, a master process creates a number of parallel "hello_world" processes, each of which prints the message:

"Hello world from process i"

where i is a different number for each process.

While both the C and Fortran versions exhibit the same behavior, they demonstrate two different termination strategies.


Example Code:
Fortran-Linda -  Hello World

C ******************************************************************
C File: hello_world.fl
C
C Simple Fortran Linda Example
C*******************************************************************
C
       subroutine real_main
       integer i, NPROC
       parameter (NPROC=8)
C
       out('count', 0)
       do 100 i=1, NPROC
       eval('worker', hello(i))
 100   continue
C
       in ('count', NPROC)
       print *, ' Hello world is finished'
       end
C
       subroutine hello(id)
       integer id, j
C
       print *, ' Hello world from process ',id
       in ('count', ?j)
       out ('count', j+1)
C
       return
       end


Example Code:
C-Linda - Hello World

/*********************************************************************** * File: hello_world.cl * * Simple C Linda example ***********************************************************************/ real_main(argc,argv) int argc; char *argv[]; { int nworker, j, hello(); nworker=atoi (argv[1]); for (j=0; j < nworker; j++) eval ("worker", hello(j)); for(j=0; j < nworker; j++) in("done"); printf("Hello_world is finished.\n"); } /** subroutine hello **/ int hello (i) int i; { printf("Hello world from number %d.\n",i); out("done"); return(0); }


Example Code:
Features Illustrated in Fortran Code

This example illustrates a number of features of Fortran-Linda:

Name of program has an .fl extension
Top level routine must be a parameter-less subroutine named real_main
Bulk of program is pure Fortran
Linda operations, eval, in, out
Program is asynchronous - no guarantee that any particular process will execute before any other
Master knows it is done when count tuple = number of workers


Example Code:
Features Illustrated in C Code

This examples illustrates the following features of C-Linda:

Name of program has an .cl extension
Top level routine must be named real_main but has the same argv and argc parameters as the C main does
Bulk of program is pure C
Linda operations eval, in, out
Program is asynchronous
Master knows it is done when it has retrieved n done tuples from tuple space where n = number of workers


Linda Programming Environment

There are two execution models on the SP2:

RS6000 Code Development System (CDS)
Network-POE Linda on Highspeed switch
- Uses IBM's native communication primitives (MPL)


Linda Programming Environment:
Code Development System (CDS)

Simulates parallel program execution in a uniprocessor environment
Processes run asynchronously
Supports use of TupleScope
- X Window System-based monitoring and debugging tool for Linda programs.
- Displays tuple classes, process interaction, program code and tuple data.
- Contains usual debugger features, such as single-step mode for Linda operations.
- Supports point-and-click invocation of native source-level debuggers.


Linda Programming Environment:
Environment Setup

Set paths to Linda executables:

using c shell

   setenv LINDA_PATH /source/vendorcode/linda/poe/
   setenv PATH ${PATH}:${LINDA_PATH}bin

using korn shell

   export LINDA_PATH=/source/vendorcode/linda/poe/
   export PATH= ${PATH}:${LINDA_PATH}bin

To use Fortran-Linda with CDS:
using cshell
```
   setenv LINDA_FLC cds
```
using korn shell
```
   export LINDA_FLC=cds
```
To use Fortran-Linda with Network-POE:
using c shell
```
   setenv LINDA_FLC network
```
using korn shell
```
   export LINDA_FLC=network
```

To use C-Linda with CDS:

using c shell

   setenv LINDA_CLC cds

using korn shell

   export LINDA_CLC=cds

To use C-Linda with Network-POE:
using c shell
```
   setenv LINDA_CLC network
```
using korn shell
```
   export LINDA_CLC=network
```
NOTE: When running Network Linda, the value of the environment variable MP_PROCS will be used to determine how many processors are used. It will use the host.list file which should contain switch node addresses. (See Parallel Operating Environment Overview section for details).


Linda Programming Environment:
Compilers

flc - Fortran-Linda compiler command
clc - C-Linda compiler command
Similar syntax to standard C and Fortran compilers
Additional -linda options

Examples:

flc -g -o hello -linda tuple_scope hello_world.fl
clc -g -o hello -linda tuple_scope hello_world.cl

See User's Guide for complete details


Using Linda Code Development System (CDS)

To use the CDS system, set the following environment variable to cds:

LINDA_FLC - for Fortran, or
LINDA_CLC - for C

An example of setting the environment variable, compiling the "hello_world" program and running the executable is listed below.


% setenv LINDA_FLC cds

% flc -o hello hello.fl

FLC (V2.5.2 CDS version)
hello.fl:
Undeclared subprogram hello is treated as a subroutine
** real_main   === End of Compilation 1 ===
** hello   === End of Compilation 2 ===
1501-510  Compilation successful for file hello_.f.
hello.fl:13: warning --- no matching Linda op.
% 


% hello

Linda initializing (2000 blocks).
Linda initialization complete.
  Hello world from process           4 
  Hello world from process           7 
  Hello world from process           6 
  Hello world from process           1 
  Hello world from process           8 
  Hello world from process           3 
  Hello world from process           2 
  Hello world from process           5 
  Hello world is finished
all tasks are completed (9 tasks).
linda: cloning proc has been told to exit, waiting for 8 clones.
linda: cleanup releasing semaphores and shared region.

Note that there is a warning of "no matching Linda op".

Linda will print a warning if there is an operation that puts something out into tuple space that has no corresponding retrieval, and vice versa.
In most cases this is a very useful message for detecting syntactically-correct (but semantically-incorrect) typos.
In this case, however, it is referring to the eval operation that starts up the workers and can be ignored.


Using Linda Code Development System:
The TupleScope Visual Debugger

To use TupleScope, you must compile with the

-linda tuple_scope

option and be using cds:

using c shell

  %setenv LINDA_CLC cds
  %clc -o array.out -linda tuple_scope array.cl

using korn shell

  %export LINDA_CLC=cds
  %clc -o array.out -linda tuple_scope array.cl

Press this image to see a larger version.

The TupleScope display consists of two parts: the control panel window and a separate window for each tuple class.

Control Panel
- Name of executable on window title bar and box in upper left of display.
- Series of menu buttons along top of window.
- Slider control bar in upper right corner. Controls execution speed. Extreme right represents normal (full) speed.
- Series of tuple class window icons along bottom of window. Allow you to open tuple windows that have been closed.
- When a process is initiated with an eval, an icon for it briefly appears above the tuple class window icon.
Tuple Class Windows
- Sizing box in upper left corner of window controls size of window:
  - Click with left button - minimum size
  - Click with middle button - medium size
  - Click with right button - maximum size.
- Textual representation of the tuple class:
  - Indicates constant string that defines class, number and type of other fields in tuples of this class.
  - Clicking with the left mouse button on the tuple string will close the tuple class window.
- Spherical icons for each tuple that exists in this class:
  - Clicking on a tuple with the left mouse button will open a small window displaying its contents.
- Icons for processes which have accessed tuples in this class. The form of the icon varies depending on the operation performed.
  - Arrows indicate successful tuple generation and extraction:
    - Solid black arrow pointing up - successful out operation
    - Solid black arrow pointing down - successful in operation
    - White arrow in black box pointing up - successful rd operation.
  - Diamonds indicate a blocked process:
    - Solid black diamond - blocked in operation
    - White diamond - blocked rd operation.
- Clicking on a process icon with the left mouse button will produce a scrollable file window containing the text of the source file corresponding to it. Line containing current tuple operation indicated by a caret ("^").


Using Linda Code Development System:
Tuple Class Windows


Using Linda Code Development System:
TupleScope Run Modes

The TupleScope run modes are controlled by buttons in the control panel:

Run button commences program execution
Program will execute in normal or single step mode dependent on setting of Single Step item on Modes menu
Clicking on Break button cause program execution to pause at next Linda operation
Continue button resumes execution after break
Quit button exits TupleScope


Using Linda Code Development System:
Using the Debugger

Compile program for TupleScope and dbx

flc -g -o hello -linda tuple_scope hello_world.fl

Single-step in TupleScope until desired process is created
Click on process icon with the middle mouse button to invoke the native debugger on that process
Set breakpoint in native debugger and turn off TupleScope single stepping
Use the continue command to resume execution of code in debugger
To change default debugger:
- Set DEBUGGER environment variable to debugger of your choice.
- Currently supported debuggers are dbx, gdb, and xdb (under HP/UX).
- Must give entire pathname value of executable if not in current path.


Exercise 1

Copy the file $WORKSHOP/samples/linda/C/linda_share.cl (for the C version) or $WORKSHOP/samples/linda/Fortran/linda_share.fl (for the Fortran version) to your own directory.
Setup the Linda Paths
Compile in the CDS environment
When compiled without errors, compile with tuple_scope option and execute


Arrays in C-Linda:
Array Specification

In C-Linda operations arrays have the attribute of having a fixed or varying length.

Fixed Array
- Has predetermined and unchanging length known at compile time
- Fixed arrays are specified by using the array name.
- The following examples puts the entire array into and out of tuple space.
```
int a [20], b[20];
     .
     .
out ("fixed array", a);
in  ("fixed array", ?b);
```
Varying Array
- Uses additional information provided at runtime to specify its current length (portion of declared array actually being used).
- Varying attribute is applied to an array by placing a colon after its name.
- Information about its current length follows the colon.
- To specify the first 10 elements of a:
```
a:10
```
- To specify the entire array as a varying array:
```
a:
```
- When used as a formal, an integer variable used for the length will be set to the number of elements retrieved.
- Example:
```
in ("array", ?a:length);
```
  will have the number of elements retrieved put into the variable length.
- NOTE: Fixed arrays never match varying arrays.
- Some other examples:
  - These variables will be used in the examples below:
```
   int *p, a[20], b[20], c[10], len;
   p=a;
```
  - These out operations yield identical tuples:
```
   out("varying array", a:);
   out("varying array", a:20);
   out("varying array", p:20);
```
    The length is required in the third case because pointers must always specify an explicit length.
  - To create a tuple containing the first 10 elements:
```
 
   out("ten elements", a:10);
   out("ten elements", p:10);
```
  - The "ten elements" tuple may be retrieved by any one of the following in operations:
```
   in("ten elements", ?a:len);
   in("ten elements", ?p:len);
   in("ten elements", ?b:);
   in("ten elements", ?c:);
```
    However,
```
   in ("ten elements", ?c)
```
    would not work, because it is a fixed type and fixed arrays never match variable arrays.


Arrays in C-Linda:
Multidimensional Arrays

Multidimensional arrays match if the portions referred to have the same shape.
Given the arrays:
```
   int a[3][5][2], b[4][6][2], c[7][2][5];
```
the following would match:
```
   out("multi", a[0][0]);
   in ("multi", ?b[0][0]);
```
- They both point to a fixed array with a length of 2:
the following would not match:
```
   out("multi", a[0]);
   in ("multi", ?b[0]);
```
- The array generated by the out operation is a 5x2, and the in template is a 6x2.
- For two dimensional arrays, portions referred to match must have same shape

Arrays do not have to have the same number of dimensions to match.

Each set of in and out operations below match.

   int a[3][5][2], b[5][2], c[2], i;

   out("fixed", a[0]);
   in("fixed", ?b);

   out("varying", a[0][0]:);
   in ("varying", ?c:);

   out("not an array", a[0][0][0]);
   in ("not an array", ?i);

When two arrays have exactly the same dimension they can be treated as single dimension arrays.

   int x[2][16][512], y[2][16][512], len

   out("fixed", x);
   in ("fixed", ?y);

   out("varying", x:);
   in ("varying, ?y:len);

   out("section", x:200);
   in ("section", ?y:len);


Arrays in C-Linda:
Template Matching and Arrays

Arrays match other arrays whose elements are of the same type.
Fixed arrays match only other fixed arrays of the same length.
Fixed arrays never match varying arrays even if they are the same size.
Multidimensional arrays match if the portions referred to have the same shape.
Actual arrays must agree in both the number of elements and the values of all corresponding elements.


Arrays in Fortran-Linda:
Array Specification

In Fortran-Linda operations arrays have the attribute of having a fixed or varying length.

Fixed Arrays
- Length is known at compile time so can be referred to by using only its name.
```
   integer a(50,10)

   out ('fixed-size array', a)
   in  ('fixed-size array, ?a)
```
Varying Arrays
- Size not known at compile time but can be determined at run time.
- Must be treated as varying-size arrays in all Linda statements.
- In the example below, the array b and the integer scalar n are subprogram arguments with b defined by:
Assumed Size Arrays
- Impossible for Fortran-Linda to determine array size by evaluating an expression at run time.
- For these arrays all references in Linda statements must explicitly give the length.
- For example, if the subprogram argument array c is defined as:


Arrays in Fortran-Linda:
Fortran 90 Array Sections

Fortran-Linda uses a subset of array syntax for Fortran 90
This syntax is supported only in Linda operations, not in the remaining Fortran source
```
     ifirst:ilast:istride
```
where:
- ifirst is the smallest index of a slice of the array
- ilast is the largest index in the slice
- istride is an optional stride
- If not specified a stride of 1 is assumed.
Example:
```
     double precision a (10,10,10)
```
- Different sections of this array might be specified by any of the following:
```
   a(1:5,1:2,1:5)
   
   a(1:10:2,2:10:2,1:10:5)

   a(1:5,:,2)
```
- The last example above uses a colon (":") to indicate the full index range for that subscript position. It is equivalent to:
```
   a(1:5,1:10,2)
```

Another example:

   out('first half', a(:,:,1:5)
   out('second half', a(:,:,6:10)

To retrieve the two tuples above the following could be used:

   in('first half', ?a:length))

   in('first half', ?a(1:10, 1:10:2, :))

   rd('second half', ?a(:, :, 6:10))

   in('second half', ?a(1, 1, 6):)


Arrays in Fortran-Linda:
Template Matching and Arrays

Formal arrays match only actual arrays of the same type
Array shape and dimensionality do not matter since all arrays are eventually mapped to varying-length arrays at runtime
Double precision arrays never match real or integer


Hints and Miscellaneous

Global variables inherited by processes created by eval
- Values of global variables inherited are the values they have when the Linda program was initiated.
- Any global variables modified through execution of user code before the eval statement will not be passed on to the eval'ed process.
  In Fortran this refers to:
  - common blocks
  - local static variables
  In C this refers to:
  - extern variables
  - static (local) variables
- This type of information must be made available to eval'ed processes through explicit tuple space operations.
Linda Support Programs
- There are several library subprograms that provide runtime support for Linda programs:
  Fortran Routines:
  - flhalt
  - flexit
  - flprocs
  - fstart_time
  - ftimer_split
  - fprint_times
  - flintoff
  - flinton
  - flonexit
  - floffexit
  C Routines:
  - start_timer
  - timer_split
  - print_times
  - lexit
  - lhalt
  - lintoff
  - linton
  - loffexit
  - lonexit
  - lprocs
- Linda programs should never call exit() or halt(); use lexit()/ flexit() or lhalt()/fhalt().
- See the Linda User's Guides for details.
Anonymous Formals
- Anonymous formals let you remove data from tuple space without copying to a local variable.
- They use the type instead of a variable name.
  For C-Linda:
```
  in ("data", ?int);
```
  For Fortran-Linda:
```
  in ('data', ?typeof(integer))
```
CDS and Tuple Space Size
- With CDS, the default size of tuple space is only 400KBytes.
- If this is not large enough, you will get the error message:
```
   out of tb's
```
- To increase the size of tuple space use the compiler option:
```
   -linda ts n
```
  where n is the size of tuple space in 200-byte blocks.
- This is a non-issue when using Network Linda, wherein tuple space is dynamically allocated as needed.
Compiling Fortran Programs
- When a Fortran-Linda file is parsed, two temporary files are created:
  - a Fortran file in which the Linda operations are replaced with calls to C functions.
  - the C functions.
- The C file is named the same as the Fortran file but with a cl extension.
- These temporary files are automatically removed when compilation is done.
- This means that if you have a C-Linda version of your program, in the same directory as your Fortran version, you better name them differently.


Exercise 2,3,4...

Select one of the workshop sample serial codes and convert it to run using Linda.
Compile and run in the CDS environment
When compiled without errors, compile with tuple_scope option and execute
Compile for Network-POE environment
Set MP_PROCS environment variable
Execute program


Acknowledgements and References

C-Linda User's Guide & Reference Manual, Version 2.5.2, Scientific Computing Associates, Inc.
Fortran Linda User's Guide, Version 2.5.2, Scientific Computing Associates, Inc.
Presentation materials, David Turner, Scientific Computing Associates, Inc., New Haven, CT
We gratefully acknowledge David Turner of Scientific Computing Associates, for the use of his presentation materials and assistance in reviewing this documentation, and Scientific Computing Associates, New Haven, CT, for the use of portions of the C-Linda User's Guide & Reference Manual and Fortran Linda User's Guide materials.

© Copyright 1994, Maui High Performance Computing Center. All rights reserved.
Documents located on the Maui High Performance Computing Center's WWW server are copyrighted by the MHPCC. Educational institutions are encouraged to reproduce and distribute these materials for educational use as long as credit and notification are provided. Please retain this copyright notice and include this statement with any copies that you make. Also, the MHPCC requests that you send notification of their use to help@mail.mhpcc.edu.
Commercial use of these materials is prohibited without prior written permission.

Last revised: 3/20/95 Blaise Barney