Class 21 — Thursday, November 5

Twelve threads at once, and one line that puts them to work on a picture’s rows: how much faster, and why not twelve times.

First the Opening Journal: its prompt is in the announcements on Brightspace.

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.

Every function gets the recipe’s one-line comment. In every function but main, no [ or ]: a walk moves its pointer.

1 Twelve threads at once

Type nproc at the prompt: it prints how many threads the machine can run at once, and on these machines it is 12: six cores, each running two. A program written as one loop uses one of them.

A picture’s rows can be worked on at the same time, as long as no row writes anything another row reads: twelve rows at once. Reading is never the trouble; a row may read every other row of a picture nobody is changing. The Mandelbrot set is such a picture. Each pixel is a point of the plane, and its gray is how many steps z = z * z + c takes to get further than 2 from the origin; a pixel needs only its own column and row.

1.1 mandel.c, on one core

Save the image library beside your files, image.h and image.c, and this program as mandel.c:

#include <stdlib.h>
#include "image.h"

#define MAX 255   // steps before a point counts as inside the set
#define W 2400    // the picture's width
#define H 1800    // and height

// returns how many steps z = z * z + c takes to leave the circle of radius 2, or MAX
int steps(double cr, double ci) {
    double zr = 0;
    double zi = 0;
    for (int n = 0; n < MAX; n++) {
        if (zr * zr + zi * zi > 4) {
            return n;
        }
        double t = zr * zr - zi * zi + cr;
        zi = 2 * zr * zi + ci;
        zr = t;
    }
    return MAX;
}

// paints the w by h picture px with the set: black inside, gray by speed outside
void mandelbrot(unsigned char * px, int w, int h) {
    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);
            int g = n == MAX ? 0 : 255 * n / MAX;
            put_pixel(&p, g, g, g);
        }
    }
}

int main() {
    unsigned char * px = new_image(W, H);
    mandelbrot(px, W, H);
    write_ppm(px, W, H);
    free(px);
}

Each row starts at its own place, px + 3 * y * w, and put_pixel walks along it. Today’s programs are timed, so they get a Makefile of their own, not the course one: save this Makefile beside them.

# Class 21: programs to time.
#   make mandel, make gray: make's own rule builds prog from prog.c with
#   CFLAGS, and the line below adds image.c to it. make -n mandel prints the
#   command without running it.
# -O2 asks gcc for a fast program. The sanitizer is left out: it checks every
# byte a program touches, and would be part of every time you take. To check
# a program with it, once:  make mandel CFLAGS="-Wall -g -fopenmp -fsanitize=address"

CFLAGS = -Wall -g -O2 -fopenmp

mandel gray: image.c

clean:
	rm -f mandel gray

There is no gcc line in it. make has a rule of its own that builds a program from the .c file of the same name with CFLAGS, and mandel gray: image.c adds the library to it: make -n mandel prints the command it would run, cc -Wall -g -O2 -fopenmp mandel.c image.c -o mandel. -O2 asks gcc for a fast program, and the sanitizer is left out, so that it is not part of every time you take. -fopenmp is new, and section 2 says what it is for.

The course Makefile builds with -Wall -g -fsanitize=address and no -O2. Timed on the instructor’s machine, real seconds, mandel with schedule(dynamic) and a 3 by 3 blur of mandel’s picture:

Built with mandel, 1 thread 12 threads blur, 1 thread 12 threads
the course flags 1.30 0.17 0.31 0.10
the same, without the sanitizer 1.28 0.16 0.20 0.08
-O2, without the sanitizer 0.75 0.075 0.037 0.011
-O2, with the sanitizer 0.77 0.10 0.16 0.056

The sanitizer costs mandel almost nothing, because mandel works in a few numbers and touches memory once a pixel; it costs the blur most, because the blur reads nine pixels for every one it writes. -O2 helps both, and the blur most. The sanitizer still finds mistakes the way it always has: build with it once to check, and time without it.

Then make mandel, and run it under time, which prints how long it took:

time ./mandel > m.ppm

Done when m.ppm opens in Loupe (loupe m.ppm) as the set, black in the middle with gray around it, and you have written down the real time.

