## Java grids and clusters

Many grid and cluster frameworks can host services implemented in Java. In fact, numerous frameworks are implemented entirely in Java. While, the Globus Toolkit 4 (GT4) grid service featured in this article is implemented in Java, the framework is implemented both in Java and in C.

Because GT4 is the reference implementation of the Open Grid Services Architecture (OGSA) based on the Open Grid Services Infrastructure (OGSI), any grid tutorial on grid technology should start with a Globus grid service implementation. The next section describes the parallel algorithm that our example grid service will implement.

## A Globus grid service algorithm

Algorithms can be made parallel by splitting processing into discrete pieces and distributing the work among many workers. Some algorithms lend themselves to this type of parallelization. For instance, it's easier to make algorithms parallel if the results from one piece of work do not have to be fed into another piece of work. For example, searching to find all the primes in the first 1,000 integers can be split into 10 distinct sets of numbers: 1-100, 101-200, etc. Given 10 computers, each of these 10 sets of 100 could be sent to the individual computers, and the time required to find all of the primes would approximately scale with the number of processors. The communication overhead of transmitting 68 prime integer results out of the 1,000 factored is negligible. More important, each of the workers can process its piece of work in isolation from the other workers. In other words, the code for finding primes for 101-1,000 would not need any output from the processing of the first 100 in order to do its work.

In this article, we implement a grid service for testing special primes called Mersenne primes. Mersenne primes are primes of the form 2^p-1. Mersenne primes interest mathematicians because they represent the largest-known primes, and are perfect numbers.

To test for a Mersenne prime, our service will apply the Lucas-Lehmer test using Java's `BigInteger`

class. We must use the `BigInteger`

class to search for new Mersenne primes, because current Mersenne primes significantly exceed the bounds of a `long`

. The `BigInteger`

class implement integers of unbounded size. The Lucas-Lehmer test provides an extremely simple and efficient way to test for primality. The following pseudo-code implements this test:

` ````
mersenne = 2 ^ exponent - 1
lucas = 4
for(i = 3; i <= exponent; i++)
lucas = (lucas ^ 2 - 2 ) % mersenne;
if (lucas == 0) then 2 ^ exponent - 1 is a Mersenne prime
```

As of the writing of this article, the 44th and largest-known Mersenne prime was found by the Great Internet Mersenne Prime Search (GIMPS). The Electronic Frontier Foundation (EFF) is offering a $100,000 prize for the first Mersenne prime found with more than 10 million digits.