如何加速带有ordered子句的OpenMP并行for循环？

我尝试用OpenMP并行化一段串行C++代码的for循环，核心难点在于正确处理linkingVarVals这个共享数据结构。为了保证结果和串行代码一致，我用了OpenMP的ordered子句，代码能正常运行，但并行版本反而比串行慢，推测是ordered带来的性能开销。请问这个场景下有什么办法加速OpenMP实现？

相关代码片段：

typedef tuple<int,int,int> key3;
struct key3_hash : public std::unary_function<key3, std::size_t> {
    std::size_t operator()(const key3& k) const {
        return std::get<0>(k) ^ std::get<1>(k) ^ std::get<2>(k);
    }
};
struct key3_equal : public std::binary_function<key3, key3, bool> {
    bool operator()(const key3& v0, const key3& v1) const {
        return (std::get<0>(v0) == std::get<0>(v1) && std::get<1>(v0) == std::get<1>(v1) && std::get<2>(v0) == std::get<2>(v1));
    }
};
typedef tuple<int,int> key2;
struct key2_hash : public std::unary_function<key2, std::size_t> {
    std::size_t operator()(const key2& k) const {
        return std::get<0>(k) ^ std::get<1>(k);
    }
};
struct key2_equal : public std::binary_function<key2, key2, bool> {
    bool operator()(const key2& v0, const key2& v1) const {
        return (std::get<0>(v0) == std::get<0>(v1) && std::get<1>(v0) == std::get<1>(v1));
    }
};
typedef unordered_map<key3, double, key3_hash, key3_equal> CoeffMap;
typedef unordered_map<key3, GRBVar, key3_hash, key3_equal> VarMap;
typedef unordered_map<key2, double, key2_hash, key2_equal> ValueMap;
typedef unordered_map<key3, GRBConstr, key3_hash, key3_equal> ConstrMap;
void myalgorithm(GRBModel model, const vector<GRBModel*>& submips, const set<string>& linkingvarnames, const map<string,int>& nametoidxmap, const map<int,string>& idxtonamemap, const map<int,set<int> >& linkvaridxtoblock, const map<int,set<int> >& blocktolinkvaridx) {
    size_t nBlocks = submips.size();
    size_t nVars = model.get(GRB_IntAttr_NumVars);
    CoeffMap slackPosCoeffs;
    CoeffMap slackNegCoeffs;
    VarMap slackPosVars;
    VarMap slackNegVars;
    ValueMap linkingVarVals;
    ConstrMap couplingCons;
    // the following code shows the connection between
    // submips[block] and couplingCons
    for (size_t block = 0; block < nBlocks; ++block) {
        set<int> linkVarsInBlock = blocktolinkvaridx.at(block);
        for (set<int>::const_iterator it = linkVarsInBlock.begin(), ei = linkVarsInBlock.end(); it != ei; ++it) {
            int linkVarIdx = *it;
            set<int> blocksContainingLinkVar = linkvaridxtoblock.at(linkVarIdx);
            for (set<int>::const_iterator jt = blocksContainingLinkVar.begin(), ej = blocksContainingLinkVar.end(); jt != ej; ++jt) {
                int blockContainingLinkVar = *jt;
                if (blockContainingLinkVar != block) {
                    auto idx2 = make_tuple(blockContainingLinkVar, linkVarIdx);
                    auto idx3 = make_tuple(block, blockContainingLinkVar, linkVarIdx);
                    stringstream constrName;
                    constrName << idxtonamemap.at(linkVarIdx) << "_Coupling_Block_" << blockContainingLinkVar;
                    couplingCons[idx3] = submips[block]->addConstr(submips[block]->getVarByName(idxtonamemap.at(linkVarIdx)) + slackPosVars.at(idx3) - slackNegVars.at(idx3) == linkingVarVals.at(idx2), constrName.str());
                }
            }
        }
        submips[block]->update();
    }
#if defined(_OPENMP)
    // set number of openmp threads
    unsigned int numprocs = omp_get_num_procs();
    cout << "=== NumProcessors " << numprocs << endl;
    unsigned int numthreads = numprocs > 1 ? numprocs : std::min((int)nBlocks, 4);
    omp_set_num_threads(numthreads);
    cout << "=== OpenMP threads " << numthreads << endl;
#endif
    double newRHS;
#pragma omp parallel for ordered schedule(dynamic) // 1. loop
    for (size_t block = 0; block < nBlocks; ++block) {
        set<int> linkVarsInBlock = blocktolinkvaridx.at(block);
        // 2. loop
        for (set<int>::const_iterator it = linkVarsInBlock.begin(), ei = linkVarsInBlock.end(); it != ei; ++it) {
            int linkVarIdx = *it;
            set<int> blocksContainingLinkVar = linkvaridxtoblock.at(linkVarIdx);
            // 3. loop
            for (set<int>::const_iterator jt = blocksContainingLinkVar.begin(), ej = blocksContainingLinkVar.end(); jt != ej; ++jt) {
                int blockContainingLinkVar = *jt;
                if (blockContainingLinkVar != block) {
                    auto idx3 = make_tuple(block, blockContainingLinkVar, linkVarIdx);
                    auto idx2 = make_tuple(blockContainingLinkVar, linkVarIdx);
                    GRBConstr c = couplingCons.at(idx3);
                    string name = c.get(GRB_StringAttr_ConstrName);
                    double oldRHS = c.get(GRB_DoubleAttr_RHS);
#pragma omp ordered
                    {
                        newRHS = linkingVarVals.at(idx2);
                    }
                    c.set(GRB_DoubleAttr_RHS, newRHS);
                    slackPosVars.at(idx3).set(GRB_DoubleAttr_Obj, slackPosCoeffs.at(idx3));
                    slackNegVars.at(idx3).set(GRB_DoubleAttr_Obj, slackNegCoeffs.at(idx3));
                }
            }
        }
    }
}

