Homework 7
Due Monday, April 12: on CourseSite, at 11:59pm
CSE 440: Spring 2021
1. Give the work, span, and parallelism for the following: Transpose(A)
1 2 3 4 5 6
n = A.rows parallelforj=2ton
do
parallel for i = 1 to j − 1
do
exchange A[i, j] with A[j, i]
2. Give pseudocode for an efficient multithreaded algorithm that transposes an n × n matrix in place by using divide-and-conquer to divide the matrix recursively into four n2 × n2 submatrices. Give the span and work for this algorithm.
3. The figure below shows an execution of two threads concurrently accessing a FIFO queue Q.
Is this execution possible if Q is linearizable? Why or Why not?
4. In this question, you are asked to investigate whether we can/should use the same elimination concept for linked list-based sets. Assume that the set has three methods: add, remove, and contains; list is sorted; duplicates are not allowed; and methods return true/false based on whether they are successful or unsuccessful. Also, assume that elimination is achieved using a structure similar to the elimination array discussed in lectures, where operations can meet before accessing the actual linked list.
(a) Briefly state how elimination can be made in each of the following cases (a possible answer in some cases is ”elimination cannot be used”):
– add(x) operation meets remove(x) operation – add(x) operation meets contains(x) operation – add(x) operation meets add(x) operation
– add(x) operation meets remove(y) operation
(b) Another concept used in stacks that is similar to elimination is combination: if two non-matching operations (e.g., two push operations) collide in the elimination array, only one thread executes the two operations and forwards the return value of the second operation to the other thread. Can we use the same concept in any of the above cases for sets?
1
(c) Professor Palmieri claims that, unlike stacks, applying the concepts of elimination and combina- tion on sets is overselling the idea and will not improve performance in most of the cases. Do you agree with him? Why or Why not?
Please show details of your work to allow for possible partial credit.
2