Многопользовательский префикс Trie со стратегией прохождения-решает проблемы дисбаланса? ⇐ C++

[Anonymous]

Я пытаюсь многопоточно прочитать префикс Trie без замков или мутекс. В моем случае все строки имеют одинаковую длину, поэтому я подумал, что смогу справиться с работой. n потоков, каждый поток вставляет 1/N строки в Trie.
-После вставки его детали поток передает работу в следующий поток, который продолжается со следующим 1/N строки.
-это продолжается до тех пор, пока последний поток не завершит вставку строки. Проблема, с которой я сталкиваюсь:
Несмотря на то, что строки справедливо разделены, мой кольцевой буфер быстро заполняется для некоторых потоков, в то время как другие кажутся недооцененными.
Если буфер кольца заполняется, я в конечном итоге получаю бесконечную петлю.
Теоретически, каждая поток должен занять примерно столько же времени, чтобы обработать свою часть, поэтому я не понимаю, откуда исходит дисбаланс.
Вопросы:
откуда истекает дисбаланс? Если работа равномерно разделена, почему некоторые потоки отстают?
OpenMP даже хорошим выбором здесь? Или есть лучший способ структурировать это?
Любые идеи или альтернативные стратегии будут оценены! Буфер не нужен буфер. avg - это число Chars, каждый поток вставляет в Trie, а узел - это узел, откуда мы вставляем строку. По -видимому, потоки заполняют дорогу быстрее кольцо, затем следующий поток может обработать. < /P>
std::vector queues(numThreads - 1);

#pragma omp parallel
{
int threadId = omp_get_thread_num();

for (int i = 0; i < castRelation.size(); i++) {
if (threadId == 0) {
TrieNode* node = nullptr;
const char* note = castRelation.note;

node = &myTrie.insertTree(note, node, avg);

note=note+avg;
if (numThreads > 1) {
queues[0].push_back(node,note);
}
else {
node->addIndex(i);
}
}
else {

while (queues[threadId - 1].empty()) {
std::this_thread::yield();
}

std::unique_ptr myTask = queues[threadId - 1].pop();

TrieNode* node = &myTrie.insertTree(myTask->str, myTask->node, avg);
if (threadId < numThreads - 1) {
queues[threadId].push_back(node,myTask->str+avg);
}
else {
node->addIndex(i);
}
}
}

}


Подробнее здесь: https://stackoverflow.com/questions/794 ... nce-issues