CMSE401 Quiz Instructions

This quiz is designed to take approximately 20 minutes to complete (you will be given until the end of the lecture 11.40, i.e. 80 minutes).

This is an open Internet quiz. Feel free to use anything on the Internet with one important exception...

  • DO NOT communicate live with other people during the quiz (either verbally or on-line). The goal here is to find answers to problems as you would in the real world.

Use your time wisely.

Honor Code

I, agree to neither give nor receive any help on this quiz from other people. I also understand that providing answers to questions on this quiz to other students is also an academic misconduct violation as is live communication or receiving answers to questions on this quiz from other people. It is important to me to be a person of integrity and that means that ALL ANSWERS on this quiz are my answers.

✅ DO THIS: Include your name in the line below to acknowledge the above statement:

Put your name here.

Quiz 3: The Collatz problem

In this quiz you are going to verify that for any integer $ n = 1,2,3,\ldots,10,000,000$ the folowing algorithm terminates:

  1. Set $k \leftarrow n$ and $i = 1$
  2. if $k = 1$ stop and record $i$ for this $n$, else goto 2
  3. if $k$ is odd set $k \leftarrow 3k+1$, else set $k \leftarrow k/2$.
  4. Increment the number of iterations $i$ by one.
  5. Goto 1.

✅ Question 1: (10 points) Write a MPI program that splits the 10,000,000 different values for $n$ between $P$ processes.

  1. Each process should write the number of iterations and corresponding values for $n$ to file. The easiest approach is to write $P$ files (one for each process) with the values of $n$ and $P$ files for the number of iterations (or you can write $P$ files with both).
  2. The program should use MPI_Wtime to measure the time it takes from start to finish for your program.
  3. NOTE that you will need to use long long int k = n as $k$ may grow larger than what the standard int can hold.

To get a fair timing you should place a barrier before you measure the final time

  MPI_Init(&argc, &argv);
  double t1,t2;
  t1 = MPI_Wtime();
    //    ....  stuff to be timed  ...

  MPI_Barrier(MPI_COMM_WORLD);
  t2   = MPI_Wtime();
  if (rank==0)
        cout << "MPI_Wtime timing: " << (t2-t1) << endl;
  MPI_Finalize();

Upload the C / C++ file to D2L

✅ Question 2: (5 points) Run the program with 1, 2, 4, 8, 16, 32, & 64 processes and record the times. For example you can use the following batch script

#!/bin/bash
#SBATCH --job-name=Collatz
#SBATCH --nodes=1
#SBATCH --ntasks=64
#SBATCH --mem=25G
#SBATCH --time=0:30:00
#SBATCH --output=%x-%j.SLURMout 

echo `pwd`

rm *.txt

mpirun -np 64 ./a.out 10000000
cat number_* > num.txt
cat iters_* > its.txt

mpirun -np 32 ./a.out 10000000
mpirun -np 16 ./a.out 10000000
mpirun -np 8 ./a.out 10000000
mpirun -np 4 ./a.out 10000000
mpirun -np 2 ./a.out 10000000
mpirun -np 1 ./a.out 10000000

Provide a table (or a list) of $T_1, 2T_2, 4T_4, \ldots$. Here $T_4$ is the time it takes using 4 processes etc.

Ideally, how should the numbers in the table relate to each other?

Put your answer to the above question here.

✅ Question 3: (5 points)

  1. Provide a histogram of the number of itrations with around 100 bins.
  2. Make a scatter plot of the number of iterations as a function of $n$.

Put your answer to the above question here.

Congratulations, you're done with your EXAM

Now, you just need to submit this assignment by uploading it and your program to the course Desire2Learn web page.

Congratulations

You are done with your quiz. Please save the file and upload the jupyter notebook to the D2L dropbox.

Written by Daniel Appelö, Michigan State University Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.