Next: 6 Ibis RMI Up: Ibis Programmer's Manual Previous: 4 Compiling and Running
Subsections

- 5.1 Satin jobs
- 5.2 Exceptions and abort
- 5.3 Satin job scheduling
- 5.4 Other SatinObject methods
- 5.5 Satin program arguments
- 5.6 Satin Shared Objects
- 5.7 Compiling and running a Satin program

#
5 The Satin Divide-and-Conquer System

Satin is a parallel programming environment for divide-and-conquer parallelization, and master-worker parallelization. Satin extends Java with two simple primitives for divide-and-conquer programming: `spawn` and `sync`. The Satin byte-code rewriter and runtime system cooperate to implement these primitives efficiently on top of the IPL.

##
5.1 Satin jobs

To use Satin, the programmer must label one or more methods in his class as Satin jobs. This is done by defining an interface that extends the Satin interface ibis.satin.Spawnable. For example:

    interface Searcher extends ibis.satin.Spawnable {
       public int search(int a[], int from, int to, int val);
    }

All methods that implement Searcher.search() will be Satin jobs, they are marked as spawnable. In general such a marker interface may contain an arbitrary number of methods. When a Satin program is compiled with the Satin compiler, methods marked as spawnable may be executed in parallel. A class that has spawnable methods must extend the special class ibis.satin.SatinObject. The result of a Satin job can only be used after the invocation of the sync method, which lives in ibis.satin.SatinObject. The sync method is guaranteed to only terminate after the earlier job invocations have terminated. Satin imposes one restriction on the type of parameters and return type of a Satin job: they must be of a basic type or must be serializable. Since a SatinObject is serializable, all its subclasses are serializable as well. This restriction ensures that a Satin job can be stored and moved from one processor to another. Note that this means that all fields of a Satin object must be either serializable or transient.

Figure 1: Parallel search with Satin.

As an example, Figure 1 shows an implementation of the search method. It just looks at a range of elements of the passed array, and tries if one of the elements equals val. If so, it returns the index of the element. If no matching element was found, -1 is returned. Now, we can invoke search as is shown in the main method of Figure 1. In this case, we call search twice, once for the first half of the array, and once for the second half. If we compile the program with javac, the two search invocations will be done sequentially. The sync method in SatinObject does nothing. So we can run the program normally on any JVM. If we modify the class files using the Satin bytecode rewriter, however, the program will be converted to a parallel program. The two calls to search in the main class of Figure 1 will be executed in parallel if two JVMs are available. To run the code on more JVMs, the array can be split into more chunks. In general, an arbitrary number of invocations to Satin job methods may be done.

Figure 2: Divide-and-conquer parallel search with Satin.

It is also allowed to recursively invoke job methods from job methods, as is shown in Figure 2. Here the search is recursively divided into smaller problems until a problem remains that is trivially handled. This model of programming is called divide-and-conquer. Satin has special grid-aware load-balancing algorithms built-in to run such programs efficiently on the grid, on any number of machines. This way, the entire search can be done in parallel on a large number of machines. The example shows how easy it is to write a real parallel grid application using Satin.

##
5.2 Exceptions and abort

A Satin job may throw exceptions in the usual way. This can be used to rapidly terminate a large set of jobs, e.g., when a search result was found. Terminating jobs that are no longer useful can be done with the abort method from the SatinObject class. Satin has its own exception type: `ibis.satin.Inlet`. By extending the `Inlet` class, the programmer can inhibit the generation of a stack trace, which is an expensive operation. The stack trace is usually not useful in the Satin context, because the exception is not an error, it is used to steer the search. Extending `Inlet` is optional, regular exceptions can also be used. Figures 3 and 4 change the search algorithm we used in the previous examples to use exceptions.

Figure 3: Speculative parallel search with Satin.

Figure 4: Speculative parallel search with Satin.

