如何用PThreads高效并行化奇偶换位排序算法？

核心优化思路 #

原 naive 实现为每个相邻比较对创建线程，大数组下线程创建/销毁的开销远大于并行收益。要固定线程数（比如4个，匹配CPU核心数），核心是将每一轮的比较任务分片到固定线程中：

• 奇数轮（处理索引0-1、2-3...的相邻对）：把所有偶数索引开头的比较对平均分配给4个线程，每个线程负责间隔的若干组比较
• 偶数轮（处理索引1-2、3-4...的相邻对）：同理拆分奇数索引开头的比较对到4个线程
• 用线程屏障（pthread_barrier_t）同步每一轮的奇偶步骤，确保所有线程完成当前步后再进入下一步，保证排序逻辑正确性

4线程PThreads实现代码 #

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

#define THREAD_COUNT 4

typedef struct {
    int* arr;
    int arr_size;
    int thread_id;
    pthread_barrier_t* barrier;
} ThreadData;

// 交换元素
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 线程执行函数
void* oddEvenSortThread(void* arg) {
    ThreadData* data = (ThreadData*)arg;
    int* arr = data->arr;
    int arr_size = data->arr_size;
    int tid = data->thread_id;
    pthread_barrier_t* barrier = data->barrier;

    for (int k = 0; k < arr_size; k++) {
        // 奇数轮：处理偶数索引开头的相邻对（0-1, 2-3...）
        if (k % 2 == 0) {
            for (int i = tid; i < arr_size - 1; i += THREAD_COUNT * 2) {
                if (i % 2 == 0 && arr[i] > arr[i + 1]) {
                    swap(&arr[i], &arr[i + 1]);
                }
            }
        } 
        // 偶数轮：处理奇数索引开头的相邻对（1-2, 3-4...）
        else {
            for (int i = tid + 1; i < arr_size - 1; i += THREAD_COUNT * 2) {
                if (i % 2 == 1 && arr[i] > arr[i + 1]) {
                    swap(&arr[i], &arr[i + 1]);
                }
            }
        }
        // 等待所有线程完成当前轮次的比较交换
        pthread_barrier_wait(barrier);
    }

    pthread_exit(NULL);
}

// 并行奇偶排序入口函数
void parallelOddEvenSort(int* arr, int arr_size) {
    pthread_t threads[THREAD_COUNT];
    ThreadData thread_data[THREAD_COUNT];
    pthread_barrier_t barrier;

    // 初始化线程屏障
    pthread_barrier_init(&barrier, NULL, THREAD_COUNT);

    // 创建线程并分配任务
    for (int i = 0; i < THREAD_COUNT; i++) {
        thread_data[i].arr = arr;
        thread_data[i].arr_size = arr_size;
        thread_data[i].thread_id = i;
        thread_data[i].barrier = &barrier;
        pthread_create(&threads[i], NULL, oddEvenSortThread, &thread_data[i]);
    }

    // 等待所有线程执行完成
    for (int i = 0; i < THREAD_COUNT; i++) {
        pthread_join(threads[i], NULL);
    }

    // 销毁屏障
    pthread_barrier_destroy(&barrier);
}

// 测试用例
int main() {
    int arr[1000];
    // 填充随机测试数据
    for (int i = 0; i < 1000; i++) {
        arr[i] = rand() % 10000;
    }

    parallelOddEvenSort(arr, 1000);

    // 验证排序结果（可选）
    for (int i = 0; i < 999; i++) {
        if (arr[i] > arr[i + 1]) {
            printf("排序失败\n");
            return 1;
        }
    }
    printf("排序成功\n");
    return 0;
}

代码说明 #

• 线程通过ThreadData结构体共享数组、线程屏障等核心资源
• 每一轮奇偶步，线程按THREAD_COUNT * 2的步长遍历分配给自己的比较对，避免任务冲突
• 线程屏障保证所有线程同步完成当前轮次，确保奇偶排序的全局逻辑正确

并行计算学习资料推荐 #

• 《并行程序设计导论》：从基础概念到PThreads、OpenMP等主流并行API都有详细讲解，适合入门
• 《多核与GPU编程：工具、方法及实践》：侧重实际编程技巧，包含大量并行算法的实现案例
• MIT 6.172 并行计算机体系结构与编程：经典公开课，涵盖并行架构、算法优化等核心内容，适合系统学习

内容的提问来源于stack exchange，提问作者jakeprog123