Description
In this lab we will be writing code which allows the user to input a polynomial function of x of
arbitrary order. The code will calculate the integral of that polynomial between x = 0 and
x = 100 using several techniques. First, you will use your knowledge of calculus to write code to
analytically evaluate the integral. Then, you will write code to numerically calculate the integral
for various numbers of grid points (subdivisions). Finally, you will write code to farm out the
numerical integration to 10 different cores on the deepthought cluster.
Numerical Integration (Quadrature)
Numerical integration is a powerful technique for integrating any function. In this case, we
happen to be numerically integrating a polynomial that could be analytically integrated
(integrated using pencil and paper to get a closed-form solution). But the numerical integration
code you write will also be capable of integrating functions that are impossible to integrate
analytically.
Fig. 1. Illustration of the use of the ‘rectangle rule’ for numerical integration. The sum of the
areas of the rectangles will approximately equal the integral of the function. A larger number of
thinner rectangles will yield a better approximation.
To understand numerical integration, we must recall the definition of an integral: it is just the
area underneath a function. We will use the simplest numerical approach to (approximately)
calculate that area; namely, breaking up the area into rectangles, as shown in Fig 1. The area of
each rectangle is easy to find, just height times width. As shown in Fig. 2, the width of each
rectangle is dx, which is called the grid spacing. The height of each rectangle is the function
evaluated at one grid point, f(xi), where xi is a grid point. To numerically calculate the integral,
we simply sum up the value of the function at all of the grid points times dx:
� � �� ≈ �� �(�’)
‘
)
*
As shown in Fig. 1, in general a larger number of (thinner) rectangles will result in a better
approximation of the integral.
Fig. 2. Illustrating the meaning of the grid points and grid spacing.
Multithreading
As you know, most modern computer microprocessors have multiple cores. (It has proven more
practical to increase the number of cores rather than increase the clock speed further, which
causes excess heating.) The deepthought cluster is composed of many microprocessors linked
together, each of which has many cores. This incredible parallel computing power does not
automatically accrue benefits to our programs, however. In order to exploit the parallel
processing capabilities of a cluster like deepthought, we must write code that splits up its tasks
into multiple threads, each of which can be performed on a separate core. Some problems are
more amenable to multithreading, and others are less so. Numerical integration happens to
benefit greatly from multithreading, as any integral can be split into a sum of sub-integrals over
smaller ranges:
� � �� =
,-
–
� � �� + � � ��
,-
/-
/-
–
Essentially, we will send each sub-integral to a different core to be evaluated, then sum those
results to get the total result.
Lab Programming Instructions
You must download three files from t-square: integration.cc, gthread.cc, and gthread.h. You
should ONLY modify integration.cc; leave gthread.cc and gthread.h unchanged. The gthread
files were written by Dr. George Riley to provide easy-to-use multithreading functionality, and
their use will be described in class. For the purposes of this lab, you will need to use three
functions provided by gthread: CreateThread, EndThread, and WaitAllThreads.
You should transfer all of the above files to a subdirectory named ‘Lab7’ which you will create
in your home directory on deepthought. Your code must run on deepthought. The correct
command to use when compiling this code on deepthought is as follows:
g++ -std=c++0x integration.cc gthread.cc -lpthread
You must add code to the integration.cc file. The code you should add is described in
extensive comments in that file. Please see the file for more details.
Numerical Notes
Numerical calculations have many peculiarities. Here I will describe two that you need to pay
attention to for this lab.
It is problematic to add a very small number to a very large number on a computer (or subtract
two very large numbers that have a tiny difference). The reason is that the computer only stores
a finite number of significant digits. Let’s say the computer stores 8 digits. If I want to add 1 to
1010, the result on the computer will be: 1.000000e10 + 1.0e0 = 1.0000000e10. The computer
incorrectly decides that 1010 is unchanged by adding one, because it lacks enough digits to store
the change.
This presents a challenge when we are trying to calculate our grid points xi, because the
difference between them (dx) can be very tiny. To mitigate this issue, we should use the
following equation to calculate each xi:
�’ = � ∗ �� + �2’3
Where xmin is the lower bound of the integral.
Another consideration is error. We can define the error as the difference between the exact result
(obtained analytically) and the numerical result. However, the error will never go to zero, so we
need to be able to judge how much error is acceptable. If our calculated error is 1000, that
sounds bad; but in fact it might be very good if the value of the integral is 1015. What is
important, then, is relative error, which is the difference between the exact result and the
numerical result divided by the exact result:
relative error = � � �� exact − � � �� (numerical)
� � �� (exact)
Multiplying this by 100 yields the percent relative error.
Turn-in Procedures
You must submit your source code on the deepthought cluster by using the turnin script, as you
did for Lab 0. You MUST ensure that your code compiles and runs properly on deepthought.
Depending on your section, from your home directory enter one of the following at the command
prompt:
turnin-ece2036a Lab7
or
turnin-ece2036b Lab7
This automatically copies everything in your Lab7 directory to a place that we can access (and
grade) it.
Grading Rubric
GRADING POINT DEDUCTIONS
Element Percentage
Deduction
Details
Does not compile 30% Does not compile on deepthought.
Does not correctly
calculate the analytic
integral
20% Self-explanatory
Does not correctly
calculate the
numerical integral
20% Does not achieve a relative error of less than 10-6 for a
typical cubic polynomial
Does not correctly
use threads to
calculate the
numerical integral
20% Does not show a substantial decrease in execution time
using 10 threads while calculating the same result
Does not use vector
and/or array properly
10% Does not use vector and/or array as indicated in
comments
LATE POLICY
Element Percentage
Deduction
Details
First Day 20% By Monday after the due date
Each Additional Day 20% per day The weekend (Sat/Sun) will count as one day
Sample output from completed code
-bash-4.1$ ./a.out
Welcome to the numerical integrator.
Please enter the coefficient of the 0th-degree term of your
polynomial: 12.3
Please enter the coefficient of the term of degree 1, or ‘x’ to
stop: 1.9
Please enter the coefficient of the term of degree 2, or ‘x’ to
stop: -6.7
Please enter the coefficient of the term of degree 3, or ‘x’ to
stop: 0.5
Please enter the coefficient of the term of degree 4, or ‘x’ to
stop: x
The coefficients you entered were: 12.3 1.9 -6.7 0.5
The analytically calculated integral of your polynomial is:
1.02774e+07
The relative error of the numerical integration with 1000 points
is: -0.0021086
The relative error of the numerical integration with 100000000
points is: -2.10749e-08
The computation time with one thread was: 20 seconds.
The relative error of the numerical integration with 100000000
points and 10 threads is: -2.10749e-08
The computation time with 10 threads was: 2 seconds.