Hi Artyom, Thank you for the insight. Given the metrics, it surely looks like even implementing those operations in ublas won't do any good. I will look into the blas/LAPACK backend for ublas. I will look for a possible proposal which can be completed in the given GSOC time frame. Then again there is this question, is there any mentor available for this project who can refine some of the requirements ? Regards Shikhar Srivastava On 21-Jan-2018 12:36 AM, "Artyom Beilis via Boost" wrote:

On Fri, Jan 19, 2018 at 8:37 AM, SHIKHAR SRIVASTAVA via Boost wrote:

...

Hi everyone,

I am a 4th year undergraduate student pursuing a degree in Computer Science and Engineering. I have strong programming experience in C++ through internships, self projects and programming events. I wish to be a part of gsoc18 under boost and am particularly interested in the linear algebra library Boost.ublas.

The ublas library can be made more useful for Machine Learning applications like recommendation systems, clustering and classification, pattern recognition by adding some operations required in those. I propose to add advanced matrix operations to ublas including -

1. Triangular Factorisation (LU and Cholesky) 2. Orthogonal Factorisation (QR and QL) 3. Operations to find Singular Value lists 4. Eigenvalue algorithms 5. Singular Value Decomposition (SVD) 6. Jordan Decomposition 7. Schur Decomposition 8. Hessenberg Decomposition

Hello,

I'm sorry to disappoint you but uBlas is not nearby useful library for real world machine learning applications because it exceptionally slow in comparison to "real" BLAS libraries being used for such applications like OpenBLAS, Atlas or proprietary MKL.

They all give you what you are talking about, they are tested very well and exceptionally fast.

I mean uBlas is by 2-3 orders of magnitude slower than OpenBLAS or Atlas even for small matrices

8x8 GEMM - uBlas slower by 50 times than OpenBlas and 30 times slower than Atlas 128x128 GEMM - uBlas slower by 600 times thatn OpenBlas and 50 times slower than Atlas.

So I don't think investing in implementation of algorithm that are already implemented in LAPACK libraries and have way better performance would actually will be helpful for real world applications.

What you CAN do is to provide *Blas/LAPACK based backend for uBlas...

Regards, Artyom

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost

Hi all, I'll try to make it short and answer to everyone in one shot: - yes uBLAS is slow. Not only needs it a support for hardware acceleration but also it needs to be more modern (C++11/14/17) and its architecture could be much more improved. This would help integrating hardware acceleration, IMHO. - we would love to have basic stats in uBLAS but for more advanced algorithms, we could have a (better ?) interface with LAPACK, and others - GSoC 2015 was a great GSoC. Not problem with the algo, just problem with my own job taking most of my time since then and no time to do the integration. Guys, we have abeautiful code from Rajaditya which still needs to be integrated into the main. As you can see, I have more time now to take care of the Boost GSoC organization, so I hope I will have time to integrate GSoC'15 too. But help is always welcome. Cheers, David On Sat, Jan 20, 2018 at 11:05 PM, Rajaditya Mukherjee via Boost < boost@lists.boost.org> wrote:

Hello

I did the Eigenvalue codes in GSOC 2015 but it had some stability issues with one specific test matrix and hence it wasn't merged. I can commit to merging them well before the start date of this years GSOC since I have some time between now and march to work on this if someone wants to take the work forward.

*Rajaditya Mukherjee * *6th Year Graduate Student* Dept. of Computer Science and Engineering The Ohio State University Columbus, Ohio Tel :- +1-(614)-271-4439 email :- rajaditya.mukherjee@gmail.com,mukherjee.62@osu.edu

On Sat, Jan 20, 2018 at 4:30 PM, SHIKHAR SRIVASTAVA via Boost < boost@lists.boost.org> wrote:

...

Hi Artyom,

Thank you for the insight. Given the metrics, it surely looks like even implementing those operations in ublas won't do any good.

I will look into the blas/LAPACK backend for ublas. I will look for a possible proposal which can be completed in the given GSOC time frame. Then again there is this question, is there any mentor available for this project who can refine some of the requirements ?

Regards Shikhar Srivastava

On 21-Jan-2018 12:36 AM, "Artyom Beilis via Boost" < boost@lists.boost.org> wrote:

