[2/2] incubator-systemml git commit: [SYSTEMML-1418] New codegen plan selection framework, fuse-all selector

[mb...@apache.org]

[SYSTEMML-1418] New codegen plan selection framework, fuse-all selector

This patch introduces a new plan selection framework as well as the
initial fuse-all selector. Additionally, this includes the following
minor extensions:

* Refactoring existing rowagg, outer, cell templates
* Support for unary operations in row aggregate template
* New row aggregate test case with multiple dag roots


Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/b3120ce2
Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/b3120ce2
Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/b3120ce2

Branch: refs/heads/master
Commit: b3120ce24106a3593ff4353c99935adce41ed8b3
Parents: 0dd095f
Author: Matthias Boehm <mb...@gmail.com>
Authored: Fri Mar 24 20:13:00 2017 -0700
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Sat Mar 25 15:54:54 2017 -0700

----------------------------------------------------------------------
 .../sysml/hops/codegen/SpoofCompiler.java       |  14 +-
 .../sysml/hops/codegen/template/BaseTpl.java    | 124 --------
 .../hops/codegen/template/CPlanMemoTable.java   | 109 +++----
 .../sysml/hops/codegen/template/CellTpl.java    | 304 -------------------
 .../hops/codegen/template/OuterProductTpl.java  | 213 -------------
 .../hops/codegen/template/PlanSelection.java    |  73 +++++
 .../codegen/template/PlanSelectionFuseAll.java  |  85 ++++++
 .../sysml/hops/codegen/template/RowAggTpl.java  | 246 ---------------
 .../hops/codegen/template/TemplateBase.java     | 129 ++++++++
 .../hops/codegen/template/TemplateCell.java     | 304 +++++++++++++++++++
 .../codegen/template/TemplateOuterProduct.java  | 213 +++++++++++++
 .../hops/codegen/template/TemplateRowAgg.java   | 259 ++++++++++++++++
 .../hops/codegen/template/TemplateUtils.java    |  16 +-
 .../functions/codegen/RowAggTmplTest.java       |  13 +-
 .../scripts/functions/codegen/rowAggPattern7.R  |  34 +++
 .../functions/codegen/rowAggPattern7.dml        |  31 ++
 16 files changed, 1205 insertions(+), 962 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b3120ce2/src/main/java/org/apache/sysml/hops/codegen/SpoofCompiler.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/SpoofCompiler.java b/src/main/java/org/apache/sysml/hops/codegen/SpoofCompiler.java
index 8587367..17e2fcf 100644
--- a/src/main/java/org/apache/sysml/hops/codegen/SpoofCompiler.java
+++ b/src/main/java/org/apache/sysml/hops/codegen/SpoofCompiler.java
@@ -41,9 +41,9 @@ import org.apache.sysml.hops.codegen.cplan.CNodeTernary.TernaryType;
 import org.apache.sysml.hops.codegen.cplan.CNodeTpl;
 import org.apache.sysml.hops.codegen.cplan.CNodeUnary;
 import org.apache.sysml.hops.codegen.cplan.CNodeUnary.UnaryType;
-import org.apache.sysml.hops.codegen.template.BaseTpl;
-import org.apache.sysml.hops.codegen.template.BaseTpl.CloseType;
-import org.apache.sysml.hops.codegen.template.BaseTpl.TemplateType;
+import org.apache.sysml.hops.codegen.template.TemplateBase;
+import org.apache.sysml.hops.codegen.template.TemplateBase.CloseType;
+import org.apache.sysml.hops.codegen.template.TemplateBase.TemplateType;
 import org.apache.sysml.hops.codegen.template.CPlanMemoTable;
 import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntry;
 import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntrySet;
@@ -317,7 +317,7 @@ public class SpoofCompiler
 			rExploreCPlans(hop, memo, compileLiterals);
 		
 		//select optimal cplan candidates
-		memo.pruneSuboptimal();
+		memo.pruneSuboptimal(roots);
 		
 		//construct actual cplan representations
 		LinkedHashMap<Long, Pair<Hop[],CNodeTpl>> ret = new LinkedHashMap<Long, Pair<Hop[],CNodeTpl>>();
@@ -341,7 +341,7 @@ public class SpoofCompiler
 			rExploreCPlans(c, memo, compileLiterals);
 		
 		//open initial operator plans, if possible
-		for( BaseTpl tpl : TemplateUtils.TEMPLATES )
+		for( TemplateBase tpl : TemplateUtils.TEMPLATES )
 			if( tpl.open(hop) )
 				memo.add(hop, tpl.getType());
 		
