back to API     back to index     back to guided tour index     prev     next  

5. The nbody example

Using facilities provided by ProActive on a complete example

1 Rationale and overview

This section of the guided tour goes through the different steps that could take you to writing an application with ProActive, from a simple design, to a more complicated structure. This is meant to help you get familiar with the Group facilities offered by ProActive. Please take note that this page tries to take you through the progression, step by step. You may find some more information, mainly on the design, on the web page of the applications/examples of proactive. This is a snapshot of the ProActive nbody example running on 3 hosts with 8 bodies:

n-body is a classic problem. It consists in working out the position of bodies in space, which depend only on the gravitational forces that apply to them. A good introduction to the problem is given here. You may find a detailled explanation of the underlying mathematics here. Different ways of finding numerical solutions are given here.

In short, one considers several bodies (sometimes called particles) in space, where the only force is due to gravity. When only two bodies are at hand, this is expressed as


Fp->b is the force that p applies on b, G is the gravitational constant, mp mb describe the mass of the bodies, r is the distance between p and b, and u is a unit vector in the direction going from p to b. When we consider all the forces that apply to one given body, we have to sum up the contribution of all the other bodies :


This should be read as : the total force on the body b is the sum of all the forces applied to b, generated by all the other bodies in the system.
This is the force that has to be computed for every body in the system. With this force, using the usual physics formulae, (Newton's second Law)


one may now compute the movement of a particle for a given time step (a the acceleration, v the velocity, x the position, t the time):



2 Source files: ProActive/src/org/objectweb/proactive/examples/nbody

This guided tour is based on the files you may find in the directory ProActive/src/org/objectweb/proactive/examples/nbody. You'll find the following tree:



The common directory contains files reused through the different version. 'simple' is the simplest example, groupcom is the first example with Group communication, and 'groupdistrib' and 'groupoospmd' are two enhancement based on different synchronization schemes. 'barneshut' is a bit special, in that it contains a different algorithm to solve the nbody problem.

3 Common files

The files contained in 'common' are those that are reused throughout the different versions.  Let's see what they do:

The files contained in the other directories, 'simple', 'groupcom', 'groupdistrib' , 'groupoospmd' , detail steps of increasing complexity, making the application use different concepts. 'barneshut' contains the final implementation, featuring the Barnes-Hut algorithm. But let's not go too fast. Let's have a look at the insides of the simplest implementation of the n-body problem.

4 Simple Active Objects

This is the implementation of the simplest example of nbody. We defined the Planet to be a passive object, and it does nothing. It is a container for position, velocity and mass, as we've seen in the description given higher up. The real actors are the Domains, they do all the work. To every Planet in the universe, is associated a Domain, which is an Active Object. This  Domain contains the code to manage the communication of the possitions of the Planets during the simulation. They are created in the Start.java file :

        Rectangle universe = new Rectangle (-100,-100,100,100);
        Domain [] domainArray = new Domain [totalNbBodies];
        for (int  i = 0 ; i < totalNbBodies ; i++) {
            Object [] constructorParams = new Object [] {
                    new Integer(i),
                    new Planet (universe)
                };
            try {
                // Create all the Domains used in the simulation
                domainArray[i] = (Domain) ProActive.newActive(
                        Domain.class.getName(),
                        constructorParams,
                        nodes[(i+1) % nodes.length]
                );
            }
            catch (ActiveObjectCreationException e) { killsupport.abort(e); }
            catch (NodeException e) { killsupport.abort(e); }
        }

See how the call to ProActive.newActive creates one new Active Object, a Domain, at each iteration of the loop. The array nodes contains all the nodes on which an Active Object may be deployed; at each iteration, one given node, ie one JVM, is selected. The constructorParams are the parameters that are to be passed to the constructor of Domain, and since it's an Object [] , the parameters may only be Objects (don't try to build constructors using ints in their constructor - this explains the use of the class Integer).

The Domains, once created, are initialized, and then they synchronize themselves by all pinging the maestro, with the notifyFinished call:

        // init workers, from the Start class
        for (int i=0 ; i < totalNbBodies ; i ++)
            domainArray[i].init(domainArray, displayer, maestro);


         // init method, defined within each worker
         public void init(Domain [] domainArray, Displayer dp, Maestro master) {
                 this.neighbours = domainArray;
                 .....
                 maestro.notifyFinished();                 // say we're ready to start
           }

         public void notifyFinished() {
             this.nbFinished ++ ;
             if (this.nbFinished == this.domainArray.length) {
                  this.iter ++;
                  if (this.iter ==this.maxIter)
                       this.killsupport.quit();
                  this.nbFinished = 0 ;
                  for (int i= 0 ; i < domainArray.length ; i++)
                           this.domainArray[i].sendValueToNeighbours();
             }
         }

