CMSE401 Quiz Instructions

This quiz is designed to take approximately 20 minutes to complete (you will be given 50 Minutes).

Please read the following instructions before starting the quiz.

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.

You will be given 20 minutes to complete this quiz. Use your time wisely.

HINTS:

  • Neatness and grammar is important. We will ignore all notes or code we can not read or understand.
  • Read the entire quiz from beginning to end before starting. Not all questions are equal in points vs. time so plan your time accordingly.
  • Some of the information provided my be a distraction. Do not assume you need to understand everything written to answer the questions.
  • Spaces for answers are provided. Delete the prompting text such as "Put your answer to the above question here" and replace it with your answer. Do not leave the prompting text with your answer.
  • Do not assume that the answer must be in the same format of the cell provided. Feel free to change the cell formatting (e.g., markdown to code, and vice versa) or add additional cells as needed to provide your answer.
  • When a question asks for an answer "in your own words" it is still okay to search the Internet for the answer as a reminder. However, we would like you to do more than cut and paste. Make the answer your own.
  • If you get stuck, try not to leave an answer blank. It is better to include some notes or stub functions so we have an idea about your thinking process so we can give you partial credit.
  • Always provid links to any references you find helpful.
  • Feel free to delete the provided check marks (✅) as a way to keep track of which questions you have successfully completed.

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 2: Mandelbrots

classic Mandelbrot image generated using the code in this quiz

