archive/plugins/org.eclipse.app4mc.multicore.partitioning/src/org/eclipse/app4mc/multicore/partitioning/algorithms/TCbasedPart.java

/*******************************************************************************
 * Copyright (c) 2020 Dortmund University of Applied Sciences and Arts and others.
 *
 *  This program and the accompanying materials are made
 *  available under the terms of the Eclipse Public License 2.0
 *  which is available at https://www.eclipse.org/legal/epl-2.0/
 *
 *  SPDX-License-Identifier: EPL-2.0
 *
 *  Contributors:
 *      Dortmund University of Applied Sciences and Arts - initial API and implementation
 *******************************************************************************/
package org.eclipse.app4mc.multicore.partitioning.algorithms;

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Set;

import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solution;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.variables.IntVar;
import org.chocosolver.solver.variables.Task;
import org.eclipse.app4mc.amalthea.model.Amalthea;
import org.eclipse.app4mc.amalthea.model.AmaltheaFactory;
import org.eclipse.app4mc.amalthea.model.ConstraintsModel;
import org.eclipse.app4mc.amalthea.model.ProcessPrototype;
import org.eclipse.app4mc.amalthea.model.Runnable;
import org.eclipse.app4mc.amalthea.model.RunnableCall;
import org.eclipse.app4mc.amalthea.model.RunnableSequencingConstraint;
import org.eclipse.app4mc.amalthea.model.util.CustomPropertyUtil;
import org.eclipse.app4mc.multicore.partitioning.utils.CycleElimination;
import org.eclipse.app4mc.multicore.partitioning.utils.Helper;
import org.jgrapht.DirectedGraph;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;


public class TCbasedPart {
	private final Amalthea amaltheaModel;
	private int gDivisor = 1;
	private static final Logger LOGGER = LoggerFactory.getLogger(TCbasedPart.class);

	public TCbasedPart(final Amalthea ama) {
		this.amaltheaModel = ama;
	}

	public void run(final int nBPartitions, final int solveTimeInS, DirectedGraph<Runnable, RunnableSequencingConstraint> directedGraph) {
		if (null == directedGraph) {
			final CriticalPath cp = new CriticalPath(this.amaltheaModel.getSwModel(), this.amaltheaModel.getConstraintsModel());
			cp.getCP();
			directedGraph = cp.getGraph();
		}
		long instrSum = 0;
		for (final Runnable r : this.amaltheaModel.getSwModel().getRunnables()) {
			instrSum += new Helper().getInstructions(r);
		}
		if (instrSum > Integer.MAX_VALUE / 2) {
			this.gDivisor = 100;
		}
		final ConstraintsModel cm = new Helper().ensureDepsNoCycles(this.amaltheaModel);
		final int nbRuns = this.amaltheaModel.getSwModel().getRunnables().size();
		final int maxLength = this.gDivisor > 1 ? (int) (getInstruSum() + this.gDivisor * nbRuns) : getInstruSum();


		/**************** 1. CONSTRUCT CHOCO MODEL ******************/
		final Model chocoModel = new Model("Partitioning_Cumulative");

		final IntVar[] weightsiv = chocoModel.intVarArray("weights", nbRuns, 0, maxLength);
		for (final Runnable r : this.amaltheaModel.getSwModel().getRunnables()) {
			int instr = (int) new Helper().getInstructions(r) / this.gDivisor;
			final int index = this.amaltheaModel.getSwModel().getRunnables().indexOf(r);
			instr = instr > this.gDivisor ? instr : this.gDivisor;
			weightsiv[index].eq(instr).post();
		}
		final IntVar[] runStart = chocoModel.intVarArray("runStartTime", nbRuns, 0, maxLength, true);
		final IntVar[] runEnd = chocoModel.intVarArray("runEndTime", nbRuns, 0, maxLength, true);

		final Task[] tv = chocoModel.taskVarArray(runStart, weightsiv, runEnd);
		final IntVar[] heights = chocoModel.intVarArray(nbRuns, 1, 1);

		final IntVar maxEndTime = chocoModel.intVar("maxEndTime", 0, maxLength, true);
		LOGGER.debug("TCPart Vars set for {} partitions", nBPartitions);


		/**************** 2. APPLY CONSTRAINTS **********************/
		chocoModel.cumulative(tv, heights, chocoModel.intVar(nBPartitions)).post();
		chocoModel.max(maxEndTime, runEnd).post();

		/* precedence constraints */
		final CriticalPath cp = new CriticalPath(this.amaltheaModel.getSwModel(), this.amaltheaModel.getConstraintsModel());
		cp.getCP();
		final CycleElimination ce = new CycleElimination(this.amaltheaModel.getSwModel(), this.amaltheaModel.getConstraintsModel());
		if (ce.containsCycles()) {
			LOGGER.error("Model contains cycles");
			return;
		}
		LOGGER.debug("Model contains NO cycles");
		final Helper h = new Helper();
		for (final Runnable r : this.amaltheaModel.getSwModel().getRunnables()) {
			final int rindex = this.amaltheaModel.getSwModel().getRunnables().indexOf(r);
			final Set<Runnable> rs = h.getPreceedingRunnables(cm, r, directedGraph);
			rs.remove(r);
			for (final Runnable pred : rs) {
				final int predindex = this.amaltheaModel.getSwModel().getRunnables().indexOf(pred);
				chocoModel.arithm(runStart[rindex], ">=", runEnd[predindex]).post();
			}
		}
		LOGGER.debug("TCPart Constraints set");

		chocoModel.setObjective(false, maxEndTime);
		chocoModel.getSolver().limitTime(solveTimeInS * 1000l);

		/**************** 3. SOLUTION PROCESS ***********************/
		final Solution fs = new Solution(chocoModel);
		final Solver solver = chocoModel.getSolver();
		try {
			while (solver.solve()) {
				LOGGER.debug("Solution found");
				fs.record();
			}
		}
		catch (final Exception e) {
			e.printStackTrace();
		}


		if (!fs.exists()) {
			this.solved = false;
			LOGGER.error("CP-P did not finish.");
			solver.printStatistics();
			return;
		}
		solver.printStatistics();
		LOGGER.info("Solution: {}", fs);
		final String str = printStartEndTimes(fs, runStart, runEnd);
		LOGGER.trace("Resolution finished\n{}", str);


		/**************** 4. APPLY SOLUTION TO AMALTHEA MODEL *******/
		/* apply CP solution to new PPs */
		createPPsFromSolution(nBPartitions, runStart, maxEndTime, solver, fs);
		final String str2 = new Helper().writePPs(this.amaltheaModel.getSwModel().getProcessPrototypes());
		LOGGER.debug("\n{}", str2);
	}