Notice how domainArray is passed to all the Domains, when calling init. This is the value assigned to the local field neighbours, which later on serves to communicate with all the other Domains of the simulation.

The synchronization is done by the Maestro, which counts the number of Domains that have finished, and then asks them to go on to the next iteration. While in their execution, the Domains gather information concerning the position of all the other bodies, which need to be known to move the local Planet, at every time step. This is done using a push schema : instead of explicitly asking for information, this information is automatically issued :

        public void sendValueToNeighbours() {
           for (int i = 0 ; i < this.neighbours.length ; i ++)
              if (i != this.identification) // don't notify self!
                  this.neighbours[i].setValue(this.info, this.identification);
            .....  
           }
      
       public void setValue(Planet inf, int id) {
          this.values [id] = inf;
          this.nbReceived ++ ;
          if (this.nbReceived > this.nbvalues)  // This is a bad sign!
              System.err.println("Domain " + identification + " received too many answers");
          if (this.nbReceived == this.nbvalues) {
              this.maestro.notifyFinished();
              moveBody();
          }
      }  

This means that each Domain sends its information to all the other Domains, and then waits until it has received all the positions it is waiting for. The other Domains are stored as an array, which is called neighbours. You may find another view of this example on this web page.

5 Groups of Active objects

This is a simple improvement, which allows to have faster communication. You may have noticed the Group capabilities of ProActive. They give us the ability to call an operation on an object which is  a Group, and have it sent to all the members of the Group. We can use them in this framework : first, create a Group (instead of having independant Active Objects) :

           // in the Start class
           Object [][] params = ...
           Domain  domainGroup = null;
           try {
               // Create all the Domains as part of a Group
               domainGroup = (Domain) ProActiveGroup.newGroup ( Domain.class.getName(), params, nodes);
           }
           catch ....>

The double array params stores the parameters passed to the constructors of the Domains we're creating. Domain 0 will have params[0][] passed as arguments, Domain 1 params[1][], and so on. The nodes are the Nodes on which to create these Active Objects. Do notice the try... catch construction, which is needed, like around any creation of Active Objects, because it may raise exceptions. In this previous bit of  code, a Group containing new Active Objects has been created, and all these Objects belong to the group .  You may have noticed that the type of the Group is Domain. It's a bit strange at first, and you may think this reference points to only one Active Object at once, but that's not true. We're accesssing all the objects in the group, and to be able to continue using the methods of the Domain class, the group is typed as Domain, and that's the reason why it's called a typed Group.

Then, this group is passed as parameter to all the members of the Group, in just one call:

           // Still in the Start class
           domainGroup.init(domainGroup, displayer, maestro);

