Assignment 09 (Part 1): Follow the thread

Due Wednesday, April 5, before midnight

The goals for this assignment are:

  • Implement multi-thread algorithms using the pthread library

Update your repository

Do a fetch upstream to obtain the basecode for this assignment.

Using the command line

  • Open terminal and change your current directory to your assignment repository.

  • Run the command git fetch upstream

  • Run the command git merge upstream/master

Your repository should now contain a new folder named A09.

The fetch and merge commands update your repository with any changes from the original.

1. Search

In the file, search.c, implement a program that uses N threads to search for a value in a list. Your program should load the binary file data.bin and then split the workload between the N threads.

$ make search
gcc -g -Wall -Wvla -Werror search.c -o search -lpthreads
$ ./search 2
Enter a value to search: 3
Thread 2 found 3 at index 5003
$ ./search 2
Enter a value to search: 5003
Thread 1 found 5003 at index 3
$ ./search 2
Enter a value to search: -2
Not found!

Requirements:

  • Your program should load the binary file, data.bin. This file stores a sequence of non-sorted integers. The first value in the file holds the number of integers. This class example shows how to read in binary data. Your program should read the first integer to get the size, malloc an array with the given size, and then read in the data as a big block.

  • Your program should split the work of searching through the data between each thread.

2. Threaded Mandelbrot

Implement a multi-threaded version of the mandelbrot set that you implemented for Assignment 09.

In the file, thread_mandelbrot.c, compute a program that outputs a PPM image of the mandelbrot set. You have been given basecode that initializes the following values from command line arguments. This code uses the getopt function.

Arguments:

  • -s <size> the image width and height

  • -l <xmin> the leftmost coordinate, e.g. minimum x value

  • -r <xmax> the rightmost coordinate, e.g. maximum x value

  • -t <ymin> the topmost coordinate, e.g. minimum y value

  • -b <ymax> the bottommost coordinate, e.g. maximum y value

When you run your program, you should get the output such as the following

$ make thread_mandelbrot
$ ./thread_mandelbrot
Generating mandelbrot with size 480x480
  X range = [-2.0000,0.4700]
  Y range = [-1.1200,1.1200]
Thread 140392055985920) sub-image block: cols (0, 240) to rows (0,240)
Thread 140392047593216) sub-image block: cols (240, 480) to rows (0,240)
Thread 140392039200512) sub-image block: cols (0, 240) to rows (240,480)
Thread 140392030807808) sub-image block: cols (240, 480) to rows (240,480)
Thread 140392055985920) finished
Thread 140392047593216) finished
Thread 140392039200512) finished
Thread 140392030807808) finished
Computed mandelbrot set (480x480) in 0.143906 seconds
Writing file: mandelbrot-480-1650116924.ppm

Requirements and hints:

  • You can re-use your PPM and mandelbrot functions from A09. You should re-use your implementation for read/write PPM as well.

  • Create four threads. Each thread should process a quadrant of the image.

  • Print the ids and work tasks for each thread. You can print either the pthread_t ID, or your own given id. Above, we print the pthread_t ID. See the code from class for examples.

  • Allocate an array of pixels using malloc and then save the final image using write_ppm.

  • Do not declare global variables! Use parameters to send data to each thread’s start_routine.

  • You should output the number of seconds needed to compute the image. Use this class example, matrix.c for an example. The performance should be comparable to your multi_mandelbrot version from A09.

  • Your output filename should have the format mandelbrot-<size>-<timestamp>.ppm. The timestamp can be obtained by calling time(0).

  • Set a random seed to ensure that the color palette is different each time, e.g. srand(time(0))

3. Submit your work

Submit both your code and images.

1) Push your code work to github

$ git status
$ git add .
$ git status
$ git commit -m "assignment complete"
$ git status
$ git push
$ git status