MATLAB Central Newsreader - multithreading with chol

multithreading with chol

fabio freschi — Tue, 23 Jun 2009 13:55:03 -0400

Hi all,
I have found a strange but absolutely fine behavior of chol function. It seems that chol can gain speed when multithreading is enabled. I do not have the access to data of my 8 cores linux machine, but also on my intel MACBOOK the factorization of a sparse matrix coming from a scalar poisson problem is faster. Some data
*Matlab 7.5.0 (R2007b)
*size(A) = 125000x125000
*nnz(A) = 1815598
*metis preordering (from SuiteSparse, thanks Tim Davis!)
chol with multithread (2 cores) -> 20.51 sec
chol w/o multithread -> 27.44 sec

This can be extrapolated for a 1.6Mx1.6M matrix on a 8 cores machine...
These results are not in accordance with "Muli-threaded performance and Cleve's Corner" on cholmod webpage. Any ideas?
thanks
fabio

Re: multithreading with chol

fabio freschi — Fri, 26 Jun 2009 07:26:01 -0400

I have rebuilt the benchmark on the 8-core linux machine
*size(A) = 1626142x1626142
*nnz(A) = 11277220
*metis preordering
multithread enabled (8 cores) -> [L,p] = chol(A(ip,ip),'lower','vector') 618 sec
multithread disabled (1 core) -> [L,p] = chol(A(ip,ip),'lower','vector') 1986 sec

not bad! Any idea for these unexpected good results?
fabio

Re: multithreading with chol

fabio freschi — Fri, 26 Jun 2009 07:32:01 -0400

The exact call of chol I used is (of course)
[L,p] = chol(A(ip,ip),'lower')
sorry for the mistyping
fabio

Re: multithreading with chol

Tim Davis — Tue, 07 Jul 2009 03:35:03 -0400

"fabio freschi" <fabio.freschi@remove.gmail.com> wrote in message <h21thh$nro$1@fred.mathworks.com>...
> The exact call of chol I used is (of course)
> [L,p] = chol(A(ip,ip),'lower')
> sorry for the mistyping
> fabio

UMFPACK and CHOLMOD use the BLAS, and those benefit
from multithreading. When Cleve Moler wrote that
"Cleve's Corner" article, there was a performance
bug in the BLAS that slowed it down when multithreading
was enabled. That's no longer the case. In a later
version of MATLAB (including 7.5) the bug was fixed.

Neither UMFPACK nor CHOLMOD include any explicit
parallelism. They just call the BLAS (dense matrix
operations) which benefit from multithreading.

MATLAB uses the MKL BLAS, so UMFPACK and CHOLMOD should
get the same parallel speedup inside or outside of
MATLAB.

My sparse QR (SuiteSparseQR) does include explicit
multithreading (as well as calling the parallel BLAS),
but it's not used in the sparse QR in MATLAB.

Re: multithreading with chol

fabio freschi — Tue, 14 Jul 2009 14:03:02 -0400

Thank you for your answer.
Your answer confirms my thoughts. However it is curious that all CPUs are at their 100% for most of the factorization time. This could mean that BLAS *does* the work and thus your (really impressive) algorithms have strong benefits when activating multithreading.
fabio