.
Department Of Computer Engineering
STES’S SINHGAD ACADEMY OF ENGINEERING KONDHWA
BK, PUNE 411048
2024-2025
“Evaluate performance enhancement of parallel Quicksort Algorithm using
MPI.”
Submitted to the
Savitribai Phule Pune University
In partial fulfillment for the award of the Degree of
Bachelor of Engineering
in
Computer Engineering
By
1) Nikhil Khade COBA14
2) Arshin Mokashi COBB26
3) Dipti Panchal COBA27
Under the guidance of
Prof. [Link]
1
CERTIFICATE
This is to certify that the mini project report entitled “Evaluate performance
enhancement of parallel quicksort using MPI” being submitted by Dipti Panchal
COBB27, Arshin Mokashi COBB26 and Nikhil Khade COBA14 is a record of
bonafide work carried out by him/her under the supervision and guidance of Prof.
[Link] in partial fulfillment of the requirement for BE (Computer Engineering) –
2019 course of Savitribai Phule Pune University, Pune in the academic year 2024-2025.
Date:
Place: Pune
Subject Coordinator Head of the Department
Principal
This Mini Project report has been examined by us as per the Savitribai Phule Pune University,
Pune requirements at SINHGAD ACADEMY OF ENGINEERING Pune – 411048
Internal Examiner External Examiner
2
ACKNOWLEDGEMENT
First and foremost, praises and thanks to the God, the Almighty, for showers of
blessings throughout my project work to complete the research successfully.
I would like to express my deep and sincere gratitude to my subject teacher Prof.
[Link] for giving us the opportunity to do this project and provide
invaluable guidance throughout this project. Her dynamism, vision, sincerity,
and motivation have deeply inspired us. She has taught us the methodology to
carry out the research and to present the project works as clearly as possible. It
was a great privilege and honor to work and study under her guidance. We are
extremely grateful for what she has offered us. We would also like to thank him
for his friendship, empathy, and great sense of humor.
We are extremely grateful to all group members Harshvardhan Patil, Sahil
Chavan, and Mohit Nagarkar for their dedication and consistency towards this
mini project. And also thankful for all the resources which are provided by each
group member and that played a very crucial role in the accomplishment of this
project.
Name Sign
Nikhil Khade
Arshin Mokashi
Dipti Panchal
(Student's Name & Signature)
3
CONTENTS
Sr. No TITLE Page no
1. Abstract 5
2. Introduction 6
3. Problem Statement 7
4. Motivation 7
5. Objectives 8
6. Theory and Outputs 8-10
7. Conclusion 11
8. References 11
4
Abstract
This study investigates the performance enhancement achieved by implementing the
Quicksort algorithm in parallel using the Message Passing Interface (MPI). Quicksort is
a widely used sorting algorithm renowned for its efficiency in sequential computing.
However, with the increasing demand for high-performance computing, there is a
growing need to leverage parallel processing to further accelerate computational tasks.
In this work, the classic Quicksort algorithm is parallelized by distributing data and
computational workload among multiple processors using MPI. The parallel version is
benchmarked against its sequential counterpart under various data sizes and processor
counts to assess speedup, efficiency, and scalability. Experimental results indicate a
significant reduction in execution time with increasing processor count, demonstrating
that parallel Quicksort using MPI offers a scalable and efficient solution for large-scale
sorting tasks. The findings validate the suitability of MPI-based parallelism in optimizing
divide-and-conquer algorithms like Quicksort.
5
Introduction
Sorting is one of the most fundamental operations in computer science, with wide-ranging applications
in data processing, information retrieval, and algorithm optimization. Among the many sorting
algorithms available, Quicksort stands out due to its average-case time complexity of O(n log n) and its
efficient divide-and-conquer approach. Despite its efficiency in sequential computation, Quicksort can
become a bottleneck when dealing with large datasets or real-time processing needs. As modern
computing increasingly relies on multi- core and distributed systems, enhancing algorithm performance
through parallelism has become a necessity.
Parallel computing enables tasks to be divided and executed concurrently across multiple processors,
thereby significantly reducing execution time and improving performance. Message Passing Interface
(MPI) is a standardized and portable message-passing system designed to allow processes to
communicate with one another in a distributed memory environment. MPI is particularly well-suited for
high-performance computing tasks, including the parallelization of algorithms like Quicksort.
This research focuses on the parallel implementation of the Quicksort algorithm using MPI and
evaluates its performance against the traditional sequential version. By dividing the dataset among
multiple processors and applying recursive sorting in parallel, we aim to minimize sorting time and
optimize resource utilization.
6
Problem Statement
Sequential Quicksort becomes inefficient with large datasets due to increased execution time. This
project aims to enhance its performance by implementing a parallel version using MPI and evaluating
its speedup, efficiency, and scalability compared to the traditional approach.
Motivation
With the exponential growth of data in modern applications, efficient data processing has become a
critical requirement. Although Quicksort is one of the fastest sorting algorithms in sequential computing,
it struggles with large-scale datasets in terms of time performance. Leveraging parallel computing can
significantly reduce this bottleneck. Using MPI, which is designed for high-performance distributed
systems, allows us to parallelize Quicksort and handle larger datasets more efficiently. This motivates
the need to explore and evaluate the performance benefits of parallel Quicksort using MPI, aiming for
faster computation.
Objective
The objective of this project is to evaluate the performance enhancement achieved by parallelizing the
Quicksort algorithm using the Message Passing Interface (MPI) library. The study aims to compare the
parallel implementation with the traditional serial Quicksort algorithm in terms of execution time
and scalability.
7
Theory
Parallel Quicksort is a parallelized version of the Quicksort algorithm, which is a popular sorting
algorithm known for its efficiency and simplicity. In the parallel version, the sorting process is divided
among multiple processors or cores, allowing for concurrent sorting of different parts of the input array.
This parallelization can lead to significant speedups, especially for large datasets. The key idea behind
parallel Quicksort is to divide the input array into smaller subarrays and distribute these subarrays among
the processors. Each processor independently sorts its assigned subarray using the Quicksort algorithm.
Once all processors have completed sorting their subarrays, the sorted subarrays are merged to obtain the
final sorted array.
Parallel Quicksort can be implemented using parallel programming techniques and libraries such as MPI
(Message Passing Interface) or OpenMP. By parallelizing the Quicksort algorithm, it is possible to take
advantage of modern multi-core processors and distributed computing environments, improving the
efficiency of the sorting process for large datasets.
The performance evaluation of the parallel Quicksort algorithm using MPI is a study aimed at assessing
the effectiveness of parallelization in enhancing the speed and efficiency of the Quicksort sorting
algorithm. Quicksort is known for its simplicity and average-case time complexity of O(n log n), but its
performance can be further improved by leveraging parallel computing techniques.
Methodology:
• Serial Quicksort: Implement the traditional serial Quicksort algorithm to serve as a baseline for
comparison.
• Parallel Quicksort with MPI: Divide the input array into smaller subarrays and distribute them among
MPI processes. Each process independently sorts its subarray using the Quicksort algorithm. Merge
the sorted subarrays to obtain the final sorted array.
• Experimental Setup: Use a cluster or a multi-core machine with MPI support for conducting
experiments. Generate input arrays of varying sizes (e.g., 10^5 to 10^7 elements) for performance
evaluation.
8
• Performance Metrics: Execution Time: Measure the time taken by the serial and parallel algorithms
to sort the input arrays.
• Scalability: Evaluate how the parallel algorithm scales with an increasing number of MPI processes.
Advantages:
1. Improved Performance: Parallel Quicksort can offer significant speedups over the serial Quicksort
algorithm, especially for large datasets, by leveraging multiple processors or cores.
2. Scalability: Parallel Quicksort can scale well with increasing dataset sizes and the number of
processors, making it suitable for sorting very large datasets efficiently.
3. Efficient Resource Utilization: By distributing the sorting process among multiple processors, Parallel
Quicksort can efficiently utilize available computing resources in parallel computing environments.
4. Simplicity: Parallel Quicksort retains the simplicity and elegance of the serial Quicksort algorithm,
making it easy to understand and implement.
Disadvantages:
1. Complexity: Implementing Parallel Quicksort requires handling additional complexity related
to data partitioning, communication, and synchronization among parallel processes, which can
make the implementation more challenging.
2. Overhead: Parallel Quicksort can introduce overhead due to the need for data partitioning,
communication, and synchronization, which can impact its performance, especially for smaller
datasets.
3. Load Imbalance: Uneven distribution of data among parallel processes can lead to load
imbalance, where some processes may finish their work earlier than others, causing idle time
and reducing overall efficiency.
4. Communication Overhead: Communication between parallel processes in Parallel Quicksort can
introduce overhead, especially in distributed computing environments, where communication
latency between nodes can be significant.
9
Application:
• Big Data Processing: In big data analytics, Parallel Quicksort can be used to efficiently sort large
datasets distributed across multiple nodes in a cluster.
• Parallel File Systems: Parallel Quicksort can be used to sort file directories or file metadata in parallel
file systems, improving file access and retrieval times.
• Database Systems: Parallel Quicksort can be used in database systems to sort large result sets or
indexes, improving query performance.
• Scientific Computing: Parallel Quicksort is used in scientific computing applications to sort large
arrays of data generated in simulations or experiments.
• Data Warehousing: In data warehousing environments, Parallel Quicksort can be used to sort and
organize large volumes of data for analysis and reporting.
10
Implementation:
Code:
#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
using namespace
std;
void swap(int* arr, int i, int j)
{ int t = arr[i];
arr[i] =
arr[j]; arr[j]
= t;
}
void quicksort(int* arr, int start, int end)
{ int pivot, index;
if (end <= 1) return;
pivot = arr[start + end / 2]; swap(arr, start,
start + end / 2); index = start; for (int i =
start + 1; i < start + end; i++) {
if (arr[i] < pivot) {
index++; swap(arr,
i, index);
} } swap(arr, start, index);
quicksort(arr, start, index -
start);
quicksort(arr, index + 1, start + end - index - 1);
}
int* merge(int* arr1, int n1, int* arr2, int n2)
{ int* result = (int*)malloc((n1 + n2) * sizeof(int));
int i = 0; int j = 0; int k;
for (k = 0; k < n1 + n2; k++) { if (i
>= n1) { result[k] = arr2[j];
j++;
} else if (j >= n2) {
result[k] = arr1[i];
i++; }
else if (arr1[i] < arr2[j])
{ result[k] = arr1[i];
i++;
}
11
// v2[j] <= v1[i] else
{ result[k] = arr2[j];
j++;
}
} return
result;
}
int main(int argc, char* argv[])
{ int number_of_elements; int*
data = NULL; int chunk_size,
own_chunk_size; int* chunk;
FILE* file = NULL; double
time_taken; MPI_Status status;
if (argc != 3) { printf("Desired number of arguments are not
their "
"in argv ... \n"); printf("2 files
required first one input and "
"second one output ... \n"); exit(-1);
}
int number_of_process, rank_of_process; int rc =
MPI_Init(&argc, &argv);
if (rc != MPI_SUCCESS) { printf("Error in
creating MPI "
"program.\n "
"Terminating ............ \n");
MPI_Abort(MPI_COMM_WORLD, rc);
}
MPI_Comm_size(MPI_COMM_WORLD, &number_of_process);
MPI_Comm_rank(MPI_COMM_WORLD, &rank_of_process);
if (rank_of_process == 0) { file
= fopen(argv[1], "r");
if (file == NULL) { printf("Error in
opening file\n"); exit(-1); } printf(
"Reading number of Elements From file ............
\n"); fscanf(file, "%d", &number_of_elements);
printf("Number of Elements in the file is %d \n",
number_of_elements);
chunk_size
= (number_of_elements % number_of_process == 0)
? (number_of_elements / number_of_process)
: (number_of_elements / number_of_process
- 1);
data = (int*)malloc(number_of_process * chunk_size
* sizeof(int));
12
printf("Reading the array from the file ................
\n"); for (int i = 0; i < number_of_elements; i++)
{ fscanf(file, "%d", &data[i]);
}
for (int i = number_of_elements; i <
number_of_process * chunk_size; i++) {
data[i] = 0;
}
printf("Elements in the array is : \n"); for
(int i = 0; i < number_of_elements; i++) {
printf("%d ", data[i]);
}
printf("\n");
fclose(file);
file = NULL;
}
MPI_Barrier(MPI_COMM_WORLD);
time_taken -= MPI_Wtime();
MPI_Bcast(&number_of_elements, 1, MPI_INT, 0,
MPI_COMM_WORLD);
chunk_size
= (number_of_elements % number_of_process == 0)
? (number_of_elements / number_of_process)
: number_of_elements
/ (number_of_process - 1);
chunk = (int*)malloc(chunk_size * sizeof(int));
MPI_Scatter(data, chunk_size, MPI_INT, chunk,
chunk_size, MPI_INT, 0, MPI_COMM_WORLD);
free(data); data = NULL;
own_chunk_size = (number_of_elements
>= chunk_size * (rank_of_process + 1))
? chunk_size
: (number_of_elements
- chunk_size * rank_of_process);
quicksort(chunk, 0, own_chunk_size);
for (int step = 1; step < number_of_process; step =
2 * step) {
if (rank_of_process % (2 * step) != 0) {
MPI_Send(chunk, own_chunk_size, MPI_INT,
rank_of_process - step, 0,
MPI_COMM_WORLD);
break;
}
if (rank_of_process + step < number_of_process) { int
received_chunk_size
= (number_of_elements
>= chunk_size
* (rank_of_process + 2 * step))
13
? (chunk_size * step)
: (number_of_elements
- chunk_size
* (rank_of_process + step));
int* chunk_received; chunk_received =
(int*)malloc( received_chunk_size *
sizeof(int));
MPI_Recv(chunk_received,
received_chunk_size, MPI_INT,
rank_of_process + step, 0,
MPI_COMM_WORLD, &status);
data = merge(chunk, own_chunk_size,
chunk_received,
received_chunk_size);
free(chunk); free(chunk_received); chunk = data;
own_chunk_size= own_chunk_size +
received_chunk_size;
} } time_taken +=
MPI_Wtime();
if (rank_of_process == 0) {
file = fopen(argv[2], "w");
if (file == NULL) { printf("Error in opening file...
\n"); exit(-1);
}
fprintf( file,
"Total number of Elements in the array :
%d\n", own_chunk_size);
for (int i = 0; i < own_chunk_size; i++) {
fprintf(file, "%d ", chunk[i]);
} fclose(file); printf("\n\n\n\nResult printed
in [Link] file "
"and shown below: \n"); printf("Total number
of Elements given as input : "
"%d\n",
number_of_elements);
printf("Sorted array is: \n");
for (int i = 0; i < number_of_elements; i++) { printf("%d
", chunk[i]);
} printf(
"\n\nQuicksort %d ints on %d procs: %f
secs\n", number_of_elements,
number_of_process, time_taken);
}
MPI_Finalize();
return 0;
}
14
Output:
15
Conclusion:
The parallel Quicksort algorithm using MPI demonstrates significant performance enhancement
compared to the serial algorithm, especially for large input sizes. The scalability of the parallel algorithm
allows it to efficiently utilize resources in a distributed computing environment, making it suitable for
high-performance computing applications requiring efficient sorting.
In this study, we implemented and evaluated the performance of the Quicksort algorithm in a parallel
computing environment using the Message Passing Interface (MPI). The results demonstrate that
parallelizing Quicksort significantly reduces execution time, especially as the number of processors and
size of the dataset increase. By distributing the workload efficiently among multiple processes, the MPI-
based parallel Quicksort not only improves sorting performance but also highlights the scalability and
effectiveness of parallel programming in handling computation-intensive tasks.
The experiment shows that parallel computing is a practical solution for enhancing traditional
algorithms like Quicksort. However, the performance gain depends on factors such as data distribution,
communication overhead, and system architecture. Further improvements can be achieved by
optimizing load balancing and minimizing inter-process communication.
16
References
1. Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts. Wiley.
2. Gropp, W., Lusk, E., & Skjellum, A. (1999). Using MPI: Portable Parallel Programming with
the Message-Passing Interface. MIT Press.
3. Hennessy, J. L., & Patterson, D. A. (2011). Computer Architecture: A Quantitative Approach.
Morgan Kaufmann.
4. Message Passing Interface Forum. (2015). MPI: A Message-Passing Interface Standard –
Version 3.1. Retrieved from: [Link]
5. GeeksforGeeks.(n.d.). Quicksort Algorithm. Retrieved from:
[Link]
6. Tannenbaum, A. S., & Bos, H. (2015). Modern Operating Systems. Pearson.
17