Ich lerne Python Multiprocessing-Paket für peinlich parallele Probleme zu verwenden, so schrieb ich serielle und parallele Versionen für die Bestimmung der Anzahl der Primzahlen kleiner oder gleich einer natürlichen Zahl n . Nach dem, was ich von einem blog post lesen und Stack Overflow question, kam ich mit dem folgenden Code auf:Erwartete Beschleunigung von peinlich parallelen Aufgabe mit Python Multiprocessing
Serien
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)
Parallel
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)
Hier ist, was ich für n = 10000000 (für parallele Ich Anfrage 8 Prozesse):
$ 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
So sieht es aus wie ich etwas über 3x beschleunigen kann. Hier sind meine Fragen:
- Klar ist das nicht lineare Beschleunigung, so wie viel besser kann ich (oder was Speedup soll ich erwarten, realistisch)?
- Es sieht so aus, als ob Amdahls Gesetz dies beantwortet, aber ich weiß nicht, wie ich feststellen soll, welcher Teil meines Programms streng seriell ist.
Jede Hilfe wird geschätzt.
Edit: Es gibt 4 physikalische Kerne, Hyperthreading fähig.
Wie viele Kerne haben Sie? –
Ihr Code wird bei größeren Zahlen wahrscheinlich länger dauern, so dass die Aufgabe mit der größten Reichweite am längsten dauert. Haben Sie überprüft, ob die Prozessoren gegen Ende des Programmlaufs inaktiv sind? –
Für ernsthafte Beschleunigungen sollten Sie zuerst überlegen, ob Python die richtige Wahl ist. Ein Programm aus einer kompilierten Sprache ist wahrscheinlich 10x so schnell, das Äquivalent davon, dass 10 Kerne perfekt parallel sind. –