PCA 25: Parallel Python

In order to successfully complete this assignment you must do the required reading, watch the provided videos and complete all instructions. The embedded survey form must be entirely filled out and submitted on or before 11:59pm. Students must come to class the next day prepared to discuss the material covered in this assignment.

PCA 25: Parallel Python#

1. Matrix Multiply Example#

The following is a simple implementation of a matrix multiply written in python. Review the code try to understand what it is doing.

%matplotlib inline
import matplotlib.pylab as plt
import numpy as np
import sympy as sp
import random
import time
sp.init_printing(use_unicode=True)

#simple matrix multiply (no numpy)
def multiply(m1,m2):
    m = len(m1)
    d = len(m2)
    n = len(m2[0])
    if len(m1[0]) != d:
        print("ERROR - inner dimentions not equal")
    result = [[0 for i in range(m)] for j in range(n)]
    for i in range(0,m):
        for j in range(0,n):
            for k in range(0,d):
                result[i][j] = result[i][j] + m1[i][k] * m2[k][j]
    return result

# Random generated 2d lists of lists that can be multiplied 
m = 4
d = 10
n = 4

A = [[random.random() for i in range(d)] for j in range(m)]
B = [[random.random() for i in range(n)] for j in range(d)]

#Compute matrix multiply using your function
start = time.time()

simple_answer = multiply(A, B)
simple_time = time.time()-start

print('simple_answer =',simple_time,'seconds')

Lets compare this to the numpy result:

#Compare to numpy result
start = time.time()

np_answer = np.matrix(A)*np.matrix(B)
np_time = time.time()-start

print('np_answer =',np_time,'seconds')

For this example, numpy result are most likely slower than the simple result. Think about why this might be. We will discuss this later.

✅ DO THIS: See if you can write a loop to do a scaling study for the above code. Loop over the value of \(n\) such that \(n\) is 4, 16, 32, 64, 128 and 256. For each iteration generate two random matrices (as above) with \(m = d = n\). Then time the matrix multiply for the provided function and again for the numpy function. Graph the results as size of \(n\) vs time.

# Put your code here

##ANSWER##
simple_time = []
np_time = []
n_vals = [4,16,32,64,128, 256]
for n in n_vals:
    
    m = n
    d = n

    A = [[random.random() for i in range(d)] for j in range(m)]
    B = [[random.random() for i in range(n)] for j in range(d)]
    
    start = time.time()

    simple_answer = multiply(A, B)
    simple_time.append(time.time()-start)

    start = time.time()

    np_answer = np.matrix(A)*np.matrix(B)
    np_time.append(time.time()-start)

plt.plot(n_vals,np_time)
plt.plot(n_vals,simple_time)
##ANSWER##

✅ DO THIS: Explore the Internet for ways to speed up Python (There are a lot of them). Save some of your search results in the cell below and come to class prepaired to discuss what you found.

Put your search results here.

2. Parallel Python example#

Here is an example for running parallel python using the multiprocessing library. Note, that running multiprocessing in Python doesn’t generally work well from a Jupyter notebook, so you should copy the Python code into a .py file and run it directly from the command line if you encounter errors.

https://stackoverflow.com/questions/10415028/how-can-i-recover-the-return-value-of-a-function-passed-to-multiprocessing-proce

import multiprocessing
num_procs = multiprocessing.cpu_count()
print('You have', num_procs, 'processors')

def worker(procnum, return_dict):
    '''worker function'''
    print(str(procnum) + ' represent!')
    return_dict[procnum] = procnum


if __name__ == '__main__':
    manager = multiprocessing.Manager()
    return_dict = manager.dict()
    jobs = []
    for i in range(num_procs):
        p = multiprocessing.Process(target=worker, args=(i,return_dict))
        jobs.append(p)
        p.start()

    for proc in jobs:
        proc.join()
    print(return_dict.values())

Lets try to make a parallel matrix multiply#

The following is the instructor’s attempt at using multiprocessing to do matrix multiply. First lets start with a serial method.

%matplotlib inline
import matplotlib.pylab as plt
import numpy as np
import sympy as sp
import random
import time
sp.init_printing(use_unicode=True)

#simple matrix multiply (no numpy)
def multiply(m1,m2):
    m = len(m1)
    d = len(m2)
    n = len(m2[0])
    if len(m1[0]) != d:
        print("ERROR - inner dimentions not equal")
    result = [[0 for i in range(m)] for j in range(n)]
    for i in range(0,m):
        for j in range(0,n):
            for k in range(0,d):
                result[i][j] = result[i][j] + m1[i][k] * m2[k][j]
    return result

# Random generated 2d lists of lists that can be multiplied 
m = 4
d = 10
n = 4

A = [[random.random() for i in range(d)] for j in range(m)]
B = [[random.random() for i in range(n)] for j in range(d)]

#Compute matrix multiply using your function

start = time.time()

simple_answer = multiply(A, B)
simple_time = time.time()-start

print('simple_answer =',simple_time,'seconds')

Lets compare this to the numpy result:

#Compare to numpy result
start = time.time()

np_answer = np.matrix(A)*np.matrix(B)
np_time = time.time()-start

print('np_answer =',np_time,'seconds')

#Compare to numpy result
A_ = np.matrix(A)
B_ = np.matrix(B)

start = time.time()

np_answer = A_*B_
np_time = time.time()-start

print('np_answer =',np_time,'seconds')

np.allclose(simple_answer,np_answer)