Package org.apache.sysds.hops.rewrite

Class RewriteMatrixMultChainOptimization

java.lang.Object
org.apache.sysds.hops.rewrite.HopRewriteRule
org.apache.sysds.hops.rewrite.RewriteMatrixMultChainOptimization
Direct Known Subclasses:
RewriteMatrixMultChainOptimizationSparse
public class RewriteMatrixMultChainOptimization extends HopRewriteRule
Rule: Determine the optimal order of execution for a chain of matrix multiplications Solution: Classic Dynamic Programming Approach: Currently, the approach based only on matrix dimensions Goal: To reduce the number of computations in the run-time (map-reduce) layer

  • Constructor Details

    • RewriteMatrixMultChainOptimization

      public RewriteMatrixMultChainOptimization()

  • Method Details

    • rewriteHopDAGs

      public ArrayList<Hop> rewriteHopDAGs(ArrayList<Hop> roots, ProgramRewriteStatus state)
      Description copied from class: HopRewriteRule
      Handle a generic (last-level) hop DAG with multiple roots.
      Specified by:
      rewriteHopDAGs in class HopRewriteRule
      Parameters:
      roots - high-level operator roots
      state - program rewrite status
      Returns:
      list of high-level operators

    • rewriteHopDAG

      public Hop rewriteHopDAG(Hop root, ProgramRewriteStatus state)
      Description copied from class: HopRewriteRule
      Handle a predicate hop DAG with exactly one root.
      Specified by:
      rewriteHopDAG in class HopRewriteRule
      Parameters:
      root - high-level operator root
      state - program rewrite status
      Returns:
      high-level operator

    • mmChainDP

      public static int[][] mmChainDP(double[] dimArray, int size)
      mmChainDP(): Core method to perform dynamic programming on a given array of matrix dimensions. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms, Third Edition, MIT Press, page 395.