9 ms·
C++ Library for Linear Algebra on Supercomputers
Elemental is an open-source C++ library meant for performing dense linear algebra on tens of thousands of processes (via the Message Passing Interface). I have been the primary developer for the past four years, but a community is starting to emerge. In addition to the website, the project is also hosted on github: http://github.com/elemental/Elemental
- poulson 13y agoI'm happy to answer any questions about the pros and cons of the library (and to remain quite objective). The main feature that the library currently lacks that is available in ScaLAPACK is a parallel Schur decomposition, but one is in the works. I'm also happy to answer general questions about parallel linear algebra and to point people to the appropriate literature.
- balsam 13y agowhat is the range of matrix sizes that would enjoy a speedup over ScaLAPACK? let's assume a 8 or 16-core cluster with N nodes, so, a function of N.
- poulson 13y agoThere is unfortunately no good answer to this question, as it would completely depend upon the algorithm, MPI implementation, communication network, vendor-tuned BLAS library, etc., etc. However, I can safely say that Elemental is always competitive with ScaLAPACK in performance. The Elemental papers on my website (pick between the preprint or journal article), http://www.stanford.edu/~poulson http://www.stanford.edu/~poulson, go into this in more detail, but keep in mind that the article was written a couple of years ago, when it was still a fledgling library, and so the tone is a bit more aggressive than necessary. With that said, the main advantage of the library is its high-level of software-engineering, which tends to encourage the rapid development of new features. It is actively used within a large number of research projects.
- jeff_science 13y agoIndeed, we didn't chose Elemental over ScaLAPACK; we used Elemental to replace LAPACK because it was impossible to refactor our code to use ScaLAPACK without absolutely ruining it forever. The ScaLAPACK interface is horrible and should only be used inside of a higher-level library interface that hides its ugly, ugly control structures. From my perspective, Elemental is primarily about human performance. That it scales to thousands of nodes of Blue Gene and achieves performance on par with (and in some cases significantly better than) ScaLAPACK is really icing on the cake. Granted, I really like scalability and performance, but I will not ruin my code in the name of these things.
- dmlorenzetti 13y agoDo you see this getting put into the ACTS toolkit (http://acts.nersc.gov/tools.html http://acts.nersc.gov/tools.html)? I see some on your project team are at Argonne, which would seem like a natural fit.
- poulson 13y agoHonestly, I doubt it. Getting added to such a list has both political and merit-based components.
- dmlorenzetti 13y agoInteresting. I had the impression it was just meant to be a repository for DOE-related numerical tools. That's a shame, because having collections of useful tools like that makes it a lot easier to keep track of options.
- jeff_science 13y agoGiven that a few dozen US-based students attend ACTS every year, I hardly see how it is a game-changer w.r.t. the widespread acceptance of Elemental. I think the internet is doing just fine so far.
- jedbrown 13y agoElemental is available via PETSc (http://mcs.anl.gov/petsc http://mcs.anl.gov/petsc), which is part of ACTS. We might be able to talk ACTS into giving Jack a session at the tutorial session next year. (Disclaimer: I'm a PETSc developer and helped with the Elemental interface.)
- n00b101 13y agoWithout GPU support I don't see how this is a good idea, if we are talking about HPC applications. Based on my understanding, a large number of dense matrix operations can be significantly accelerated in GPUs.
- poulson 13y agoAccelerator support is something that happens within the node and is in some sense orthogonal to the high-level design. I recently received funding to add such support to the library (and I hope to add it within the next year). Also, not all supercomputers have accelerators (consider Blue Gene/Q), and often simply having access to more memory is more of a concern than solving the problem at the absolute fastest rate.
- dmlorenzetti 13y agoThis targets distributed-memory applications, so it's not clear why failing to support GPUs with the first iteration makes it a bad idea. I imagine the authors could make a single node of the cluster use a GPU, if they wanted.
- n00b101 13y agoMaybe I should have just said that I think GPU support would be a great addition. Distributed memory and GPUs are not mutually exclusive. Multi-GPU clusters are extremely common. In fact the latest devices (e.g. Tesla K10) have multiple GPU processors packaged in a single card, so it is necessary for applications to target multiple GPUs. There is explicit support for distributed-memory applications in GPUs through the "GPUDirect" technology that allows peer-to-peer DMA and RDMA transfers between GPUs. Given that reports of 30-50x GPU performance gains (versus CPUs) are common, the issue is important because it means solving a problem with (say) $10,000 of kit instead of $500,000.
- jedbrown 13y ago30x to 50x claims are the result of a terrible CPU implementation. When normalized by power consumption (e.g., TDP) or by acquisition cost (assume high-end rather than consumer versions, as with all supercomputing centers), you'll find about a 2x advantage for operations like DGEMM and much less for other operations. Strong scaling is important for many super-computing applications and accelerators like GPUS and Intel MIC are much slower for that purpose. For examples, look at the MKL benchmarks for Xeon Phi (http://software.intel.com/en-us/intel-mkl/ http://software.intel.com/en-us/intel-mkl/) and normalize as 3 Sandy Bridge sockets per Xeon Phi (common configurations pair one SB socket with one Xeon Phi, the Phi has more than twice the TDP and costs more than twice as much). Don't forget to look at QR and Cholesky, for which the Phi at best breaks even, but only for enormous matrix sizes.
- temp453463343 13y agoGreat.. another C++ linear algebra library... boost::uBLAS eigen armadillo a dozen other... why not contribute to an existing project? The reoccurring bifurcation of talent and resources in the open source community is really disheartening. Can't we focus on one or two libraries and make them actually good? Or at least fork off of something that already exists and add your own features. I look at benchmarks of the existing tools and one library will do one operation very efficiently, while another will work well with something. Often the differences in speed are huge (more than a factor of 10). So I end up having to flip a coin in choosing which library to use.
- poulson 13y agoWith all due respect, did you even read the title of the post? This is a distributed-memory library, unlike all of the ones you just mentioned. This is a fundamental difference in design and capability. The only related libraries are ScaLAPACK, PLAPACK, and DPLASMA.
- temp453463343 13y agoAnd why exactly can't that be made part of an existing library?
- poulson 13y agoEssentially all distributed dense linear algebra libraries are built on top of sequential dense linear algebra libraries (mine as well, but on the interface rather than the implementation). Distributed libraries are at least an order of magnitude more complex than their sequential counterparts.
- temp453463343 13y agoI guess I don't get what you're saying: the C++ linear algebra libraries are basically syntactic sugar for interacting with optimized Fortran libraries like BLAS, LAPACK, etc. (I'm sure I'm overlooking some complexity here, because the C++ libraries, while linking to the same Fortran libraries have very different run times) Yours interacts with ScaLAPACK and other distributed memory libraries. Why would it not be possible to simply extend say armadillo or eigen to interact with distributed memory libraries? If you need more syntax, then extend the interface.
- ssawyer06 13y agoNice work, this is important stuff. Next step... sparse linear algebra!
- poulson 13y agoThanks! I actually work on a lot of fast/sparse linear algebra. For example, see Clique: http://github.com/poulson/Clique http://github.com/poulson/Clique
- ssawyer06 13y agoInteresting, a direct sparse solver (for structured sparse matrices?). The name "clique" implies graph theory, so I was expecting to see distributed iterative SVD. I've yet to see a good distributed SVD for huge real-world/power-law graphs.
- poulson 13y agoSparse-direct solvers use graph theory to exploit nonzeros. In particular, Clique uses recursive nodal bisection ("nested dissection") for this purpose. The separators from this process end up (more-or-less) becoming cliques in the graph implied by the factored sparse matrix. Each of these cliques ends up corresponding to a dense matrix, which I then factor/solve-against using Elemental.
- knepley 13y agoSLEPc, http://www.grycap.upv.es/slepc/ http://www.grycap.upv.es/slepc/, has distributed SVD for sparse matrices.
- poulson 13y agoYes, I should have mentioned this. SLEPc has the only distributed implementation of partial reorthogonalization (the key component of high-performance Krylov SVD and Hermitian eigensolvers) that I'm aware of.