Complete implementation of LSKGES

rileyjmurray commented 1 year ago

This PR supersedes PR #26. Big changes include:

Added support for long-axis-sparse sketching operators, or "LASOs". Prior to this PR, we only supported short-axis-sparse operators, or "SASOs."
Added support for transposes on the sketching operator and data matrix.
Added support for "lifting" instead of just "sketching" with LSKGES and LSKGE3. More on this below.
LSKGES previously had a helper function for sketching row-major data from the left with a (non-transposed) SASO. This PR removes that function. More on this below.
Burlen's changes in PR #28 for improved templating of RNGState structs.

Lifting versus sketching

We used to have a requirement that B = op(S) * op(A) had fewer rows than op(A). That requirement is valid if we only allow proper sketching. However, there are situations where we need to "lift" the result of a sketch back into the higher-dimensional space, in the sense that B = op(S) * op(A) has more rows than op(A).

Removing specialized row-major sketching function

The new implementation for applying a CSC-like sketching operator accesses data with appropriate strides. I did this because it substantially simplified the case handling for SASOs, LASOs, transposes thereof, row-major and column-major data, and (eventually) right-sketching. However, accessing data via strides does introduce a performance penalty, so we should look at restoring the functionality I removed in the near future.

rileyjmurray commented 1 year ago

@burlen I'm getting an error when I try to compile locally on my M1 MacBook Pro. Output is below. Any idea what the issue could be?

