c++ - openMP を使用した C++ マルチスレッド: ローカライズされた変数にもかかわらずパフォーマンスが低い (偽共有?)

Question

かなり奇妙な openMP の問題に遭遇しました。

タスクは、文字列のベクトルを取得し、各要素をそれに含まれる k-Mer (長さ k のすべての含まれる部分文字列) に分割することです。k-Merification 手順は要素ごとに独立して行われるため、これはベクトルの要素に沿って自明に並列化する必要があります。結果をマップ/セット STL データ構造 ( ) に格納したいので、そのstd::map<long long, std::map<std::string, std::set<unsigned int> > > local_forReturnためにスレッド ローカル変数を割り当てます。

ただし、達成された並列化の動作は驚くほど悪いです。Linux の top は、40 コアのマシンで 40 スレッドで実行しているにもかかわらず、CPU 使用率が ~ 200% であることを示しています。(そして、#omp criticalセクションがボトルネックではないことをテストしました)。

ローカライズされたマップ/セット STL クラスに含まれる実際のデータが最終的にヒープになるため、これは偽共有に関連している可能性があると私は考えています。ただし、直感をテストする方法や、STL コンストラクトの偽共有を減らす方法についてはわかりません (これが問題である場合)。どんなアイデアでも大歓迎です！

完全なコード:

#include <string>
#include <assert.h>
#include <set>
#include <map>
#include <vector>
#include <omp.h>
#include <iostream>

int threads = 40;
int k = 31;

std::string generateRandomSequence(int length);
char randomNucleotide();
std::vector<std::string> partitionStringIntokMers(std::string str, int k);

int main(int argc, char *argv[])
{
    // generate test data
    std::vector<std::string> requiredSEQ;
    for(unsigned int i = 0; i < 10000; i++)
    {
        std::string seq = generateRandomSequence(20000);
        requiredSEQ.push_back(seq);
    }

    // this variable will contain the final result
    std::map<long long, std::map<std::string, std::map<unsigned int, int> > > forReturn;

    omp_set_num_threads(threads);

    std::cerr << "Data generated, now start parallel processing\n" << std::flush;

    // split workload (ie requiredSEQ) according to number of threads
    long long max_i = requiredSEQ.size() - 1;
    long long chunk_size = max_i / threads;
    #pragma omp parallel
    {
        assert(omp_get_num_threads() == threads);
        long long thisThread = omp_get_thread_num();
        long long firstPair = thisThread * chunk_size;
        long long lastPair = (thisThread+1) * chunk_size - 1;
        if((thisThread == (threads-1)) && (lastPair < max_i))
        {
            lastPair = max_i;
        }

        std::map<long long, std::map<std::string, std::map<unsigned int, int> > > local_forReturn;

        for(long long seqI = firstPair; seqI <= lastPair; seqI++)
        {
            const std::string& SEQ_sequence = requiredSEQ.at(seqI);

            const std::vector<std::string> kMersInSegment = partitionStringIntokMers(SEQ_sequence, k);
            for(unsigned int kMerI = 0; kMerI < kMersInSegment.size(); kMerI++)
            {
                const std::string& kMerSeq = kMersInSegment.at(kMerI);
                local_forReturn[seqI][kMerSeq][kMerI]++;
            }   
        }

        #pragma omp critical
        {
            forReturn.insert(local_forReturn.begin(), local_forReturn.end());
        }
    }

    return 0;   
}

std::string generateRandomSequence(int length)
{
    std::string forReturn;
    forReturn.resize(length);
    for(int i = 0; i < length; i++)
    {
        forReturn.at(i) = randomNucleotide();
    }
    return forReturn;
}

char randomNucleotide()
{
    char nucleotides[4] = {'A', 'C', 'G', 'T'};
    int n = rand() % 4;
    assert((n >= 0) && (n <= 3));
    return nucleotides[n];
}


std::vector<std::string> partitionStringIntokMers(std::string str, int k)
{
    std::vector<std::string> forReturn;
    if((int)str.length() >= k)
    {
        forReturn.resize((str.length() - k)+1); 
        for(int i = 0; i <= (int)(str.length() - k); i++)
        {
            std::string kMer = str.substr(i, k);
            assert((int)kMer.length() == k);
            forReturn.at(i) = kMer;
        }
    }
    return forReturn;
}