Watch, Follow, &
Connect with Us

For forums, blogs and more please visit our
Developer Tools Community.


ID: 26320, Parallel Sort using C++ and the WinAPI

by Colin Maharaj Email: Anonymous


This shows a divide-and-conquer technique for doing simultaneous quick sort in separate threads with 2 partitioned segments of data. A Merge is required after the sort.
Download Details
FTP  download also available
CDN Login Required to Download. (You will be redirected to the login page if you click on the Download Link)
To download this, you must have registered:
A free membership

For C++Builder, Version 6.0  to 7.0 214 downloads
Copyright: No significant restrictions


Size: 396,876 bytes
Updated on Sun, 30 Nov 2008 17:57:58 GMT
Originally uploaded on Sun, 30 Nov 2008 12:29:01 GMT
SHA1 Hash: 75683E32F0F1D9CBF718B417B7CAF2996D5A09C1
MD5 Hash: 8F21A061BE6F1524921E40974BCE0A9C

    Explore the files in this upload

Description
This is a divide-and-conquer sorting technique that uses threading to ....

1. Partition contigious data in two parts

2. Sort each part in Parallel

3. Merge the two parts

The average speed up is 2x on a dual core.


Other notes...

1. Assumes that your processor is dual or multicore.

2. The code should work in a single core but maybe with lower performance (untested).

3. No attempt was made to choose a core/thread affinity, the O/S seems to choose core 0 and core 1 magically to get the parallel deed done as expected.

4. We use CreateEvent/SetEvent and WaitForMultipleObjects for synchronization.

5. I wrote my own quick sort code and did not use the rtl qsort - just in case it was not thread safe. And I advise you do the same as well in your code (just in case).

6. I hacked up the merge code, had one error since last upload (did not test it).

7. The button that says timing screen shows the timing for the threads. Frankly that timing screen is more complex than the parallel sort.

8. This approach to merging takes up more memory than just sorting all your data in one go. I think there are merging techniques that usse less RAM but I did not fully research this.

9. The approach of the code is ment for a dual core, a quad core will still see a 2x improvement in speed (untested) but no more. The code should be easy enough to follow to have a multicore (>2) solution.

10. More memory is required. If it were a straight sort of all the data then we do not need to merge. However this merge algorithm requires we have another copy of RAM required for the merge destination, so while there is a speed up, more RAM is required.

Disclaimer:
The code is an attempt to use synchronization to do SMP type work on a multi core processor. It is quite possible that they may be bugs and other items that may need attention to get this code commercial quality. There is no support for this code and no guarantee it will work perfectly in all O/S Processor environments.





   Latest Comments  View All Add New

Move mouse over comment to see the full text

Could not retrieve comments. Please try again later.

Server Response from: ETNACDC04