Title image Fall 2018

Due: Friday, 7 December 2018

Part I: Parallel Programming in C

This part explores parallel programming in the C language.

Tasks

The end result of this part should be a set of programs that compare the performance of parallel v. non-parallel code to do the same task.

  1. Write a function that sorts an array. Use parallelism to reduce the computation time. You can use sort functions from the standard library, like qsort in C, or write your own from scratch. Write code that supports 1 thread, 2 threads, or 4 threads. It is an extension to support N threads.

    A simple approach is to divide the array into equal parts, sort each part independently, then recombine the parts into a single sorted array. Just sorting each part independently does not sort the whole array and does not solve the task.

    Your function does not need to be generic, but why not make it so?

    As part of your experimentation, determine how computation time changes with both the number of threads and the size of the problem. Is using two threads twice as fast? Is using four threads four times as fast? What is the improvement in speed with additional threads? How do your findings relate to Amdahl's Law for predicting the degree of speedup?

  2. Write a program that reads an image and applies a pixel-wise operator to it. Use parallelism to reduce the computation time. You can use this C-kit as the basis for your C example. As with task one, your code should support 1, 2, and 4 threads. Supporting N threads is an extension.

    To compile the files, use the following.

    gcc -o colorize -I. colorize.c ppmIO.c -lm

    Compare computation times for the serial and parallel versions. You may need to process the image some number of times in order to make it slow enough to measure accurately.

    As above, you should also compare how computation time depends upon the number of threads.

Part II: Parallel Programming in Selected Languages

This part explores parallel programming in the selected languages.

Tasks

  1. For your list A language, discuss on a wiki page how parallelism is supported in the language, either implicitly or explicitly. This does not need to be a long description, but you may need to do a little research on this in order to be accurate.
  2. In one of {your list A language, Java, or Python}, implement tasks 1 and 2 from above. Do the same comparative analysis of execution time with different numbers of threads. Here is a Python 3 PPM class you are welcome to use.
  3. Does your list B language support or use parallelization? If so, give an example? If not, could parallelism make it faster? If so, explain how?

Extensions

  1. Support an arbitrary number of threads for one or more of the tasks.
  2. Write some other useful routine that would be good to parallelize, such as matrix multiplication or an image filter.
  3. Do one or both tasks of part I in another language (your B language, if it is supported).
  4. Demonstrate the use of a semaphore or mutex lock to control access to a critical section.
  5. Poetry.

Submission

The submission of this project has three components:

  1. Code: The source code for the memory management in C and the selected languages should be submitted to the fileserver along with code for any extensions. Please make the filenames of your source code meaningful.Note that the quality of your comments counts toward your grade.
  2. README: Submit a README file to the fileserver for your C code and the code for your selected languages. The README file can be a .txt file. No matter what, it should be readable from the terminal (no Word or pdf files). It should be well-organized such that readers can easily understand the usage and the outputs of the C code and the code for your selected languages. In addition, any known bugs should be in the README file. Follow the format and content instructions from the writing guide.
  3. Wiki Report: The non-C language pages for this project should have the following elements.

    • Title of the project and your name. Include your partner's name if you worked with someone for the non-C tasks.
    • A section for each task of part II. Each section should contain appropriate snippets of your sample programs, the outputs, and your explanations. Write these as tutorials for other students in the class. Aim for the right level of detail, and define anything that may not be clear. Presenting examples without explanation is insufficient.
    • If you complete extensions in your selected languages, please include a section for each extension, providing sample programs, outputs, and explanations. Be sure to indicate credit, if necessary.

    To check whether you've made your write-up well organized, please follow the Organization part in the Wiki section on this writing page.

Please note that it is your responsibility to explicitly indicate the extensions you have undertaken. If you complete extensions for the C tasks, please indicate that explicitly in the code and README file. If you complete an extension in a selected language, please indicate this explicitly in your wiki report. Along with each extension, indicate if you completed it with a partner.