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

- 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*. - Given a constant
*0 < E*, determine_{0}< 1**asymptotically minimum**function*f*such that_{1}*for all n*is_{p}=\Omega(f_{1}(p))*E(n*._{p},p)>= E_{0} - Similarly, determine
**asymptotically maximum**function*f*such that_{2}*for all p*is_{n}=O(f_{2}(n))*E(n,p*._{n})>= E_{0} - What is the scalability of this algorithm?