• Overview
• Prime Finder
• Prime Finder Grid Task
• Executing Grid Task
• Results
• Try It Out!

 View this example as Flash-based presentation!

Overview

The following example demonstrates how easy it is to grid-enable your application with xTier™/GRID. The example used is a simple program called "Prime Finder". The entire application source code will be provided and explained in the following paragraphs. By the end of this page, you’ll understand first hand how easy it is to harness the power of grid computing in your new or existing applications using xTier™/GRID.

We chose to demonstrate xTier™/GRID using the prime finder example because it solves a well known and easily understood mathematical problem: finding the number of prime numbers in a given range. It is a good problem to demonstrate xTier™/GRID because its "problem domain" is relatively simple (and generic) and it is an "embarrassingly parallel" problem and thus easily applicable to grid computing.

Implementing a grid-enabled application with xTier™/GRID is a straight forward task accomplished with three steps as the Prime Finder will demonstrate. First, we will write a simple class that implements the logic of finding the number of primes in a given numeric range. Then we will use this class to write a grid task. Last, we will run this grid task on the grid. Three easy steps, that's all there is to it!

The entire source code one needs to write to run this task is in the following sections. This code will execute on 1 computer, 20 computers, or on a high-performance 100+ node Beowulf cluster with no changes. With xTier™/GRID there’s absolutely no difference what-so-ever in the code or configuration as the application scales. Read on...

 Top
 Grid Service

Prime Finder

