HW#2 --- last modified March 18 2019 20:23:13.

Solution set.

Due date: Mar 4

Files to be submitted:
  Hw2.zip

Purpose: To gain experience with analyzing and coding parallel algorithms

Related Course Outcomes:

The main course outcomes covered by this assignment are:

CLO2 -- Analyze or code a parallel algorithm using a thread library

CLO3 -- Analyze or code a parallel algorithm using a library such as OpenCL

Specification:

This homework will consist of two parts, a written part and a coding part. Both parts will be submitted in the Hw2.zip file. The written part should be in a file Hw2.pdf. For the written part of the homework you should write solutions for the following questions. In what you turn in, make sure to write the names and student ids for each group member. For each problem, first copy and paste the question, then write your solution to it beneath it.

1. Do problem 27.1-2 out of CLRS.
2. Do problem 27.1-6 out of CLRS.
3. Do problem 27.2-5 out of CLRS.
4. Let `A=(a_{ij})` represent the adjacency matrix of an `n` node graph. I.e., `a_{ij}` is 1 if there is an edge from `i` to `j` and `0` otherwise. Let `A_{trans}=(a'_{ij})` be the adjacency matrix of the transitive closure of `A`. That is, `a'_{ij} =1` if there is a path from `i` to `j` in `A` and 0 otherwise. Design a multithreaded algorithm which computes `A_{trans}` with work `O(n^4)` and span `O(log^3n)`.
5. Suppose we have an array A[1] to A[n] each entry of which has a positive integer. Devise a CREW PRAM algorithm that sets each of these `A[i]`'s to the value of the maximum among `A[i]`'s in `O(log n)` steps using at most `n` processors.

For the coding part of this homework I would like you to write two parallel programs in Java: ThreadOuter.java and JoclOuter.java. These program should computer the outer product of two column vectors `vec v` and `vec w`. I.e., `vec v vec w^T`. The first program makes use of Java Threads and the second makes use of JOCL jar file that provides Java bindings to OpenCL. Both of these programs should compute the norm of a vector of integers that comes from a file. I would like you to code both of your programs so that their spans are `O(log n)`. ThreadOuter.java will be compiled from the command line via:

javac ThreadOuter.java

It can use either classic Java Threads or the Fork Join/Parallel Array frameworks in java.util.concurrent. We didn't talk about the latter so you'll be own your own to learn about if you want to use those. To run your program I will then type:

java ThreadOuter filename_with_vector_data

On this input, your program should read in the contents filename_with_vector_data, which should consist of lines with two comma separated integers followed by a new line character/line, make two vectors `vec x and `vec y` from these, and computes their outer product. Finally, it should output the resulting matrix, entries in a row comma separated, rows delimited by a newline. For example, I might have the file my_vectors.txt with contents:

1,-1
2,1
3,4
10,5

On this input, it should output:

-1,1,4,5
-2,2,8,10
-3,3,12,15
-10,10,40,50

Your JoclOuter.java program should do exactly the same thing, but use JOCL rather than Java Threads. I.e., I'll compile it with

javac JoclOuter.java

You can assume I have set up the classpath to find the JoCL jar file. Then I'll run your program with a line like:

java JoclOuter filename_with_vector_data

For each program you should add a mechanism of your choice to time just the portion of the code in which parallel processing is done (not reading in the file, you probably want to be using System.nanoTime()). I want you to do experiments with both programs varying the length of the vector you compute the outer of. Look up the number of cores the machine you are experimenting on has, and the number of GPU shader processors it has. If you plot time versus the length of vectors you compute the norms of, does it match what you'd expect in each case if Brent's Theorem were an equality rather than an inequality? Write up your experiments also in Hw2.pdf. This timing should be turned off by default.

The above concludes the description of the required homework. I am also willing to give 1 bonus point if you recode your JOCL program in Vulkan and if you show me your Vulkan code working.

Point Breakdown