n<1e6物理模拟嵌套循环多线程工作负载分配最优方案咨询

现有方案的缺陷 #

你当前构思的两种方案都存在明显的性能损耗：

• 方案1：每个任务都需要执行整数平方根计算，哪怕是二分实现的sqrt，单任务开销也远高于引力计算的前置开销，且逐任务拉取的原子操作粒度太小，多线程下缓存同步竞争非常严重，n越大额外开销占比越高。
• 方案2：总循环次数是实际需要的2倍，有一半的循环会因为i >= j被直接跳过，浪费了近一半的计算资源，同样存在原子操作粒度过小的问题。

最优方案：按i维度批量拆分任务 #

最优思路是将连续的多个i打包为一个任务块，每个线程每次拉取一整块任务执行，既完全避免了x到(i,j)的坐标转换开销，又大幅摊薄了原子操作的同步开销，同时完全没有无效计算。

实现代码 #

const int BATCH_SIZE = 32; // 可根据实际硬件测试调整，一般取16~128均可获得较好效果
std::atomic<int> current_i = 0;
int n = 元素总数;

// 线程执行函数
void worker() {
    while (true) {
        int i_start = current_i.fetch_add(BATCH_SIZE);
        // 所有i都已分配完毕，退出
        if (i_start >= n - 1) break;
        int i_end = std::min(i_start + BATCH_SIZE, n - 1);
        // 执行当前块内的所有(i,j)对计算
        for (int i = i_start; i < i_end; ++i) {
            for (int j = i + 1; j < n; ++j) {
                dostuff(i, j);
            }
        }
    }
}

附加优化建议 #

1. 避免多线程写冲突开销：给每个线程分配私有accelerations数组，线程处理完所有分配给自己的任务后，再将私有数组合并到全局accelerations数组，可完全避免多线程同时写同一个加速度变量导致的缓存行失效问题，性能提升可超过30%。
2. 若n接近1e6，可调整BATCH_SIZE为线程数的1/100左右，保证负载均衡的同时进一步降低原子操作开销。

方案对比 #

该方案相比你原有两种方案的性能提升非常明显：

• 相比方案1：省去了所有任务的平方根计算开销，原子操作次数降低2个数量级以上。
• 相比方案2：完全没有无效的循环判断，总计算量直接减少一半，原子操作次数同样降低2个数量级以上。

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