Package org.jcsp.lang

# Class Sequence

java.lang.Object
org.jcsp.lang.Sequence

All Implemented Interfaces:
  `CSProcess`

public class Sequence extends Object implements CSProcess
This constructor taks an array of `CSProcess`es and returns a `CSProcess` that is the sequential composition of its process arguments.

Shortcut to the Constructor and Method Summaries.

## Description

The `Sequence` constructor taks an array of `CSProcess`es and returns a `CSProcess` that is the sequential composition of its process arguments.

Note: for those familiar with the occam programming language, the `Sequence` class gives the semantics of the `SEQ` construct.

This class is included for completeness. Sequential code is normally be handled by sequential Java code. If we need to run some `CSProcess`es in sequence, we can just execute their `run` methods in sequence. However, using this `Sequence` class lets us switch between sequential and parallel composition of processes with a single word change (replace `Sequence` by `Parallel`) in our code. For some applications (e.g. the example below), this may provide a useful comparison.

`CSProcess`es can be added to a `Sequence` object either via the `constructor` or the ``addProcess`` methods. If a call to `addProcess` is made while the `run` method is executing, the extra process(es) will not be executed until the next time `run` is invoked.

`CSProcess`es can be removed from `Sequence` object via the ``removeProcess`` or ``removeAllProcesses`` method. If a call to `removeProcess` or `removeAllProcesses` is made while the `run` method is executing, the process will not be removed from the network until the next time `run` is invoked.

## Example - Matrix Multiply (in Sequence and in Parallel)

The following example illustrates a simple transformation of sequential code into parallel code. On a shared-memory parallel machine (e.g. a Symmetric Multi-Processor) and depending on the overheads for starting up and shutting down the concurrency and the scale of the problem to which it is applied, the parallel code will terminate earlier than its sequential equivalent.

### Sequential Implementation

The example is simple matrix multiplication. The standard implementation consists of three nested `for`-loops, the innermost of which computes the dot-product of a row (of the first matrix) against a column (of the second) to produce one element of the result matrix. It is expressed here as a static method, which would belong to some larger collection of static methods providing a general matrix handling class:

       public static void multiply (final double[][] X,
                                    final double[][] Y,
                                    final double[][] Z) {

         ...  check (X[0].length == Y.length)
         ...  check (X.length == Z.length)
         ...  check (Y[0].length == Z[0].length)

         for (int i = 0; i invalid input: '<' X.length; i++) {
           final double[] Xi = X[i];
           final double[] Zi = Z[i];
           for (int j = 0; j invalid input: '<' Y[0].length; j++) {
             double sum = 0.0d;
             for (int k = 0; k invalid input: '<' Y.length; k++) {
               sum += Xi[k]*Y[k][j];
             }
             Zi[j] = sum;
           }
         }

       }

The method computes the matrix multiplication of `X` by `Y`, leaving the result in `Z`. The (hidden) checks ensure that the supplied arrays have compatible dimensions for multiplication, throwing a ``java.lang.RuntimeException`` if they are not. The abbreviations `Xi` and `Zi` are not strictly necessary, but for those brought up in an occam world are automatic good practice - the `Xi[k]` reference in the O(n3)-innermost loop saves an array index computation and check.

### Parallel Implementation

The two outer `for`-loops of `multiply` set up the particular row and column pairs for the dot-product computed by the innermost loop. Unnecessarilly, they impose an ordering in which those dot-products are computed. Each dot-product computes one element of the result matrix and is independent of its sibling dot-products. The sequential constraint may, therefore, be removed and all elements of the result matrix may be computed in parallel.

