You are given two parallel algorithms A and B for solving a problem of size n:...

 

Transcribed Image Text:

You are given two parallel algorithms A and B for solving a problem of size n: T(n, n) = n TB(n,n) = nn (a) Which algorithm will run faster on a machine with p processors? Do not make any particular assumption on the values of p. Instead, consider all possible values of p. (b) Now assume you have to run k independent instances of the same problem, each of size n on a p = n processor machine. You can run multiple instances concurrently each using only a subset of the available processors. Which algorithm will finish the fastest? Consider all possible values for k. You are given two parallel algorithms A and B for solving a problem of size n: T(n, n) = n TB(n,n) = nn (a) Which algorithm will run faster on a machine with p processors? Do not make any particular assumption on the values of p. Instead, consider all possible values of p. (b) Now assume you have to run k independent instances of the same problem, each of size n on a p = n processor machine. You can run multiple instances concurrently each using only a subset of the available processors. Which algorithm will finish the fastest? Consider all possible values for k.