C 并行排序

问题描述 投票:2回答:1

我有以下代码,它是在C语言中使用线程实现并行排序。我如何使用命令行参数来表示线程数,而不是使用 #define NUM_THREADS 2?

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/time.h>


#define SEED  100
#define LENGTH 100000
#define UPPER_LIM 10000
#define LOWER_LIM  1
#define NUM_THREADS 2


const int NUMBERS_PER_THREAD = LENGTH / NUM_THREADS;
const int OFFSET = LENGTH % NUM_THREADS;
int arr[LENGTH];

int generate_random_number(unsigned int lower_limit, unsigned int upper_limit);
void merge_sort(int arr[], int left, int right);
void merge(int arr[], int left, int middle, int right);
void* thread_merge_sort(void* arg);
void merge_sections_of_array(int arr[], int number, int aggregation);
void test_array_is_in_order(int arr[]);

int main(int argc, const char * argv[]) {
    srand(SEED);
    struct timeval  start, end;
    double time_spent;


    for (int i = 0; i < LENGTH; i ++) {
        arr[i] = generate_random_number(LOWER_LIM, UPPER_LIM);
    }

    /* incepe timing-ul */
    pthread_t threads[NUM_THREADS];
    gettimeofday(&start, NULL);

    /* creaza thread-urile */
    for (long i = 0; i < NUM_THREADS; i ++) {
        int rc = pthread_create(&threads[i], NULL, thread_merge_sort, (void *)i);
        if (rc){
            printf("ERROR; return code from pthread_create() is %d\n", rc);
            exit(-1);
        }
    }

    for(long i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }

    merge_sections_of_array(arr, NUM_THREADS, 1);

    /* incheie timing-ul*/
    gettimeofday(&end, NULL);
    time_spent = ((double) ((double) (end.tv_usec - start.tv_usec) / 1000000 +
                            (double) (end.tv_sec - start.tv_sec)));
    printf("Time taken for execution: %f seconds\n", time_spent);
    /* testeaza pentru a se asigura ca array-ul este sortat */
    /* test_array_is_in_order(arr); */
    return 0;
}

/* genereaza numere random intre valorile limita */
int generate_random_number(unsigned int lower_limit, unsigned int upper_limit) {
    return lower_limit + (upper_limit - lower_limit) * ((double)rand() / RAND_MAX);
}

/* imbina sectiunile de sortare local */
void merge_sections_of_array(int arr[], int number, int aggregation) {
    for(int i = 0; i < number; i = i + 2) {
        int left = i * (NUMBERS_PER_THREAD * aggregation);
        int right = ((i + 2) * NUMBERS_PER_THREAD * aggregation) - 1;
        int middle = left + (NUMBERS_PER_THREAD * aggregation) - 1;
        if (right >= LENGTH) {
            right = LENGTH - 1;
        }
        merge(arr, left, middle, right);
    }
    if (number / 2 >= 1) {
        merge_sections_of_array(arr, number / 2, aggregation * 2);
    }
}

/** assigneaza "de lucru" fiecarui thread pentru a realiza mergesort */
void *thread_merge_sort(void* arg)
{
    int thread_id = (long)arg;
    int left = thread_id * (NUMBERS_PER_THREAD);
    int right = (thread_id + 1) * (NUMBERS_PER_THREAD) - 1;
    if (thread_id == NUM_THREADS - 1) {
        right += OFFSET;
    }
    int middle = left + (right - left) / 2;
    if (left < right) {
        merge_sort(arr, left, right);
        merge_sort(arr, left + 1, right);
        merge(arr, left, middle, right);
    }
    return NULL;
}

/* testeaza ca array-ul sa fie sortat */
void test_array_is_in_order(int arr[]) {

    for (int i = 1; i < LENGTH; i ++) {
        if (arr[i] >= arr[i - 1]) {
            max = arr[i];
        } else {
            printf("Error. Out of order sequence: %d found\n", arr[i]);
            return;
        }
    }
    printf("Array is in sorted order\n");
}

/* realizeaza merge sort */
void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int middle = left + (right - left) / 2;
        merge_sort(arr, left, middle);
        merge_sort(arr, middle + 1, right);
        merge(arr, left, middle, right);
    }
}

/* functia merge */
void merge(int arr[], int left, int middle, int right) {
    int i = 0;
    int j = 0;
    int k = 0;
    int left_length = middle - left + 1;
    int right_length = right - middle;
    int left_array[left_length];
    int right_array[right_length];

    /* copiaza valorile in array-ul din stanga */
    for (int i = 0; i < left_length; i ++) {
        left_array[i] = arr[left + i];
    }

    /* copiaza valorile in array-ul din dreapta */
    for (int j = 0; j < right_length; j ++) {
        right_array[j] = arr[middle + 1 + j];
    }

    i = 0;
    j = 0;
    /** alege dintre array din stanga si dreapta si copiaza */
    while (i < left_length && j < right_length) {
        if (left_array[i] <= right_array[j]) {
            arr[left + k] = left_array[i];
            i ++;
        } else {
            arr[left + k] = right_array[j];
            j ++;
        }
        k ++;
    }

    /* copiaza valorile ramase in array */
    while (i < left_length) {
        arr[left + k] = left_array[i];
        k ++;
        i ++;
    }
    while (j < right_length) {
        arr[left + k] = right_array[j];
        k ++;
        j ++;
    }
}
c linux multithreading sorting
1个回答
2
投票

首先使 NUM_THREADS 一个 int,并删除依赖它的 globals 的初始化。

int NUM_THREADS;
int NUMBERS_PER_THREAD;
int OFFSET;

然后在 main读取线程数作为参数,并设置依赖的 globals。

if (argc >= 2) {
    NUM_THREADS = atoi(argv[1]);
    if (NUM_THREADS < 1) {
        printf("invalid thread count\n");
        exit(1);
    }

    NUMBERS_PER_THREAD = LENGTH / NUM_THREADS;
    OFFSET = LENGTH % NUM_THREADS;
} else {
    printf("must specify thread count\n");
    exit(1);
}

1
投票

你可以使用 atoi 函数,将命令行参数从字符串转换为整数。 即

if ( args == 1 ) {
    fprintf(stderr,"Missing argument: Number of threads\n");
    return 1;
}

int numberOfThreads = atoi(argv[1]);

之后,你将不得不动态地分配某些数组,这些数组的大小在编译时将不再是已知的。 比如说

pthread_t *threads = malloc(numberOfThreads*sizeof(pthread_t));

EDIT: 您也可以使用 alloca (也来自stdlib.h),而不是用 malloc 来分配栈上的数组。 这样做的一个好处是你不用再调用 free 当你完成后。

© www.soinside.com 2019 - 2024. All rights reserved.