核心问题分析 #

你现在的ordered子句相当于给所有线程加了一个串行执行的枷锁——每次只有一个线程能进入ordered块读取linkingVarVals，这直接把并行循环打回了串行状态，性能不下降才怪。而且从代码逻辑看，linkingVarVals在整个并行循环过程中是只读的，完全不需要这种严格的同步保护！

优化方案 #

1. 立刻移除不必要的ordered子句（优先级最高）

只要linkingVarVals在并行循环期间没有被任何线程修改，所有线程都可以安全地并发读取它。直接删掉#pragma omp ordered块，同时把外层循环的ordered关键字去掉：

#pragma omp parallel for schedule(dynamic) // 移除ordered关键字
for (size_t block = 0; block < nBlocks; ++block) {
    // ... 内部循环代码 ...
    // 直接读取，不需要ordered保护
    newRHS = linkingVarVals.at(idx2);
    // ... 后续代码 ...
}

这个改动应该能立刻让并行版本的性能追上甚至超过串行。

2. 优化数据结构，减少哈希表访问开销

你现在用的unordered_map每次at()调用都要计算哈希、遍历桶，在循环里反复调用会累积不小的开销。可以做两个优化：

• 把哈希表转成连续数组：如果blockContainingLinkVar和linkVarIdx的取值范围不大，提前把linkingVarVals的内容复制到二维vector里，直接通过索引访问，速度比哈希表快得多：

  // 并行循环前预处理
  size_t maxLinkVarIdx = 0;
  for (const auto& pair : linkingVarVals) {
      maxLinkVarIdx = max(maxLinkVarIdx, (size_t)get<1>(pair.first));
  }
  vector<vector<double>> linkingVarVals_arr(nBlocks, vector<double>(maxLinkVarIdx + 1));
  for (const auto& pair : linkingVarVals) {
      int block = get<0>(pair.first);
      int varIdx = get<1>(pair.first);
      linkingVarVals_arr[block][varIdx] = pair.second;
  }
  
  // 并行循环里直接访问
  newRHS = linkingVarVals_arr[blockContainingLinkVar][linkVarIdx];
  

• 线程本地缓存：如果某些idx2的值会被同一个线程多次访问，可以把这些值缓存到线程本地变量里，减少重复的哈希表查询。

3. 调整OpenMP调度策略

你当前用的schedule(dynamic)适合任务量差异很大的场景，如果每个block的计算量比较均匀，换成schedule(static)能减少调度开销；如果任务量差异大，试试schedule(guided)，它会动态调整每个线程的任务块大小，平衡负载。

4. 确认Gurobi API的线程安全性

并行循环里你调用了GRBConstr::set()和GRBVar::set()，要确认Gurobi的这些方法是不是线程安全的。如果每个线程只操作属于自己block的submips实例，通常是安全的（因为每个submips[block]是独立的模型对象），但如果有跨线程的模型操作，可能需要针对性加锁（尽量避免，锁会带来额外开销）。

总结 #

最优先的是移除不必要的ordered子句，然后优化数据结构减少哈希访问开销，最后根据任务特性调整调度策略。这些改动应该能让你的OpenMP并行版本性能明显提升。

内容的提问来源于stack exchange，提问作者Dieter W.