Exercises

1. What do you understand by the work and depth of a parallel algorithm? How these are computed for multiprocesor systems?

2. What are the criteria for the design of a parallel algorithm? What stages / operations are retained from sequential algorithms and what not?

3. Find the work-done, depth, and parallelism in the work-depth models shown in figure  (a)-(d).

   Figure: Work-depth models.

   

4. Construct a work-depth model structure such that the work is maximum and depth is minimum.

5. Construct a work-depth model structure such that the depth is maximum and work is minimum.

6. What are the commonly used global-operations in parallel algorithms? How are they implemented? Explain each in detail.