CS 333 Programming Languages
Project 6

Due: Friday, May 9 2025, 11:59 pm

Part I: Parallel Programming in C

This part explores parallel programming in the C language.

Tasks

  1. Confirming Benford's law

    In this task, you will be confirming that data from a (relatively wide) log-normal distribution follows Benford's Law. Benford's Law states that data meeting certain qualifications will have way more leading digits that are 1's than are 9's. This property can be used to detect fraud, so it has gotten lots of attention. Read about Benford's Law on Wikipedia.

    Not only do we want to confirm the data follow Benford's Law, we want to confirm it efficiently. In this project, you will write P-threads code to count the frequency of 1's, 2's, etc. in each element of a data files. The question is: where do you store your counters? Do you use a local variable? Do you use a global variables? Should you use mutexes?

    • Sequential

      Download the code zipfile to it. Then expand the tarball.

      Read the code, compile it, run it, and embrace it. I supply several data files, two of which should have data that follows Benford's Law. Read the comments in benford_sequential.c for more information. The output should indicate that approximately 30% of the leading digits are ones. To compile benford_sequential.c, use the command

       gcc -o benford_sequential my_timing.c benford_sequential.c

    • Parallel

      You will be implementing several parallel versions. All should use 8 threads. Each thread analyzes a section of the data array (the first thread examines indices 0 through N/8-1, the second threads analyzes numbers N/8 through 2*N/8-1, etc.). Note that N is not necessarily divisible by 8, so you will need to account for that.

      To test each Pthreads version, just compare its output to that of the sequential version.

      To compile the Pthreads version, you will need to include the lpthread library. If you name your file benford_par.c, then the command would be 

      gcc -o benford_par my_timing.c benford_par.c -lm -lpthread

      1. Global Counter Array Protected by Single Mutex

        Use a global variable (array of 10 ints) to keep track of the total count of each digit (0 through 9). Since all threads will be reading and writing to it like crazy, we need to protect it with a mutex lock. So, make a global variable mutex lock. For each number the thread analyzes, it locks the lock, updates the counter for the appropriate digit, and then unlocks the lock.

      2. Global Counter Array Protected by Array of Mutexes

        Use a global variable (array of 10 ints) to keep track of the total count of each digit (0 through 9). Since the count for each digit is independent of the count for every other digit, we can protect each digit-counter with its own mutex. So, make a globa variable that contains an array of 10 mutex locks. For each number the thread analyzes, it locks the appropriate lock, updates the corresponding counter, and then unlocks the lock.

      3. Local Counter Array, with Final Update Protected by Single Mutex

        Each thread should use a local variable (array of 10 ints) to keep track of the number of times it sees each digit as a leading digit. After it has looped through its section of the data, it should use one mutex to protect the entire global array of counts and add its local counts to it.

      4. Local Counter Array, with Final Update Protected by Array of Mutexes

        Each thread should use a local variable (array of 10 ints) to keep track of the number of times it sees each digit as a leading digit. After it has looped through its section of the data, it should use one mutex per digit to protect the appropriate entry in the global array of counts and add its local count to it.

      5. Global Counter Array of Arrays, Grouped by Thread, no Mutex

        Use a global variable that is an array of ints with 10*NUMTHREADS entries. The digit counts for each thread should be stored in that array. For this version store the counts for all digits for a single thread together (e.g. thread 0 uses entries 0 through 9, thread 1 uses entries 10 through 19, etc.). Because each thread has its own section of the array, there is no need for a mutex! After all the threads have joined, loop through this new array of arrays, and sum the counts for each digit.

      6. Global Counter Array of Arrays, Grouped by Digit, no Mutex

        Use a global variable that is an array of ints with 10*NUMTHREADS entries. The digit counts for each thread should be stored in that array. For this version store the counts from all the threads for a single digit together (e.g. entries 0 through NUMTHREADS-1 are used to keep track of the number of 0's, entries NUMTHREADS through 2*NUMTHREADS-1 are used to keep track of the number of 1's, etc.). Again, because each thread has its own section of the array, there is no need for a mutex! After all the threads have joined, loop through this new array of arrays, and sum the counts for each digit.

    In your README file, report your data (graphically) and analysis (by writing text). Here's the data we want you to collect: the number of seconds it takes to run each version of the program. You should record this at least 5 times for each program. Drop the min and max values from these 5 and then report the mean of the middle 3. Present the data so that it is as easy to read as possible. You may format your analysis however you would like to, but be sure to answer the following questions in your report:

    1. What conclusions can you draw?
    2. What can you say about the roles of mutex locks for this problem?
    3. In what conditions would you want to use a mutex?

  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. Your code should support 1, 2, and 4 threads.

    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. Include your data graphically, and your analysis as text in the README file.

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

