-
Aayush Kapadia (201401407)
-
Mit Naria (201401448)
Brief explanation of How algorithm works is present in file named CS301_project_ppt_pdf.pdf.
Proof of complexity of algorithm and scalability of algorithm is discussed in file CS301_project_report.pdf.
C, MPI library
For C, use GCC or any other C compiler.
For MPI library, install MPICH using command sudo apt-get install libcr-dev mpich2 mpich2-doc.
qsort.c -> Serial Quicksort implementation. This code automatically generates random input data (aka unsorted array) and generates output. We haven't stored input and output files to avoid any I/O related bottlenecks. (from disk to RAM). But this can be done by simply uncommenting printf statements that are commented in our code.
samplesort.c -> Parallel Sample sort implementation. This code automatically generates random input data (aka unsorted array) in each node parallelly and generates parallel output. We haven't stored input and output files to avoid any I/O related bottlenecks. (from disk to RAM). But this can be done by simply setting DEBUG_FLAG=1 in our code.
If you set DEBUG_FLAG=1 , following things are generated.
-
n input files with name in0.txt , in1.txt , ... , in[p-1].txt . [ This files contains random input data (aka unsorted array). in[i].txt is the input data generated by processor with rank =i.].
-
n output files with name out0.txt , out1.txt , ... , out(p-1).txt . [ This files contains output sorted data. out[i].txt is the bucket i sorted by processor with rank =i.]
-
Global splitters printed to stderr.
- Tested on Intel Xeon. Configuration: 2 sockets, 8 cores on each socket. 1 thread per 1 core. (Intel Hyper Threading disabled.)
Problem size: 2*10^9 64 bit integers
| Number of procs | Time is seconds | Speedup | Efficiency |
|---|---|---|---|
| 1 | 864.8 | - | 1 |
| 2 | 617.02 | 1.40 | 0.70 |
| 4 | 309.6 | 2.793 | 0.6983 |
| 8 | 153.825 | 5.621 | 0.702 |
| 12 | 117.98 | 7.330 | 0.610 |
| 16 | 104.7 | 8.259 | 0.5162 |