Databases
StackOverflow2013
Postsdbo
POGPU-accelerated sort (~1GB) and merge sort (~100GB)
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POGPU-accelerated sort (~1GB) and merge sort (~100GB)
    primarykey
    data
    text
    <p>I'm asking for a c++ library to do GPU-accelerated sort (around 1GB of data) and merge sort (say, around 100GB of data &mdash; but the size do not matter, because merge is a stream algorithm). License have to be LGPL, BSD or like this. I greatly prefer OpenCL because of portability (but I also interested in links to CUDA libraries). I appreciate links to papers and blog posts on this subject.</p> <h3> Some background (please correct me if I wrong): </h3> <p>2-way merge sort of 1GB (that is, 128 000 000 of 8-bytes entities) will consume approximately log<sub>2</sub>(128 000 000)&middot;1G = 27GB of memory bandwidth, that is around 1 second on modern CPU with <em>sequential</em> memory bandwidth of ~30GB/s. (Any non-merge sort seems to take much longer time, because non-sequential memory access is slower in 10-100 times).</p> <p>Although I am not familiar with modern GPU, I suspect that merge sort of 1GB will take 0.2 second or even less, because typical GPU memory bandwidth is around 150GB/s, like AMD/ATI 58xx (see, for example <a href="http://en.wikipedia.org/wiki/Comparison_of_AMD_graphics_processing_units#Evergreen_.28HD_5xxx.29_series" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Comparison_of_AMD_graphics_processing_units#Evergreen_.28HD_5xxx.29_series</a>) </p> <p>That is at least 5x speedup. (The time to transfer 1GB over 16x PCI-E 2.0 is around 0.125s, but it seems possible to make PCI transfers in parallel with sorting; however, this may require 2GB or 3GB of video-card memory instead of 1GB).</p> <p>I suspect even more speed-up due to more-than-2-way merge sort or some sort, suitable for GPU.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USuser1123502
    1. USuser1123502
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POGPU-accelerated sort (~1GB) and merge sort (~100GB)
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POGPU-accelerated sort (~1GB) and merge sort (~100GB)
      1. USOmnipotentEntity
      1. VTFavorite
    3. VO
      singulars
      1. POGPU-accelerated sort (~1GB) and merge sort (~100GB)
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI hope to be wrong, but IO in big data problem (the 100GB part) will kill any gains you'll get from using GPU in the small problem (the 1GB part), even if you use multiple SSD, unless the comparison procedure is so complex it needs GPU. Second problem is sending data to GPU and receiving it back—it's much slower than pure GPU memory bandwdith. But I'm curious what answers will you get.
      singulars
      1. POGPU-accelerated sort (~1GB) and merge sort (~100GB)
      1. USliori
    2. CO@liori At least, 100 of 1GB-gpu-sorted-blocks may be merged by CPU, not GPU (it's around 7 passes, so it really seems that PCI transfer will be a bottleneck). However, there may exist a clever trick, that I am not aware of.
      singulars
      1. POGPU-accelerated sort (~1GB) and merge sort (~100GB)
      1. USuser1123502
    3. COAlso, not an answer and might be barely related, as they're mostly using clusters and not GPUs, but you might find some ideas on http://sortbenchmark.org/
      singulars
      1. POGPU-accelerated sort (~1GB) and merge sort (~100GB)
      1. USliori
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload