Repository: systemml Updated Branches: refs/heads/master bb53c6b46 -> 79db07968
[SYSTEMML-2241] Fine tuning ultra-sparse matrix mult selection This patch further tunes the selection of ultra-sparse matrix mult block operations by (1) using ultra-sparse operations (with sparse output) for outer-product like operations that are known to result in sparse outputs, and (2) avoid unnecessary sparse-dense conversion for operations with colunm vector outputs. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/79db0796 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/79db0796 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/79db0796 Branch: refs/heads/master Commit: 79db07968d3f5425e6ff27c024e0260f13077b52 Parents: bb53c6b Author: Matthias Boehm <mboe...@gmail.com> Authored: Sat Apr 14 15:25:00 2018 -0700 Committer: Matthias Boehm <mboe...@gmail.com> Committed: Sat Apr 14 16:27:45 2018 -0700 ---------------------------------------------------------------------- .../instructions/spark/MapmmSPInstruction.java | 36 ++++++-------------- .../runtime/matrix/data/LibMatrixMult.java | 14 ++++++-- .../sysml/runtime/matrix/data/MatrixBlock.java | 4 ++- .../matrix/data/OperationsOnMatrixValues.java | 6 ++-- 4 files changed, 27 insertions(+), 33 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/79db0796/src/main/java/org/apache/sysml/runtime/instructions/spark/MapmmSPInstruction.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/instructions/spark/MapmmSPInstruction.java b/src/main/java/org/apache/sysml/runtime/instructions/spark/MapmmSPInstruction.java index d54ccf8..21c1be3 100644 --- a/src/main/java/org/apache/sysml/runtime/instructions/spark/MapmmSPInstruction.java +++ b/src/main/java/org/apache/sysml/runtime/instructions/spark/MapmmSPInstruction.java @@ -431,43 +431,27 @@ public class MapmmSPInstruction extends BinarySPInstruction { throws Exception { ArrayList<Tuple2<MatrixIndexes, MatrixBlock>> ret = new ArrayList<>(); - MatrixIndexes ixIn = arg0._1(); MatrixBlock blkIn = arg0._2(); - if( _type == CacheType.LEFT ) - { + if( _type == CacheType.LEFT ) { //for all matching left-hand-side blocks int len = _pbc.getNumRowBlocks(); - for( int i=1; i<=len; i++ ) - { + for( int i=1; i<=len; i++ ) { MatrixBlock left = _pbc.getBlock(i, (int)ixIn.getRowIndex()); - MatrixIndexes ixOut = new MatrixIndexes(); - MatrixBlock blkOut = new MatrixBlock(); - - //execute matrix-vector mult - OperationsOnMatrixValues.performAggregateBinary( - new MatrixIndexes(i,ixIn.getRowIndex()), left, ixIn, blkIn, ixOut, blkOut, _op); - - ret.add(new Tuple2<>(ixOut, blkOut)); + MatrixBlock blkOut = OperationsOnMatrixValues + .performAggregateBinaryIgnoreIndexes(left, blkIn, new MatrixBlock(), _op); + ret.add(new Tuple2<>(new MatrixIndexes(i, ixIn.getColumnIndex()), blkOut)); } } - else //if( _type == CacheType.RIGHT ) - { + else { //RIGHT //for all matching right-hand-side blocks int len = _pbc.getNumColumnBlocks(); - for( int j=1; j<=len; j++ ) - { - //get the right hand side matrix + for( int j=1; j<=len; j++ ) { MatrixBlock right = _pbc.getBlock((int)ixIn.getColumnIndex(), j); - MatrixIndexes ixOut = new MatrixIndexes(); - MatrixBlock blkOut = new MatrixBlock(); - - //execute matrix-vector mult - OperationsOnMatrixValues.performAggregateBinary( - ixIn, blkIn, new MatrixIndexes(ixIn.getColumnIndex(),j), right, ixOut, blkOut, _op); - - ret.add(new Tuple2<>(ixOut, blkOut)); + MatrixBlock blkOut = OperationsOnMatrixValues + .performAggregateBinaryIgnoreIndexes(blkIn, right, new MatrixBlock(), _op); + ret.add(new Tuple2<>(new MatrixIndexes(ixIn.getRowIndex(), j), blkOut)); } } http://git-wip-us.apache.org/repos/asf/systemml/blob/79db0796/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 b36e306..91adc93 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 @@ -1490,7 +1490,8 @@ public class LibMatrixMult */ private static void matrixMultUltraSparse(MatrixBlock m1, MatrixBlock m2, MatrixBlock ret, int rl, int ru) { final boolean leftUS = m1.isUltraSparse() - || (m1.isUltraSparse(false) && !m2.isUltraSparse()); + || (m1.isUltraSparse(false) && !m2.isUltraSparse()) + || (m1.sparse && !m2.sparse); final int m = m1.rlen; final int cd = m1.clen; final int n = m2.clen; @@ -3693,14 +3694,21 @@ public class LibMatrixMult } public static boolean isUltraSparseMatrixMult(MatrixBlock m1, MatrixBlock m2) { + if( m2.clen == 1 ) //mv always dense + return false; //note: ultra-sparse matrix mult implies also sparse outputs, hence we need //to be conservative an cannot use this for all ultra-sparse matrices. + double outSp = OptimizerUtils.getMatMultSparsity( + m1.getSparsity(), m2.getSparsity(), m1.rlen, m1.clen, m2.clen, true); return (m1.isUltraSparse() || m2.isUltraSparse()) //base case || (m1.isUltraSparsePermutationMatrix() && 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); + && outSp < MatrixBlock.ULTRA_SPARSITY_TURN_POINT2) + || (m1.getSparsity() < MatrixBlock.ULTRA_SPARSITY_TURN_POINT2 + && m1.getNonZeros() < MatrixBlock.ULTRA_SPARSE_BLOCK_NNZ + && m1.getLength()+m2.getLength() < (long)m1.rlen*m2.clen + && outSp < MatrixBlock.SPARSITY_TURN_POINT); } private static MatrixBlock prepMatrixMultRightInput( MatrixBlock m1, MatrixBlock m2 ) { http://git-wip-us.apache.org/repos/asf/systemml/blob/79db0796/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 ce9ea3c..3b6d682 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 @@ -101,6 +101,7 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab //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_POINT2 = 0.0004; + public static final int ULTRA_SPARSE_BLOCK_NNZ = 40; //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 @@ -874,7 +875,8 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab public boolean isUltraSparse(boolean checkNnz) { double sp = ((double)nonZeros/rlen)/clen; //check for sparse representation in order to account for vectors in dense - return sparse && sp<ULTRA_SPARSITY_TURN_POINT && (!checkNnz || nonZeros<40); + return sparse && sp<ULTRA_SPARSITY_TURN_POINT + && (!checkNnz || nonZeros<ULTRA_SPARSE_BLOCK_NNZ); } public boolean isUltraSparsePermutationMatrix() { http://git-wip-us.apache.org/repos/asf/systemml/blob/79db0796/src/main/java/org/apache/sysml/runtime/matrix/data/OperationsOnMatrixValues.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/OperationsOnMatrixValues.java b/src/main/java/org/apache/sysml/runtime/matrix/data/OperationsOnMatrixValues.java index 3715404..a698e46 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/OperationsOnMatrixValues.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/OperationsOnMatrixValues.java @@ -217,15 +217,15 @@ public class OperationsOnMatrixValues valueIn.aggregateUnaryOperations(op, valueOut, brlen, bclen, indexesIn); } - public static void performAggregateBinary(MatrixIndexes indexes1, MatrixBlock value1, MatrixIndexes indexes2, MatrixBlock value2, + public static MatrixBlock performAggregateBinary(MatrixIndexes indexes1, MatrixBlock value1, MatrixIndexes indexes2, MatrixBlock value2, MatrixIndexes indexesOut, MatrixBlock valueOut, AggregateBinaryOperator op) { //compute output index indexesOut.setIndexes(indexes1.getRowIndex(), indexes2.getColumnIndex()); //perform on the value if( value2 instanceof CompressedMatrixBlock ) - value2.aggregateBinaryOperations(value1, value2, valueOut, op); + return value2.aggregateBinaryOperations(value1, value2, valueOut, op); else //default - value1.aggregateBinaryOperations(indexes1, value1, indexes2, value2, valueOut, op); + return value1.aggregateBinaryOperations(indexes1, value1, indexes2, value2, valueOut, op); } public static MatrixBlock performAggregateBinaryIgnoreIndexes(MatrixBlock value1, MatrixBlock value2,
