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

[Anonymous]

Я пытаюсь многопоточно прочитать префикс Trie без замков или мутекс. В моем случае все строки имеют одинаковую длину, поэтому я подумал, что могу справедливо распределить работу. < /P>
Идея: < /h4>

[*] Если у нас есть n потоки, каждый поток вставляет 1/n строки в Trie.
После вставки своей части поток передает Работайте со следующим потоком, который продолжается со следующим 1/N строки. />> > Проблема, с которой я сталкиваюсь: < /h4>
Несмотря на то, что строки справедливо разделены, мой кольцевой буфер быстро заполняется для некоторых потоков, в то время как другие кажутся недостаточно используемыми.
Если кольцо Буфер становится полным, я получаю бесконечную петлю. от. < /p>
Вопросы: < /h4>
откуда происходит дисбаланс? Если работа равномерно разделена, почему некоторые потоки отстают? Или есть лучший способ структурировать это?
Любые идеи или альтернативные стратегии будут оценены! Буфер не нужен буфер. avg - это число Chars, каждый поток вставляет в Trie, а узел - это узел, откуда мы вставляем строку. По-видимому, потоки заполняют дорогу быстрее кольцевой буфер, затем следующий поток может обработать.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