2 One line

OpenMP, built into gcc with -fopenmp, runs a loop’s turns on several threads at once when one line above the loop asks it to:

#pragma omp parallel for

Before you build it, write in the Journal: on twelve threads, how many times faster will mandel be?

Put that line directly above mandelbrot’s for (int y = 0; ...), build again, and run time ./mandel > m.ppm again. time prints two lines worth reading: real is the time on the clock on the wall, and user is the time all the cores spent, added up.

Done when real is smaller than before, user a little larger, and the picture is the same: OMP_NUM_THREADS=1 ./mandel > one.ppm, then cmp one.ppm m.ppm prints nothing.

3 How many threads

OMP_NUM_THREADS=3 in front of a command runs it on 3 threads:

time OMP_NUM_THREADS=3 ./mandel > m.ppm

To run it for every count in a row, the shell has a loop: for each t in the list, it prints the count and times one run.

for t in 1 2 3 4 8 12; do echo "threads $t"; time OMP_NUM_THREADS=$t ./mandel > m.ppm; done

In a file times.txt, write the real time for each of the six.

Done when times.txt has six lines, a thread count and a time on each.

3.1 A picture that is all black

If your table is done, keep going here; the next part starts when the room stops to look at the tables. Make a copy, cp mandel.c inside.c, and in it change the call to steps so that the picture shows a small square inside the set, where every point is black:

int n = steps(-0.5 + 0.4 * x / w, -0.2 + 0.4 * y / h);

Add inside to the Makefile’s line, mandel gray inside: image.c, then make inside and time ./inside > i.ppm on 1, 2 and 3 threads.

Done when you have the three times, and can say whether 3 threads beat 2 this time, unlike on the whole picture.

3.2 A longer wait

In another copy, cp mandel.c max1000.c, change MAX to 1000, add max1000 to the Makefile’s line, and time ./max1000 > l.ppm on 1, 2 and 3 threads. Open l.ppm too: it is darker, because a gray is 255 * n / MAX.

Done when you have the three times, and can say which pixels the longer wait made slower.

gcc can set a #define itself: -DMAX=1000 on its command line acts as #define MAX 1000. So mandel.c keeps its 255 only when nobody gave another:

#ifndef MAX
#define MAX 255   // steps before a point counts as inside the set
#endif

make’s own rule passes CPPFLAGS to gcc along with CFLAGS, so

make -B mandel CPPFLAGS=-DMAX=1000

builds mandel with MAX 1000. -B makes make build again: it notices a changed file, never a changed flag.

4 Rows that are not equal

OpenMP hands each thread an equal block of rows, one after another: with 3 threads, the first takes the top third, the next the middle third, the last the bottom third. Add schedule(dynamic) to the line,

#pragma omp parallel for schedule(dynamic)

and each thread takes the next row not yet done, as soon as it finishes one. Write the six times again, beside the first ones.

Done when times.txt has a second column, and the picture is still the same as one.ppm.

5 Keep going

For pairs who are done with section 4.

5.1 gray.c, in parallel

Write void gray(unsigned char * px, int w, int h), which gives every pixel the average of its three bytes, one row at a time: the row starts at px + 3 * y * w, and a pointer walks it. Put the line above the row loop, and a main that reads a picture, grays it, writes it and frees it. The Makefile already has its rule: make gray. Time ./gray < m.ppm > g.ppm on 1 thread and on 12.

Done when g.ppm is gray, and you have both times. Are they what section 3 led you to expect?

5.2 The loop alone

time counts the whole program, reading and writing included. To time the loop alone, #include <omp.h>, and around the call:

double start = omp_get_wtime();
gray(px, w, h);
fprintf(stderr, "gray %.3f s\n", omp_get_wtime() - start);

stderr is not redirected by >, so the line reaches the screen while the picture goes to the file. Done when you have the loop’s time on 1 thread and on 12, beside the whole program’s.

5.3 A bigger picture

Make W and H twice as big in mandel.c and time 1 and 12 threads again. Done when you can say whether twelve threads gained more or less than before.

6 Before you leave