Professor Karan measures her deterministic multi-threaded algorithm on 4, 10, and 64 processors of an ideal parallel computer using a greedy scheduler. She claims that the three runs yielded T₄= 80 seconds, T₁₀= 42 seconds, and T₆₄= 10 seconds. Argue that the professor is either lying or incompetent. Use the work law (27.2), the span law (27.3), and inequality (27.5) from Exercise 27.1-3.

Exercise 27.1-3

Prove that a greedy scheduler achieves the following time bound, which is slightly stronger than the bound proven in Theorem 27.1:

Transcribed Image Text:

T1 – To. Too VI