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

/*******************************************************************************
 * Copyright (c) 2017-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.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

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.SWModel;
import org.eclipse.app4mc.multicore.partitioning.utils.CheckLabels;
import org.eclipse.app4mc.multicore.partitioning.utils.Helper;
import org.eclipse.core.runtime.NullProgressMonitor;
import org.eclipse.emf.common.util.EList;
import org.jgrapht.alg.CycleDetector;
import org.jgrapht.alg.cycle.SzwarcfiterLauerSimpleCycles;
import org.jgrapht.experimental.dag.DirectedAcyclicGraph;
import org.jgrapht.experimental.dag.DirectedAcyclicGraph.CycleFoundException;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * This class provides critical path determination, as well as timeframe values (earliest initial time and latest initial time) for any runnable, that is
 * contained within the critical path's graph
 *
 */
public class CriticalPath {
	private static final Logger LOGGER = LoggerFactory.getLogger(CriticalPath.class);
	private final DirectedAcyclicGraph<Runnable, RunnableSequencingConstraint> graph;
	private final SWModel swm;
	private ConstraintsModel cm;
	private Path cp;
	private final Map<Runnable, CriticalPath.TimeFrame> cache = new HashMap<>();
	private final HashMap<Runnable, Long> earliestFinTime = new HashMap<>();

	class TimeFrame {
		long eit = 0;
		long lit = 0;

		public TimeFrame(final long eit, final long lit) {
			this.eit = eit;
			this.lit = lit;
		}

		@Override
		public String toString() {
			return (Long.toString(this.eit) + " " + Long.toString(this.lit));
		}
	}

	/**
	 * Constructor creates graph from given @param swmodel (swm) and @param constraints model (cm) already
	 *
	 */
	public CriticalPath(final SWModel swm, final ConstraintsModel cm) {
		this.swm = swm;
		this.cm = cm;
		LOGGER.debug("{} RSCs", cm.getRunnableSequencingConstraints().size());
		this.graph = createJGraphT();
	}


	/**
	 * Get the @param r Runnable's time frame wrt the graph
	 *
	 * @return
	 */
	public TimeFrame getTF(final Runnable r) {
		return this.cache.get(r);
	}


	/**
	 * calculates the critical path of a swmodel
	 *
	 * @return critical path as EList<Runnable>
	 */
	public EList<Runnable> getCP() {
		if (null != this.cp) {
			return this.cp.getRunnablesL();
		}
		if (this.swm.getProcessPrototypes().isEmpty()) {
			final AmaltheaFactory swf = AmaltheaFactory.eINSTANCE;
			final ProcessPrototype pp = swf.createProcessPrototype();
			pp.setName("AllRunnables");
			for (final Runnable r : this.swm.getRunnables()) {
				final RunnableCall trc = swf.createRunnableCall();
				trc.setRunnable(r);
				pp.getRunnableCalls().add(trc);
			}
			this.swm.getProcessPrototypes().add(pp);
		}
		final Path cpt = getCrPa();
		assert cpt != null;
		this.cp = cpt;
		updateCacheTFs();
		return sortRunnables(cpt.getRunnablesL());
	}


	/**
	 * returns the @param EList<Runnable> p as a string of runnables
	 *
	 * @return String with runnables and time frames
	 */
	public String getPathString(final EList<Runnable> p) {
		final StringBuilder str = new StringBuilder();
		for (final Runnable r : p) {
			str.append(r.getName() + "(" + getTFString(r) + ") ");
		}
		return str.toString();
	}


	/**
	 * calculates the complete runtime (instructions) of a given @param EList <Runnable>
	 */
	public long getPathLength(final EList<Runnable> rl) {
		long length = 0;
		for (final Runnable r : rl) {
			length += new Helper().getInstructions(r);
		}
		return length;
	}


	public long getPathLength() {
		long length = 0;
		for (final Runnable r : this.cp.getRunnablesL()) {
			length += new Helper().getInstructions(r);
		}
		return length;
	}


