如何实现线程负载均衡？非整除场景下矩阵行分配方案问询

当前已实现当N % Num_Threads == 0时，N*N矩阵的线程行分配逻辑（例如N=4、Num_Threads=2的场景），对应的C++代码如下：

for (int i = 0 ; i < num_threads; i++){
    if ( i == 0) { RANGE -> R1 = 0; RANGE -> R2 = n/num_threads; }
    else {
        RANGE -> R1 = RANGE -> R2  ; // 此前已定义包含R1、R2（代表起始行、结束行）的结构体
        RANGE -> R2 = RANGE -> R1 + n/num_threads ; }
        cout << "ThreadID= " << i << ", startRow= " << RANGE -> R1 << ", endRow= " << RANGE -> R2 << endl ;   
        pthread_create(&threads[i],NULL,Median,RANGE);
    }
}

输出结果：

ThreadID= 0 start_row = 0  , end_row = 2
ThreadID= 1 start_row = 2 , end_row=4

当N % Num_Threads != 0且Num_Threads < N时（例如N=5、Num_Threads=3，或N=101、Num_Threads=7的场景），需要调整分配逻辑以实现负载均衡：

核心逻辑是让前N%Num_Threads个线程多处理1行，剩余线程处理基础行数N/Num_Threads，这样所有线程的任务量差异最多为1行，达到最优均衡效果。

步骤说明 #

1. 计算基础处理行数：base_rows = N / Num_Threads
2. 计算剩余未分配行数：remainder = N % Num_Threads
3. 对每个线程i：
   • 若i < remainder，处理base_rows + 1行
   • 否则处理base_rows行
4. 逐线程计算连续的起始行（R1）和结束行（R2），确保覆盖所有矩阵行

修改后的代码示例 #

// 预计算基础参数
int base_rows = n / num_threads;
int remainder = n % num_threads;

for (int i = 0; i < num_threads; ++i) {
    // 为每个线程分配独立的Range结构体，避免多线程数据竞争
    Range* thread_range = new Range();
    
    // 计算起始行
    if (i == 0) {
        thread_range->R1 = 0;
    } else {
        if (i < remainder) {
            thread_range->R1 = i * (base_rows + 1);
        } else {
            thread_range->R1 = remainder * (base_rows + 1) + (i - remainder) * base_rows;
        }
    }
    
    // 计算结束行
    if (i < remainder) {
        thread_range->R2 = thread_range->R1 + base_rows + 1;
    } else {
        thread_range->R2 = thread_range->R1 + base_rows;
    }
    
    cout << "ThreadID= " << i << ", startRow= " << thread_range->R1 << ", endRow= " << thread_range->R2 << endl;
    pthread_create(&threads[i], NULL, Median, thread_range);
}

关键注意事项 #

• 避免共享内存：原代码中所有线程共用同一个RANGE指针，会引发数据竞争，必须为每个线程分配独立的Range实例（如通过new动态分配，或提前创建数组）
• 示例验证：以N=5、Num_Threads=3为例，分配结果为：
  • Thread 0：startRow=0，endRow=2（处理行0、1）
  • Thread 1：startRow=2，endRow=4（处理行2、3）
  • Thread 2：startRow=4，endRow=5（处理行4）
    总处理行数为2+2+1=5，完全覆盖且负载差异最小

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