Why is this MATLAB script taking so long to execute?

Question

I'm trying to simulate the performance of an LDPC code on a BPSK AWGN channel when using sum-product decoding.

For this, I've written a function in MATLAB that follows the algorithm described in the 34th page of this paper. However, when I use the function I've written with parity-check matrices of large dimension (I need to use a matrix of 1012 x 1518), the program takes FOREVER to do a single iteration (I'm trying to simulate the performance of the code in this channel by doing at least 100k iterations to have a good estimation). The matrix H I'm using is of very low density (it only has two 1's per column), so I would expect the script to run way faster.

I thought that maybe using float to represent matrices with only 0's and 1's may be the issue, but I'm not sure if this would mean a huge change. Also, I wouldn't know how to perform some of the operations I use in my function if these matrices were boolean.

So does anyone have any idea? I'll put the function I wrote below.

function y = sum_product(r, H, I_max)

[m , n] = size(H);

I = 0;

for i = 1:n
    for j = 1:m
        if H(j,i) == 1
            M(j,i) = r(i);
        else
            M(j,i) = 0;
        end
    end
end

M = sparse(M);

E = M;

while 1

for j = 1:m
    for i = 1:n
        aux = 1;
        if H(j,i) == 1
            for l = 1:n
                if l~=i & H(j,l) == 1
                    aux = tanh(M(j,l)/2)*aux;
                end
            end
            E(j,i) = log(1+aux)-log(1-aux);
        end
    end
end

for i = 1:n
    aux = 0;
    for j = 1:m
        if H(j,i) == 1
            aux = aux + E(j,i);
        end
    end

    L(i) = aux + r(i);

    z(i) = L(i)<=0;
end

if I == I_max | mod((H*transpose(z)) , 2) == 0
    break;
else
    for i = 1:n
        for j = 1:m
            aux = 0;
            if H(j,i) == 1
                for l = 1:m
                    if l~=j & H(l,i) == 1
                        aux = aux + E(l,i);
                    end
                end
            M(j,i) = aux + r(i);
            end
        end
    end
I = I + 1;
end
end

y = z;

end

What version of MATLAB? What are the values of r, H, and I_max that reproduce the performance issue? Have you profiled your code to identify where the majority of computation time is being spent? — excaza

rahnema1 rahnema1 · Accepted Answer · 2016-12-25T13:28:39

As in other answer stated vectorization often will speed your computation. It means that instead of running the same function multiple times for each element of a matrix you can only run the function once for the whole matrix. If you are more comfortable with loops and if else statements you may consider using languages such as c++ to reach the desired speed. So here is a vectorized form;

function z = sum_product(r, H, It_max)
    m  = size(H,1);
    n  = size(H,2);
    M = repmat(r,m,1);
    L = zeros(m,n);
    E = zeros(m,n);
    x = reshape(1:numel(H),m,n).';
    idx1= reshape(x(logical(H')),[],m).';
    idx2= reshape(find(H),[],n);
    for It = 0:It_max
        tn = tanh(M(idx1)/2);
        pr = bsxfun(@rdivide,prod(tn,2),tn);
        E(idx1) = log((1+ pr)./(1-pr));
        sumE = sum(E(idx2));
        L = sumE + r;
        z = L <= 0;
        if all(mod(H * z.',2) == 0)
            break;
        end
        M(idx2) = bsxfun(@plus,bsxfun(@minus,sumE , E(idx2) ),r);
    end
end

Why is this MATLAB script taking so long to execute?

2 Answers