Search code examples
c++openmp

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

On my class on university I need to create program in C++ which find all divisors of big number. I need to do it in several ways. One of them is to use OpenMP. So far i have this:

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();
    }
}

It take so long than use synchronized version (I know that its better algorithm but still too long):

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);
    }
}

I've tried to add schedule(static, n) (after shared) but program simply ended after reach to openmp section...

I'm using CLion with CMake and run it in Docker container:

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()

Dockerfile:

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"]

EDIT: Example number: 922337203685477580 tooked for sync version 22.69 but OpenMP more than 15 min...

Solution

  • Since it is your university work I give you hints not solution (code). The problem is with the OpenMP code is that numbers are shared, and write operations to containers and container adapters from more than one thread are not required by the C++ standard to be thread safe. So you have to add an openmp directive to protect it. Alternatively, you can create a used defined reduction in openmp.

    Why are you surprised that the 1st algorithm is so slow? That is the expected behaviour (it is not related to OpenMP, just to the algorithm). ps: I have changed the 1st algorithm and measured runtimes: A modified 1st algorithm using OpenMP (4 cores+hyperthreading) =1.4s, your second algorithm=15.5 s

    EDIT: More hints: