Build A Parallel MPI Solution

We will approach building an MPI based compute solution by following the steps below:

• Identify the problem
• Writing a function or algorithm which solves a specific compute problem
• Testing that algorithm in a single threaded, single process
• Benchmarking the single process approach
• An approach to dividing the problem into discrete units
  • Implementing an MPI framework on top of the existing function, without requiring any changes to the algorithm itself
• Benchmarking the parallel MPI approach
• Considering limitations to the MPI approach

For the purposes of this MPI example, we are going to use a simple mathematics problem - finding prime numbers in a given (huge!) range.

This is an easy problem to illustrate and write code for, but it is one which demonstrates the thought processes which need to go in to designing your algorithm and the process for deconstructing a large problem into discrete sub-components.

Let us formally define the problem as:

Find all prime numbers between two positive integers supplied by the user (called start and end - also the searchspace) and record the total number of primes found.

Clearly this is relatively fast on modern CPU hardware for a small range, but the larger the range we want to find primes for, the longer the processing will take. Given a large enough search space the problem becomes unsolveable in a reasonable timeframe if approached purely sequentially.

First, we need to write a function which takes our start and end integers and can calculate which prime numbers are in that range. We'll limit the implementation to 32bit integers for simplicity.

In this case we are going to be using the C programming language, but the actual language implementation is not important at this stage - you could be using Python, Fortran, R or any other programming language with MPI bindings.

We write a standalone function called primeCount() which takes the input values start and end, and also returns prime_count, which is the total number of primes found. Because we're writing the algorithm as a standalone function, we will have more flexibility in how we call it later; generally extracting out core logic and algorithms to their own functions usually leads to cleaner applications.

Either extract the file from the downloads .zip file, or save the file below as primes.c:

#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include "primes.h"

uint32_t primeCount(uint32_t start, uint32_t end){
	// Calculate all of the primes between start and end
	// Return a count of how many primes have been found
	// This is *not* the most optimised version, but serves
	// to illustrate the differences in sequential vs parallel processing.
	uint32_t prime_count = 0;
	uint32_t not_prime_count = 0;
	uint32_t div_count = 0;
	uint32_t start_num, end_num, i;
	printf("primeCount: Calculating primes %d - %d\n", start, end);
	for (start_num = start; start_num <= end; start_num++){
		div_count = 0;
        for (i = 2; i * i <= start_num; i++){
            if (start_num % i == 0){
				div_count++;
			}
        }
        if (div_count > 0){
        		// Not prime
        		not_prime_count++;
		} else {
			// Prime
			prime_count++;
		}
    }
    printf("primeCount: Found %d primes\n", prime_count);
    return prime_count;
};

Because it's written in C, and the function is not going to be used directly, but be called by other applications, we will also need a very small header file so that other applications know how to call it (what values it takes and what it returns). Other software we write will treat the actual code inside the function as a black box.

Either extract the file from the downloads .zip file, or save the file below as primes.h:

#include <stdint.h>
uint32_t primeCount(uint32_t start, uint32_t end);

Now that we've written a function to implement our algorithm, we need to move on to the simplest method of testing it.

Let's build a simple implementation which just calls our primeCount() function with two command line parameters (start and end) for the entire searchspace and then prints out the result which primeCount() sends back.

Either extract the file from the downloads .zip file, or save the file below as single.c:

#include "primes.h"
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]){
	uint32_t total_primes = 0;
	uint32_t start = 0;
	uint32_t end = 0;
	
	// Arg1 is the number to start searching from
	if (argv[1]){
		start = atoi(argv[1]);
	}
	// Arg2 is the number to end the search at
	if (argv[2]){
		end = atoi(argv[2]);
	}
	// You must supply both arguments
	if ((start < 2) || (end < 2)){
		printf("You must enter two positive numbers in the range 2 - 2^32\n");
		return 0;
	}
	
	printf("main: Calculating primes in the range %d - %d\n", start, end);
	// Make a single call to the primeCount function, for the entire start-end search space
	total_primes = primeCount(start, end);

	printf("main: Found a total of %d primes\n", total_primes);
	return 0;
}

Compile primes.c and single.c using GCC:

$ module load GCC
$ gcc -c primes.c -o primes.o
$ gcc -c single.c -o single.o

The output should be primes.o and single.o.

With both files compiled we need to create a runnable programme by linking the primes.o library we have created

$ gcc -o single single.o primes.o

The output should be an executable named single.

Now that we have a programme which runs, we can test it:

$ ./single
You must enter two positive numbers in the range 2 - 2^32
$

Okay, let's try with a simple test:

$ ./single 2 100
main: Calculating primes in the range 2 - 100
primeCount: Calculating primes 2 - 100
primeCount: Found 25 primes
main: Found a total of 25 primes
$

It works! We can measure the time by prefixing the command with the Linux time command:

$ time ./single 2 100
main: Calculating primes in the range 2 - 100
primeCount: Calculating primes 2 - 100
primeCount: Found 25 primes
main: Found a total of 25 primes

real	0m0.003s
user	0m0.000s
sys	    0m0.004s

Not very long at all… but let's try increasing the searchspace to see how well it performs…

This looks like we experience an exponential slowdown as we start to increase the search space:

We're going to have tackle the problem in a different way - further increases of the searchspace will quickly become infeasible to calculate in reasonable amounts of time.

• Increasing the amount of workers decreases overall time to solve the problem… but
• Increasing the amount of workers also raises the minimum latency to solve smaller problems
• There is a minimum time to solve - for small problems this is greater than the single process solution as we have to marshal all of the workers, distribute work and mark their results when finished
• There are decreasing gains after a certain threshold - if we run N workers we will never see a speedup of Nx
  • This will vary based on your problem, the algorithm you are using and the architecture of the hardware you are running on - there is no magic number
  • Large numbers of workers on the same node/processor can cause high levels of contention for CPU cache access and memory throughput
• Our problem involved only limited communication between workers and the parent process (hand the input values over and receive the result when complete)
• More complex algorithms that require additional inter-worker communication will have greater overheads, reducing our improvement to an even smaller value of N

You can download all of the scripts used in this example using the link below:

Back to Advanced Slurm Job Optimisation