Massively Parallel Problems

A problem is given the designation of Massively Parallel if it fits a number of criteria:

• Almost no interaction between parallel threads calculating independent parts of a solution
• Every single part can be run at the same time

Example

Numerically integrate from $a$ to $b$.

${\int }_0^4(16-x^2)dx=42.\overline{6}$ We can manually calculate this with the Trapezoidal Rule:

• Split the range $\mathrm{0..4}$ into $1000$ parts
• Calculate the area of each in parallel with the trapezoidal rule.
• Sum each one at the end

#include <stdio.h>
#include <pthread.h>
 
#define NUM_SLICES 1000
#define H 4.0/NUM_SLICES
 
double floor(double x) {
	return 16.0 - x*x;
}
 
double trapezoid(double a, double b) {
	return H * (floor(a) + floor(b)) / 2.0;
}
 
void* integrate_section(void* arg) {
	int i = (int) arg;
 
	double a = (int)i * H;
	double b = a + H;
		
	return trapezoid(a, b);
}
 
int main(int argc, const char * argv[]) {
  pthread_t threads[NUM_THREADS];
	ThreadData thread_data[NUM_THREADS]; 
	int* thread_result;
	
	double answer = 0.0;
		
  // Run all thread calculations
	for(int i = 0; i < NUM_SLICES; i++) 
		if (pthread_create(&threads[i], NULL, integrate_section, &i) != 0) {
   		perror("pthread_create failed"); 
   		exit(EXIT_FAILURE);
   	}
 
  // Synchronously collect the results	
   for (int i = 0; i < NUM_THREADS; i++) {
  	  if (pthread_join(threads[i], (void**)&thread_result) != 0) {
  		  perror("pthread_join failed");
  		  exit(EXIT_FAILURE);
  	  } 
  	  answer += thread_result;
  }	
	
	printf("\nAnswer is %f\n", answer);
	return 0;
}