Programming Assignment 2: Threads CSE 3320
Due: October 9th, 2019 5:30PM
Description
In order to study parallelism, we must have a problem that will take a significant amount of computation. For fun, we will generate images in the Mandelbrot set, which is a well known fractal structure. The set is interesting both mathematically and aesthetically because it has an infinitely recursive structure. You can zoom into any part and find swirls, spirals, snowflakes, and other fun structures, as long as you are willing to do enough computation.
./mandel -x -5 -y 0 -s 2 -o mandel1.bmp
./mandel -x -0.5 -y -0.5 -s 1 -o mandel2.bmp
./mandel -x -0.5 -y -0.5 -s 0.005 -o mandel3.bmp
./mandel -x -0.5 -y -0.5 -s 0.05 -o mandel3.bmp
./mandel -x -0.5 -y -0.5 -s 0.05 -o mandel4.bmp
You will be provided a program that generates images of the Mandelbrot set and saves them as BMP files. Run make to build the code. If you run the program with no arguments, it generates a default image and writes it to mandel.bmp. You can see all of the command line options with mandel -h, and use them to override the defaults. This program uses the escape time algorithm. For each pixel in the image, it starts with the x and y position, and then computes a recurrence relation until it exceeds a fixed value or runs for max iterations.
Then, the pixel is assigned a color according to the number of iterations completed. An easy color scheme is to assign a gray value proportional to the number of iterations.
The max value controls the amount of work done by the algorithm. If we increase max, then we can see much more detail in the set, but it may take much longer to compute. Generally speaking, you need to turn the max value higher as you zoom in. For example, here is the same area in the set computed with four different values of max:
./mandel -x 0.286932 -y 0.014287 -s .0005 -m 50 -o mandel1.bmp
./mandel -x 0.286932 -y 0.014287 -s .0005 -m 100 -o mandel2.bmp
./mandel -x 0.286932 -y 0.014287 -s .0005 -m 500 -o mandel3.bmp
./mandel -x 0.286932 -y 0.014287 -s .0005 -m 1000 -o mandel4.bmp
./mandel -x 0.286932 -y 0.014287 -s .0005 -m 2000 -o mandel5.bmp
Parallel Programming
What does this all have to do with operating systems? It can take a long time to compute a Mandelbrot image. The larger the image, the closer it is to the origin, and the higher the max value, the longer it will take. Suppose that you want to create a movie of high resolution Mandelbrot images, and it is going to take a long time. Your job is to speed up the process by using multiple CPUs. You will do this in two different ways: using multiple processes and using multiple threads.
Find an image
Explore the Mandelbrot space a little bit, and find an interesting area. The more you zoom in, the more interesting it gets, so try to get -s down to 0.0001 or smaller. Play around with -m to get the right amount of detail. Find a configuration that takes about 5 seconds to generate on omega. If you find an image that you like, but it only takes a second or two to create, then increase the size of the image using -W and -H, which will definitely make it run longer.
Part 1: Multiple Threads
Instead of running multiple programs at once, we can take a different approach of making each individual process faster by using multiple threads.
Modify mandel.c to use an arbitrary number of threads to compute the image. Each thread should compute a completely separate band of the image. For example, if you specify three threads and the image is 500 pixels high, then thread 0 should work on lines 0-165, thread 1 should work on lines 166-331, and thread 2 should work on lines 332-499. Add a new command line argument -n to allow the user to specify the number of threads. If -n is not given, assume a default of one thread. Your modified version of mandel should work correctly for any arbitrary number of threads and image configuration. Verify that your modified mandel.c produces the same output as the original.
You may choose to use any threading library as long as your code is in C/C++. If your chosen library is not available on omega I will grant you access to a linux machine with gcc 8.2.1. If you wish to use this machine you must let me know by September 27th, 2019 at 5:00pm. To request access you must use the subject CSE3320 REQUEST and tell me the threading library you wish to use in the body of the email. If you are using a library that is NOT pthreads, C++ threads or openmp I will need to be given a link to an RPM on an official website.
Part 2: Evaluation Report
Write a short lab report that evaluates your parallel version:
¥ In your own words, briefly explain the purpose of the experiments and your experimental setup. Be sure to clearly state what your command line arguments were, so that your results can be reproduced to review your report.
¥ Describe why you chose the threading library and implementation.
¥ For the following two configurations, measure and graph the execution time of multithreaded mandel using 1, 2, 3, 4, 5, 10, and 50 threads. The execution time of these experiments may be upset by other things going on in the machine. So, repeat each measurement ten times, and use the fastest time achieved.
¥ A:mandel-x-.5-y.5-s1-m2000-W2048 -H2048
¥ B: mandel -x 0.2869325 -y 0.0142905 -s .000001 -W 2048 -H 2048 -m 1000
¥ Explain the shape of the two curves. What is the optimal number of threads? Why do
curves A and B have a different shape?
¥ If there any anomalous results be sure to note them and provide an explanation as to why they occurred.
Code
The code for this assignment may be found on the course GitHub page at: https://github.com/CSE3320/Fractal-Assignment
Grading
This assignment must be coded in C or C++. Any other language will result in 0 points. You programs will be compiled and graded on omega.uta.edu. Please make sure they compile and run on omega before submitting them. Code that does not compile on omega will result in a 0.
Good coding style, including clear formatting, sensible variable names, and useful comments. (10%)
A correct implementation of multi-threaded Mandelbrot. (40%)
A lab report which is clearly written using correct English, contains an appropriate description of your experiments, contains correct results that are clearly presented, and draws appropriate conclusions. (50%)
Your programs are to be turned in via Canvas. Submission time is determined by the Canvas system time. You may submit your programs as often as you wish. Only your last submission will be graded.
Academic Integrity
This assignment must be 100% your own work. No code may be copied from friends, previous students, books, web pages, etc. All code submitted is automatically checked against a database of previous semesterÕs graded assignments, current studentÕs code and common web sources. By submitting your code on Canvas you are attesting that you have neither given nor received unauthorized assistance on this work. Code that is copied from an external source, excluding the course github or Canvas, will result in a 0 for the assignment and referral to the Office of Student Conduct.