Fast Database Emerges from MIT Class, GPUs and Student’s Invention

Some background mixed with some opinion:

This is an area still without a major commercial competitor and there aren't yet any such public product efforts as far as I know (IBM has a couple of researchers publishing on the topic). The difficulty is that really exploiting the GPU requires rethinking architecture from the ground up, including how your query plan handles parallelism, how your data is stored, and most significantly, how to efficiently move data to the GPU for processing. Most databases aren't partitioned nearly well enough to shoehorn GPU processing in on the backend, and it seems like the vast majority of recent database development has been around highly distributed systems and commodity hardware, eg Hadoop. A German company called ParStream has a DB that uses GPUs for certain indexing operations, though last time I spoke to them it sounded like there is much much more that can be done with GPU hardware.

In general, speedup is highly variable, and depends on the data set, indexing characteristics, data type (fixed vs variable length), individual query, etc, but its fairly common to see 10x speedups over optimized multicore query execution. Though the extreme parallelism of the GPU is responsible for some of this, in my opinion the big win there is just absolute memory throughput. Newer Tesla GPUs have a memory throughput of > 100 GB/s without breaking a sweat, while most CPUs are around 30 GB/s. If you can push data through your hardware that quickly, its easy to see how the GPU can have such an advantage.

The difficulty, however, is actually moving the data into GPU memory (1-8 GB generally) to exploit this throughput, which is a major bottleneck (some of my research was around doing this better). I understand that GPU direct disk access is just becoming a reality, which could make this easier. The holy grail, however, is a full-powered integrated server CPU/GPU. If both of these components had equivalent main-memory access and this architecture becomes cheap and commoditized, then GPU databases will immediately become extremely relevant.

I expect that there will be a serious commercial competitor in this area within 3 years, either in the relational data warehousing space (think Vertica) or closely integrated into MapReduce type execution. My guess as to the reason it doesn't exist is that 1) production DB development is really hard and 2) GPU processing is only a really big win for certain workloads, namely heavy analytical/research workloads over fixed-size data. As I said, if GPUs become commoditized in server hardware or fully integrated with CPUs, however, I expect this domain will quickly become extremely important. This is a very cool area and its common to see 10x speedups even with optimized CPU implementations.

Always happy to chat about this stuff, feel free to shoot me a message.

https://github.com/antonmks/Alenka

Shoehorning things to run on the GPU seems to me a dirty hack, indicating that there is an underlying problem that could and should be addressed in a better way.

For every point to test, you need, on average, to test half the polygons. Testing a point against a polygon means testing the point against, on average, about half the polygon's edges. Each of those tests takes a multiplication, an addition, and a comparison.

That's 4E7 points times 2500 polygons times, at least, 1.5 edges. Total: 1.5E11 multiplications, additions, and comparisons.

With 100-sided polygons, it would be 1E13 or so multiplications/addition/comparison steps.

Memory pressure is dominated by polygon storage. 5000 poly's, 100 points each, is 500,000 edges at two doubles each, or 4MB. That fits comfortably in cache.

So, 1E9 multiplications/addition/comparison steps a second should be possible. That's 10,000 seconds or 3 hours.

=> Should be doable on one CPU in hours (famous last words)