Эффективное распараллеливание операций над операциями с двумерным массивом в python
Я пытаюсь распараллелить операции на двумерном массиве, используя joblib библиотека в питоне. Вот код, который у меня есть
from joblib import Parallel, delayed
import multiprocessing
import numpy as np
# The code below just aggregates the base_array to form a new two dimensional array
base_array = np.ones((2**12, 2**12), dtype=np.uint8)
def compute_average(i, j):
return np.uint8(np.mean(base_array[i*4: (i+1)*4, j*4: (j+1)*4]))
num_cores = multiprocessing.cpu_count()
new_array = np.array(Parallel(n_jobs=num_cores)(delayed(compute_average)(i, j)
for i in xrange(0,1024) for j in xrange(0,1024)), dtype=np.uint8)
Приведенный выше код занимает больше времени, чем основной вложенный цикл for ниже.
new_array_nested = np.ones((2**10, 2**10), dtype=np.uint8)
for i in xrange(0,1024):
for j in xrange(0,1024):
new_array_nested[i,j] = compute_average(i,j)
Почему параллельные операции занимают больше времени? Как повысить эффективность приведенного выше кода?
1 ответ
Мы можем довольно легко попасть куда-то под 77 [ms] , но для этого нужно освоить несколько шагов, поэтому начнем:
Вопрос: почему параллельные операции занимают больше времени?
Потому что предложенный шаг с joblibсоздает такое количество полномасштабных технологических копий - чтобы убежать от чистого шага GIL [SERIAL] танцы (один за другим), но (!) это включает в себя дополнительные расходы на все передачи памяти (очень дорого / чувствительно для действительно больших numpy массивов) всех переменных и всего интерпретатора Python и его внутреннего состояния, прежде чем он начнет делать первый шаг к "полезной" работе над вашей стратегией расчета "полезной нагрузки",
так
сумма всех этих накладных расходов на реализацию может легко стать больше, чем ожидание, не зависящее от накладных расходов, обратно пропорционально 1 / N фактор,
где вы устанавливаете N ~ num_cores,
Вопрос: может помочь повысить эффективность кода выше?
Сэкономьте как можно больше на все накладные расходы:
- где возможно:
- на стороне процесса, попробуйте использовать n_jobs = ( num_cores - 1 ) чтобы дать больше места для "основного" процесса в будущем и сравнительного анализа, если производительность возрастет
- на стороне завершения процесса, избегая сбора и конструирования нового (возможно, большого по размеру) объекта из возвращаемых значений, а скорее предварительно выделяя достаточно большие локальные структуры данных процесса и возвращая некоторые эффективные, сериализованные для простого и неблокирующее объединение per-partes возвращенных результатов.
Обе эти "скрытые" затраты являются вашими главными врагами дизайна, поскольку они линейно добавляются к чистой [SERIAL] часть вычислительного пути решения всей проблемы ( см.: эффекты обоих из них в формуле Закона Амдала о строгих издержках)
Эксперименты и результаты:
>>> from zmq import Stopwatch; aClk = Stopwatch()
>>> base_array = np.ones( (2**12, 2**12), dtype = np.uint8 )
>>> base_array.flags
C_CONTIGUOUS : True
F_CONTIGUOUS : False
OWNDATA : True
WRITEABLE : True
ALIGNED : True
UPDATEIFCOPY : False
>>> def compute_average_per_TILE( TILE_i, TILE_j ): // NAIVE MODE
... return np.uint8( np.mean( base_array[ 4*TILE_i:4*(TILE_i+1),
... 4*TILE_j:4*(TILE_j+1)
... ]
... )
... )
...
>>> aClk.start(); _ = compute_average_per_TILE( 12,13 ); aClk.stop()
25110
102
109
93
Это занимает около 93 [us] за один выстрел. Имея ожидание о 1024*1024*93 ~ 97,517,568 [us] покрыть среднюю обработку по всему base_array,
Экспериментально, здесь хорошо видно влияние не очень хорошо обработанных накладных расходов, эксперимент с наивным вложением:
>>> aClk.start(); _ = [ compute_average_per_TILE( i, j )
for i in xrange(1024)
for j in xrange(1024)
]; aClk.stop()
26310594
^^......
26310594 / 1024. / 1024. == 25.09 [us/cell]
что примерно в 3,7 раза меньше (из-за не понесенных издержек "tail"-part (назначение отдельных возвращаемых значений) 2**20 раз, но только один раз, при назначении терминала.
Тем не менее, еще больше сюрпризов.
Какой правильный инструмент здесь?
Универсального правила, универсального для всех никогда не бывает.
Дано
не более, чем просто матричная плитка 4x4 будет обрабатываться за вызов (фактически 25 [us] согласно предложенному joblib управляемый нерест 2**20 звонки, распределенные по ~ .cpu_count() полностью реализованные процессы по первоначальному предложению
...( joblib.Parallel( n_jobs = num_cores )(
joblib.delayed( compute_average )( i, j )
for i in xrange( 1024 )
for j in xrange( 1024 )
)
действительно есть место для улучшения производительности.
Для этих мелкомасштабных матриц (не все проблемы так хороши в этом смысле) можно ожидать лучших результатов от шаблонов доступа к более "умной" памяти и от уменьшения слабостей, порожденных GIL-кодами из Python.
Поскольку интервал между вызовами составляет всего лишь 4x4 микропроцессора, лучше использовать интеллектуальную векторизацию (все данные помещаются в кэш, поэтому вычисления в кеше - это выходной день для достижения максимальной производительности)
Лучший (все еще очень наивно векторизованный код)
смог получить от ~ 25 [us/cell] менее чем ~ 74 [ns/cell] (наличие там еще места для лучшей выровненной обработки, как потребовалось ~ 4.6 [ns] / а base_array обработки ячеек), поэтому ожидайте еще один уровень ускорений, если оптимизированный в кеше векторизованный код будет создан правильно.
В 77 [ms]?! Стоит сделать это правильно, не так ли?
Не 97 секунд,
не 25 секунд,
но меньше чем 77 [ms] всего за несколько нажатий на клавиатуру, и больше можно было бы выжать, если бы лучше оптимизировать сигнатуру вызова:
>>> import numba
>>> @numba.jit( nogil = True, nopython = True )
... def jit_avg2( base_IN, ret_OUT ): // all pre-allocated memory for these data-structures
... for i in np.arange( 1024 ): // vectorised-code ready numpy iterator
... for j in np.arange( 1024 ):// vectorised-code ready numpy iterator
... ret_OUT[i,j] = np.uint8( np.mean( base_IN[4*i:4*(i+1),
... 4*j:4*(j+1)
... ]
... )
... )
... return // avoid terminal assignment costs
...
>>> aClk.start(); _ = jit_avg2( base_array, mean_array ); aClk.stop()
1586182 (even with all the jit-compilation circus, it was FASTER than GIL-stepped nested fors ...)
76935
77337