~ $ cd research && cat README.md

Research

In 2003 every new processor had run old programs faster for twenty-five years, and it seemed it would last for ever. My thesis began from the hunch that it would not: that the desktop would go multi-core, and that the problem would stop being the hardware and become the programmer, who now had to write many coordinated lists of instructions instead of one, and mostly did not know how.

So the question of the whole PhD is one of usability. Supercomputers had been parallel for decades, and most of their users were not computer scientists. What they used, OpenMP, lets you take a serial program and annotate it, a line at a time, until it runs in parallel. Could that way of working be carried to the machines everyone was about to own, which did not share memory, and whose cores were not all the same?

Algorithms Acceleration of Pattern-Matching in Multi-Core Architectures, Universitat Rovira i Virgili, defended in Tarragona on 8 July 2011, cum laude, directed by Francesc Serratosa. Eight years, two universities, and an unusual spread for one thesis: a runtime, a simulator, a compiler, and an algorithm.

The tools: UPC and the Barcelona Supercomputing Center, 2003–2008

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. It is team work and I am its third author. What is mine is the base and its modularity, and above all the protocol by which modules talk to each other purely as memory accesses, so that any of them can be connected to any other. My thesis calls that protocol its best contribution.

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. SAMOS 2007, and the consortium's paper in the International Journal of Parallel Programming.

In between: a database engine, 2008–2009

Between the two halves of the thesis I spent a year at DAMA-UPC, the group behind the graph database DEX, later sold as Sparksee. The engine is theirs. My work was to make its core concurrent, which until then ran under one global lock.

Three things from that year have stayed with me. Measure the locks themselves — I put counters inside them, and they said the contention was nearly all in one place, the buffer pool, which is where the effort then went. Write the protocol down before the code: the pool's pin and unpin became lock-free, a counter and three flags packed into one word changed by compare-and-swap, and I verified it by hand, step by step, with invariants and pre- and postconditions, because no test finds the interleaving that happens once a week. And give the people using the engine tasks instead of threads: a small framework for its Java interface, with serial, parallel and for-each tasks, cancellation, and exceptions that arrive where they should.

In the same group I built a tool that loads the diagnostic dumps of a hung IBM DB2 into a graph and looks there for what is waiting on what, in collaboration with IBM. That work is under its own terms, and a description is all there is of it here.

The application: Universitat Rovira i Virgili, 2009–2011

Computer vision likes to describe things as graphs: a house is a roof, a door, two windows, and how they touch. Comparing two graphs exactly is exponential in their size, and even the good approximations were too slow to use outside a laboratory.

I took two of those algorithms, graduated assignment for a pair of graphs and for the common labelling of many, and rewrote them for what a desktop had become: a multi-core processor beside a graphics card. The method is what the first half had taught. Transform the equations, not the code — splitting, tiling and reordering loops in a notation close to the mathematics — so that the program falls into the same two levels of parallelism, and the result does not change by a single bit. Up to about thirty-five times faster than the serial version, on hardware chosen for its low power consumption: close to real time, which is what a robot or a fingerprint reader needs.

Both are first-author papers in Springer's Lecture Notes in Computer Science: IbPRIA 2011 and GbR 2011.

What it left

The thesis ends on a sentence I still use: desktop computers are indeed desktop supercomputers, not only by their performance, but also by their complexity. Its tools were released under the GPL, and its last slide argued that research software should be published with its sources, the way a paper is published with its proofs.

And it left a habit. Everything I have built since for other engineers — a platform, a test harness, a course — starts from the question this started from: not what the machine can do, but what the person in front of it can be expected to get right. A small case of it: the recipe for concurrency I wrote a consensus algorithm by, so that students could.

The thesis lists sixteen publications. The record: the thesis, at Dialnet, and what DBLP indexes.