Class 23 — Thursday, November 12

Threads started by hand: pthread_create and pthread_join, and a struct for each thread with its own share of the work.

First 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 a new folder, class-23, with this Makefile: make hello builds with -O2 -pthread.

1 Threads by hand

OpenMP’s pragma started the threads and split the loop among them. pthreads, the reading’s [DIS] 14.2 — Hello Threading! Writing Your First Multithreaded Program, does neither for you: pthread_create starts a thread running a function you name, and pthread_join waits until it has finished. The function always has the same shape, void * f(void * arg): arg is the address of whatever you handed it, and the function’s first line says what that is.

1.1 hello.c

Make hello.c and build it with make hello, with this Makefile beside it: its CFLAGS has -pthread where the OpenMP one had -fopenmp, which is what pthread_create needs. Then run it a few times:

#include <stdio.h>
#include <pthread.h>

#define THREADS 4

// prints a hello from the thread whose number arg points at
void * hello(void * arg) {
    long * id = (long *) arg;
    printf("hello from thread %ld\n", *id);
    return NULL;
}

int main() {
    pthread_t threads[THREADS];
    long ids[THREADS];
    for (int i = 0; i < THREADS; i++) {
        ids[i] = i;
        pthread_create(&threads[i], NULL, hello, &ids[i]);
    }
    for (int i = 0; i < THREADS; i++) {
        pthread_join(threads[i], NULL);
    }
    printf("all %d joined\n", THREADS);
}

pthread_create takes where to put the new thread’s name, NULL for the usual settings, the function, and the address to hand it.

Done when every run prints four hellos and all 4 joined, and two runs print the hellos in different orders.

1.2 Without the joins

If you are done, keep going here; the next part starts when the room stops. Take the second loop, the one with pthread_join, out of hello.c, build it, and run it several times.

Done when you have seen a run with fewer than four hellos, and can say what all 4 joined now claims that is not true.

2 Each thread its own share

This program changes one thing in hello.c: every thread is handed &i, the address of the loop’s own variable.

int main() {
    pthread_t threads[THREADS];
    long i;
    for (i = 0; i < THREADS; i++) {
        pthread_create(&threads[i], NULL, hello, &i);
    }
    for (int t = 0; t < THREADS; t++) {
        pthread_join(threads[t], NULL);
    }
}

Write in the Journal what its four lines say before it runs.

A thread needs an argument of its own, which nobody changes while it runs. When one number is not enough, a struct holds several: a type of your own, with named fields. For a share of a count, where it starts, where it ends, and what it counted:

// one thread's part of the count
struct share {
    long start;   // the first number it counts
    long end;     // one past its last
    long count;   // how many it counted
};

struct share shares[THREADS]; is an array of them, and shares[t].start is one field of one of them. A thread is handed a struct’s address, and s->start is the field of the struct s points at, the same as (*s).start.

2.1 share.c, the count, a share each

Write share.c, which counts to a hundred million by adding 1 a hundred million times, the additions split among twelve threads you start. It is what OpenMP’s reduction did for you, written out: each thread counts its own share into a variable of its own and leaves the number in its struct, and main adds the twelve. No critical is needed, because main reads a thread’s count only after pthread_join says that thread has finished.

  • #define N 100000000L and #define THREADS 12, and struct share as above.
  • void * count_share(void * arg) starts struct share * s = (struct share *) arg;. It counts from s->start up to s->end into a long mine = 0, a local of its own, and at the end sets s->count = mine;.
  • In main, pthread_t threads[THREADS] and struct share shares[THREADS]. For each t, its share’s start is t * N / THREADS and its end (t + 1) * N / THREADS, and then pthread_create(&threads[t], NULL, count_share, &shares[t]).
  • Then, for each t, pthread_join(threads[t], NULL), and only after it count += shares[t].count. Print count %ld of %ld.

Build it without -O2, which would rewrite a loop this simple into one addition: make -B share CFLAGS="-Wall -g -pthread". Time it, then with THREADS 1.

Done when it prints count 100000000 of 100000000 on every run, with 12 threads and with 1, and you have both times.

2.2 Straight into s->count

If you are done, keep going here. Leave mine out: count_share sets s->count = 0; and adds 1 to s->count itself, every time round. Build it the same way and time it on 12 threads. Nothing is shared between the threads, and still: is it faster than one thread?

Done when you have its time beside the two from 2.1, and a guess at why. Then open the note.

On a lab machine, 2.1 on twelve threads takes about 0.02 s, and this version about 0.18 s: as long as one thread. The program shares nothing; the hardware does.

A core does not read and write memory a byte at a time. It works on cache lines, pieces of 64 bytes, and keeps a copy of each line it is using in its own cache. When one core writes into a line, every other core’s copy of that line is thrown away, and the next time one of them touches it, it has to fetch the line again.

struct share is 24 bytes, so shares[0], shares[1] and most of shares[2] sit in one 64-byte line, and the twelve structs fill five lines between them. In this version each thread writes s->count a hundred million times over twelve, and each write throws the line out of two other cores’ caches, which are writing their own count in the same line. The twelve threads spend their time fetching the same five lines back from each other. That is false sharing: no variable is shared, but the lines holding them are.

In 2.1, mine lives on the thread’s own stack, far from the other threads’ stacks, so each core writes a line no other core is using, and the struct is written once, at the end. Dive Into Systems 14.5 has the same picture, and week 13 measures it on purpose.

2.3 mandel, in bands

For pairs done with 2.2. The Mandelbrot set, painted on threads you start, each thread a band of the picture’s rows. Start from Class 21’s one-thread mandel.c, with image.c and image.h:

  • The body of mandelbrot’s row loop becomes a function of its own, void paint_row(unsigned char * px, int w, int h, int y).
  • struct band holds px, w, h and id, the thread’s number, 0 to THREADS - 1.
  • void * paint_band(void * arg) paints the rows from id * h / THREADS up to (id + 1) * h / THREADS.
  • main makes the picture, starts THREADS threads, each with its band, joins them, and writes the picture. The pragma, if yours has one, comes out.

Done when loupe m.ppm shows the set, and you have its time on 12 threads beside the OpenMP version’s with schedule(dynamic), from your A9 table. Which is faster, and why?

2.4 Rows spread out

For pairs done with 2.3. Give thread id the rows id, id + THREADS, id + 2 * THREADS, and so on to the bottom, instead of a band.

Done when its time on 12 threads is near the OpenMP version’s with schedule(dynamic), and you can say why the bands lost.

3 Before you leave

  • A10 is out, due Wednesday, November 18: A9’s blur on threads you start, on a photo of your own.
  • The Closing Journal: its prompt is in the announcements.