@@ -349,7 +349,7 @@ public class SpoofCompiler
 		for( Hop c : hop.getInput() ) {
 			if( memo.contains(c.getHopID()) )
 				for( MemoTableEntry me : memo.getDistinct(c.getHopID()) ) {
-					BaseTpl tpl = TemplateUtils.createTemplate(me.type, me.closed);
+					TemplateBase tpl = TemplateUtils.createTemplate(me.type, me.closed);
 					if( tpl.fuse(hop, c) ) {
 						int pos = hop.getInput().indexOf(c);
 						MemoTableEntrySet P = new MemoTableEntrySet(tpl.getType(), pos, c.getHopID(), tpl.isClosed());
@@ -376,7 +376,7 @@ public class SpoofCompiler
 			Iterator<MemoTableEntry> iter = memo.get(hop.getHopID()).iterator();
 			while( iter.hasNext() ) {
 				MemoTableEntry me = iter.next();
-				BaseTpl tpl = TemplateUtils.createTemplate(me.type);
+				TemplateBase tpl = TemplateUtils.createTemplate(me.type);
 				CloseType ccode = tpl.close(hop);
 				if( ccode == CloseType.CLOSED_INVALID )
 					iter.remove();

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b3120ce2/src/main/java/org/apache/sysml/hops/codegen/template/BaseTpl.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/BaseTpl.java b/src/main/java/org/apache/sysml/hops/codegen/template/BaseTpl.java
deleted file mode 100644
index 2f643af..0000000
--- a/src/main/java/org/apache/sysml/hops/codegen/template/BaseTpl.java
+++ /dev/null
@@ -1,124 +0,0 @@
-/*
- * 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.hops.codegen.template;
-
-import org.apache.sysml.hops.Hop;
-import org.apache.sysml.hops.codegen.cplan.CNodeTpl;
-import org.apache.sysml.runtime.matrix.data.Pair;
-
-public abstract class BaseTpl 
-{	
-	public enum TemplateType {
-		CellTpl,
-		OuterProdTpl,
-		RowAggTpl
-	}
-	
-	public enum CloseType {
-		CLOSED_VALID,
-		CLOSED_INVALID,
-		OPEN,
-	}
-
-	protected TemplateType _type = null;
-	protected boolean _closed = false;
-	
-	protected BaseTpl(TemplateType type) {
-		_type = type;
-		_closed = false;
-	}
-	
-	public TemplateType getType() {
-		return _type;
-	}
-	
-	public boolean isClosed() {
-		return _closed;
-	}
-	
-	/////////////////////////////////////////////
-	// Open-Fuse-Merge-Close interface 
-	// (for candidate generation and exploration)
-	
-	/**
-	 * Indicates if this template can be opened at the given hop,
-	 * where hop represents bottom (first operation on the inputs) 
-	 * of the fused operator.
-	 * 
-	 * @param hop current hop
-	 * @return true if template can be opened 
-	 */
-	public abstract boolean open(Hop hop);
-	
-	/**
-	 * Indicates if the template can be expanded to the given hop
-	 * starting from an open template at the input.
-	 * 
-	 * @param hop current hop
-	 * @param input hop with open template of same type
-	 * @return true if the current hop can be fused into the operator.
-	 */
-	public abstract boolean fuse(Hop hop, Hop input);
-	
-	/**
-	 * Indicates if the template at the current hop can be expanded
-	 * by merging another template available for one of its other inputs
-	 * which is not yet covered by the template of the current hop. 
-	 * 
-	 * @param hop current hop
-	 * @param input direct input of current hop with available template
-	 * @return true if the the input hop can be fused into the current hop
-	 */
-	public abstract boolean merge(Hop hop, Hop input);
-	
-	/**
-	 * Indicates if the template must be closed at the current hop; either
-	 * due to final operations (e.g., aggregate) or unsupported operations.
-	 * 
-	 * @param hop current hop
-	 * @return close type (closed invalid, closed valid, open)
-	 */
-	public abstract CloseType close(Hop hop);
-	
-	/**
-	 * Mark the template as closed either invalid or valid.
-	 */
-	public void close() {
-		_closed = true;
-	}
-	
-	/////////////////////////////////////////////
-	// CPlan construction interface
-	// (for plan creation of selected candidates)
-	
-	/**
-	 * Constructs a single cplan rooted at the given hop, according 
-	 * to the plan given in the memo structure for this particular 
-	 * hop and its recursive inputs.  
-	 * 
-	 * @param hop root of cplan
-	 * @param memo memoization table for partial subplans
-	 * @param compileLiterals if true compile non-integer literals 
-	 * as constants, otherwise variables. note: integer literals are 
-	 * always compiled as constants.
-	 * @return
-	 */
-	public abstract Pair<Hop[], CNodeTpl> constructCplan(Hop hop, CPlanMemoTable memo, boolean compileLiterals);	
-}

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b3120ce2/src/main/java/org/apache/sysml/hops/codegen/template/CPlanMemoTable.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/CPlanMemoTable.java b/src/main/java/org/apache/sysml/hops/codegen/template/CPlanMemoTable.java
index 03cb7e7..9a66f09 100644
--- a/src/main/java/org/apache/sysml/hops/codegen/template/CPlanMemoTable.java
+++ b/src/main/java/org/apache/sysml/hops/codegen/template/CPlanMemoTable.java
@@ -35,19 +35,18 @@ import org.apache.commons.logging.Log;
 import org.apache.commons.logging.LogFactory;
 import org.apache.sysml.hops.Hop;
 import org.apache.sysml.hops.codegen.SpoofCompiler;
-import org.apache.sysml.hops.codegen.template.BaseTpl.TemplateType;
-import org.apache.sysml.hops.rewrite.HopRewriteUtils;
+import org.apache.sysml.hops.codegen.template.TemplateBase.TemplateType;
 
 public class CPlanMemoTable 
 {
 	private static final Log LOG = LogFactory.getLog(SpoofCompiler.class.getName());
 	
-	private HashMap<Long, ArrayList<MemoTableEntry>> _plans;
-	private HashMap<Long, Hop> _hopRefs;
-	private HashSet<Long> _plansBlacklist;
+	protected HashMap<Long, List<MemoTableEntry>> _plans;
+	protected HashMap<Long, Hop> _hopRefs;
+	protected HashSet<Long> _plansBlacklist;
 	
 	public CPlanMemoTable() {
-		_plans = new HashMap<Long, ArrayList<MemoTableEntry>>();
+		_plans = new HashMap<Long, List<MemoTableEntry>>();
 		_hopRefs = new HashMap<Long, Hop>();
 		_plansBlacklist = new HashSet<Long>();
 	}
@@ -94,6 +93,16 @@ public class CPlanMemoTable
 			_plans.put(hop.getHopID(), new ArrayList<MemoTableEntry>());
 		_plans.get(hop.getHopID()).addAll(P.plans);
 	}
+	
+	public void remove(Hop hop, HashSet<MemoTableEntry> blackList) {
+		_plans.put(hop.getHopID(), _plans.get(hop.getHopID()).stream()
+			.filter(p -> !blackList.contains(p)).collect(Collectors.toList()));	
+	}
+	
+	public void setDistinct(long hopID, List<MemoTableEntry> plans) {
+		_plans.put(hopID, plans.stream()
+			.distinct().collect(Collectors.toList()));
+	}
 
 	@SuppressWarnings("unchecked")
 	public void pruneRedundant(long hopID) {
@@ -102,7 +111,7 @@ public class CPlanMemoTable
 		
 		//prune redundant plans (i.e., equivalent) 
 		HashSet<MemoTableEntry> set = new HashSet<MemoTableEntry>();
-		ArrayList<MemoTableEntry> list = _plans.get(hopID);
+		List<MemoTableEntry> list = _plans.get(hopID);
 		for( MemoTableEntry me : list )
 			set.add(me);
 		
@@ -127,13 +136,13 @@ public class CPlanMemoTable
 		list.addAll(CollectionUtils.subtract(set, rmList));
 	}
 
-	public void pruneSuboptimal() {
+	public void pruneSuboptimal(ArrayList<Hop> roots) {
 		if( SpoofCompiler.LDEBUG )
 			LOG.info("#1: Memo before plan selection ("+size()+" plans)\n"+this);
 		
 		//build index of referenced entries
 		HashSet<Long> ix = new HashSet<Long>();
-		for( Entry<Long, ArrayList<MemoTableEntry>> e : _plans.entrySet() )
+		for( Entry<Long, List<MemoTableEntry>> e : _plans.entrySet() )
 			for( MemoTableEntry me : e.getValue() ) {
 				ix.add(me.input1); 
 				ix.add(me.input2); 
@@ -141,15 +150,13 @@ public class CPlanMemoTable
 			}
 		
 		//prune single-operation (not referenced, and no child references)
-		Iterator<Entry<Long, ArrayList<MemoTableEntry>>> iter = _plans.entrySet().iterator();
+		Iterator<Entry<Long, List<MemoTableEntry>>> iter = _plans.entrySet().iterator();
 		while( iter.hasNext() ) {
-			Entry<Long, ArrayList<MemoTableEntry>> e = iter.next();
+			Entry<Long, List<MemoTableEntry>> e = iter.next();
 			if( !ix.contains(e.getKey()) ) {
-				ArrayList<MemoTableEntry> list = e.getValue();
-				for( int i=0; i<list.size(); i++ )
-					if( !list.get(i).hasPlanRef() )
-						list.remove(i--);
-				if( list.isEmpty() )
+				e.setValue(e.getValue().stream().filter(
+					p -> p.hasPlanRef()).collect(Collectors.toList()));
+				if( e.getValue().isEmpty() )
 					iter.remove();
 			}
 		}
@@ -157,13 +164,23 @@ public class CPlanMemoTable
 		//prune dominated plans (e.g., plan referenced by other plan and this
 		//other plan is single consumer) by marking it as blacklisted because
 		//the chain of entries is still required for cplan construction
-		for( Entry<Long, ArrayList<MemoTableEntry>> e : _plans.entrySet() )
+		for( Entry<Long, List<MemoTableEntry>> e : _plans.entrySet() )
 			for( MemoTableEntry me : e.getValue() ) {
 				for( int i=0; i<=2; i++ )
 					if( me.isPlanRef(i) && _hopRefs.get(me.intput(i)).getParent().size()==1 )
 						_plansBlacklist.add(me.intput(i));
 			}
 		
+		//core plan selection
+		switch( SpoofCompiler.PLAN_SEL_POLICY ) {
+			case FUSE_ALL: 
+				new PlanSelectionFuseAll().selectPlans(this, roots);
+				break;
+			case FUSE_NO_REDUNDANCY:
+			case FUSE_COST_BASED:
+				throw new RuntimeException("Not implemented yet.");
+		}
+		
 		if( SpoofCompiler.LDEBUG )
 			LOG.info("#2: Memo after plan selection ("+size()+" plans)\n"+this);
 	}
@@ -183,51 +200,21 @@ public class CPlanMemoTable
 		List<MemoTableEntry> tmp = get(hopID);
 		if( tmp == null || tmp.isEmpty() )
 			return null;
-		
-		//get first plan by type preference
-		TemplateType[] ttPrefOrder = new TemplateType[]{TemplateType.RowAggTpl, 
-				TemplateType.OuterProdTpl, TemplateType.CellTpl}; 
-		for( TemplateType pref : ttPrefOrder )
-			for( MemoTableEntry me : tmp )
-				if( me.type == pref && isValid(me, _hopRefs.get(hopID)) )
-					return me;
-		return null;
+
+		//single plan per type, get plan w/ best rank in preferred order
+		//but ensure that the plans valid as a top-level plan
+		return tmp.stream().filter(p -> PlanSelection.isValid(p, _hopRefs.get(hopID)))
+			.min(Comparator.comparing(p -> p.type.getRank())).orElse(null);
 	}
 	
-	//TODO revisit requirement for preference once cost-based pruning (pruneSuboptimal) ready
 	public MemoTableEntry getBest(long hopID, TemplateType pref) {
 		List<MemoTableEntry> tmp = get(hopID);
-		if( tmp.size()==1 ) //single plan available
-			return tmp.get(0);
-		
-		//try to find plan with preferred type
-		if( SpoofCompiler.LDEBUG )
-			LOG.warn("Multiple memo table entries available, searching for preferred type.");
-		ArrayList<MemoTableEntry> tmp2 = new ArrayList<MemoTableEntry>();
-		for( MemoTableEntry me : tmp )
-			if( me.type == pref )
-				tmp2.add(me);
-		if( !tmp2.isEmpty() ) {
-			if( tmp2.size() > 1 && SpoofCompiler.LDEBUG )
-				LOG.warn("Multiple memo table entries w/ preferred type available, return max refs entry.");
-			return getMaxRefsEntry(tmp2);
-		}
-		else {
-			if( SpoofCompiler.LDEBUG )
-				LOG.warn("Multiple memo table entries available but none with preferred type, return max refs entry.");
-			return getMaxRefsEntry(tmp);
-		}
-	}
-	
-	private static MemoTableEntry getMaxRefsEntry(List<MemoTableEntry> tmp) {
-		return Collections.max(tmp, Comparator.comparing(p -> p.countPlanRefs()));
-	}
-	
-	private static boolean isValid(MemoTableEntry me, Hop hop) {
-		return (me.type == TemplateType.OuterProdTpl 
-				&& (me.closed || HopRewriteUtils.isBinaryMatrixMatrixOperation(hop)))
-			|| (me.type == TemplateType.RowAggTpl && me.closed)	
-			|| (me.type == TemplateType.CellTpl);
+		if( tmp == null || tmp.isEmpty() )
+			return null;
+
+		//single plan per type, get plan w/ best rank in preferred order
+		return Collections.min(tmp, Comparator.comparing(
+			p -> (p.type==pref) ? -1 : p.type.getRank()));
 	}
 	
 	public int size() {
@@ -242,7 +229,7 @@ public class CPlanMemoTable
 		sb.append("----------------------------------\n");
 		sb.append("MEMO TABLE: \n");
 		sb.append("----------------------------------\n");
-		for( Entry<Long, ArrayList<MemoTableEntry>> e : _plans.entrySet() ) {
+		for( Entry<Long, List<MemoTableEntry>> e : _plans.entrySet() ) {
 			sb.append(e.getKey() + " "+_hopRefs.get(e.getKey()).getOpString()+": ");
 			sb.append(Arrays.toString(e.getValue().toArray(new MemoTableEntry[0]))+"\n");
 		}
@@ -252,6 +239,10 @@ public class CPlanMemoTable
 		sb.append("----------------------------------\n");
 		return sb.toString();	
 	}
+
+	////////////////////////////////////////
+	// Memo table entry abstractions
+	//////
 	
 	public static class MemoTableEntry 
 	{

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b3120ce2/src/main/java/org/apache/sysml/hops/codegen/template/CellTpl.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/CellTpl.java b/src/main/java/org/apache/sysml/hops/codegen/template/CellTpl.java
deleted file mode 100644
index b919b6d..0000000
--- a/src/main/java/org/apache/sysml/hops/codegen/template/CellTpl.java
+++ /dev/null
@@ -1,304 +0,0 @@
-/*
- * 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.hops.codegen.template;
-
-import java.util.ArrayList;
-import java.util.Comparator;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.List;
-import java.util.stream.Collectors;
-
-import org.apache.sysml.hops.AggBinaryOp;
-import org.apache.sysml.hops.AggUnaryOp;
-import org.apache.sysml.hops.BinaryOp;
-import org.apache.sysml.hops.Hop;
-import org.apache.sysml.hops.UnaryOp;
-import org.apache.sysml.hops.Hop.AggOp;
-import org.apache.sysml.hops.Hop.Direction;
-import org.apache.sysml.hops.Hop.OpOp2;
-import org.apache.sysml.hops.IndexingOp;
-import org.apache.sysml.hops.LiteralOp;
-import org.apache.sysml.hops.TernaryOp;
-import org.apache.sysml.hops.codegen.cplan.CNode;
-import org.apache.sysml.hops.codegen.cplan.CNodeBinary;
-import org.apache.sysml.hops.codegen.cplan.CNodeBinary.BinType;
-import org.apache.sysml.hops.codegen.cplan.CNodeCell;
-import org.apache.sysml.hops.codegen.cplan.CNodeData;
-import org.apache.sysml.hops.codegen.cplan.CNodeTpl;
-import org.apache.sysml.hops.codegen.cplan.CNodeUnary;
-import org.apache.sysml.hops.codegen.cplan.CNodeUnary.UnaryType;
-import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntry;
-import org.apache.sysml.hops.codegen.cplan.CNodeTernary;
-import org.apache.sysml.hops.codegen.cplan.CNodeTernary.TernaryType;
-import org.apache.sysml.hops.rewrite.HopRewriteUtils;
-import org.apache.sysml.parser.Expression.DataType;
-import org.apache.sysml.runtime.matrix.data.Pair;
-
-public class CellTpl extends BaseTpl 
-{	
-	public CellTpl() {
-		super(TemplateType.CellTpl);
-	}
-
-	@Override
-	public boolean open(Hop hop) {
-		return isValidOperation(hop)
-			|| (hop instanceof IndexingOp && ((IndexingOp)hop).isColLowerEqualsUpper());
-	}
-
-	@Override
-	public boolean fuse(Hop hop, Hop input) {
-		return !isClosed() && (isValidOperation(hop) 
-			|| (HopRewriteUtils.isSum(hop) && ((AggUnaryOp) hop).getDirection()!= Direction.Col)
-			|| (HopRewriteUtils.isMatrixMultiply(hop) && hop.getDim1()==1 && hop.getDim2()==1)
-				&& HopRewriteUtils.isTransposeOperation(hop.getInput().get(0)));
-	}
-
-	@Override
-	public boolean merge(Hop hop, Hop input) {
-		//merge of other cell tpl possible
-		return (!isClosed() && isValidOperation(hop));
-	}
-
-	@Override
-	public CloseType close(Hop hop) {
-		//need to close cell tpl after aggregation, see fuse for exact properties
-		if( (HopRewriteUtils.isSum(hop) && ((AggUnaryOp) hop).getDirection()!= Direction.Col)
-			|| (HopRewriteUtils.isMatrixMultiply(hop) && hop.getDim1()==1 && hop.getDim2()==1) )
-			return CloseType.CLOSED_VALID;
-		else if( hop instanceof AggUnaryOp || hop instanceof AggBinaryOp )
-			return CloseType.CLOSED_INVALID;
-		else
-			return CloseType.OPEN;
-	}
-
-	@Override
-	public Pair<Hop[], CNodeTpl> constructCplan(Hop hop, CPlanMemoTable memo, boolean compileLiterals) 
-	{
-		//recursively process required cplan output
-		HashSet<Hop> inHops = new HashSet<Hop>();
-		HashMap<Long, CNode> tmp = new HashMap<Long, CNode>();
-		hop.resetVisitStatus();
-		rConstructCplan(hop, memo, tmp, inHops, compileLiterals);
-		hop.resetVisitStatus();
-		
-		//reorder inputs (ensure matrices/vectors come first) and prune literals
-		//note: we order by number of cells and subsequently sparsity to ensure
-		//that sparse inputs are used as the main input w/o unnecessary conversion
-		List<Hop> sinHops = inHops.stream()
-			.filter(h -> !(h.getDataType().isScalar() && tmp.get(h.getHopID()).isLiteral()))
-			.sorted(new HopInputComparator()).collect(Collectors.toList());
-		
-		//construct template node
-		ArrayList<CNode> inputs = new ArrayList<CNode>();
-		for( Hop in : sinHops )
-			inputs.add(tmp.get(in.getHopID()));
-		CNode output = tmp.get(hop.getHopID());
-		CNodeCell tpl = new CNodeCell(inputs, output);
-		tpl.setCellType(TemplateUtils.getCellType(hop));
-		tpl.setSparseSafe((HopRewriteUtils.isBinary(hop, OpOp2.MULT) && hop.getInput().contains(sinHops.get(0)))
-				|| (HopRewriteUtils.isBinary(hop, OpOp2.DIV) && hop.getInput().get(0) == sinHops.get(0)));
-		tpl.setRequiresCastDtm(hop instanceof AggBinaryOp);
-		
-		// return cplan instance
-		return new Pair<Hop[],CNodeTpl>(sinHops.toArray(new Hop[0]), tpl);
-	}
-	
-	private void rConstructCplan(Hop hop, CPlanMemoTable memo, HashMap<Long, CNode> tmp, HashSet<Hop> inHops, boolean compileLiterals) 
-	{
-		//recursively process required childs
-		MemoTableEntry me = memo.getBest(hop.getHopID(), TemplateType.CellTpl);
-		for( int i=0; i<hop.getInput().size(); i++ ) {
-			Hop c = hop.getInput().get(i);
-			if( me.isPlanRef(i) )
-				rConstructCplan(c, memo, tmp, inHops, compileLiterals);
-			else {
-				CNodeData cdata = TemplateUtils.createCNodeData(c, compileLiterals);	
-				tmp.put(c.getHopID(), cdata);
-				inHops.add(c);
-			}
-		}
-		
-		//construct cnode for current hop
-		CNode out = null;
-		if(hop instanceof UnaryOp)
-		{
-			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
-			if( TemplateUtils.isColVector(cdata1) )
-				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_R);
-			else if( cdata1 instanceof CNodeData && hop.getInput().get(0).getDataType().isMatrix() )
-				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_RC);
-			
-			String primitiveOpName = ((UnaryOp)hop).getOp().toString();
-			out = new CNodeUnary(cdata1, UnaryType.valueOf(primitiveOpName));
-		}
-		else if(hop instanceof BinaryOp)
-		{
-			BinaryOp bop = (BinaryOp) hop;
-			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
-			CNode cdata2 = tmp.get(hop.getInput().get(1).getHopID());
-			String primitiveOpName = bop.getOp().toString();
-			
-			//cdata1 is vector
-			if( TemplateUtils.isColVector(cdata1) )
-				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_R);
-			else if( cdata1 instanceof CNodeData && hop.getInput().get(0).getDataType().isMatrix() )
-				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_RC);
-			
-			//cdata2 is vector
-			if( TemplateUtils.isColVector(cdata2) )
-				cdata2 = new CNodeUnary(cdata2, UnaryType.LOOKUP_R);
-			else if( cdata2 instanceof CNodeData && hop.getInput().get(1).getDataType().isMatrix() )
-				cdata2 = new CNodeUnary(cdata2, UnaryType.LOOKUP_RC);
-			
-			if( bop.getOp()==OpOp2.POW && cdata2.isLiteral() && cdata2.getVarname().equals("2") )
-				out = new CNodeUnary(cdata1, UnaryType.POW2);
-			else if( bop.getOp()==OpOp2.MULT && cdata2.isLiteral() && cdata2.getVarname().equals("2") )
-				out = new CNodeUnary(cdata1, UnaryType.MULT2);
-			else //default binary	
-				out = new CNodeBinary(cdata1, cdata2, BinType.valueOf(primitiveOpName));
-		}
-		else if(hop instanceof TernaryOp) 
-		{
-			TernaryOp top = (TernaryOp) hop;
-			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
-			CNode cdata2 = tmp.get(hop.getInput().get(1).getHopID());
-			CNode cdata3 = tmp.get(hop.getInput().get(2).getHopID());
-			
-			//cdata1 is vector
-			if( TemplateUtils.isColVector(cdata1) )
-				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_R);
-			else if( cdata1 instanceof CNodeData && hop.getInput().get(0).getDataType().isMatrix() )
-				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_RC);
-			
-			//cdata3 is vector
-			if( TemplateUtils.isColVector(cdata3) )
-				cdata3 = new CNodeUnary(cdata3, UnaryType.LOOKUP_R);
-			else if( cdata3 instanceof CNodeData && hop.getInput().get(2).getDataType().isMatrix() )
-				cdata3 = new CNodeUnary(cdata3, UnaryType.LOOKUP_RC);
-			
-			//construct ternary cnode, primitive operation derived from OpOp3
-			out = new CNodeTernary(cdata1, cdata2, cdata3, 
-					TernaryType.valueOf(top.getOp().toString()));
-		}
-		else if( hop instanceof IndexingOp ) 
-		{
-			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
-			out = new CNodeTernary(cdata1, 
-					TemplateUtils.createCNodeData(new LiteralOp(hop.getInput().get(0).getDim2()), true), 
-					TemplateUtils.createCNodeData(hop.getInput().get(4), true),
-					TernaryType.LOOKUP_RC1);
-		}
-		else if( HopRewriteUtils.isTransposeOperation(hop) ) 
-		{
-			out = tmp.get(hop.getInput().get(0).getHopID());	
-		}
-		else if( hop instanceof AggUnaryOp && ((AggUnaryOp)hop).getOp() == AggOp.SUM
-			&& (((AggUnaryOp) hop).getDirection() == Direction.RowCol 
-			|| ((AggUnaryOp) hop).getDirection() == Direction.Row) )
-		{
-			out = tmp.get(hop.getInput().get(0).getHopID());
-		}
-		else if( hop instanceof AggBinaryOp ) {
-			//guaranteed to be a dot product, so there are two cases:
-			//(1) t(X)%*%X -> sum(X^2) and t(X) %*% Y -> sum(X*Y)
-			if( HopRewriteUtils.isTransposeOfItself(hop.getInput().get(0), hop.getInput().get(1)) ) {
-				CNode cdata1 = tmp.get(hop.getInput().get(1).getHopID());
-				out = new CNodeUnary(cdata1, UnaryType.POW2);
-			}
-			else {
-				CNode cdata1 = TemplateUtils.skipTranspose(tmp.get(hop.getInput().get(0).getHopID()), 
-						hop.getInput().get(0), tmp, compileLiterals);
-				if( TemplateUtils.isColVector(cdata1) )
-					cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_R);
-				CNode cdata2 = tmp.get(hop.getInput().get(1).getHopID());
-				if( TemplateUtils.isColVector(cdata2) )
-					cdata2 = new CNodeUnary(cdata2, UnaryType.LOOKUP_R);
-				out = new CNodeBinary(cdata1, cdata2, BinType.MULT);
-			}
-		} 
-		
-		tmp.put(hop.getHopID(), out);
-	}
-	
-	private static boolean isValidOperation(Hop hop) 
-	{	
-		//prepare indicators for binary operations
-		boolean isBinaryMatrixScalar = false;
-		boolean isBinaryMatrixVector = false;
-		boolean isBinaryMatrixMatrixDense = false;
-		if( hop instanceof BinaryOp && hop.getDataType().isMatrix() ) {
-			Hop left = hop.getInput().get(0);
-			Hop right = hop.getInput().get(1);
-			DataType ldt = left.getDataType();
-			DataType rdt = right.getDataType();
-			
-			isBinaryMatrixScalar = (ldt.isScalar() || rdt.isScalar());	
-			isBinaryMatrixVector = hop.dimsKnown() 
-				&& ((ldt.isMatrix() && TemplateUtils.isVectorOrScalar(right) && !TemplateUtils.isBinaryMatrixRowVector(hop)) 
-				|| (rdt.isMatrix() && TemplateUtils.isVectorOrScalar(left) && !TemplateUtils.isBinaryMatrixRowVector(hop)) );
-			isBinaryMatrixMatrixDense = hop.dimsKnown() && HopRewriteUtils.isEqualSize(left, right)
-				&& ldt.isMatrix() && rdt.isMatrix() && !HopRewriteUtils.isSparse(left) && !HopRewriteUtils.isSparse(right);
-		}
-				
-		//prepare indicators for ternary operations
-		boolean isTernaryVectorScalarVector = false;
-		boolean isTernaryMatrixScalarMatrixDense = false;
-		if( hop instanceof TernaryOp && hop.getInput().size()==3 && hop.dimsKnown() 
-			&& HopRewriteUtils.checkInputDataTypes(hop, DataType.MATRIX, DataType.SCALAR, DataType.MATRIX)) {
-			Hop left = hop.getInput().get(0);
-			Hop right = hop.getInput().get(2);
-			
-			isTernaryVectorScalarVector = TemplateUtils.isVector(left) && TemplateUtils.isVector(right);
-			isTernaryMatrixScalarMatrixDense = HopRewriteUtils.isEqualSize(left, right) 
-				&& !HopRewriteUtils.isSparse(left) && !HopRewriteUtils.isSparse(right);
-		}
-		
-		//check supported unary, binary, ternary operations
-		return hop.getDataType() == DataType.MATRIX && TemplateUtils.isOperationSupported(hop) && (hop instanceof UnaryOp 
-				|| isBinaryMatrixScalar || isBinaryMatrixVector || isBinaryMatrixMatrixDense 
-				|| isTernaryVectorScalarVector || isTernaryMatrixScalarMatrixDense);	
-	}
-	
-	/**
-	 * Comparator to order input hops of the cell template. We try to order 
-	 * matrices-vectors-scalars via sorting by number of cells and for 
-	 * equal number of cells by sparsity to prefer sparse inputs as the main 
-	 * input for sparsity exploitation.
-	 */
-	public static class HopInputComparator implements Comparator<Hop> 
-	{
-		@Override
-		public int compare(Hop h1, Hop h2) {
-			long ncells1 = h1.getDataType()==DataType.SCALAR ? Long.MIN_VALUE : 
-				h1.dimsKnown() ? h1.getDim1()*h1.getDim2() : Long.MAX_VALUE;
-			long ncells2 = h2.getDataType()==DataType.SCALAR ? Long.MIN_VALUE :
-				h2.dimsKnown() ? h2.getDim1()*h2.getDim2() : Long.MAX_VALUE;
-			if( ncells1 > ncells2 ) 
-				return -1;
-			else if( ncells1 < ncells2) 
-				return 1;
-			return Long.compare(
-				h1.dimsKnown(true) ? h1.getNnz() : ncells1, 
-				h2.dimsKnown(true) ? h2.getNnz() : ncells2);
-		}
-	}
-}

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b3120ce2/src/main/java/org/apache/sysml/hops/codegen/template/OuterProductTpl.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/OuterProductTpl.java b/src/main/java/org/apache/sysml/hops/codegen/template/OuterProductTpl.java
deleted file mode 100644
index 3dce155..0000000
--- a/src/main/java/org/apache/sysml/hops/codegen/template/OuterProductTpl.java
+++ /dev/null
@@ -1,213 +0,0 @@
-/*
- * 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.hops.codegen.template;
-
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.LinkedList;
-
-import org.apache.sysml.hops.AggBinaryOp;
-import org.apache.sysml.hops.AggUnaryOp;
-import org.apache.sysml.hops.BinaryOp;
-import org.apache.sysml.hops.DataOp;
-import org.apache.sysml.hops.Hop;
-import org.apache.sysml.hops.UnaryOp;
-import org.apache.sysml.hops.Hop.AggOp;
-import org.apache.sysml.hops.Hop.Direction;
-import org.apache.sysml.hops.Hop.OpOp2;
-import org.apache.sysml.hops.codegen.cplan.CNode;
-import org.apache.sysml.hops.codegen.cplan.CNodeBinary;
-import org.apache.sysml.hops.codegen.cplan.CNodeBinary.BinType;
-import org.apache.sysml.hops.codegen.cplan.CNodeUnary;
-import org.apache.sysml.hops.codegen.cplan.CNodeUnary.UnaryType;
-import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntry;
-import org.apache.sysml.hops.codegen.cplan.CNodeData;
-import org.apache.sysml.hops.codegen.cplan.CNodeOuterProduct;
-import org.apache.sysml.hops.codegen.cplan.CNodeTpl;
-import org.apache.sysml.hops.rewrite.HopRewriteUtils;
-import org.apache.sysml.runtime.codegen.SpoofOuterProduct.OutProdType;
-import org.apache.sysml.runtime.matrix.data.Pair;
-
-public class OuterProductTpl extends BaseTpl {
-	
-	public OuterProductTpl() {
-		super(TemplateType.OuterProdTpl);
-	}
-
-	@Override
-	public boolean open(Hop hop) {
-		//open on outer product like matrix mult (output larger than common dim)
-		return HopRewriteUtils.isOuterProductLikeMM(hop)
-			&& hop.getDim1()>256 && hop.getDim2() > 256;
-	}
-
-	@Override
-	public boolean fuse(Hop hop, Hop input) {
-		return !isClosed() 
-			&&((hop instanceof UnaryOp && TemplateUtils.isOperationSupported(hop))  
-			|| (hop instanceof BinaryOp && TemplateUtils.isOperationSupported(hop)
-				&& (TemplateUtils.isBinaryMatrixColVector(hop) || HopRewriteUtils.isBinaryMatrixScalarOperation(hop)
-				|| (HopRewriteUtils.isBinaryMatrixMatrixOperation(hop) && HopRewriteUtils.isBinary(hop, OpOp2.MULT, OpOp2.DIV)) )) 
-			|| HopRewriteUtils.isTransposeOperation(hop) 
-			|| (hop instanceof AggBinaryOp && !HopRewriteUtils.isOuterProductLikeMM(hop))
-			|| (hop instanceof AggUnaryOp && ((AggUnaryOp)hop).getDirection()==Direction.RowCol));
-	}
-
-	@Override
-	public boolean merge(Hop hop, Hop input) {
-		return !isClosed() && 
-			(TemplateUtils.isBinaryMatrixRowVector(hop)
-			|| HopRewriteUtils.isBinaryMatrixScalarOperation(hop));
-	}
-
-	@Override
-	public CloseType close(Hop hop) {
-		// close on second matrix multiply (after open) or unary aggregate
-		if( hop instanceof AggUnaryOp && HopRewriteUtils.isOuterProductLikeMM(hop.getInput().get(0)) )
-			return CloseType.CLOSED_INVALID;
-		else if( (hop instanceof AggUnaryOp) 
-			|| (hop instanceof AggBinaryOp && !HopRewriteUtils.isOuterProductLikeMM(hop) 
-					&& !HopRewriteUtils.isTransposeOperation(hop.getParent().get(0)))
-			|| (HopRewriteUtils.isTransposeOperation(hop) && hop.getInput().get(0) instanceof AggBinaryOp
-					&& !HopRewriteUtils.isOuterProductLikeMM(hop.getInput().get(0)) ))
-			return CloseType.CLOSED_VALID;
-		else
-			return CloseType.OPEN;
-	}
-
-	public Pair<Hop[], CNodeTpl> constructCplan(Hop hop, CPlanMemoTable memo, boolean compileLiterals) 
-	{
-		//recursively process required cplan output
-		HashSet<Hop> inHops = new HashSet<Hop>();
-		HashMap<String,Hop> inHops2 = new HashMap<String, Hop>();
-		HashMap<Long, CNode> tmp = new HashMap<Long, CNode>();
-		hop.resetVisitStatus();
-		rConstructCplan(hop, memo, tmp, inHops, inHops2, compileLiterals);
-		hop.resetVisitStatus();
-		
-		//reorder inputs (ensure matrix is first input)
-		Hop X = inHops2.get("_X");
-		Hop U = inHops2.get("_U");
-		Hop V = inHops2.get("_V");
-		LinkedList<Hop> sinHops = new LinkedList<Hop>(inHops);
-		sinHops.remove(V); sinHops.addFirst(V);
-		sinHops.remove(U); sinHops.addFirst(U);
-		sinHops.remove(X); sinHops.addFirst(X);
-		
-		//construct template node
-		ArrayList<CNode> inputs = new ArrayList<CNode>();
-		for( Hop in : sinHops )
-			if( in != null )
-				inputs.add(tmp.get(in.getHopID()));
-
-		CNode output = tmp.get(hop.getHopID());
-		CNodeOuterProduct tpl = new CNodeOuterProduct(inputs, output);
-		tpl.setOutProdType(TemplateUtils.getOuterProductType(X, U, V, hop));
-		tpl.setTransposeOutput(!HopRewriteUtils.isTransposeOperation(hop)
-			&& tpl.getOutProdType()==OutProdType.LEFT_OUTER_PRODUCT); 
-		
-		return new Pair<Hop[],CNodeTpl>(sinHops.toArray(new Hop[0]), tpl);
-	}
-	
-	private void rConstructCplan(Hop hop, CPlanMemoTable memo, HashMap<Long, CNode> tmp, HashSet<Hop> inHops, HashMap<String, Hop> inHops2, boolean compileLiterals) 
-	{
-		//recursively process required childs
-		MemoTableEntry me = memo.getBest(hop.getHopID(), TemplateType.OuterProdTpl);
-		for( int i=0; i<hop.getInput().size(); i++ ) {
-			Hop c = hop.getInput().get(i);
-			if( me.isPlanRef(i) )
-				rConstructCplan(c, memo, tmp, inHops, inHops2, compileLiterals);
-			else {
-				CNodeData cdata = TemplateUtils.createCNodeData(c, compileLiterals);	
-				tmp.put(c.getHopID(), cdata);
-				inHops.add(c);
-			}
-		}
-		
-		//construct cnode for current hop
-		CNode out = null;
-		if(hop instanceof UnaryOp)
-		{
-			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
-			String primitiveOpName = ((UnaryOp)hop).getOp().toString();
-			out = new CNodeUnary(cdata1, UnaryType.valueOf(primitiveOpName));
-		}
-		else if(hop instanceof BinaryOp)
-		{
-			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
-			CNode cdata2 = tmp.get(hop.getInput().get(1).getHopID());
-			String primitiveOpName = ((BinaryOp)hop).getOp().toString();
-			
-			if( (cdata1.getNumRows() > 1 && cdata1.getNumCols() == 1) || (cdata1.getNumRows() == 1 && cdata1.getNumCols() > 1) ) {
-				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_R);
-			}
-			if( (cdata2.getNumRows() > 1 && cdata2.getNumCols() == 1) || (cdata2.getNumRows() == 1 && cdata2.getNumCols() > 1) ) {
-				cdata2 = new CNodeUnary(cdata2, UnaryType.LOOKUP_R);
-			}
-			
-			if( HopRewriteUtils.isEqualSize(hop.getInput().get(0), hop.getInput().get(1))
-				&& hop.getInput().get(0) instanceof DataOp )
-				inHops2.put("_X", hop.getInput().get(0));
-			
-			out = new CNodeBinary(cdata1, cdata2, BinType.valueOf(primitiveOpName));
-		}
-		else if(hop instanceof AggBinaryOp)
-		{
-			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
-			CNode cdata2 = tmp.get(hop.getInput().get(1).getHopID());
-			
-			//handle tanspose in outer or final product
-			cdata1 = TemplateUtils.skipTranspose(cdata1, hop.getInput().get(0), tmp, compileLiterals);
-			cdata2 = TemplateUtils.skipTranspose(cdata2, hop.getInput().get(1), tmp, compileLiterals);
-			
-			//outerproduct U%*%t(V), see open
-			if( HopRewriteUtils.isOuterProductLikeMM(hop) )
-			{
-				//keep U and V for later reference
-				inHops2.put("_U", hop.getInput().get(0));
-				if( HopRewriteUtils.isTransposeOperation(hop.getInput().get(1)) )
-					inHops2.put("_V", hop.getInput().get(1).getInput().get(0));
-				else
-					inHops2.put("_V", hop.getInput().get(1));
-				
-				out = new CNodeBinary(cdata1, cdata2, BinType.DOT_PRODUCT);
-			}
-			//final left/right matrix mult, see close
-			else {
-				if( cdata1.getDataType().isScalar() )
-					out = new CNodeBinary(cdata1, cdata2, BinType.VECT_MULT_ADD);	
-				else
-					out = new CNodeBinary(cdata2, cdata1, BinType.VECT_MULT_ADD);	
-			}
-		}
-		else if( HopRewriteUtils.isTransposeOperation(hop) ) 
-		{
-			out = tmp.get(hop.getInput().get(0).getHopID());	
-		}
-		else if( hop instanceof AggUnaryOp && ((AggUnaryOp)hop).getOp() == AggOp.SUM
-			&& ((AggUnaryOp)hop).getDirection() == Direction.RowCol )
-		{
-			out = tmp.get(hop.getInput().get(0).getHopID());
-		}
-		
-		tmp.put(hop.getHopID(), out);
-	}
-}

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b3120ce2/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelection.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelection.java b/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelection.java
new file mode 100644
index 0000000..e7bc554
--- /dev/null
+++ b/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelection.java
@@ -0,0 +1,73 @@
+/*
+ * 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.hops.codegen.template;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+
+import org.apache.sysml.hops.Hop;
+import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntry;
+import org.apache.sysml.hops.codegen.template.TemplateBase.TemplateType;
+import org.apache.sysml.hops.rewrite.HopRewriteUtils;
+
+public abstract class PlanSelection 
+{
+	/**
+	 * Given a HOP DAG G, and a set of partial fusions plans P, find the set of optimal, 
+	 * non-conflicting fusion plans P' that applied to G minimizes costs C with
+	 * P' = \argmin_{p \subseteq P} C(G, p) s.t. Z \vDash p, where Z is a set of 
+	 * constraints such as memory budgets and block size restrictions per fused operator.
+	 * 
+	 * @param memo partial fusion plans P
+	 * @param roots entry points of HOP DAG G
+	 */
+	public abstract void selectPlans(CPlanMemoTable memo, ArrayList<Hop> roots);	
+	
+	/**
+	 * Determines if the given partial fusion plan is valid.
+	 * 
+	 * @param me memo table entry
+	 * @param hop current hop
+	 * @return true if entry is valid as top-level plan
+	 */
+	protected static boolean isValid(MemoTableEntry me, Hop hop) {
+		return (me.type == TemplateType.OuterProdTpl 
+				&& (me.closed || HopRewriteUtils.isBinaryMatrixMatrixOperation(hop)))
+			|| (me.type == TemplateType.RowAggTpl && me.closed)	
+			|| (me.type == TemplateType.CellTpl);
+	}
+	
+	/**
+	 * Basic plan comparator to compare memo table entries with regard to
+	 * a pre-defined template preference order and the number of references.
+	 */
+	protected class BasicPlanComparator implements Comparator<MemoTableEntry> {
+		@Override
+		public int compare(MemoTableEntry o1, MemoTableEntry o2) {
+			//for different types, select preferred type
+			if( o1.type != o2.type )
+				return Integer.compare(o1.type.getRank(), o2.type.getRank());
+			
+			//for same type, prefer plan with more refs
+			return Integer.compare(
+				3-o1.countPlanRefs(), 3-o2.countPlanRefs());
+		}
+	}
+}

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b3120ce2/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelectionFuseAll.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelectionFuseAll.java b/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelectionFuseAll.java
new file mode 100644
index 0000000..e615f0b
--- /dev/null
+++ b/src/main/java/org/apache/sysml/hops/codegen/template/PlanSelectionFuseAll.java
@@ -0,0 +1,85 @@
+/*
+ * 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.hops.codegen.template;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Map.Entry;
+import java.util.HashSet;
+import java.util.List;
+
+import org.apache.sysml.hops.Hop;
+import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntry;
+import org.apache.sysml.hops.codegen.template.TemplateBase.TemplateType;
+
+
+public class PlanSelectionFuseAll extends PlanSelection
+{	
+	private HashMap<Long, List<MemoTableEntry>> _bestPlans = 
+			new HashMap<Long, List<MemoTableEntry>>();
+	
+	@Override
+	public void selectPlans(CPlanMemoTable memo, ArrayList<Hop> roots) {
+		//pruning and collection pass
+		for( Hop hop : roots )
+			rSelectPlans(memo, hop, null);
+		
+		//take all distinct best plans
+		for( Entry<Long, List<MemoTableEntry>> e : _bestPlans.entrySet() )
+			memo.setDistinct(e.getKey(), e.getValue());
+	}
+	
+	private void rSelectPlans(CPlanMemoTable memo, Hop current, TemplateType currentType) 
+	{	
+		//step 1: prune subsumed plans of same type
+		if( memo.contains(current.getHopID()) ) {
+			HashSet<MemoTableEntry> rmSet = new HashSet<MemoTableEntry>();
+			List<MemoTableEntry> hopP = memo.get(current.getHopID());
+			for( MemoTableEntry e1 : hopP )
+				for( MemoTableEntry e2 : hopP )
+					if( e1 != e2 && e1.subsumes(e2) )
+						rmSet.add(e2);
+			memo.remove(current, rmSet);
+		}
+		
+		//step 2: select plan for current path
+		MemoTableEntry best = null;
+		if( memo.contains(current.getHopID()) ) {
+			if( currentType == null ) {
+				best = memo.get(current.getHopID()).stream()
+					.filter(p -> isValid(p, current))
+					.min(new BasicPlanComparator()).orElse(null);
+			}
+			else {
+				
+				best = memo.get(current.getHopID()).stream()
+					.filter(p -> p.type==currentType || p.type==TemplateType.CellTpl)
+					.min(Comparator.comparing(p -> 3-p.countPlanRefs())).orElse(null);
+			}
+		}
+		
+		//step 3: recursively process children
+		for( int i=0; i< current.getInput().size(); i++ ) {
+			TemplateType pref = (best!=null && best.isPlanRef(i))? best.type : null;
+			rSelectPlans(memo, current.getInput().get(i), pref);
+		}
+	}	
+}

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b3120ce2/src/main/java/org/apache/sysml/hops/codegen/template/RowAggTpl.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/RowAggTpl.java b/src/main/java/org/apache/sysml/hops/codegen/template/RowAggTpl.java
deleted file mode 100644
index c16c831..0000000
--- a/src/main/java/org/apache/sysml/hops/codegen/template/RowAggTpl.java
+++ /dev/null
@@ -1,246 +0,0 @@
-/*
- * 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.hops.codegen.template;
-
-import java.util.ArrayList;
-import java.util.Comparator;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.List;
-import java.util.stream.Collectors;
-
-import org.apache.sysml.hops.AggBinaryOp;
-import org.apache.sysml.hops.AggUnaryOp;
-import org.apache.sysml.hops.BinaryOp;
-import org.apache.sysml.hops.Hop;
-import org.apache.sysml.hops.IndexingOp;
-import org.apache.sysml.hops.LiteralOp;
-import org.apache.sysml.hops.codegen.cplan.CNode;
-import org.apache.sysml.hops.codegen.cplan.CNodeBinary;
-import org.apache.sysml.hops.codegen.cplan.CNodeBinary.BinType;
-import org.apache.sysml.hops.codegen.cplan.CNodeTernary.TernaryType;
-import org.apache.sysml.hops.codegen.cplan.CNodeData;
-import org.apache.sysml.hops.codegen.cplan.CNodeRowAgg;
-import org.apache.sysml.hops.codegen.cplan.CNodeTernary;
-import org.apache.sysml.hops.codegen.cplan.CNodeTpl;
-import org.apache.sysml.hops.codegen.cplan.CNodeUnary;
-import org.apache.sysml.hops.codegen.cplan.CNodeUnary.UnaryType;
-import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntry;
-import org.apache.sysml.hops.rewrite.HopRewriteUtils;
-import org.apache.sysml.hops.Hop.AggOp;
-import org.apache.sysml.hops.Hop.Direction;
-import org.apache.sysml.hops.Hop.OpOp2;
-import org.apache.sysml.parser.Expression.DataType;
-import org.apache.sysml.runtime.matrix.data.Pair;
-
-public class RowAggTpl extends BaseTpl {
-
-	public RowAggTpl() {
-		super(TemplateType.RowAggTpl);
-	}
-	
-	@Override
-	public boolean open(Hop hop) {
-		//any unary or binary aggregate operation with a vector output, but exclude binary aggregate
-		//with transposed input to avoid counter-productive fusion
-		return ( ((hop instanceof AggBinaryOp && hop.getInput().get(1).getDim1()>1
-				&& !HopRewriteUtils.isTransposeOperation(hop.getInput().get(0))) 
-			|| (hop instanceof AggUnaryOp && ((AggUnaryOp)hop).getOp()==AggOp.SUM ))  			  
-				&& ( (hop.getDim1()==1 && hop.getDim2()!=1) || (hop.getDim1()!=1 && hop.getDim2()==1) )  );
-	}
-
-	@Override
-	public boolean fuse(Hop hop, Hop input) {
-		return !isClosed() && 
-			(  (hop instanceof BinaryOp && (HopRewriteUtils.isBinaryMatrixColVectorOperation(hop)
-					|| HopRewriteUtils.isBinaryMatrixScalarOperation(hop))) 
-			|| (hop instanceof AggUnaryOp && ((AggUnaryOp)hop).getDirection()==Direction.Col)
-			|| (hop instanceof AggBinaryOp && HopRewriteUtils.isTransposeOperation(hop.getInput().get(0))));
-	}
-
-	@Override
-	public boolean merge(Hop hop, Hop input) {
-		//merge rowagg tpl with cell tpl if input is a vector
-		return !isClosed() &&
-			(hop instanceof BinaryOp && input.getDim2()==1 ); //matrix-scalar/vector-vector ops )
-	}
-
-	@Override
-	public CloseType close(Hop hop) {
-		//close on column aggregate (e.g., colSums, t(X)%*%y)
-		if( hop instanceof AggUnaryOp && ((AggUnaryOp)hop).getDirection()==Direction.Col
-			|| (hop instanceof AggBinaryOp && HopRewriteUtils.isTransposeOperation(hop.getInput().get(0))) )
-			return CloseType.CLOSED_VALID;
-		else
-			return CloseType.OPEN;
-	}
-
-	@Override
-	public Pair<Hop[], CNodeTpl> constructCplan(Hop hop, CPlanMemoTable memo, boolean compileLiterals) {
-		//recursively process required cplan output
-		HashSet<Hop> inHops = new HashSet<Hop>();
-		HashMap<String, Hop> inHops2 = new HashMap<String,Hop>();
-		HashMap<Long, CNode> tmp = new HashMap<Long, CNode>();
-		hop.resetVisitStatus();
-		rConstructCplan(hop, memo, tmp, inHops, inHops2, compileLiterals);
-		hop.resetVisitStatus();
-		
-		//reorder inputs (ensure matrix is first input, and other inputs ordered by size)
-		List<Hop> sinHops = inHops.stream()
-			.filter(h -> !(h.getDataType().isScalar() && tmp.get(h.getHopID()).isLiteral()))
-			.sorted(new HopInputComparator(inHops2.get("X"))).collect(Collectors.toList());
-		
-		//construct template node
-		ArrayList<CNode> inputs = new ArrayList<CNode>();
-		for( Hop in : sinHops )
-			inputs.add(tmp.get(in.getHopID()));
-		CNode output = tmp.get(hop.getHopID());
-		CNodeRowAgg tpl = new CNodeRowAgg(inputs, output);
-		
-		// return cplan instance
-		return new Pair<Hop[],CNodeTpl>(sinHops.toArray(new Hop[0]), tpl);
-	}
-
-	private void rConstructCplan(Hop hop, CPlanMemoTable memo, HashMap<Long, CNode> tmp, HashSet<Hop> inHops, HashMap<String, Hop> inHops2, boolean compileLiterals) 
-	{	
-		//recursively process required childs
-		MemoTableEntry me = memo.getBest(hop.getHopID(), TemplateType.RowAggTpl);
-		for( int i=0; i<hop.getInput().size(); i++ ) {
-			Hop c = hop.getInput().get(i);
-			if( me.isPlanRef(i) )
-				rConstructCplan(c, memo, tmp, inHops, inHops2, compileLiterals);
-			else {
-				CNodeData cdata = TemplateUtils.createCNodeData(c, compileLiterals);	
-				tmp.put(c.getHopID(), cdata);
-				inHops.add(c);
-			}
-		}
-				
-		//construct cnode for current hop
-		CNode out = null;
-		if(hop instanceof AggUnaryOp)
-		{
-			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
-			if(  ((AggUnaryOp)hop).getDirection() == Direction.Row && ((AggUnaryOp)hop).getOp() == AggOp.SUM  ) {
-				if(hop.getInput().get(0).getDim2()==1)
-					out = (cdata1.getDataType()==DataType.SCALAR) ? cdata1 : new CNodeUnary(cdata1,UnaryType.LOOKUP_R);
-				else {
-					out = new CNodeUnary(cdata1, UnaryType.ROW_SUMS);
-					inHops2.put("X", hop.getInput().get(0));
-				}
-			}
-			else  if (((AggUnaryOp)hop).getDirection() == Direction.Col && ((AggUnaryOp)hop).getOp() == AggOp.SUM ) {
-				//vector div add without temporary copy
-				if(cdata1 instanceof CNodeBinary && ((CNodeBinary)cdata1).getType()==BinType.VECT_DIV_SCALAR)
-					out = new CNodeBinary(cdata1.getInput().get(0), cdata1.getInput().get(1), BinType.VECT_DIV_ADD);
-				else	
-					out = cdata1;
-			}
-		}
-		else if(hop instanceof AggBinaryOp)
-		{
-			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
-			CNode cdata2 = tmp.get(hop.getInput().get(1).getHopID());
-			
-			if( HopRewriteUtils.isTransposeOperation(hop.getInput().get(0)) )
-			{
-				//correct input under transpose
-				cdata1 = TemplateUtils.skipTranspose(cdata1, hop.getInput().get(0), tmp, compileLiterals);
-				inHops.remove(hop.getInput().get(0)); 
-				inHops.add(hop.getInput().get(0).getInput().get(0));
-				
-				out = new CNodeBinary(cdata2, cdata1, BinType.VECT_MULT_ADD);
-			}
-			else
-			{
-				if(hop.getInput().get(0).getDim2()==1 && hop.getInput().get(1).getDim2()==1)
-					out = new CNodeBinary((cdata1.getDataType()==DataType.SCALAR)? cdata1 : new CNodeUnary(cdata1, UnaryType.LOOKUP0),
-						(cdata2.getDataType()==DataType.SCALAR)? cdata2 : new CNodeUnary(cdata2, UnaryType.LOOKUP0), BinType.MULT);
-				else {
-					out = new CNodeBinary(cdata1, cdata2, BinType.DOT_PRODUCT);
-					inHops2.put("X", hop.getInput().get(0));
-				}
-			}
-		}
-		else if(hop instanceof BinaryOp)
-		{
-			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
-			CNode cdata2 = tmp.get(hop.getInput().get(1).getHopID());
-			
-			// if one input is a matrix then we need to do vector by scalar operations
-			if(hop.getInput().get(0).getDim1() > 1 && hop.getInput().get(0).getDim2() > 1 )
-			{
-				if (((BinaryOp)hop).getOp()== OpOp2.DIV)
-					out = new CNodeBinary(cdata1, cdata2, BinType.VECT_DIV_SCALAR);
-			}
-			else //one input is a vector/scalar other is a scalar
-			{
-				String primitiveOpName = ((BinaryOp)hop).getOp().toString();
-				if( (cdata1.getNumRows() > 1 && cdata1.getNumCols() == 1) || (cdata1.getNumRows() == 1 && cdata1.getNumCols() > 1) ) {
-					cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_R);
-				}
-				if( (cdata2.getNumRows() > 1 && cdata2.getNumCols() == 1) || (cdata2.getNumRows() == 1 && cdata2.getNumCols() > 1) ) {
-					cdata2 = new CNodeUnary(cdata2, UnaryType.LOOKUP_R);
-				}
-				out = new CNodeBinary(cdata1, cdata2, BinType.valueOf(primitiveOpName));	
-			}
-		}
-		else if( hop instanceof IndexingOp ) 
-		{
-			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
-			out = new CNodeTernary(cdata1, 
-					TemplateUtils.createCNodeData(new LiteralOp(hop.getInput().get(0).getDim2()), true), 
-					TemplateUtils.createCNodeData(hop.getInput().get(4), true),
-					TernaryType.LOOKUP_RC1);
-		}
-		
-		if( out.getDataType().isMatrix() ) {
-			out.setNumRows(hop.getDim1());
-			out.setNumCols(hop.getDim2());
-		}
-		
-		tmp.put(hop.getHopID(), out);
-	}
-	
-	/**
-	 * Comparator to order input hops of the row aggregate template. We try 
-	 * to order matrices-vectors-scalars via sorting by number of cells but 
-	 * we keep the given main input always at the first position.
-	 */
-	public static class HopInputComparator implements Comparator<Hop> 
-	{
-		private final Hop _X;
-		
-		public HopInputComparator(Hop X) {
-			_X = X;
-		}
-		
-		@Override
-		public int compare(Hop h1, Hop h2) {
-			long ncells1 = h1.getDataType()==DataType.SCALAR ? Long.MIN_VALUE : 
-				(h1==_X) ? Long.MAX_VALUE : 
-				h1.dimsKnown() ? h1.getDim1()*h1.getDim2() : Long.MAX_VALUE-1;
-			long ncells2 = h2.getDataType()==DataType.SCALAR ? Long.MIN_VALUE : 
-				(h2==_X) ? Long.MAX_VALUE : 
-				h2.dimsKnown() ? h2.getDim1()*h2.getDim2() : Long.MAX_VALUE-1;
-			return (ncells1 > ncells2) ? -1 : (ncells1 < ncells2) ? 1 : 0; 
-		}
-	}
-}

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b3120ce2/src/main/java/org/apache/sysml/hops/codegen/template/TemplateBase.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/TemplateBase.java b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateBase.java
new file mode 100644
index 0000000..1c5ea56
--- /dev/null
+++ b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateBase.java
@@ -0,0 +1,129 @@
+/*
+ * 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.hops.codegen.template;
+
+import org.apache.sysml.hops.Hop;
+import org.apache.sysml.hops.codegen.cplan.CNodeTpl;
+import org.apache.sysml.runtime.matrix.data.Pair;
+
+public abstract class TemplateBase 
+{	
+	public enum TemplateType {
+		RowAggTpl,
+		OuterProdTpl,
+		CellTpl;
+		
+		//rank in preferred order
+		public int getRank() {
+			return this.ordinal();
+		}
+	}
+	
+	public enum CloseType {
+		CLOSED_VALID,
+		CLOSED_INVALID,
+		OPEN,
+	}
+
+	protected TemplateType _type = null;
+	protected boolean _closed = false;
+	
+	protected TemplateBase(TemplateType type) {
+		_type = type;
+		_closed = false;
+	}
+	
+	public TemplateType getType() {
+		return _type;
+	}
+	
+	public boolean isClosed() {
+		return _closed;
+	}
+	
+	/////////////////////////////////////////////
+	// Open-Fuse-Merge-Close interface 
+	// (for candidate generation and exploration)
+	
+	/**
+	 * Indicates if this template can be opened at the given hop,
+	 * where hop represents bottom (first operation on the inputs) 
+	 * of the fused operator.
+	 * 
+	 * @param hop current hop
+	 * @return true if template can be opened 
+	 */
+	public abstract boolean open(Hop hop);
+	
+	/**
+	 * Indicates if the template can be expanded to the given hop
+	 * starting from an open template at the input.
+	 * 
+	 * @param hop current hop
+	 * @param input hop with open template of same type
+	 * @return true if the current hop can be fused into the operator.
+	 */
+	public abstract boolean fuse(Hop hop, Hop input);
+	
+	/**
+	 * Indicates if the template at the current hop can be expanded
+	 * by merging another template available for one of its other inputs
+	 * which is not yet covered by the template of the current hop. 
+	 * 
+	 * @param hop current hop
+	 * @param input direct input of current hop with available template
+	 * @return true if the the input hop can be fused into the current hop
+	 */
+	public abstract boolean merge(Hop hop, Hop input);
+	
+	/**
+	 * Indicates if the template must be closed at the current hop; either
+	 * due to final operations (e.g., aggregate) or unsupported operations.
+	 * 
+	 * @param hop current hop
+	 * @return close type (closed invalid, closed valid, open)
+	 */
+	public abstract CloseType close(Hop hop);
+	
+	/**
+	 * Mark the template as closed either invalid or valid.
+	 */
+	public void close() {
+		_closed = true;
+	}
+	
+	/////////////////////////////////////////////
+	// CPlan construction interface
+	// (for plan creation of selected candidates)
+	
+	/**
+	 * Constructs a single cplan rooted at the given hop, according 
+	 * to the plan given in the memo structure for this particular 
+	 * hop and its recursive inputs.  
+	 * 
+	 * @param hop root of cplan
+	 * @param memo memoization table for partial subplans
+	 * @param compileLiterals if true compile non-integer literals 
+	 * as constants, otherwise variables. note: integer literals are 
+	 * always compiled as constants.
+	 * @return
+	 */
+	public abstract Pair<Hop[], CNodeTpl> constructCplan(Hop hop, CPlanMemoTable memo, boolean compileLiterals);	
+}

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b3120ce2/src/main/java/org/apache/sysml/hops/codegen/template/TemplateCell.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/TemplateCell.java b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateCell.java
new file mode 100644
index 0000000..da74db2
--- /dev/null
+++ b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateCell.java
@@ -0,0 +1,304 @@
+/*
+ * 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.hops.codegen.template;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.stream.Collectors;
+
+import org.apache.sysml.hops.AggBinaryOp;
+import org.apache.sysml.hops.AggUnaryOp;
+import org.apache.sysml.hops.BinaryOp;
+import org.apache.sysml.hops.Hop;
+import org.apache.sysml.hops.UnaryOp;
+import org.apache.sysml.hops.Hop.AggOp;
+import org.apache.sysml.hops.Hop.Direction;
+import org.apache.sysml.hops.Hop.OpOp2;
+import org.apache.sysml.hops.IndexingOp;
+import org.apache.sysml.hops.LiteralOp;
+import org.apache.sysml.hops.TernaryOp;
+import org.apache.sysml.hops.codegen.cplan.CNode;
+import org.apache.sysml.hops.codegen.cplan.CNodeBinary;
+import org.apache.sysml.hops.codegen.cplan.CNodeBinary.BinType;
+import org.apache.sysml.hops.codegen.cplan.CNodeCell;
+import org.apache.sysml.hops.codegen.cplan.CNodeData;
+import org.apache.sysml.hops.codegen.cplan.CNodeTpl;
+import org.apache.sysml.hops.codegen.cplan.CNodeUnary;
+import org.apache.sysml.hops.codegen.cplan.CNodeUnary.UnaryType;
+import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntry;
+import org.apache.sysml.hops.codegen.cplan.CNodeTernary;
+import org.apache.sysml.hops.codegen.cplan.CNodeTernary.TernaryType;
+import org.apache.sysml.hops.rewrite.HopRewriteUtils;
+import org.apache.sysml.parser.Expression.DataType;
+import org.apache.sysml.runtime.matrix.data.Pair;
+
+public class TemplateCell extends TemplateBase 
+{	
+	public TemplateCell() {
+		super(TemplateType.CellTpl);
+	}
+
+	@Override
+	public boolean open(Hop hop) {
+		return isValidOperation(hop)
+			|| (hop instanceof IndexingOp && ((IndexingOp)hop).isColLowerEqualsUpper());
+	}
+
+	@Override
+	public boolean fuse(Hop hop, Hop input) {
+		return !isClosed() && (isValidOperation(hop) 
+			|| (HopRewriteUtils.isSum(hop) && ((AggUnaryOp) hop).getDirection()!= Direction.Col)
+			|| (HopRewriteUtils.isMatrixMultiply(hop) && hop.getDim1()==1 && hop.getDim2()==1)
+				&& HopRewriteUtils.isTransposeOperation(hop.getInput().get(0)));
+	}
+
+	@Override
+	public boolean merge(Hop hop, Hop input) {
+		//merge of other cell tpl possible
+		return (!isClosed() && isValidOperation(hop));
+	}
+
+	@Override
+	public CloseType close(Hop hop) {
+		//need to close cell tpl after aggregation, see fuse for exact properties
+		if( (HopRewriteUtils.isSum(hop) && ((AggUnaryOp) hop).getDirection()!= Direction.Col)
+			|| (HopRewriteUtils.isMatrixMultiply(hop) && hop.getDim1()==1 && hop.getDim2()==1) )
+			return CloseType.CLOSED_VALID;
+		else if( hop instanceof AggUnaryOp || hop instanceof AggBinaryOp )
+			return CloseType.CLOSED_INVALID;
+		else
+			return CloseType.OPEN;
+	}
+
+	@Override
+	public Pair<Hop[], CNodeTpl> constructCplan(Hop hop, CPlanMemoTable memo, boolean compileLiterals) 
+	{
+		//recursively process required cplan output
+		HashSet<Hop> inHops = new HashSet<Hop>();
+		HashMap<Long, CNode> tmp = new HashMap<Long, CNode>();
+		hop.resetVisitStatus();
+		rConstructCplan(hop, memo, tmp, inHops, compileLiterals);
+		hop.resetVisitStatus();
+		
+		//reorder inputs (ensure matrices/vectors come first) and prune literals
+		//note: we order by number of cells and subsequently sparsity to ensure
+		//that sparse inputs are used as the main input w/o unnecessary conversion
+		List<Hop> sinHops = inHops.stream()
+			.filter(h -> !(h.getDataType().isScalar() && tmp.get(h.getHopID()).isLiteral()))
+			.sorted(new HopInputComparator()).collect(Collectors.toList());
+		
+		//construct template node
+		ArrayList<CNode> inputs = new ArrayList<CNode>();
+		for( Hop in : sinHops )
+			inputs.add(tmp.get(in.getHopID()));
+		CNode output = tmp.get(hop.getHopID());
+		CNodeCell tpl = new CNodeCell(inputs, output);
+		tpl.setCellType(TemplateUtils.getCellType(hop));
+		tpl.setSparseSafe((HopRewriteUtils.isBinary(hop, OpOp2.MULT) && hop.getInput().contains(sinHops.get(0)))
+				|| (HopRewriteUtils.isBinary(hop, OpOp2.DIV) && hop.getInput().get(0) == sinHops.get(0)));
+		tpl.setRequiresCastDtm(hop instanceof AggBinaryOp);
+		
+		// return cplan instance
+		return new Pair<Hop[],CNodeTpl>(sinHops.toArray(new Hop[0]), tpl);
+	}
+	
+	private void rConstructCplan(Hop hop, CPlanMemoTable memo, HashMap<Long, CNode> tmp, HashSet<Hop> inHops, boolean compileLiterals) 
+	{
+		//recursively process required childs
+		MemoTableEntry me = memo.getBest(hop.getHopID(), TemplateType.CellTpl);
+		for( int i=0; i<hop.getInput().size(); i++ ) {
+			Hop c = hop.getInput().get(i);
+			if( me.isPlanRef(i) )
+				rConstructCplan(c, memo, tmp, inHops, compileLiterals);
+			else {
+				CNodeData cdata = TemplateUtils.createCNodeData(c, compileLiterals);	
+				tmp.put(c.getHopID(), cdata);
+				inHops.add(c);
+			}
+		}
+		
+		//construct cnode for current hop
+		CNode out = null;
+		if(hop instanceof UnaryOp)
+		{
+			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
+			if( TemplateUtils.isColVector(cdata1) )
+				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_R);
+			else if( cdata1 instanceof CNodeData && hop.getInput().get(0).getDataType().isMatrix() )
+				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_RC);
+			
+			String primitiveOpName = ((UnaryOp)hop).getOp().toString();
+			out = new CNodeUnary(cdata1, UnaryType.valueOf(primitiveOpName));
+		}
+		else if(hop instanceof BinaryOp)
+		{
+			BinaryOp bop = (BinaryOp) hop;
+			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
+			CNode cdata2 = tmp.get(hop.getInput().get(1).getHopID());
+			String primitiveOpName = bop.getOp().toString();
+			
+			//cdata1 is vector
+			if( TemplateUtils.isColVector(cdata1) )
+				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_R);
+			else if( cdata1 instanceof CNodeData && hop.getInput().get(0).getDataType().isMatrix() )
+				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_RC);
+			
+			//cdata2 is vector
+			if( TemplateUtils.isColVector(cdata2) )
+				cdata2 = new CNodeUnary(cdata2, UnaryType.LOOKUP_R);
+			else if( cdata2 instanceof CNodeData && hop.getInput().get(1).getDataType().isMatrix() )
+				cdata2 = new CNodeUnary(cdata2, UnaryType.LOOKUP_RC);
+			
+			if( bop.getOp()==OpOp2.POW && cdata2.isLiteral() && cdata2.getVarname().equals("2") )
+				out = new CNodeUnary(cdata1, UnaryType.POW2);
+			else if( bop.getOp()==OpOp2.MULT && cdata2.isLiteral() && cdata2.getVarname().equals("2") )
+				out = new CNodeUnary(cdata1, UnaryType.MULT2);
+			else //default binary	
+				out = new CNodeBinary(cdata1, cdata2, BinType.valueOf(primitiveOpName));
+		}
+		else if(hop instanceof TernaryOp) 
+		{
+			TernaryOp top = (TernaryOp) hop;
+			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
+			CNode cdata2 = tmp.get(hop.getInput().get(1).getHopID());
+			CNode cdata3 = tmp.get(hop.getInput().get(2).getHopID());
+			
+			//cdata1 is vector
+			if( TemplateUtils.isColVector(cdata1) )
+				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_R);
+			else if( cdata1 instanceof CNodeData && hop.getInput().get(0).getDataType().isMatrix() )
+				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_RC);
+			
+			//cdata3 is vector
+			if( TemplateUtils.isColVector(cdata3) )
+				cdata3 = new CNodeUnary(cdata3, UnaryType.LOOKUP_R);
+			else if( cdata3 instanceof CNodeData && hop.getInput().get(2).getDataType().isMatrix() )
+				cdata3 = new CNodeUnary(cdata3, UnaryType.LOOKUP_RC);
+			
+			//construct ternary cnode, primitive operation derived from OpOp3
+			out = new CNodeTernary(cdata1, cdata2, cdata3, 
+					TernaryType.valueOf(top.getOp().toString()));
+		}
+		else if( hop instanceof IndexingOp ) 
+		{
+			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
+			out = new CNodeTernary(cdata1, 
+					TemplateUtils.createCNodeData(new LiteralOp(hop.getInput().get(0).getDim2()), true), 
+					TemplateUtils.createCNodeData(hop.getInput().get(4), true),
+					TernaryType.LOOKUP_RC1);
+		}
+		else if( HopRewriteUtils.isTransposeOperation(hop) ) 
+		{
+			out = tmp.get(hop.getInput().get(0).getHopID());	
+		}
+		else if( hop instanceof AggUnaryOp && ((AggUnaryOp)hop).getOp() == AggOp.SUM
+			&& (((AggUnaryOp) hop).getDirection() == Direction.RowCol 
+			|| ((AggUnaryOp) hop).getDirection() == Direction.Row) )
+		{
+			out = tmp.get(hop.getInput().get(0).getHopID());
+		}
+		else if( hop instanceof AggBinaryOp ) {
+			//guaranteed to be a dot product, so there are two cases:
+			//(1) t(X)%*%X -> sum(X^2) and t(X) %*% Y -> sum(X*Y)
+			if( HopRewriteUtils.isTransposeOfItself(hop.getInput().get(0), hop.getInput().get(1)) ) {
+				CNode cdata1 = tmp.get(hop.getInput().get(1).getHopID());
+				out = new CNodeUnary(cdata1, UnaryType.POW2);
+			}
+			else {
+				CNode cdata1 = TemplateUtils.skipTranspose(tmp.get(hop.getInput().get(0).getHopID()), 
+						hop.getInput().get(0), tmp, compileLiterals);
+				if( TemplateUtils.isColVector(cdata1) )
+					cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_R);
+				CNode cdata2 = tmp.get(hop.getInput().get(1).getHopID());
+				if( TemplateUtils.isColVector(cdata2) )
+					cdata2 = new CNodeUnary(cdata2, UnaryType.LOOKUP_R);
+				out = new CNodeBinary(cdata1, cdata2, BinType.MULT);
+			}
+		} 
+		
+		tmp.put(hop.getHopID(), out);
+	}
+	
+	public static boolean isValidOperation(Hop hop) 
+	{	
+		//prepare indicators for binary operations
+		boolean isBinaryMatrixScalar = false;
+		boolean isBinaryMatrixVector = false;
+		boolean isBinaryMatrixMatrixDense = false;
+		if( hop instanceof BinaryOp && hop.getDataType().isMatrix() ) {
+			Hop left = hop.getInput().get(0);
+			Hop right = hop.getInput().get(1);
+			DataType ldt = left.getDataType();
+			DataType rdt = right.getDataType();
+			
+			isBinaryMatrixScalar = (ldt.isScalar() || rdt.isScalar());	
+			isBinaryMatrixVector = hop.dimsKnown() 
+				&& ((ldt.isMatrix() && TemplateUtils.isVectorOrScalar(right) && !TemplateUtils.isBinaryMatrixRowVector(hop)) 
+				|| (rdt.isMatrix() && TemplateUtils.isVectorOrScalar(left) && !TemplateUtils.isBinaryMatrixRowVector(hop)) );
+			isBinaryMatrixMatrixDense = hop.dimsKnown() && HopRewriteUtils.isEqualSize(left, right)
+				&& ldt.isMatrix() && rdt.isMatrix() && !HopRewriteUtils.isSparse(left) && !HopRewriteUtils.isSparse(right);
+		}
+				
+		//prepare indicators for ternary operations
+		boolean isTernaryVectorScalarVector = false;
+		boolean isTernaryMatrixScalarMatrixDense = false;
+		if( hop instanceof TernaryOp && hop.getInput().size()==3 && hop.dimsKnown() 
+			&& HopRewriteUtils.checkInputDataTypes(hop, DataType.MATRIX, DataType.SCALAR, DataType.MATRIX)) {
+			Hop left = hop.getInput().get(0);
+			Hop right = hop.getInput().get(2);
+			
+			isTernaryVectorScalarVector = TemplateUtils.isVector(left) && TemplateUtils.isVector(right);
+			isTernaryMatrixScalarMatrixDense = HopRewriteUtils.isEqualSize(left, right) 
+				&& !HopRewriteUtils.isSparse(left) && !HopRewriteUtils.isSparse(right);
+		}
+		
+		//check supported unary, binary, ternary operations
+		return hop.getDataType() == DataType.MATRIX && TemplateUtils.isOperationSupported(hop) && (hop instanceof UnaryOp 
+				|| isBinaryMatrixScalar || isBinaryMatrixVector || isBinaryMatrixMatrixDense 
+				|| isTernaryVectorScalarVector || isTernaryMatrixScalarMatrixDense);	
+	}
+	
+	/**
+	 * Comparator to order input hops of the cell template. We try to order 
+	 * matrices-vectors-scalars via sorting by number of cells and for 
+	 * equal number of cells by sparsity to prefer sparse inputs as the main 
+	 * input for sparsity exploitation.
+	 */
+	public static class HopInputComparator implements Comparator<Hop> 
+	{
+		@Override
+		public int compare(Hop h1, Hop h2) {
+			long ncells1 = h1.getDataType()==DataType.SCALAR ? Long.MIN_VALUE : 
+				h1.dimsKnown() ? h1.getDim1()*h1.getDim2() : Long.MAX_VALUE;
+			long ncells2 = h2.getDataType()==DataType.SCALAR ? Long.MIN_VALUE :
+				h2.dimsKnown() ? h2.getDim1()*h2.getDim2() : Long.MAX_VALUE;
+			if( ncells1 > ncells2 ) 
+				return -1;
+			else if( ncells1 < ncells2) 
+				return 1;
+			return Long.compare(
+				h1.dimsKnown(true) ? h1.getNnz() : ncells1, 
+				h2.dimsKnown(true) ? h2.getNnz() : ncells2);
+		}
+	}
+}

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b3120ce2/src/main/java/org/apache/sysml/hops/codegen/template/TemplateOuterProduct.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/template/TemplateOuterProduct.java b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateOuterProduct.java
new file mode 100644
index 0000000..68aaa2a
--- /dev/null
+++ b/src/main/java/org/apache/sysml/hops/codegen/template/TemplateOuterProduct.java
@@ -0,0 +1,213 @@
+/*
+ * 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.hops.codegen.template;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+
+import org.apache.sysml.hops.AggBinaryOp;
+import org.apache.sysml.hops.AggUnaryOp;
+import org.apache.sysml.hops.BinaryOp;
+import org.apache.sysml.hops.DataOp;
+import org.apache.sysml.hops.Hop;
+import org.apache.sysml.hops.UnaryOp;
+import org.apache.sysml.hops.Hop.AggOp;
+import org.apache.sysml.hops.Hop.Direction;
+import org.apache.sysml.hops.Hop.OpOp2;
+import org.apache.sysml.hops.codegen.cplan.CNode;
+import org.apache.sysml.hops.codegen.cplan.CNodeBinary;
+import org.apache.sysml.hops.codegen.cplan.CNodeBinary.BinType;
+import org.apache.sysml.hops.codegen.cplan.CNodeUnary;
+import org.apache.sysml.hops.codegen.cplan.CNodeUnary.UnaryType;
+import org.apache.sysml.hops.codegen.template.CPlanMemoTable.MemoTableEntry;
+import org.apache.sysml.hops.codegen.cplan.CNodeData;
+import org.apache.sysml.hops.codegen.cplan.CNodeOuterProduct;
+import org.apache.sysml.hops.codegen.cplan.CNodeTpl;
+import org.apache.sysml.hops.rewrite.HopRewriteUtils;
+import org.apache.sysml.runtime.codegen.SpoofOuterProduct.OutProdType;
+import org.apache.sysml.runtime.matrix.data.Pair;
+
+public class TemplateOuterProduct extends TemplateBase {
+	
+	public TemplateOuterProduct() {
+		super(TemplateType.OuterProdTpl);
+	}
+
+	@Override
+	public boolean open(Hop hop) {
+		//open on outer product like matrix mult (output larger than common dim)
+		return HopRewriteUtils.isOuterProductLikeMM(hop)
+			&& hop.getDim1()>256 && hop.getDim2() > 256;
+	}
+
+	@Override
+	public boolean fuse(Hop hop, Hop input) {
+		return !isClosed() 
+			&&((hop instanceof UnaryOp && TemplateUtils.isOperationSupported(hop))  
+			|| (hop instanceof BinaryOp && TemplateUtils.isOperationSupported(hop)
+				&& (TemplateUtils.isBinaryMatrixColVector(hop) || HopRewriteUtils.isBinaryMatrixScalarOperation(hop)
+				|| (HopRewriteUtils.isBinaryMatrixMatrixOperation(hop) && HopRewriteUtils.isBinary(hop, OpOp2.MULT, OpOp2.DIV)) )) 
+			|| HopRewriteUtils.isTransposeOperation(hop) 
+			|| (hop instanceof AggBinaryOp && !HopRewriteUtils.isOuterProductLikeMM(hop))
+			|| (hop instanceof AggUnaryOp && ((AggUnaryOp)hop).getDirection()==Direction.RowCol));
+	}
+
+	@Override
+	public boolean merge(Hop hop, Hop input) {
+		return !isClosed() && 
+			(TemplateUtils.isBinaryMatrixRowVector(hop)
+			|| HopRewriteUtils.isBinaryMatrixScalarOperation(hop));
+	}
+
+	@Override
+	public CloseType close(Hop hop) {
+		// close on second matrix multiply (after open) or unary aggregate
+		if( hop instanceof AggUnaryOp && HopRewriteUtils.isOuterProductLikeMM(hop.getInput().get(0)) )
+			return CloseType.CLOSED_INVALID;
+		else if( (hop instanceof AggUnaryOp) 
+			|| (hop instanceof AggBinaryOp && !HopRewriteUtils.isOuterProductLikeMM(hop) 
+					&& !HopRewriteUtils.isTransposeOperation(hop.getParent().get(0)))
+			|| (HopRewriteUtils.isTransposeOperation(hop) && hop.getInput().get(0) instanceof AggBinaryOp
+					&& !HopRewriteUtils.isOuterProductLikeMM(hop.getInput().get(0)) ))
+			return CloseType.CLOSED_VALID;
+		else
+			return CloseType.OPEN;
+	}
+
+	public Pair<Hop[], CNodeTpl> constructCplan(Hop hop, CPlanMemoTable memo, boolean compileLiterals) 
+	{
+		//recursively process required cplan output
+		HashSet<Hop> inHops = new HashSet<Hop>();
+		HashMap<String,Hop> inHops2 = new HashMap<String, Hop>();
+		HashMap<Long, CNode> tmp = new HashMap<Long, CNode>();
+		hop.resetVisitStatus();
+		rConstructCplan(hop, memo, tmp, inHops, inHops2, compileLiterals);
+		hop.resetVisitStatus();
+		
+		//reorder inputs (ensure matrix is first input)
+		Hop X = inHops2.get("_X");
+		Hop U = inHops2.get("_U");
+		Hop V = inHops2.get("_V");
+		LinkedList<Hop> sinHops = new LinkedList<Hop>(inHops);
+		sinHops.remove(V); sinHops.addFirst(V);
+		sinHops.remove(U); sinHops.addFirst(U);
+		sinHops.remove(X); sinHops.addFirst(X);
+		
+		//construct template node
+		ArrayList<CNode> inputs = new ArrayList<CNode>();
+		for( Hop in : sinHops )
+			if( in != null )
+				inputs.add(tmp.get(in.getHopID()));
+
+		CNode output = tmp.get(hop.getHopID());
+		CNodeOuterProduct tpl = new CNodeOuterProduct(inputs, output);
+		tpl.setOutProdType(TemplateUtils.getOuterProductType(X, U, V, hop));
+		tpl.setTransposeOutput(!HopRewriteUtils.isTransposeOperation(hop)
+			&& tpl.getOutProdType()==OutProdType.LEFT_OUTER_PRODUCT); 
+		
+		return new Pair<Hop[],CNodeTpl>(sinHops.toArray(new Hop[0]), tpl);
+	}
+	
+	private void rConstructCplan(Hop hop, CPlanMemoTable memo, HashMap<Long, CNode> tmp, HashSet<Hop> inHops, HashMap<String, Hop> inHops2, boolean compileLiterals) 
+	{
+		//recursively process required childs
+		MemoTableEntry me = memo.getBest(hop.getHopID(), TemplateType.OuterProdTpl);
+		for( int i=0; i<hop.getInput().size(); i++ ) {
+			Hop c = hop.getInput().get(i);
+			if( me.isPlanRef(i) )
+				rConstructCplan(c, memo, tmp, inHops, inHops2, compileLiterals);
+			else {
+				CNodeData cdata = TemplateUtils.createCNodeData(c, compileLiterals);	
+				tmp.put(c.getHopID(), cdata);
+				inHops.add(c);
+			}
+		}
+		
+		//construct cnode for current hop
+		CNode out = null;
+		if(hop instanceof UnaryOp)
+		{
+			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
+			String primitiveOpName = ((UnaryOp)hop).getOp().toString();
+			out = new CNodeUnary(cdata1, UnaryType.valueOf(primitiveOpName));
+		}
+		else if(hop instanceof BinaryOp)
+		{
+			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
+			CNode cdata2 = tmp.get(hop.getInput().get(1).getHopID());
+			String primitiveOpName = ((BinaryOp)hop).getOp().toString();
+			
+			if( (cdata1.getNumRows() > 1 && cdata1.getNumCols() == 1) || (cdata1.getNumRows() == 1 && cdata1.getNumCols() > 1) ) {
+				cdata1 = new CNodeUnary(cdata1, UnaryType.LOOKUP_R);
+			}
+			if( (cdata2.getNumRows() > 1 && cdata2.getNumCols() == 1) || (cdata2.getNumRows() == 1 && cdata2.getNumCols() > 1) ) {
+				cdata2 = new CNodeUnary(cdata2, UnaryType.LOOKUP_R);
+			}
+			
+			if( HopRewriteUtils.isEqualSize(hop.getInput().get(0), hop.getInput().get(1))
+				&& hop.getInput().get(0) instanceof DataOp )
+				inHops2.put("_X", hop.getInput().get(0));
+			
+			out = new CNodeBinary(cdata1, cdata2, BinType.valueOf(primitiveOpName));
+		}
+		else if(hop instanceof AggBinaryOp)
+		{
+			CNode cdata1 = tmp.get(hop.getInput().get(0).getHopID());
+			CNode cdata2 = tmp.get(hop.getInput().get(1).getHopID());
+			
+			//handle tanspose in outer or final product
+			cdata1 = TemplateUtils.skipTranspose(cdata1, hop.getInput().get(0), tmp, compileLiterals);
+			cdata2 = TemplateUtils.skipTranspose(cdata2, hop.getInput().get(1), tmp, compileLiterals);
+			
+			//outerproduct U%*%t(V), see open
+			if( HopRewriteUtils.isOuterProductLikeMM(hop) )
+			{
+				//keep U and V for later reference
+				inHops2.put("_U", hop.getInput().get(0));
+				if( HopRewriteUtils.isTransposeOperation(hop.getInput().get(1)) )
+					inHops2.put("_V", hop.getInput().get(1).getInput().get(0));
+				else
+					inHops2.put("_V", hop.getInput().get(1));
+				
+				out = new CNodeBinary(cdata1, cdata2, BinType.DOT_PRODUCT);
+			}
+			//final left/right matrix mult, see close
+			else {
+				if( cdata1.getDataType().isScalar() )
+					out = new CNodeBinary(cdata1, cdata2, BinType.VECT_MULT_ADD);	
+				else
+					out = new CNodeBinary(cdata2, cdata1, BinType.VECT_MULT_ADD);	
+			}
+		}
+		else if( HopRewriteUtils.isTransposeOperation(hop) ) 
+		{
+			out = tmp.get(hop.getInput().get(0).getHopID());	
+		}
+		else if( hop instanceof AggUnaryOp && ((AggUnaryOp)hop).getOp() == AggOp.SUM
+			&& ((AggUnaryOp)hop).getDirection() == Direction.RowCol )
+		{
+			out = tmp.get(hop.getInput().get(0).getHopID());
+		}
+		
+		tmp.put(hop.getHopID(), out);
+	}
+}