1.1 Case Study: Trapezoidal Program

Under this guide, you can find how to apply MPI in a real world problem

What is the trapezoidal rule?

Recall in calculus, we can use the area of trapezoids to estimate the area under a curve/function, this is commonly used in all mathematics such as integrals, cumulative distribution functions, etc. We want to build a program that exploits the advantage of parallelism and calculate thousands of trapezoids for a specific function

figure 1.1

figure 1.2

Pseudo-code for a serial program

input = a, b, n
h = (b-a)/n
approx = (f(a)+f(b))/2
for i = 1, i <= n-1, i++ {
    x_i = a + i*h
    approx += f(x_i)
}
approx = h*approx

Parallelizing the Trapezoidal Rule

1. Partition problem solutions into tasks – As many tasks as possible.

2. Identify communication channels between tasks.

3. Aggregate tasks into composite tasks.

4. Map composite tasks to cores.

Suppose we have 4 processes, we can assign equal amounts of tasks evenly to all processes, then add them up in the end

Get a, b, n;
h = (b - a) / n;
local_n = n / comm_sz;
local_a = a + my_rank * local_n * h;
local_b = local_a + local_n * h;
local_integral = Trap(local_a, local_b, local_n, h); // Math calculation we can ignore for now

if (my_rank != 0)
    Send local_integral to process 0;
else /* my_rank == 0 */
{
    total_integral = local_integral;
    for (proc = 1; proc < comm_sz; proc++) {
        Receive local_integral from proc;
        total_integral += local_integral;
    }
}

if (my_rank == 0)
    print result;

Tree

We can also treat each process as a tree node, when all the nodes are finished, they can start assembling the final result to the master node

1.3