Introduction to Parallel Computing

Ananth Grama

Mentioned 1

A complete source of information on almost all aspects of parallel computing from introduction, to architectures, to programming paradigms, to algorithms, to programming standards. It covers traditional Computer Science algorithms, scientific computing algorithms and data intensive algorithms.

More on

Mentioned in questions and answers.

I am taking a parallel programming class and am really struggling with understanding some of the computational complexity calculations and algebraic simplifications.Specifically for the bitonic sort algorithm I am looking when each processor is given a block of elements.

I am looking at situations when either a hypercube or 2D mesh interconnection network is used. I am given the following definitions for the calculation of Speedup, Efficiency, Iso-Efficiency and determining if the solution is cost optimal. I can understand how Speedup is determined but am totally lost as to how to solve for Efficiency and Iso-Efficiency. I think I understand cost-optimality as well. Given below are the equations.

bitonic sort equations

The text which I am using for the class is

Introduction to Parallel Computing, 2nd Edition by Ananth Grama, Anshul Gupta, George Karypis & Vipin Kumar

For my question regarding the algebra of this problem, please refer to this