5 ms·
Sorting data in parallel CPU vs GPU
- defrost 14y agoI do enjoy these 21st Century partial rediscoveries of the good old trusty Fibonacci Polyphase merge sort. It's like the late 70's / early 80's all over again, only with commodity rather than custom hardware. There's some online discussion here: http://flylib.com/books/en/3.55.1.115/1/ http://flylib.com/books/en/3.55.1.115/1/ The book references are: External Sorting, Section 5.4 in The Art of Computer Programming, Vol. 3: Sorting and Searching by Donald Knuth, Addison-Wesley, 1973. and External Sorting, Chapter 13 in Algorithms by Robert Sedgewick, Addison-Wesley, 1983. Sorting and merging blocks is the beginning of the journey, learning the various tricks to doing it optimally is where it gets interesting, although perhaps no longer relevant; 30 years ago the OPs approach might take nearly a day with polyphase tweaks reducing the grind down to under half an hour, these days it's all over in a fraction of a second and more or less bound by I/O throughput speed - does optimising sort times still matter?
- tolos 14y ago> does optimising sort times still matter? Yes, not all new computers are fast (calculators, cars, µC, etc).
- xedarius 14y agoInteresting, yet I'd have liked a little more of a break down of the results. For example the GPU will probably need to transfer the sorted data to and from the card. This will have a dramatic effect on performance.
- exDM69 14y ago> This will have a dramatic effect on performance. Agreed, but the effect is bigger on latency than throughput. If the problem set is bigger than available GPU memory, the latency is at least partially hidden by streaming as the GPU can be kept busy while DMA is still transferring. The same thing applies if you will be doing more computations on the same data in the GPU so it won't have to be transferred back and forth.
- moreaccounts 14y agoTake a look at CUDA's pinned memory.
- exDM69 14y agoPinned memory doesn't help a whole lot. It's a page-aligned memory buffer for DMA transfer, it can only avoid doing one memcpy on the CPU. It does not improve the latency over the PCI-e bus, which is a lot bigger factor than the memcpy that can be avoided with pinned memory.
- moreaccounts 14y agoI've used it to hide the latency of the copy back (GPU -> CPU) inside the actual algorithm so I didn't need to suffer the large stall (4-5ms). It helped tremendously because most of the data was fully computed before the algorithm was actually done running.
- coolj 14y agoPlease post the numbers for that box with vanilla (non-parallel) std::sort, on the whole array, as well! I'm curious!
- jbert 14y agoDoes anyone have an idea what might cause the small bump/spike in performance is on the CPU-8 graph at approx 1e6 elements? It looks to be worth around 20-25% of the performance. If it's related to a sizing parameter of the parallelisation, that suggests that choosing that parameter well could be important.
- supergirl 14y agoIt looks like a sudden degradation of performance. Might be the point when the caches become full. That CPU has 6MB L3 + 256KB L2 x 8 which means ~8MB. The bump is at 1043786 elements which require 8154KB of memory.
- pavanky 14y agoUsing 445M to compare against an i7 is ridiculous (Even if the i7 is 3 generations old).
- aseidl 14y agoI'm working on running the tests on 2x Xeon E5-2630 and a Tesla K20c. Will post the results here in a couple hours.
- octopus 14y agoYou think the average programmer (user) has a Tesla computing device on his computer ?
- benmanns 14y agoYou can buy an hour with two Tesla GPUs for $2.10 on EC2.
- pavanky 14y agoThe 445M is a mobile GPU and quite low end at that. In fact the Teslas are consistently slower than the GTX cards for single precision (until their k20 line that is). So something like a 480 would be ok. 580 would be ideal.
- allanmac 14y agoA 445M is an sm_21 Fermi device with 3 SMs (144 cores). This is a low-end GPU.
- aseidl 14y agoI've rerun the tests on some slightly more recent hardware: a Tesla K20c and Xeon E5-2630. See the 'new benchmarks' section on: https://github.com/aseidl/Sort_data_parallel https://github.com/aseidl/Sort_data_parallel
- onedognight 14y agoIt looks like the OP should be using std::inplace_merge instead of std::merge/std::copy.
- jey 14y agoTangential factoid: GNU libstdc++ has a parallel mode that includes parallel std::sort, http://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html http://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode...