Hi chsalvia,
I haven't seen you on here for a while. Good to see you back. :)
As has been pointed out, the merge process would be difficult to parallelise as its main bottleneck is disk I/O. However, if there is something you can assume about the sort key there may be something you can do.
Perhaps you could bucket the chunks. If you are sorting ascii strings, you could split the data 26 ways on your first read+chunk+sort pass. You could then merge each of the resultant 26 sets of sorted chunks in a separate thread. This may drastically impact on your disk I/O though.
Generally, when you are using an external mergesort you are usually doing it because you have a LOT of data. Optimisation of cpu usage is unlikely to have much of an impact on throughput.
Paul
Main Topics
Browse All Topics





by: sdstuberPosted on 2008-04-03 at 07:39:27ID: 21273146
The merging must be singly threaded by the nature of the algorithm.
The chunk sorting can be parellized because they are independent operations.
You might be able to parallelize "sub-merges", but I'm somewhat sceptical of the benefits of doing such.
For example 8 chunks -8 threads.
4 threads merge 2 chunks each
2 threads merge 2 double-chunks each
1 thread merges 2 quad-chunks.