Repository: systemml Updated Branches: refs/heads/master 53175c00e -> d16cc7cf8
[SYSTEMML-819] Fix missing matrix-matrix mult over compressed matrices So far, we supported matrix-vector, vector-matrix, tsmm, mmchain, unary aggregates, append, order statistics and scalar operations over compressed matrices. All other operations decompress compressed matrices and perform uncompressed operations. However, matrix-matrix multiplications failed with exceptions due to a shared code path with matrix-vector and vector-matrix multiplications. This patch fixes this issue by general support for matrix-matrix multiplications over compressed matrices. Right now, these operations are emulated with repeated matrix-vector or vector-matrix multiplications (similar to tsmm), which does not require decompression but is NOT optimized for performance yet. Also in case there are two compressed inputs, one of the inputs is still decompressed. However, this already enables algorithms such as Kmeans and Mlogreg with more than two classes over compressed matrices. For distributed operations, the repeated matrix-vector operators are not too bad because individual compressed blocks easily fit int L3 cache. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/ff8bb58f Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/ff8bb58f Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/ff8bb58f Branch: refs/heads/master Commit: ff8bb58fe8bcec711852c42245542c9955052a5c Parents: 53175c0 Author: Matthias Boehm <[email protected]> Authored: Sun Feb 25 23:23:57 2018 -0800 Committer: Matthias Boehm <[email protected]> Committed: Sun Feb 25 23:23:57 2018 -0800 ---------------------------------------------------------------------- .../runtime/compress/CompressedMatrixBlock.java | 72 +++-- .../sysml/runtime/matrix/data/MatrixBlock.java | 4 + .../compress/LargeMatrixMatrixMultTest.java | 282 +++++++++++++++++++ .../functions/compress/ZPackageSuite.java | 1 + 4 files changed, 340 insertions(+), 19 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/ff8bb58f/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java b/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java index edba26e..c5fbd35 100644 --- a/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java +++ b/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java @@ -1095,25 +1095,25 @@ public class CompressedMatrixBlock extends MatrixBlock implements Externalizable } @Override - public MatrixBlock aggregateBinaryOperations(MatrixBlock mv1, MatrixBlock mv2, MatrixBlock ret, AggregateBinaryOperator op) + public MatrixBlock aggregateBinaryOperations(MatrixBlock m1, MatrixBlock m2, MatrixBlock ret, AggregateBinaryOperator op) throws DMLRuntimeException { //call uncompressed matrix mult if necessary if( !isCompressed() ) { - return super.aggregateBinaryOperations(mv1, mv2, ret, op); + return super.aggregateBinaryOperations(m1, m2, ret, op); } //multi-threaded mm of single uncompressed colgroup if( isSingleUncompressedGroup() ){ MatrixBlock tmp = ((ColGroupUncompressed)_colGroups.get(0)).getData(); - return tmp.aggregateBinaryOperations(this==mv1?tmp:mv1, this==mv2?tmp:mv2, ret, op); + return tmp.aggregateBinaryOperations(this==m1?tmp:m1, this==m2?tmp:m2, ret, op); } Timing time = LOG.isDebugEnabled() ? new Timing(true) : null; //setup meta data (dimensions, sparsity) - int rl = mv1.getNumRows(); - int cl = mv2.getNumColumns(); + int rl = m1.getNumRows(); + int cl = m2.getNumColumns(); //create output matrix block if( ret==null ) @@ -1122,25 +1122,59 @@ public class CompressedMatrixBlock extends MatrixBlock implements Externalizable ret.reset(rl, cl, false, rl*cl); //compute matrix mult - if( mv1.getNumRows()>1 && mv2.getNumColumns()==1 ) { //MV right - CompressedMatrixBlock cmb = (CompressedMatrixBlock)mv1; - MatrixBlock mb = (MatrixBlock) mv2; + if( m1.getNumRows()>1 && m2.getNumColumns()==1 ) { //MV right + CompressedMatrixBlock cmb = (CompressedMatrixBlock)m1; if( op.getNumThreads()>1 ) - cmb.rightMultByVector(mb, ret, op.getNumThreads()); + cmb.rightMultByVector(m2, ret, op.getNumThreads()); else - cmb.rightMultByVector(mb, ret); + cmb.rightMultByVector(m2, ret); } - else if( mv1.getNumRows()==1 && mv2.getNumColumns()>1 ) { //MV left - MatrixBlock mb = (MatrixBlock) mv1; + else if( m1.getNumRows()==1 && m2.getNumColumns()>1 ) { //MV left if( op.getNumThreads()>1 ) - leftMultByVectorTranspose(_colGroups, mb, ret, false, op.getNumThreads()); + leftMultByVectorTranspose(_colGroups, m1, ret, false, op.getNumThreads()); else - leftMultByVectorTranspose(_colGroups, mb, ret, false, true); - } - else { - //NOTE: we could decompress and invoke super.aggregateBinary but for now - //we want to have an eager fail if this happens - throw new DMLRuntimeException("Unsupported matrix-matrix multiplication over compressed matrix block."); + leftMultByVectorTranspose(_colGroups, m1, ret, false, true); + } + else { //MM + //prepare the other input (including decompression if necessary) + boolean right = (m1 == this); + MatrixBlock that = right ? m2 : m1; + if( that instanceof CompressedMatrixBlock ) { + that = ((CompressedMatrixBlock)that).isCompressed() ? + ((CompressedMatrixBlock)that).decompress() : that; + } + + //transpose for sequential repeated column access + if( right ) { + that = LibMatrixReorg.transpose(that, new MatrixBlock(that.getNumColumns(), + that.getNumRows(), that.isInSparseFormat()), op.getNumThreads()); + } + + MatrixBlock tmpIn = new MatrixBlock(1, that.getNumColumns(), false).allocateBlock(); + MatrixBlock tmpOut = new MatrixBlock(right?rl:1, right?1:cl, false).allocateBlock(); + if( right ) { //MM right + for(int i=0; i<that.getNumRows(); i++) { //on transpose + tmpIn = that.sliceOperations(i, i, 0, that.getNumColumns()-1, tmpIn); + MatrixBlock tmpIn2 = LibMatrixReorg.transpose(tmpIn, //meta data op + new MatrixBlock(tmpIn.getNumColumns(), tmpIn.getNumRows(), false)); + tmpOut.reset(tmpOut.getNumRows(), tmpOut.getNumColumns()); + if( op.getNumThreads()>1 ) + rightMultByVector(tmpIn2, tmpOut, op.getNumThreads()); + else + rightMultByVector(tmpIn2, tmpOut); + ret.leftIndexingOperations(tmpOut, 0, ret.getNumRows()-1, i, i, ret, UpdateType.INPLACE); + } + } + else { // MM left + for(int i=0; i<that.getNumRows(); i++) { + tmpIn = that.sliceOperations(i, i, 0, that.getNumColumns()-1, tmpIn); + if( op.getNumThreads()>1 ) + leftMultByVectorTranspose(_colGroups, tmpIn, tmpOut, false, op.getNumThreads()); + else + leftMultByVectorTranspose(_colGroups, tmpIn, tmpOut, false, true); + ret.leftIndexingOperations(tmpOut, i, i, 0, ret.getNumColumns()-1, ret, UpdateType.INPLACE); + } + } } if( LOG.isDebugEnabled() ) http://git-wip-us.apache.org/repos/asf/systemml/blob/ff8bb58f/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 6d38a91..15e37e8 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 @@ -483,6 +483,10 @@ public class MatrixBlock extends MatrixValue implements CacheBlock, Externalizab return (rlen == 1 || clen == 1); } + public long getLength() { + return (long)rlen * clen; + } + @Override public boolean isEmpty() { return isEmptyBlock(false); http://git-wip-us.apache.org/repos/asf/systemml/blob/ff8bb58f/src/test/java/org/apache/sysml/test/integration/functions/compress/LargeMatrixMatrixMultTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/sysml/test/integration/functions/compress/LargeMatrixMatrixMultTest.java b/src/test/java/org/apache/sysml/test/integration/functions/compress/LargeMatrixMatrixMultTest.java new file mode 100644 index 0000000..06c513a --- /dev/null +++ b/src/test/java/org/apache/sysml/test/integration/functions/compress/LargeMatrixMatrixMultTest.java @@ -0,0 +1,282 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.sysml.test.integration.functions.compress; + +import org.apache.sysml.runtime.compress.BitmapEncoder; +import org.apache.sysml.runtime.compress.CompressedMatrixBlock; +import org.apache.sysml.runtime.functionobjects.Multiply; +import org.apache.sysml.runtime.functionobjects.Plus; +import org.apache.sysml.runtime.matrix.data.MatrixBlock; +import org.apache.sysml.runtime.matrix.operators.AggregateBinaryOperator; +import org.apache.sysml.runtime.matrix.operators.AggregateOperator; +import org.apache.sysml.runtime.util.DataConverter; +import org.apache.sysml.test.integration.AutomatedTestBase; +import org.apache.sysml.test.utils.TestUtils; +import org.junit.Test; + +public class LargeMatrixMatrixMultTest extends AutomatedTestBase +{ + private static final int rows = 5*BitmapEncoder.BITMAP_BLOCK_SZ; + private static final int cols = 20; + private static final int cols2 = 3; + private static final double sparsity1 = 0.9; + private static final double sparsity2 = 0.1; + private static final double sparsity3 = 0.0; + + public enum MultType { + LEFT, + RIGHT, + } + + public enum SparsityType { + DENSE, + SPARSE, + EMPTY, + } + + public enum ValueType { + RAND, //UC + CONST, //RLE + RAND_ROUND_OLE, //OLE + RAND_ROUND_DDC, //RLE + } + + @Override + public void setUp() { + + } + + @Test + public void testDenseRandDataCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.DENSE, ValueType.RAND, true); + } + + @Test + public void testSparseRandDataCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.SPARSE, ValueType.RAND, true); + } + + @Test + public void testEmptyCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.EMPTY, ValueType.RAND, true); + } + + @Test + public void testDenseRoundRandDataOLECompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.DENSE, ValueType.RAND_ROUND_OLE, true); + } + + @Test + public void testSparseRoundRandDataOLECompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.SPARSE, ValueType.RAND_ROUND_OLE, true); + } + + @Test + public void testDenseRoundRandDataDDCCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.DENSE, ValueType.RAND_ROUND_DDC, true); + } + + @Test + public void testSparseRoundRandDataDDCCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.SPARSE, ValueType.RAND_ROUND_DDC, true); + } + + @Test + public void testDenseConstantDataCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.DENSE, ValueType.CONST, true); + } + + @Test + public void testSparseConstDataCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.SPARSE, ValueType.CONST, true); + } + + @Test + public void testDenseRandDataNoCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.DENSE, ValueType.RAND, false); + } + + @Test + public void testSparseRandDataNoCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.SPARSE, ValueType.RAND, false); + } + + @Test + public void testEmptyNoCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.EMPTY, ValueType.RAND, false); + } + + @Test + public void testDenseRoundRandDataOLENoCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.DENSE, ValueType.RAND_ROUND_OLE, false); + } + + @Test + public void testSparseRoundRandDataOLENoCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.SPARSE, ValueType.RAND_ROUND_OLE, false); + } + + @Test + public void testDenseConstDataNoCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.DENSE, ValueType.CONST, false); + } + + @Test + public void testSparseConstDataNoCompressionRight() { + runMatrixVectorMultTest(MultType.RIGHT, SparsityType.SPARSE, ValueType.CONST, false); + } + + @Test + public void testDenseRandDataCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.DENSE, ValueType.RAND, true); + } + + @Test + public void testSparseRandDataCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.SPARSE, ValueType.RAND, true); + } + + @Test + public void testEmptyCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.EMPTY, ValueType.RAND, true); + } + + @Test + public void testDenseRoundRandDataOLECompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.DENSE, ValueType.RAND_ROUND_OLE, true); + } + + @Test + public void testSparseRoundRandDataOLECompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.SPARSE, ValueType.RAND_ROUND_OLE, true); + } + + @Test + public void testDenseRoundRandDataDDCCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.DENSE, ValueType.RAND_ROUND_DDC, true); + } + + @Test + public void testSparseRoundRandDataDDCCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.SPARSE, ValueType.RAND_ROUND_DDC, true); + } + + @Test + public void testDenseConstantDataCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.DENSE, ValueType.CONST, true); + } + + @Test + public void testSparseConstDataCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.SPARSE, ValueType.CONST, true); + } + + @Test + public void testDenseRandDataNoCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.DENSE, ValueType.RAND, false); + } + + @Test + public void testSparseRandDataNoCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.SPARSE, ValueType.RAND, false); + } + + @Test + public void testEmptyNoCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.EMPTY, ValueType.RAND, false); + } + + @Test + public void testDenseRoundRandDataOLENoCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.DENSE, ValueType.RAND_ROUND_OLE, false); + } + + @Test + public void testSparseRoundRandDataOLENoCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.SPARSE, ValueType.RAND_ROUND_OLE, false); + } + + @Test + public void testDenseConstDataNoCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.DENSE, ValueType.CONST, false); + } + + @Test + public void testSparseConstDataNoCompressionLeft() { + runMatrixVectorMultTest(MultType.LEFT, SparsityType.SPARSE, ValueType.CONST, false); + } + + private static void runMatrixVectorMultTest(MultType mtype, SparsityType sptype, ValueType vtype, boolean compress) + { + try + { + //prepare sparsity for input data + double sparsity = -1; + switch( sptype ){ + case DENSE: sparsity = sparsity1; break; + case SPARSE: sparsity = sparsity2; break; + case EMPTY: sparsity = sparsity3; break; + } + + //generate input data + double min = (vtype==ValueType.CONST)? 10 : -10; + double[][] input = TestUtils.generateTestMatrix(rows, cols, min, 10, sparsity, 7); + if( vtype==ValueType.RAND_ROUND_OLE || vtype==ValueType.RAND_ROUND_DDC ) { + CompressedMatrixBlock.ALLOW_DDC_ENCODING = (vtype==ValueType.RAND_ROUND_DDC); + input = TestUtils.round(input); + } + + boolean right = (mtype == MultType.RIGHT); + MatrixBlock mb = DataConverter.convertToMatrixBlock(input); + MatrixBlock vect = DataConverter.convertToMatrixBlock(right? + TestUtils.generateTestMatrix(cols, cols2, -1, 1, 1.0, 3) : + TestUtils.generateTestMatrix(cols2, rows, -1, 1, 1.0, 3)); + + //compress given matrix block + CompressedMatrixBlock cmb = new CompressedMatrixBlock(mb); + if( compress ) + cmb.compress(); + + //matrix-vector uncompressed + AggregateOperator aop = new AggregateOperator(0, Plus.getPlusFnObject()); + AggregateBinaryOperator abop = new AggregateBinaryOperator(Multiply.getMultiplyFnObject(), aop); + MatrixBlock ret1 = right ? + mb.aggregateBinaryOperations(mb, vect, new MatrixBlock(), abop) : + vect.aggregateBinaryOperations(vect, mb, new MatrixBlock(), abop); + + //matrix-vector compressed + MatrixBlock ret2 = right ? + cmb.aggregateBinaryOperations(cmb, vect, new MatrixBlock(), abop) : + cmb.aggregateBinaryOperations(vect, cmb, new MatrixBlock(), abop); + + //compare result with input + double[][] d1 = DataConverter.convertToDoubleMatrix(ret1); + double[][] d2 = DataConverter.convertToDoubleMatrix(ret2); + TestUtils.compareMatrices(d1, d2, + right?rows:cols2, right?cols2:cols, 0.0000001); + } + catch(Exception ex) { + throw new RuntimeException(ex); + } + finally { + CompressedMatrixBlock.ALLOW_DDC_ENCODING = true; + } + } +} http://git-wip-us.apache.org/repos/asf/systemml/blob/ff8bb58f/src/test_suites/java/org/apache/sysml/test/integration/functions/compress/ZPackageSuite.java ---------------------------------------------------------------------- diff --git a/src/test_suites/java/org/apache/sysml/test/integration/functions/compress/ZPackageSuite.java b/src/test_suites/java/org/apache/sysml/test/integration/functions/compress/ZPackageSuite.java index a61cbbd..cd24cb5 100644 --- a/src/test_suites/java/org/apache/sysml/test/integration/functions/compress/ZPackageSuite.java +++ b/src/test_suites/java/org/apache/sysml/test/integration/functions/compress/ZPackageSuite.java @@ -43,6 +43,7 @@ import org.junit.runners.Suite; CompressedLinregCG.class, CompressedSerializationTest.class, LargeCompressionTest.class, + LargeMatrixMatrixMultTest.class, LargeMatrixVectorMultTest.class, LargeParMatrixVectorMultTest.class, LargeParUnaryAggregateTest.class,
