尝试与 OpenMP 并行处理链表数据

Question

我正在尝试在 C++ 中与 OpenMP 并行处理链表数据。我对 OpenMP 很陌生，对 C++ 很生疏。我想做的是让几个线程打散链表，并输出特定范围内的节点数据。我不关心输出发生的顺序。如果我能让它正常工作，我想用对节点数据的一些实际处理来替换简单的输出。

我在 Internet 上找到了一些东西（包括本网站上的一些问题），根据我的发现，我拼凑了如下代码：

        #include <iostream>
        #include <omp.h>

        // various and sundry other stuff ...

        struct Node {
                int data;
                Node* next;
        };

        int main() {

            struct Node *newHead;
            struct Node *head = new Node;
            struct Node *currNode;
            int n;
            int tid;

            //create a bunch of Nodes in linked list with "data" ...

            // traverse the linked list:
            // examine data
            #pragma omp parallel private(tid)
            {
            currNode = head;
            tid=omp_get_thread_num();
            #pragma omp single
            {
            while (currNode) {
               #pragma omp task firstprivate(currNode)
               {
               cout << "Node data: " << currNode->data << " " << tid << "\n";
               } // end of pragma omp task
               currNode = currNode->next;
            } // end of while
            } //end of pragma omp single

            }  // end of pragma omp parallel


    // clean up etc. ...

    }  // end of main

所以我运行:

>: export OMP_NUM_THREADS=6
>: g++ -fopenmp ll_code.cpp
>: ./a.out

输出为：

Node data: 5 0
Node data: 10 0
Node data: 20 0
Node data: 30 0
Node data: 35 0
Node data: 40 0
Node data: 45 0
Node data: 50 0
Node data: 55 0
Node data: 60 0
Node data: 65 0
Node data: 70 0
Node data: 75 0

因此，tid 始终为 0。这意味着，除非我真的误解了什么，否则只有一个线程对链表执行任何操作，因此根本不会并行遍历链表。

当我删除 single 时，代码因段错误而失败。我尝试将一些变量移入和移出 OpenMP 指令范围，但没有任何变化。更改线程数无效。如何让它发挥作用？

第二个问题：一些网站说 firstprivate(currNode) 是必需的，而另一些网站说 currNode 默认是 firstprivate。谁是对的？

Answer 1

你当然可以使用多线程遍历链表，但实际上它会比只使用单线程慢。

原因是，要知道节点N != 0的地址，就必须知道节点N-1的地址。

假设现在您有 N 个线程，每个线程负责 "starting at i position"。上面的段落暗示线程 i 将取决于线程 i-1 的结果，而线程 i-1 又将取决于线程 i-2 的结果，依此类推。

无论如何，你最终得到的是一个串行遍历。但是现在，不仅是简单的 for，您还必须同步线程，这使得事情本质上变慢了。

但是，如果您正在尝试进行一些繁重的处理，而这些处理将从并行运行中获益，那么是的，您将采用正确的方法。您可以更改获取线程 ID 的方式：

#include <iostream>
#include <omp.h>

struct Node {
        int data;
        Node* next;
};

int main() {

    struct Node *head = new Node;
    struct Node *currNode = head;

    head->data = 0;
    for (int i=1;i<10;++i) {
        currNode->next = new Node;
        currNode = currNode->next;
        currNode->data = i;
    }

    // traverse the linked list:
    // examine data
    #pragma omp parallel
    {
        currNode = head;
        #pragma omp single
        {
            while (currNode) {
               #pragma omp task firstprivate(currNode)
               {
                   #pragma omp critical (cout)
                   std::cout << "Node data: " << currNode->data << " " << omp_get_thread_num() << "\n";
               }
               currNode = currNode->next;
            }
        }
    }
}

可能的输出：

Node data: 0 4
Node data: 6 4
Node data: 7 4
Node data: 8 4
Node data: 9 4
Node data: 1 3
Node data: 2 5
Node data: 3 2
Node data: 4 1
Node data: 5 0

See it live!

最后，对于更惯用的方法，请考虑使用 std::forward_list:

#include <forward_list>
#include <iostream>
#include <omp.h>

int main() {

    std::forward_list<int> list;
    for (int i=0;i<10;++i) list.push_front(i);

    #pragma omp parallel
    #pragma omp single
    for(auto data : list) {
       #pragma omp task firstprivate(data)
       #pragma omp critical (cout)
       std::cout << "Node data: " << data << " " << omp_get_thread_num() << "\n";
    }
}

尝试与 OpenMP 并行处理链表数据

Trying to process linked list data in parallel with OpenMP

c++

openmp

singly-linked-list

See it live!