This method sets the local field as a copy of the passed parameter, and as such is unique, and we can play around with it without affecting the others. So let's remove the local Domain from the Group, to avoid having calls on self:

           public void init(Domain domainGroup, Displayer dp, Maestro master) {
              this.neighbours = domainGroup;
              Group g = ProActiveGroup.getGroup(neighbours);
              g.remove(ProActive.getStubOnThis());                 // no need to send information to self
              .....

Remember that in the previous example, the neighbours where stocked in an array, and each was accessed in turn:

           for (int i = 0 ; i < this.neighbours.length ; i ++)
              if (i != this.identification) // don't notify self!
                  this.neighbours[i].setValue(this.info, this.identification);

Well, that's BAAAAD, or at least inefficient! Replace this by the following code, because it works faster :

           this.neighbours.setValue(this.info, this.identification);

This has the following meaning : call the method setValue, with the given parameters, on all the members of the Group neighbours. In one line of code, the method setValue is called on all the Active Objects in the group.
You may find another view of this example on this web page.

6 groupdistrib

Now, do like the idea that the synchronization is centralized on one entity, the Maestro? I don't and it's the bottleneck of the application anyway : once a Domain has finished, it sends the notifyFinshed, and then sits idle. Well, a way of making this better is to remove this bottleneck completely! This is done by using an odd-even scheme : if a Domain receives information from a distant Domain too early (ie in the wrong iteration), this information is stored, and will get used at the next iteration. In the meantime, the local Domain does not change its iteration, because it is still waiting for more results, in the current iteration.

    public void setValue(Planet inf, int receivedIter) {
        if (this.iter == receivedIter) {
            this.currentForce.add(info, inf);
            this.nbReceived ++ ;
            if (this.nbReceived == this.nbvalues)
                moveBody();
        }
        else {
            this.prematureValues.add(new Carrier (inf, receivedIter));
        }
    }

Also notice how the computation is done incrementally when the result is received (this.currentForce.add(info, inf);), instead of when all the results have arrived. This allows for less time spent idle. Indeed, waiting for all the results before computing might leave idle time between setValue requests. And then, just before computing the new position of the body, the sum of all the forces has to be computed. It's better to have this sum ready when needed.
The prematureValues Vector is the place where we put the values that arrive out of sync. When a value is early, it is queued there, and dequeued as soon as this Domain changes iteration.

       public void sendValueToNeighbours() {
       
        reset();
                this.iter++;
       
        if (this.iter < this.maxIter) {     
                    neighbours.setValue(this.info, this.iter);
                    ... // display related code
       
            treatPremature();
                }
                ... // JVM destruction related code
           }

That treatPremature() method simply treats the values that were early as if they had just arrived, by calling the setValue method with the parameters stored.
You may find another view of this example on this web page.

7 Object Oriented SPMD Groups

This is another way to improve the groupcom example. It also removes the master, but this time by inserting oospmd barriers, that can be thought as behaving like the maestro class, but faster. To create functional OOspmd Groups, there is a special instruction, which takes the same parameters as a newGroup instruction :
                      Object [][] params =
             ...
             Domain domainGroup = null;
             try {
                   domainGroup = (Domain) ProSPMD.newSPMDGroup( Domain.class.getName(), params, nodes);
                }
             catch ...

Now, to use this OOspmd group properly, we want to use the barrier() methods. We put these in the Domains code, to do the synchronization. What happens is that each Domain hits the barrier call, and then waits for all the others to have reached it, before reading its request queue again.

        public void sendValueToNeighbours() {
                this.neighbours.setValue(this.info, this.identification);
                ProSPMD.barrier("barrier" + this.iter);
                this.iter++;
                this.asyncRefToSelf.moveBody();    
                ....
Beware, the stop-and-wait is not just after the barrier call, but instead blocks the request queue. So if there is code after that barrier, it will get executed. In fact, the barrier should be seen as a prioritary request on the queue. This explains why we had to put the code after the barrier as a method placed on an asynchronous refernce to self. If we hadn't done it that way, but just appended the code of that method just after the barrier, the call to moveBody() would be executed before the barrier execution, which is exactly what we don't want!
You may find another view of this example on this web page.

8 Barnes-Hut

This way to construct the nbody simulation is based on a very different algorithm. This is inserted to show how one can express this algorithm in ProActive, but breaks off from the previous track, having such a different approach to solving the problem. Here's how it works:

To avoid broadcasting to every active object the new position of every particle, a tree implementation can simplify the problem by agglomerating sets of particles as a single particle, with a mass equal to the sum of masses of the all the particles:. This is the core of the Barnes-Hut algorithm. References on this can be found for example here, and here. This method allows us to have a complexity brought down to O(N log N).

In our parallel implementation, we have defined an Active Object called Domain, which represents a volume in space, and which contains Planets. It is either subdivided into smaller Domains, or is a leaf of the total tree, and then only contains Planets. A Planet is still an Object with mass, velocity and position, but is no longer on a one-to-one connection with a Domain. We have cut down communications to the biggest Domains possible : when a Planet is distant enough, its interactions are not computed, but it is grouped with its local neighbours to a bigger particle. Here is an example of the Domains which would be known by the Domain drawn in red :

   


The Domain in the lower left hand-corner, drawn in blue, is also divided into sub-Domains, but this needs not be known by the Domain in red : it assumes all the particles in the blue Domain are only one big one, centered at the center of mass of all the particles within the blue.

In this version, the Domains communicate with a reduced set of other Domains, spanning on volumes of different sizes. Synchronization is achieved by sending explicitely iteration numbers, and returning when needed older positions. You may notice that some Domains seem desynchronized with other ones, having several iterations inbetween. That is no problem because if they then need to be synchronized and send each other information, a mechanism saving the older positions permits to send them when needed.

You may find another view of this example on this web page.

9 Conclusion

In this guided tour, we tried to show different facilities provided by ProActive, based on a real problem (nbody). We first saw how to deploy the application, then tuned it by adding Group communication, then removed a bottleneck ( due to the hard synchronization ) . Finally, given is the code associated to a different algorithm, which cumbersomely shows how to get Active Objects deployed along a tree structure to communicate. Remember that there is another explanation of all this on the web.