If this were occam, all we would need to do is replace the two outer `for`-loops with `par`-loops. Since this is Java, we have to jump through some slightly higher syntactic hoops. First, we need to transform the body of the `for`-loop into a process and use the loop to assign each one to consecutive elements of a process array. Then, we simply run the array in parallel:

       public static void parMultiply (final double[][] X,
                                       final double[][] Y,
                                       final double[][] Z) {

         ...  check array dimensions are compatible

         final CSProcess[] rowProcess = new CSProcess[X.length];

         for (int i = 0; i invalid input: '<' X.length; i++) {
           final int ii = i;
           rowProcess[ii] = new CSProcess () {
             public void run () {
               final double[] Xi = X[ii];
               final double[] Zi = Z[ii];
               final double[][] YY = Y;
               for (int j = 0; j invalid input: '<' YY[0].length; j++) {
                 double sum = 0.0d;
                 for (int k = 0; k invalid input: '<' YY.length; k++) {
                   sum += Xi[k]*YY[k][j];
                 }
                 Zi[j] = sum;
               }
             }
           };
         }

         new Parallel (rowProcess).run ();

       }

[Note: anonymous inner classes, as in the above code, may only access global variables that are qualified as `final` - hence, the need to freeze the loop control index, `i`, as `ii`. The abreviation `YY`, of `Y`, is so that access to that matrix is via a variable local to the process. The global `Y` could have been used, but at the cost of needless run-time overhead.]

### Back to Sequential Implementation

Having expressed this algorithm in terms of processes, we come to the motivation for this example. To run a collection of processes, we must decide whether to run them is parallel or sequence. JCSP makes either decision equally easy to implement. The above coding ran them in parallel. To revert to running them is sequence, all we need do is change the last line of executable code to:

         new Sequence (rowProcess).run ();

It would probably be good to name this new method `seqMultiply` (instead or `parMultiply`!). Of course, it has the same behaviour as the original sequential `multiply` and suffers only slightly increased overheads - negligible for matrices above a modest size.

### `Sequence` versus `Parallel`

Beware that it is only in certain circumstances that `Sequence` and `Parallel` can be interchanged without upsetting the semantics of the system. The processes under their control must be finite (i.e. they must all terminate), they must engage in no synchronisations (e.g. channel communication) either between themselves or with other processes and they must obey CREW-parallel usage rules (i.e. if one process updates some data, no other process may look at it). These are fulfilled by the `rowProcess` array, each of whose processes computes a separate row (`Zi`) of the target result matrix (`Z`).

### Exercise

The above `parMultiply` has transformed only the outermost `for`-loop of `multiply` into a `par`-loop. Current SMPs do not scale well above 4 or 8 processors, so we do not need very large matrices for this code to demonstrate high parallel efficiencies. Future architectures, however, may offer much higher levels of physical concurrency that efficiently support much finer granularities of process. For those machines and as an interesting exercise, parallelise the middle `for`-loop. To exploit even finer levels of parallel granularity, parallelise the innermost `for`-loop so that it computes its dot-product in O(log(n)) time - rather than the O(n) time of the sequential code.

### Two Important Modifications on `parMultiply`

The first time it is `run`, the JCSP `Parallel` process creates a new `Thread` for all but one of its component processes, running its last component in the thread invoking the `run`. When (and if) all those component processes terminate, the `Parallel` `run` terminates but leaves the newly created threads parked for later use. Subsequent `run`s of the `Parallel` process resuse those parked threads. So the overhead of thread creation occurs only for the first run.

In `parMultiply`, however, the `Parallel` process is anonymous and local to the method and so can never be used again. Worse, the threads it created and parked are left parked - wasting space for the remainder of the program. Repeated invocations of `parMultiply`, therefore, will leak memory.

There are two ways to fix this. The first is to accept that the `Parallel` process created by `parMultiply` remains local to it (and, hence, un-reusable) and, explicitly, to unpark and terminate its unwanted threads. This can be done by invoking ``releaseAllThreads`` on the `Parallel` after it has been `run` - the memory associated with those threads will be released. A temporary name for the process needs to be assigned and the last executable line of `parMultiply` becomes the three lines:

         final Parallel par = new Parallel (rowProcess);
         par.run ();
         par.releaseAllThreads ();

The second way to improve things is to save the `Parallel` process for later runs. There is no easy way for doing this local to the class to which `parMultiply` belongs. `parMultiply` is `static` and may be invoked with matrix parameters of different dimensions. So, a `static` data structure would need to be set up and consulted each time `parMultiply` was invoked to see if a suitable `Parallel` process had already been saved.

