Final Review

There is no checkoff for this lab. It is intended to be review for a subset of the material that will be covered in the final.

Objectives

• The student will review some of the post-midterm 2 concepts that may appear on the final exam.

Setup

Pull the final review files from the lab starter repository with

git pull staff master

Exercise 1

One of your friends has just learned about concurrency in their computer architecture class and they wanted to try it out! They wrote the parallel.c file to try implementing a lock in place of the OpenMP critical section. You can find the file in the final_review directory.

Let’s first examine your friend’s code.

1. Which section of memory is ARR_SIZE located? How about lock?
2. Your friend has a very unique way of initializing their array and they want you to analyze a particular for loop (which has been highlighted in parallel.c). Given the following assumptions, what is the hit rate of the for loop in question?
   • Assume that the cache starts out cold just before the for loop begins.
   • Your system’s cache is 1 KiB in size, 4-way associative with an LRU replacement policy, and has 16B blocks.
   • ints are 4B
   • Array A starts at 0xF000000, B starts at 0xE000000, and arr starts at 0x1000000.
   • Expressions are evaluated from left to right.
3. The partial_sum variable is intended to be the sum that each thread computes, but you foresee some issues with how it is being declared. What issues could arise with the current implementation, and how could we fix them?
4. Examine your friends implementation of their critical section. You suspect that there are some issues with this implementation. For a 2 thread example, write out the execution order for the critical section that would lead both threads to think that they acquired the lock.

Exercise 2

Let’s say we want to use MapReduce to calculate the frequency of every word for every document it appears in. In other words, if we have the following output:

(("I", "doc1"), 0.03)

that means that the word “I” made up 3% of the words in the document “doc1”. Suppose that documents are stored in the following object:

Document:
    String name
    list<String> text

where the first parameter is the document’s name and the second is its contents represented as a list of words. Given the following map and reduce headers, come up with a method to produce the desired output. For this problem, you have access to the len keyword which returns the length of a list.

map(Document doc):
    # Implementation here

reduce(_____________, _____________):
    # Implementation here

Exercise 3

The Power Iteration method is a way to find the largest eigenvalue of a matrix. The details of why the algorithm works don’t concern us. What does matter is that we are doing repeated matrix-vector and vector-vector multiplications, both of which can be sped up with SIMD. Your task is to fill out the _simd implementations for each of the relevant functions in the simd.c file. To run this file, execute the following commands:

gcc simd.c -o simd -lm -march=haswell -Wall
./simd

No Checkoff