parallel-sorting.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <omp.h>
   5 #include <time.h>
   6
   7
   8 // Global variables (simulating shared memory access)
   9 int* data = NULL;
  10 size_t data_size = 0;
  11
  12 /**
  13  * @brief Merges two sorted sub-arrays (data[low...mid] and data[mid+1...high]).
  14  * NOTE: This function must manually manage temporary memory allocation and deallocation.
  15  */
  16 void merge(int low, int mid, int high) {
  17     // Calculate sizes of the two halves
  18     int n1 = mid - low + 1;
  19     int n2 = high - mid;
  20
  21     // Manual Memory Allocation for Temporary Arrays
  22     // We must allocate space for L and R.
  23     int* L = (int*)malloc(n1 * sizeof(int));
  24     int* R = (int*)malloc(n2 * sizeof(int));
  25
  26     if (L == NULL || R == NULL) {
  27         perror("Failed to allocate temporary merge arrays");
  28         exit(EXIT_FAILURE);
  29     }
  30
  31     // Copy data from the main array into the temporary arrays
  32     for (int i = 0; i < n1; i++) {
  33         L[i] = data[low + i];
  34     }
  35     for (int j = 0; j < n2; j++) {
  36         R[j] = data[mid + 1 + j];
  37     }
  38
  39     // Standard sequential merging logic
  40     int i = 0; // Index for L
  41     int j = 0; // Index for R
  42     int k = low; // Index for the main data array
  43
  44     while (i < n1 && j < n2) {
  45         if (L[i] <= R[j]) {
  46             data[k++] = L[i++];
  47         } else {
  48             data[k++] = R[j++];
  49         }
  50     }
  51
  52     // Copy remaining elements of L
  53     while (i < n1) {
  54         data[k++] = L[i++];
  55     }
  56
  57     // Copy remaining elements of R
  58     while (j < n2) {
  59         data[k++] = R[j++];
  60     }
  61
  62     // Manual Memory Cleanup
  63     free(L);
  64     free(R);
  65 }
  66
  67 /**
  68  * @brief Recursive function to perform parallel Merge Sort using OpenMP.
  69  */
  70 void parallel_merge_sort(int low, int high) {
  71     if (low < high) {
  72         int mid = low + (high - low) / 2;
  73
  74         // Use OpenMP sections to parallelize the recursive calls, runtime handles the threads assignment and synchronization.
  75         #pragma omp parallel sections
  76         {
  77             #pragma omp section
  78             {
  79                 // Recurse on the left half
  80                 parallel_merge_sort(low, mid);
  81             }
  82             #pragma omp section
  83             {
  84                 // Recurse on the right half
  85                 parallel_merge_sort(mid + 1, high);
  86             }
  87         }
  88         // Implicit barrier ensures merge only happens when both halves are sorted.
  89         // Combine the two sorted halves
  90         merge(low, mid, high);
  91     }
  92 }
  93
  94
  95 /**
  96  * @brief Reads all integers from the specified input file.
  97  * @return 1 on success, 0 on failure.
  98  */
  99 int read_file(const char* filename) {
 100     FILE* infile = fopen(filename, "r");
 101     if (infile == NULL) {
 102         perror("Error opening input file");
 103         return 0;
 104     }
 105
 106     // Initial allocation (guessing a reasonable maximum size)
 107     size_t capacity = 1024;
 108     data = (int*)malloc(capacity * sizeof(int));
 109     if (data == NULL) {
 110         perror("Memory allocation failed for data array");
 111         fclose(infile);
 112         return 0;
 113     }
 114     int count = 0;
 115
 116     int num;
 117     while (fscanf(infile, "%d", &num) == 1) {
 118         // Check if realloc is necessary
 119         if (count == capacity - 1) {
 120             capacity *= 2;
 121             int* new_data = (int*)realloc(data, capacity * sizeof(int));
 122             if (new_data == NULL) {
 123                 perror("Failed to reallocate memory for data array");
 124                 free(data);
 125                 fclose(infile);
 126                 return 0;
 127             }
 128             data = new_data;
 129         }
 130         data[count++] = num;
 131     }
 132
 133     fclose(infile);
 134     data_size = count;
 135     return 1;
 136 }
 137
 138 /**
 139  * @brief Writes the sorted elements to the specified output file.
 140 * @return 1 on success, 0 on failure.
 141 */
 142 int write_file(const char* filename) {
 143     FILE* outfile = fopen(filename, "w");
 144     if (outfile == NULL) {
 145         perror("Error opening output file");
 146         return 0;
 147     }
 148
 149     // Write the data sequentially
 150     for (size_t i = 0; i < data_size; ++i) {
 151         fprintf(outfile, "%d\n", data[i]);
 152     }
 153
 154     fclose(outfile);
 155     return 1;
 156 }
 157
 158
 159 int main(int argc, char *argv[]) {
 160     // Handle Command Line Arguments
 161     int thread_count = -1;
 162     char *input_file = NULL;
 163     char *output_file = NULL;
 164
 165     for (int i = 1; i < argc; ++i) {
 166         if (strcmp(argv[i], "-t") == 0 && i + 1 < argc) {
 167             // Get thread count from the next argument
 168             thread_count = atoi(argv[i+1]);
 169             i++; // Skip the argument after -t
 170         } else if (input_file == NULL) {
 171             input_file = argv[i];
 172         } else if (output_file == NULL) {
 173             output_file = argv[i];
 174         }
 175     }
 176
 177     // Check for mandatory arguments and thread count
 178     if (thread_count <= 0 || input_file == NULL || output_file == NULL) {
 179         fprintf(stderr, "Usage: %s <input_file> <output_file> [-t <thread_count>]\n", argv[0]);
 180         return EXIT_FAILURE;
 181     }
 182
 183     // Setup OpenMP Threads ---
 184     omp_set_num_threads(thread_count);
 185     printf("--- Starting Sort Process ---\n");
 186     printf("Threads allocated by OpenMP: %d\n", omp_get_max_threads());
 187
 188     //  Read Data
 189     if (!read_file(input_file)) {
 190         fprintf(stderr, "Failed to read data.\n");
 191         // Clean up data memory before exit
 192         free(data);
 193         return EXIT_FAILURE;
 194     }
 195     printf("Successfully read %zu elements from %s\n", data_size, input_file);
 196
 197     // ------------------------------- WALL CLOCK TIME ------------------------------------
 198     struct timespec start_sort_time;
 199     clock_gettime(CLOCK_MONOTONIC, &start_sort_time);
 200     if (data_size > 0) {
 201         // Execute the parallel sort
 202         parallel_merge_sort(0, data_size - 1);
 203         printf("Sorting completed successfully.\n");
 204     }
 205     struct timespec end_sort_time;
 206     clock_gettime(CLOCK_MONOTONIC, &end_sort_time);
 207     // ------------------------------- END WALL CLOCK TIME ---------------------------------
 208
 209     // determine actual wall clock time
 210     double elapsed_time = (end_sort_time.tv_sec - start_sort_time.tv_sec);
 211     elapsed_time += (end_sort_time.tv_nsec - start_sort_time.tv_nsec) / 1e9;
 212
 213     if (!write_file(output_file)) {
 214         fprintf(stderr, "Failed to write output data.\n");
 215         free(data);
 216         return EXIT_FAILURE;
 217     }
 218     printf("Sorted data written successfully to %s\n", output_file);
 219     printf("Total Elapsed Wall-Clock Time: %lf seconds\n", elapsed_time);
 220
 221     // Cleanup
 222     free(data);
 223     return EXIT_SUCCESS;
 224 }