~ $ cd research/graph-matching && cat README.md
Graph matching on a desktop
The second half of the thesis, at the Universitat Rovira i Virgili between 2009 and 2011: the tools of the first half, put to work on a problem that needed them.
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, and it has a page of its own. 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.
The machine was chosen for what it did not have: an Intel Atom with two cores, the kind put in netbooks, and the small graphics chip sold beside it. Eighteen watts between them.
| each graph has | one thread | OpenMP, every core | CUDA, the graphics card |
|---|---|---|---|
| Matching every pair of 150 graphsIntel Atom 330, 2 cores, 8 W · NVIDIA 9400M, 16 cores, 10 W | |||
| 8 vertices | 42 s | 14 s ×3.0 | 2.6 s ×16 |
| 16 vertices | 12 min | 4 min 8 s ×3.0 | 33 s ×22 |
| 24 vertices | 1 h 13 min | 20 min ×3.6 | 1 min 49 s ×40 |
| Matching every pair of 150 graphsIntel i7 950, 4 cores, 130 W · NVIDIA GT 430, 96 cores, 49 W | |||
| 8 vertices | 7.5 s | 1.5 s ×5.0 | 0.7 s ×11 |
| 16 vertices | 2 min 16 s | 25 s ×5.4 | 5.2 s ×26 |
| 24 vertices | 8 min 36 s | 2 min 6 s ×4.1 | 19 s ×27 |
| Finding one labelling common to 50 graphsIntel Atom 330, 2 cores, 8 W · NVIDIA 9400M, 16 cores, 10 W | |||
| 8 vertices | 14 min | 3 min 35 s ×3.9 | 33 s ×25 |
| 16 vertices | 4 h 44 min | 1 h 11 min ×4.0 | 9 min 10 s ×31 |
| 24 vertices | 19 h 54 min | 5 h 37 min ×3.5 | 39 min ×31 |
Matching every pair of 150 graphs of 24 vertices took one thread an hour and a quarter. OpenMP on the same two cores brought it to twenty minutes; the graphics chip, to under two. The common labelling of fifty such graphs went from twenty hours to thirty-nine minutes. And the larger the graphs, the larger the gain — sixteen, twenty-two, forty times — which is the right way round: it is the large ones that were out of reach.
The same programs on a fast desktop of the day, a four-core i7 with a ninety-six-core card, did that hour and a quarter in nineteen seconds: two hundred and thirty times faster than where it started, one thread of the Atom. The thesis rounds it to 250.
On the largest graphs tried, 512 vertices, the thesis reports the parallel version 366 times faster than the serial one, whose run at 1,024 vertices was not attempted: it was estimated at forty-two days.
That is close to real time, on hardware a robot or a fingerprint reader could carry, which is what the algorithms had been waiting for.
Both are first-author papers in Springer's Lecture Notes in Computer Science: IbPRIA 2011 and GbR 2011.