...

...

Hi everyone,

I am a 4th year undergraduate student pursuing a degree in Computer Science and Engineering. I have strong programming experience in C++ through internships, self projects and programming events. I wish to be a

On Fri, Jan 19, 2018 at 8:37 AM, SHIKHAR SRIVASTAVA via Boost wrote: part of

...

gsoc18 under boost and am particularly interested in the linear algebra library Boost.ublas.

The ublas library can be made more useful for Machine Learning applications like recommendation systems, clustering and classification, pattern recognition by adding some operations required in those. I propose to add advanced matrix operations to ublas including -

1. Triangular Factorisation (LU and Cholesky) 2. Orthogonal Factorisation (QR and QL) 3. Operations to find Singular Value lists 4. Eigenvalue algorithms 5. Singular Value Decomposition (SVD) 6. Jordan Decomposition 7. Schur Decomposition 8. Hessenberg Decomposition

Hello,

I'm sorry to disappoint you but uBlas is not nearby useful library for real world machine learning applications because it exceptionally slow in comparison to "real" BLAS libraries being used for such applications like OpenBLAS, Atlas or proprietary MKL.

They all give you what you are talking about, they are tested very well and exceptionally fast.

I mean uBlas is by 2-3 orders of magnitude slower than OpenBLAS or Atlas even for small matrices

8x8 GEMM - uBlas slower by 50 times than OpenBlas and 30 times slower than Atlas 128x128 GEMM - uBlas slower by 600 times thatn OpenBlas and 50 times slower than Atlas.

So I don't think investing in implementation of algorithm that are already implemented in LAPACK libraries and have way better performance would actually will be helpful for real world applications.

What you CAN do is to provide *Blas/LAPACK based backend for uBlas...

Regards, Artyom

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost

On Mon, Jan 22, 2018 at 11:16:55AM +0100, Hans Dembinski via Boost wrote:

Hi David, Rajaditya, Artyom, Shikhar,

...

On 21. Jan 2018, at 13:00, David Bellot via Boost wrote:

- yes uBLAS is slow. Not only needs it a support for hardware acceleration but also it needs to be more modern (C++11/14/17) and its architecture could be much more improved. This would help integrating hardware acceleration, IMHO.

I am surprised that no one here mentioned Eigen, an IMHO excellent high-level header-only C++ library to do matrix-vector calculations.

http://eigen.tuxfamily.org/index.php?title=Main_Page http://eigen.tuxfamily.org/index.php?title=Main_Page

It uses expression templates to re-structure the expressions written by users to fast optimised code. It supports both matrices with dimensions known at compile-time and at run-time, and supports mixed versions, e.g. one dimension fixed the other dynamic.

Hello, Tensorflow uses Eigen. If Shikhar is most interested in machine learning libraries, the TensorFlow might have some GSOC projects. Karen.

According to their own (admittedly, a bit outdated) benchmarks, they are extremely competitive, either on par or even beating $$$ closed-source libraries.

http://eigen.tuxfamily.org/index.php?title=Benchmark http://eigen.tuxfamily.org/index.php?title=Benchmark

Eigen tracks its own performance, so you don't need to worry about it getting slower, but perhaps the others have gotten faster in the meantime.

http://eigen.tuxfamily.org/index.php?title=Performance_monitoring http://eigen.tuxfamily.org/index.php?title=Performance_monitoring

I used the library in projects and it is very convenient. You just write your expressions as you would on paper and let Eigen generate the fastest possible code out of that. I only dislike that Eigen does not play well with "auto" since C++11, because they use the assignment to a matrix or vector to trigger the evaluation of the expression template.

I haven't done it myself, but Eigen seems to have a good strategy for adding new features, too. People can start to develop their stuff in an "unsupported" subdirectory, which is not meant for production, but the code is nevertheless distributed with Eigen. This helps to exposes the experimental code to more adventurous users. Eventually, a project that passed the test of time can move from "unsupported" to the main library.

Best regards, Hans

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

--- end quoted text --- -- Karen Shaeffer The subconscious mind is driven by your deeply Neuralscape Services held beliefs -- not your deeply held desires.

