Section#16: Homework 7
(CS838: Topics in parallel computing, CS1221, Thu, Mar 25, 1999, 8:00-9:15 a.m.)

Performance and scalability of ShearSort

1. Give expressions for parallel time T(N,p), cost C(N,p) and efficiency E(N,p) of ShearSort for sorting N numbers on a mesh of p processors M(\sqrt{p},\sqrt{p}), 1<= p<= N. Assume that the operation Compare&Split of two sorted sequences of k numbers performed by two adjacent processors takes time k.
2. Given a constant 0 < E₀ < 1, determine asymptotically minimum function f₁ such that

   for all  np=\Omega(f1(p)) is E(np,p)>= E0.
   

3. Similarly, determine asymptotically maximum function f₂ such that

   for all  pn=O(f2(n)) is E(n,pn)>= E0.
   

4. What is the scalability of this algorithm?