Ожидаемое ускорение от смущающей параллельной задачи с использованием многопроцессорной обработки Python
Я учусь использовать пакет многопроцессорной обработки Python для смущающих параллельных задач, поэтому я написал последовательные и параллельные версии для определения числа простых чисел, меньшего или равного натуральному числу n. На основании того, что я прочитал в блоге и вопроса о переполнении стека, я придумал следующий код:
последовательный
import math
import time
def is_prime(start, end):
"""determine how many primes within given range"""
numPrime = 0
for n in range(start, end+1):
isPrime = True
for i in range(2, math.floor(math.sqrt(n))+1):
if n % i == 0:
isPrime = False
break
if isPrime:
numPrime += 1
if start == 1:
numPrime -= 1 # since 1 is not prime
return numPrime
if __name__ == "__main__":
natNum = 0
while natNum < 2:
natNum = int(input('Enter a natural number greater than 1: '))
startTime = time.time()
finalResult = is_prime(1, natNum)
print('Elapsed time:', time.time()-startTime, 'seconds')
print('The number of primes <=', natNum, 'is', finalResult)
Параллельно
import math
import multiprocessing as mp
import numpy
import time
def is_prime(vec, output):
"""determine how many primes in vector"""
numPrime = 0
for n in vec:
isPrime = True
for i in range(2, math.floor(math.sqrt(n))+1):
if n % i == 0:
isPrime = False
break
if isPrime:
numPrime += 1
if vec[0] == 1:
numPrime -= 1 # since 1 is not prime
output.put(numPrime)
def chunks(vec, n):
"""evenly divide list into n chunks"""
for i in range(0, len(vec), n):
yield vec[i:i+n]
if __name__ == "__main__":
natNum = 0
while natNum < 2:
natNum = int(input('Enter a natural number greater than 1: '))
numProc = 0
while numProc < 1:
numProc = int(input('Enter the number of desired parallel processes: '))
startTime = time.time()
numSplits = math.ceil(natNum/numProc)
splitList = list(chunks(tuple(range(1, natNum+1)), numSplits))
output = mp.Queue()
processes = [mp.Process(target=is_prime, args=(splitList[jobID], output))
for jobID in range(numProc)]
for p in processes:
p.start()
for p in processes:
p.join()
print('Elapsed time:', time.time()-startTime, 'seconds')
procResults = [output.get() for p in processes]
finalResult = numpy.sum(numpy.array(procResults))
print('Results from each process:\n', procResults)
print('The number of primes <=', natNum, 'is', finalResult)
Вот что я получаю для n= 10000000 (для параллельного я запрашиваю 8 процессов):
$ python serial_prime_test.py
Enter a natural number greater than 1: 10000000
Elapsed time: 162.1960825920105 seconds
The number of primes <= 10000000 is 664579
$ python parallel_prime_test.py
Enter a natural number greater than 1: 10000000
Enter the number of desired parallel processes: 8
Elapsed time: 49.41204643249512 seconds
Results from each process:
[96469, 86603, 83645, 80303, 81796, 79445, 78589, 77729]
The number of primes <= 10000000 is 664579
Так что, похоже, я могу получить чуть более 3-х кратное ускорение. Вот мои вопросы:
- Очевидно, что это не линейное ускорение, так насколько лучше я могу сделать (или какое ускорение мне реально ожидать)?
- Похоже, что Закон Амдала отвечает на это, но я не знаю, как определить, какая часть моей программы является строго последовательной.
Любая помощь приветствуется.
Изменить: есть 4 физических ядра, способных к гиперпоточности.
2 ответа
Я думаю, что вы хотите разделить работу по-другому.
Хотя ваша программа равномерно распределяет диапазон возможных целых чисел по ядрам, работа в каждом диапазоне вряд ли будет равномерной. Это означает, что некоторые ядра заканчивают работу раньше, и им нечего делать, в то время как другие все еще работают. Это теряет параллельную эффективность, быстро.
Просто чтобы подчеркнуть, представьте, что у вас есть 1000 ядер. Первое ядро видит очень маленькие числа кандидатов и не занимает много времени, чтобы их учесть, затем бездействует. Последнее (тысячное) ядро видит только очень большие числа кандидатов, и их анализ занимает гораздо больше времени. Так он работает, пока первое ядро бездействует. Потраченные впустую циклы. Аналогично для 4 ядер.
То, что вы хотите делать, когда объем работы, передаваемой ядру, неизвестен, - это передать всем ядрам множество кусков скромного размера, намного больше, чем есть ядра. Тогда ядра могут работать с неравной скоростью, и каждое ядро возвращается, чтобы найти немного больше работы. По сути, это алгоритм рабочего списка. Вы в конечном итоге неровности в самом конце, но это только на небольших кусках, так что не так много тратится впустую.
Я не программист на Python, поэтому вместо этого я написал решение в Parlanse.
(includeunique `Console.par')
(includeunique `Timer.par')
(define upper_limit 10000000)
(define candidates_per_segment 10)
(define candidates_per_segment2 (constant (* candidates_per_segment 2)))
(= [prime_count natural] 0)
[prime_finding_team team]
(define primes_in_segment
(action (procedure [lower natural] [upper natural])
(;;
(do [candidate natural] lower upper 2
(block test_primality
(local (= [divisor natural] 3)
(;;
(while (< (* divisor divisor) candidate)
(ifthenelse (== (modulo candidate divisor) 0)
(exitblock test_primality)
(+= divisor 2)
)ifthenelse
)while
(ifthen (~= (* divisor divisor) candidate)
(consume (atomic+= prime_count))
)ifthen
);;
)local
)block
)do
);;
)action
)define
(define main
(action (procedure void)
(local [timer Timer:Timer]
(;;
(Console:Put (. `Number of primes found: '))
(Timer:Reset (. timer))
(do [i natural] 1 upper_limit candidates_per_segment2
(consume (draft prime_finding_team primes_in_segment
`lower':i
`upper':(minimum upper_limit (- (+ i candidates_per_segment2) 2))))
)do
(consume (wait (@ (event prime_finding_team))))
(Timer:Stop (. timer))
(Console:PutNatural prime_count)
(Console:PutNewline)
(Timer:PrintElapsedTime (. timer) (. `Parallel computed in '))
(Console:PutNewline)
);;
)local
)action
)define
Parlanse выглядит как LISP, но работает и компилируется больше как C.
Рабочий является primes_in_segment; он принимает диапазон значений-кандидатов, определенных его параметрами снизу и сверху. Он проверяет каждого кандидата в этом диапазоне и увеличивает (атомарно) общее значение prime_count, если этот кандидат является простым числом.
Полный диапазон разбивается на небольшие пакеты диапазонов (последовательности нечетных чисел) с помощью цикла do в main. Параллелизм происходит с командой черновика, которая создает зерно параллельного выполнения вычислений (не поток Windows) и добавляет его в prime_finding_team, который представляет собой совокупный набор работ, представляющий все основные факторинг. (Цель команды - разрешить управление всей этой работой как единым целым, например, уничтожение при необходимости, не нужное в этой программе). Аргументы тяги - это функция, которая должна выполняться раздвоенным зерном, и ее параметры. Работа выполняется с помощью набора потоков (Windows), управляемого Parlanse, с использованием алгоритма кражи работы. Если работы слишком много, Парланс душит генерирующие работу зерна и тратит свою энергию на выполнение зерен, которые являются чистым вычислением.
Можно передать только одно значение-кандидат в каждое зерно, но тогда на каждого кандидата накладываются дополнительные издержки, и общее время выполнения соответственно ухудшается. Мы выбрали 10 эмпирически, чтобы гарантировать, что накладные расходы вилки на диапазон кандидатов малы; установка кандидатов на сегмент 1000 не дает большого дополнительного ускорения.
Цикл do просто производит работу так быстро, как только может. Парланс регулирует шаг черновика, когда достаточно параллелизма, чтобы быть полезным. Ожидание командного события заставляет основную программу ждать завершения всех членов команды.
Мы запускали его на шестигранном процессоре HP AMD Phenom II X6 1090T с частотой 3,2 ГГц. Выполнение работает ниже; сначала на 1 процессор:
>run -p1 -v ..\teamprimes
PARLANSE RTS: Version 19.1.53
# Processors = 1
Number of primes found: 664579
Parallel computed in 13.443294 seconds
---- PARLANSE RTS: Performance Statistics
Duration = 13.527557 seconds.
CPU Time Statistics:
Kernel CPU Time: 0.031s
User CPU Time: 13.432s
Memory Statistics:
Peak Memory Usage : 4.02 MBytes
Steals: 0 Attempts: 0 Success rate: 0.0% Work Rediscovered: 0
Exiting with final status 0.
Тогда для 6 процессоров (хорошо масштабируется):
>run -p6 -v ..\teamprimes
PARLANSE RTS: Version 19.1.53
# Processors = 6
Number of primes found: 664579
Parallel computed in 2.443123 seconds
---- PARLANSE RTS: Performance Statistics
Duration = 2.538972 seconds.
CPU Time Statistics:
Kernel CPU Time: 0.000s
User CPU Time: 14.102s
Total CPU Time: 14.102s
Memory Statistics:
Peak Memory Usage : 4.28 MBytes
Steals: 459817 Attempts: 487334 Success rate: 94.4% Work Rediscovered: 153
Обратите внимание, что общее время процессора для параллельной версии примерно такое же, как и для последовательной версии; это потому, что они делают ту же работу.
Учитывая операции Python "fork" и "join", я уверен, что есть эквивалент Python, который вы можете легко кодировать. В нем может не хватить места или потоков из-за возможности одновременного использования слишком большого количества вилок. (С candidates_per_segment в 10 лет под Parlanse работает до 1 миллиона живых зерен). Это то, где автоматическое регулирование генерации работы - это хорошая вещь. В качестве замены вы можете установить candidates_per_segment намного большее число, например, 10000, что означает, что вы получите только 1000 потоков в худшем случае. (Я думаю, что вы все равно заплатите высокую цену из-за интерпретации Python). По мере того, как вы устанавливаете кандидатов на сегмент все ближе и ближе к 1e7/4, вы приближаетесь к точному поведению, которое вы используете с вашим нынешним кодом Python.
Вы не получите больше параллелизма, чем количество ядер / потоков в вашем процессоре. Если вы получаете 3-кратную скорость на 4-ядерном компьютере, это очень хорошо. У вас только небольшие накладные расходы. Я хотел бы предложить, чтобы на 4-ядерном компьютере вы установили "количество параллельных процессов" на 4, чтобы уменьшить накладные расходы. Теперь, если вы работаете с этим на 16-ядерном компьютере, скорость всего в 3 раза кажется низкой. Я хотел бы взглянуть на многопроцессорную библиотеку Python, в частности, на то, как она запускает свои потоки (процессы?).
Каковы были ваши результаты с numProc == 4?
Здесь действует закон Амдала, но только очень небольшая часть вашей параллельной программы является последовательной (в основном основной частью), поскольку работа довольно равномерно распределяется по целочисленным диапазонам.