Shri Madhwa Vadiraja Institute of Technology and Management
Bantakal , Udupi
Dept. of Computer Science and Engineering
(Parallel Computing)
Title
Performance Analysis of Serial and Parallel Shell Sort
Using OpenMP
Submitted to : Mr. Raghavendra GS
[Link]
Department of Computer Science and Engineering
Submitted by :
Satvik S Bhat Swayam Foundekar
4MW22CS139 4MW22CS171
Sujan Kumar Supriya S Poojary
4MW22CS164 4MW22CS69
4th Year
Department of Computer Science and Engineering
Performance Analysis of Serial and Parallel Shell Sort Using OpenMP
Introduction :
Sorting is a fundamental operation in computer science, widely used in databases,
operating systems, numerical computations, and various optimization tasks. Shell Sort is
an improvement over Insertion Sort that allows exchanges of far-apart elements,
significantly reducing the time taken for partially sorted lists.
With the rise of multicore processors, parallelizing traditional sorting algorithms has
become essential to improve performance. This report analyzes the performance
improvements gained by parallelizing Shell Sort using OpenMP, a widely used API for
shared-memory parallel programming.
Objective :
The main objectives of this study are:
1. To implement Shell Sort in both serial and parallel versions.
2. To evaluate the performance of both versions using OpenMP.
3. To measure execution time, speedup, and efficiency for different thread counts.
4. To analyze the behavior of Shell Sort when parallelized, and identify whether it
benefits significantly from multithreading.
Methodology / Procedure :
Hardware & Software
Programming Language: C
Parallel Framework: OpenMP
Array Size: 100000 elements
Number of Threads Tested: 1, 2, 4, 8
System: Multi-core CPU (OpenMP compatible)
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include <time.h>
int i, gap, t;
void shellSortSerial(int arr[], int n) {
for( gap = n / 2; gap > 0; gap /= 2) {
for( i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
}
void shellSortParallel(int arr[], int n) {
for( gap = n / 2; gap > 0; gap /= 2) {
#pragma omp parallel for shared(arr, gap, n)
for( i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
int main() {
int n = 100000;
int *arr = (int *)malloc(n * sizeof(int));
int *temp = (int *)malloc(n * sizeof(int));
double start, end, serial_time, parallel_time;
int max_threads = 8;
srand(time(NULL));
for( i = 0; i < n; i++)
arr[i] = rand();
// SERIAL EXECUTION
for( i = 0; i < n; i++) temp[i] = arr[i];
start = omp_get_wtime();
shellSortSerial(temp, n);
end = omp_get_wtime();
serial_time = end - start;
printf("\n===== SHELL SORT PERFORMANCE ANALYSIS =====\n");
printf("Array size: %d\n", n);
printf("Serial Execution Time: %.6f sec\n\n", serial_time);
// PARALLEL EXECUTION
printf("Threads\tTime(sec)\tSpeedup\t\tEfficiency(%%)\n");
printf("-----------------------------------------------------\n");
for( t = 1; t <= max_threads; t *= 2) {
omp_set_num_threads(t);
for( i = 0; i < n; i++) temp[i] = arr[i];
start = omp_get_wtime();
shellSortParallel(temp, n);
end = omp_get_wtime();
parallel_time = end - start;
double speedup = serial_time / parallel_time;
double efficiency = (speedup / t) * 100.0;
printf("%d\t%.6f\t%.2f\t\t%.2f\n", t, parallel_time, speedup, efficiency);
}
printf("-----------------------------------------------------\n");
printf("Note: Efficiency = (Speedup / Threads) x 100\n");
free(arr);
free(temp);
return 0;
}
Algorithm Implemented
The code implements two versions of Shell Sort:
a. Serial Shell Sort
Performs traditional Shell Sort using decreasing gaps.
Inner loops run sequentially.
b. Parallel Shell Sort
Each pass of the outer loop is parallelized using:
#pragma omp parallel for
Threads work on different sections of the array for the current gap size.
Performance Metrics
For each thread count:
Execution Time (Tₚ)
Time taken to complete sorting using p threads.
Speedup (Sₚ)
𝑇
𝑆 =
𝑇
Efficiency (Eₚ)
𝑆
𝐸 = × 100
𝑝
Where:
Tₛ = Serial execution time
Tₚ = Parallel execution time with p threads
Experimental Results:
Analysis:
Serial vs Parallel Performance
The serial version acts as the baseline.
As threads increase, execution time generally decreases.
Speedup Observation
Speedup improves when going from 1 → 2 → 4 threads.
Speedup becomes limited due to:
o Gap-based dependencies in Shell Sort.
o High number of memory accesses.
o False sharing between threads.
Efficiency Trend
Efficiency decreases as threads increase.
This is expected because:
o Shell Sort is not fully parallel-friendly.
o Overhead of thread creation and synchronization.
o Workload imbalance between threads.
Why Shell Sort Doesn’t Scale Well
Shell Sort has inherent data dependencies in its inner loop.
Even though the for(i = gap; i < n; i++) loop is parallelized, the shifting operations inside
the loop may cause:
Race conditions without correct memory barriers
Cache contention
Irregular access patterns reducing parallel efficiency
Thus, Shell Sort benefits only modestly from increasing threads.
Conclusion :
This assignment demonstrates the practical use of OpenMP for accelerating CPU-bound algorithms.
Key findings:
Serial Shell Sort performs reliably but slowly for large datasets.
Parallel Shell Sort offers performance improvement, especially for small thread counts.
Speedup increases with threads, but not linearly.
Efficiency drops as threads increase due to parallel overhead and dependency issues.
Shell Sort is not highly scalable, but moderate speedup is achievable on multi-core processors.
****************************