You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemml.apache.org by mb...@apache.org on 2016/07/30 00:20:33 UTC
incubator-systemml git commit: [SYSTEMML-821] Extended multi-threaded
compression (parallel co-coding)
Repository: incubator-systemml
Updated Branches:
refs/heads/master 13211190f -> b36fb29ea
[SYSTEMML-821] Extended multi-threaded compression (parallel co-coding)
Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/b36fb29e
Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/b36fb29e
Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/b36fb29e
Branch: refs/heads/master
Commit: b36fb29eac81a2b28b862c299b5c01e8b30b8a86
Parents: 1321119
Author: Matthias Boehm <mb...@us.ibm.com>
Authored: Fri Jul 29 17:11:53 2016 -0700
Committer: Matthias Boehm <mb...@us.ibm.com>
Committed: Fri Jul 29 17:20:01 2016 -0700
----------------------------------------------------------------------
.../runtime/compress/CompressedMatrixBlock.java | 18 +--
.../sysml/runtime/compress/PlanningCoCoder.java | 132 +++++++++++++++----
.../runtime/compress/PlanningCoCodingGroup.java | 7 +-
3 files changed, 117 insertions(+), 40 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b36fb29e/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 f2ccb43..2f14f1c 100644
--- a/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java
+++ b/src/main/java/org/apache/sysml/runtime/compress/CompressedMatrixBlock.java
@@ -237,9 +237,6 @@ public class CompressedMatrixBlock extends MatrixBlock implements Externalizable
CompressedSizeEstimator bitmapSizeEstimator =
SizeEstimatorFactory.getSizeEstimator(rawblock, numRows);
- //allocate list of column groups
- allocateColGroupList();
-
// The current implementation of this method is written for correctness,
// not for performance or for minimal use of temporary space.
@@ -255,7 +252,7 @@ public class CompressedMatrixBlock extends MatrixBlock implements Externalizable
// information about the bitmap amenable columns
List<Integer> bitmapCols = new ArrayList<Integer>();
List<Integer> uncompressedCols = new ArrayList<Integer>();
- List<Integer> colsCardinalities = new ArrayList<Integer>();
+ List<Integer> colsCards = new ArrayList<Integer>();
List<Long> compressedSizes = new ArrayList<Long>();
HashMap<Integer, Double> compressionRatios = new HashMap<Integer, Double>();
@@ -275,7 +272,7 @@ public class CompressedMatrixBlock extends MatrixBlock implements Externalizable
if (compRatio >= MIN_COMPRESSION_RATIO) {
bitmapCols.add(col);
compressionRatios.put(col, compRatio);
- colsCardinalities.add(sizeInfos[col].getEstCarinality());
+ colsCards.add(sizeInfos[col].getEstCarinality());
compressedSizes.add(compressedSize);
}
else
@@ -295,15 +292,13 @@ public class CompressedMatrixBlock extends MatrixBlock implements Externalizable
// Too many columns to compute co-coding groups with current methods.
// Generate singleton groups.
bitmapColGrps = new ArrayList<int[]>(bitmapCols.size());
- for (int col : bitmapCols) {
+ for (int col : bitmapCols)
bitmapColGrps.add(new int[] { col });
- }
}
else {
- bitmapColGrps = PlanningCoCoder.findCocodesByPartitioning(
- bitmapSizeEstimator, bitmapCols, colsCardinalities,
- compressedSizes, numRows, isInSparseFormat() ?
- OptimizerUtils.getSparsity(numRows, numCols, getNonZeros()): 1);
+ bitmapColGrps = PlanningCoCoder.findCocodesByPartitioning(bitmapSizeEstimator,
+ bitmapCols, colsCards, compressedSizes, numRows, isInSparseFormat() ?
+ OptimizerUtils.getSparsity(numRows, numCols, getNonZeros()):1, k);
}
_stats.timePhase2 = time.stop();
@@ -322,6 +317,7 @@ public class CompressedMatrixBlock extends MatrixBlock implements Externalizable
ColGroup[] colGroups = (k > 1) ?
compressColGroups(rawblock, bitmapSizeEstimator, compressionRatios, numRows, bitmapColGrps, k) :
compressColGroups(rawblock, bitmapSizeEstimator, compressionRatios, numRows, bitmapColGrps);
+ allocateColGroupList();
for( int j=0; j<colGroups.length; j++ ) {
if( colGroups[j] != null ) {
for( int col : colGroups[j].getColIndices() )
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b36fb29e/src/main/java/org/apache/sysml/runtime/compress/PlanningCoCoder.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/compress/PlanningCoCoder.java b/src/main/java/org/apache/sysml/runtime/compress/PlanningCoCoder.java
index 07d9757..d1fd7af 100644
--- a/src/main/java/org/apache/sysml/runtime/compress/PlanningCoCoder.java
+++ b/src/main/java/org/apache/sysml/runtime/compress/PlanningCoCoder.java
@@ -24,7 +24,12 @@ import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeMap;
+import java.util.concurrent.Callable;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.Future;
+import org.apache.sysml.runtime.DMLRuntimeException;
import org.apache.sysml.runtime.compress.estim.CompressedSizeEstimator;
public class PlanningCoCoder
@@ -45,58 +50,110 @@ public class PlanningCoCoder
* @param numRows
* @param sparsity
* @return
+ * @throws DMLRuntimeException
*/
public static List<int[]> findCocodesByPartitioning(CompressedSizeEstimator sizeEstimator, List<Integer> availCols,
- List<Integer> colsCardinalities,List<Long> compressedSize, int numRows, double sparsity)
+ List<Integer> colsCardinalities, List<Long> compressedSize, int numRows, double sparsity, int k)
+ throws DMLRuntimeException
{
- float numRowsWeight = numRows;
List<int[]> retGroups = new ArrayList<int[]>();
+
// filtering out non-groupable columns as singleton groups
- int numCols = availCols.size();
- List<Integer> groupabaleCols = new ArrayList<Integer>();
// weighted of each column is the ratio of its cardinality to the number
// of rows scaled by the matrix sparsity
- List<Float> groupabaleColWeights = new ArrayList<Float>();
- HashMap<Integer, GroupableColInfo> groupableColsInfo = new HashMap<Integer, GroupableColInfo>();
+ int numCols = availCols.size();
+ List<Integer> groupCols = new ArrayList<Integer>();
+ List<Float> groupColWeights = new ArrayList<Float>();
+ HashMap<Integer, GroupableColInfo> groupColsInfo = new HashMap<Integer, GroupableColInfo>();
for (int i = 0; i < numCols; i++) {
int colIx = availCols.get(i);
int cardinality = colsCardinalities.get(i);
- float weight = ((float) cardinality) / numRowsWeight;
+ float weight = ((float) cardinality) / numRows;
if (weight <= GROUPABILITY_THRESHOLD) {
- groupabaleCols.add(colIx);
- groupabaleColWeights.add(weight);
- groupableColsInfo.put(colIx, new GroupableColInfo(weight,
- compressedSize.get(i)));
+ groupCols.add(colIx);
+ groupColWeights.add(weight);
+ groupColsInfo.put(colIx, new GroupableColInfo(weight,compressedSize.get(i)));
} else {
retGroups.add(new int[] { colIx });
}
}
+
// bin packing based on PARTITION_WEIGHT and column weights
float weight = computeWeightForCoCoding(numRows, sparsity);
TreeMap<Float, List<List<Integer>>> bins = new PlanningBinPacker(
- weight, groupabaleCols, groupabaleColWeights)
- .packFirstFit();
+ weight, groupCols, groupColWeights).packFirstFit();
// brute force grouping within each partition
+ retGroups.addAll( (k > 1) ?
+ getCocodingGroupsBruteForce(bins, groupColsInfo, sizeEstimator, numRows, k) :
+ getCocodingGroupsBruteForce(bins, groupColsInfo, sizeEstimator, numRows));
+
+ return retGroups;
+ }
+
+ /**
+ *
+ * @param bins
+ * @param groupColsInfo
+ * @param estim
+ * @param rlen
+ * @return
+ */
+ private static List<int[]> getCocodingGroupsBruteForce(TreeMap<Float, List<List<Integer>>> bins, HashMap<Integer, GroupableColInfo> groupColsInfo, CompressedSizeEstimator estim, int rlen)
+ {
+ List<int[]> retGroups = new ArrayList<int[]>();
for (List<List<Integer>> binList : bins.values()) {
for (List<Integer> bin : binList) {
// building an array of singleton CoCodingGroup
- PlanningCoCodingGroup[] singltonGroups = new PlanningCoCodingGroup[bin.size()];
- int i = 0;
- GroupableColInfo colInfo;
- for (Integer col : bin) {
- colInfo = groupableColsInfo.get(col);
- singltonGroups[i++] = new PlanningCoCodingGroup(col, colInfo.size,
- colInfo.cardRatio);
- }
+ ArrayList<PlanningCoCodingGroup> sgroups = new ArrayList<PlanningCoCodingGroup>();
+ for (Integer col : bin)
+ sgroups.add(new PlanningCoCodingGroup(col, groupColsInfo.get(col)));
+ // brute force co-coding
PlanningCoCodingGroup[] outputGroups = findCocodesBruteForce(
- sizeEstimator, numRowsWeight, singltonGroups);
-
- for (PlanningCoCodingGroup grp : outputGroups) {
+ estim, rlen, sgroups.toArray(new PlanningCoCodingGroup[0]));
+ for (PlanningCoCodingGroup grp : outputGroups)
retGroups.add(grp.getColIndices());
- }
}
}
+
+ return retGroups;
+ }
+
+ /**
+ *
+ * @param bins
+ * @param groupColsInfo
+ * @param estim
+ * @param rlen
+ * @param k
+ * @return
+ * @throws DMLRuntimeException
+ */
+ private static List<int[]> getCocodingGroupsBruteForce(TreeMap<Float, List<List<Integer>>> bins, HashMap<Integer, GroupableColInfo> groupColsInfo, CompressedSizeEstimator estim, int rlen, int k)
+ throws DMLRuntimeException
+ {
+ List<int[]> retGroups = new ArrayList<int[]>();
+ try {
+ ExecutorService pool = Executors.newFixedThreadPool( k );
+ ArrayList<CocodeTask> tasks = new ArrayList<CocodeTask>();
+ for (List<List<Integer>> binList : bins.values())
+ for (List<Integer> bin : binList) {
+ // building an array of singleton CoCodingGroup
+ ArrayList<PlanningCoCodingGroup> sgroups = new ArrayList<PlanningCoCodingGroup>();
+ for (Integer col : bin)
+ sgroups.add(new PlanningCoCodingGroup(col, groupColsInfo.get(col)));
+ tasks.add(new CocodeTask(estim, sgroups, rlen));
+ }
+ List<Future<PlanningCoCodingGroup[]>> rtask = pool.invokeAll(tasks);
+ for( Future<PlanningCoCodingGroup[]> lrtask : rtask )
+ for (PlanningCoCodingGroup grp : lrtask.get())
+ retGroups.add(grp.getColIndices());
+ pool.shutdown();
+ }
+ catch(Exception ex) {
+ throw new DMLRuntimeException(ex);
+ }
+
return retGroups;
}
@@ -215,7 +272,7 @@ public class PlanningCoCoder
/**
*
*/
- private static class GroupableColInfo {
+ protected static class GroupableColInfo {
float cardRatio;
long size;
@@ -224,4 +281,27 @@ public class PlanningCoCoder
size = lsize;
}
}
+
+ /**
+ *
+ */
+ private static class CocodeTask implements Callable<PlanningCoCodingGroup[]>
+ {
+ private CompressedSizeEstimator _estim = null;
+ private ArrayList<PlanningCoCodingGroup> _sgroups = null;
+ private int _rlen = -1;
+
+ protected CocodeTask( CompressedSizeEstimator estim, ArrayList<PlanningCoCodingGroup> sgroups, int rlen ) {
+ _estim = estim;
+ _sgroups = sgroups;
+ _rlen = rlen;
+ }
+
+ @Override
+ public PlanningCoCodingGroup[] call() throws DMLRuntimeException {
+ // brute force co-coding
+ return findCocodesBruteForce(_estim, _rlen,
+ _sgroups.toArray(new PlanningCoCodingGroup[0]));
+ }
+ }
}
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b36fb29e/src/main/java/org/apache/sysml/runtime/compress/PlanningCoCodingGroup.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/compress/PlanningCoCodingGroup.java b/src/main/java/org/apache/sysml/runtime/compress/PlanningCoCodingGroup.java
index 6553c20..a1e0123 100644
--- a/src/main/java/org/apache/sysml/runtime/compress/PlanningCoCodingGroup.java
+++ b/src/main/java/org/apache/sysml/runtime/compress/PlanningCoCodingGroup.java
@@ -21,6 +21,7 @@ package org.apache.sysml.runtime.compress;
import java.util.Arrays;
+import org.apache.sysml.runtime.compress.PlanningCoCoder.GroupableColInfo;
import org.apache.sysml.runtime.compress.estim.CompressedSizeEstimator;
import org.apache.sysml.runtime.compress.estim.CompressedSizeInfo;
@@ -38,10 +39,10 @@ public class PlanningCoCodingGroup
* Constructor for a one-column group; i.e. do not co-code a given column.
*
*/
- public PlanningCoCodingGroup(int col, long estSize, float cardRatio) {
+ public PlanningCoCodingGroup(int col, GroupableColInfo info) {
_colIndexes = new int[]{col};
- _estSize = estSize;
- _cardRatio = cardRatio;
+ _estSize = info.size;
+ _cardRatio = info.cardRatio;
}
/**