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 for simplicity)
   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     // --- Crucial Step: 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
  75         // The OpenMP runtime handles the threads assignment and synchronization.
  76         #pragma omp parallel sections
  77         {
  78             #pragma omp section
  79             {
  80                 // Recurse on the left half
  81                 parallel_merge_sort(low, mid);
  82             }
  83             #pragma omp section
  84             {
  85                 // Recurse on the right half
  86                 parallel_merge_sort(mid + 1, high);
  87             }
  88         }
  89         // Implicit barrier ensures merge only happens when both halves are sorted.
  90         // Combine the two sorted halves
  91         merge(low, mid, high);
  92     }
  93 }
  94
  95
  96 /**
  97  * @brief Reads all integers from the specified input file.
  98  * @return 1 on success, 0 on failure.
  99  */
 100 int read_file(const char* filename) {
 101     FILE* infile = fopen(filename, "r");
 102     if (infile == NULL) {
 103         perror("Error opening input file");
 104         return 0;
 105     }
 106
 107     // Initial allocation (guessing a reasonable maximum size)
 108     size_t capacity = 1024;
 109     data = (int*)malloc(capacity * sizeof(int));
 110     if (data == NULL) {
 111         perror("Memory allocation failed for data array");
 112         fclose(infile);
 113         return 0;
 114     }
 115     int count = 0;
 116
 117     int num;
 118     while (fscanf(infile, "%d", &num) == 1) {
 119         // Check if realloc is necessary
 120         if (count == capacity - 1) {
 121             capacity *= 2;
 122             int* new_data = (int*)realloc(data, capacity * sizeof(int));
 123             if (new_data == NULL) {
 124                 perror("Failed to reallocate memory for data array");
 125                 free(data);
 126                 fclose(infile);
 127                 return 0;
 128             }
 129             data = new_data;
 130         }
 131         data[count++] = num;
 132     }
 133
 134     fclose(infile);
 135     data_size = count;
 136     return 1;
 137 }
 138
 139 /**
 140  * @brief Writes the sorted elements to the specified output file.
 141 * @return 1 on success, 0 on failure.
 142 */
 143 int write_file(const char* filename) {
 144     FILE* outfile = fopen(filename, "w");
 145     if (outfile == NULL) {
 146         perror("Error opening output file");
 147         return 0;
 148     }
 149
 150     // Write the data sequentially
 151     for (size_t i = 0; i < data_size; ++i) {
 152         fprintf(outfile, "%d\n", data[i]);
 153     }
 154
 155     fclose(outfile);
 156     return 1;
 157 }
 158
 159
 160 int main(int argc, char *argv[]) {
 161     // Handle Command Line Arguments
 162     int thread_count = -1;
 163     char *input_file = NULL;
 164     char *output_file = NULL;
 165
 166     for (int i = 1; i < argc; ++i) {
 167         if (strcmp(argv[i], "-t") == 0 && i + 1 < argc) {
 168             // Get thread count from the next argument
 169             thread_count = atoi(argv[i+1]);
 170             i++; // Skip the argument after -t
 171         } else if (input_file == NULL) {
 172             input_file = argv[i];
 173         } else if (output_file == NULL) {
 174             output_file = argv[i];
 175         }
 176     }
 177
 178     // Check for mandatory arguments and thread count
 179     if (thread_count <= 0 || input_file == NULL || output_file == NULL) {
 180         fprintf(stderr, "Usage: %s <input_file> <output_file> [-t <thread_count>]\n", argv[0]);
 181         return EXIT_FAILURE;
 182     }
 183
 184     // Setup OpenMP Threads ---
 185     omp_set_num_threads(thread_count);
 186     printf("--- Starting Sort Process ---\n");
 187     printf("Threads allocated by OpenMP: %d\n", omp_get_max_threads());
 188
 189     //  Read Data
 190     if (!read_file(input_file)) {
 191         fprintf(stderr, "Failed to read data.\n");
 192         // Clean up data memory before exit
 193         free(data);
 194         return EXIT_FAILURE;
 195     }
 196     printf("Successfully read %zu elements from %s\n", data_size, input_file);
 197
 198     // Parallel Sort Data
 199     struct timespec start_sort_time;
 200     clock_gettime(CLOCK_MONOTONIC, &start_sort_time);
 201     if (data_size > 0) {
 202         // Execute the parallel sort
 203         parallel_merge_sort(0, data_size - 1);
 204         printf("Sorting completed successfully.\n");
 205     }
 206     struct timespec end_sort_time;
 207     clock_gettime(CLOCK_MONOTONIC, &end_sort_time);
 208
 209     // Write Results
 210     double elapsed_time = (end_sort_time.tv_sec - start_sort_time.tv_sec);
 211     elapsed_time += (end_sort_time.tv_sec - start_sort_time.tv_sec) / 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 }