Repository: systemml Updated Branches: refs/heads/master ca615ca10 -> ec0448850
[SYSTEMML-2241] Improved selection of ultra-sparse matrix multiply ops This patch improves the selection of ultra-sparse matrix multiply block operations (used in all backends) for scenarios where neither of the inputs qualifies for pure ultra-sparse operations but the output sparsity is known to satisfy the ultra-sparse sparsity threshold. Since this ultra-sparse operation is the only matrix multiply operation which allocates the output in sparse, this patch has the potential to change the asymptotic behavior. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/f8229506 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/f8229506 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/f8229506 Branch: refs/heads/master Commit: f8229506749d7e9525b91dfadf247a6d7a52c24e Parents: ca615ca Author: Matthias Boehm <mboe...@gmail.com> Authored: Fri Apr 13 22:51:01 2018 -0700 Committer: Matthias Boehm <mboe...@gmail.com> Committed: Fri Apr 13 22:51:01 2018 -0700 ---------------------------------------------------------------------- .../org/apache/sysml/runtime/matrix/data/LibMatrixMult.java | 5 ++++- .../java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java | 3 ++- 2 files changed, 6 insertions(+), 2 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/f8229506/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixMult.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixMult.java b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixMult.java index adc955e..b36e306 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixMult.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixMult.java @@ -3697,7 +3697,10 @@ public class LibMatrixMult //to be conservative an cannot use this for all ultra-sparse matrices. return (m1.isUltraSparse() || m2.isUltraSparse()) //base case || (m1.isUltraSparsePermutationMatrix() - && OptimizerUtils.getSparsity(m2.rlen, m2.clen, m2.nonZeros)<1.0); + && OptimizerUtils.getSparsity(m2.rlen, m2.clen, m2.nonZeros)<1.0) + || ((m1.isUltraSparse(false) || m2.isUltraSparse(false)) + && OptimizerUtils.getMatMultSparsity(m1.getSparsity(), m2.getSparsity(), + m1.rlen, m1.clen, m2.clen, true) < MatrixBlock.ULTRA_SPARSITY_TURN_POINT2); } private static MatrixBlock prepMatrixMultRightInput( MatrixBlock m1, MatrixBlock m2 ) { http://git-wip-us.apache.org/repos/asf/systemml/blob/f8229506/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java index efe2365..ce9ea3c 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixBlock.java @@ -99,7 +99,8 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab //sparsity nnz threshold, based on practical experiments on space consumption and performance public static final double SPARSITY_TURN_POINT = 0.4; //sparsity threshold for ultra-sparse matrix operations (40nnz in a 1kx1k block) - public static final double ULTRA_SPARSITY_TURN_POINT = 0.00004; + public static final double ULTRA_SPARSITY_TURN_POINT = 0.00004; + public static final double ULTRA_SPARSITY_TURN_POINT2 = 0.0004; //default sparse block type: modified compressed sparse rows, for efficient incremental construction public static final SparseBlock.Type DEFAULT_SPARSEBLOCK = SparseBlock.Type.MCSR; //default sparse block type for update in place: compressed sparse rows, to prevent serialization