🚀 go-pugleaf

                  STRAND88 NEWSLETTER VOLUME 1, ISSUE 4

                               July, 1992


     THIS ISSUE'S TOPIC - MULTIPLE LANGUAGE PROGRAMMING WITH STRAND88  

        by Professor J. John Florentin of Birkbeck College, London


                            INTRODUCTION

The techniques of parallel programming are evolving slowly.
Initially parallel programs were a collection of sequential
programs written in traditional sequential languages. These
languages were extended with communication instructions to effect
inter-process communication. In this approach programmers have to
ensure that data is exchanged between processes only at logically
appropriate times. Such synchronizing communication is feasible in
problems with completely regular patterns of execution, but it is
difficult to control in problem-solving computations where the
execution pattern is strongly data-dependent and irregular.

Logical control of synchronization was then added using features
such as the rendezvous [1]. A further development was to devise new
programming languages in which control of synchronization was a key
element of the programming model. Typical of these are dataflow and
functional languages, [2] and [3].

More recently, concurrent logic languages using the stream, or
pipelining, abstraction have been developed as a progression from
sequential logic languages [4]. An important feature of these
languages is that one form of the data decomposition which is
essential to useful parallel execution is abstracted and
represented in the language itself. Abstracting and representing
data decomposition allows the programmer to comprehend the parallel
execution and to exercise some control over it. This programmer
control can overcome some of the performance limitations found when
running programs written in existing dataflow languages.

The Strand concurrent programming language, [5], is a further
development of this trend. Strand concentrates on representing data
decomposition and links it directly to process synchronization.
Strand takes a minimalist approach and it drops most of the
characteristic features of logic languages, including parameter
passing by unification and backtracking.

Originally the foreign language interface was provided to cater to  
users with existing code which they did not want to re-write. After
some experience this multiple language approach has come to be
adopted for new programs.

THE STRAND CONCURRENT PROGRAMMING LANGUAGE

Strand has a syntax based on logic languages like Prolog. Its
semantics are, however, quite different. A Strand program consists
of a collection of process definitions together with a call to
these processes. A simple illustration defining a process 'twice'
is:

     twice(X,Y) :-
          x > 0 |
               Y is 2*X.

     twice(X,Y) :-
          x <= 0 |
               Y := 0.


Here, X is an input parameter and Y is an output parameter. The
definition has separate cases. These cases are tested when a call
is made. A call to 'twice' might be 'twice (2,Z)', when Z would
receive the value 4.

A call 'twice(2,W), twice (W,Y)' sets up a network of two
concurrent 'twice' processes which communicate through the shared
variable W, see fig 1. Strand automatically manages the data
transfer and also invokes the second 'twice' only at the
appropriate time.


  X      +---------+         W         +---------+     Y
-------> |  twice  |  ---------------> |  twice  | -------->
         +---------+                   +---------+

         Figure 1 : PROCESS INVOCATION IN STRAND

      
A call is effected in stages whose simplest form is:

      (i) the parameter list of the call is pattern-matched against
          the definition head parameters using simple rules which
          will not be detailed here;

     (ii) when a parameter list match is successful, the
          corresponding guard conditions are tested;

    (iii) if at least one guard test succeeds, one corresponding
          case body is chosen and executed; if no guard succeeds a
          program fault occurs.

A more interesting behavior for process invocation occurs when one
of the above stages is held in suspension. For example, a call of
'twice(X,W)' can occur because parallel computing is always in
real-time mode and the value of X may not be known when the call is
made. In this situation the call proceeds until the value of X is
needed in the guard test or in the execution of the body. At the
point where the value of X is needed there is an orderly suspension.

Other matching rules induce suspension before the guard test
commences. An example would occur if there were a special case of
twice for X=3:

     twice(3,Y) :-
          Y := 0.

A call of 'twice(X,Y)' would suspend, waiting to see whether X
became instantiated to 3.

STRAND PROCESSES

Strand processes are created dynamically and are short-lived. In
the usual patterns of Strand programming, new processes are created
continually. The efficiency of this approach can be kept up because
of the simplicity of most processes resulting in a "lightweight
process" implementation.


DATA SHARING PARALLELISM IN STRAND

