org.apache.sysds.runtime.controlprogram.parfor.opt

Class OptimizerRuleBased

java.lang.Object

org.apache.sysds.runtime.controlprogram.parfor.opt.Optimizer

org.apache.sysds.runtime.controlprogram.parfor.opt.OptimizerRuleBased

Direct Known Subclasses:

OptimizerConstrained, OptimizerHeuristic

public class OptimizerRuleBased
extends Optimizer

Rule-Based ParFor Optimizer (time: O(n)): Applied rule-based rewrites - 1) rewrite set data partitioner (incl. recompile RIX) - 2) rewrite remove unnecessary compare matrix - 3) rewrite result partitioning (incl. recompile LIX) - 4) rewrite set execution strategy - 5) rewrite set operations exec type (incl. recompile) - 6) rewrite use data colocation - 7) rewrite set partition replication factor - 8) rewrite set export replication factor - 9) rewrite use nested parallelism - 10) rewrite set degree of parallelism - 11) rewrite set task partitioner - 12) rewrite set fused data partitioning and execution - 13) rewrite transpose vector operations (for sparse) - 14) rewrite set in-place result indexing - 15) rewrite disable caching (prevent sparse serialization) - 16) rewrite enable runtime piggybacking - 17) rewrite inject spark loop checkpointing - 18) rewrite inject spark repartition (for zipmm) - 19) rewrite set spark eager rdd caching - 20) rewrite set result merge - 21) rewrite set recompile memory budget - 22) rewrite remove recursive parfor - 23) rewrite remove unnecessary parfor TODO fuse also result merge into fused data partitioning and execute (for writing the result directly from execute we need to partition columns/rows according to blocksize -> rewrite (only applicable if numCols/blocksize>numreducers)+custom MR partitioner) TODO take remote memory into account in data/result partitioning rewrites (smaller/larger) TODO memory estimates with shared reads TODO memory estimates of result merge into plan tree TODO blockwise partitioning

Nested Class Summary

Nested classes/interfaces inherited from class org.apache.sysds.runtime.controlprogram.parfor.opt.Optimizer

Optimizer.CostModelType, Optimizer.PlanInputType

Field Summary

Fields

Modifier and Type	Field and Description
static boolean	ALLOW_REMOTE_NESTED_PARALLELISM
static String	FUNCTION_UNFOLD_NAMEPREFIX
static int	MAX_REPLICATION_FACTOR_EXPORT
static int	MAX_REPLICATION_FACTOR_PARTITIONING
static double	PAR_K_FACTOR
static double	PAR_K_MR_FACTOR
static double	PROB_SIZE_THRESHOLD_MB
static double	PROB_SIZE_THRESHOLD_PARTITIONING
static double	PROB_SIZE_THRESHOLD_REMOTE

Constructor Summary

Constructors

Constructor and Description
OptimizerRuleBased()

Method Summary

Modifier and Type	Method and Description
static boolean	allowsBinaryCellPartitions(MatrixObject mo, ParForProgramBlock.PartitionFormat dpf)
Optimizer.CostModelType	getCostModelType()
ParForProgramBlock.POptMode	getOptMode()
Optimizer.PlanInputType	getPlanInputType()
static boolean	isInMemoryResultMerge(long rows, long cols, double memBudget)
boolean	optimize(ParForStatementBlock sb, ParForProgramBlock pb, OptTree plan, CostEstimator est, ExecutionContext ec) Main optimization procedure.
static String	toMB(double inB)

Methods inherited from class org.apache.sysds.runtime.controlprogram.parfor.opt.Optimizer

getNumEvaluatedPlans, getNumTotalPlans

Methods inherited from class java.lang.Object

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

Field Detail

PROB_SIZE_THRESHOLD_REMOTE

public static final double PROB_SIZE_THRESHOLD_REMOTE

See Also:

Constant Field Values

PROB_SIZE_THRESHOLD_PARTITIONING

public static final double PROB_SIZE_THRESHOLD_PARTITIONING

See Also:

Constant Field Values

PROB_SIZE_THRESHOLD_MB

public static final double PROB_SIZE_THRESHOLD_MB

See Also:

Constant Field Values

MAX_REPLICATION_FACTOR_PARTITIONING

public static final int MAX_REPLICATION_FACTOR_PARTITIONING

See Also:

Constant Field Values

MAX_REPLICATION_FACTOR_EXPORT

public static final int MAX_REPLICATION_FACTOR_EXPORT

See Also:

Constant Field Values

ALLOW_REMOTE_NESTED_PARALLELISM

public static final boolean ALLOW_REMOTE_NESTED_PARALLELISM

See Also:

Constant Field Values

FUNCTION_UNFOLD_NAMEPREFIX

public static final String FUNCTION_UNFOLD_NAMEPREFIX

See Also:

Constant Field Values

PAR_K_FACTOR

public static final double PAR_K_FACTOR

See Also:

Constant Field Values

PAR_K_MR_FACTOR

public static final double PAR_K_MR_FACTOR

See Also:

Constant Field Values

Constructor Detail

OptimizerRuleBased

public OptimizerRuleBased()

Method Detail

getCostModelType

public Optimizer.CostModelType getCostModelType()

Specified by:

getCostModelType in class Optimizer

getPlanInputType

public Optimizer.PlanInputType getPlanInputType()

Specified by:

getPlanInputType in class Optimizer

getOptMode

public ParForProgramBlock.POptMode getOptMode()

Specified by:

getOptMode in class Optimizer

optimize

public boolean optimize(ParForStatementBlock sb,
                        ParForProgramBlock pb,
                        OptTree plan,
                        CostEstimator est,
                        ExecutionContext ec)

Main optimization procedure. Transformation-based heuristic (rule-based) optimization (no use of sb, direct change of pb).

Specified by:

optimize in class Optimizer

Parameters:

sb - parfor statement block

pb - parfor program block

plan - complete plan of a top-level parfor

est - cost estimator

ec - execution context

Returns:

true if plan changed, false otherwise

allowsBinaryCellPartitions

public static boolean allowsBinaryCellPartitions(MatrixObject mo,
                                                 ParForProgramBlock.PartitionFormat dpf)

isInMemoryResultMerge

public static boolean isInMemoryResultMerge(long rows,
                                            long cols,
                                            double memBudget)

toMB

public static String toMB(double inB)