Basic Chares: Primality Testing Exercise

(testing with a chare for each number being tested)

Part A

Write a program based on the outline below. (Note that the program has a few artificial restrictions/elements that are meant to teach you specific concepts. So, please follow the instructions to the letter.)

The main chare generates K random integers, and fires a checkPrimality chare for each. The chare checks if the number given to it is a prime using a variant of the function below, and returns the result to the main chare. The main chare maintains an array of pairs: <number, Boolean>, and prints it at the end. An entry should be added to this array (with the number being tested, and a default value such as "False") as soon as the chare is fired. In particular, you are not allowed to delay adding the entry after the result is returned by the chare. Make sure that your program does not search the array when a response comes. So, figure out a bookkeeping scheme to avoid it.

Obtain K from a command line argument. You may use rand() from the math library for generating random integers.

For testing primality, use the following function. For extra credit, modify it so that it is not testing for every i, but (a) avoids testing even numbers except 2 and (b) don’t let the loop run all the way to “number-1”).

int isPrime(const long number)
{
  if(number<=1) return 0;
  for(int i=2; i<number; i++)
  {
                if(0 == number%i)
                  return 0;
  }
  return 1;
}


Part B (grainsize control)

Measuring performance and improving it via grainsize control:

Grainsize control is a way to improve performance of the above program. Use information from the Charm++ manual about how to pass arrays of data to entry methods, and send a bunch (M) of numbers to be tested to each new Chare, and experiment with different values of M to get good performance. You may wish to read M as a command line parameter, for ease of experimentation. Measure performance by adding two calls to CkTimer() in the main chare, one just before starting creation of checkPrimality chares, and the other after all the results have been returned (but before they are printed), and printing the difference between the timers. You may omit (and probably should omit) printing primality results for performance runs. Vary M and report smallest M for which performance was within 5% infinite grainsize (i.e. $M == K$). Again, make sure our artificial restriction is obeyed: do not send back the numbers the number being tested (because you are not allowed to search for it anyway).

Part C:

Let the numbers being tested be 64 bit random numbers. For simplicity, generate them by concatenating 2 32 bit random numbers.