4 ms·
As with lots of GPU-accelerated benchmarks unfortunately, they ignore the time to transfer the 1B keys from main memory to the GPU and back.
by whakojacko 16y ago
As with lots of GPU-accelerated benchmarks unfortunately, they ignore the time to transfer the 1B keys from main memory to the GPU and back.
- deleted 16y ago[deleted]
- jacquesm 16y agoThat's not entirely fair. If you benchmark a sorting algorithm you normally don't measure the time it takes to bring the records in from the disk either. Of course there is overhead, that's obvious, there would be overhead in any co-processor driven situation, but that overhead depends to a large extent on the host machine and the bus used to connect, so it would be reducing the value of the benchmark to include those figures in the timing. Also, there are plenty of applications where the input to the radix sort would come from other kernels and/or where the output would go to other kernels. In those cases there is no overhead.
- pbhjpbhj 16y agoCan you, jacquesm, or some other knowledgeable sort give an example of a situation which could call for this level of sorting? Sorting a billion of anything in 1s seems likely to kick against other problems. Just curious (I'm not asking why you'd want to, but you can tell me that too if you like).
- jacquesm 16y agoParticle simulations would be one example.
- _delirium 16y agoThere's a handful of ML algorithms where sorting is a bottleneck, or where the algorithm could have some complex data-structures ripped out if sorting were an order of magnitude faster. They're often hard to implement entirely on the GPU, though, so you'd have to be careful with the transfer to/from the GPU if you were using it solely for the sorting.
- wingo 16y agoThe problem is not only time from disk, it's time from memory.
- barrettcolin 16y agoOutside of a benchmark- that's latency you can hide though, right? Without reference to the specifics of this situation, which I don't claim to know much about, the co-processor can be sorting one dataset in it's local memory while the CPU is transferring data into another local buffer (or even, the co-processor can initiate the transfer itself using DMA).
- whakojacko 16y agoOnly to a limited extent. Assuming this is a regular-ish implementation of radix sort, you could start doing the first bucketing while data is being copied in. Likewise, you can copy out the sections which already have been fully sorted. But I would be surprised if you saw more than 10-15% percent speedup over naive copy execute copy.
- barrettcolin 16y agoYour observation is likely correct, but I was talking about sorting two or more independent sets, not partitioning the sort of one set; assuming that a "proper" (non benchmark) application will have several workloads waiting to be processed at a given time, so the GPU can be working on one while the data for the next is being transferred (so hiding the latency for the transfer for all but the first set). [edit] I don't know how practical that is on real world hardware; a billion keys is obviously a lot of data to transfer.
- tomjen3 16y agoThat assumes that the data the should be sorted wasn't created on the GPU right?
- _delirium 16y agoIt does seem like a nice tool for that case. I think a lot of people, though, especially reading the discussion at places like reddit, are expecting that this means you can now just replace your sort() call with a drop-in replacement gpu_sort(), getting a 4x speedup in the process, which is not likely to be true.
- herf 16y agoA lot of applications generate their own data. The pure "on disk" piece might be a fraction of the total. e.g., consider z-sorting vertices for a million-polygon model as it rotates (that's useful for some kinds of transparency.) Bandwidth to main memory is a small piece of the total.