org.apache.sysds.hops.estim

Class EstimatorDensityMap

java.lang.Object

org.apache.sysds.hops.estim.SparsityEstimator

org.apache.sysds.hops.estim.EstimatorDensityMap

public class EstimatorDensityMap
extends SparsityEstimator

This estimator implements an approach called density maps, as introduced in David Kernert, Frank Köhler, Wolfgang Lehner: SpMacho - Optimizing Sparse Linear Algebra Expressions with Probabilistic Density Estimation. EDBT 2015: 289-300. The basic idea is to maintain a density matrix per input, i.e., non-zero counts per bxb cells of the matrix, and compute the output density map based on a matrix-multiply-like aggregation of average estimates per cell. The output sparsity is then derived as an aggregate of the output density map, but this density map can also be used for intermediates in chains of matrix multiplications.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	EstimatorDensityMap.DensityMap

Nested classes/interfaces inherited from class org.apache.sysds.hops.estim.SparsityEstimator

SparsityEstimator.OpCode

Field Summary

Fields inherited from class org.apache.sysds.hops.estim.SparsityEstimator

MIN_PAR_THRESHOLD, MULTI_THREADED_BUILD, MULTI_THREADED_ESTIM

Constructor Summary

Constructors

Constructor and Description
EstimatorDensityMap()
EstimatorDensityMap(int blocksize)

Method Summary

Modifier and Type	Method and Description
double	estim(MatrixBlock m1, MatrixBlock m2) Estimates the output sparsity for a single matrix multiplication.
double	estim(MatrixBlock m1, MatrixBlock m2, SparsityEstimator.OpCode op) Estimates the output sparsity for a given binary operation.
double	estim(MatrixBlock m, SparsityEstimator.OpCode op) Estimates the output sparsity for a given unary operation.
DataCharacteristics	estim(MMNode root) Estimates the output sparsity of a DAG of matrix multiplications for the given operator graph of a single root node.
EstimatorDensityMap.DensityMap	estimIntern(EstimatorDensityMap.DensityMap m1Map, EstimatorDensityMap.DensityMap m2Map, SparsityEstimator.OpCode op) Computes the output density map given the density maps of the input operands.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

EstimatorDensityMap

public EstimatorDensityMap()

EstimatorDensityMap

public EstimatorDensityMap(int blocksize)

Method Detail

estim

public DataCharacteristics estim(MMNode root)

Description copied from class: SparsityEstimator

Estimates the output sparsity of a DAG of matrix multiplications for the given operator graph of a single root node.

Specified by:

estim in class SparsityEstimator

Parameters:

root - DAG root node

Returns:

output data characteristics

estim

public double estim(MatrixBlock m1,
                    MatrixBlock m2)

Description copied from class: SparsityEstimator

Estimates the output sparsity for a single matrix multiplication.

Specified by:

estim in class SparsityEstimator

Parameters:

m1 - left-hand-side operand

m2 - right-hand-side operand

Returns:

sparsity

estim

public double estim(MatrixBlock m1,
                    MatrixBlock m2,
                    SparsityEstimator.OpCode op)

Description copied from class: SparsityEstimator

Estimates the output sparsity for a given binary operation.

Specified by:

estim in class SparsityEstimator

Parameters:

m1 - left-hand-side operand

m2 - right-hand-side operand

op - operator code

Returns:

sparsity

estim

public double estim(MatrixBlock m,
                    SparsityEstimator.OpCode op)

Description copied from class: SparsityEstimator

Estimates the output sparsity for a given unary operation.

Specified by:

estim in class SparsityEstimator

Parameters:

m - left-hand-side operand

op - operator code

Returns:

sparsity

estimIntern

public EstimatorDensityMap.DensityMap estimIntern(EstimatorDensityMap.DensityMap m1Map,
                                                  EstimatorDensityMap.DensityMap m2Map,
                                                  SparsityEstimator.OpCode op)

Computes the output density map given the density maps of the input operands.

Parameters:

m1Map - density map left-hand-side operand

m2Map - density map right-hand-side operand

op - operator code

Returns:

density map