A process allowing parallel processing is -

     quad(X,Y) :-
          twice(X,V1),
          twice(X,V2),
          sum(V1,V2,Y).

Both instances of the 'twice' process can compute in parallel (see
Figure 2).


                   +---------+  
               /-->|  twice  |->\
              /    +---------+   \ V1
             /                    \      +-------+   Y
     X ---->                        ---> |  sum  |------->
             \                    /      +-------+
              \    +---------+   / V2
               \-->|  twice  |->/
                   +---------+

                        Figure 2


STREAM PROCESSING IN STRAND

Stream processing is the basis for pipeline parallelism where the
data is "salami sliced" into a list of items which is processed by
several operations. A process 'stwice' which operates on a list of
numbers and produces a list of numbers is as follows:

     stwice([Hx|Tx],Ly) :-
          W is 2*Hx,
          Ly := [W|Ly1],
          stwice(Tx,Ly1).

     stwice([],Ly) :-
          Ly := [].

Here, Hx is the first data item on the input list and Tx is the
tail. All three calls on the right hand side potentially execute in
parallel. On a call: 'stwice([1,2,3],Ly)', each data item is
processed by recursive looping.

On a call: 'stwice([1|Tx],Ly)', the first item, 1, is processed and
then a call 'stwice(Tx,Ly1)' is left in suspension. It can be
brought out of suspension by instantiating 'Tx : = [2|Tx1]'. This
instantiation can occur some considerable time after the first
version of stwice is left in suspension. In this situation stwice
appears to be a persistent object.


STREAM PARALLELISM

A call of 'stwice(Lx,V), stwice(V,Ly)' appears to be a network of
two processes inter-connected by the shared variable V, as shown in
Figure 3. Both processes are initially in suspension. An instantiation
'Lx : = [1|Tx]' brings the first stwice out of suspension. As the
first stwice computes the first item in the list V, the number 2
becomes available to fill this slot. This availability causes the
second stwice to come out of suspension and execute one iteration to
produce the first item, 4, of the output list Ly.


 [1,2,3,..]   +---------+      V       +---------+   [4,8,12,..] 
   ---------> | stwice  |  ----------> | stwice  | ------------->
              +---------+              +---------+

                           Figure 3


The result of entering the first item of Lx is that both processes
execute one iteration in sequence and then leave two suspended
descendant processes.

Alternatively, if Lx had been instantiated to 'Lx := [1,2,3|Tx]',
then the first stwice would be processing the input, 2, while the
second stwice was simultaneously processing the first intermediate
result, 2. Parallel execution would need separate physical
processors. This is the basis of stream parallelism, which is
exploited practically in more complex ways in Strand programming.

COMMENTS ON STREAM PARALLELISM

1.   Streams are not confined to linear lists. The stream construct
     works whenever a recursive function and a recursive data
     structure are dovetailed precisely. For example, it is
     possible to fan out parallel processing across a tree in this
     way.

2.   The name of the tail of a stream, like T in [H|T], can be
     regarded as the name of the channel to the process suspended
     on T. Process definitions are often arranged so that channels
     can be closed down by instantiating 'T : = [ ]'. Thus channels
     are abstract and can be created and destroyed dynamically.


STREAMS AND SYNCHRONIZATION

1.   Processes can be suspended awaiting simple data items as in
     the definition of 'twice(3,Y)' above. They can also wait on the
     continuation of a stream as in the stwice example above.
     Processes can also await input events at several parameter
     positions, some of which might be simple items and some of
     which might be streams.

2.   Different cases of a process definition may be set so that it
     is not necessary that input arrives at all parameter positions
     to bring a process out of suspension, and start execution.
     This allows a programming style with a varying response to
     different event combination patterns.


To illustrate this, consider the skeleton definition sketched in
Figure 4: 

     complex(go,[H1|T1],In2,Out) :-
          do(H1,Flag),
          complex(Flag,In1,In2,Out),
          etc...

     complex(go,In1,[H2|T2],Out) :-
          do(H2,Flag),
          complex(Flag,In1,In2,Out),
          etc...


          In1   _____
          [...]      \
                      \     +----------+   Out
          In2-------------> |  complex |----------->
          [...]       /     +----------+
          go ________/

                            Figure 4


