Slashdot Mirror

← Back to Stories (view on slashdot.org)

Sorting Algorithm Breaks Giga-Sort Barrier, With GPUs

Posted by timothy on from the quick-like-double-time dept.

An anonymous reader writes "Researchers at the University of Virginia have recently open sourced an algorithm capable of sorting at a rate of one billion (integer) keys per second using a GPU. Although GPUs are often assumed to be poorly suited for algorithms like sorting, their results are several times faster than the best known CPU-based sorting implementations."

9 of 187 comments (clear)

  1. Excel Charts by Anonymous Coward · · Score: 3, Insightful

    I find it very disappointing that a group of programmer/computer science types who even supply BibTeX to make it easier to reference their work, resort to screen-capturing an Excel chart to display their data.

    1. Re:Excel Charts by Anpheus · · Score: 3, Insightful

      Maybe excel was just the right tool for the job? It's quick and easy to use, and to reformat the graphs.

      I know the Linux tools tend to be a little longer between tweaking, rendering and displaying, so a fast WYSIWIG tool works just fine.

    2. Re:Excel Charts by pspahn · · Score: 4, Insightful

      Actually, I find even more disappointing that a decent way to display datasets on a web page isn't standard yet. Why can't a nice one be embeddable with column sorts and robust methods for retrieving data? There are solutions, sure, but I have yet to find one that isn't unnecessarily complex or just plain ugly and difficult to use. But I guess it's just a matter of time, right?

      --
      Someone flopped a steamer in the gene pool.
  2. Not a barrier by Captain+Segfault · · Score: 5, Insightful

    This isn't a "barrier" like the "sound barrier". There are no special difficulties that start around 1G/sec! It's just a threshold.

    Don't get me wrong -- I'm not saying this isn't impressive, but no "barrier" was broken here!

    1. Re:Not a barrier by XanC · · Score: 4, Insightful

      It's not a threshold! It's just a milestone.

  3. Um... by Anonymous Coward · · Score: 5, Insightful

    Algorithms aren't measured in "x per second"... only implementations are measured that way. The speed of an algorithm is described in big-O notation, such as O(n log n). The metric of "sorted keys per second" is largely useless, because it depends on the particular hardware setup.

  4. Ugh. by martin-boundary · · Score: 3, Insightful
    Stupid HTML ate my <...

    The problem with big-oh notation is that the constant isn't explicit, so for any given n (pick as large as desired), it is possible that O(nlogn) < O(n) for some choice of constants. That's why ops per second is still a useful metric when comparing implementations on standardized hardware.

    As always, in theory there's no difference between theory and practice, but in practice there is...

  5. Re:No by black3d · · Score: 3, Insightful

    Unfortunately I can't mod having already posted in this thread, but please allow me to /bow. This is the best explanation I've ever read anywhere for the differences. Even I knew the differences but couldn't have expressed it so finely. Bravo.

    --
    "The true measure of a person is how they act when they know they won't get caught." - DSRilk
  6. Re:Big deal. Radix sort works well IF ... by Trepidity · · Score: 4, Insightful

    Well, yeah, they're not claiming they invented radix sort. They're claiming that their GPU implementation of radix sort runs about 4x as fast as the CPU implementation you describe.

    --
    10 PRINT CHR$(205.5+RND(1)); : GOTO 10