使用 OpenMP 查找大数的所有除数的正确方法

Question

在我 class 上大学时，我需要用 C++ 创建程序来找到大数的所有除数。我需要通过多种方式来做到这一点。其中之一是使用 OpenMP。到目前为止我有这个：

void printDivisors(unsigned long long n) {
    stack<unsigned long long> numbers;
    #pragma omp parallel for shared(numbers)
    for (unsigned long long i = 1; i <= n; i++) {
        if (n % i == 0) {
            numbers.push(i);
        }
    }

    while( !numbers.empty() ){
        printf("%lld ", numbers.top());
        numbers.pop();
    }
}

它比使用同步版本花费的时间长（我知道它的算法更好，但仍然太长）：

void printDivisors(long long n)
{
    for (long long i = 1; i*i < n; i++) {
        if (n % i == 0)
            printf("%lld ", i);
    }
    for (long long i = sqrt(n); i >= 1; i--) {
        if (n % i == 0)
            printf("%lld ", n / i);
    }
}

我尝试添加 schedule(static, n)（在 shared 之后）但是程序 在到达 openmp 部分后就结束了 ...

我将 CLion 与 CMake 一起使用，运行它在 Docker 容器中：

cmake_minimum_required(VERSION 3.16.3)
project(projekt_dzielniki)

set(CMAKE_CXX_STANDARD 11)

OPTION (USE_OpenMP "Use OpenMP" ON)
add_executable(projekt_dzielniki_openmp openmp.cpp openmp.h)

FIND_PACKAGE( OpenMP REQUIRED)
if(OPENMP_FOUND)
    message("OPENMP FOUND")
    set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} ${OpenMP_C_FLAGS}")
    set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${OpenMP_CXX_FLAGS}")
    set(CMAKE_EXE_LINKER_FLAGS "${CMAKE_EXE_LINKER_FLAGS} ${OpenMP_EXE_LINKER_FLAGS}")
endif()

Docker文件:

FROM ubuntu:20.04

RUN DEBIAN_FRONTEND="noninteractive" apt-get update && apt-get -y install tzdata

RUN apt-get update \
  && apt-get install -y ssh \
      build-essential \
      gcc \
      g++
      gdb \
      clang \
      cmake \
      rsync \
      tar \
      python \
  && apt-get clean

RUN ( \
    echo 'LogLevel DEBUG2'; \
    echo 'PermitRootLogin yes'; \
    echo 'PasswordAuthentication yes'; \
    echo 'Subsystem sftp /usr/lib/openssh/sftp-server'; \
  ) > /etc/ssh/sshd_config_test_clion \
  && mkdir /run/sshd

RUN useradd -m user \
  && yes password | passwd user

RUN usermod -s /bin/bash user

CMD ["/usr/sbin/sshd", "-D", "-e", "-f", "/etc/ssh/sshd_config_test_clion"]

编辑：示例编号：922337203685477580 同步版本 22.69 但 OpenMP 超过 15 分钟...

Answer 1

因为这是你的大学作业，所以我给你提示而不是解决方案（代码）。 OpenMP 代码的问题在于 numbers 是共享的，并且 C++ 标准不要求来自多个线程的容器和容器适配器的写入操作是线程安全的。所以你必须添加一个 openmp 指令来保护它。或者，您可以在 openmp 中创建使用定义的缩减。

为什么您对第一个算法这么慢感到惊讶？这是预期的行为（它与 OpenMP 无关，仅与算法相关）。 ps：我更改了第一个算法并测量了运行时间：使用 OpenMP（4 核 + 超线程）修改的第一个算法 =1.4s，你的第二个算法 =15.5s

编辑：更多提示：

How to deal with data race in OpenMP?
关于不同的算法：All divisors of a number using its prime factorization, Find divisors of any number

使用 OpenMP 查找大数的所有除数的正确方法

Proper way to use OpenMP in find all divisors of big number

c++

openmp