3 ms·

Database workloads tend to be very branch heavy, e.g. string comparisons. If you've ever programmed a GPU you know that taking a data-dependent branch serialize

by hendzen 10y ago

Database workloads tend to be very branch heavy, e.g. string comparisons. If you've ever programmed a GPU you know that taking a data-dependent branch serializes the execution of the GPU stream processing units. So already the 70-100x benefit GPUs give on vectorized floating point workloads is greatly reduced. Add in the memory bandwidth penalty and it's a complete waste for IO intensive database workloads. Save the GPUs for training neural nets and physics simulations. When the fundamental hardware capabilities of GPUs make them worth investing in for database workloads, I'll change my opinion. Until then, any budget for expensive DB hardware is much better spent on NVMe storage.

zlynx 10y ago
You can write code to compare strings without branches. Imagine comparing one string to every string in a database column. Pad to a fixed size first (if you find an ambiguous match later you can do a full string compare then). Subtract the strings, aka compare, and store the result. At the end of all the commparisons you have a memory structure of negative, zero, or positive values. Then you can do something with the matching values. There have been some very sweet algorithms for doing B+ tree searches for Itanium and for AVX and those work just as well, if not better on GPU. With some thinking, branch operations can be converted into math and applied to masses of data without checking for branch conditions. This wastes some work but is still faster than branching.
- hendzen 10y ago
  That sounds like an interesting technique - but it unfortunately does not apply on a majority of real-world data. In particular I mean sorting non-English text which any serious database needs to be able to do. Subtracting characters doesn't work when you're dealing language specific Unicode collation [0]. [0] - http://www.unicode.org/reports/tr10/ http://www.unicode.org/reports/tr10/
  - zlynx 10y ago
    Yeah, well, you just can't do it that way and be fast at the same time. I mean seriously fast. What you can do is decide how your comparison should be collated and preprocess your strings into a sort key form that is strictly big-endian binary (first byte has highest weight). Or little-endian I suppose, whichever works best for your hardware. Your sort key doesn't have to be the actual string.
felipe_aramburu 10y ago
Yes data dependent branch serialzizes the execution of the gpu stream processing units (this is not true for amd actually). Yes it sucks operating on string sometimes on gpu and we don't always do it because of this. But we are ignoring certain aspects. Long strings are dictionary encoded in our database usually (no one picks this an optimizer finds the best cascading compression scheme and imposes this). Dictionary encodings are sorted so that each dicitionary value's key is in sorted order. So guess what you can already do comparison and equality checks on much smaller datasizes. A long string can be encoded in 8, 4 ,2 sometimes even 1 byte. Many times we have to do string comparisons on strings that we hhave not encoded ie select * from table where column1 = "some awesome text here" In this case we actually do a comparison between hashes of the data. Hashing is cheap, fast, and makes comparisons on the GPU's be a breeze. So long story short, we have no data dependent branching. We do this by never using certain statements inside of kernel code. the use of "if" is expressly forbidden at blazing for any gpu code and it's use is punished viciously (said individual usually has to be the one that captures meaningful input from one the 80 log files of our 80 gpu cluster ). Editing to mention the way you can encode a long string down to a 1 byte is by doing a dictionary compression and then bit packing the keys. On gpu the way you do this is getting the max key (min key is always 0) and then you can store this data in 1 byte (if max(key) < 255).
- sitkack 10y ago
  The whole point of making things fast is to remove all the if statements. People complain that their current if-heavy algorithm can't run on GPUs therefor GPUs suck. Of course then the algorithms need to be reworked to have less branches.

by hendzen 10y ago

zlynx 10y ago

You can write code to compare strings without branches. Imagine comparing one string to every string in a database column. Pad to a fixed size first (if you find an ambiguous match later you can do a full string compare then). Subtract the strings, aka compare, and store the result. At the end of all the commparisons you have a memory structure of negative, zero, or positive values. Then you can do something with the matching values. There have been some very sweet algorithms for doing B+ tree searches for Itanium and for AVX and those work just as well, if not better on GPU. With some thinking, branch operations can be converted into math and applied to masses of data without checking for branch conditions. This wastes some work but is still faster than branching.

hendzen 10y ago
That sounds like an interesting technique - but it unfortunately does not apply on a majority of real-world data. In particular I mean sorting non-English text which any serious database needs to be able to do. Subtracting characters doesn't work when you're dealing language specific Unicode collation [0]. [0] - http://www.unicode.org/reports/tr10/ http://www.unicode.org/reports/tr10/
- zlynx 10y ago
  Yeah, well, you just can't do it that way and be fast at the same time. I mean seriously fast. What you can do is decide how your comparison should be collated and preprocess your strings into a sort key form that is strictly big-endian binary (first byte has highest weight). Or little-endian I suppose, whichever works best for your hardware. Your sort key doesn't have to be the actual string.

felipe_aramburu 10y ago

Yes data dependent branch serialzizes the execution of the gpu stream processing units (this is not true for amd actually). Yes it sucks operating on string sometimes on gpu and we don't always do it because of this. But we are ignoring certain aspects. Long strings are dictionary encoded in our database usually (no one picks this an optimizer finds the best cascading compression scheme and imposes this). Dictionary encodings are sorted so that each dicitionary value's key is in sorted order. So guess what you can already do comparison and equality checks on much smaller datasizes. A long string can be encoded in 8, 4 ,2 sometimes even 1 byte. Many times we have to do string comparisons on strings that we hhave not encoded ie select * from table where column1 = "some awesome text here" In this case we actually do a comparison between hashes of the data. Hashing is cheap, fast, and makes comparisons on the GPU's be a breeze. So long story short, we have no data dependent branching. We do this by never using certain statements inside of kernel code. the use of "if" is expressly forbidden at blazing for any gpu code and it's use is punished viciously (said individual usually has to be the one that captures meaningful input from one the 80 log files of our 80 gpu cluster ). Editing to mention the way you can encode a long string down to a 1 byte is by doing a dictionary compression and then bit packing the keys. On gpu the way you do this is getting the max key (min key is always 0) and then you can store this data in 1 byte (if max(key) < 255).

sitkack 10y ago
The whole point of making things fast is to remove all the if statements. People complain that their current if-heavy algorithm can't run on GPUs therefor GPUs suck. Of course then the algorithms need to be reworked to have less branches.