Vector Addition

The problem we will examine is this: we wish to add each element of vector A with its corresponding element in vector B and placing the sum of the two elements in its corresponding location in vector C. This example problem has sometimes been called the “Hello, World” of parallel programming. The reasons for this are:

• the sequential implementation of the code is easy to understand
• the pattern we employ to split the work is used many times in many situations in parallel programming

Once you understand the concept of splitting the work that we illustrate in this example, you should be able to use this pattern in other situations you encounter.

The problem is quite simple and can be illustrated as follows:

We have two arrays, A and B, and array C will contain the addition of corresponding elements in A and B. In this simple example we are illustrating very small arrays containing 8 elements each. Suppose those elements are integers and A and B had the following elements in it:

The elements in array C above depict the result of adding a vector as stored in array A to a vector as stored in array B.

We use very small vectors of size 8 for illustration purposes. A sequential solution to this problem, written in C code, is found in the file named VectorAdd/Serial/VA-sequetial.c in the compressed tar file of examples that accompanies this reading. It looks like this:

#include <stdlib.h>   //malloc and free
#include <stdio.h>    //printf

#define ARRAY_SIZE 8     //Size of arrays whose elements will be added together.

/*
 *  Classic vector addition.
 */
int main (int argc, char *argv[]) 
{
	// elements of arrays a and b will be added
	// and placed in array c
	int * a;
	int * b; 
	int * c;
        
        int n = ARRAY_SIZE;   // number of array elements
	int i;       // loop index
        
        // allocate spce for the arrays
        a = (int *) malloc(sizeof(int)*n);
	b = (int *) malloc(sizeof(int)*n);
	c = (int *) malloc(sizeof(int)*n);

        // initialize arrays a and b with consecutive integer values
	// as a simple example
        for(i=0; i<n; i++) {
            a[i] = i;
        }
        for(i=0; i<n; i++) {
            b[i] = i;
        }   
        
        // Compute the vector addition
        for(i=0; i<n; i++) {
		c[i] = a[i]+b[i];
        }
	
	// Check for correctness (only plausible for small vector size)
	// A test we would eventually leave out
	printf("i\ta[i]\t+\tb[i]\t=\tc[i]\n");
        for(i=0; i<n; i++) {
		printf("%d\t%d\t\t%d\t\t%d\n", i, a[i], b[i], c[i]);
        }
	
        // clean up memory
        free(a);  free(b); free(c);
	
	return 0;
}

Note the for loop that is doing the actual work we desire, beginning on line 35. This depicts what we sometimes refer to as the ‘do N times’ pattern in classical sequential programming. In the next section we will describe how we consider using multiple processing units to do this work in parallel.