ProActive - Eratosthenes example

This program uses the Sieve of Eratosthenes algorithm to find prime numbers. Numbers of increasing size are tested if dividible by any previously found prime number. If this is not the case, the number is a new prime number.
Active objects are used to store the prime numbers and to make the tests, which allows to distribute the calculation on different machines.

Run it!

Scripts

All active objects except Main are migratable using IC2D. You can use this to explore the different latency times implied by calls to Nodes on other VMs or hosts. Pause the application and wait for all containers to finish their current work before migrating.

The parameter -nogui starts the calculation immediately without opening a control window.

Screenshot of the interface

Prime number output is done on the console where you started the application, or on the node where the ConsolePrimeOutputListener is located if you migrated it.

Design

The program stores the prime numbers in a linked list of passive PrimeNumberImpl objects that are controlled by active containers. Each PrimeNumberImpl object has a pointer to the next PrimeNumber, which may be a passive object in the same container, the next container or null, if a bigger prime number has not yet been found.
Testing requests travel the chain of objects inside a container until a divisor is found or the end of the container is reached and the request is automatically being handed over to the next container. If the end of the chain is reached, a new prime number has been found. FIFO serving is required for the active objects in order to ensure that a number is tested with all smaller prime numbers before being declared a new prime number.
The source that enumerates the numbers, the result output handler and the creator of new containers are active objects too.
ActivePrimeContainers have a link towards the previous container, so that they can slow it down if they are overcharged with requests.

The program can be started on a single node or on VirtualNodes described by an XML deployment descriptor. The number source is created on a node described by NumberSource, the output handler on a node described by OutputListener and the active containers in the node(s) described by Containers. Four succeeding ActivePrimeContainer objects are created on a node before continuing with the next node in order to limit network traffic to a reasonable amount. An example of a descriptor is given in descriptors/Eratosthenes.xml.

As a lot of method calls on active objects are produced in this example, requests accumulating in the request queues of the active objects can be observed using IC2D.

Interfaces

public
interface PrimeNumber

public long getValue() - Returns the value of the prime number
public void tryModulo(long n) - Tries a potential prime number

public interface PrimeOutputListener

public void newPrimeNumberFound(long n) - Reports a new prime number

public interface
ActivePrimeContainerCreator

public void newActivePrimeContainer(long n) - Creates a new container

public interface Slowable

public void sleep(boolean sleep) - Makes this container or source sleep or wake up

Active Objects

public class
Main implements ActivePrimeContainerCreator,
InitActive

public void newActivePrimeContainer(long n) - Creates a new container that initially contains the prime number n

public class ActivePrimeContainer implements
PrimeNumber, Slowable, RunActive

public long getValue() - Returns the value of the first prime number in the container
public void tryModulo(long n) - Tries a potential prime number starting with the first prime number in the container
public PrimeNumber newPrimeNumber(long n) - Creates a new passive PrimeNumberImpl object in the container or demands creation of a new container if the maximum size has been reached.
public void sleep(boolean sleep) - Pauses work because of overcharge of the next container

public class NumberSource implements
Slowable, RunActive

public void pause(boolean n) - Switches number producing on or off because of user interaction
public void sleep(boolean sleep) - Switches number producing on or off because of overcharge of the first container

public class ConsolePrimeOutputListener implements
PrimeOutputListener

public void newPrimeNumberFound(long n) - Reports a new prime number to the console

Object Graph

Benchmark

To make a basic test about the influence of distributed calculation, the program was run in a cluster environment with two different settings:

The difference between the single CPU and the multiple CPU setting shows the cost of inter-JVM-communication. With increasing numbers the distributed calculation profits from its CPU power, although the communication between the machines has to be done.

Operating System	Path	Script name	Parameters
Unix	`ProActive/scripts/unix/`	`eratosthenes.sh`	[-nogui] [XML deployment descriptor file]
Windows	`ProActive/scripts/windows/`	`eratosthenes.bat`	[-nogui] [XML deployment descriptor file]

Prime number found	Value	Time: 1 CPU	Time: 8 CPU
2000th	7919	7s	19s
10000th	104729	111s	75s
20000th	224737	494s	187s

Sieve of Eratosthenes example

Description