The Mandelbrot set has become popular for its aesthetic appeal and as an example of a complex structure arising from the application of simple rules. The study of these types of fractal patterns has helped theorists better understand chaotic systems. There is a close relationship is some scientific simulations which are "sensitive" to their inputs. For example, even a very small changes in the inputs for a "sensitive" simulation results in very large changes in the output. This was first discovered with early weather simulations and is often called the butterfly effect (i.e. the small change in wind velocity input parameter from, say, a butterfly flapping it's wings can cause a significant change in the situation).

For this question the instructor modified some mandelbrot code to use OpenMP. As a useful reference, the original program can be found here on github: https://gist.github.com/andrejbauer/7919569

The modified code is as follows:

/*
  This program is an adaptation of the Mandelbrot program
  from the Programming Rosetta Stone, see
  http://rosettacode.org/wiki/Mandelbrot_set
  Compile the program with:
  gcc -o mandelbrot -O4 mandelbrot.c
  Usage:

  ./mandelbrot <xmin> <xmax> <ymin> <ymax> <maxiter> <res> <out.ppm>
  Example:
  ./mandelbrot 0.27085 0.27100 0.004640 0.004810 1000 1024 pic.ppm
  The interior of Mandelbrot set is black, the levels are gray.
  If you have very many levels, the picture is likely going to be quite
  dark. You can postprocess it to fix the palette. For instance,
  with ImageMagick you can do (assuming the picture was saved to pic.ppm):
  convert -normalize pic.ppm pic.png
  The resulting pic.png is still gray, but the levels will be nicer. You
  can also add colors, for instance:
  convert -negate -normalize -fill blue -tint 100 pic.ppm pic.png
  See http://www.imagemagick.org/Usage/color_mods/ for what ImageMagick
  can do. It can do a lot.
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdint.h>

int main(int argc, char* argv[])
{
  /* Parse the command line arguments. */
  if (argc != 8) {
    printf("Usage:   %s <xmin> <xmax> <ymin> <ymax> <maxiter> <res> <out.ppm>\n", argv[0]);
    printf("Example: %s 0.27085 0.27100 0.004640 0.004810 1000 1024 pic.ppm\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  /* The window in the plane. */
  const double xmin = atof(argv[1]);
  const double xmax = atof(argv[2]);
  const double ymin = atof(argv[3]);
  const double ymax = atof(argv[4]);

  /* Maximum number of iterations, at most 65535. */
  const uint16_t maxiter = (unsigned short)atoi(argv[5]);

  /* Image size, width is given, height is computed. */
  const int xres = atoi(argv[6]);
  const int yres = xres //(xres*(ymax-ymin))/(xmax-xmin);

  /* The output file name */
  const char* filename = argv[7];

  /* Open the output file and write the header. */
  FILE * fp = fopen(filename,"wb");
  char *comment="# Mandelbrot set";/* comment should start with # */

  int * k_vector = (int *) malloc(xres*yres*sizeof(int));
  int **k = malloc(xres * sizeof(int*));
  for (int r=0; r<xres; r++)
      k[r] = &k_vector[r*yres]; 

  /*write ASCII header to the file*/
  fprintf(fp,
          "P6\n# Mandelbrot, xmin=%lf, xmax=%lf, ymin=%lf, ymax=%lf, maxiter=%d\n%d\n%d\n%d\n",
          xmin, xmax, ymin, ymax, maxiter, xres, yres, (maxiter < 256 ? 256 : maxiter));

  /* Precompute pixel width and height. */
  double dx=(xmax-xmin)/xres;
  double dy=(ymax-ymin)/yres;

  //Question 1
  for (int j = 0; j < yres; j++) {
    double y;
    y = ymax - j * dy;
    for(int i = 0; i < xres; i++) {
      double u = 0.0;
      double v= 0.0;
      double u2 = u * u;
      double v2 = v*v;
      double x = xmin + i * dx;
      k[i][j] = 0;
      /* iterate the point */
      for (k[i][j] = 1; k[i][j] < maxiter && (u2 + v2 < 4.0); k[i][j]++) {
            v = 2 * u * v + y;
            u = u2 - v2 + x;
            u2 = u * u;
            v2 = v * v;
      }
    }
  }

  //Question 2
  for (int j = 0; j < yres; j++) {
    for(int i = 0; i < xres; i++) {
      /* compute  pixel color and write it to file */
      if (k[i][j] >= maxiter) {
        /* interior */
        const unsigned char black[] = {0, 0, 0, 0, 0, 0};
        fwrite (black, 6, 1, fp);
      }
      else {
        /* exterior */
        unsigned char color[6];
        color[0] = k[i][j] >> 8;
        color[1] = k[i][j] & 255;
        color[2] = k[i][j] >> 8;
        color[3] = k[i][j] & 255;
        color[4] = k[i][j] >> 8;
        color[5] = k[i][j] & 255;
        //Write color to output file.
        fwrite(color, 6, 1, fp);
      } 
    }
  }

  fclose(fp);
  return 0;
}

Question 1: (5 points) What OpenMP command should be included on the line with the Question 1 comment to make the j loop run in parallel?

Put your answer to the above question here.

Question 2: (5 points) Explain why we can NOT include an omp parallel command at the output loop just after the comment Question 2.

Put your answer to the above question here.

Question 3: (10 points) Explain why dynamic scheduling is probably better for this example.

Put your answer to the above question here.

Question 4: (5 points) The above code has quite a few minor changes from the original code. For example, the declaration of variables x,y,i and j were moved from just before the loops to inside the loop so that each thread will have their own private variables and avoid data collisions. However, one of the bigger modifications is that the variable k was changed from a single integer to an array of integers. In your own words explain why an entire 2D array is necessary.

Put your answer to the above question here

Question 5: (5 points) Assume that the above code is stored in a file named mandelbrot.c, in your current directory. What command(s) are needed to compile the code (with OpenMP and level 3 optimization) on a dev node and make an executable named mandelbrot.

Put the answer to the above question here

The following script runs the mandelbrot command 49 times at high resolution and generates a movie.

#!/bin/bash 
mkdir -p images
for i in {01..49}
do
   bot=$i
   top=`printf "%.2d " $(( 100 - 10#$i ))` 
   time ./mandelbrot .269${bot} .269${top} .004${bot} .004${top} 1000 4096 ./images/pic${i}.ppm
   convert -negate -normalize -fill blue -tint 100 ./images/pic${i}.ppm ./images/pic${i}.png
   rm ./images/pic${i}.ppm
done
rm out.mp4
ffmpeg  -i ./images/pic%02d.png -c:v libx264 -vf fps=25 -pix_fmt yuvj420p out.mp4

Question 6: (10 points) Add SBATCH commands to the above bash script which will allow it to be submitted to the cluster and request a single node on the cluster with 20 cores. Give the program 10 minutes and 10gb of RAM to run.

Question 7: (5 points) This above bash script requires both ImageMagic and FFmpeg programs to be available to run. Modify the above submission script to ensure that the needed paths are set for both programs will run properly.

Question 8: (5 points) Assuming it takes the full 10 minutes to generate 50 frames for a 2 second video (25 frames per second). Estimate how long it will take to generate a 10 minute video. Explain how you came up with this calculation and show your work.

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 to the course Desire2Learn web page for today's dropbox.

DO THIS:

Congratulations

You are done with your quiz. Please save the file and upload the jupyter notebook to the D2L dropbox. Send a message to your Instructor though the zoom chat and let him know you are done and wait until you are excused.

Written by Dr. Dirk Colbry, Michigan State University Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.