TL; DR: Первый: prange идентичен range, за исключением случаев, когда вы добавляете параллель к jit, например njit(parallel=True).Если вы попробуете, вы увидите исключение о «неподдерживаемом сокращении» - это потому, что Numba ограничивает область действия prange до «чистых» циклов и «нечистых циклов» с поддержкой numbaсокращает и возлагает ответственность за обеспечение того, чтобы пользователь относился к любой из этих категорий.
Это четко указано в документации numbas prange (версия 0.42) :
1.10.2.Явные параллельные циклы
Другая особенность этого этапа преобразования кода - поддержка явных параллельных циклов.Можно использовать prange Numba вместо range, чтобы указать, что цикл может быть распараллелен.Пользователь должен убедиться, что цикл не имеет перекрестных итерационных зависимостей, за исключением поддерживаемых сокращений.
То, что в комментариях называют «нечистыми», в этой документации называется «перекрестными итерационными зависимостями».Такая «перекрестная итерационная зависимость» является переменной, которая изменяется между циклами.Простым примером будет:
def func(n):
a = 0
for i in range(n):
a += 1
return a
Здесь переменная a зависит от значения, которое она имела до начала цикла и , сколько итераций цикла было выполнено.Вот что подразумевается под «перекрестной итерационной зависимостью» или «нечистым» циклом.
Проблема при явном распараллеливании такого цикла состоит в том, что итерации выполняются параллельно, но каждая итерация должна знать, что представляют собой другие итерации.делает.Невыполнение этого требования может привести к неверному результату.
Давайте на минутку предположим, что prange породит 4 рабочих, и мы передадим 4 как n функции.Что будет делать совершенно наивная реализация?
Worker 1 starts, gets a i = 1 from `prange`, and reads a = 0
Worker 2 starts, gets a i = 2 from `prange`, and reads a = 0
Worker 3 starts, gets a i = 3 from `prange`, and reads a = 0
Worker 1 executed the loop and sets `a = a + 1` (=> 1)
Worker 3 executed the loop and sets `a = a + 1` (=> 1)
Worker 4 starts, gets a i = 4 from `prange`, and reads a = 2
Worker 2 executed the loop and sets `a = a + 1` (=> 1)
Worker 4 executed the loop and sets `a = a + 1` (=> 3)
=> Loop ended, function return 3
Порядок, в котором различные работники читают, выполняют и записывают в a, может быть произвольным, это был только один пример.Это также может привести (случайно) к правильному результату!Обычно это называется Race условие .
Что может сделать более изощренный prange, который распознает наличие такой кросс-итерационной зависимости?
Существует три варианта:
- Просто не распараллеливайте его.
- Реализуйте механизм, в котором работники делят переменную.Типичные примеры: Locks (это может повлечь за собой большие накладные расходы).
- Признать, что это сокращение, которое можно распараллелить.
Учитывая мое пониманиеДокументация по Numba (повторяется снова):
Пользователь должен убедиться, что цикл не имеет перекрестных итерационных зависимостей, за исключением поддерживаемых сокращений.
Numba делает:
- Если это известное сокращение, тогда используйте шаблоны для его распараллеливания
- Если это не известное сокращение, выведите исключение
К сожалению, не ясно, что "поддерживаетсясокращения "есть.Но документация намекает на то, что это двоичные операторы, которые работают с предыдущим значением в теле цикла:
Сокращение выводится автоматически, если переменная обновляется двоичной функцией / оператором с использованием ее предыдущего значения втело петли.Начальное значение сокращения выводится автоматически для операторов += и *=.Для других функций / операторов редукционная переменная должна содержать значение идентификатора непосредственно перед входом в цикл prange.Подобные сокращения поддерживаются для скаляров и массивов произвольных измерений.
Код в OP использует список в качестве перекрестной итеративной зависимости и вызывает list.append в теле цикла.Лично я бы не назвал list.append сокращением, и он не использует бинарный оператор, поэтому я предполагаю, что вполне вероятно, что не поддерживается .Что касается другой кросс-итерационной зависимости running: он использует сложение по результату предыдущей итерации (что было бы хорошо), но также условно сбрасывает его в ноль, если он превышает пороговое значение (что, вероятно, не в порядке).
Numba предоставляет способы проверки кода промежуточного кода (LLVM и ASM):
dynamic_cumsum.inspect_types()
dynamic_cumsum.inspect_llvm()
dynamic_cumsum.inspect_asm()
Но даже если бы у меня было необходимое понимание результатов, чтобы сделать какое-либо утверждение о правильности выведенного кода -в общем, очень нетривиально «доказать», что многопоточный / процессный код работает правильно.Учитывая, что мне даже не хватает знаний LLVM и ASM, чтобы даже увидеть, пытается ли он даже распараллелить их, я не могу ответить на ваш конкретный вопрос, какой результат он дает.
Возвращаясь к коду, как уже упоминалось, он вызывает исключениеНеподдерживаемое сокращение), если я использую parallel=True, поэтому я предполагаю, что numba ничего не распараллеливает в примере:
from numba import njit, prange
@njit(parallel=True)
def dynamic_cumsum(seq, index, max_value):
cumsum = []
running = 0
for i in prange(len(seq)):
if running > max_value:
cumsum.append([index[i], running])
running = 0
running += seq[i]
cumsum.append([index[-1], running])
return cumsum
dynamic_cumsum(np.ones(100), np.arange(100), 10)
AssertionError: Invalid reduction format
During handling of the above exception, another exception occurred:
LoweringError: Failed in nopython mode pipeline (step: nopython mode backend)
Invalid reduction format
File "<>", line 7:
def dynamic_cumsum(seq, index, max_value):
<source elided>
running = 0
for i in prange(len(seq)):
^
[1] During: lowering "id=2[LoopNest(index_variable = parfor_index.192, range = (0, seq_size0.189, 1))]{56: <ir.Block at <> (10)>, 24: <ir.Block at <> (7)>, 34: <ir.Block at <> (8)>}Var(parfor_index.192, <> (7))" at <> (7)
Итак, что остается сказать: prange не дает никакого преимущества в скорости в этом случае по сравнению с нормальным range (потому что он не выполняется параллельно).Поэтому в этом случае я бы не «рискнул» потенциальными проблемами и / или не запутал читателей - учитывая, что это не поддерживается в соответствии с документацией Numba.
from numba import njit, prange
@njit
def p_dynamic_cumsum(seq, index, max_value):
cumsum = []
running = 0
for i in prange(len(seq)):
if running > max_value:
cumsum.append([index[i], running])
running = 0
running += seq[i]
cumsum.append([index[-1], running])
return cumsum
@njit
def dynamic_cumsum(seq, index, max_value):
cumsum = []
running = 0
for i in range(len(seq)): # <-- here is the only change
if running > max_value:
cumsum.append([index[i], running])
running = 0
running += seq[i]
cumsum.append([index[-1], running])
return cumsum
Просто быстрое время, которое поддерживает «не быстрее, чем"заявление, которое я сделал ранее:
import numpy as np
seq = np.random.randint(0, 100, 10_000_000)
index = np.arange(10_000_000)
max_ = 500
# Correctness and warm-up
assert p_dynamic_cumsum(seq, index, max_) == dynamic_cumsum(seq, index, max_)
%timeit p_dynamic_cumsum(seq, index, max_)
# 468 ms ± 12.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit dynamic_cumsum(seq, index, max_)
# 470 ms ± 9.49 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)