Можно ли использовать незанятые потоки в OpenMP / Cython для распараллеливания оставшейся части рабочего блока? - PullRequest
Новая
       57

Можно ли использовать незанятые потоки в OpenMP / Cython для распараллеливания оставшейся части рабочего блока?

2 голосов
/ 09 октября 2019

Я новичок в OpenMP и использую его для распараллеливания цикла for (если быть точным, я использую prange в Cython).

Однако операции очень неравномерны, и, как результат,Есть довольно много незанятых потоков, пока один блок цикла for не будет завершен.

Я хотел знать, есть ли способ получить доступ к незанятым потокам, чтобы я мог использовать их для распараллеливания операций узкого места.

1 Ответ

2 голосов
/ 09 октября 2019

Этот вопрос сводится к вопросу о точном планировании задач, что довольно сложно для общего случая, поэтому, как правило, возникает проблема эвристики.

OpenMP предлагает различные эвристики для планирования, которые можно выбратьчерез schedule -аргумент prange ( документация ).

Давайте рассмотрим следующий пример: 

%%cython -c=/openmp --link-args=/openmp
cdef double calc(int n) nogil:
    cdef double d=0.0
    cdef int i
    for i in range(n):
        d+=0.1*i*n
    return d

def single_sum(int n):
    cdef int i
    cdef double sum = 0.0
    for i in range(n):
        sum += calc(i)
    return sum

Оценка calc занимает O(n), поскольку компилятор, соответствующий стандарту IEEE 754. Не может оптимизировать цикл for.

Теперь давайте заменим range на prange: 

...
from cython.parallel import prange   
def default_psum(int n):
    cdef int i
    cdef double sum = 0.0
    for i in prange(n, nogil=True, num_threads=2):
        sum += calc(i)
    return sum

Я выбрал ограничениеколичество нитей до 2, чтобы сделать эффект более драматичным. Теперь, сравнивая время выполнения, мы видим: 

N=4*10**4
%timeit single_sum(N) #no parallelization
# 991 ms ± 2.37 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit default_psum(N) #parallelization
# 751 ms ± 11.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

не так много улучшений, как хотелось бы (т.е. мы хотели бы ускорить 2)!

Это деталь реализации OpenMP-поставщик, расписание которого выбирается, если оно не задано явно, но, скорее всего, оно будет "static" без определения chunksize. В этом случае диапазон уменьшается вдвое, и один поток становится первой, быстрой половиной, а второй - вторым, где почти вся работа должна быть выполнена - поэтому большая часть работы в конце не распараллеливается.

Лучшая стратегия для достижения лучшего баланса - дать i=0 первому потоку, i=1 второму, i=2 снова первому и так далее. Это может быть достигнуто для "static" -сканирования путем установки chunksize в 1: 

def static_psum1(int n):
    cdef int i
    cdef double sum = 0.0
    for i in prange(n, nogil=True, num_threads=2, schedule="static", chunksize=1):
        sum += calc(i)
    return sum

, мы почти достигаем максимально возможного ускорения 2: 

%timeit static_psum1(N)
# 511 ms ± 13.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

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

Вот некоторые временные характеристики для приведенного выше примера для разных стратегий планирования и разного количества потоков: 

(schedule,chunksize)        N=2                  N=8
single-threaded            991 ms               991 ms
(default)                  751 ms               265 ms
static                     757 ms               274 ms
static,1                   511 ms               197 ms
static,10                  512 ms               166 ms
dynamic,1                  509 ms               158 ms
dynamic,10                 509 ms               156 ms
guided                     508 ms               158 ms

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

Если есть задача, которая занимает 90% времени выполнения, то независимо от того, какая стратегия используется, - улучшить производительность не удастся. В этом случае сама большая задача должна быть распараллелена, к сожалению, поддержка OpenMP в Cython несколько отсутствует (см., Например, SO-post ), поэтому возможно, что лучше написать код на чистом C, а затем обернуть полученный результатфункциональность с Cython.

...