The base implementation was taken from here.
We extend and improved the base implementation. One in C++. One in Python.
In both extensions, the proccesses read the random values from a binary file.
The C++ implementation can also deal with non even proportion of proccesses and count of values.
The result-table with the C++ implementation.
The result-table with the python implementation (processing).
-
Install MPICH2: http://mpitutorial.com/tutorials/installing-mpich2/
-
Generating binary file with random values:
Compile:
g++ RandomNumberGenerator.cpp -o RandomNumberGenerator -std=gnu++0x
Run:
./RandomNumberGenerator <count_values_to_generate> <optinal_flag "y" if_output_on_console_is_desired>
Example-Call:
./RandomNumberGenerator 100 y
The generated result file have this format and will saved in the same directory, where this program will executed:
<countNumbersToGenerate> numbers - <Current Date>.bin
Example-Output:
100 numbers - Wed Dez 13 21:42:25 2017.bin
-
Execute the Odd-Even Sort
Compile:
mpic++ OddEvenSort.cpp -o OddEvenSort
Run on single machine:
mpirun -np <count_proccesses> ./OddEvenSort "<numbers_file.bin>"
Example-Call:
mpirun -np 4 ./OddEvenSort "100 numbers - Wed Dez 13 21:42:25 2017.bin"
On a cluster you have to fill your hostfile (/etc/hosts) and pass it with the -f flag like:
mpirun -np 4 -f hosts ./OddEvenSort "100 numbers - Wed Dez 13 21:42:25 2017.bin"
Time in seconds.
Count Processes | 15 | 30 | 60 | 120 | 240 | 480 | ||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Count Values | Scaling | Scaling | Scaling | Scaling | Scaling | Scaling | ||||||
4.800 | 0,976 | 1,355 | 1,938 | 3,444 | 6,545 | 12,657 | ||||||
48.000 | 1,027 | 1,052 | 1,368 | 1,010 | 2,064 | 1,065 | 3,539 | 1,028 | 6,775 | 1,035 | 12,711 | 1,004 |
480.000 | 1,630 | 1,587 | 2,001 | 1,463 | 2,662 | 1,290 | 4,071 | 1,150 | 7,441 | 1,098 | 13,651 | 1,074 |
4.800.000 | 7,566 | 4,642 | 7,840 | 3,918 | 8,545 | 3,210 | 11,537 | 2,834 | 15,479 | 2,080 | 22,729 | 1,665 |
48.000.000 | 71,458 | 9,445 | 71,589 | 9,131 | 71,076 | 8,318 | 75,547 | 6,548 | 103,359 | 6,677 | 105,701 | 4,650 |
make sure Python3 is installed on your system
make sure numpy is installed on your system
for generating numbers:
python3 generator.py 128
for sorting :
mpiexec python3 sort.py
Time in seconds.
Count Processes: | 4 | 8 | 16 | 32 | 64 | 128 | 256 | np/qs | timsort | odd/even |
---|---|---|---|---|---|---|---|---|---|---|
Count Values | ||||||||||
128 | 1.963 | 1.853 | 2.042 | 2.322 | 3.110 | 4.663 | N/A | 0.810 | 0.749 | 0.793 |
4096 | 1.855 | 1.921 | 2.022 | 2.370 | 3.093 | 4.732 | 8.909 | 0.770 | 0.813 | 41.529 |
131072 | 2.066 | 2.025 | 2.344 | 2.698 | 3.633 | 4.840 | 8.478 | 0.769 | 1.55 | N/A |
4194304 | 5.353 | 5.722 | 6.225 | 6.654 | 7.312 | 9.851 | 13.817 | 1.680 | 36.631 | N/A |
16777216 | 18.66 | 18.513 | 19.546 | 22.012 | 22.13 | 24.340 | 29.714 | 4.933 | N/A | N/A |
33554432 | N/A | N/A | 52.181 | 41.715 | 39.72 | 41.970 | 47.170 | 9.292 | N/A | N/A |
np/qs = quicksort with python library numpy on 1 core timsort = default python "sorted(...)" on 1 core odd/even = simple odd even sort on 1 core
Count Processes | 15 | 30 | 60 | 120 | 240 | 480 | ||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Count Values | Scaling | Scaling | Scaling | Scaling | Scaling | Scaling | ||||||
4.800 | 0,976 | 1,355 | 1,938 | 3,444 | 6,545 | 12,657 | ||||||
48.000 | 1,027 | 1,052 | 1,368 | 1,010 | 2,064 | 1,065 | 3,539 | 1,028 | 6,775 | 1,035 | 12,711 | 1,004 |
480.000 | 1,630 | 1,587 | 2,001 | 1,463 | 2,662 | 1,290 | 4,071 | 1,150 | 7,441 | 1,098 | 13,651 | 1,074 |
4.800.000 | 7,566 | 4,642 | 7,840 | 3,918 | 8,545 | 3,210 | 11,537 | 2,834 | 15,479 | 2,080 | 22,729 | 1,665 |
48.000.000 | 71,458 | 9,445 | 71,589 | 9,131 | 71,076 | 8,318 | 75,547 | 6,548 | 103,359 | 6,677 | 105,701 | 4,650 |