# 程序代写代做代考 c++ AI data structure algorithm CX 4220 / CSE 6220 Introduction to High Performance Computing

CX 4220 / CSE 6220 Introduction to High Performance Computing

Spring 2017

Programming Assignment 1

Due Friday, March 3

In this assignment you will implement an MPI application that evaluates a simple polynomial

in the form of,

y = P (x) = a0 + a1x + a2x

2 + . . . + an−1x

n−1

Making use of what you have learned in class regarding efficient communication between processors,

you are to implement the functions Scatter, Broadcast, ParallelPrefix and PolyEvaluator us-

ing the MPI primitives MPI Send/MPI Recv or MPI Isend/MPI Irecv for a hypercube network.

Function Name Purpose1 Runtime2 Space

Scatter Block decompose an O(n) size array of real numbers

(residing in processor Pi) among p processors such

that each processor will have O(n

p

) elements

O(n) O(n

p

)

Broadcast Broadcast a real number (residing in processor Pi)

among p processors

O(log p) O(1)

ParallelPrefix Run parallel prefix algorithm on p processors by

taking an O(n

p

) element local array of real numbers

and sum/product as the operator as inputs.

O(n

p

+ log p) O(n

p

)

PolyEvaluator Evaluate the polynomial function P (x) for a O(n

p

)

element local array of constants and an x value.

Returns result from the evaluation.

O(n

p

+ log p) O(n

p

)

Your design of the algorithms should adhere to the following:

• You will be graded based on correctness of your algorithms and for efficient implementation

of the functions Broadcast, ParallelPrefix and PolyEvaluator.

• You can implement a naive Scatter function such that Processor Pi having array of size

O(n) simply sends blocks of size O(n

p

) individually to rest of the processors. (i.e., Processor-0

can use O(n) space and does O(n) work for this. At the end each processor will have O(n

p

)

portion of the array).

• DO NOT USE the existing functions MPI Bcast MPI Scatter or MPI Scan.

1for any integer n and p such that n ≥ p > 0

2latency τ and bandwidth µ constants are omitted in the runtime

1

Code Framework

Download the code framework provided at http://b.gatech.edu/2kSZFP1. Implement the func-

tions defined in mpi evaluator.h header file inside mpi evaluator.cpp source file using C language

(avoid having any C++ functions or data structures in your final submission). Additionally in order

for you to test the correctness of the results from running your parallel algorithm you may im-

plement the serial version of the polynomial evaluation by implementing the functions defined in

evaluator.h header file inside evaluator.cpp source file.

Please refer to the README.md provided with the code framework for more details about the struc-

ture of the framework.

Input Format

Input to the application will be 2 files containing the constants (a0, a1, . . . , an−1 where ai ∈ R) of

the polynomial equation and a set of values for x (x0, x1, . . . , xm−1 where xi ∈ R) to evaluate the

polynomial on.

eg:

Listing 1: Constants in polynomial equation

n

a0

a1

a2

. . .

. . .

. . .

an−1

Listing 2: Values of x to evaluate upon

m

x0

x1

x2

. . .

. . .

. . .

xm−1

Teams

You are expected to work in teams of two. You may divide the work among the team members

as you see fit, however we ask the student to be knowledgeable of other team members portion of

contribution to the assignment. All team members in a team will be given the same grade for the

programming assignment.

Testing Your Implementation

You are given access to the Jinx computing cluster. You should test your code locally in your own

computer before you move the testing to the Jinx cluster. However due to limited resources in Jinx

we urge you to not to wait until the last few days before the assignment deadline to use Jinx.

http://b.gatech.edu/2kSZFP1

Before starting the assignment, test your access to Jinx. If you have trouble accessing it, please

contact the TA’s immediately at hpc17ta@lists.gatech.edu. For all other issues you might face in

compiling and/or executing your programs, we recommend you post the problem on piazza for

everyones benefit of learning.

Submission Guideline

This assignment is due March 3, 11:55pm EST on T-Square. One member from each team

should submit zip/tar file containing the following.

1. A text file containing the names of all team members and their contribution in terms of

percentage of work done.

2. All source files. Your implementations should be well commented and easy to read.

3. A report in pdf format containing the following:

• Short design description of your algorithms.

• Graph plots and analysis for run-times of the Broadcast + PolyEvaluator functions

vs. the number of processors for a large n. You pick a fixed and large n that will show

meaningful execution times (i.e., larger than 1 milliseconds) for all p values you have

tested. What observations can you make?

References

Apart from MPI lecture slides, additional helpful resources have being added3 in T-Square to get

you started on working with MPI programs. More resources will be added as needed.

GettingStartedwithMPIlocally.pdf An introductory guide to writing MPI programs

DebuggingMPIprograms.pdf Some helpful hints on how to debug MPI programs

UsingJinx.pdf A simple introduction on the Jinx cluster and how you

can test your programs in it

If you are new to programming in MPI, GettingStartedwithMPIlocally.pdf is a good place

to start. We recommend you code your first MPI hello world program and execute it locally and

in the Jinx cluster before you start working on the assignment.

3We acknowledge the author of these documents Flick, Patrick

hpc17ta@lists.gatech.edu