时间戳

首页 > 解决方案 > C中快速排序的并行化

c - C中快速排序的并行化

问题描述

对于一个作业，我得到了一个用 C 语言编写的快速排序程序的完整功能顺序版本，但现在我需要使用线程通过并行化来加速它。下面修改后的程序正在排序并且正在使用线程（使用 >100% CPU），但是现在按顺序执行时比以前需要更长的时间。

该程序的工作方式是，当第 8 个线程终止时，程序现在应该继续按顺序执行程序的其余部分。

我知道这可能不是使用线程进行优化时的可选方式，但这就是该程序应该如何工作的方式。我想这与 . 有一些关系pthread_join，但我试图移动它，但这没有任何区别，有时甚至更糟。

*注意，我确实在这里包含了数组的初始化，因为它不相关。

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define THREADS 8
#define KILO (1024)
#define MEGA (1024*1024) //1 048 576
#define MAX_ITEMS (64 *MEGA) //67 108 864
#define swap(v, a, b) {unsigned tmp; tmp=v[a]; v[a]=v[b]; v[b]=tmp;}

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
static int *v; 
int global_thread = 1; //Starts at 1, because the thread from main is the first

struct threadArgs 
{
    int low;
    int high;
};

static int partition(int *v, int low, int high, int pivot_index)
{
    if (pivot_index != low)
        swap(v, low, pivot_index);

    pivot_index = low;
    low++;

    while (low <= high) 
    {
        if (v[low] <= v[pivot_index]) 
            low++;
        else if (v[high] > v[pivot_index])
            high--;
        else
            swap(v, low, high);
    }
    
    if (high != pivot_index)
        swap(v, pivot_index, high);

    return high;
}

void* quick_sort(void* arguments)
{
    struct threadArgs* parent = (struct threadArgs*) arguments;
    pthread_t child;
    
    struct threadArgs* child_thread;
    child_thread =  malloc(sizeof(struct threadArgs));    
    
    int pivot_index;

    int low = parent->low;
    int high = parent->high;

    if (low >= high)
        return NULL;

    pivot_index = (low + high) / 2;
    pivot_index = partition(v, low, high, pivot_index);
    
    if(global_thread < THREADS) //should only create 7 new threads, 1 is already from main
    {
        if(pivot_index < high) //child: right side
        {
            child_thread->low = pivot_index +1;
            child_thread->high = high;
            pthread_mutex_lock(&lock);
            global_thread++;
            pthread_mutex_unlock(&lock);
            
            pthread_create(&child, NULL, quick_sort, (void*) child_thread);
        }
        if(low < pivot_index) //parent: left side,
        {
            parent->low = low;
            parent->high = pivot_index - 1;
            quick_sort((void*) parent);
        }
        pthread_join(child, NULL);
    }
    else
    {
        if (low < pivot_index) //left side sequential
        {
            parent->low = low;
            parent->high = pivot_index - 1;
            quick_sort((void*) parent);
        }
        if (pivot_index < high) //right side sequential
        {
            parent->low = pivot_index +1;
            parent->high = high;
            quick_sort((void*) parent);
        }
    }
    return NULL;
}

int main(int argc, char **argv)
{
    init_array();

    struct threadArgs* args; // main thread
    args =  malloc(sizeof(struct threadArgs));
    args->low = 0;
    args->high = MAX_ITEMS - 1;

    quick_sort((void *)args);
    pthread_mutex_destroy(&lock);
    free(args);
    return 0;
}

标签： cmultithreadingparallel-processingpthreadsquicksort

解决方案

您的代码存在严重的内存泄漏：每次调用都会quick_sort()为子线程的参数分配内存，即使它最终没有启动新的子线程，并且没有任何内存被释放。 malloc()相对昂贵，并且根据您的实现，它可能会获得锁，从而产生瓶颈。

您的代码存在数据竞争：在互斥锁或其他同步对象的保护之外quick_sort()读取共享变量global_threads，并且该变量也被您的某些线程修改。因此，产生的行为是未定义的。

您的代码有一个缺陷，即global_thread < THREADS您的函数分支quick_sort()仅有条件地启动一个新线程，但无条件地尝试加入一个新线程。如果没有启动子线程，则连接尝试将由于读取child不确定的变量值而产生未定义的行为。然而，在实践中使用随机数据不太可能发生这种情况。

建议：

  1. 移动malloc()调用，以便仅在实际要创建新线程的情况下进行分配。由于每次分配的数量很小并且分配的数量也会很小，您可能可以继续允许该内存泄漏，但最好在加入孩子之后释放它。

  2. 更改决定是否启动子线程的策略。例如，跟踪递归深度，并仅在较浅的深度（两个或三个级别）启动一个新子级。然后，您不需要共享变量或互斥锁，只需struct threadArgs.

  3. 确保不要在尚未启动子线程时尝试加入子线程。

实现留作练习，但我自己对这些修复的实现产生了显着的单线程性能改进，并且通过添加更多线程表现出合理（但不是很好）的加速：两个线程的加速大约 30%，略高于 50%有四个。

推荐阅读