Class 22 — Tuesday, November 10

Twelve threads adding to one count lose some of the additions: a data race, and two ways to fix it, taking turns and each thread counting its own.

Quiz 8 first, on Brightspace: one attempt now. The second comes near the end of class, when it is announced. Then the Opening Journal: its prompt is in the announcements.

Pairs protocol
  1. The navigator (not typing) says what the next line has to do.
  2. The driver types it, and decides how it becomes C.
  3. If either of you is stuck, drop the roles for a minute and talk it over.
  4. Swap at every section.

Work in Thursday’s folder, with its Makefile: make mandel builds with -O2 -fopenmp.

1 One count, twelve threads

Twelve threads adding to one count. The program from the projector, count.c, does nothing else: twelve threads adding 1, a hundred million times between them.

#include <stdio.h>

#define N 100000000

int main() {
    long count = 0;
    #pragma omp parallel for
    for (long i = 0; i < N; i++) {
        count++;
    }
    printf("count %ld of %d\n", count, N);
}

Build count.c without -O2, as on the projector:

gcc -Wall -g -fopenmp -o count count.c

objdump prints the machine code gcc made from a program. The pragma made the loop into a function, main._omp_fn.0, which every thread runs; ask for that one:

objdump -d -S -M intel --no-show-raw-insn --disassemble=main._omp_fn.0 count

-d turns the machine code back into instructions, -S puts each C line above its own (it needs the -g you built with), -M intel picks how the instructions are spelled, and --no-show-raw-insn leaves out their bytes. Under count++ are five instructions; the numbers on the left may differ:

        count++;
    1223:  mov    rax,QWORD PTR [rbp-0x28]
    1227:  mov    rax,QWORD PTR [rax]
    122a:  lea    rcx,[rax+0x1]
    122e:  mov    rax,QWORD PTR [rbp-0x28]
    1232:  mov    QWORD PTR [rax],rcx
  • 1223 fetches count’s address, which each thread is handed: the threads share count through its address, as a function given &x changes x.
  • 1227 reads count, and 122a adds 1 to it, in another register.
  • 122e fetches the address again, and 1232 writes the new value back.

Between the read at 1227 and the write at 1232, another thread can read the same value, and one of the two additions is lost.

Then build it with -O2, gcc -Wall -g -O2 -fopenmp -o count count.c, and look again. The loop is gone: under count++ is one instruction, add QWORD PTR [rbp+0x0],rax, which adds the thread’s whole share of the hundred million at once. Run it on 12 threads a few times. Is the count right now?

1.1 The black pixels in mandel

How many pixels of the picture are inside the set? Thursday’s mandelbrot can count them as it paints: one variable, black, and one more line where a pixel comes out black. Change it to this:

// paints px with the set, and returns how many of its pixels are inside it
long mandelbrot(unsigned char * px, int w, int h) {
    long black = 0;
    #pragma omp parallel for schedule(dynamic)
    for (int y = 0; y < h; y++) {
        unsigned char * p = px + 3 * y * w;
        for (int x = 0; x < w; x++) {
            int n = steps(-2.0 + 3.0 * x / w, -1.2 + 2.4 * y / h);
            if (n == MAX) {
                black++;
            }
            int g = n == MAX ? 0 : 255 * n / MAX;
            put_pixel(&p, g, g, g);
        }
    }
    return black;
}

and in main, #include <stdio.h> at the top, and the count printed to stderr, so that the picture still goes to the file:

    long black = mandelbrot(px, W, H);
    fprintf(stderr, "black %ld\n", black);

Done when OMP_NUM_THREADS=1 ./mandel > m.ppm prints black 913492, and ./mandel > m.ppm, on twelve threads, run twice, prints two other numbers.

2 Taking turns

The reading, [DIS] 14.7 — Implicit Threading with OpenMP, has a pragma for code that only one thread at a time may run: #pragma omp critical.

2.1 critical above black++

Put #pragma omp critical on the line directly above black++, build, and run twelve threads again.

Done when twelve threads print black 913492, every run. Time it: is it slower than before?

2.2 count.c, with and without critical

If you are done, keep going here; the next part starts when the room stops. In mandel, the count is one line among many; in count.c, from section 1, it is all the work. Save it, and build it without -O2, which would rewrite a loop this simple into one addition: gcc -Wall -g -fopenmp -o count count.c. Time it on 1 thread and on 12, then with #pragma omp critical above count++, on 1 and on 12.

Done when you have four times, and whether each count came out right.

3 Each thread its own count

critical gets the count right by making every addition wait its turn: a hundred million turns. The reading’s countElems takes a turn once per thread instead. Each thread counts into a variable of its own and adds it to the shared count once, at the end.

3.1 The reading’s way, by hand

Write that in count.c, from section 1, in place of its parallel for:

  • #pragma omp parallel above a block, { to }, which every thread runs;
  • inside it, long mine = 0;, which is each thread’s own, because it is declared inside the block;
  • #pragma omp for above the loop, which splits it among the threads as before, and the loop adds 1 to mine;
  • after the loop, still inside the block, count += mine; under #pragma omp critical.

Build it without -O2: gcc -Wall -g -fopenmp -o count count.c.

Done when twelve threads print count 100000000 of 100000000, every run, and you have its time on 1 thread and on 12 beside the four from section 2.2.

3.2 The clause that writes it for you

OpenMP writes section 3.1’s block for you, for one variable, with a clause on the loop’s own line. In mandel, add it to the end of the line you have; schedule(dynamic) is Thursday’s, and stays:

#pragma omp parallel for schedule(dynamic) reduction(+:black)

Take the critical away from black++, put the clause on the line, build, and run twelve threads.

Done when twelve threads print black 913492, every run, and you have the time.

3.3 count.c with the clause

If you are done, keep going here. Back to count.c’s first version, with reduction(+:count) on its parallel for line and no critical, built the same way, on 1 and on 12 threads. Done when both times sit beside those of your block from section 3.1.

4 Keep going

For pairs who are done with section 3.2.

4.1 How many pixels of each gray

Write void histogram(unsigned char * px, int w, int h, long * hist), which counts how many pixels have each gray, 0 to 255, into hist, an array of 256 zeros: the gray is a pixel’s first byte, so *(hist + *p) += 1. In parallel, the reading’s way: inside a #pragma omp parallel, each thread has its own long local[256] = {0}, fills it under #pragma omp for over the rows, and adds it into hist under #pragma omp critical. main reads a picture from the input, counts, and prints hist[0] and the sum of all 256.

Done when ./hist < m.ppm prints the same counts on 1 thread and on 12, the 256 counts add up to w * h, and hist[0] is 913492: why?

4.2 atomic

#pragma omp atomic above count++ makes the one addition safe, without a lock around it. Time count.c with it on 12 threads. Done when its time sits beside critical’s and reduction’s, and you can say which is between which.

5 Before you leave

  • A9 is due Friday, November 13.
  • The second attempt of Quiz 8, now that it is announced, and then the Closing Journal: its prompt is in the announcements.