Introduction to Parallel Computer Architecture Counting sort

counting_sort/counting_sort.cu

/* Host-side code to perform counting sort * Author: Naga Kandasamy * Date created: 2/15/2018 * Date modified: 3/17/2018 * * Compile as follows: make clean && make */ #include <stdlib.h> #include <stdio.h> #include <time.h> #include <sys/time.h> #include <string.h> #include <math.h> #include <limits.h> #include "counting_sort.h" #include "counting_sort_kernel.cu" extern "C" int counting_sort_gold (int *, int *, int, int); int get_random_integer (int, int); void print_array (int *, int); void print_min_and_max_in_array (int *, int); void compute_on_device (int *, int *, int, int); int check_if_sorted (int *, int); int compare_results (int *, int *, int); int main (int argc, char **argv) { int *input_array, *sorted_array_reference, *sorted_array_d; // Populate the input array with random integers between [0, RANGE] printf ("Generating input array with %d elements in the range 0 to %d.\n", NUM_ELEMENTS, RANGE); input_array = (int *)malloc (NUM_ELEMENTS * sizeof(int)); if (input_array == NULL){ printf("Cannot malloc memory for the input array. \n"); exit(0); } srand (time (NULL)); for (int i = 0; i < NUM_ELEMENTS; i++) input_array[i] = get_random_integer (0, RANGE); #ifdef DEBUG_FLAG print_array (input_array, NUM_ELEMENTS); print_min_and_max_in_array (input_array, NUM_ELEMENTS); #endif /* Sort the elements in the input array using the reference implementation. * The result is placed in sorted_array_reference. */ int status; sorted_array_reference = (int *)malloc (NUM_ELEMENTS * sizeof(int)); if (sorted_array_reference == NULL){ printf("Cannot malloc memory for the output array. \n"); exit(0); } memset(sorted_array_reference, 0, NUM_ELEMENTS); status = counting_sort_gold (input_array, sorted_array_reference, NUM_ELEMENTS, RANGE); if (status == 0){ exit (0); } status = check_if_sorted (sorted_array_reference, NUM_ELEMENTS); if (status == 0){ printf ("Error sorting the input array using the reference code. \n"); exit (0); } printf("Counting sort was successful on the CPU. \n"); #ifdef DEBUG_FLAG print_array (sorted_array_reference, NUM_ELEMENTS); #endif /* Write the function to sort the elements in the array in parallel fashion. * The result should be placed in sorted_array_mt. */ sorted_array_d = (int *)malloc (NUM_ELEMENTS * sizeof(int)); if (sorted_array_d == NULL){ printf("Cannot malloc memory for the output array. \n"); exit(0); } memset(sorted_array_d, 0, NUM_ELEMENTS); compute_on_device (input_array, sorted_array_d, NUM_ELEMENTS, RANGE); /* Check the two results for correctness. */ printf("Comparing CPU and GPU results. \n"); status = compare_results (sorted_array_reference, sorted_array_d, NUM_ELEMENTS); if (status == 1) printf ("Test passed. \n"); else printf ("Test failed. \n"); exit(0); } /* Write the GPU implementation of counting sort. */ void compute_on_device (int *input_array, int *sorted_array, int num_elements, int range) { } /* Check if the array is sorted. */ int check_if_sorted (int *array, int num_elements) { int status = 1; for (int i = 1; i < num_elements; i++){ if (array[i -1] > array[i]){ status = 0; break; } } return status; } /* Check if the arrays elements are identical. */ int compare_results (int *array_1, int *array_2, int num_elements) { int status = 1; for (int i = 0; i < num_elements; i++){ if (array_1[i] != array_2[i]){ status = 0; break; } } return status; } /* Returns a random integer between the specified min and max values. */ int get_random_integer (int min, int max) { return (int) floor ((double)(min + (max - min + 1) * ((float) rand () / ((float) RAND_MAX + 1.0)))); } /* Helper function to print the given array. */ void print_array (int *this_array, int num_elements) { printf ("Array: "); for (int i = 0; i < num_elements; i++) printf ("%d ", this_array[i]); printf ("\n"); } /* Helper function to return the min and max values in the given array. */ void print_min_and_max_in_array (int *this_array, int num_elements) { int i; int current_min = INT_MAX; for (i = 0; i < num_elements; i++) if (this_array[i] < current_min) current_min = this_array[i]; int current_max = INT_MIN; for (i = 0; i < num_elements; i++) if (this_array[i] > current_max) current_max = this_array[i]; printf ("Minimum value in the array: %d. \n", current_min); printf ("Maximum value in the array: %d. \n", current_max); }