main.c
· 2.7 KiB · C
Raw
#include <math.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define TRUE 1
#define FALSE 0
int *array_ptr;
pthread_barrier_t barrier;
typedef struct {
int thread_id;
int *arr;
int size;
int n_threads;
} thread_args;
void generateArray(int *array, int size) {
for (int i = 0; i < size; ++i) {
array[i] = rand() % 1000;
}
}
int verify(int *array, int size) {
for (int i = 0; i < size - 1; ++i) {
if (array[i] > array[i + 1]) {
return FALSE;
}
}
return TRUE;
}
void printArray(int *arr, int n) {
for (int i = 0; i < n; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
void *parallel_bubble_sort(void *arg) {
thread_args *args = (thread_args *)arg;
int tid = args->thread_id;
int *arr = args->arr;
int n = args->size;
int n_threads = args->n_threads;
for (int step = 0; step < n; ++step) {
int start = (step % 2 == 0) ? 0 : 1;
for (int i = start + 2 * tid; i < n - 1; i += 2 * n_threads) {
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
}
}
pthread_barrier_wait(&barrier);
}
return NULL;
}
// Argument parsing utility
int get_named_arg(int argc, char *argv[], const char *name) {
for (int i = 1; i < argc - 1; ++i) {
if (strcmp(argv[i], name) == 0) {
return atoi(argv[i + 1]);
}
}
return -1;
}
int main(int argc, char *argv[]) {
int power = get_named_arg(argc, argv, "--size");
int n_threads = get_named_arg(argc, argv, "--threads");
if (power < 1 || n_threads < 1) {
fprintf(stderr, "Usage: %s --threads <num> --size <log10(size)>\n",
argv[0]);
return EXIT_FAILURE;
}
int n = (int)pow(10, power);
array_ptr = (int *)malloc(n * sizeof(int));
if (!array_ptr) {
perror("malloc");
return EXIT_FAILURE;
}
pthread_t *threads = malloc(n_threads * sizeof(pthread_t));
thread_args *args = malloc(n_threads * sizeof(thread_args));
if (!threads || !args) {
perror("malloc");
return EXIT_FAILURE;
}
generateArray(array_ptr, n);
pthread_barrier_init(&barrier, NULL, n_threads);
for (int i = 0; i < n_threads; ++i) {
args[i].thread_id = i;
args[i].arr = array_ptr;
args[i].size = n;
args[i].n_threads = n_threads;
pthread_create(&threads[i], NULL, parallel_bubble_sort, &args[i]);
}
for (int i = 0; i < n_threads; ++i) {
pthread_join(threads[i], NULL);
}
pthread_barrier_destroy(&barrier);
// Uncomment to see result
// printArray(array_ptr, n);
/*
if (verify(array_ptr, n))
printf("\nArray is sorted.\n");
else
printf("\nArray is NOT sorted.\n");
*/
free(array_ptr);
free(threads);
free(args);
return 0;
}
| 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 | } |
| 133 |