~ $ cd research/parallel-tools && cat README.md

Tools for parallel machines

The first half of the thesis, at UPC and the Barcelona Supercomputing Center between 2003 and 2008. Four pieces of work with one aim: that a program written one line after another can be made parallel by annotating it, a line at a time, on machines that make that hard.

OpenMP on many cores

IBM's Cyclops put 32 cores and 128 hardware threads on one chip, with small caches. A first port of OpenMP to it had scaled poorly. I found why: the threads' stacks were fighting over the same cache lines. I fixed it twice, once in the runtime and once as a change proposed to the hardware, and showed scalability 40% to 100% better than the earlier port, and speed-ups above 80 on the multi-zone benchmarks. Written with IBM T.J. Watson Research; I am first author. IPDPS 2005.

OpenMP without shared memory

The same annotated programs running on a cluster, over software distributed shared memory instead of MPI. It works, and it works best on programs with two levels of parallelism, coarse outside and fine inside. That observation came back six years later.

A simulator of a heterogeneous chip

CellSim, a modular simulator of the Cell processor, built by two teams; I am third author of its papers. The accelerator cores are the other team's. Ours was the rest, and what I wrote is its base: the general-purpose core, which is an interpreter of its PowerPC instructions; the emulation of the operating system under it, where a system call runs natively and reaches into the simulated program's memory as it needs to; the loader that puts a compiled binary in that memory; and the protocol by which modules talk to each other purely as memory accesses, so that any of them can be connected to any other. A program compiled for the real chip ran on it unchanged: only the library of system calls and threads had to be swapped for mine. My thesis calls the protocol its best contribution. The paper, at the BSC.

A compiler for streams

In the European project ACOTES, with NXP, IBM Haifa, INRIA and STMicroelectronics: annotations that turn a serial C program into a pipeline of tasks passing data along. Two clauses, input and output, are enough. I wrote the ACOTES phase of the BSC's Mercurium compiler — the compiler itself is not mine — with its runtime library and a tracing library. The model, by its own examples. SAMOS 2007, and the consortium's paper in the International Journal of Parallel Programming.

In numbers

The Cyclops chip had 32 cores and 128 hardware threads, and caches small enough that how the threads were laid out over them decided everything.

Past the line, because a core there ran four threads at once and the multi-zone programs kept every one of them fed. The fix for the cache conflict alone, without touching the programs, was worth 10% to 70% done in the runtime, and 40% to 100% as the change proposed to the hardware. The programs that did not balance their work across threads stopped near 30 whatever was done for them, which is its own lesson.

On the cluster with no shared memory, the same annotated program came close to its hand-written MPI version, and was far easier to write and keep. And the stream compiler took an FM radio written as plain serial C and ran it 3.5 times faster as a pipeline, with nobody drawing the pipeline by hand; the limit was one filter heavier than all the others.

What connects them

Each piece took away something OpenMP assumed: that caches were large, that memory was shared, that the cores were all alike, that the program was a loop rather than a stream. What survived every time was the way of working: keep the serial program, keep it readable, and say in the margin what may run together. The thesis calls it incremental parallelisation, and its conclusions call it the corner stone of everything else in it.

Next: what all this was for.