	/**
	 * @param runnable that predecessor run time should be found
	 * @return longst predecessor run time
	 */
	public long getLongestPrecRT(final Runnable r) {
		if (this.earliestFinTime.containsKey(r)) {
			return this.earliestFinTime.get(r) - new Helper().getInstructions(r);
		}
		assert this.graph != null;
		if (this.graph.incomingEdgesOf(r).isEmpty()) {
			this.earliestFinTime.put(r, new Helper().getInstructions(r));
			return 0l;
		}
		final Iterator<RunnableSequencingConstraint> i = this.graph.incomingEdgesOf(r).iterator();
		final Set<Long> rts = new HashSet<>();
		while (i.hasNext()) {
			addRecPrcRT(r, i, rts);
		}
		long max = 0;
		for (final long rtc : rts) {
			if (rtc > max) {
				max = rtc;
			}
		}
		this.earliestFinTime.put(r, max + new Helper().getInstructions(r));
		return max;
	}


	/**
	 * Get a directed graph with runnables as vertices and runnablesequencingconstraints as edges
	 *
	 * @return graph
	 */
	public DirectedAcyclicGraph<Runnable, RunnableSequencingConstraint> getGraph() {
		return this.graph;
	}


	public Map<Runnable, CriticalPath.TimeFrame> getCache() {
		return this.cache;
	}


	private DirectedAcyclicGraph<Runnable, RunnableSequencingConstraint> createJGraphT() {
		final DirectedAcyclicGraph<Runnable, RunnableSequencingConstraint> test = new DirectedAcyclicGraph<>(null);
		for (final Runnable r : this.swm.getRunnables()) {
			test.addVertex(r);
		}
		if (null == this.cm || this.cm.getRunnableSequencingConstraints().isEmpty()) {
			final CheckLabels cl = new CheckLabels();
			cl.setSwm(this.swm);
			cl.setCMModel(this.cm);
			cl.run(new NullProgressMonitor());
			this.cm = cl.getCMModel();
		}
		for (final RunnableSequencingConstraint rsc : this.cm.getRunnableSequencingConstraints()) {
			try {
				test.addDagEdge(rsc.getRunnableGroups().get(0).getRunnables().get(0), rsc.getRunnableGroups().get(1).getRunnables().get(0),
						rsc);
			}
			catch (final CycleFoundException e) {
				// do not add a cycle
			}
		}
		LOGGER.debug("Created {} RSCs", this.cm.getRunnableSequencingConstraints().size());

		return test;
	}

	/**
	 * Sorts the given @param rl wrt each runnable's eit value
	 *
	 * @return
	 */
	private EList<Runnable> sortRunnables(final EList<Runnable> rl) {
		Collections.sort(rl, (final Runnable o1, final Runnable o2) -> (int) getTF(o1).eit - (int) getTF(o2).eit);
		return rl;
	}

	/**
	 * Get a time frame of the Runnable @param r, wrt the graph
	 *
	 * @return timeframe consisting of eit (earliest initial time) and lit (latest initial time)
	 */
	private String getTFString(final Runnable r) {
		final TimeFrame tF = this.cache.get(r);
		return tF.eit + " " + tF.lit + " " + (tF.eit + new Helper().getInstructions(r));
	}

	/**
	 * critical path calculation
	 *
	 * @return critial path
	 */
	private Path getCrPa() {
		final SzwarcfiterLauerSimpleCycles<Runnable, RunnableSequencingConstraint> slsc = new SzwarcfiterLauerSimpleCycles<>();
		slsc.setGraph(this.graph);
		final CycleDetector<Runnable, RunnableSequencingConstraint> cd = new CycleDetector<>(this.graph);
		if (cd.detectCycles()) {
			LOGGER.error("THERE ARE STILL CYCLES");
			return null;
		}
		final List<Runnable> sinks = new GGP(this.swm, this.cm, this.graph).getSinks();
		LOGGER.debug("{} sinks out of {} runnables.", sinks.size(), this.swm.getRunnables().size());
		final HashMap<Runnable, Long> rts = new HashMap<>();
		for (final Runnable sink : sinks) {
			rts.put(sink, getLongestPrecRT(sink) + new Helper().getInstructions(sink));
		}
		Runnable cps = null;
		long max = 0;
		for (final Entry<Runnable, Long> r : rts.entrySet()) {
			if (rts.get(r.getKey()) > max) {
				max = rts.get(r.getKey());
				cps = r.getKey();
			}
		}
		LOGGER.debug("Max sinklength {}", max);
		final Path cpt = getPrecedingCriticalPath(cps);
		if (max != new Helper().getRSLenth(cpt)) {
			LOGGER.error("CP does not match longestPrecLength!");
		}
		this.cp = cpt;
		this.cp.updateRunTime();
		return cpt;
	}

