MPI sort implementation

1
votes

I need to sort a really huge file several, hundred of Gb. Luckily I have access to a Linux MPI cluster. Does somebody know a good but most importantly working sort program which can run in distributed environment using MPI. Actually I want to count unique lines in that file so if somebody knows a program that does exactly that even better. Otherwise I can figure out how to do it myself later.

1
sortingmpi
How many lines are there? Could you significantly reduce the size of the file by replacing lines with short hashes? - Dmitri Chubarov
More precisely the file size is 21Gb. My worry is that even though if I eventually decide to code something like merge sort myself I will also have to worry about RAM availability which will make whole program a bit more complicated. - Sergej Andrejev
Possibly less efficient but a simple approach: for P nodes choose a function f that assign a number from 0 to P-1 to each line so that the lines are more or less evenly distributed. Let each node K count occurences of lines where f(line) = K: unique lines counted without sorting. Complexity: N * N / (P * P). - Dmitri Chubarov
But isn't this just making a problem a bit smaller but not solves it. If every node K count inaccuracies of lines in partition assigned to it there will still be a need to merge these counts (which also involves counting). - Sergej Andrejev
Actually I think I'm on the right track now. I found this site sortbenchmark.org and been able to download a winner from 2004 (nsort). Compared to default linux sort it's blazingly fast and finishes in about 10 minutes on my file. I'm trying to find now whether any of other winners provide non-commercial versions of their software because I think the time could be pushed even further if I can find application which can use more than one cluster machine - Sergej Andrejev

1 Answers

1
votes

Because there was no no answer provided I though I would just share my results.

I downloaded nsort program from ordinal.com (2004 winner in sortbenchmark.org annual sorting algorithm competition). It sorts amazingly fast though not in a cluster manner. I don't remember what was it anymore but I got huge time improvement using nsort. I'm talking about tens of times more faster (maybe around ~50) than default linux sort.

Two more things to notice.

  • It is limited to text files sorting in non-commercial distribution.
  • It has exactly the same interface as linux sort utility.