ORT BRAUDE COLLEGE OF ENGINEERING Electronic and Electrical Engineering Department Client Server Systems and prallel programming 31261 PROJECT 6: Multiprocessing * We continue with basic parallel programming * At this project we will use the Python multiprocessing module * We are going to solve the following problems in the laboratory * As an example of a computational problem that can be solved with parallel techniques is: ******************************************************* * * * Find the sum of all prime numbers less than 40000 * * * ******************************************************* At project 5 we realized that Multi-Threading techniques did not yield any run time gain for such computational problems: on the contrary, it increased run time! * To overcome this difficulty, Python was supplemented with the Multi-Processing module. * Work in c:\workspace: Copy and paste the following code to a file named: proj6.py ------------------------------------------------------------------------ import sys, os, time, subprocess from multiprocessing import Process # calculate the sum of all prime numbers smaller than n def sum_of_primes(n): s = sum(find_primes(2,n)) return s # Find all prime numbers from a to b (excluding b) def find_primes(a,b): primes = [] p=a while i 17 What will happen if you forget the 'thread.join()' statement ?? Try to comment this statement and see what happens? --------- PROBLEM 5 --------- Run the following two processes concurrently: result_que = Queue() p1 = PrimeSumProcess(0, 100, result_que) p2 = PrimeSumProcess(100, 200, result_que) p1. start() p2. start() How can you prove that this two processes are really running concurrently ?! (maybe I'm bloffing ...) Hint: In find_primes() function, uncomment the line: #sys.stdout.write(str(i)+':') then run the above code again --------- PROBLEM 6 --------- (a) Use the PrimeSumProcess class to write a function: def sum_of_primes_parallel(n): #code ... which computes the sum of primes smaller than the integer n, in 4 parallel threads. (b) Write a small test2() for computing: sum_of_primes_parallel(40000) and measure the run time for this computation Hint: def sum_of_primes_parallel(n): thread = {} thread[0] = PrimeSumProcess(2, n/4) thread[1] = PrimeSumProcess(n/4, 2*n/4) thread[2] = PrimeSumProcess(2*n/4, 3*n/4) thread[3] = PrimeSumProcess(3*n/4, n) # continue from here ... # ...................... def test2(): t1 = time.time() #code t2 = time.time() time = t2-t1 --------- PROBLEM 6 --------- What was the surprise you found in problem 4 ??? To solve this surprise we will need to resolt to the multiprocessing module: goto project 6 ... Now let's try the multiprocessing module: To do that we need first learn about the multiprocessing.Queue class. Create a global Queue() object by: from multiprocessing import Queue q = Queue() q.put(111) q.put(222) print q.get() print q.get() PART (a) -------- Queue() objects are thread-safe - they can be used as a shared memory storage between processes. Create a simple example of a process and a child process that exchange information through a global Queue() object PART (b) -------- # Compute the sum of all primes between a and b # in a separate process ! class PrimeSumProcess(multiprocessing.Process): def __init__(self, a, b, result_que), multiprocessing.Process.__init__(self) self.a = a self.b = b self.sum = 0 def run(self): for p in find_primes(self.a, self.b): self.sum += p Complete the following function: # Compute the sum of primes from 1 to n in 4 parallel processes def sum_of_primes_parallel2(n): proc = {} proc[0] = PrimeSumProcess(2, n/4) proc[1] = PrimeSumProcess(n/4, 2*n/4) proc[2] = PrimeSumProcess(2*n/4, 3*n/4) proc[3] = PrimeSumProcess(3*n/4, n) # Continue from here ... Compute how musch time it takes sum_of_primes_parallel2(n) for n=40000 ? --------- PROBLEM 6 --------- Calculate the value of PI according to the Gregory-Leibnitz formula: PI = 4/1 - 4/3 + 4/5 - 4/7 + 4/9 - 4/11 .... In two ways: (a) single process calculation (b) 4 parallel processes like in the primes example Hint: def partsum(a,b): # calculate the sum from term a to term b (excluding b) Break partsum(0,n) to 4 partsums: partsum(a0,a1) + partsum(a1,a2) + partsum(a2,a3) + partsum(a3,a4) For example, partsum(0,400000) should be broken to: partsum(0,100000) + partsum(100000,200000) + partsum(200000,300000) + partsum(300000, 400000) where: partsum(a,b) = Sum of term(i) ( a<=i<=b) term(i) = 4*(-1)**i / (2*i+1) Note that the Queue data structure is thread and process safe! The Queue class in this module implements all the required locking semantics! It depends on the availability of thread support in Python That means if a thread (or a process) access the Queue object, then it is automatically locked for the other threads (or processes)! To get a better understanding please read: http://docs.python.org/2/library/queue.html The exact value of PI, 48 digits precision is: 3.141592653589793238462643383279502884197269399375