Python: Пул процессов — параллельные вычисления

Посчитаем сумму простых чисел в диапазоне от 5000000 до 6000000 загрузив все процессорные ядра. Так как GIL в обычном CPython делает паттерн пул потоков совершенно неэффективным, реализуем для наших параллельных вычислений пул из процессов, воспользовавшись стандартным модулем multiprocessing

Вкраце: пул процессов отличается от пула потоков лишь тем, что каждый воркер (worker) — это отдельный процесс, а не поток. Набор методик, при помощи которых главный процесс обменивается информацией с воркерами, объединяют общим названием IPC. В целом, именно IPC ограничивает эффективность параллельных вычислений, представляя значительную долю накладных расходов на синхронизацию данных между процессами/потоками и запуск новых. (к слову, затраты на IPC для процессов значительно больше, чем для потоков) Чем больше процессов — тем больше объем накладных расходов. Таким образом, самый эффективный способ использовать multiprocessing это поделить объем вычислений на n равных частей, где n это размер пула, который должен быть примерно равен числу ядер в системе. Если разделить вычисления на много небольших частей,  оверхед от IPC будет очень значительным.

Конкретно в нашем случае, можно было бы поделить диапазон чисел на n равных частей и задать каждому воркеру начало и конец его части диапазона, после чего дождаться пока все воркеры вернут найденные ими простые числа в заданных диапазонах и сложить их. Однако, стоит упомянуть так-же случай, когда работу нельзя просто разделить на равные части. В частности, при поиске больших простых чисел сложность значительно возрастает вместе с начальным значением под-диапазона. В таком случае имеет смысл делить всю работу пула не на n частей, а на n*k, где k это небольшое выверенное число, допустим, от 10 до 100. В таком случае, когда один из воркеров закончит свою частью работы быстрее остальных, он сможет взять себе следующую часть и так каждый из них. Такой подход позволит достаточно эффективно и равномерно распределить вычисления на все воркеры. Итак, код:

#!/user/bin/python.exe
import math
from multiprocessing import Pool, cpu_count

global total_primes_sum
total_primes_sum = 0

def onWorkerFinished(sum_of_primes_in_range):
    global total_primes_sum
    total_primes_sum += sum_of_primes_in_range

def isPrime( n ):
    if n < 2:
        return False
    if n == 2:
        return True
    max_divisor = int(math.ceil(math.sqrt(n)))
    for i in xrange(2,max_divisor+1):
        if not n % i:
            return False
    return True

def getPrimesSumWorker(start, stop):
    primes_sum = 0
    for i in xrange(start, stop):
        if isPrime(i):
            primes_sum += i

    return primes_sum

if __name__ == "__main__":
    start = 5000000
    stop = 6000000
    range_length = stop - start
    n = cpu_count()
    print "Pool size:", n
    pool = Pool(n)
    k = 20
    chunks_count = n*k
    print "Chunks count:", chunks_count
    step = range_length / chunks_count
    import time
    t = time.time()
    for i in xrange(start, stop, step):
        pool.apply_async(getPrimesSumWorker,(i, min(stop-1,i+step),), callback = onWorkerFinished)
    print "Waiting workers to finish..."
    pool.close()
    pool.join()
    t = time.time() - t

    print total_primes_sum,t,"seconds elapsed"

ЗЫ: Искать настоящие БПЧ перебирая все возможные делители- это полное сумасшествие . Существуют гораздо более эффективные алгоритмы генерации простых чисел.

Спасибо, что читаете!

За основу взят вопрос на stackoverflow.com, код видоизменен.
Отличная документация по модулю multiprocessing

 

Запись опубликована в рубрике На заметку с метками , , , . Добавьте в закладки постоянную ссылку.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *