如何在C语言中用并行归约法实现带线程依赖的部分求和？

核心思路 #

你需要的是带显式依赖的树形归约，8个线程对应3层归约（2^3=8）。每个线程完成计算任务后，通知依赖它的后续线程继续执行。这里用pthread的互斥锁+条件变量实现线程间的等待/通知机制，全局数组存储原始数据与归约中间结果。

实现代码 #

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

#define THREAD_COUNT 8
#define ARRAY_SIZE 8  // 数组大小与线程数匹配，可按需调整

// 全局数组：存储原始数据和归约中间结果
int arr[ARRAY_SIZE] = {1, 2, 3, 4, 5, 6, 7, 8};
// 标记每个线程是否完成当前阶段任务
int thread_done[THREAD_COUNT] = {0};
// 同步用的互斥锁和条件变量
pthread_mutex_t mutex;
pthread_cond_t cond;

// 等待指定线程完成任务的辅助函数
void wait_for_thread(int target_thread) {
    pthread_mutex_lock(&mutex);
    while (!thread_done[target_thread]) {
        pthread_cond_wait(&cond, &mutex);
    }
    pthread_mutex_unlock(&mutex);
}

// 标记当前线程完成任务，并通知所有等待的线程
void mark_thread_done(int thread_id) {
    pthread_mutex_lock(&mutex);
    thread_done[thread_id] = 1;
    pthread_cond_broadcast(&cond);
    pthread_mutex_unlock(&mutex);
}

// 线程执行的归约任务
void* reduce_task(void* arg) {
    int thread_id = *(int*)arg;
    free(arg);

    // 第一步归约：线程0-3先执行，线程4-7等待对应前置线程
    if (thread_id < 4) {
        // 线程0-3：保留原始值（若数组更大，可改为计算分片局部和）
        printf("线程%d完成初始计算，值为%d\n", thread_id, arr[thread_id]);
        mark_thread_done(thread_id);
    } else {
        int wait_id = thread_id - 4;
        wait_for_thread(wait_id);
        arr[thread_id] += arr[wait_id];
        printf("线程%d完成第一步归约，值为%d（等待线程%d完成）\n", thread_id, arr[thread_id], wait_id);
        mark_thread_done(thread_id);
    }

    // 第二步归约：线程6等4，线程7等5
    if (thread_id == 6) {
        wait_for_thread(4);
        arr[thread_id] += arr[4];
        printf("线程%d完成第二步归约，值为%d（等待线程4完成）\n", thread_id, arr[thread_id]);
        mark_thread_done(thread_id);
    } else if (thread_id == 7) {
        wait_for_thread(5);
        arr[thread_id] += arr[5];
        printf("线程%d完成第二步归约，值为%d（等待线程5完成）\n", thread_id, arr[thread_id]);
        mark_thread_done(thread_id);
    }

    // 第三步归约：线程7等6
    if (thread_id == 7) {
        wait_for_thread(6);
        arr[thread_id] += arr[6];
        printf("线程%d完成第三步归约，最终总和为%d（等待线程6完成）\n", thread_id, arr[thread_id]);
        mark_thread_done(thread_id);
    }

    return NULL;
}

int main() {
    pthread_t threads[THREAD_COUNT];
    int i;

    // 初始化同步对象
    pthread_mutex_init(&mutex, NULL);
    pthread_cond_init(&cond, NULL);

    // 创建所有线程
    for (i = 0; i < THREAD_COUNT; i++) {
        int* thread_id = malloc(sizeof(int));
        *thread_id = i;
        pthread_create(&threads[i], NULL, reduce_task, thread_id);
    }

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

    // 输出最终数组
    printf("\n最终数组内容：");
    for (i = 0; i < ARRAY_SIZE; i++) {
        printf(" %d", arr[i]);
    }
    printf("\n");

    // 销毁同步对象
    pthread_mutex_destroy(&mutex);
    pthread_cond_destroy(&cond);

    return 0;
}

关键说明 #

• 同步逻辑：thread_done数组记录线程完成状态，wait_for_thread会阻塞直到目标线程完成，mark_thread_done标记完成并唤醒所有等待线程，确保依赖关系严格执行。
• 归约流程：完全匹配你指定的等待规则，从底层线程到顶层线程逐步累加，最终线程7得到总和。
• 编译运行：用gcc编译时需链接pthread库，命令为gcc -o reduce reduce.c -lpthread，运行./reduce即可查看输出。

扩展方向 #

• 如果数组规模远大于线程数，可让每个线程先计算自己负责分片的局部和，再进入归约阶段。
• 若需要调整归约结构，可提前定义依赖关系表，避免硬编码等待逻辑，提升灵活性。

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