For this example we chose one of the simplest methods of searching for prime numbers: wheel factorization (more information can be found, for example, here http://primes.utm.edu/glossary/page.php?sort=WheelFactorization). Below is the full source code for the class that implements that logic (all comments removed):

PrimeFinder.java

1		public class PrimeFinder {
2		static final long[] wheel =
3		new long[] {2, 3, 5};
4		static final long[] spokes =
5		new long[] {1, 7, 11, 13, 17, 19, 23, 29};
6		static final long modulo =
7		wheel[0] * wheel[1] * wheel[2];
8
9		static long findPrimesCount(long min, long max) {
10		long count = 0;
11
12		for (long n = min; n <= max; n++) {
13		if (isPrime(n)) {
14		count++;
15		}
16		}
17
18		return count;
19		}
20
21		static private boolean isPrime(long n) {
22		if (n == 0 || n == 1) {
23		return false;
24		}
25
26		if (n == 2 || n == 3 || n == 5) {
27		return true;
28		}
29
30		for (int i = 0; i < wheel.length; i++) {
31		if (n % wheel[i] == 0) {
32		return false;
33		}
34		}
35
36		long sqrt = Math.round(Math.sqrt(n));
37
38		for (int i = 0; ; i++)  {
39		long d = modulo * (i / spokes.length) +
40		spokes[i % spokes.length];
41
42		if (d > wheel[wheel.length -1]) {
43		if (d <= sqrt) {
44		if (n % d == 0) {
45		return false;
46		}
47		}
48		else {
49		break;
50		}
51		}
52		}
53
54		return true;
55		}
56		}

The static method findPrimesCount(long min, long max) on line 9 is all we need. We pass the range extremities and it returns the number of primes within this range.

Note that this algorithm is far from being efficient (especially for large numbers) and there are many better performing prime finding routines, but for the sake of this example, this approach is simple and sufficient enough.

What is important to note is that this class has nothing to do with a grid computing per-se. It is what usually would be called the domain logic that we will grid-enable in the next chapter. So far, so good...

 Top
 Grid Service

Prime Finder Grid Task

Now to the beefy parts. We want to run this prime finder task on the grid. The reason for that is usually two-fold: we want to run it much faster than we can on a single computer and we want to have better utilization of computers that we have in the grid. The last reason will become more apparent when we get closer to the end. For now, let’s concentrate on making the prime finder task run much faster.

The essence of running something faster on the grid is practically the same old parallel computing axiom: take the task, split it into multiple sub-tasks, and execute these sub-tasks in parallel aggregating results back for overall faster execution.

The following picture illustrates what happens in our trivial example (3 grid nodes + 1 driver node):

xTier™/GRID has direct and simple support for this type of work. The two main concepts that one needs to understand in xTier™/GRID are: grid task and grid task unit.

Grid task is a holder for all grid-specific components that relate to the given grid task such as grid topology resolver, task unit router, failure resolver and task unit factory. For our simple example, however, we will need to create only a task unit factory that will be responsible for creating task units.

Grid task unit is a simple unit of work (a sub-task) belonging to a grid task that "knows" how to execute itself (if needed), split itself into further sub-task units (if needed) and aggregate results from sub-task units (if needed).

A grid task can be logically represented as a tree of task units where leaves are executed locally on their respective nodes, and non-leaf nodes get split into further sub-task units (shown below as the tree node’s children).

Note that this representation is only logical and not physical: for example, the fact that task unit is split does not necessarily mean that sub-task units will be executed on different nodes (although it is usually the case), or in some cases task units can split differently or not split at all on each execution to accommodate for changing grid topology or other conditions.

Every task and task unit has an ID. Both of these IDs define different types of tasks or task units and not the different instances. In the diagram below, for example, the task unit with UID₂ gets split into two sub-task units of the same type and UID₄:

A grid task is simply configured in the 'grid' service XML configuration via IoC-based configuration. The only element that must be provided by the user is a task unit factory (the grid task will automatically use the default implementation for the other elements if their implementations are not provided).

To provide a task unit factory implementation we need to implement two interfaces: GridTaskUnitFactory and GridTaskUnit – and that is almost all you need to do to run an application on the grid!

PrimeGridTaskUnitFactory.java

1		public class PrimeGridTaskUnitFactory implements
2		GridTaskUnitFactory {
3		public GridTaskUnit newTaskUnit(
4		int tid,
5		int uid,
6		long eid) {
7		return new PrimeGridTaskUnit(tid, uid, eid);
8		}
9		}

On line 2 the grid task unit factory takes 3 parameters and creates a new instance of the task unit. Here is the full source code for this task unit:

PrimeGridTaskUnit.java

1		public class PrimeGridTaskUnit1 extends GridTaskUnitAdapter {
2		private static int SUB_TASK_UNIT_ID = 2;
3
4		PrimeGridTaskUnit1(int tid, int uid, long eid) {
5		super(tid, uid, eid);
6		}
7
8		public GridTaskUnitResult aggregate(Set res) {
9		long count = 0;
10
11		Iterator i = res.iterator();
12
13		while (i.hasNext() == true) {
14		MarshalObject obj = (MarshalObject)
15		((GridTaskUnitResult)i.next()).getReturnValue();
16
17		count += obj.getInt64("count");
18		}
19
20		MarshalObject ret = new MarshalObject(1);
21
22		ret.putInt64("count", count);
23
24		return makeResult(GridTaskUnitResult.TASK_UNIT_OK,
25		ret);
26		}
27
28		public GridTaskUnitResult exec(Marshallable arg) {
29		MarshalObject argObj = (MarshalObject)arg;
30
31		MarshalObject retObj = new MarshalObject(1);
32
33		retObj.putInt64("count",
34		PrimeFinder.findPrimesCount(
35		argObj.getInt64("min"),
36		argObj.getInt64("max")
37		)
38		);
39
40		return makeResult(GridTaskUnitResult.TASK_UNIT_OK,
41		retObj);
42		}
43
44		private GridTaskUnitResult makeResult(
45		int retCode, Marshallable retval) {
46		return new GridTaskUnitResultAdapter(
47		retCode,
48		getTaskId(),
49		getUnitId(),
50		getExecId(),
51		retval);
52		}
53
54		public Set split(
55		Set grid,
56		GridTaxonomy tax,
57		Marshallable arg) {
58		if (getUnitId() == SUB_TASK_UNIT_ID) {
59		return null;
60		}
61
62		MarshalObject argObj = (MarshalObject)arg;
63
64		long min = argObj.getInt64("min");
65		long max = argObj.getInt64("max");
66
67		assert max > min;
68
69		Set refs = new HashSet();
70
71		long range = max - min;
72		int optimalSplit = grid.size();
73		int n = Math.min(optimalSplit, (int)range);
74		long split = range / n;
75
76		for (int i = 0; i < n; i++) {
77		MarshalObject obj = new MarshalObject(2);
78
79		obj.putInt64("min", min);
80		obj.putInt64("max", i < n - 1 ? min + split : max);
81
82		min += split + 1;
83
84		refs.add(
85		new GridTaskSplitRefAdapter(
86		getTaskId(),
87		SUB_TASK_UNIT_ID,
88		getExecId(),
89		obj
90		)
91		);
92		}
93
94		return refs;
95		}
96		}

Now, as we mentioned before the grid task unit is responsible for three main tasks (all of which are generally optional): splitting itself into a sub-grid task unit, aggregating results from sub-grid task units, and executing itself locally (without splitting). To do that one needs to provide an implementation for the following three methods:

• public GridTaskUnitResult aggregate(Set res), line 8
• public GridTaskUnitResult exec(Marshallable arg), line 28
• public Set split(Set grid, GridTaxonomy tax, Marshallable arg), line 54

Note that for simplicity this example assumes that it will run in a homogenous environment (all computers in the grid are identical) and we do not account for an uneven distribution of prime numbers. Both of these considerations, however, can be easily added. (The example source code shipped with xTier™ provides for heterogeneous splitting.)

What is important to note is that this is the only code that needs to be written to execute our simple example on a single node, two nodes or 100s of nodes. xTier™/GRID automatically takes care of the underlying topology management, cluster communication, failure resolution and many other aspects of grid task execution. Most of that functionality, however, is pluggable and more advanced examples can take advantage of custom routing or topology resolution, for example.

If you run more than one grid task (which is what happens in reality) xTier™/GRID will enable greater utilization of the grid computing resources through smart topology management coupled with such innovative concepts like pluggable dynamic grid taxonomy and task routing.

 Top
 Grid Service

Executin Grid Task

Once you have started xTier™/GRID on all nodes that you want to include into your example run (examples ship with convenient driver and standby node implementations) the only code you need to execute the grid task is the following:

1		private static final long MIN = 0;
2
3		private static final long MAX = 1500000;
4
5		private static final int PRIME_TID = 1;
6
7		public static void test() {
8		XtierKernel xtier = XtierKernel.getInstance();
9
10		GridService grid = xtier.grid();
11
12		MarshalObject arg = new MarshalObject();
13
14		arg.putInt64("min", MIN);
15		arg.putInt64("max", MAX);
16
17		GridTask task = grid.getTask(PRIME_TID);
18
19		GridTaskResult result = grid.exec(task, arg);
20
21		if (result.isSuccessful() == true) {
22		long n = ((MarshalObject)result.
23		getReturnValue()).getInt64("count");
24		long duration =
25		result.getEndTime() - result.getStartTime();
26
27		System.out.println("Number of primes: " + n);
28		System.out.println("Found in " + duration + " msec.");
29		}
30		else {
31		System.err.println("Grid task failed: " + result);
32		}
33		}

Most of the work happens in lines 12 to 19 where we prepare the arguments for the grid task call and perform the actual grid task execution (line 19).

That is all Java code you need to have for your simple grid application!

 Top
 Grid Service

Results

We have run the prime finder example on a Beowulf cluster in 5, 10, 15, 20 and 25 nodes configuration. Each node had the following characteristics:

Compute Nodes	HP Itanium 2 rx2600 (2 X 900 MHz)
Operating System	Red Hat Advanced Server 3
Memory	2GB / rx2600
Network	Gigabit Ethernet

Each test was performed for a [0 ... 10,000,000] range and yielded 664579 prime numbers. All results were averaged on 5 runs. Ideal (theoretical) durations were calculated based on 5 nodes run.

The following table and charts show the result we obtain for each grid configuration:

Nodes	Actual Duration, ms.	Ideal Duration, ms.
5	26990	26990
10	13293	13450
15	9120	8967
20	7006	6725
25	5705	5380

 Top
 Grid Service

Try It Out

Try it out for yourself! xTier™/GRID ships with fully commented and documentation prime finder example that you can run practically out-of-the-box. Download xTier™ evaluation here and have fun!

 Top
 Grid Service