Class 22 — Tuesday, November 10
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.
- The navigator (not typing) says what the next line has to do.
- The driver types it, and decides how it becomes C.
- If either of you is stuck, drop the roles for a minute and talk it over.
- 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);
}count++ as the machine runs it
Build count.c without -O2, as on the projector:
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:
-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
1223fetchescount’s address, which each thread is handed: the threads sharecountthrough its address, as a function given&xchangesx.1227readscount, and122aadds 1 to it, in another register.122efetches the address again, and1232writes 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:
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 parallelabove 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 forabove the loop, which splits it among the threads as before, and the loop adds 1 tomine;- 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:
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.