	private String printStartEndTimes(final Solution fs, final IntVar[] runStart, final IntVar[] runEnd) {
		final StringBuilder sb = new StringBuilder();
		for (final Runnable r : this.amaltheaModel.getSwModel().getRunnables()) {
			final int index = this.amaltheaModel.getSwModel().getRunnables().indexOf(r);
			sb.append(r.getName() + ":" + fs.getIntVal(runStart[index]) + "-" + fs.getIntVal(runEnd[index]) + "\n");
		}
		return sb.toString();
	}

	boolean solved = true;

	private void createPPsFromSolution(final int nBPartitions, final IntVar[] runStart, final IntVar maxEndTime, final Solver solver,
			final Solution fs) {
		if (solver.getSolutionCount() > 0) {
			this.amaltheaModel.getSwModel().getProcessPrototypes().clear();
			final Set<Runnable> assigned = new HashSet<>();
			for (int i = 0; i < nBPartitions; i++) {
				final ProcessPrototype pp = AmaltheaFactory.eINSTANCE.createProcessPrototype();
				pp.setName(Integer.toString(i));
				this.amaltheaModel.getSwModel().getProcessPrototypes().add(pp);
			}
			for (int i = 0; i < nBPartitions; i++) {
				fillPP(runStart, maxEndTime, fs, assigned, i);
			}
		}
	}

	private void fillPP(final IntVar[] runStart, final IntVar maxEndTime, final Solution fs, final Set<Runnable> assigned, final int i) {
		long ctime = 0;
		long slack = 0;
		while (ctime < fs.getIntVal(maxEndTime)) {
			final RunnableCall rc = AmaltheaFactory.eINSTANCE.createRunnableCall();
			if (slack != Long.MAX_VALUE && slack > 0) {
				CustomPropertyUtil.customPut(rc, "slack", (int) slack);
				slack = 0;
			}
			final Runnable ar = getAssignableRunnable(ctime, assigned, fs, runStart);
			if (null == ar) {
				/*
				 * to ensure precedence constraints, an empty runnable could be
				 * created here with length=getNextRStart-ctime
				 */
				final long cslack = getNextRStart(ctime, assigned, fs, runStart);
				if (cslack != Long.MAX_VALUE) {
					slack += cslack - ctime;
				}
				ctime = cslack;
				continue;
			}
			assigned.add(ar);
			rc.setRunnable(ar);
			ctime += new Helper().getInstructions(ar) / this.gDivisor;
			this.amaltheaModel.getSwModel().getProcessPrototypes().get(i).getRunnableCalls().add(rc);
		}

	}

	private long getNextRStart(final long ctime, final Set<Runnable> assigned, final Solution fs, final IntVar[] runStart) {
		long minStart = Long.MAX_VALUE;
		for (final Runnable r : this.amaltheaModel.getSwModel().getRunnables()) {
			if (assigned.contains(r)) {
				continue;
			}
			final long start = fs.getIntVal(runStart[this.amaltheaModel.getSwModel().getRunnables().indexOf(r)]);
			if (start > ctime && start < minStart) {
				minStart = start;
			}
		}
		return minStart;
	}

	private Runnable getAssignableRunnable(final long ctime, final Set<Runnable> assigned, final Solution fs, final IntVar[] runStart) {
		for (final Runnable r : this.amaltheaModel.getSwModel().getRunnables()) {
			if (assigned.contains(r)) {
				continue;
			}
			if (fs.getIntVal(runStart[this.amaltheaModel.getSwModel().getRunnables().indexOf(r)]) == ctime) {
				return r;
			}
		}
		return null;
	}

	public Amalthea getAmaltheaModel() {
		return this.amaltheaModel;
	}

	private int getInstruSum() {
		BigInteger sum = BigInteger.valueOf(0);
		for (final Runnable r : this.amaltheaModel.getSwModel().getRunnables()) {
			sum = sum.add(BigInteger.valueOf(new Helper().getInstructions(r) / this.gDivisor));
		}
		return sum.intValue();
	}

	public boolean wasSolved() {
		return this.solved;
	}

}