A suspended process 'complex(Flag,In1,In2,Out)' awaits the arrival
of the constant 'go' in parameter position 1 plus either a message
in position 2 or a message in position 3.

THE ALLOCATION OF PROCESSES TO PROCESSORS IN STRAND88

Present implementations of STRAND88 do not allocate newly created
processes to physical processors automatically under the control of
an internal scheduler. Process calls have to be annotated to guide
the run-time system. This annotation will not affect the
non-deterministic meaning of the program; as an illustration, the
previous definition of stwice may be annotated to:

     stwice([Hx|Tx],Ly) :-
          W is 2*Hx,
          Ly1 := [W|Ly],
          stwice(Tx,Ly1)@N.

The annotation '@N' means that the regenerated process should be
run at processor node N. The value of N may be computed at run
time. The processes 'W is 2*Hx' and 'Ly1 := [W|Ly]' run on the same
node as the original call. Thus the grain size is determined by
bunching small processes onto a physical node.

A further alternative is:

     stwice([Hx|Tx],Ly) :-
          W is 2*Hx,
          Ly1 := [W|Ly],
          stwice(Tx,Ly1)@next.


The annotation '@next' means that the programmer is assuming a
virtual, or logical, machine with ring-connected processor nodes.
The regenerated process will be passed around the ring. The
run-time system has a machine-dependent routine which is able to
map the programmer's logical ring onto the available physical
processors. Similarly, the programmer may assume a logical infinite
mesh-connected machine.


FOREIGN CODE IN STRAND88

STRAND88 incorporates foreign code by replacing a call to a
STRAND88 process by a call to a routine written in the foreign
language. STRAND88 continues to manage the data transfer and the
process invocation, so the foreign language routines run
concurrently in a correct manner.

STRAND88 and the foreign code have to be coupled so that their
features cooperate properly. For example, STRAND88 has lists as
data structures while Fortran has arrays. Interface routines are
needed to translate between the data structures which might have to
incorporate data buffers. Interface routines are supplied in
library form.

MULTIPLE LANGUAGE PROGRAMMING

The design of the STRAND88 harness can incorporate all of the
synchronizing and data decomposition constructs described in the
sections on stream and data sharing parallelism above. These
constructs do not have to be considered when writing C or Fortran
code.

BIBLIOGRAPHY

[1]  Reference Manual for the Ada Programming Languages, US Dept of
     Defense, US Govt Printing Office, ANSI/MIL-STD-1815A edition,
     Jan 1983

[2]  'Data Flow Languages', William B. Ackerman, Computer Vol 15,
     No 2 pp 15-25, February 1982

[3]  Introduction to Functional Programming, Richard Bird and
     Philip Wadler, Prentice Hall, London 1988

[4]  'The Family of Concurrent Logic Programming Languages', E.
     Shapiro, ACM Computing Surveys, Vol 2 1, No 3 September 1989,
     pp 412-5100

[5]  Strand: New Concepts in Parallel Programming, Ian Foster and
     Stephen Taylor, Prentice Hall, New Jersey 1990

[6]  'Converting sequential applications software for parallel
     execution with STRAND88 harnesses', A. Dinn and G. Phillis,
     Report, Strand Software Technologies, Greycaine Road, Watford,
     Herts WD2 4JP, England, January 12, 1990.


Strand88 is a highly portable and scalable parallel programming language
designed for efficient execution on many hardware platforms: shared-memory
multiprocessors, distributed-memory multiprocessors, and networks of
workstations.

Strand88 is currently ported to the following platforms:

     iPSC/860, iPSC2/386, Sequent Balance/Symmetry, Sun SparcStation, 
     Sun 600MP Multiprocessing Workstation, Transputer/Helios,
     Alliant FX/2800, Meiko Computing Surface, MIPS RISCstation, nCube 2,



     Encore Multimax and System 9x, Cogent XTM Workstation, MacII,
     IBM PS/2, NeXT, Pyramid, and TI TMS320C40 Digital Signal Processor.

Dr. Stuart Bar-On & Jeff Graham, of Parallel Performance Group, Inc., at
(619) 634-0882, or (619) 483-4325, E-Mail: 4956839@mcimail.com, will send
information and answer any questions you may have about Strand88.