(base) Rileys-MacBook-Pro:RandBLAS-build riley$ make
[ 20%] Building CXX object test/CMakeFiles/RandBLAS_tests.dir/test_sparse.cc.o
In file included from /Users/riley/BALLISTIC_RNLA/randla/RandBLAS/test/test_sparse.cc:1:
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:238:19: error: reference to local binding 'c' declared in enclosing function 'RandBLAS::dense::fill_rmat'
        auto cc = c;
                  ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:215:11: note: 'c' declared here
    auto [c, k] = seed;
          ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:246:45: error: reference to local binding 'k' declared in enclosing function 'RandBLAS::dense::fill_rmat'
            auto rv = OP::generate(rng, cc, k);
                                            ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:215:14: note: 'k' declared here
    auto [c, k] = seed;
             ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:222:39: error: expected variable name
    #pragma omp parallel firstprivate(c, k)
                                      ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:285:20: note: in instantiation of function template specialization 'RandBLAS::dense::fill_rmat<double, r123::Philox4x32_R<10>, r123ext::boxmul>' requested here
            return fill_rmat<T,RNG,r123ext::boxmul>(D.n_rows, D.n_cols, buff, state);
                   ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/test/test_sparse.cc:431:26: note: in instantiation of function template specialization 'RandBLAS::dense::fill_buff<double, r123::Philox4x32_R<10>>' requested here
        RandBLAS::dense::fill_buff(A0.data(), DA0, RandBLAS::base::RNGState{ctr_A0, seed_A0});
                         ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/test/test_sparse.cc:819:9: note: in instantiation of function template specialization 'TestLSKGES::submatrix_A<double>' requested here
        submatrix_A<double>(
        ^
In file included from /Users/riley/BALLISTIC_RNLA/randla/RandBLAS/test/test_sparse.cc:1:
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:222:42: error: expected variable name
    #pragma omp parallel firstprivate(c, k)
                                         ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:238:19: error: reference to local binding 'c' declared in enclosing function 'RandBLAS::dense::fill_rmat<double, r123::Philox4x32_R<10>, r123ext::boxmul>'
        auto cc = c;
                  ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:215:11: note: 'c' declared here
    auto [c, k] = seed;
          ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:246:45: error: reference to local binding 'k' declared in enclosing function 'RandBLAS::dense::fill_rmat<double, r123::Philox4x32_R<10>, r123ext::boxmul>'
            auto rv = OP::generate(rng, cc, k);
                                            ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:215:14: note: 'k' declared here
    auto [c, k] = seed;
             ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:222:39: error: expected variable name
    #pragma omp parallel firstprivate(c, k)
                                      ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:287:20: note: in instantiation of function template specialization 'RandBLAS::dense::fill_rmat<double, r123::Philox4x32_R<10>, r123ext::uneg11>' requested here
            return fill_rmat<T,RNG,r123ext::uneg11>(D.n_rows, D.n_cols, buff, state);
                   ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/test/test_sparse.cc:431:26: note: in instantiation of function template specialization 'RandBLAS::dense::fill_buff<double, r123::Philox4x32_R<10>>' requested here
        RandBLAS::dense::fill_buff(A0.data(), DA0, RandBLAS::base::RNGState{ctr_A0, seed_A0});
                         ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/test/test_sparse.cc:819:9: note: in instantiation of function template specialization 'TestLSKGES::submatrix_A<double>' requested here
        submatrix_A<double>(
        ^
In file included from /Users/riley/BALLISTIC_RNLA/randla/RandBLAS/test/test_sparse.cc:1:
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:222:42: error: expected variable name
    #pragma omp parallel firstprivate(c, k)
                                         ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:238:19: error: reference to local binding 'c' declared in enclosing function 'RandBLAS::dense::fill_rmat<double, r123::Philox4x32_R<10>, r123ext::uneg11>'
        auto cc = c;
                  ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:215:11: note: 'c' declared here
    auto [c, k] = seed;
          ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:246:45: error: reference to local binding 'k' declared in enclosing function 'RandBLAS::dense::fill_rmat<double, r123::Philox4x32_R<10>, r123ext::uneg11>'
            auto rv = OP::generate(rng, cc, k);
                                            ^
/Users/riley/BALLISTIC_RNLA/randla/RandBLAS/RandBLAS/../RandBLAS/dense.hh:215:14: note: 'k' declared here
    auto [c, k] = seed;
             ^
10 errors generated.
make[2]: *** [test/CMakeFiles/RandBLAS_tests.dir/test_sparse.cc.o] Error 1
make[1]: *** [test/CMakeFiles/RandBLAS_tests.dir/all] Error 2
make: *** [all] Error 2
(base) Rileys-MacBook-Pro:RandBLAS-build riley$

The code is the latest on the finish-lskges branch.

burlen commented 1 year ago

@rileyjmurray fixed in a commit I just pushed here. it's due to how LLVM clang implements OpenMP using lambdas which in C++17 don't capture structured bindings. In C++20 they do, so our work around may not be needed when we update to 20.

rileyjmurray commented 1 year ago

All code-based TODOs are resolved! Almost ready to merge.

burlen commented 1 year ago

@rileyjmurray On macos the following tests are failing. Note: macos w/ Apple's clang does not have OpenMP support. These may be test tolerance issues though.

     11 - TestLSKGES.sketch_saso_rowMajor_oneThread (Failed)
     13 - TestLSKGES.sketch_saso_rowMajor_FourThreads (Failed)

rileyjmurray commented 1 year ago

@rileyjmurray On macos the following tests are failing. Note: macos w/ Apple's clang does not have OpenMP support. These may be test tolerance issues though.
   11 - TestLSKGES.sketch_saso_rowMajor_oneThread (Failed)
   13 - TestLSKGES.sketch_saso_rowMajor_FourThreads (Failed)

I've looked at this, and it is indeed a tolerance issue. But the tolerances are already set in a generous way so it's odd that they're failing. I'm inclined to merge as-is and have us investigate in more detail later. I'll try some minor changes before merging though.

rileyjmurray commented 1 year ago

Alright, the numerical precision issues in

 11 - TestLSKGES.sketch_saso_rowMajor_oneThread (Failed)
 13 - TestLSKGES.sketch_saso_rowMajor_FourThreads (Failed)

are persisting. I'm going to merge as-is and open an issue for us to investigate more.

BallisticLA / RandBLAS

Complete implementation of LSKGES #27

Lifting versus sketching

Removing specialized row-major sketching function