Part II: Parallel Programming in Selected Languages

This part explores parallel programming in the selected language.

Tasks

  1. For your selected language, discuss on a Google Sites 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 selected, Java, or Python}, implement task 2 from part I. Do the same comparative analysis of execution time with different numbers of threads. Here is Java code to start from, if you want to use Java. Here is a Python 3 PPM class you are welcome to use.

    Please note that the above Python 3 PPM class is incompatible with some versions of Python. You can figure out whether your Python supports the Python 3 PPM class by downloading the code and run it by passing an input file from the command to it. The input file can be a .ppm image file, and you can find one in the C-kit provided in the task 2 of Part I. If it doesn't generate appropriate outputs including a new mod.ppm file, it means the class is incompatible with you machine. Then, you can try the following two steps.

    1. Comment out the line 50 self.colors = int(words[2]) in the Python 3 PPM class. Then, try to run it again with a ppm image file. If you still cannot get appropriate outputs, try the following step.

    2. Use the Image module from PIL package. Use Image.open() to open the given ppm image file. Then, invoke the load method from the file handler. The load method will return a pixel map, which is a 2D array of pixels. You can then use multiple threads to manipulate the 2D array.

      Here is a sample code for opening a ppm image file, generate its pixel map, and manipulate each pixel.

      from PIL import Image

img = Image.open(argv[1]) # read the input filename from the command line
pixelmap = img.load() # generate the pixel map for the input image

for i in range(img.size[0]): # loop through the 2D pixel map
	for j in range(img.size[1]):
		pixelmap[i, j] = (i, j, 50) # set the color of each pixel
		
img.show()

      Please refer to the PIL.Image documentation for more information.

      Your code should support 1, 2, and 4 threads, and you should compare how computation time depends upon the number of threads in your report.

Extensions

  1. Write some other useful routine that would be good to parallelize, such as matrix multiplication or an image filter.
  2. Does your second selected language support or use parallelization? If so, do one or both tasks of part I in a second language. If not, could parallelism make it faster? If so, explain how?
  3. Demonstrate the use of a semaphore or mutex lock to control access to a critical section.
  4. Compilable poetry in your selected language.

Please note that it is your responsibility to explicitly indicate the extensions you have taken. If you take the extension in C, please indicate explicitly in the codes and README file. If you take the extensions in the selected languages, please indicate explicitly in your Google Sites report or source codes and README.

Submission

The submission of this project has two components:

  1. Create a folder named Project6_<username> Place the required files into it, zip it, and upload it to the Google Classroom.

    Required Files::

    1. Code: Create a fold for each language, including C and your selected language(s). Place all of your C code and selected language programs to corresponding folders. It should be clear which files correspond to which tasks. All these language folders should be placed into the Project6_<username> folder. Note that the quality of your comments counts toward your grade.
    2. README: We use markdown files for README files. Markdown files are files with the .md filename extension. Each project should have a README file along with all your source codes. The README file will contain:
      • Project identifier, your name, and the submission date.
      • The URL of your Google Sites report.
      • The directory layout for your hand-in folder. You can use the Unix tree command to generate this.
      • Your operating system and C compiler (e.g. use gcc --version).
      • For each task, include how to compile your program, how to run your program, known bugs if there is any, and the program output (a screenshot). The screenshot should include the actual output of running the program if the output is no more than 100 lines. Otherwise, give a brief version of the output.
      • Text and images reporting on the C part of the project.
      • A description of each extension you undertook (for the C part of the project).

      You can follow the instructions for the README file from Project 1.

  2. Google Sites Report: The report of this project should have the following elements.
    • Title of the project and your name
    • A section for each task of part II. Every section should contain the snapshot of your sample programs, the outputs, and your explanations.
    • If you complete extensions in your selected language, please include a section for each extension, providing sample programs, outputs, and explanations.

    To check whether you've made your report well organized, please follow the Organization part in the Google Sites section in this writing page. Remember to publish all your changes and include the homepage link of your CS333 Google Sites in the README file.

© 2025 Ying Li. Page last modified: .