Parallelization: Area Under a Curve
By Aaron Weeden
Shodor, Durham, North Carolina
This module teaches how to approximate the area under a curve using a Riemann sum, how approximating the area under a curve is used in solutions to scientific problems, how the area under a curve application falls into the MapReduce "dwarf" (a class of algorithms that have similar communication and computation patterns), how to implement parallel code for a MapReduce application (including versions that use distributed memory via the Message Passing Interface (MPI), shared memory via OpenMP, and hybrid via a combination of MPI and OpenMP), and how to measure the performance and scaling of a MapReduce application in multicore and manycore environments.
Upon completion of this module, students should be able to understand the importance of approximating the area under a curve in solving scientific problems, explain the communication and computation patterns of the MapReduce "dwarf", design a parallel algorithm for a MapReduce application, implement it using MPI and/or OpenMP, and measure the scalability of a parallel code over multiple or many cores. The documents can be downloaded below:
Resources:
Module Document (docx) : Module document providing description of approximating the area under a curve and the applications of that approximation to scientific problems, parallel implementation in code, performance and scaling in multicore and manycore environments, and the MapReduce "dwarf".
Exercise 1 (docx) : This exercise will take you through developing the parallel Area Under a Curve algorithm.
Exercise 2 (docx) : This exercise will take you through writing a small piece of C code, outfitting it with MPI and OpenMP directives, and running it on a cluster.
Exercise 3 (docx) : This exercise will take you through strong and weak scaling of the Area Under a Curve parallel code.
area.zip : zip file with coded implementations of the parallel algorithm.
Parallelization_Area_Under_a_Curve : Powerpoint slides for introducing the materials presented in the module document.
Scaling_Area_Under_a_Curve : Powerpoint slides introducing the concepts of scaling, Amdahl's Law, and Gustafson's Law.
Exercise 1 (pdf) : This exercise will take you through developing the parallel Area Under a Curve algorithm.
Exercise 2 (pdf) : This exercise will take you through writing a small piece of C code, outfitting it with MPI and OpenMP directives, and running it on a cluster.
Exercise 3 (pdf) : This exercise will take you through strong and weak scaling of the Area Under a Curve parallel code.
Module Document (pdf) : Module document providing description of approximating the area under a curve and the applications of that approximation to scientific problems, parallel implementation in code, performance and scaling in multicore and manycore environments, and the MapReduce "dwarf".