Much better is to give the user of `parMultiply` the responsibilty of looking after - and directly using, reusing and (if necessary) terminating the threads in - the `Parallel` process. So, we change the method into something that manufactures a process that does parallel matrix multiplication. That multiplication will be specific to the three matrices given as parameters (i.e. it performs `Z = X*Y` on those matrices only):

       public static Parallel makeParMultiply (final double[][] X,
                                               final double[][] Y,
                                               final double[][] Z) {

         ...  check array dimensions are compatible                     // as before

         final CSProcess[] rowProcess = new CSProcess[X.length];        // as before

         for (int i = 0; i invalid input: '<' X.length; i++) {                           // as before
           final int ii = i;                                            // as before
           rowProcess[ii] = new CSProcess () {                          // as before
             public void run () {                                       // as before
               final double[] Xi = X[ii];                               // as before
               final double[] Zi = Z[ii];                               // as before
               final double[][] YY = Y;                                 // as before
               for (int j = 0; j invalid input: '<' YY[0].length; j++) {                 // as before
                 double sum = 0.0d;                                     // as before
                 for (int k = 0; k invalid input: '<' YY.length; k++) {                  // as before
                   sum += Xi[k]*YY[k][j];                               // as before
                 }                                                      // as before
                 Zi[j] = sum;                                           // as before
               }                                                        // as before
             }                                                          // as before
           };                                                           // as before
         }                                                              // as before

         return new Parallel (rowProcess);

       }

The invoker of `makeParMultiply` gets back a parallel process that can be invoked as often as needed and incurs a thread creation overhead only on its first use. The data for the matrix parameters may be freely changed between invocations - each invocation will work on whatever data is present at the time. All the user must remember is that the manufactured parallel process is good only for working with the matrix objects specified originally to `makeParMultiply` as its parameters. For example, if `Matrix` is the class to which `makeParMultiply` belongs:

         final Parallel par = Matrix.makeParMultiply (X, Y, Z);

         while (...) {
           ...  set up matrices X and Y
           par.run ();
           ...  do something with the result matrix Z
         }

         par.releaseAllThreads ();

Author:
  P.D. Austin, P.H. Welch
See Also:
  - `CSProcess`
  - `Parallel`

## Constructor Summary

Constructors
Constructor
Description
`Sequence()`
Construct a new `Sequence` object initially without any processes.
`Sequence(CSProcess[] processes)`
Construct a new `Sequence` object with the processes specified.

## Method Summary

Modifier and Type
Method
Description
`void`
`addProcess(CSProcess process)`
Add the process to the `Sequence` object.
`void`
`addProcess(CSProcess[] newProcesses)`
Add the array of processes to the `Sequence` object.
`void`
`removeAllProcesses()`
Remove all processes from the `Sequence` object.
`void`
`removeProcess(CSProcess process)`
Remove a process from the `Sequence` object.
`void`
`run()`
Run the sequential composition of the processes registered with this `Sequence` object.

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

## Constructor Details

### Sequence

public Sequence()
Construct a new `Sequence` object initially without any processes.

### Sequence

public Sequence(CSProcess[] processes)
Construct a new `Sequence` object with the processes specified.

Parameters:
  `processes` - the processes to be executed in sequence

## Method Details

### addProcess

public void addProcess(CSProcess process)
Add the process to the `Sequence` object. The extended network will be executed the next time run() is invoked.

Parameters:
  `process` - The CSProcess to be added

### addProcess

public void addProcess(CSProcess[] newProcesses)
Add the array of processes to the `Sequence` object. The extended network will be executed the next time run() is invoked.

Parameters:
  `newProcesses` - the processes to be added

### removeProcess

public void removeProcess(CSProcess process)
Remove a process from the `Sequence` object. The cut-down network will be executed the next time run() is invoked.

Parameters:
  `process` - the process to be removed

### removeAllProcesses

public void removeAllProcesses()
Remove all processes from the `Sequence` object. The cut-down network will not be executed until the next time `run()` is invoked.

### run

public void run()
Run the sequential composition of the processes registered with this `Sequence` object.

Specified by:
  `run` in interface `CSProcess`