Chapter 19. High Level Patterns -- The Calcium Skeleton Framework

19.1. Introduction

19.1.1. About Calcium

Calcium is part of the ProActive Grid Middleware for programming structured parallel and distributed applications. The framework provides a basic set of structured patterns (skeletons) that can be nested to represents more complex patterns. Skeletons are considered a high level programming model because all the parallelisms details are hidden from the programmer. In Calcium, distributed programming is achieved by using ProActive deployment framework and active object model.

19.1.2. The Big Picture

The following steps must be performed for programming with the framework.

  1. Define the skeleton structure.

  2. Implement the classes of the structure (the muscle codes).

  3. Create a new Calcium instance.

  4. Provide an input of problems to be solved by the framework.

  5. Collect the results.

  6. View the performance statistics.

Problems inputed into the framework are treated as tasks. The tasks are interpreted by the remote skeleton interpreters as shown in the following Figure:

Task Flow in Calcium

Figure 19.1. Task Flow in Calcium

19.2. Quick Example

In this example we will implement skeleton that finds prime numbers for an interval of numbers using a naive approach.

19.2.1. Define the skeleton structure

The approach we will use corresponds to dividing the original search space into several smaller search spaces. Therefore, the most suitable pattern corresponds to Divide and Conquer.

// Dac(<Divide>,<Condition>,<Skeleton>,<Conquer>)
Skeleton<Challenge> root = new DaC<Challenge>( new ChallengeDivide(1),
                           new ChallengeDivideCondition(2), 
                           new Seq<Challenge>(new SolveChallenge(3)),
                           new ConquerChallenge(4));
        

19.2.2. Implementing the Muscle

We will call the problem as Challenge and we will represent it using the following class.

class Challenge implements Serializable{

public int max, min, solvableSize;

    public Vector<Integer> primes;

    /**
     * Creates a new challenge for finding primes.
     * @param min  The minimum of the interval.
     * @param max  The maximum of the interval.
     * @param solvableSize The size of the problems to be solved.
     */
    public Challenge(int min, int max, int solvableSize){
        this.min=min;
        this.max=max;
        this.solvableSize=solvableSize;
        primes=new Vector<Integer>();
    }
}

Note that the skeleton structure is parametrized using the Challenge class.

19.2.2.1. Divide

public class ChallengeDivide implements Divide<Challenge>{
    
    public Vector<Challenge> divide(Challenge param) {
        
        Challenge ttUp = new Challenge(1+param.min+(param.max-param.min)/2,param.max,param.solvableSize);

        Challenge ttDown = new Challenge(param.min,param.min+(param.max-param.min)/2, param.solvableSize);
        
        Vector<Challenge> v = new Vector<Challenge>();
        v.add(ttUp);
        v.add(ttDown);
        
        return v;
    }
}

19.2.2.2. Condition

public class ChallengeDivideCondition implements Condition<Challenge>{
    
    public boolean evalCondition(Challenge params) {
        
        return params.max-params.min > params.solvableSize;
    }
}

19.2.2.3. Skeleton

public class SolveChallenge implements Execute<Challenge>{

    public Challenge execute(Challenge param) {
        for(int i=param.min;i<=param.max;i++){
            if(isPrime(i)){
                param.primes.add(new Integer(i));
            }
        }
        
        return param;
    }
    //...
}

19.2.2.4. Conquer

public class ConquerChallenge implements Conquer<Challenge>{
    
    public Challenge conquer(Challenge parent, Vector<Challenge> p) {
            
        for(Challenge param:p){
            parent.max=Math.max(parent.max, param.max);
            parent.min=Math.min(parent.min, param.min);
            parent.primes.addAll(param.primes);
        }

        Collections.sort(parent.primes);
        return parent;
    }
}

19.2.3. Create a new Calcium Instance

Skeleton<Challenge> root = ...; //Step 1
ResourceManager manager= new ProActiveManager(descriptor, "local");
Calcium<Challenge> calcium = new Calcium<Challenge>(manager);

19.2.4. Provide an input of problems to be solved by the framework

Stream<Board> stream = calcium.newStream(root);

stream.input(new Challenge(1,6400,300));
stream.input(new Challenge(1,100,20));
stream.input(new Challenge(1,640,64));

calcium.boot(); //begin the evaluation

19.2.5. Collect the results

for(Challenge res = stream.getResult(); res != null; res = stream.getResult())
    System.out.println(res); //print results

calcium.shutdown(); //release the resources

19.2.6. View the performance statistics

Stats stats=stream.getStats(res);
System.out.println(stats);

19.3. Supported Patterns

Skeletons can be composed in the following way:

S := farm(S)|pipe(S1,S2)|if(cond,S1,S2)|while(cond,S)|for(i,S)|D&C(cond,div,S,conq)|map(div, S, conq)|Seq(f)

Each skeleton represents a different parallelism described as follows:

  • Farm , also known as Master-Slave, corresponds to the task replication pattern where a specific function must be executed over a set of slaves.

  • Pipe corresponds to computation divided in stages were the stage n+1 is always executed after the n-th stage.

  • If corresponds to a decision pattern, were a choice must be made between executing two functions.

  • While corresponds to a pattern were a function is executed while a condition is met.

  • For corresponds to a pattern were a function is executed a specific number of times.

  • Divide and Conquer corresponds to a pattern were a problem is divided into several smaller problems while a condition is met. The tasks are solved and then solutions are then conquered into a single final solution for the original problem.

  • Map corresponds to a pattern were the same function is applied to several parts of a problem.

19.4. Choosing a Resource Manager

In Calcium, remote resources are acquired using ProActive's deployment framework in the following way:

ResourceManager manager = new ProActiveManager("descriptor/path/to/file.xml", "virtualNodeName");

Additionally, for debugging purposes, two other resource managers are available: MonoThreaded and MultiThreaded:

ResourceManager manager = new MonoThreadedManager();

//or

ResourceManager manager = new MultiThreadedManager(2); //Two threads

19.5. Performance Statistics

There are two ways to obtain performance statistics.

19.5.1. Global Statistics

These statistics refer to the global state of the framework by providing state information. The tasks can be in three different states: ready for execution, processing, waiting for other tasks to finish, and finished (ready to be collected by the user). The statistics corresponding to these states are:

  • Number of tasks on each state.

  • Average time spent by the tasks on each state.

Statistics for a specific moment can be directly retrieved from the Calcium instance:

StatsGlobal statsGlobal = calcium.getStatsGlobal()

An alternative is to create a monitor that can be performe functions based on the statistics. In the following example we activate a simple logger monitor that prints the statistics every 5 seconds.

Monitor monitor= new SimpleLogMonitor(calcium, 5);

monitor.start();
...
monitor.stop();

19.5.2. Result Statistics

This statistics are specific for each result obtained from the framework. They provide information on how the result was obtained:

  • Execution time for each muscle of the skeleton.

  • Time spent by this task in the ready, processing, waiting and executing state. Also, the wallclock and computation time are provided.

  • Data parallelism achieved: tree size, tree depth, number of elements in the tree.

19.6. Future Work

  • Handle fault tolerance

  • Allow scalability on the number of resources used