	private Path getPrecedingCriticalPath(Runnable cps) {
		final Path p = new Path();
		p.getRunnables().add(cps);
		long time = this.earliestFinTime.get(cps).longValue() - new Helper().getInstructions(cps);
		while (time > 0) {
			final Set<RunnableSequencingConstraint> iel = this.graph.incomingEdgesOf(cps);
			final long temp = time;
			for (final RunnableSequencingConstraint rsc : iel) {
				final Runnable source = this.graph.getEdgeSource(rsc);
				if (this.earliestFinTime.get(source).longValue() == time) {
					p.getRunnables().add(source);
					cps = source;
					time -= new Helper().getInstructions(cps);
					break;
				}
			}
			if (temp == time) {
				LOGGER.error("No preceeding runnable found. TIME {}", time);
				break;
			}
		}
		return p;
	}

	/**
	 * Called, after CP has been found to set all available time frames
	 */
	private void updateCacheTFs() {
		initSrtl();
		long max = 0;
		for (final Runnable run : this.swm.getRunnables()) {
			final TimeFrame tF = new TimeFrame(0, 0);
			tF.eit = this.earliestFinTime.get(run) - new Helper().getInstructions(run);
			tF.lit = this.cp.getRuntime() - getLongestSuceedingRT(run);
			max = this.earliestFinTime.get(run).longValue() > max ? this.earliestFinTime.get(run).longValue() : max;
			this.cache.put(run, tF);
			LOGGER.trace("{} precRT {}", run.getName(), tF.eit);
		}
		LOGGER.trace("max {}", max);
	}

	private void addRecPrcRT(final Runnable r, final Iterator<RunnableSequencingConstraint> i, final Set<Long> rts) {
		final RunnableSequencingConstraint rscTemp = i.next();
		final Runnable source = this.graph.getEdgeSource(rscTemp);
		if (null != new Helper().getPPfromR(r, this.swm) && null != new Helper().getPPfromR(source, this.swm)
				&& new Helper().getPPfromR(r, this.swm).equals(new Helper().getPPfromR(source, this.swm))) {
			if (!this.earliestFinTime.containsKey(source)) {
				getLongestPrecRT(source);
			}
			rts.add(this.earliestFinTime.get(source));
		}
		else {
			if (null == new Helper().getPPfromR(r, this.swm) || null == new Helper().getPPfromR(source, this.swm)) {
				LOGGER.error("No ProcessPrototype for Runnable {} or {}", r.getName(), source.getName());
			}
		}
	}

	private final HashMap<Runnable, Long> srtl = new HashMap<>();

	private void initSrtl() {
		for (final Runnable r : this.swm.getRunnables()) {
			this.srtl.put(r, (long) 0);
		}
	}

	private long getLongestSuceedingRT(final Runnable r) {
		long rt = 0;
		if (this.graph.outgoingEdgesOf(r).isEmpty()) {
			rt = new Helper().getInstructions(r);
			this.srtl.put(r, rt);
			return rt;
		}
		final Iterator<RunnableSequencingConstraint> i = this.graph.outgoingEdgesOf(r).iterator();
		final Set<Long> outgoingEdges = new HashSet<>();
		while (i.hasNext()) {
			final RunnableSequencingConstraint rscTemp = i.next();
			final Runnable target = this.graph.getEdgeTarget(rscTemp);

			if (null != new Helper().getPPfromR(r, this.swm) && null != new Helper().getPPfromR(target, this.swm)
					&& new Helper().getPPfromR(r, this.swm).equals(new Helper().getPPfromR(target, this.swm))) {
				if (this.srtl.get(target).longValue() == 0) {
					outgoingEdges.add(getLongestSuceedingRT(target));
				}
				else {
					// prevents already visited runnables from redundant
					// calculations
					outgoingEdges.add(this.srtl.get(target));
				}
			}
		}
		for (final long rtc : outgoingEdges) {
			if (rt < rtc) {
				rt = rtc;
			}
		}

		final long rtt = rt + new Helper().getInstructions(r);
		this.srtl.put(r, rtt);
		return rtt;
	}

}