how to speed up my program? parallel?

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);

Answer 1

[Roger Stafford]

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?

[Liqun]

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).

Answer 2

[Stephen23]

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.

[Liqun]

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!

Answer 3

[Liqun]

Under of the help from Roger, the speed is double now. But, still looking for some significant speed up.

can this do parallel?

[Jan]

Please post the current version then to let us look for further improvements.

Answer 4

[Liqun]

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