Note that in this version the search method doesn't return a value. It will throw a SearchResultFound object containing the result if the element was found, or it will terminate without throwing an exception if no result is found. This is also the reason the search method implements the Searcher3 interface instead of the Seacher interface. The declaration of the exception in the throws clause and the return type are the only differences. At the top level this exception is caught, and the other search jobs can then be terminated. They have become useless, because the element has already been found in the array. The parallel search can thus be stopped. We call the catch block in the main method that handles the result of the search an inlet. The way of searching in Figures 3 and 4 is called speculative parallelism: the search speculatively starts on both two parts of the array simultaneously, even though we know from the start that a part of the search may be terminated as soon as the element is found. We might thus do more work than a sequential search. On the other hand, we might also do less work than the sequential version, for instance if the element is in the beginning of the second part of the array. The inlet in main contains a return statement. This must be there, because the inlet runs in a new thread. The original main thread is still blocked in the sync statement. When the inlet returns, the main thread is unblocked, because both search jobs have finished: one threw an exception, the other has been aborted.

##
5.3 Satin job scheduling

Satin offers a choice of three different job scheduling strategies:

  Random work-stealing. When looking for work, each Satin instance first examines its own job queue. When this job queue is empty, it randomly selects another Satin instance and takes the first job on its job queue. If that job queue is empty, it randomly selects another Satin instance, et cetera, et cetera. This strategy is the default, and has in the past been proven to be optimal, although that might seem counter-intuitive.

  Cluster-aware random work-stealing. The word ``cluster'' refers to a group of computers that are connected to each other by means of a fast local network. In turn, clusters can be connected to each other, but usually the network between clusters is much slower, and/or has a much higher latency. The cluster-aware random work-stealing strategy is very similar to random work-stealing, except that each participant first tries to steal jobs from other participants in its own cluster (thus using the fast local network). It will only go to participants from other clusters if no participant on the same cluster has work. To determine to which cluster a participant belongs, the cluster name is used. As described in Section 4.2, the `ibis.pool.cluster` system property can be used to specify a cluster name to the Ibis instance.

  Master-worker This strategy is suitable for applications where all Satin jobs are generated on a single participant, the ``master''. All other participants are ``workers'', they obtain jobs from the master and execute them.

Making sure that all participants always can find work to do may need some tuning. Jobs must not be too small, because otherwise the mechanism for obtaining jobs, which may involve network traffic, is too expensive. On the other hand, there must be enough jobs to keep everybody busy. The `SatinObject` class has a boolean method `needMoreJobs()`, which indicates whether it would be useful to generate more jobs.

##
5.4 Other SatinObject methods

The `pause()` method pauses Satin's operation. When the application contains a large sequential part, this method can be called to temporarily pause Satin's internal load distribution strategies to avoid communication overhead during the execution of sequential code. To resume Satin's operation, the `resume()` method must be used.

##
5.5 Satin program arguments

The Satin system accepts the following arguments. They are filtered out from the program arguments, leaving the application's arguments:

  `-satin-closed` Only use the initial set of hosts for the computation; do not allow further hosts to join the computation later on.
  `-satin-stats` Display some statistics at the end of the Satin run. This is the default.
  `-satin-detailed-stats` Display detailed statistics for every member at the end of the Satin run.
  `-satin-no-stats` Don't display statistics at the end of the Satin run.
  `-satin-panda` Use the Panda version of Ibis.
  `-satin-mpi` Use the MPI version of Ibis.
  `-satin-net` Use NetIbis.
  `-satin-nio` Use NIO Ibis.
  `-satin-tcp` Use the TCP version of Ibis.
  `-satin-ibis` Use Ibis serialization. When no serialization is specified, the object serialization used is determined by Ibis itself.
  `-satin-sun` Use Sun serialization.
  `-satin-upcalls` Use upcalls for receiving messages. This is the default.
  `-satin-no-upcalls` Use explicit receipt for receiving messages.
  `-satin-upcall-polling` Use upcalls for receiving messages, but Satin must explicitly poll to get upcalls.
  `-satin-alg` algorithm Specify the load-balancing algorithm to use. The possible values for algorithm are: RS for random work-stealing, CRS for cluster-aware random-work stealing, and MW for master-worker

The following flags are for tuning by the developers of Satin, and should not be used unless you really know what you are doing:

  `-satin-queue-size` integer The maximum desirable job queue size. If the current work queue has more than this number of jobs, Satin indicates that it does not need more jobs (as can be asked though the needMoreJobs() method).

##
5.6 Satin Shared Objects

The divide-and-conquer model operates by subdividing the problem into subproblems (subtasks) and solving them recursively. The only way of sharing data between tasks is by passing parameters and returning results. Therefore, a task can share data with its subtasks and the other way round, but the subtasks cannot share data with each other. Therefore, we have extended the model, and in the process renamed it "divide-and-share".

