An Introduction to Parallel Programming

Chapter01 - Home
Exercises: 1 - 2 - 3 - 4 - 5 - 6 - 7

Exercise. This is the solution to exercise 1.1 in the book.

Solution. Consider that the cores are numbered 0p 1 (p cores) and the numbers to be added have indices 0n 1 (n numbers, n p). We would obviously like to have as smallest a difference in the number of sums executed by any one processor. This difference is zero when n is divisible by p and one when n is not divisible by p. If there are p1 cores executing a sums and p2 cores executing a + 1 sums, then:

p = p1 + p2 n = p1 a + p2 (a + 1)

We want to choose a such that |p1 p2| is minimized. We have that:

n = a p + p2 n = a p + p p1

Therefore:

p2 p1 = 2n p 2a p

thus we need that:

|2n (2a + 1)p| = min

This expression is minimized when:

a = n p

Therefore,

p2 = n pn p = n mod p p1 = p p1 = p (n mod p)

and thus, the first n mod p cores execute n p sums, while the remaining cores execute n p sums.

 domain_core(j) = jn p(j + 1)n p 1  if 0 j n mod p 1 n mod pn pn mod pn p + n p 1  if j = n mod p (j n mod p 1)n p + n mod pn p + n p (j n mod p)n p + n mod pn p + n p 1n mod p < j p 1

which can be simplified to:

 domain_core(j) = jn p(j + 1)n p 1  if 0 j n mod p 1 n mod pn pn mod pn p + n p 1  if j = n mod p jn p + n mod p(j + 1)n p + n mod p 1n mod p < j p 1

and even further to:

 domain_core(j) = jn p(j + 1)n p 1  if 0 j n mod p 1 jn p + n mod p(j + 1)n p + n mod p 1n mod p j p 1
 
#include <stdio.h> 
#include <stdlib.h> 
#include <ctype.h> 
#include <math.h> 
 
int main(int argc, char **argv){ 
 
    int N_numbers, N_cores, i, floor_value, ceil_value, remainder_value; 
 
    if (argc<5){ 
        printf("Usage: %s -N <numbers> -p <cores>\n", argv[0]); 
        return -1; 
    } 
 
    for (i=1; i<argc; i++){ 
        if ( (0==strncmp(argv[i],"-N",2)) && (argc>(i+1)) && isdigit(argv[i+1][0]) ){ 
            sscanf(argv[i+1], "%d", &N_numbers); 
            i++; 
        } else 
        if ( (0==strncmp(argv[i],"-p",2)) && (argc>(i+1)) && isdigit(argv[i+1][0]) ){ 
            sscanf(argv[i+1], "%d", &N_cores); 
            i++; 
        } else { 
            printf("%s\n", "Unexpected argument. Exiting ..."); 
            printf("Usage: %s -N <numbers> -p <cores>\n", argv[0]); 
            return -1; 
        } 
    } 
    floor_value = floor((double)N_numbers/(double)N_cores); 
    ceil_value = ceil((double)N_numbers/(double)N_cores); 
    remainder_value = N_numbers % N_cores; 
 
    N_cores = (N_numbers >= N_cores) ? N_cores : N_numbers; 
 
    for (i=0; i<N_cores; i++){ 
        if (i <= remainder_value-1){ 
            printf("Core %2d:%3d...%3d\n", i, i*ceil_value, (i+1)*ceil_value-1); 
        }else{ 
            printf("Core %2d:%3d...%3d\n", i, i*floor_value+remainder_value, (i+1)*floor_value+remainder_value-1); 
        } 
    } 
    return 0; 
}