Description
-
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.
