how to speed up my program? parallel?

3 ビュー (過去 30 日間)
Liqun
Liqun 2015 年 3 月 24 日
コメント済み: Liqun 2015 年 3 月 27 日
I have a piece code which would take long time to run, I am wondering how to speed up. Any hints or suggestions are welcome! One think in my mind is parallel, but I have never done that before, so please help me out! Thanks!
When time steps (nT), # of nodes (Vn and Xn) are large (> 500, or even 800), the program will take more than 24 hours to finish.
These codes is using tree method to compute value at the starting points. First, I have 2 1-D trees: V-tree and X-tree, then the two trees are combined into one 2-D tree, I need to compute the value at the starting point in 2-D tree.
Below is my matlab codes:
% compute the value using tree method
% Input:
% nT -- time step
% Vn -- total # of nodes in V-tree
% Xn -- total # of nodes in X-tree
% both V- and X- trees are layed down on the floor,
% root on the left hand side and leaves on the right hand side
% the nodes labeled (by level) from top to bottom(floor):
% 1, 2, 3,.., Vn (Xn)
% Vindex -- 2-D matrix, branches index of V-tree on each level
% pv -- 2-D martix, probability of each branch
% on each level of V-tree
% xindex -- 3-D matrix, branches index of X-tree on each level
% px -- 3-D matrix, probability of each branch
% on each level of X-tree
% r -- growth rate
% dt -- time interval
% Vmid -- V0 position in V-tree (starting point of V-tree)
% Xmid -- X0 position in X-tree (starting point of X-tree)
% value -- 2-D matrix, value at last time step
% output:
% treeValu -- value at starting point
function treeValu = treemethod(nT, Vn, Xn, vindex, pv, xindex, px, r, dt, Vmid, Xmid, value)
for tstep = (nT-1) : -1 : 1 % backward along the tree
valuenew = zeros(Vn, Xn); %value martic for 2-D tree for iteration
for vlevel = 1 : Vn % loop on V-tree
clear vi vitemp vp vptemp;
vitemp = vindex(vlevel, :);
vi = nonzeros(vitemp); % V-tree branches after truncation
vptemp = pv(vlevel, :)'; %--- MUST BE COLUMN VECTOR
vp = vptemp(vitemp>0); % V-tree probability,
% pick prob by existing branches
for xlevel = 1 : Xn % loop on X-tree
clear xi xi3 x3temp xp xp3 xp3temp
xi3 = xindex(vlevel, xlevel, :); % take branch index of
% X-tree from 3-D matrix
xi3temp = reshape(xi3, 1, Xn);% reshape into 1-D vector
xi = nonzeros(xi3temp); % then remove zeros
xp3 = px(vlevel, xlevel, :); % take prob of X-tree
% from 3-D matrix
xp3temp = reshape(xp3, 1, Xn);% reshape into 1-D vector
xp = xp3temp(xi3temp>0); % X-tree probability, pick prob
% by existing branches
% Find the expected value at current node in 2-D tree
valuenew(vlevel, xlevel) = valuenew(vlevel, xlevel)...
+ sum(sum((vp*xp).*value(vi, xi)));
end
end % end loop on V-tree level
value = exp(-r*dt)*valuenew;
end % end loop on backward time step
% output the value at starting point
treeValu = value(Vmid, Xmid);

回答 (4 件)

Roger Stafford
Roger Stafford 2015 年 3 月 24 日
There seem to be a number of inefficiencies in this code:
1) If you make 'vp' a row vector and 'xp' a column vector, the expression
sum(sum((vp*xp).*value(vi, xi)))
can be replaced by the matrix product
vp*value(vi,xi)*xp
which I rather think is faster.
2) You set 'valuenew' to all zeros at the beginning of each 'tstep' and therefore there seems no point in adding the above matrix product to valuenew(vlevel,xlevel) because it will always be zero for each new pair (vleval, xlevel) each time they are encountered. Just write
valuenew(vlevel,xlevel) = vp*value(vi,xi)*xp;
3) Though you can experiment with this, there seems no point in doing the two clearing operations. The subsequent assignment operations should be able to take care of any necessary reallocation of memory at least as quickly.
4) There is something fishy with the returned value in 'treevalue'. As it stands, it reflects only the last 'tstep' operation. The results of all previous steps are being overwritten. Are you sure you haven't copied this code incorrectly?
  1 件のコメント
Liqun
Liqun 2015 年 3 月 25 日
Thanks a lot, Roger! 1), 2), and 3) do help to speed up the program, almost double the speed!
4): the code is correct. the last line of the code:
treeValu = value(Vmid, Xmid);
is out of loop of tstep. value matrix is updated at each time step backward from nT-1, nT-2, ......, 1. When it is time = 1, after the computation, I only pick the particular value at the point of (Vmid, Xmid).

サインインしてコメントする。


Stephen23
Stephen23 2015 年 3 月 26 日
Roger Stafford made very good comments specific to the code you gave. You also might like to consider some general advice on how to speed up MATLAB code, some of which you might find useful:
  • use vectorized code rather than loops.
  • preallocate arrays before loops.
  • use logical indexing rather than subscripts.
  • do not change a variable's data class.
  • do not clear unnecessarily.
  • use tic and toc to time parts of a program.
  • use the profiler to check how long all parts of a function require.
In the MATLAB documentation we also find these tips:
Additional Tips on Improving Performance
If the performance of your program remains a concern, then consider the following suggestions:
  • Split large script files into smaller ones, having the first file call the second if necessary.
  • Construct separate functions (or local functions and nested functions) from the larger chunks of code.
  • If you have overly complicated functions or expressions, use simpler ones to reduce size. * Simpler functions often make good utility functions that you can share with others.
  • Use functions instead of scripts because they are generally faster.
  • Vectorize your code to take advantage of the full functionality of MATLAB.
  • Use a sparse matrix structure to vectorize code without requiring large amounts of memory.
  • Avoid running large processes in the background while executing your program in MATLAB.
  • Avoid overloading MATLAB built-in functions on any standard MATLAB data classes because this can negatively affect performance.
  1 件のコメント
Liqun
Liqun 2015 年 3 月 27 日
Thanks, Stephen! Since the for loops are very large, nT > 500, Vn > 1001, Xn > 1500, after I changed my code under you and Roger's help, the code is much faster, but still not fast enough. So, I am looking for suggestions about parallel coding, since I can connect to a cluster to do the computation.
This is my first time working on parallel coding, so many things to learn. Any comments are welcome! Thanks!

サインインしてコメントする。


Liqun
Liqun 2015 年 3 月 25 日
Under of the help from Roger, the speed is double now. But, still looking for some significant speed up.
can this do parallel?
  1 件のコメント
Jan
Jan 2015 年 3 月 26 日
Please post the current version then to let us look for further improvements.

サインインしてコメントする。


Liqun
Liqun 2015 年 3 月 26 日
I tried to change
for vlevel = 1 : Vn % loop on V-tree
to
parfor vlevel = 1 : Vn % loop on V-tree
But, it is said payoff is a broadcast variable. Will cause some problems. How can I fixed this issue?
Thanks

カテゴリ

Help Center および File ExchangeMatrix Indexing についてさらに検索

製品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by