Impletement Function Prototypes of The Various Functions Worksheet

For this homework assignment I am giving you three files:

The Homework02.h Download Homework02.h header file which contains the prototypes of the various functions needed

The Homework02.cpp Download Homework02.cpp C++ file which will contain the implementations of the functions defined in Homework02.h.

I am giving you the implementation of two of these functions

computeFTk

initializeOriginal

The file correct-1000.dat Download correct-1000.dat, which contains the Fourier transform of the function defined in initializeOriginal when 1000 data points are used. You can use this file to check whether your program is functioning correctly.

A MS Word document (Homework02Timing.docx) which you will fill out with timing data from your finished program. See below for more details.

Your job will be to implement the other functions defined in Homework02.h and develop a program that can run in a multithreaded way. The DFT is an ideal example of a one-to-one data parallel program that can be multithreaded without synchronization. Please take time to study the source code I’m providing to help understand the variables and functions used in this program!

Homework requirements

Your program must operate in the following manner: Note that there are several layers of helper functions which you must implement.

The program should take two int command-line arguments. The first one is the number of samples in the function (N) and the second is the number of threads to use for the computation (nthreads). If two arguments are not provided, the program should print an error message to standard output and exit with status 0. See the sample output below for details.

Note that you normally would write the error message to standard error and exit with a non-zero status. However, due to limitations in the CODE plugin, you must use standard output and status 0.

The program should define and initialize vectors to hold the original function and its Fourier transform. Because the Fourier transform is complex, you will need two vectors to define the functions — one for the real part and one for the imaginary part. Create and initialize vectors oR, oI, fR, and fI.

The program should then define the original function via a call to the initializeOriginal function. For this assignment, the original function is a sinc functionLinks to an external site. with a = 4.

I am giving you the implementation of initializeOriginal.

After initializing the original function, the program should compute the Fourier transform via a call to the computeFT function, which you will implement based on the prototype in Homework02.h. computeFT should divide the problem across threads in the same manner as discussed in class for one-to-one data parallelism.

The function that each thread runs is computeFTMT, which you will implement based on the prototype. For each value of k that the thread is working on, computeFTMT will call the computeFTk function to calculate the kth component of the Fourier transform.

I am giving you the implementation of computeFTk.

When the computation is complete, you should write out the resulting Fourier transform (k, fR[k] and fI[k]). The code to use for this is available in comments in the Homework02.cpp file.

To check if your program is working correctly, run it for N = 1000 and compare the output with that in the correct-1000.dat file I have provided.

You can do this most efficiently using the diffLinks to an external site. command.

Your program’s output should be exactly the same as what’s in that file — close is not good enough.

You should get the same results regardless of the number of threads you use.

After testing that your program gives the correct output for N = 1000, you will run it for a larger value of N and time the program with /usr/bin/time for different numbers of threads.

For this assignment, your virtual machine will need to be defined with at least 4 processors. Note that this is only necessary after you have written, debugged, and tested the program for N = 1000. To change the number of cores, power off your VM, then edit the virtual machine settings to increase the number of processors to at least 4. You can change this back to its current value after you have completed this assignment.

When your program is working correctly, and you have at least 4 CPUs assigned to your virtual machine, run and time the program for N = 40000 and 1, 2, 3 and 4 threads via

$ /usr/bin/time ./Homework02 40000 1 > /dev/null

$ /usr/bin/time ./Homework02 40000 2 > /dev/null

and so on for 3 and 4 threads. Then use the output of /usr/bin/time to complete the table in the Homework02Timing.docx file. Note: If you are not seeing the elapsed time drop as you increase the number of threads then there is a problem with your multithreading implementation!

Output Samples

No command line arguments

$ ./Homework02

Usage: Homework02 N nthreads

Only one command line arguments

$ ./Homework02

Usage: Homework02 N nthreads

Two command line arguments – 1 thread

$ ./Homework02 10 1

0 3.516133994 0

1 3.513802601 0.1356541907

2 3.503210897 0.3119196779

3 3.447089869 0.6622405087

4 5.195194731 1.038296187

5 5.16526981 1.774031285e-16

6 5.195194731 -1.038296187

7 3.447089869 -0.6622405087

8 3.503210897 -0.3119196779

9 3.513802601 -0.1356541907

Two command line arguments – 4 threads — should be identical to the output with one thread!

$ ./Homework02 10 4

0 3.516133994 0

1 3.513802601 0.1356541907

2 3.503210897 0.3119196779

3 3.447089869 0.6622405087

4 5.195194731 1.038296187

5 5.16526981 1.774031285e-16

6 5.195194731 -1.038296187

7 3.447089869 -0.6622405087

8 3.503210897 -0.3119196779

9 3.513802601 -0.1356541907

This assignment is tailored to the incremental development approach I discussed in class as it’s possible to implement it without multithreading and still get some credit.

A lot of the coding concepts you need can be gleaned from the lecture slides.

DO NOT use global variables!

Make sure that you are compiling with these options: -g -Wall -std=c++17 -O3