Стратегия блокировки программирования OpenMP в C++ для вложенных циклов

Question

Вчера я проверил свою программу эволюции ландшафта с большим набором данных (20 миллионов узлов), без сомнения, скорость работы была неприемлемой. Во время отладки я заметил, что это была определенная функция, которая замедляла всю систему. Поэтому я хотел бы добавить к нему многопоточность.

Однако сама функция представляет собой вложенный цикл с итераторами-указателями, и я считаю, что некоторые данные должны быть заблокированы во время процесса.

В основном то, что я пытался сделать, это вычислить вкладку каждого узла. Область вкладок, как предлагается по ее названию, является продуктом (суммой) всей области от восходящего узла.

Вот код, что две функции,

for(curnode = nodIter.FirstP(); nodIter.IsActive(); 
    curnode = nodIter.NextP()) //iterating thru a linked-list of pointers to active stream nodes (*IsActive* returns a bool value) 
{ 
    CalcDRArea(curnode, curnode->getVArea()); //calls another function and pass a pointer to current node as well as a value of its VArea 
} 

---

void CalcDRArea(NodeClass *curnode, double addedArea) 
{ 
    // As long as the current node is neither a boundary nor non-valid, add 
    // _addedArea_ to its total drainage area and advance to the next node downstream 

    while((curnode->ReachBoundary() == NonBoundary) && 
     (curnode->valid()!=Nonvalid)) 
    { 
     curnode->AddDrArea(addedArea); //*AddDrArea* is a simple inline function *`"drarea +=value"`* 

    curnode = curnode->getDownStreammNeighbor();  // *getDownstrmNbr()* reruns a pointer to the downstream node 
    } 

} 

Вот простая иллюстрация узлов и их текучий направление

A  B  C  D 
    \ |/  | 
E  F  G  H 
     |   | 
I  Q  K  L 
     |  /
M  N  O  P 
//letters are stream nodes and slashes are their flowing directions 

Мой план заключается в использовании OpenMP для реализации многопоточности в начале первой функции, для цикла , В идеале он будет создавать несколько потоков для вычисления каждого узла отдельно.

Однако, как показано на рисунке выше, процесс секвенции может обрабатывать потоки, как

A-> F -> Q -> N 
B-> F -> Q -> N 
C-> F -> Q -> N 

легко, но это, безусловно, вызовет проблему в многопоточных условиях.

Из того, что я только что прочитал из документа OpenMP, в вровень и замок может быть правильный способ сделать это, но все же я сейчас я совершенно невежественны и там еще может быть и другие потенциальные проблемы в пределах этой петли (например, gcc ver. из OpenMP не поддерживает «! =»).

==== Обновление ====== Существует два вида областей: vArea, который является областью каждого узла; и drArea, которая является суммой площади текущего узла и области от всех ее восходящих узлов. мне было интересно, если я могу изменить текущую функцию на это:

for(active node iterator） 
{ 
    if（currentNode.hasDownStreamNode） 
    { 
     downStreamNode.drArea += currentNode.vArea + currentNode.DrArea; 
    } 
    CurrentNode.drArea += currentNode.varea; 
} 

Answer 1

Перед тревожиться о параллельности, вы должны сначала выбрать лучший алгоритм. Хотя в этом случае на самом деле происходит с другим.

Вы хотите использовать динамическое программирующее решение в O (N) вместо вашего текущего подхода O (n^2). Интуиция проста, просто вызовите следующий метод на каждом из узлов листьев в дереве:

def compute_value(node): 
    if node.DrArea != 0: return node.DrArea 
    total = node.vArea 
    for n in node.upstream_nodes(): 
      total += compute_value(n) 
    node.DrArea = total 
    return node.DrArea 

Чтобы понять, почему это более эффективно, давайте взглянем на вашем примере. В настоящий момент вы добавляете значение A в F, Q и N. Затем вы делаете то же самое для B и для C. Таким образом, у вас есть 12 операций добавления. С другой стороны, рекурсивный метод сначала вычисляет значение для A, B и C, затем вычисляет F из уже известных значений A, B и C. Q вычисляется из F и так далее. Так что всего 8 добавлений. В основном каждый узел добавляет только значение ко всем своим дочерним элементам вместо того, чтобы проходить через все поддерево и добавлять только свое значение.

Для простого последовательного алгоритма вы можете продолжить и просто реализовать это итеративно, используя список узлов, чьи предшественники все были оценены (поэтому вместо того, чтобы начинать с листьев начинать с корневых узлов). Простейшая параллельная реализация здесь состоит в том, чтобы просто использовать параллельную операцию очереди и атомарного добавления, хотя использование обычной очереди на процессор и некоторая обработка работы, вероятно, были бы очень хорошей идеей на практике.