High Performance Computing

CS-400: Fall 2004

Programming Assignment 1

Recall that the definite integral from a to b of a nonnegative function f(x) can be thought of as the area bounded below by the x-axis, bounded on the sides by the vertical lines x = a and x = b, and bounded above by the graph of the function f(x).

f(x)

x

y

a

b

ò^b_a f(x) dx

A computational approach to estimating the area of this interval is to partition the region into regular geometric shapes and then add the areas of the shapes. In the trapezoidal rule, the regular geometric shapes are trapezoids; each trapezoid has its base on the x-axis, vertical sides at a and b, and its top edge joining two points on f(x). The width of the base depends upon the number of intervals we partition (b - a) into.

A relatively simple parallel version of this algorithm apportions to each parallel process a single trapezoid to compute the area of, followed by a summation of the areas. If we use p processes (processors), then the width of the base of each is
h = (b - a) / p. The first process computes the trapezoid in the interval [a, a + h]. The next process computes the trapezoid in the interval [ a + h, a + 2h]. The last interval is given by [b - h, b].

First write a sequential program to calculate an estimation of the integral of f(x) = x^2, where the program queries the user for the values of a, b, and p and using the trapezoidal algorithm described above.
Next, write a parallel version and use LAM MPI on the Linux machines in Olin 219 to demonstrate your parallel algorithm. A master process can interact with the user and get the values of a and b and then distribute them to all the other processes. The master should participate in the calculation. The summation representing the integral estimate should be reported upon completion by the master process. The number of processes (p) should be determined by the number of processes specified in the MPI launch.
For extra credit, allow the number of trapezoids to differ from the number of parallel processes (and not be an integral multiple).