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 < E0 < 1, determine asymptotically minimum function f1 such that
    for all  np=\Omega(f1(p)) is E(np,p)>= E0.
  3. Similarly, determine asymptotically maximum function f2 such that
    for all  pn=O(f2(n)) is E(n,pn)>= E0.
  4. What is the scalability of this algorithm?