archive/plugins/org.eclipse.app4mc.multicore.partitioning/src/org/eclipse/app4mc/multicore/partitioning/algorithms/GGP.java - app4mc/org.eclipse.app4mc - Git at Google

 /*******************************************************************************
  * 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.HashSet;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
 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.Helper;
 import org.jgrapht.experimental.dag.DirectedAcyclicGraph;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;

 /**
  * GGP means Global Graph Partitioning. The GGP approach identifies independent graphs and creates ProcessPrototypes for each graph.
  */
 public class GGP {
 	private static final Logger LOGGER = LoggerFactory.getLogger(GGP.class);
 	private final SWModel swm;
 	private final ConstraintsModel cm;
 	private LinkedList<Runnable> unassigned = new LinkedList<>();
 	LinkedList<LinkedList<Runnable>> tasks = new LinkedList<>();
 	private final LinkedList<Runnable> visited = new LinkedList<>();
 	private final LinkedList<Runnable> unvisited = new LinkedList<>();
 	private DirectedAcyclicGraph<Runnable, RunnableSequencingConstraint> graph = null;

 	GGP(final SWModel swm, final LinkedList<Runnable> uCNs, final LinkedList<LinkedList<Runnable>> threads, final ConstraintsModel cm) {
 		this.swm = swm;
 		this.unassigned = uCNs;
 		this.tasks = threads;
 		this.cm = cm;
 	}

 	public GGP(final SWModel swm, final ConstraintsModel cm) {
 		this.cm = cm;
 		this.swm = swm;
 		for (final Runnable r : swm.getRunnables()) {
 			this.unassigned.add(r);
 			this.unvisited.add(r);
 		}
 	}

 	public GGP(final SWModel swm, final ConstraintsModel cm, final DirectedAcyclicGraph<Runnable, RunnableSequencingConstraint> graph) {
 		this.cm = cm;
 		this.swm = swm;
 		this.graph = graph;
 	}

 	/**
 	 * starts the independent graph identification and stores its outcome in the SWModel swm as prototypes
 	 */
 	public void build() {
 		if (this.unassigned.isEmpty()) {
 			this.unassigned.addAll(this.swm.getRunnables());
 		}
 		else if (this.unassigned.size() != this.swm.getRunnables().size()) {
 			LOGGER.debug("Unassigned != Runnables.size");
 		}
 		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);
 		}

 		this.graph = new CriticalPath(getSwm(), getCm()).getGraph();

 		for (final ProcessPrototype pp : this.swm.getProcessPrototypes()) {
 			genGraphs(pp);
 		}
 		final StringBuilder sb = new StringBuilder();
 		int ct = 0;
 		for (final LinkedList<Runnable> lrl : this.tasks) {
 			sb.append(ct++ + ": ");
 			for (final Runnable r : lrl) {
 				sb.append(r.getName() + ", ");
 			}
 			sb.append("\n");
 		}
 		correctPPs();
 	}

 	/**
 	 * This method identifies the first unassigned source runnable of a ProcessPrototype, and returns the corresponding graph. In case there are multiple
 	 * independent graphs within a ProcessPrototype, the method recursively assigns all graphs to the global thread list begnning with the biggest graph untill
 	 * the smallest graph is returned. In case there is no graph but loose runnables only, the method returns a list of all loose runnables according to the
 	 * ProcessPrototye.
 	 *
 	 * @throws Exception
 	 **/
 	private void genGraphs(final ProcessPrototype pp) {
 		final List<Runnable> sinks = getSinks(pp);
 		if (sinks.isEmpty()) {
 			LOGGER.debug("getGraph didnt find unhandled Runnable at {}; TRCs {}", pp.getName(), pp.getRunnableCalls().size());
 			return;
 		}

 		for (final Runnable r : sinks) {
 			if (this.unassigned.contains(r)) {
 				final Set<Runnable> task = getCoherentNodes(r, pp);
 				this.unassigned.removeAll(task);
 				final LinkedList<Runnable> temp = new LinkedList<>();
 				temp.addAll(task);
 				this.tasks.add(temp);
 			}
 		}
 	}

 	private List<Runnable> getSinks(final ProcessPrototype pp) {
 		final List<Runnable> sinks = getSinks();
 		final Set<Runnable> rs = new HashSet<>();
 		for (final RunnableCall trc : pp.getRunnableCalls()) {
 			rs.add(trc.getRunnable());
 		}
 		sinks.retainAll(rs);
 		return sinks;
 	}

 	public List<Runnable> getSinks() {
 		final List<Runnable> sinks = new LinkedList<>();
 		for (final Runnable r : this.swm.getRunnables()) {
 			if (this.graph.outgoingEdgesOf(r).isEmpty()) {
 				sinks.add(r);
 			}
 			else {
 				final Set<RunnableSequencingConstraint> oe = this.graph.outgoingEdgesOf(r);
 				int ct = 0;
 				for (final RunnableSequencingConstraint rsc : oe) {
 					final Runnable target = this.graph.getEdgeTarget(rsc);
 					if (!new Helper().getPPfromR(r, this.swm).equals(new Helper().getPPfromR(target, this.swm))) {
 						ct++;
 					}
 				}
 				if (oe.size() == ct) {
 					sinks.add(r);
 				}
 			}
 		}
 		if (sinks.isEmpty()) {
 			LOGGER.error("No sink found");
 		}
 		return sinks;
 	}

 	/**
 	 * Looks for all Runnables within the ProcessPrototype @param ppi, that precede or succeed the runnable @param r according to dependencies
 	 *
 	 */
 	private Set<Runnable> getCoherentNodes(final Runnable r, final ProcessPrototype pp) {
 		final Set<Runnable> rl = new HashSet<>();
 		rl.add(r);
 		this.visited.add(r);
 		final Iterator<RunnableSequencingConstraint> i = this.graph.incomingEdgesOf(r).iterator();
 		while (i.hasNext()) {
 			final RunnableSequencingConstraint rsc = i.next();
 			final Runnable source = this.graph.getEdgeSource(rsc);
 			if (new Helper().getPPfromR(source, this.swm).equals(pp) && !this.visited.contains(source)) {
 				rl.addAll(getCoherentNodes(source, pp));
 			}
 		}
 		final Iterator<RunnableSequencingConstraint> i2 = this.graph.outgoingEdgesOf(r).iterator();
 		while (i2.hasNext()) {
 			final RunnableSequencingConstraint rsc = i2.next();
 			final Runnable target = this.graph.getEdgeTarget(rsc);
 			if (new Helper().getPPfromR(target, this.swm).equals(pp) && !this.visited.contains(target)) {
 				rl.addAll(getCoherentNodes(target, pp));
 			}
 		}
 		return rl;
 	}

 	public SWModel getSwm() {
 		return this.swm;
 	}

 	public ConstraintsModel getCm() {
 		return this.cm;
 	}

 	/**
 	 * creates PPs, TRCs, PPname, PPactivation, PPfirstrunnable, PPlastrunnable requires this.tasks
 	 */
 	private void correctPPs() {
 		this.swm.getProcessPrototypes().clear();
 		int i = 0;
 		for (final LinkedList<Runnable> llr : this.tasks) {
 			final AmaltheaFactory instance = AmaltheaFactory.eINSTANCE;

 			final ProcessPrototype pp = instance.createProcessPrototype();
 			for (final Runnable r : llr) {
 				final RunnableCall trc = instance.createRunnableCall();
 				trc.setRunnable(r);
 				pp.getRunnableCalls().add(trc);
 			}
 			pp.setName("PP" + i++);
 			pp.setActivation(pp.getRunnableCalls().get(0).getRunnable().getFirstActivation());
 			pp.setFirstRunnable(llr.get(0));
 			pp.setLastRunnable(llr.get(llr.size() - 1));
 			this.swm.getProcessPrototypes().add(pp);
 		}
 		/* update PP references in constraints model */
 		for (final RunnableSequencingConstraint rsc : this.cm.getRunnableSequencingConstraints()) {
 			setProcessScopes(rsc);
 		}
 	}

 	private void setProcessScopes(final RunnableSequencingConstraint rsc) {
 		final Runnable source = rsc.getRunnableGroups().get(0).getRunnables().get(0);
 		final Runnable target = rsc.getRunnableGroups().get(1).getRunnables().get(0);
 		if (!this.swm.getRunnables().contains(source) || !this.swm.getRunnables().contains(target)) {
 			LOGGER.debug("Runnable {} / {} could not be found. SWM.size {}", source.getName(), target.getName(),
 					this.swm.getRunnables().size());
 		}
 		for (final ProcessPrototype pp : this.swm.getProcessPrototypes()) {
 			for (final RunnableCall trc : pp.getRunnableCalls()) {
 				if (trc.getRunnable().equals(source) || trc.getRunnable().equals(target)) {
 					rsc.getProcessScope().clear();
 					rsc.getProcessScope().add(pp);
 				}
 			}
 		}
 	}
 }
	/*******************************************************************************
	* 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.HashSet;
	import java.util.Iterator;
	import java.util.LinkedList;
	import java.util.List;
	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.Helper;
	import org.jgrapht.experimental.dag.DirectedAcyclicGraph;
	import org.slf4j.Logger;
	import org.slf4j.LoggerFactory;

	/**
	* GGP means Global Graph Partitioning. The GGP approach identifies independent graphs and creates ProcessPrototypes for each graph.
	*/
	public class GGP {
	private static final Logger LOGGER = LoggerFactory.getLogger(GGP.class);
	private final SWModel swm;
	private final ConstraintsModel cm;
	private LinkedList<Runnable> unassigned = new LinkedList<>();
	LinkedList<LinkedList<Runnable>> tasks = new LinkedList<>();
	private final LinkedList<Runnable> visited = new LinkedList<>();
	private final LinkedList<Runnable> unvisited = new LinkedList<>();
	private DirectedAcyclicGraph<Runnable, RunnableSequencingConstraint> graph = null;

	GGP(final SWModel swm, final LinkedList<Runnable> uCNs, final LinkedList<LinkedList<Runnable>> threads, final ConstraintsModel cm) {
	this.swm = swm;
	this.unassigned = uCNs;
	this.tasks = threads;
	this.cm = cm;
	}

	public GGP(final SWModel swm, final ConstraintsModel cm) {
	this.cm = cm;
	this.swm = swm;
	for (final Runnable r : swm.getRunnables()) {
	this.unassigned.add(r);
	this.unvisited.add(r);
	}
	}

	public GGP(final SWModel swm, final ConstraintsModel cm, final DirectedAcyclicGraph<Runnable, RunnableSequencingConstraint> graph) {
	this.cm = cm;
	this.swm = swm;
	this.graph = graph;
	}

	/**
	* starts the independent graph identification and stores its outcome in the SWModel swm as prototypes
	*/
	public void build() {
	if (this.unassigned.isEmpty()) {
	this.unassigned.addAll(this.swm.getRunnables());
	}
	else if (this.unassigned.size() != this.swm.getRunnables().size()) {
	LOGGER.debug("Unassigned != Runnables.size");
	}
	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);
	}

	this.graph = new CriticalPath(getSwm(), getCm()).getGraph();

	for (final ProcessPrototype pp : this.swm.getProcessPrototypes()) {
	genGraphs(pp);
	}
	final StringBuilder sb = new StringBuilder();
	int ct = 0;
	for (final LinkedList<Runnable> lrl : this.tasks) {
	sb.append(ct++ + ": ");
	for (final Runnable r : lrl) {
	sb.append(r.getName() + ", ");
	}
	sb.append("\n");
	}
	correctPPs();
	}

	/**
	* This method identifies the first unassigned source runnable of a ProcessPrototype, and returns the corresponding graph. In case there are multiple
	* independent graphs within a ProcessPrototype, the method recursively assigns all graphs to the global thread list begnning with the biggest graph untill
	* the smallest graph is returned. In case there is no graph but loose runnables only, the method returns a list of all loose runnables according to the
	* ProcessPrototye.
	*
	* @throws Exception
	**/
	private void genGraphs(final ProcessPrototype pp) {
	final List<Runnable> sinks = getSinks(pp);
	if (sinks.isEmpty()) {
	LOGGER.debug("getGraph didnt find unhandled Runnable at {}; TRCs {}", pp.getName(), pp.getRunnableCalls().size());
	return;
	}

	for (final Runnable r : sinks) {
	if (this.unassigned.contains(r)) {
	final Set<Runnable> task = getCoherentNodes(r, pp);
	this.unassigned.removeAll(task);
	final LinkedList<Runnable> temp = new LinkedList<>();
	temp.addAll(task);
	this.tasks.add(temp);
	}
	}
	}

	private List<Runnable> getSinks(final ProcessPrototype pp) {
	final List<Runnable> sinks = getSinks();
	final Set<Runnable> rs = new HashSet<>();
	for (final RunnableCall trc : pp.getRunnableCalls()) {
	rs.add(trc.getRunnable());
	}
	sinks.retainAll(rs);
	return sinks;
	}

	public List<Runnable> getSinks() {
	final List<Runnable> sinks = new LinkedList<>();
	for (final Runnable r : this.swm.getRunnables()) {
	if (this.graph.outgoingEdgesOf(r).isEmpty()) {
	sinks.add(r);
	}
	else {
	final Set<RunnableSequencingConstraint> oe = this.graph.outgoingEdgesOf(r);
	int ct = 0;
	for (final RunnableSequencingConstraint rsc : oe) {
	final Runnable target = this.graph.getEdgeTarget(rsc);
	if (!new Helper().getPPfromR(r, this.swm).equals(new Helper().getPPfromR(target, this.swm))) {
	ct++;
	}
	}
	if (oe.size() == ct) {
	sinks.add(r);
	}
	}
	}
	if (sinks.isEmpty()) {
	LOGGER.error("No sink found");
	}
	return sinks;
	}

	/**
	* Looks for all Runnables within the ProcessPrototype @param ppi, that precede or succeed the runnable @param r according to dependencies
	*
	*/
	private Set<Runnable> getCoherentNodes(final Runnable r, final ProcessPrototype pp) {
	final Set<Runnable> rl = new HashSet<>();
	rl.add(r);
	this.visited.add(r);
	final Iterator<RunnableSequencingConstraint> i = this.graph.incomingEdgesOf(r).iterator();
	while (i.hasNext()) {
	final RunnableSequencingConstraint rsc = i.next();
	final Runnable source = this.graph.getEdgeSource(rsc);
	if (new Helper().getPPfromR(source, this.swm).equals(pp) && !this.visited.contains(source)) {
	rl.addAll(getCoherentNodes(source, pp));
	}
	}
	final Iterator<RunnableSequencingConstraint> i2 = this.graph.outgoingEdgesOf(r).iterator();
	while (i2.hasNext()) {
	final RunnableSequencingConstraint rsc = i2.next();
	final Runnable target = this.graph.getEdgeTarget(rsc);
	if (new Helper().getPPfromR(target, this.swm).equals(pp) && !this.visited.contains(target)) {
	rl.addAll(getCoherentNodes(target, pp));
	}
	}
	return rl;
	}

	public SWModel getSwm() {
	return this.swm;
	}

	public ConstraintsModel getCm() {
	return this.cm;
	}

	/**
	* creates PPs, TRCs, PPname, PPactivation, PPfirstrunnable, PPlastrunnable requires this.tasks
	*/
	private void correctPPs() {
	this.swm.getProcessPrototypes().clear();
	int i = 0;
	for (final LinkedList<Runnable> llr : this.tasks) {
	final AmaltheaFactory instance = AmaltheaFactory.eINSTANCE;

	final ProcessPrototype pp = instance.createProcessPrototype();
	for (final Runnable r : llr) {
	final RunnableCall trc = instance.createRunnableCall();
	trc.setRunnable(r);
	pp.getRunnableCalls().add(trc);
	}
	pp.setName("PP" + i++);
	pp.setActivation(pp.getRunnableCalls().get(0).getRunnable().getFirstActivation());
	pp.setFirstRunnable(llr.get(0));
	pp.setLastRunnable(llr.get(llr.size() - 1));
	this.swm.getProcessPrototypes().add(pp);
	}
	/* update PP references in constraints model */
	for (final RunnableSequencingConstraint rsc : this.cm.getRunnableSequencingConstraints()) {
	setProcessScopes(rsc);
	}
	}

	private void setProcessScopes(final RunnableSequencingConstraint rsc) {
	final Runnable source = rsc.getRunnableGroups().get(0).getRunnables().get(0);
	final Runnable target = rsc.getRunnableGroups().get(1).getRunnables().get(0);
	if (!this.swm.getRunnables().contains(source) \|\| !this.swm.getRunnables().contains(target)) {
	LOGGER.debug("Runnable {} / {} could not be found. SWM.size {}", source.getName(), target.getName(),
	this.swm.getRunnables().size());
	}
	for (final ProcessPrototype pp : this.swm.getProcessPrototypes()) {
	for (final RunnableCall trc : pp.getRunnableCalls()) {
	if (trc.getRunnable().equals(source) \|\| trc.getRunnable().equals(target)) {
	rsc.getProcessScope().clear();
	rsc.getProcessScope().add(pp);
	}
	}
	}
	}
	}