Skip to content

Latest commit

 

History

History
55 lines (39 loc) · 1.77 KB

README.md

File metadata and controls

55 lines (39 loc) · 1.77 KB

Parallel Bitonic Sort using MPI

Sorting algorithms usually take $O(nlogn)$ time to sort an array of size n. Bitonic sort is a parallel sorting algorithm that can sort very large arrays faster with the power of MPI and parallel processing.

The algorithm follows the standard Bitonic Sort Network pattern as shown below. More info about the implementation can be found in the report.

Bitonic Sort

How to run

  1. Clone the repository
git clone [email protected]:NontasBak/parallel-bitonic-sort.git
  1. Change your active directory
cd parallel-bitonic-sort/src/mpi/
  1. Compile the code using make. You might need to install mpicc if you haven't already.
  2. Run the code
make run
  1. Remove the executables after running
make clean

In order to change the number of elements per process, you can modify the variable num_q inside the main function.

To change the number of processes, you can modify the mpirun command in the Makefile.

Benchmarks

The following benchmarks were run on the Aristotel Cluster on the rome and batch partitions. The specs can be found here.

Execution time with different number of processes (2^27 elements per process)

Benchmark 2

Speedup compared to QuickSort (2^27 elements total)

Benchmark 3

Execution time using different number of nodes (128 processes)

Benchmark 1

Authors

Eleni Koumparidou and Epameinondas Bakoulas

Class: Parallel and Distributed Systems with professor Nikolaos Pitsianis

January 2025