CS61C Fall 2018 Lab 9: Data- and Thread-Level Parallelism

Congrats on finishing a difficult midterm! We're going to dive a deeper into practical parallelism this week, which should get you excited for Project 2. This lab covers a lot of very important ground, so please don't hesitate to ask for help!

CS61C TA helping their student (Cartoon from Liz Climo)

The Lab Files

Pull the Lab 9 files from the lab starter repository with

$ git pull starter master

Part 1: SIMD

NOTE: For this part of the lab, we'll be working in the simd directory:

$  cd simd

Exercise 1: Writing SIMD Code

For Exercise 1, you will vectorize/SIMDize the following code in common.h to speed up the naive implementation shown here:

 long long int sum(unsigned int vals[NUM_ELEMS]) {
  long long int sum = 0;
  
  for(unsigned int w = 0; w < OUTER_ITERATIONS; w++) {
    for(unsigned int i = 0; i < NUM_ELEMS; i++) {
      if(vals[i] >= 128) {
        sum += vals[i];
      }
    } 
  }
  return sum;

Note: you need only vectorize the inner loop.

You might find the following intrinsics useful (Hint: You're going to need all of these functions):

Task: Start with sum, and use SSE instrinsics to implement the sum_simd() function, which needs to be vectorized and achieve a significant amount of speedup.

How do I do this?

Recall that the SSE intrinsics are basically functions which perform operations on multiple pieces of data in a vector in parallel. This turns out to be faster than running through a for loop and applying the operation once for each element in the vector.

In our sum function, we've got a basic structure of iterating through an array. On every iteration, we add an array element to a running sum. To vectorize, you should add a few array elements to a sum vector in parallel and then consolidate the individual values of the sum vector into our desired sum at the end.

Hint 1: __m128i is the data type for 128-Bit vectors which will be handled by Intel's special 128-bit vector. We'll be using them to encode 4 (four) 32-bit ints.

Hint 2: We've left you a vector called _127 which contains four copies of the number 127. You should use this to compare with some stuff when you implement the condition within the sum loop.

Hint 3: DON'T use the store function (_mm_storeu_si128) until after completing the inner loop! It turns out that storing is very costly and performing a store in every iteration will actually cause your code to slow down. However, if you wait until after the outer loop completes you may have overflow issues.

Hint 4: It's bad practice to index into the __m128i vector like they are arrays. You should store them into arrays first with the storeu function, and then access the integers elementwise by indexing into the array.

Hint 5: READ the function declarations in the above table carefully! You'll notice that the loadu and storeu take __m128i* type arguments. You can just cast an int array to a _m128i pointer. Alternatively, you could skip the typecast at the cost of a bunch of compiler warnings.

COMMON LITTLE MISTAKES

The following are bugs that the staff have noticed were preventing students from passing the tests (bold text is what you should not do):

• Trying to store your sum vector into a long long int array. Use an int array. Side note: why?? The return value of this function is indeed a long long int, but that's because an int isn't big enough to hold the sum of all the values across all iterations of the outer loop. However, it is big enough to hold the sum of all the value accross a single iteration of the outer loop. This means you'll want to store your sum vector into an int array after every iteration of the outer loop and add the total sum to the final result result.
• Re-initializing your sum vector. Make sure when you add to your running sum vector, you aren't declaring a new sum vector!!
• Forgetting the CONDITIONAL in the tail case!
• Adding to an UNINITIALIZED array! If you add stuff to your result array without initializing it, you are adding stuff to garbage, which makes the array still garbage! Using storeu before adding stuff is okay though.

To compile your code, run the following command:

$  make simd

To run your code, run the following command:

$ ./simd

Sanity check: The naive version runs at about 25 seconds on the hive machines, and your SIMDized version should run in about 5-6 seconds. The naive function may take a long time to run! Do not try commenting it out, since we rely on that result for comparing against a reference; sometimes code can take a long time to run and this is one of those cases.

Exercise 2: Loop Unrolling

In this exercise, we'll get an additional performance boost for our code with a technique called loop unrolling. Loop unrolling involves reducing the number of iterations a for loop has to go through by doing more work in each iteration of the for loop. For example, consider this very simple example that adds togther the first n elements of an array arr:

int total = 0; 
for (int i = 0; i < n; i++) {
  total += arr[i]; 
}

The corresponding assembly code might look something like this:

      add t0, x0, x0
      add t1, x0, x0 // Initialize loop counter
  loop: beq t0, a1, end // Assume register a1 contains the size n of the array
      slli t2, t1, 2
      add t2, t1, a0 // Assume register a0 contains a pointer to the beginning of the array
      lw t3, 0(t2) // Load arr[i] into t3
      add t0, t3, t0 // total += arr[i]
      addi t1, t1, 1 // Increment the loop counter
      jal x0, loop 
  end: ... 

If we unroll the loop 4 times, this would be our equivalent code, with a tail case for the situations where n is not a multiple of 4:

int total = 0; 
for (int i = 0; i < n / 4 * 4; i+=4) {
  total += arr[i];
  total += arr[i + 1];
  total += arr[i + 2];
  total += arr[i + 3];
}

for (i = n / 4 * 4; i < n; i++) {
  total += arr[i];
}

For the unrolled code, the corresponding assembly code might look something like this:

      add t0, x0, x0
      add t1, a1, x0 // Assume register a1 contains the size n of the array
      srli t1, t1, 2 
      slli t1, t1, 2 // Find largest of multiple 4 <= n
      add t2, x0, x0 // Initialize loop counter
  loop: beq t2, t1, tail
      slli t3, t2, 2
      add t3, t3, a0 // Assume register a0 contains a pointer to the beginning of the array
      lw t4, 0(t3) // Load arr[i] into t3
      add t0, t4, t0 // total += arr[i]
      lw t4, 4(t3) // Load arr[i + 1] into t3
      add t0, t4, t0 
      lw t4, 8(t3), t0 // Load arr[i + 2] into t3
      add t0, t4, t0
      lw t4, 12(t3), // Load arr[i + 3] into t3
      add t0, t4, t0
      addi t2, t2, 4 // Increment the loop counter
      jal x0, loop 
  tail: beq t2, a1, end
      slli t3, t2, 2
      lw t4, 0(t3)
      add t0, t4, t0
      addi t2, t2, 1
  end: ... 

Why does loop unrolling give us a speedup? In the code above, if N was 100, in the "rolled up" code, we would call the instruction beq t0, a1, end 100 times. In the unrolled code, we would call the equivalent instruction beq t2, t1, tail only 25 times. When we cover how the datapath is implemented, we'll learn that branch instructions often take longer to execute than other instructions, because they cause something called a control hazard. Loop unrolling can significantly cut down on the number of branch instructions in our compiled code, leading to a performance improvement. However, don't go crazy and unroll all the way! We need to strike a balance when unrolling our loops; if we increase the number of instructions we have too much, we will start getting misses in our instruction cache.

Carefully unroll the SIMD vector sum code that you created in the previous exercise. This should get you a little more increase in performance from sum_simd (a few fractions of a second). As an example of loop unrolling, consider the supplied function sum_unrolled():

long long int sum_unrolled(unsigned int vals[NUM_ELEMS]) {
  long long int sum = 0;

  for(unsigned int w = 0; w < OUTER_ITERATIONS; w++) { 
    for(unsigned int i = 0; i < NUM_ELEMS / 4 * 4; i += 4) {
      if(vals[i] >= 128) sum += vals[i];
      if(vals[i + 1] >= 128) sum += vals[i + 1];
      if(vals[i + 2] >= 128) sum += vals[i + 2];
      if(vals[i + 3] >= 128) sum += vals[i + 3];
    }

    // This is what we call the TAIL CASE
    for(unsigned int i = NUM_ELEMS / 4 * 4; i < NUM_ELEMS; i++) {
      if (vals[i] >= 128) {
        sum += vals[i];
      }
    }
  }
  return sum;
}

Task: Within common.h, copy your sum_simd() code into sum_simd_unrolled() and unroll it 4 (four) times.

To compile your code, run the following command:

make simd

To run your code, run the following command:

./simd

Part 2: OpenMP

NOTE: For this part of the lab, we'll be working in the openmp directory:

$  cd openmp

      int main() {
      #pragma omp parallel
        {
        int thread_ID = omp_get_thread_num();
        printf(" hello world %d\n", thread_ID);
        }
      }

    $ make hello
    $ ./hello

    void v_add(double* x, double* y, double* z) {
    #pragma omp parallel
    {
    for(int i=0; i<ARRAY_SIZE; i++)
      z[i] = x[i] + y[i];
    }
    }

      int omp_get_num_threads();
      int omp_get_thread_num();

void v_add(double* x, double* y, double* z) {
  #pragma omp parallel
  {
    #pragma omp for
    for(int i=0; i<ARRAY_SIZE; i++)
      z[i] = x[i] + y[i];
  }
}

    $ make v_add
    $ ./v_add

double dotp(double* x, double* y) {
  double global_sum = 0.0;
  #pragma omp parallel
  {
    #pragma omp for
    for(int i=0; i<ARRAY_SIZE; i++)
      #pragma omp critical
        global_sum += x[i] * y[i];
  }
  return global_sum;
}

    $ make dotp
    $ ./dotp

Part 3: Survey