src/main/java/org/apache/sysds/runtime/util/AutoDiff.java - systemds - Git at Google

 /*
  * 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.sysds.runtime.util;

 import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Stack;

 import org.apache.commons.lang3.mutable.MutableInt;
 import org.apache.sysds.common.Types;
 import org.apache.sysds.hops.DataGenOp;
 import org.apache.sysds.hops.DataOp;
 import org.apache.sysds.hops.Hop;
 import org.apache.sysds.hops.LiteralOp;
 import org.apache.sysds.hops.ReorgOp;
 import org.apache.sysds.hops.recompile.Recompiler;
 import org.apache.sysds.hops.rewrite.HopRewriteUtils;
 import org.apache.sysds.parser.DataExpression;
 import org.apache.sysds.parser.DataIdentifier;
 import org.apache.sysds.runtime.DMLRuntimeException;
 import org.apache.sysds.runtime.controlprogram.BasicProgramBlock;
 import org.apache.sysds.runtime.controlprogram.Program;
 import org.apache.sysds.runtime.controlprogram.caching.MatrixObject;
 import org.apache.sysds.runtime.controlprogram.context.ExecutionContext;
 import org.apache.sysds.runtime.instructions.Instruction;
 import org.apache.sysds.runtime.instructions.InstructionParser;
 import org.apache.sysds.runtime.instructions.InstructionUtils;
 import org.apache.sysds.runtime.instructions.cp.CPInstruction;
 import org.apache.sysds.runtime.instructions.cp.CPOperand;
 import org.apache.sysds.runtime.instructions.cp.Data;
 import org.apache.sysds.runtime.instructions.cp.DataGenCPInstruction;
 import org.apache.sysds.runtime.instructions.cp.ListObject;
 import org.apache.sysds.runtime.instructions.cp.ScalarObjectFactory;
 import org.apache.sysds.runtime.instructions.cp.VariableCPInstruction;
 import org.apache.sysds.runtime.instructions.spark.RandSPInstruction;
 import org.apache.sysds.runtime.lineage.LineageItem;
 import org.apache.sysds.runtime.lineage.LineageParser;
 import org.apache.sysds.utils.Explain;

 public class AutoDiff {
 	private static final String ADVARPREFIX = "adVar";
 	private static final boolean DEBUG = false;

 	public static ListObject getBackward(MatrixObject mo, ArrayList<Data> lineage, ExecutionContext adec) {

 		ArrayList<String> names = new ArrayList<>();
 		// parse the lineage and take the number of instructions as for each instruction there is separate hop DAG
 		String lin = lineage.get(0).toString();
 		// get rid of foo flag
 		lin = lin.replace("foo", "");
 		List<Data>  data = parseNComputeAutoDiffFromLineage(mo, lin, names, adec);
 		return new ListObject(data, names);
 	}

 	public static List<Data> parseNComputeAutoDiffFromLineage(MatrixObject mo, String mainTrace,
 		ArrayList<String> names, ExecutionContext ec ) {

 		LineageItem root = LineageParser.parseLineageTrace(mainTrace);
 		if (DEBUG) {
 			System.out.println("Lineage trace of the forward pass");
 			System.out.println(mainTrace);
 		}
 		// Recursively construct hops
 		root.resetVisitStatusNR();
 		Map<Long, Hop> operands = new HashMap<>();
 		// set variable for input matrix
 		ec.setVariable("X", mo);
 		DataOp input = HopRewriteUtils.createTransientRead("X", mo);
 		// each instruction Hop is stored separately as each instruction creates a new differentiation
 		ArrayList<Hop> allHops = constructHopsNR(root, operands, input, names);

 		ArrayList<Data> results = new ArrayList<>();
 		for(int i=0; i< allHops.size(); i++) {
 			DataOp dop = HopRewriteUtils.createTransientWrite("advar"+i, allHops.get(i));
 			ArrayList<Instruction> dInst = Recompiler
 				.recompileHopsDag(dop, ec.getVariables(), null, true, true, 0);
 			if (DEBUG) {
 				System.out.println("HOP Dag and instructions for " + names.get(i));
 				System.out.println(Explain.explain(dop));
 				System.out.println(Explain.explain(dInst));
 			}
 			// create derivative instructions
 			executeInst(dInst, ec);
 			results.add(ec.getVariable("advar"+i));
 		}
 		return results;
 	}

 	public static ArrayList<Hop> constructHopsNR(LineageItem item, Map<Long, Hop> operands,	Hop mo, ArrayList<String> names)
 	{
 		// Hop dags for the derivatives share common sub-dags with
 		// the lineage dag of the forward pass. This method starts
 		// constructing the hop dag from the lineage dag, but adds
 		// extra hops to the resulting dags as needed.
 		ArrayList<Hop>  allHops = new ArrayList<>();
 		Stack<LineageItem> stackItem = new Stack<>();
 		Stack<MutableInt> stackPos = new Stack<>();
 		stackItem.push(item); stackPos.push(new MutableInt(0));
 		while (!stackItem.empty()) {
 			LineageItem tmpItem = stackItem.peek();
 			MutableInt tmpPos = stackPos.peek();
 			// check ascent condition - no item processing
 			if (tmpItem.isVisited()) {
 				stackItem.pop(); stackPos.pop();
 			}
 			// check ascent condition - append item
 			else if( tmpItem.getInputs() == null
 				|| tmpItem.getInputs().length <= tmpPos.intValue() ) {
 				constructSingleHop(tmpItem, operands, mo, allHops, names);
 				stackItem.pop(); stackPos.pop();
 				tmpItem.setVisited();
 			}
 			// check descent condition
 			else if( tmpItem.getInputs() != null ) {
 				stackItem.push(tmpItem.getInputs()[tmpPos.intValue()]);
 				tmpPos.increment();
 				stackPos.push(new MutableInt(0));
 			}
 		}
 		return allHops;
 	}

 	private static void constructSingleHop(LineageItem item, Map<Long, Hop> operands, Hop mo,
 		ArrayList<Hop> allHops, ArrayList<String> names)
 	{
 		//process current lineage item
 		switch (item.getType()) {
 			case Creation: {
 				if(item.getData().startsWith(ADVARPREFIX)) {
 					long phId = Long.parseLong(item.getData().substring(3));
 					Hop input = operands.get(phId);
 					operands.remove(phId);
 					// Replace the placeholders with TReads
 					operands.put(item.getId(), input); // order preserving
 					break;
 				}
 				Instruction inst = InstructionParser.parseSingleInstruction(item.getData());

 				if(inst instanceof DataGenCPInstruction) {
 					DataGenCPInstruction rand = (DataGenCPInstruction) inst;
 					HashMap<String, Hop> params = new HashMap<>();
 					if(rand.getOpcode().equals("rand")) {
 						if(rand.output.getDataType() == Types.DataType.TENSOR)
 							params.put(DataExpression.RAND_DIMS, new LiteralOp(rand.getDims()));
 						else {
 							params.put(DataExpression.RAND_ROWS, new LiteralOp(rand.getRows()));
 							params.put(DataExpression.RAND_COLS, new LiteralOp(rand.getCols()));
 						}
 						params.put(DataExpression.RAND_MIN, new LiteralOp(rand.getMinValue()));
 						params.put(DataExpression.RAND_MAX, new LiteralOp(rand.getMaxValue()));
 						params.put(DataExpression.RAND_PDF, new LiteralOp(rand.getPdf()));
 						params.put(DataExpression.RAND_LAMBDA, new LiteralOp(rand.getPdfParams()));
 						params.put(DataExpression.RAND_SPARSITY, new LiteralOp(rand.getSparsity()));
 						params.put(DataExpression.RAND_SEED, new LiteralOp(rand.getSeed()));
 					}
 					Hop datagen = new DataGenOp(Types.OpOpDG.valueOf(rand.getOpcode().toUpperCase()),
 						new DataIdentifier("tmp"), params);
 					datagen.setBlocksize(rand.getBlocksize());
 					operands.put(item.getId(), datagen);
 				}
 				else if(inst instanceof VariableCPInstruction && ((VariableCPInstruction) inst).isCreateVariable()) {
 					String parts[] = InstructionUtils.getInstructionPartsWithValueType(inst.toString());
 					Types.DataType dt = Types.DataType.valueOf(parts[4]);
 					Types.ValueType vt = dt == Types.DataType.MATRIX ? Types.ValueType.FP64 : Types.ValueType.STRING;
 					HashMap<String, Hop> params = new HashMap<>();
 					params.put(DataExpression.IO_FILENAME, new LiteralOp(parts[2]));
 					params.put(DataExpression.READROWPARAM, new LiteralOp(Long.parseLong(parts[6])));
 					params.put(DataExpression.READCOLPARAM, new LiteralOp(Long.parseLong(parts[7])));
 					params.put(DataExpression.READNNZPARAM, new LiteralOp(Long.parseLong(parts[8])));
 					params.put(DataExpression.FORMAT_TYPE, new LiteralOp(parts[5]));
 					DataOp pread = new DataOp(parts[1].substring(5), dt, vt, Types.OpOpData.PERSISTENTREAD, params);
 					pread.setFileName(parts[2]);
 					operands.put(item.getId(), pread);
 				}
 				else if(inst instanceof RandSPInstruction) {
 					RandSPInstruction rand = (RandSPInstruction) inst;
 					HashMap<String, Hop> params = new HashMap<>();
 					if(rand.output.getDataType() == Types.DataType.TENSOR)
 						params.put(DataExpression.RAND_DIMS, new LiteralOp(rand.getDims()));
 					else {
 						params.put(DataExpression.RAND_ROWS, new LiteralOp(rand.getRows()));
 						params.put(DataExpression.RAND_COLS, new LiteralOp(rand.getCols()));
 					}
 					params.put(DataExpression.RAND_MIN, new LiteralOp(rand.getMinValue()));
 					params.put(DataExpression.RAND_MAX, new LiteralOp(rand.getMaxValue()));
 					params.put(DataExpression.RAND_PDF, new LiteralOp(rand.getPdf()));
 					params.put(DataExpression.RAND_LAMBDA, new LiteralOp(rand.getPdfParams()));
 					params.put(DataExpression.RAND_SPARSITY, new LiteralOp(rand.getSparsity()));
 					params.put(DataExpression.RAND_SEED, new LiteralOp(rand.getSeed()));
 					Hop datagen = new DataGenOp(Types.OpOpDG.RAND, new DataIdentifier("tmp"), params);
 					datagen.setBlocksize(rand.getBlocksize());
 					operands.put(item.getId(), datagen);
 				}
 				break;
 			}
 			case Instruction: {
 				CPInstruction.CPType ctype = InstructionUtils.getCPTypeByOpcode(item.getOpcode());

 				if(ctype != null) {
 					switch(ctype) {
 						case AggregateBinary: {
 							Hop input1 = operands.get(item.getInputs()[0].getId());
 							Hop input2 = operands.get(item.getInputs()[1].getId());
 							//Build the hops for the derivatives
 							ReorgOp trasnX = HopRewriteUtils.createTranspose(input1);
 							ReorgOp trasnW = HopRewriteUtils.createTranspose(input2);
 							Hop dX = HopRewriteUtils.createMatrixMultiply(mo, trasnW);
 							Hop dW = HopRewriteUtils.createMatrixMultiply(trasnX, mo);
 							operands.put(item.getId(), dX);
 							operands.put(item.getId() + 1, dW);
 							allHops.add(dX);
 							allHops.add(dW);
 							names.add("dX");
 							names.add("dW");
 							break;
 						}
 						case Binary: {
 							//handle special cases of binary operations
 							String opcode = item.getOpcode();
 							Hop output = null;
 							if(opcode.equals("+"))
 								output = HopRewriteUtils.createAggUnaryOp(mo, Types.AggOp.SUM, Types.Direction.Col);
 							operands.put(item.getId(), output);
 							allHops.add(output);
 							names.add("dB");
 							break;
 						}
 						default:
 							throw new DMLRuntimeException(
 								"Unsupported autoDiff instruction " + "type: " + ctype.name() + " (" + item.getOpcode() + ").");
 					}
 				}
 				break;
 			}
 			case Literal: {
 				CPOperand op = new CPOperand(item.getData());
 				operands.put(item.getId(), ScalarObjectFactory
 					.createLiteralOp(op.getValueType(), op.getName()));
 				break;
 			}
 			default:
 				throw new DMLRuntimeException("Lineage type " + item.getType() + " is not supported");
 		}
 	}
 	private static void executeInst(ArrayList<Instruction> newInst, ExecutionContext lrwec)
 	{
 		try {
 			//execute instructions
 			BasicProgramBlock pb = new BasicProgramBlock(new Program());
 			pb.setInstructions(newInst);
 			pb.execute(lrwec);
 		}
 		catch (Exception e) {
 			throw new DMLRuntimeException("Error executing autoDiff instruction" , e);
 		}
 	}
 }
	/*
	* 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.sysds.runtime.util;

	import java.util.ArrayList;
	import java.util.HashMap;
	import java.util.List;
	import java.util.Map;
	import java.util.Stack;

	import org.apache.commons.lang3.mutable.MutableInt;
	import org.apache.sysds.common.Types;
	import org.apache.sysds.hops.DataGenOp;
	import org.apache.sysds.hops.DataOp;
	import org.apache.sysds.hops.Hop;
	import org.apache.sysds.hops.LiteralOp;
	import org.apache.sysds.hops.ReorgOp;
	import org.apache.sysds.hops.recompile.Recompiler;
	import org.apache.sysds.hops.rewrite.HopRewriteUtils;
	import org.apache.sysds.parser.DataExpression;
	import org.apache.sysds.parser.DataIdentifier;
	import org.apache.sysds.runtime.DMLRuntimeException;
	import org.apache.sysds.runtime.controlprogram.BasicProgramBlock;
	import org.apache.sysds.runtime.controlprogram.Program;
	import org.apache.sysds.runtime.controlprogram.caching.MatrixObject;
	import org.apache.sysds.runtime.controlprogram.context.ExecutionContext;
	import org.apache.sysds.runtime.instructions.Instruction;
	import org.apache.sysds.runtime.instructions.InstructionParser;
	import org.apache.sysds.runtime.instructions.InstructionUtils;
	import org.apache.sysds.runtime.instructions.cp.CPInstruction;
	import org.apache.sysds.runtime.instructions.cp.CPOperand;
	import org.apache.sysds.runtime.instructions.cp.Data;
	import org.apache.sysds.runtime.instructions.cp.DataGenCPInstruction;
	import org.apache.sysds.runtime.instructions.cp.ListObject;
	import org.apache.sysds.runtime.instructions.cp.ScalarObjectFactory;
	import org.apache.sysds.runtime.instructions.cp.VariableCPInstruction;
	import org.apache.sysds.runtime.instructions.spark.RandSPInstruction;
	import org.apache.sysds.runtime.lineage.LineageItem;
	import org.apache.sysds.runtime.lineage.LineageParser;
	import org.apache.sysds.utils.Explain;

	public class AutoDiff {
	private static final String ADVARPREFIX = "adVar";
	private static final boolean DEBUG = false;

	public static ListObject getBackward(MatrixObject mo, ArrayList<Data> lineage, ExecutionContext adec) {

	ArrayList<String> names = new ArrayList<>();
	// parse the lineage and take the number of instructions as for each instruction there is separate hop DAG
	String lin = lineage.get(0).toString();
	// get rid of foo flag
	lin = lin.replace("foo", "");
	List<Data> data = parseNComputeAutoDiffFromLineage(mo, lin, names, adec);
	return new ListObject(data, names);
	}

	public static List<Data> parseNComputeAutoDiffFromLineage(MatrixObject mo, String mainTrace,
	ArrayList<String> names, ExecutionContext ec ) {

	LineageItem root = LineageParser.parseLineageTrace(mainTrace);
	if (DEBUG) {
	System.out.println("Lineage trace of the forward pass");
	System.out.println(mainTrace);
	}
	// Recursively construct hops
	root.resetVisitStatusNR();
	Map<Long, Hop> operands = new HashMap<>();
	// set variable for input matrix
	ec.setVariable("X", mo);
	DataOp input = HopRewriteUtils.createTransientRead("X", mo);
	// each instruction Hop is stored separately as each instruction creates a new differentiation
	ArrayList<Hop> allHops = constructHopsNR(root, operands, input, names);

	ArrayList<Data> results = new ArrayList<>();
	for(int i=0; i< allHops.size(); i++) {
	DataOp dop = HopRewriteUtils.createTransientWrite("advar"+i, allHops.get(i));
	ArrayList<Instruction> dInst = Recompiler
	.recompileHopsDag(dop, ec.getVariables(), null, true, true, 0);
	if (DEBUG) {
	System.out.println("HOP Dag and instructions for " + names.get(i));
	System.out.println(Explain.explain(dop));
	System.out.println(Explain.explain(dInst));
	}
	// create derivative instructions
	executeInst(dInst, ec);
	results.add(ec.getVariable("advar"+i));
	}
	return results;
	}

	public static ArrayList<Hop> constructHopsNR(LineageItem item, Map<Long, Hop> operands, Hop mo, ArrayList<String> names)
	{
	// Hop dags for the derivatives share common sub-dags with
	// the lineage dag of the forward pass. This method starts
	// constructing the hop dag from the lineage dag, but adds
	// extra hops to the resulting dags as needed.
	ArrayList<Hop> allHops = new ArrayList<>();
	Stack<LineageItem> stackItem = new Stack<>();
	Stack<MutableInt> stackPos = new Stack<>();
	stackItem.push(item); stackPos.push(new MutableInt(0));
	while (!stackItem.empty()) {
	LineageItem tmpItem = stackItem.peek();
	MutableInt tmpPos = stackPos.peek();
	// check ascent condition - no item processing
	if (tmpItem.isVisited()) {
	stackItem.pop(); stackPos.pop();
	}
	// check ascent condition - append item
	else if( tmpItem.getInputs() == null
	\|\| tmpItem.getInputs().length <= tmpPos.intValue() ) {
	constructSingleHop(tmpItem, operands, mo, allHops, names);
	stackItem.pop(); stackPos.pop();
	tmpItem.setVisited();
	}
	// check descent condition
	else if( tmpItem.getInputs() != null ) {
	stackItem.push(tmpItem.getInputs()[tmpPos.intValue()]);
	tmpPos.increment();
	stackPos.push(new MutableInt(0));
	}
	}
	return allHops;
	}

	private static void constructSingleHop(LineageItem item, Map<Long, Hop> operands, Hop mo,
	ArrayList<Hop> allHops, ArrayList<String> names)
	{
	//process current lineage item
	switch (item.getType()) {
	case Creation: {
	if(item.getData().startsWith(ADVARPREFIX)) {
	long phId = Long.parseLong(item.getData().substring(3));
	Hop input = operands.get(phId);
	operands.remove(phId);
	// Replace the placeholders with TReads
	operands.put(item.getId(), input); // order preserving
	break;
	}
	Instruction inst = InstructionParser.parseSingleInstruction(item.getData());

	if(inst instanceof DataGenCPInstruction) {
	DataGenCPInstruction rand = (DataGenCPInstruction) inst;
	HashMap<String, Hop> params = new HashMap<>();
	if(rand.getOpcode().equals("rand")) {
	if(rand.output.getDataType() == Types.DataType.TENSOR)
	params.put(DataExpression.RAND_DIMS, new LiteralOp(rand.getDims()));
	else {
	params.put(DataExpression.RAND_ROWS, new LiteralOp(rand.getRows()));
	params.put(DataExpression.RAND_COLS, new LiteralOp(rand.getCols()));
	}
	params.put(DataExpression.RAND_MIN, new LiteralOp(rand.getMinValue()));
	params.put(DataExpression.RAND_MAX, new LiteralOp(rand.getMaxValue()));
	params.put(DataExpression.RAND_PDF, new LiteralOp(rand.getPdf()));
	params.put(DataExpression.RAND_LAMBDA, new LiteralOp(rand.getPdfParams()));
	params.put(DataExpression.RAND_SPARSITY, new LiteralOp(rand.getSparsity()));
	params.put(DataExpression.RAND_SEED, new LiteralOp(rand.getSeed()));
	}
	Hop datagen = new DataGenOp(Types.OpOpDG.valueOf(rand.getOpcode().toUpperCase()),
	new DataIdentifier("tmp"), params);
	datagen.setBlocksize(rand.getBlocksize());
	operands.put(item.getId(), datagen);
	}
	else if(inst instanceof VariableCPInstruction && ((VariableCPInstruction) inst).isCreateVariable()) {
	String parts[] = InstructionUtils.getInstructionPartsWithValueType(inst.toString());
	Types.DataType dt = Types.DataType.valueOf(parts[4]);
	Types.ValueType vt = dt == Types.DataType.MATRIX ? Types.ValueType.FP64 : Types.ValueType.STRING;
	HashMap<String, Hop> params = new HashMap<>();
	params.put(DataExpression.IO_FILENAME, new LiteralOp(parts[2]));
	params.put(DataExpression.READROWPARAM, new LiteralOp(Long.parseLong(parts[6])));
	params.put(DataExpression.READCOLPARAM, new LiteralOp(Long.parseLong(parts[7])));
	params.put(DataExpression.READNNZPARAM, new LiteralOp(Long.parseLong(parts[8])));
	params.put(DataExpression.FORMAT_TYPE, new LiteralOp(parts[5]));
	DataOp pread = new DataOp(parts[1].substring(5), dt, vt, Types.OpOpData.PERSISTENTREAD, params);
	pread.setFileName(parts[2]);
	operands.put(item.getId(), pread);
	}
	else if(inst instanceof RandSPInstruction) {
	RandSPInstruction rand = (RandSPInstruction) inst;
	HashMap<String, Hop> params = new HashMap<>();
	if(rand.output.getDataType() == Types.DataType.TENSOR)
	params.put(DataExpression.RAND_DIMS, new LiteralOp(rand.getDims()));
	else {
	params.put(DataExpression.RAND_ROWS, new LiteralOp(rand.getRows()));
	params.put(DataExpression.RAND_COLS, new LiteralOp(rand.getCols()));
	}
	params.put(DataExpression.RAND_MIN, new LiteralOp(rand.getMinValue()));
	params.put(DataExpression.RAND_MAX, new LiteralOp(rand.getMaxValue()));
	params.put(DataExpression.RAND_PDF, new LiteralOp(rand.getPdf()));
	params.put(DataExpression.RAND_LAMBDA, new LiteralOp(rand.getPdfParams()));
	params.put(DataExpression.RAND_SPARSITY, new LiteralOp(rand.getSparsity()));
	params.put(DataExpression.RAND_SEED, new LiteralOp(rand.getSeed()));
	Hop datagen = new DataGenOp(Types.OpOpDG.RAND, new DataIdentifier("tmp"), params);
	datagen.setBlocksize(rand.getBlocksize());
	operands.put(item.getId(), datagen);
	}
	break;
	}
	case Instruction: {
	CPInstruction.CPType ctype = InstructionUtils.getCPTypeByOpcode(item.getOpcode());

	if(ctype != null) {
	switch(ctype) {
	case AggregateBinary: {
	Hop input1 = operands.get(item.getInputs()[0].getId());
	Hop input2 = operands.get(item.getInputs()[1].getId());
	//Build the hops for the derivatives
	ReorgOp trasnX = HopRewriteUtils.createTranspose(input1);
	ReorgOp trasnW = HopRewriteUtils.createTranspose(input2);
	Hop dX = HopRewriteUtils.createMatrixMultiply(mo, trasnW);
	Hop dW = HopRewriteUtils.createMatrixMultiply(trasnX, mo);
	operands.put(item.getId(), dX);
	operands.put(item.getId() + 1, dW);
	allHops.add(dX);
	allHops.add(dW);
	names.add("dX");
	names.add("dW");
	break;
	}
	case Binary: {
	//handle special cases of binary operations
	String opcode = item.getOpcode();
	Hop output = null;
	if(opcode.equals("+"))
	output = HopRewriteUtils.createAggUnaryOp(mo, Types.AggOp.SUM, Types.Direction.Col);
	operands.put(item.getId(), output);
	allHops.add(output);
	names.add("dB");
	break;
	}
	default:
	throw new DMLRuntimeException(
	"Unsupported autoDiff instruction " + "type: " + ctype.name() + " (" + item.getOpcode() + ").");
	}
	}
	break;
	}
	case Literal: {
	CPOperand op = new CPOperand(item.getData());
	operands.put(item.getId(), ScalarObjectFactory
	.createLiteralOp(op.getValueType(), op.getName()));
	break;
	}
	default:
	throw new DMLRuntimeException("Lineage type " + item.getType() + " is not supported");
	}
	}
	private static void executeInst(ArrayList<Instruction> newInst, ExecutionContext lrwec)
	{
	try {
	//execute instructions
	BasicProgramBlock pb = new BasicProgramBlock(new Program());
	pb.setInstructions(newInst);
	pb.execute(lrwec);
	}
	catch (Exception e) {
	throw new DMLRuntimeException("Error executing autoDiff instruction" , e);
	}
	}
	}