In the divide-and-share model, tasks can share data using shared objects. Updates performed on a shared object are visible to all tasks. Operations on shared objects are executed atomically. Satin guarantees that shared object operations do not run concurrently with each other. Satin also guarantees that the shared object operations do not run concurrently with divide-and-conquer tasks. An operation performed by a task becomes visible to other tasks only when the system reaches a so-called safe point: when a task is creating (spawning) subtasks, when a task is waiting for its subtasks to finish, or when a task completes. Tasks can also explicitly poll for shared object updates. This makes the model clean and easy to use, as the programmer does not need to use locks and semaphores to synchronize access to shared data.

Shared objects are replicated on every processor taking part in the computation. Replication is implemented using an update protocol with function shipping: write methods, that is, methods that modify the state of the object, are forwarded to all processors which apply them on their local replicas. Read methods, that is, methods that do not change the state of the objects, are executed locally.

A shared object type must be marked as such by extending the special class `ibis.satin.SharedObject`. This class exports a single method

        public void exportObject();

which may optionally be invoked to inform Satin that it might be useful to broadcast the object to all participants in the run.

Write methods must be marked as such, by specifying them in an interface that extends the marker interface `ibis.satin.WriteMethodsInterface`. Note that it is up to the user to specify which methods are write methods. Here is a small example:

    interface MinInterface extends ibis.satin.WriteMethodsInterface {
        public void set(int val);
    }

    final class Min extends ibis.satin.SharedObject
            implements MinInterface {
        private int val = Integer.MAX_VALUE;
        public void set(int newVal) {
            if (newVal< val) val = newVal;
        }
        public int get() { return val; }
    }

Our shared object model provides a relaxed consistency model called guard consistency. Under guard consistency, the user can define the application consistency requirements using guard functions. Guard functions are associated with divide-and-conquer tasks. Conceptually, a guard function is executed before each divide-and-conquer task. A guard checks the state of the shared objects accessed by the task and returns true if those objects are in a correct state, or false otherwise. Satin allows replicas to become inconsistent as long as guards are satisfied: the updates are propagated to remote replicas on a best effort basis. Satin does not guarantee that the updates will not be lost or duplicated. Updates may be applied in different order on different replicas. When a guard is unsatisfied, Satin invalidates the local replica of a shared object and fetches a consistent replica from another processor.

For each spawnable method, the programmer may define a boolean guard method which specifies what the state of shared object parameters should be before actually executing the spawned method. Such a guard function must be defined in the same class as the spawnable method it guards. The name of the guard function is `guard_`spawnable_function. It must have exactly the same parameter list as the spawnable method and return a boolean value. Therefore, it will have access to exactly the same shared objects and it can check their consistency. It will also have access to other parameters of the Satin task on which the consistency state of the objects may depend. Satin takes care of invoking this method at the right moment. Here is a small example:

        /* A spawnable method. */
        public Result compute(int iteration, Data data) {
            ...
        }

        /* Guard: make sure that data represents the right iteration. */
        public boolean guard_compute(int iteration, Data data) {
            return data.iteration == iteration-1;
        }

##
5.7 Compiling and running a Satin program

Before running a Satin application it must be compiled. Using ant, this is quite easy. Here is a build.xml file for our example program:

    <project
        name="Search"
        default="build"
        basedir=".">

        <description>
        Satin application build.
        </description>

        <property environment="env" />
        <property name="ibis"   value="${env.IBIS_ROOT}" />

        <property name="satin-main-class" value="Search"/>

        <property name="build"  location="build"/>

        <import file="${ibis}/build-files/apps/build-satin-app.xml"/>
    </project>

Again, we assume that the environment variable `IBIS_ROOT` reflects the location of your Ibis installation. Also note that the Satin bytecode rewriter needs to know the main class of your Satin application. Its name is specified in the `satin-main-class` property.

Invoking ant clean compile compiles a sequential version of the application, leaving the class files in a directory called `build`.

Invoking ant clean build compiles the application for parallel runs.

Running a Satin program is very much like running an Ibis application. See Section 4 for details.

Next: 6 Ibis RMI Up: Ibis Programmer's Manual Previous: 4 Compiling and Running