Parallelize msmf corr coeff.m

From edegan.com
Jump to navigation Jump to search


McNair Project
Parallelize msmf corr coeff.m
Project logo 02.png
Project Information
Project Title Parallelize msmf corr coeff.m
Owner Wei Wu
Start Date 2018-07-09
Deadline
Keywords Matlab, parallel computing, CPU
Primary Billing
Notes
Has project status Active
Is dependent on Estimating Unobserved Complementarities between Entrepreneurs and Venture Capitalists Matlab Code
Copyright © 2016 edegan.com. All Rights Reserved.


This page documents all changes that Wei made to the Matlab code for Matching Entrepreneurs to VC. It also explains the decisions Wei made, and analyzes where further improvement might be achieved in the future.

Changes made to the code

To speed up the valuation of the objective function used by ga, Wei parallelized a couple of lines in msmf_corr_coeff.m.

Around line 80 of msmf_corr_coeff

Original code:

for m = 1 : M
   cholA = chol(exchsig(N1(m)-1, N2(m)-1, th));
   epsim12 = zeros(N1(m), N2(m), R);
   epsimR12 = reshape(mtimesx(repmat(cholA', [1 1 R]), reshape(epsimR(psa(m)+1: psa(m)+(N1(m)-1)*(N2(m)-1), :, :), [(N1(m)-1)*(N2(m)-1) 1 R])), [N1(m)-1 N2(m)-1 R]);
   epsim12(2:end, 2:end, :) = epsimR12;          
   f(psa(m)+1 : psa(m+1), :) = f(psa(m)+1 : psa(m+1), :) - reshape(epsim12, [N1(m)*N2(m) R])                   
end

For R=200, monte_M = 70 (hence large M), and mktsize = 30, each call to msmf_corr_coeff takes ~140 seconds. Computing epsimR12 is taking more than 50% time of msmf_corr_coeff.m. Each computation of epsimR12 is taking no more than 2 seconds, but for a large M it will take a long time in total. To improve this, we use a parfor to paralellize this part.
EpsimR12 new.png
New code:

epsim_cell = cell(M,1);  
parfor m = 1 : M
   cholA = chol(exchsig(N1(m)-1, N2(m)-1, th));
   epsim12 = zeros(N1(m), N2(m), R);
   epsimR12 = reshape(mtimesx(repmat(cholA', [1 1 R]), reshape(epsimR(psa(m)+1 : psa(m)+(N1(m)-1)*(N2(m)-1), :, :), [(N1(m)-1)*(N2(m)-1) 1 R])), [N1(m)-1 N2(m)-1 R]);
   epsim12(2:end, 2:end, :) = epsimR12;
   epsim_cell{m} = reshape(epsim12, [N1(m)*N2(m) R]);                           
end   
for m = 1 : M
    f(psa(m)+1 : psa(m+1), :) = f(psa(m)+1 : psa(m+1), :) - epsim_cell{m};
end

To avoid data-racing, in each iteration m, we stored epsim12 into epsim_cell, and compute f using another for loop. Using parfor on a 12-cores machine gives a four time speed up for computing msmf_corr_coeff.m. Note that the actual speedup depends how many cores you are using. For the same R, monte_M, and mktsize, it now takes ~ 35 seconds to finish one call to msmf_corr_coeff.

Msmf corr coeff speedup.png