MULTI-THREADED SORT
SUMMARY
The multi-threaded sort uses multiple CPU cores as multiple threads to sort an array faster than one CPU core. The following three steps are followed by the multi-threading sort algorithm:
- Divide array into equal-sized groups equal to the number of threads
- Use either quick sort or merge sort on each group (one thread per group)
- Merge sort is used if a stable sort is required. A stable sort preserves the order of ties.
- Quick sort is faster, but is not a stable sort.
- Merge the sorted groups together using a bottom-up merge sort approach.
- The final merge of the sorted groups can be done two ways
- Simple method uses single-threaded merge
- Advanced method merges sorted groups as soon as a pair is finished and uses a multi-threaded merge
- The benefit of the advanced method is small
- The final merge of the sorted groups can be done two ways
Source code:
Multi-threaded Quicksort Fortran source code (faster, but order of ties is not preserved)
Simple: real number array derived data type array
Improved: real number array derived data type array
Multi-threaded Merge Sort Fortran source code (slower, order of ties is preserved)
Simple: real number array derived data type array
Improved: real number array derived data type array
Binaries complied for Linux using the Intel Fortran Complier are also available for download at Bitbucket.
Compiling Fortran Test Code
Instructions are for Linux. Windows is similar, but I haven't tested it.
Intel Fortran
Eclipse: Right-click on the project and to go Properties. Expand Fortran Build. Go to Settings. Under the Tool Settings tab, under the Intel Fortran Compiler menu select Language. In the pull-down menu next to Process OpenMP Directives select Generate Parallel Code (-openmp). Under the Intel Fortran Linker menu select Command Line. In the Additional Options field type -openmp.
Command Line: To compile the MTSort_QRB.f90 file type the following in a terminal window:
ifort MTSort_QRB.f90 -oSort -O2 -openmp
The result is a executable named Sort that is run by typing Sort in windows or ./Sort in Linux.
Eclipse: Right-click on the project and to go Properties. Expand Fortran Build. Go to Settings. Under the Tool Settings tab, under the GNU Fortran Compiler menu select Miscellaneous. In the Other flags field add -fopenmp. Under the GNU Fortran Linker menu select Miscellaneous.In the Linker flags field type -fopenmp.
Command Line: To compile the MTSort_QRB.f90 file type the following in a terminal window:
gfortran MTSort_QRB.f90 -O3 -oSort2 -fopenmp
The result is an executable named Sort2 that is run by typing Sort in windows or ./Sort in Linux.
Note: The multi-threaded sort test programs from produce different results in GNU Fortran and Intel Fortran due to different random number generators. When given identical data sets both GNU Fortran and Intel Fortran produce identical results.