Construct a computation dag for which one execution of a greedy scheduler can take nearly twice the time of another execution of a greedy scheduler on the same number of processors. Describe how the two executions would proceed.
Professor Karan measures her deterministic multithreaded algorithm on 4, 10, and 64 processors of an ideal parallel computer using a greedy scheduler. She claims that the three runs yielded T4 D 80 seconds, T10 D 42 seconds, and T64 D 10 seconds. Argue that the professor is either lying or incompetent. (Hint: Use the work law (27.2), the span law (27.3), and inequality (27.5) from Exercise 27.1-3.)
Give pseudocode for an efficient multithreaded algorithm that multiplies a p×q matrix by a q×r matrix. Your algorithm should be highly parallel even if any of p, q, and r are 1. Analyse your algorithm.
4 Let A=(aij) be an n×n matrix. Design a multithreaded algorithm which computes Am wit work O(m⋅n3) and span O(logmlog2n)
Suppose we have an array A[1] to A[n] each entry of which has a positive integer priority. Devise a CREW PRAM algorithm that computes the median of these numbers in O(logn) steps using at most n processors.