Dear all, pon., 22 sty 2018 o 19:03 użytkownik SHIKHAR SRIVASTAVA via Boost < boost@lists.boost.org> napisał:

Hi all,

Thanks a lot for your suggestions. It made a lot of things clearer. My proposal was to add advanced matrix operations that were missing from ublas.

From the discussions it seems that it isn't a great idea to reimplement everything in ublas itself as there can be other options giving much better performance.

@karen - I am not specifically interested in machine learning. I want to contribute to ublas for performance and more usability in applications.

@david - The discussions lead me to think if adding Openblas/LAPACK backend for advanced matrix operation is a really good idea. It would boost performance and make some hardware acceleration possible (depending on blas implementation). It would be nice to have some interface with them. Can this be a potential gsoc anyone would like to mentor?

as others have already suggested, there's no point in manually implementing various linear algebra problems since there are multiple BLAS and LAPACK implementations which provide the most optimized and vectorized implementations for a given platform. However, I don't think that uBLAS would benefit from it unless the expression templates structure provides a way of effectively dispatching kernels to the library. I've used uBLAS briefly in 2015 and I've seen it much less performant than other C++ libraries. I experienced performance problems in nested expressions where creating a temporary is necessary, such as: "A * (a + b + c)" or "(A - B) * (C - D)". Were there major improvements to the library since 2015? Furthermore, I don't recall uBLAS being able to handle well matrix chain computations. Of course, the problem is exponential in time but I've seen decent implementations. For example, Armadillo solves this problem by broking down chains into subchains of the length shorter than four. Obviously, the algorithm is not complete but I've found it quite efficient in practice. The same applies to expressions involving matrix-vector products, I've seen both Blaze and Armadillo being able of finding the efficient parenthesization, e.g. A(Bv) instead of (AB)v. I've done a lot of linear algebra benchmarking in the last couple of months and I believe there are three high-performance C++ linear algebra libraries: Eigen, already mentioned by Hans, Armadillo, and Blaze. Blaze developers present several benchmarks on their website: https://bitbucket.org/blaze-lib/blaze/wiki/Benchmarks It might be a good starting point to benchmark uBLAS against other libraries and discuss whether it is possible to easily modify the library to offer competitive performance. I believe there's no point in targeting accelerators if the library cannot find an efficient mapping of the expression templates tree to BLAS/LAPACK kernels, unless your goal is to simply provide high-level API for BLAS/LAPACK functions. Best regards, Marcin

Regards Shikhar Srivastava

On 22-Jan-2018 10:59 PM, "Karen Shaeffer via Boost"

...

wrote:

...

On Mon, Jan 22, 2018 at 11:16:55AM +0100, Hans Dembinski via Boost wrote:

...

Hi David, Rajaditya, Artyom, Shikhar,

...

On 21. Jan 2018, at 13:00, David Bellot via Boost < boost@lists.boost.org> wrote:

- yes uBLAS is slow. Not only needs it a support for hardware acceleration but also it needs to be more modern (C++11/14/17) and its architecture could be much more improved. This would help integrating hardware acceleration, IMHO.

I am surprised that no one here mentioned Eigen, an IMHO excellent high-level header-only C++ library to do matrix-vector calculations.

http://eigen.tuxfamily.org/index.php?title=Main_Page < http://eigen.tuxfamily.org/index.php?title=Main_Page>

It uses expression templates to re-structure the expressions written by users to fast optimised code. It supports both matrices with dimensions known at compile-time and at run-time, and supports mixed versions, e.g. one dimension fixed the other dynamic.

Hello, Tensorflow uses Eigen.

If Shikhar is most interested in machine learning libraries, the TensorFlow might have some GSOC projects.

Karen.

...

According to their own (admittedly, a bit outdated) benchmarks, they

are extremely competitive, either on par or even beating $$$ closed-source libraries.

...

http://eigen.tuxfamily.org/index.php?title=Benchmark <

http://eigen.tuxfamily.org/index.php?title=Benchmark>

...

Eigen tracks its own performance, so you don't need to worry about it

getting slower, but perhaps the others have gotten faster in the meantime.

...

http://eigen.tuxfamily.org/index.php?title=Performance_monitoring <

