Let's rewrite the previous program to take advantage of multiple CPUs! The idea is to have a master generating some pieces of work, some workers executing slices of the work and posting their results to the master. Fairly straightforward to write in Java using RMI! Starting with the interface defining the master:

import java.rmi.*;

public interface MersenneServer extends Remote {
  public int[] getInterval() throws RemoteException;
  public void postResult(int[] values) throws RemoteException;
}

Workers simply grab slices of the work and test the integers in the slices are primes:

import java.math.*;
import java.rmi.*;
import java.rmi.server.*;
import java.util.ArrayList;

public class MersenneClient {

  static final BigInteger one  = new BigInteger("1");
  static final BigInteger two  = new BigInteger("2");
  static final BigInteger four = new BigInteger("4");

  public MersenneClient() throws RemoteException {
  }

  private static boolean LucasLehmerTest(int p) {
    BigInteger s = four;
    BigInteger n = one.shiftLeft(p).subtract(one);
    for (int i = 3; i <= p; i++) {
      s = s.multiply(s).subtract(two).mod(n);
    }
    if (s.bitCount() == 0) {
      return true;
    } else {
      return false;
    }
  }


  public static void main(String[] args) {
    String host = args[0];
    String name = "rmi://" + host + "/MersenneSolver";
    System.out.println("Looking up " + name + "...");
    MersenneServer server = null;

    try {
      server = (MersenneServer)Naming.lookup(name);
    } catch (Exception ex) {
      System.out.println("Caught an exception looking up Solver.");
      ex.printStackTrace();
      System.exit(1);
    }

    while (true) {
      try {
        int[] interval = server.getInterval();
        if (interval == null) break; // no more intervals
        ArrayList list = new ArrayList();
        for (int i = interval[0]; i <= interval[1]; i++) {
          if (LucasLehmerTest(i)) {
            list.add(i);
          }
        }
        int[] values = new int[list.size()];
        for (int i = 0; i < list.size(); i++) values[i] = list.get(i);
        server.postResult(values);
      } catch (RemoteException ex) {
        System.out.println("Caught remote exception.");
        System.out.println("Probably server shutdown as all intervals are evaluated");
        System.exit(1);
      }
    }
  }

}

The implementation of the master generates slices and checks if all slices have been evaluated:

import java.rmi.*;
import java.rmi.server.UnicastRemoteObject;
public class MersenneServerImpl extends UnicastRemoteObject implements MersenneServer {

  private int i = 1;
  private int interval = 100;

  //private int totalInterval = 40;
  private int totalInterval = 80;

  public MersenneServerImpl() throws RemoteException {
  }

  // calcuate the Mersenne primes up to 5000
  // break the range into small intervals
  // each client will test the primes within a given interval
  public synchronized int[] getInterval() throws RemoteException {
    if (i >= 5000) return null;
    //if (i >= 3000) return null;
    if (i >= 2000) interval = 50;
    int j = i;
    int k = i + interval-1;
    i = i + interval;
    return new int[] {j, k};
  }

  public synchronized void postResult(int[] values) throws RemoteException {
    for (int i = 0; i < values.length; i++) {
      System.out.println("2^" + values[i] + "-1 is prime");
    }
    // check if we should exit
    totalInterval--;
    if (totalInterval == 0) System.exit(0);
  }

  public static void main(String[] args) {
    try {
      String name = "MersenneSolver";
      System.out.println("Registering Mersenne Solver");
      MersenneServerImpl solver = new MersenneServerImpl();
      Naming.rebind(name, solver);
      System.out.println("Remote Solver ready...");
    } catch (Exception ex) {
      ex.printStackTrace();
    }
  }

}

I first test this program locally using this simple script:

#!/bin/ksh

echo "Starting registry"
rmiregistry &

# Wait until the registry is started
proc=0
while [ "$proc" == 0 ]
do
  proc=$( ps -ef | grep "[r]miregistry" )
  echo $proc is running
  sleep 10
done

echo "Starting server"
java MersenneServerImpl &
sleep 10
echo "Starting client"
java MersenneClient localhost &
sleep 2
echo "Starting client"
java MersenneClient localhost &

Tomorrow, I will go over the Grid Engine commands to actually run this application on a Grid.