Repository: incubator-systemml Updated Branches: refs/heads/master 82d5c5f16 -> bcf4c901a
[SYSTEMML-378] Extended sparse block abstraction (reset/size) incl tests Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/bcf4c901 Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/bcf4c901 Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/bcf4c901 Branch: refs/heads/master Commit: bcf4c901a49ecd7c22957bcf161e097c35fb2c9c Parents: 82d5c5f Author: Matthias Boehm <[email protected]> Authored: Mon Jan 18 13:41:14 2016 -0800 Committer: Matthias Boehm <[email protected]> Committed: Mon Jan 18 13:41:14 2016 -0800 ---------------------------------------------------------------------- pom.xml | 1 + .../sysml/runtime/matrix/data/SparseBlock.java | 28 ++++ .../runtime/matrix/data/SparseBlockCOO.java | 21 +++ .../runtime/matrix/data/SparseBlockCSR.java | 22 +++ .../runtime/matrix/data/SparseBlockMCSR.java | 27 +++ .../functions/sparse/SparseBlockSize.java | 165 +++++++++++++++++++ .../functions/sparse/ZPackageSuite.java | 1 + 7 files changed, 265 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/bcf4c901/pom.xml ---------------------------------------------------------------------- diff --git a/pom.xml b/pom.xml index e459ab0..7ef6d1e 100644 --- a/pom.xml +++ b/pom.xml @@ -329,6 +329,7 @@ <includes> <include>**/integration/applications/**/*Suite.java</include> <include>**/integration/functions/gdfo/*Suite.java</include> + <include>**/integration/functions/sparse/*Suite.java</include> <include>**/integration/functions/**/*Test*.java</include> <include>**/integration/scalability/**/*Test.java</include> </includes> http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/bcf4c901/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlock.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlock.java b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlock.java index 478e900..9715fd3 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlock.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlock.java @@ -78,6 +78,12 @@ public abstract class SparseBlock implements Serializable * @return */ public abstract boolean isThreadSafe(); + + /** + * Clears the sparse block by deleting non-zero values. After this call + * size() is guaranteed to return 0. + */ + public abstract void reset(); /** * Get the number of non-zero values in the sparse block. @@ -95,6 +101,28 @@ public abstract class SparseBlock implements Serializable public abstract int size(int r); /** + * Get the number of non-zeros values in the row range + * of [rl, ru). + * + * @param rl row index starting at 0 + * @param ru column index starting at 0 + * @return + */ + public abstract long size(int rl, int ru); + + /** + * Get the number of non-zeros values in the row and column + * range of [rl/cl, ru/cu); + * + * @param rl + * @param ru + * @param cl + * @param cu + * @return + */ + public abstract long size(int rl, int ru, int cl, int cu); + + /** * Get information if row r is empty, i.e., does not contain non-zero * values. Equivalent to size(r)==0. Users should do this check if * it is unknown if the underlying row data structure is allocated. http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/bcf4c901/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java index d2c6731..0408dae 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCOO.java @@ -98,6 +98,11 @@ public class SparseBlockCOO extends SparseBlock return false; } + @Override + public void reset() { + _size = 0; + } + @Override public long size() { return _size; @@ -116,6 +121,22 @@ public class SparseBlockCOO extends SparseBlock cnt ++; return cnt; } + + @Override + public long size(int rl, int ru) { + return pos(ru) - pos(rl); + } + + public long size(int rl, int ru, int cl, int cu) { + long nnz = 0; + for(int i=rl; i<ru; i++) + if( !isEmpty(i) ) { + int start = posFIndexGTE(i, cl); + int end = posFIndexGTE(i, cu); + nnz += (start!=-1) ? (end-start) : 0; + } + return nnz; + } @Override public boolean isEmpty(int r) { http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/bcf4c901/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java index 1f7a890..d4acc01 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java @@ -100,6 +100,11 @@ public class SparseBlockCSR extends SparseBlock return false; } + @Override + public void reset() { + _size = 0; + } + @Override public long size() { return _size; @@ -109,8 +114,25 @@ public class SparseBlockCSR extends SparseBlock public int size(int r) { return _ptr[r+1] - _ptr[r]; } + + @Override + public long size(int rl, int ru) { + return _ptr[ru] - _ptr[rl]; + } @Override + public long size(int rl, int ru, int cl, int cu) { + long nnz = 0; + for(int i=rl; i<ru; i++) + if( !isEmpty(i) ) { + int start = posFIndexGTE(i, cl); + int end = posFIndexGTE(i, cu); + nnz += (start!=-1) ? (end-start) : 0; + } + return nnz; + } + + @Override public boolean isEmpty(int r) { return (_ptr[r+1] - _ptr[r] == 0); } http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/bcf4c901/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockMCSR.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockMCSR.java b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockMCSR.java index 4a19c68..9fb007e 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockMCSR.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockMCSR.java @@ -71,6 +71,13 @@ public class SparseBlockMCSR extends SparseBlock public boolean isThreadSafe() { return true; } + + @Override + public void reset() { + for( SparseRow row : _rows ) + if( row != null ) + row.reset(row.size(), -1); + } @Override public long size() { @@ -87,6 +94,26 @@ public class SparseBlockMCSR extends SparseBlock //prior check with isEmpty(r) expected return _rows[r].size(); } + + @Override + public long size(int rl, int ru) { + int ret = 0; + for( int i=rl; i<ru; i++ ) + ret += (_rows[i]!=null) ? _rows[i].size() : 0; + return ret; + } + + @Override + public long size(int rl, int ru, int cl, int cu) { + long nnz = 0; + for(int i=rl; i<ru; i++) + if( !isEmpty(i) ) { + int start = posFIndexGTE(i, cl); + int end = posFIndexGTE(i, cu); + nnz += (start!=-1) ? (end-start) : 0; + } + return nnz; + } @Override public boolean isEmpty(int r) { http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/bcf4c901/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockSize.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockSize.java b/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockSize.java new file mode 100644 index 0000000..aca66dc --- /dev/null +++ b/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockSize.java @@ -0,0 +1,165 @@ +/* + * 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.sparse; + +import org.junit.Assert; +import org.junit.Test; +import org.apache.sysml.runtime.matrix.data.MatrixBlock; +import org.apache.sysml.runtime.matrix.data.SparseBlock; +import org.apache.sysml.runtime.matrix.data.SparseBlockCOO; +import org.apache.sysml.runtime.matrix.data.SparseBlockCSR; +import org.apache.sysml.runtime.matrix.data.SparseBlockMCSR; +import org.apache.sysml.runtime.matrix.data.SparseRow; +import org.apache.sysml.runtime.util.DataConverter; +import org.apache.sysml.test.integration.AutomatedTestBase; +import org.apache.sysml.test.utils.TestUtils; + +/** + * This is a sparse matrix block component test for sparse block size + * functionality (nnz). In order to achieve broad coverage, we test + * against different overloaded versions of size as well as different + * sparsity values. + * + */ +public class SparseBlockSize extends AutomatedTestBase +{ + private final static int rows = 762; + private final static int cols = 649; + private final static int rl = 31; + private final static int ru = 345; + private final static int cl = 345; + private final static int cu = 525; + private final static double sparsity1 = 0.12; + private final static double sparsity2 = 0.22; + private final static double sparsity3 = 0.32; + + @Override + public void setUp() { + TestUtils.clearAssertionInformation(); + } + + @Test + public void testSparseBlockMCSR1() { + runSparseBlockSizeTest(SparseBlock.Type.MCSR, sparsity1); + } + + @Test + public void testSparseBlockMCSR2() { + runSparseBlockSizeTest(SparseBlock.Type.MCSR, sparsity2); + } + + @Test + public void testSparseBlockMCSR3() { + runSparseBlockSizeTest(SparseBlock.Type.MCSR, sparsity3); + } + + @Test + public void testSparseBlockCSR1() { + runSparseBlockSizeTest(SparseBlock.Type.CSR, sparsity1); + } + + @Test + public void testSparseBlockCSR2() { + runSparseBlockSizeTest(SparseBlock.Type.CSR, sparsity2); + } + + @Test + public void testSparseBlockCSR3() { + runSparseBlockSizeTest(SparseBlock.Type.CSR, sparsity3); + } + + @Test + public void testSparseBlockCOO1() { + runSparseBlockSizeTest(SparseBlock.Type.COO, sparsity1); + } + + @Test + public void testSparseBlockCOO2() { + runSparseBlockSizeTest(SparseBlock.Type.COO, sparsity2); + } + + @Test + public void testSparseBlockCOO3() { + runSparseBlockSizeTest(SparseBlock.Type.COO, sparsity3); + } + + /** + * + * @param btype + * @param sparsity + */ + private void runSparseBlockSizeTest( SparseBlock.Type btype, double sparsity) + { + try + { + //data generation + double[][] A = getRandomMatrix(rows, cols, -10, 10, sparsity, 123); + + //init sparse block + SparseBlock sblock = null; + MatrixBlock mbtmp = DataConverter.convertToMatrixBlock(A); + SparseRow[] srtmp = mbtmp.getSparseBlock(); + switch( btype ) { + case MCSR: sblock = new SparseBlockMCSR(srtmp,true); break; + case CSR: sblock = new SparseBlockCSR(srtmp, (int)mbtmp.getNonZeros()); break; + case COO: sblock = new SparseBlockCOO(srtmp, (int)mbtmp.getNonZeros()); break; + } + + //prepare summary statistics nnz + int[] rnnz = new int[rows]; + int nnz = 0; + int nnz2 = 0; + for( int i=0; i<rows; i++ ) { + for( int j=0; j<cols; j++ ) { + rnnz[i] += (A[i][j]!=0) ? 1 : 0; + nnz2 += (i>=rl && j>=cl && i<ru && j<cu && A[i][j]!=0) ? 1 : 0; + } + nnz += rnnz[i]; + } + + //check full block nnz + if( nnz != sblock.size() ) + Assert.fail("Wrong number of non-zeros: "+sblock.size()+", expected: "+nnz); + + //check row nnz + for( int i=0; i<rows; i++ ) + if( sblock.size(i) != rnnz[i] ) { + Assert.fail("Wrong number of row non-zeros ("+i+"): " + + sblock.size(i)+", expected: "+rnnz[i]); + } + + //check two row nnz + for( int i=1; i<rows; i++ ) + if( sblock.size(i-1,i+1) != rnnz[i-1]+rnnz[i] ) { + Assert.fail("Wrong number of row block non-zeros ("+(i-1)+","+(i+1)+"): " + + sblock.size(i-1,i+1)+", expected: "+rnnz[i-1]+rnnz[i]); + } + + //check index range nnz + if( sblock.size(rl, ru, cl, cu) != nnz2 ) + Assert.fail("Wrong number of range non-zeros: " + + sblock.size(rl, ru, cl, cu)+", expected: "+nnz2); + } + catch(Exception ex) { + ex.printStackTrace(); + throw new RuntimeException(ex); + } + } +} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/bcf4c901/src/test_suites/java/org/apache/sysml/test/integration/functions/sparse/ZPackageSuite.java ---------------------------------------------------------------------- diff --git a/src/test_suites/java/org/apache/sysml/test/integration/functions/sparse/ZPackageSuite.java b/src/test_suites/java/org/apache/sysml/test/integration/functions/sparse/ZPackageSuite.java index f4d1411..633e152 100644 --- a/src/test_suites/java/org/apache/sysml/test/integration/functions/sparse/ZPackageSuite.java +++ b/src/test_suites/java/org/apache/sysml/test/integration/functions/sparse/ZPackageSuite.java @@ -33,6 +33,7 @@ import org.junit.runners.Suite; SparseBlockIndexRange.class, SparseBlockIterator.class, SparseBlockScan.class, + SparseBlockSize.class, })