http://eigen.tuxfamily.org/index.php?title=Performance_monitoring>

...

I used the library in projects and it is very convenient. You just

write your expressions as you would on paper and let Eigen generate the fastest possible code out of that. I only dislike that Eigen does not play well with "auto" since C++11, because they use the assignment to a matrix or vector to trigger the evaluation of the expression template.

...

I haven't done it myself, but Eigen seems to have a good strategy for

adding new features, too. People can start to develop their stuff in an "unsupported" subdirectory, which is not meant for production, but the code is nevertheless distributed with Eigen. This helps to exposes the experimental code to more adventurous users. Eventually, a project that passed the test of time can move from "unsupported" to the main library.

...

Best regards, Hans

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/

mailman/listinfo.cgi/boost --- end quoted text ---

-- Karen Shaeffer The subconscious mind is driven by your deeply Neuralscape Services held beliefs -- not your deeply held desires.

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

wt., 23 sty 2018 o 14:52 użytkownik Hans Dembinski napisał:

On 22. Jan 2018, at 22:50, Marcin Copik via Boost wrote:

I've done a lot of linear algebra benchmarking in the last couple of months and I believe there are three high-performance C++ linear algebra libraries: Eigen, already mentioned by Hans, Armadillo, and Blaze. Blaze developers present several benchmarks on their website: https://bitbucket.org/blaze-lib/blaze/wiki/Benchmarks

It looks like whoever makes the benchmarks wins ;)

Since Eigen3 does much worse in these benchmarks, I wonder whether the comparison is fair. I cannot imagine a good reason why Eigen is much faster than uBlas in their own benchmarks and much slower than uBlas in the benchmarks shown by Blaze.

I'm surprised why Eigen performs so poorly with BLAS-1 functionalities. Blaze benchmarks are in the repository and I can't see an easy answer how the timing could be skewed against Eigen: https://bitbucket.org/blaze-lib/blaze/src/ed0d6f15559e6019d1b10d7010b753182a... To me it looks like a vectorization which does not utilize AVX capabilities.

Best regards, Hans

On 22. Jan 2018, at 23:07, Marcin Copik wrote:

pon., 22 sty 2018 o 11:16 użytkownik Hans Dembinski via Boost mailto:boost@lists.boost.org> napisał: Hi David, Rajaditya, Artyom, Shikhar,

...

On 21. Jan 2018, at 13:00, David Bellot via Boost mailto:boost@lists.boost.org> wrote:

I used the library in projects and it is very convenient. You just write your expressions as you would on paper and let Eigen generate the fastest possible code out of that. I only dislike that Eigen does not play well with "auto" since C++11, because they use the assignment to a matrix or vector to trigger the evaluation of the expression template.

As far as I know, direct usage of auto is not possible in any Expression Templates library since the assigment triggers an evaluation, as you already noticed. It's a minor inconviencen since it requires from the you user to know if final type of an expression should be a matrix or a vector. It might be a larger problem in a library which provides specialized types for matrices of different shapes, such as: symmetric, upper/lower triangular, diagonal. Such types are benefitial since it helps the library to find a more optimized kernel, e.g. use trmm instead of gemm for a matrix-matrix product if one of operands is lower/upper triangular. Then, the return type of an expression depends on types of input matrices and the actual computation and one should not expect from the user to be able to guess it correctly. As far as I know, only Blaze implements specialized types called adaptors (Eigen has views but their applicability is rather limited).

That is a good point. In Eigen, you can use .eval(), see https://eigen.tuxfamily.org/dox/TopicPitfalls.html Example: MatrixXd A, B; auto C_bad = A * B; // this is an expression template, not to be used auto C_good = (A * B).eval(); // this is a matrix type, eval() can chose the best type to represent the result

Fortunately, there should be an easy solution available in each library. Each ET library should have a return type implemented in each expression node. Then, it is possible to implement a simple evaluate function: template<typename Expr> typename Expr::expression_type evaluate(Expr && expr) { return typename Expr::expression_type(expr); } It should always enforce the evaluation of an expression and one can safely return an expression from a function without knowing the actual type.

Agreed. I am not sure whether a free function or a method call is better. Apparently, the Eigen guys went for the latter. Best regards, Hans