Project 3

Shared Data Histogram with Pthreads

The question

Suppose we have a large collection of scores from 0 through 99. How many fall in each range: 0–9, 10–19, and so on? A histogram records those ten counts. You will build two correct Pthreads programs that divide this counting work and combine the results in different ways.

This uses Module 8’s private result slots and Module 9’s mutex-protected merge. All workers run in one process on one PicoCluster board.

Use the same input every time

We will generate the score at index i with this function. Use it unchanged in both versions:

int score(int i) {
    return (37 * (i % 100) + 11) % 100;
}

The first few scores are 11, 48, 85, 22, 59. A score’s bin is score(i) / 10, using integer division: 11 belongs to bin 1, representing 10–19. Generate scores at indices 0 through N-1. You do not need a random generator or a large input array.

histogram_serial.c supplies a complete serial reference. Read it and try N=5 and N=103 before adding threads:

gcc -Wall -O2 -o histogram_serial histogram_serial.c
./histogram_serial 103

Divide the counting work

Both threaded programs should accept N and the worker count from the command line:

./pth_histogram_slots 103 4
./pth_histogram_mutex 103 4

Support 1 <= N <= 10000000 and 1 <= thread_count <= 16. Reject missing or unsupported input with a clear message. Fixed arrays sized for 16 workers are fine; dynamic allocation is not required. Give workers stable IDs using an ID array as in Module 8.

Use a cyclic loop so every index is handled once, even if the worker count does not divide N:

for (int i = id; i < n; i += thread_count) {
    int bin = score(i) / 10;
    /* Count this value in this worker's histogram. */
}

With five scores and three workers, worker 0 handles indices 0 and 3, worker 1 handles 1 and 4, and worker 2 handles 2. The histogram counts scores, not worker IDs or index ranges.

Version 1: separate result slots

Write pth_histogram_slots.c. Give each worker its own row of a shared array such as partial[16][10], initially zero. Worker id updates only partial[id][bin]. After joining all workers, main combines those rows into a ten-bin result. This version should use no mutex.

Version 2: merge with a mutex

Write pth_histogram_mutex.c. Each worker builds a private int local[10] = {0} in its function. After counting, it takes a common mutex and adds all ten local counts to a shared histogram[10]. Unlock afterward. Each worker should acquire the mutex once for its merge, rather than once per score. Initialize the mutex before creation and destroy it after all joins.

All workers use the same mutex. Main prints and checks the result after the workers finish. Do not replace the mutex with sleeps, volatile, or a guessed order of execution.

Check the answers

In each program, compute a serial reference histogram in main and compare every bin with the threaded result. Print the ten ranges and counts, their total, and PASS or FAIL for the comparison. The bin total should equal N. A matching total alone is insufficient: counts could be assigned to the wrong bins.

N Expected histogram, bins 0–9
5 0 1 1 0 1 1 0 0 1 0
100 10 10 10 10 10 10 10 10 10 10
103 10 11 10 10 11 10 10 10 11 10
1000000 100000 in every bin

Compile both programs with warnings enabled:

gcc -Wall -O2 -pthread -o pth_histogram_slots pth_histogram_slots.c
gcc -Wall -O2 -pthread -o pth_histogram_mutex pth_histogram_mutex.c

For each version, run N=103 with 1, 2, 3, and 4 workers. Also run N=5 with 4 workers and N=1000000 with 1 and 4 workers. The small uneven cases matter: they check that your loop neither skips nor duplicates indices. Test one invalid input, such as zero workers. Run directly with ./program; these programs do not use mpirun.

Explain the design

About one page is enough. Include:

  1. A table of the indices owned by workers 0–2 for N=5 with three workers. Show which bins those scores enter.
  2. Which arrays are shared in each version, which data belongs to one worker, and why the slot version needs no lock.
  3. What the mutex protects in the merge version. Why must it cover the shared additions, and why is locking once per score unnecessary here?
  4. Your correctness results for the required runs. Does changing the number of workers change the histogram? Explain why checking each bin is stronger than checking only the total.

If something fails, show the discrepancy and explain what you checked. Timing is not required. The work per score is small, so do not assume that four workers will be faster.

What to submit

Submit through Moodle:

  • pth_histogram_slots.c and pth_histogram_mutex.c, compiling without warnings using the commands above.
  • Your short explanation and clearly labeled output from the required runs, including the commands and hostname.

Do not submit executables. Keep N and the worker count as command-line arguments so you can change them without recompiling.

Optional experiment

Compare the two correct versions using repeated shell time runs with the same N, worker count, and compiler options. Record real time. Shell time measures the whole program, including the serial correctness check and thread startup; label these as whole-program timings. What overheads might outweigh the saved computation? You may also try a correct version that locks once per score and compare it with the local-merge version. Keep this separate from the required correctness checks.

Back to top