4/22/2020 CS 475/575 Project #2
CS 475/575 — Spring Quarter 2020
Project #2
Numeric Integration with OpenMP Reduction 100 Points
Due: April 26
This page was last updated: March 27, 2020
Introduction
We all know that the equation of a unit sphere centered at the origin is x2 + y2 + z2 = 1. But, there is something called a superquadric whose equation is xN + yN + zN = 1. In this exercise, we will use parallel reduction to
compute the volume of a superquadric using N=4.
If you are curious what effect the exponent N has, watch this video.
Using some number of subdivisions in both X and Y, NUMNODESxNUMNODES, take NUMNODES2 height samples. We will think of each height sample as sitting on a 2D tile. That really makes that height sample act as a volume
where the tile is extruded vertically from the bottom to the top.
The tiles in the middle of the floor are full-sized tiles. Tiles along the edges are half-sized. Tiles in the corners are quarter-sized. The volume contribution of each extruded height tile needs to be weighted accordingly. The logic
web.engr.oregonstate.edu/~mjb/cs575/Projects/proj02.html
1/4
4/22/2020 CS 475/575 Project #2
of this is for you to figure out.
Requirements
Center the superquadric around (0,0,0).
Using OpenMP, compute the total volume by using the given Height function. (Note that this will give you Z=0. to Z=Height. As the superquadric is symmetric in the vertical direction, multiply the 0.-Height area you get by 2.)
Use a variety of number of subdivisions (NUMNODES). Pick at least 8 different ones.
Use a variety of number of threads (NUMT). You must use at least 1, 2, and 4.
Record the data in units of something that gets larger as speed increases. Joe Parallel used “MegaHeights Computed Per Second”, but you can use anything that makes sense.
From the speed-up that you are seeing, use the “Inverse Amdahl’s Law” to determine the Parallel Fraction for this application.
From the Parallel Fraction, determine what maximum speed-up you could ever get, regardless of how many cores/threads you throw at this, even with a million cores.
Your commentary write-up (turned in as a PDF file) should include:
1. Tell what machine you ran this on
2. What do you think the actual volume is?
3. Show the performances you achieved in tables and graphs as a function of NUMNODES and NUMT 4. What patterns are you seeing in the speeds?
5. Why do you think it is behaving this way?
6. What is the Parallel Fraction for this application, using the Inverse Amdahl equation?
7. Given that Parallel Fraction, what is the maximum speed-up you could ever get?
The Height-Evaluation Code
In this code sample, NUMNODES is the number of nodes, or dots, subdividing the floor area. So, for example,
NUMNODES=4 means that there are 4 dots on each side edge.
Each node has some amount of tile space surrounding it.
I recommend a single for-loop over all the nodes that looks like this:
#pragma omp parallel for default(none) . . .
web.engr.oregonstate.edu/~mjb/cs575/Projects/proj02.html
2/4
4/22/2020 CS 475/575 Project #2
for( int i = 0; i < NUMNODES*NUMNODES; i++ )
{
int iu = i % NUMNODES;
int iv = i / NUMNODES; float z = Height( iu, iv ); .. .
}
.. .
Depending on what version of OpenMP you are using, you can also say:
#pragma omp parallel for collapse(2) default(none) . . .
for( int iv = 0; iv < NUMNODES; iv++ )
{
for( int iu = 0; iu < NUMNODES; iu++ )
{
.. .
} }
Note! The above pragma lines are not complete. You need to add more to them! The code to evaluate the height at a given iu and iv is:
float
Height( int iu, int iv ) // iu,iv = 0 .. NUMNODES-1
{
}
float x = -1. + 2.*(float)iu /(float)(NUMNODES-1);
float y = -1. + 2.*(float)iv /(float)(NUMNODES-1);
float xn = pow( fabs(x), (double)N );
float yn = pow( fabs(y), (double)N );
float r = 1. - xn - yn;
if( r < 0. )
return 0.;
float height = pow( 1. - xn - yn, 1./(float)N );
return height;
// -1. to +1.
// -1. to +1.
The main Program
Your main program would then look something like this:
#define XMIN -1.
#define XMAX 1.
#define YMIN -1.
#define YMAX 1.
float Height( int, int );
int main( int argc, char *argv[ ] )
{
.. .
// the area of a single full-sized tile:
float fullTileArea = ( ( ( XMAX - XMIN )/(float)(NUMNODES-1) ) *
( ( YMAX - YMIN )/(float)(NUMNODES-1) ) );
web.engr.oregonstate.edu/~mjb/cs575/Projects/proj02.html
3/4
4/22/2020 CS 475/575 Project #2
}
Grading:
// sum up the weighted heights into the variable "volume"
// using an OpenMP for loop and a reduction:
?????
Feature
Points
Results for a variety of NUMNODES values
20
Results for a variety of NUMT values
20
Tables
20
Graphs
20
Correct volume
10
Parallel Fraction and Max spoeedup possible
10
Potential Total
100
web.engr.oregonstate.edu/~mjb/cs575/Projects/proj02.html
4/4