mga revised this gist 5 months ago. Go to revision
1 file changed, 132 insertions
main.c(file created)
| @@ -0,0 +1,132 @@ | |||
| 1 | + | #include <math.h> | |
| 2 | + | #include <pthread.h> | |
| 3 | + | #include <stdio.h> | |
| 4 | + | #include <stdlib.h> | |
| 5 | + | #include <string.h> | |
| 6 | + | #include <unistd.h> | |
| 7 | + | ||
| 8 | + | #define TRUE 1 | |
| 9 | + | #define FALSE 0 | |
| 10 | + | ||
| 11 | + | int *array_ptr; | |
| 12 | + | pthread_barrier_t barrier; | |
| 13 | + | ||
| 14 | + | typedef struct { | |
| 15 | + | int thread_id; | |
| 16 | + | int *arr; | |
| 17 | + | int size; | |
| 18 | + | int n_threads; | |
| 19 | + | } thread_args; | |
| 20 | + | ||
| 21 | + | void generateArray(int *array, int size) { | |
| 22 | + | for (int i = 0; i < size; ++i) { | |
| 23 | + | array[i] = rand() % 1000; | |
| 24 | + | } | |
| 25 | + | } | |
| 26 | + | ||
| 27 | + | int verify(int *array, int size) { | |
| 28 | + | for (int i = 0; i < size - 1; ++i) { | |
| 29 | + | if (array[i] > array[i + 1]) { | |
| 30 | + | return FALSE; | |
| 31 | + | } | |
| 32 | + | } | |
| 33 | + | return TRUE; | |
| 34 | + | } | |
| 35 | + | ||
| 36 | + | void printArray(int *arr, int n) { | |
| 37 | + | for (int i = 0; i < n; ++i) { | |
| 38 | + | printf("%d ", arr[i]); | |
| 39 | + | } | |
| 40 | + | printf("\n"); | |
| 41 | + | } | |
| 42 | + | ||
| 43 | + | void *parallel_bubble_sort(void *arg) { | |
| 44 | + | thread_args *args = (thread_args *)arg; | |
| 45 | + | int tid = args->thread_id; | |
| 46 | + | int *arr = args->arr; | |
| 47 | + | int n = args->size; | |
| 48 | + | int n_threads = args->n_threads; | |
| 49 | + | ||
| 50 | + | for (int step = 0; step < n; ++step) { | |
| 51 | + | int start = (step % 2 == 0) ? 0 : 1; | |
| 52 | + | for (int i = start + 2 * tid; i < n - 1; i += 2 * n_threads) { | |
| 53 | + | if (arr[i] > arr[i + 1]) { | |
| 54 | + | int tmp = arr[i]; | |
| 55 | + | arr[i] = arr[i + 1]; | |
| 56 | + | arr[i + 1] = tmp; | |
| 57 | + | } | |
| 58 | + | } | |
| 59 | + | pthread_barrier_wait(&barrier); | |
| 60 | + | } | |
| 61 | + | ||
| 62 | + | return NULL; | |
| 63 | + | } | |
| 64 | + | ||
| 65 | + | // Argument parsing utility | |
| 66 | + | int get_named_arg(int argc, char *argv[], const char *name) { | |
| 67 | + | for (int i = 1; i < argc - 1; ++i) { | |
| 68 | + | if (strcmp(argv[i], name) == 0) { | |
| 69 | + | return atoi(argv[i + 1]); | |
| 70 | + | } | |
| 71 | + | } | |
| 72 | + | return -1; | |
| 73 | + | } | |
| 74 | + | ||
| 75 | + | int main(int argc, char *argv[]) { | |
| 76 | + | int power = get_named_arg(argc, argv, "--size"); | |
| 77 | + | int n_threads = get_named_arg(argc, argv, "--threads"); | |
| 78 | + | ||
| 79 | + | if (power < 1 || n_threads < 1) { | |
| 80 | + | fprintf(stderr, "Usage: %s --threads <num> --size <log10(size)>\n", | |
| 81 | + | argv[0]); | |
| 82 | + | return EXIT_FAILURE; | |
| 83 | + | } | |
| 84 | + | ||
| 85 | + | int n = (int)pow(10, power); | |
| 86 | + | ||
| 87 | + | array_ptr = (int *)malloc(n * sizeof(int)); | |
| 88 | + | if (!array_ptr) { | |
| 89 | + | perror("malloc"); | |
| 90 | + | return EXIT_FAILURE; | |
| 91 | + | } | |
| 92 | + | ||
| 93 | + | pthread_t *threads = malloc(n_threads * sizeof(pthread_t)); | |
| 94 | + | thread_args *args = malloc(n_threads * sizeof(thread_args)); | |
| 95 | + | if (!threads || !args) { | |
| 96 | + | perror("malloc"); | |
| 97 | + | return EXIT_FAILURE; | |
| 98 | + | } | |
| 99 | + | ||
| 100 | + | generateArray(array_ptr, n); | |
| 101 | + | pthread_barrier_init(&barrier, NULL, n_threads); | |
| 102 | + | ||
| 103 | + | for (int i = 0; i < n_threads; ++i) { | |
| 104 | + | args[i].thread_id = i; | |
| 105 | + | args[i].arr = array_ptr; | |
| 106 | + | args[i].size = n; | |
| 107 | + | args[i].n_threads = n_threads; | |
| 108 | + | pthread_create(&threads[i], NULL, parallel_bubble_sort, &args[i]); | |
| 109 | + | } | |
| 110 | + | ||
| 111 | + | for (int i = 0; i < n_threads; ++i) { | |
| 112 | + | pthread_join(threads[i], NULL); | |
| 113 | + | } | |
| 114 | + | ||
| 115 | + | pthread_barrier_destroy(&barrier); | |
| 116 | + | ||
| 117 | + | // Uncomment to see result | |
| 118 | + | // printArray(array_ptr, n); | |
| 119 | + | ||
| 120 | + | /* | |
| 121 | + | if (verify(array_ptr, n)) | |
| 122 | + | printf("\nArray is sorted.\n"); | |
| 123 | + | else | |
| 124 | + | printf("\nArray is NOT sorted.\n"); | |
| 125 | + | */ | |
| 126 | + | ||
| 127 | + | free(array_ptr); | |
| 128 | + | free(threads); | |
| 129 | + | free(args); | |
| 130 | + | ||
| 131 | + | return 0; | |
| 132 | + | } | |
Newer
Older