Dear Octave/Octave-forge developers, I am an enthusiastic (occasional) Octave user since some good 5 years. This is my first post to this mailing list; here I would like to propose a contribution to Octave-forge.
I am writing now after a three years PhD experience, during which I've designed, analyzed and implemented code for a data structure and related algorithms for (basic, Sparse-BLAS-like) sparse matrices computations. This data structure (or simply 'format') is named "Recursive Sparse Blocks" and it is essentially a hybrid: a quad-tree partitioning of a matrix, with 16/32-bit COO (Coordinate)/CSR (Compressed Sparse Rows) representation of "leaf" submatrices (in a "cache blocking" fashion). Its code comes in form of a C library running on Unix systems. Library operation is shared memory parallel, by means of OpenMP. The focus of this library is on the basic operations needed by iterative methods for the solution of linear systems; that is, matrix-vector multiply, triangular system solve, with/without multiple right hand sides, with/without scaling, with/without transposition, supporting symmetric/hermitian matrices, sub-blocks extraction, norm computation, transposition, etc. There is a vast set of self-tests which can be executed at build time (while executing the 'make tests' goal) in order to check for consistency. As far as I know, there aren't many open source shared memory parallel sparse matrix packages around, so I thought that releasing this (so far, research prototype) software to a wider audience may turn out useful to many. As a fan of Octave, I thought that some kind of Octave integration would be beneficial to the potential user of librsb interested in having fast/shared-memory parallel matrix multiplications. As far as I know, Octave's "sparse" matrix implementation is serial, and based on the Compressed Sparse Columns format (CSC), which supports many very useful algorithms, as well as interfaces to many specialized sparse computations packages. However, when it comes to parallel sparse matrix-vector multiplication, CSC may not be always optimal, so in these situations maybe librsb could come to help, at least for some applications. The ideas+performance details of librsb are documented in articles, as well as my PhD thesis, all available on the web; see http://claudius.ce.uniroma2.it/~martone/ . There the algorithms for multiplication, triangular solve, and parallel data structure assembly are explained and the librsb implementation is benchmarked. The reported benchmarks compare librsb's performance to that of Intel MKL's CSR implementation; there, librsb usually performs better on larger matrices. I did not do a similar, exhaustive benchmarking against Octave (e.g.: using same compilation flags), but I assume that having good results when comparing to MKL is encouraging enough. By some "preliminary" serial runs against Octave, I see librsb can be faster by some (small integer) factor, given matrices big enough. In parallel, it scales up, but this depends strongly on the memory subsystem: sparse matrix computations suffer from cpu's-memory transfer bottleneck. A note: assembly of an "rsb" data structure takes generally more time than a CSC one, currently. However this cost is not prohibitive, and its procedure can be tuned further if needed, I would say. I deliberately choose to not quantify here because, as anyone who has experience with sparse matrix computations performance can confirm, actual numbers may change a lot depending on {computer,matrix,compilers}. Following my fascination with Octave, I have attempted to produce an OCT package to allow (potentially) any Octave user to use librsb easily; that is, without the necessity of using it from its C (or Fortran) API. To this end, I have implemented a new "Octave type", that can be instantiated by using a new function, called "sparsersb", with an invocation syntax very close to that of "sparse". This "plugin" code is far from complete: not all of the operations possible on a "sparse" typed matrix work also on a "sparsersb" typed one, but many do. On the other hand, the "librsb" library is of quite a substantial size, and almost ready for release. I speculate that developing, testing and releasing an Octave function (call it "sparsersb") for librsb would be of use to: - the wider community (a new software contribution) - the Octave users interested in high-performance matrix multiplication - librsb itself: by allowing usage of librsb "through" Octave's syntax, it may be easier to spot latent bugs The intended licensing is GPLv3, for both the library and the OCT package. I am ready to make the two packages available, as well as information to whoever interested in these projects. Essentially, the "librsb" library is almost ready for a release and it only needs more "early users" for a wider testing. The "sparsersb" Octave plugin/type is quite functional, although I think some expert Octave developer should give a look at it --- I am not even sure how much it is "legal" to introduce a new Octave type by mimicking the Octave internals/headers (as I did). I am not even sure whether/how much having OpenMP usage from within librsb is safe in the wider context of Octave. I've put together some material for the interested people: A talk about librsb+sparsersb I gave 2 weeks ago (a good place to start): http://home.rzg.mpg.de/~mima/librsb.pdf A practical "sparsersb" documentation (similar to `help sparse`): http://home.rzg.mpg.de/~mima/sparsersb.txt The "librsb" library documentation (Doxygen-generated): http://home.rzg.mpg.de/~mima/librsb/html/ sparsersb.oct's code: http://home.rzg.mpg.de/~mima/sparsersb.tgz Invocation is almost the same as that of "sparse", and allowed operations are a subset of the ones allowed on "sparse" type objects. For all these reasons I ask you, the Octave/Octave-Forge community, for a response about these projects. In particular, if you think that "sparsersb" may be a worthwhile contribution to Octave-Forge, please let me know. In developing the OCT plugin, I've tried to follow the guidelines on http://octave.sourceforge.net/developers.html (and I have a SF account). However, only a thorough check by Octave-savvy developers may tell about its goodness. Finally, I wish to thank you for all of your effort in making Octave an extraordinarily comfortable and useful tool to work with. Michele p.s.: There is another project it may be worth pointing out: it's an idea we ({me, Salvatore Filippone, Alfredo Buttari}, in CC -- please keep them in CC when responding -- they're not subscribed to this mailing list) had; that is to write a single Octave function, capable of solving linear systems by using the two packages: - the "PSBLAS" linear systems solver http://claudius.ce.uniroma2.it/psblas/ - its "MLD2P4" preconditioners package http://www.mld2p4.it/ This project however, is in a quite early stage --- it depends on the forthcoming release of the next PSBLAS version (at least 2~3 months). But we plan to integrate "librsb" as one of the sparse matrix representations available in PSBLAS, so in some way this additional project of ours is closely related to "sparsersb". If you think such contribution may be useful to Octave please let us know. -- Michele Martone High Level Support Team (HLST) Max-Planck-Institut fuer Plasmaphysik Tel.: +49 (0)89 3299 3529 Boltzmannstrasse 2 D-85748 Garching bei Muenchen e-mail: michele.mart...@ipp.mpg.de Germany WWW: http://www.ipp.mpg.de/~mima/ (personal) http://www.efda-hlst.eu/ (team) PGP Key/Fingerprint: 94CE8331/CEE3 A5D1 E752 90FE 91DE 9B14 39B8 7E50 94CE 8331
pgpowilwwr4e4.pgp
Description: PGP signature
------------------------------------------------------------------------------ RSA(R) Conference 2012 Save $700 by Nov 18 Register now http://p.sf.net/sfu/rsa-sfdev2dev1
_______________________________________________ Octave-dev mailing list Octave-dev@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/octave-dev
