Slashdot Mirror
Data Sorting World Record — 1 Terabyte, 1 Minute
An anonymous reader writes "Computer scientists from the University of California, San Diego have broken the 'terabyte barrier' — and a world record — when they sorted more than a trillion bytes of data in 60 seconds. During this 2010 'Sort Benchmark' competition, a sort of 'World Cup of data sorting,' the UCSD team also tied a world record for fastest data sorting rate, sifting through one trillion data records in 172 minutes — and did so using just a quarter of the computing resources of the other record holder."
As long as you use Intelligent Design Sort.
I had a 6502 system with BASIC in ROM and a machine code monitor. The idea is to copy a page (256 bytes) from the BASIC ROM to the video card address space. This puts random characters into one quarter of the screen. Then bubble sort the 256 bytes. It took about one second.
For extra difficulty do it again with the full 1K of video. Thats harder with the 6502 because you have to use vectors in RAM for the addresses. So reads and writes are a two step operation, as is incrementing the address. You have to test for carry. But the result was spectacular.
http://michaelsmith.id.au
You almost think at this point that with super fast systems attention to algorithmic complexity hardly matters, it's good to see research still advancing and that there are areas where carefully designed algorithms make a huge difference. I look forward to seeing how they fare against the Daytona set.
"There is more worth loving than we have strength to love." - Brian Jay Stanley
How many parallel predicting octopuses were required to predict their victory?
134340: I am not a number. I am a free planet!
Ah, my mistake - the "trillion data records" refers to a different benchmark. In the 1TB benchmark, records are 100 bytes long.
You've got to be kidding me. Each node was only 2 quad core processors, with 16 500GB drives (big potential disk IO per node) but this system doesn't even begin to scratch the very bottom of the top 500 list.
I just can't image that if even the bottom rung of the top 500 was even slightly interested in this record, that they wouldn't blow this team out of the water.
The cesspool just got a check and balance.
LARPers > Fan-fiction writers > Professional Data Sorting Competitors > Furries
Why is sorting 1TB so hard?
I can just instruct my tape library to put the tapes in the library in alphabetical order in the slots... Y'know AA0000 AA0001 AA0002... moves a hell of a lot more than 1TB.
No, a sort of 'world cup of data sorting' ends in 'cup data of sorting world'.
When I read the summary I thought what's the big deal if the 1 TB of data only contained two records 0.5 TB each. Then I saw that kdawson wrote the summary. So I browsed over here and saw that the impressive thing is that they sorted 1,000,000,000,000 records of 100 bytes each with 10 byte keys.
I think this is cool, but.... how fast is it in a more practical situation?
source
Impressive and all, but I take umbrage at calling it a "1 TB barrier". Is it disproportionately more difficult than sorting 0.99 TB?
Breaking "the sound barrier" was hard because of the inherent difficulty of going faster that sound in an atmosphere (sonic booms and whatnot). It was harder than simply travelling that fast would have been.
If this is just further evolution of sorting speed, it makes it a milestone, not a barrier.
Let's consider 100TB in 172 minute thing they also did. 52 nodes, 16 spindles per node is 832 spindles total and 120GB of data per spindle. 120GB of data can be read in 20 minutes and transfered in another 15 to the target spindles (assuming uniform distribution of keys). You can then break it down into 2GB chunks locally (again by key) as you reduce. Then you spend another hour and a half reading individual chunks, sorting them in memory, concatenating and writing.
Of course this only works well if the keys are uniformly distributed (which they often are) and if data is already on the spindles (which it often isn't).
Please don't tell my girlfriend, she'll realize I've been faking being a semi-normal cool guy for years, and leave me.
Nah, she'll realize that you're more turned on by a new processor than by a pair of tits, and stay with you forever knowing you'll never cheat on her (except when you go to that site to download algorithms). You might have to give in and move out of the basement though. But not to worry - a good set of blackout curtains and it's almost the same. Plus as you get older the lack of dampness is easier on your rheumatism...
Seven puppies were harmed during the making of this post.
A paper describing the test is here. TritonSort is the abstract method; GraySort and MinuteSort are concrete/benchmarked variations of TritonSort.
As TFA states, this is more about balancing system resources than anything else. The actual sort method used was "a variant of radix sort" (page two of the linked PDF). Everything else was an exercise in how to break up the data into manageable chunks (850MB), distribute the chunks to workers, then merge the results. That was the real breakthrough, I think. But I wonder how much is truly a breakthrough and how much was just taking advantage of modern hardware, since one of the major changes in MinuteSort is simply avoiding a couple of disk writes by keeping everything in RAM (a feat possible because that much RAM is readily available to a single worker).
Regardless, this kind of work is very cool. If web framework developers (for example) paid greater attention to balancing data flow and work performed, we could probably get away with half the hardware footprint in our data centers. As it stands now, too many COTS -- and hence, often-used -- frameworks are out of balance. They read too much data for the task, don't allow processing until it's all read in, etc.. This causes implementors to add hardware to scale up.