BUG 562793: Add blocking analysis.
Change-Id: Ibcfe2527c2392aa2577052104b119173cd05b05f
Signed-off-by: The Bao Bui <ZeroVNB@Gmail.com>
diff --git a/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/Blocking.java b/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/Blocking.java
new file mode 100644
index 0000000..ad1531b
--- /dev/null
+++ b/eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/Blocking.java
@@ -0,0 +1,1127 @@
+/*******************************************************************************
+ * Copyright (c) 2020 Dortmund University of Applied Sciences and Arts.
+ *
+ * This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License 2.0
+ * which accompanies this distribution, and is available at
+ * https://www.eclipse.org/legal/epl-2.0/
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ *
+ * Contributors: The Bao Bui
+ * FH Dortmund - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.app4mc.gsoc_rta;
+
+import java.math.BigDecimal;
+import java.math.BigInteger;
+import java.math.RoundingMode;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import org.eclipse.app4mc.amalthea.model.ActivityGraphItem;
+import org.eclipse.app4mc.amalthea.model.Amalthea;
+import org.eclipse.app4mc.amalthea.model.Group;
+import org.eclipse.app4mc.amalthea.model.InterProcessStimulus;
+import org.eclipse.app4mc.amalthea.model.InterProcessTrigger;
+import org.eclipse.app4mc.amalthea.model.Label;
+import org.eclipse.app4mc.amalthea.model.LabelAccess;
+import org.eclipse.app4mc.amalthea.model.LabelAccessEnum;
+import org.eclipse.app4mc.amalthea.model.Process;
+import org.eclipse.app4mc.amalthea.model.ProcessingUnit;
+import org.eclipse.app4mc.amalthea.model.Runnable;
+import org.eclipse.app4mc.amalthea.model.RunnableCall;
+import org.eclipse.app4mc.amalthea.model.Semaphore;
+import org.eclipse.app4mc.amalthea.model.SemaphoreAccess;
+import org.eclipse.app4mc.amalthea.model.SetEvent;
+import org.eclipse.app4mc.amalthea.model.Task;
+import org.eclipse.app4mc.amalthea.model.Ticks;
+import org.eclipse.app4mc.amalthea.model.Time;
+import org.eclipse.app4mc.amalthea.model.TimeUnit;
+import org.eclipse.app4mc.amalthea.model.util.FactoryUtil;
+import org.eclipse.app4mc.amalthea.model.util.HardwareUtil;
+import org.eclipse.app4mc.amalthea.model.util.RuntimeUtil;
+import org.eclipse.app4mc.amalthea.model.util.RuntimeUtil.TimeType;
+import org.eclipse.app4mc.amalthea.model.util.SoftwareUtil;
+import org.eclipse.emf.common.util.EList;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+public class Blocking {
+ Amalthea model;
+ private final int[] ia;
+ private final int[] flagArray;
+ private final HashMap<Task, List<Label>[]> gpuLabels = new HashMap<>();
+ int gpuIndexCnst = 6; // GPU index = 6
+ int shottingIndexCnst = 0; // shottingindex = 0
+ int shotIndexCnst = 1;
+ Logger log = LoggerFactory.getLogger(this.getClass());
+
+ public Blocking(final int[] iap, final Amalthea modelp) {
+ this.ia = iap;
+ this.model = modelp;
+ this.flagArray = new int[iap.length];
+ setUpFlagArrayAndHashMap(iap);
+
+ }
+
+ /**
+ * Initilization for labelList hashmap and flagArray for eliminate unused task
+ * when collecting
+ */
+ private void setUpFlagArrayAndHashMap(final int[] iap) {
+ final EList<Task> modelTask = this.model.getSwModel().getTasks();
+ /* get gpu task list via checking task with InterProcessStimulus */
+
+ final List<Task> gpuTask = modelTask.stream().filter(a -> a.getStimuli().get(0) instanceof InterProcessStimulus)
+ .collect(Collectors.toList());
+ /* get shotting task start */
+ for (final Task t : gpuTask) {
+ /* shotting task => t.getName */
+ final List<SetEvent> shottingTaskEvent = SoftwareUtil.collectSetEvents(t, null);
+ final Process shottingTask = shottingTaskEvent.get(0).getProcess();
+ final int shotIndex = this.model.getSwModel().getTasks().indexOf(shottingTask);
+ final int gpuIndex = this.model.getSwModel().getTasks().indexOf(t);
+ if (iap[gpuIndex] != gpuIndexCnst) {
+ /* If GPU is at GPU task then no flag */
+ this.flagArray[shotIndex] = shotIndexCnst;
+ }
+ /* create HashMap for GPU task that mapped to CPU start here */
+ final List<Label> readLabelList = new ArrayList<>();
+ final List<Label> writeLabelList = new ArrayList<>();
+ final List<InterProcessTrigger> callList = shottingTask.getActivityGraph().getItems().stream()
+ .filter(geb -> geb instanceof Group).map(g -> (Group) g).iterator().next().getItems().stream()
+ .filter(csi -> csi instanceof InterProcessTrigger).map(csi -> ((InterProcessTrigger) csi))
+ .collect(Collectors.toList());
+ /* SoftwareUtil.collectCalls(shottingTask) also possible */
+ final ActivityGraphItem ipt = callList.iterator().next();
+ /*
+ * get the position of InterProcessTrigger within task taking readLabel and
+ * write labels from pre and post processing ( preprocessing happen before
+ * trigger and post_processing happen after the trigger )
+ */
+
+ final int indexforTrigger = callList.indexOf(ipt);
+ for (int i = 0; i < callList.size(); i++) {
+ Runnable thisRunnable = null;
+ /* Pre-processing Runnable */
+ if ((i < indexforTrigger) && (callList.get(i) instanceof RunnableCall)) {
+ thisRunnable = ((RunnableCall) callList.get(i)).getRunnable();
+ final List<LabelAccess> thisLAList = SoftwareUtil.getLabelAccessList(thisRunnable, null);
+ for (final LabelAccess la : thisLAList) {
+ if (la.getAccess().equals(LabelAccessEnum.READ)) {
+ readLabelList.add(la.getData());
+ }
+ }
+ }
+ /* Post-processing Runnable */
+ else if ((i > indexforTrigger) && (callList.get(i) instanceof RunnableCall)) {
+ thisRunnable = ((RunnableCall) callList.get(i)).getRunnable();
+ final List<LabelAccess> thisLAList = SoftwareUtil.getLabelAccessList(thisRunnable, null);
+ for (final LabelAccess la : thisLAList) {
+ if (la.getAccess().equals(LabelAccessEnum.WRITE)) {
+ writeLabelList.add(la.getData());
+ }
+ }
+ }
+ }
+
+ final List<Label>[] aryofLabelList = new ArrayList[2];
+ aryofLabelList[0] = readLabelList;
+ aryofLabelList[1] = writeLabelList;
+
+ this.gpuLabels.put(t, aryofLabelList);
+ // HashMap created with <Task, ArrayofLabelList>
+ }
+ }
+
+ /**
+ * get a list of task that in the same core with thisTask
+ *
+ * @param thisTask
+ * @return List<Task>
+ */
+ private List<Task> groupTask(final Task thisTask) {
+ final List<Task> stepOneTaskList = new ArrayList<>();
+ final EList<Task> taskList = this.model.getSwModel().getTasks();
+ final int currentIndex = this.model.getSwModel().getTasks().indexOf(thisTask);
+ final int PUI = this.ia[currentIndex];
+ for (int i = 0; i < this.ia.length; i++) {
+ if (PUI == this.ia[i] && this.flagArray[i] == 0) {
+ stepOneTaskList.add(taskList.get(i));
+ }
+ }
+
+ return taskSorting(stepOneTaskList);
+ }
+
+ private List<Task> groupTaskFromOtherCore(final Task thisTask, int[] ia) {
+ final List<Task> sameCoreTaskList = new ArrayList<>();
+ final EList<Task> taskList = this.model.getSwModel().getTasks();
+ final int currentIndex = this.model.getSwModel().getTasks().indexOf(thisTask);
+ int[] thisIA = ia.clone();
+ final int PUI = thisIA[currentIndex];
+ // Add task in the same core with thisTask to a list (include thisTask)
+ for (int i = 0; i < ia.length; i++) {
+ if (PUI == thisIA[i]) {
+ sameCoreTaskList.add(taskList.get(i));
+ }
+ }
+
+ // loop all the task in model again and task that are not on sameCoreTaskList
+ // are task from different core
+ final List<Task> diffCoreTaskList = new ArrayList<>();
+ for (final Task currentTask : taskList) {
+ if (!sameCoreTaskList.contains(currentTask)) {
+ diffCoreTaskList.add(currentTask);
+ }
+ }
+ return diffCoreTaskList;
+ }
+
+ /**
+ * get a list of task that in the same core with thisTask
+ *
+ * @param thisTask
+ * @return List<Task>
+ */
+ private List<Task> groupTaskWithIA(final Task thisTask, int[] ia) {
+ final List<Task> stepOneTaskList = new ArrayList<>();
+ final EList<Task> taskList = this.model.getSwModel().getTasks();
+ final int currentIndex = this.model.getSwModel().getTasks().indexOf(thisTask);
+ int[] thisIA = ia.clone();
+
+ final int PUI = thisIA[currentIndex];
+ for (int i = 0; i < thisIA.length; i++) {
+ if (PUI == thisIA[i]) {
+ stepOneTaskList.add(taskList.get(i));
+ }
+ }
+ return taskSorting(stepOneTaskList);
+ }
+
+ /**
+ * @author JunHyungKi
+ * @param taskList
+ * @return sorted Task list based on RM
+ */
+ private List<Task> taskSorting(final List<Task> taskList) {
+ /* Getting stimuliList out of the given taskList (because it is RMS) */
+ final List<Time> stimuliList = new ArrayList<>();
+ for (final Task t : taskList) {
+ stimuliList.add(CommonUtils.getStimInTime(t));
+ }
+
+ /* Sorting (Shortest Period(Time) first) */
+ Collections.sort(stimuliList, new TimeCompIA());
+ /*
+ * Sort tasks to the newTaskList in order of Period length (shortest first
+ * longest last)-(according to the stimuliList)
+ */
+ final List<Task> newTaskList = new ArrayList<>();
+ for (int i = 0; i < stimuliList.size(); i++) {
+ for (final Task t : taskList) {
+ if ((!newTaskList.contains(t)) && (stimuliList.get(i).compareTo(CommonUtils.getStimInTime(t)) == 0)) {
+ newTaskList.add(t);
+ }
+ }
+ }
+ return newTaskList;
+ }
+
+ /**
+ * Sort a list of label by size
+ *
+ * @param labelList
+ * @return
+ */
+ private List<Label> labelSortingBySize(List<Label> labelList) {
+
+ // Sonarlint said replaced by lambdas to highly increase the readability of the
+ // source code, but joke on you, lamda look ugly and I don't understand it that
+ // well
+ Collections.sort(labelList, new Comparator<Label>() {
+ @Override
+ public int compare(Label label1, Label label2) {
+ long label1Size = label1.getSize().getNumberBits();
+ long label2Size = label2.getSize().getNumberBits();
+ if (label1Size > label2Size) {
+ return 1;
+ } else if (label1Size < label2Size) {
+ return -1;
+ }
+ return 0;
+ }
+ });
+
+ Collections.reverse(labelList);
+
+ return labelList;
+ }
+
+ /**
+ * @author Junhyung Ki this inner class is used for the method "taskSorting" to
+ * help compare between two tasks' periods (which is longer)
+ */
+ class TimeCompIA implements Comparator<Time> {
+ @Override
+ public int compare(final Time arg0, final Time arg1) {
+ if (arg0.compareTo(arg1) < 0) {
+ return -1;
+ }
+ return 1;
+ }
+ }
+
+ /**
+ * return a list of label that this task read and write (HashMap form) Hash =
+ * task, [readList,WriteList]
+ *
+ * @param thisTask
+ * @return Hash<Task, List<Label>[]>
+ * @return
+ */
+ private HashMap<Task, List<Label>[]> getReadWriteLabelHash(Task thisTask) {
+ List<Label> readLabelList = new ArrayList<>();
+ List<Label> writeLabelList = new ArrayList<>();
+ HashMap<Task, List<Label>[]> taskHask = new HashMap<>();
+
+ final List<Label>[] aryofLabelList = new ArrayList[2];
+
+ List<Runnable> runnableList = SoftwareUtil.getRunnableList(thisTask, null);
+ for (Runnable run : runnableList) {
+ Set<Label> readSet = SoftwareUtil.getReadLabelSet(run, null);
+ for (Label label : readSet) {
+ readLabelList.add(label);
+ }
+ Set<Label> writeSet = SoftwareUtil.getWriteLabelSet(run, null);
+ for (Label label : writeSet) {
+ writeLabelList.add(label);
+ }
+ }
+ aryofLabelList[0] = readLabelList;
+ aryofLabelList[1] = writeLabelList;
+ taskHask.put(thisTask, aryofLabelList);
+ return taskHask;
+ }
+
+ private List<Label> getAccessedLabelListWithDuplicate(Task thisTask) {
+ List<Label> labelList = new ArrayList<>();
+ List<Runnable> runnableList = SoftwareUtil.getRunnableList(thisTask, null);
+ for (Runnable run : runnableList) {
+ Set<Label> readSet = SoftwareUtil.getReadLabelSet(run, null);
+ for (Label label : readSet) {
+ labelList.add(label);
+ }
+ Set<Label> writeSet = SoftwareUtil.getWriteLabelSet(run, null);
+ for (Label label : writeSet) {
+ labelList.add(label);
+ }
+ }
+ return labelList;
+ }
+
+ /**
+ * Get whatever 2 list have in common, similar with list.retainAll().
+ *
+ * @param <Label>
+ * @param thisList
+ * @param thisSet
+ * @return
+ */
+ private List<Label> getDuplicateBetweenListAndSet(List<Label> thisList, Set<Label> thisSet) {
+ List<Label> newList = new ArrayList<>();
+ for (Label element : thisList) {
+ if (thisSet.contains(element)) {
+ newList.add(element);
+ }
+ }
+ return newList;
+ }
+
+ /**
+ * get a list of task that access the label
+ *
+ * @param thisLabel
+ * @param model
+ * @return
+ */
+ private List<Task> getLabelCalledTaskSet(Label thisLabel) {
+ List<Task> labelAccessTaskList = new ArrayList<>();
+ List<Runnable> labelReaderRun = SoftwareUtil.getReaderListOfLabel(thisLabel, null);
+ List<Runnable> labelWriteRun = SoftwareUtil.getWriterListOfLabel(thisLabel, null);
+ for (Runnable run : labelReaderRun) {
+ List<Process> readerTaskList = SoftwareUtil.getCallingProcesses(run, null);
+ for (Process process : readerTaskList) {
+ labelAccessTaskList.add((Task) process);
+ }
+ }
+ for (Runnable run : labelWriteRun) {
+ List<Process> writerTaskList = SoftwareUtil.getCallingProcesses(run, null);
+ for (Process process : writerTaskList) {
+ labelAccessTaskList.add((Task) process);
+ }
+ }
+
+ // remove duplicate and return
+ List<Task> returnTaskList = removeDuplicates(labelAccessTaskList);
+
+ return returnTaskList.stream().distinct().collect(Collectors.toList());
+ }
+
+ /**
+ * Get local label access by other local task.
+ *
+ * @param thisTask
+ * @param sameCoreTaskList
+ * @return
+ */
+ private Time getLocalCrossingLabelAccessTime(Task thisTask, List<Task> sameCoreTaskList) {
+ Time timeZero = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ // Modify sameCoreTaskList to lowerPriorityTaskList that contain only task that
+ // are lower priority than thisTask
+ int thisTaskIndex = sameCoreTaskList.indexOf(thisTask);
+
+ // if thisTask is lowest priority -> no need for local crossing
+ if (thisTaskIndex == (sameCoreTaskList.size() - 1)) {
+ log.debug("[{}] task have lowest priority -> return 0", thisTask.getName());
+ return timeZero;
+ }
+
+ List<Task> lowerPriorityTaskList = new ArrayList<>();
+ for (int i = thisTaskIndex + 1; i < sameCoreTaskList.size(); i++) {
+ Task lpTask = sameCoreTaskList.get(i);
+ lowerPriorityTaskList.add(lpTask);
+ }
+
+ // label list of this task (without duplicate)
+ Set<Label> thisTaskLabelListWithoutDuplicate = SoftwareUtil.getAccessedLabelSet(thisTask, null);
+
+ // If thisTask doesn't access any label, then no need to calculate label
+ // crossing
+ if (thisTaskLabelListWithoutDuplicate.isEmpty()) {
+ log.debug("[{}] task doesn't access any label -> return 0", thisTask.getName());
+ return timeZero;
+ }
+ // list of label of this task (with duplicate)
+ List<Label> thisTaskLabelListWithDuplicate = getAccessedLabelListWithDuplicate(thisTask);
+
+ // sort label by size
+
+ thisTaskLabelListWithDuplicate = labelSortingBySize(thisTaskLabelListWithDuplicate);
+ List<Task> potentialLowerPriorityTaskList = new ArrayList<>();
+ // Assign hashmap with <Label, accessedTask>
+ HashMap<Label, List<Task>> localLabelAccessTaskHash = new HashMap<>();
+ for (Label label : thisTaskLabelListWithoutDuplicate) {
+ List<Task> accessedTaskList = getLabelCalledTaskSet(label);
+ // Get task that : accessed the label & have lower priority
+ List<Task> lowerPriorityTaskWithLabelCrossing = new ArrayList<>(lowerPriorityTaskList);
+ lowerPriorityTaskWithLabelCrossing.retainAll(accessedTaskList);
+
+ // Add the lowerPriorityTaskWithLabelCrossing into Hashmap
+ localLabelAccessTaskHash.put(label, lowerPriorityTaskWithLabelCrossing);
+
+ // add lowerPriorityTaskWithLabelCrossing as potention blocking tassk to the
+ // list
+ potentialLowerPriorityTaskList.addAll(lowerPriorityTaskWithLabelCrossing);
+ }
+
+ // Remove duplicate from potentialLowerPriorityTaskList
+ potentialLowerPriorityTaskList = removeDuplicates(potentialLowerPriorityTaskList);
+
+ /**
+ * From this point, we should have something that can look like this
+ *
+ * A D A C A A A B B B A B C D C
+ * ------------------------------------------------------------------ [F] [B]
+ * [D] [E] [A] [C] [G] [H]
+ *
+ * For each task, after iterate the code above we should get - a list of label
+ * sorted by size (thisTaskLabelListWithDuplicate) - a Hash contain label name
+ * and lower priroity task accessed to it (localLabelAccessTaskHash) - a list of
+ * *potential* tasks is (lower priority) and (access the labels of thisTask)
+ * (potentialLowerPriorityTaskList) [*] is the label name, the alphabet [above
+ * the line] is task that access that [*] label. task A,B,C,D access some label
+ * of thisTask, thisTask have label [A,B,C,D,E,G,H] (missed the F here, meh)
+ * label are ordered by size biggest -> smallest (hence alphabet isn't in order)
+ *
+ */
+
+ Time localLabelAccessBlockingTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ // Check for task
+ int thisTaskLabelListWithDuplicateSize = thisTaskLabelListWithoutDuplicate.size();
+ log.debug("no of label: {} ----- no of potential task: {} ", thisTaskLabelListWithDuplicateSize,
+ potentialLowerPriorityTaskList.size());
+ for (Label label : thisTaskLabelListWithDuplicate) {
+
+ if (potentialLowerPriorityTaskList.isEmpty()) {
+ break;
+ }
+ int currentLabelIndex = thisTaskLabelListWithDuplicate.indexOf(label);
+
+ // Get the task list above the line for label
+ List<Task> accessTaskList = localLabelAccessTaskHash.get(label);
+ // only retain potentialTask here
+
+ // skip this label if it doesn't get accessed by other lp task
+ if (accessTaskList.isEmpty())
+ continue;
+
+ // Get total number of lp task access thisLabel
+ int numberOfAccessTasks = accessTaskList.size();
+
+ /*
+ * Check whether task B is access other label of thisTask (check until the
+ * upcoming label index = number of task) I.e there is 3 task A,B,C access label
+ * [F], hence we check 3 label include label [F] : [F] [B] [D] result return
+ * task B do exist in checked label [D], so [B] will have lower priority
+ */
+
+ // iterating index should not exceed labelListSize-1
+ int maxIteratingLabelIndex = numberOfAccessTasks + currentLabelIndex;
+ if (maxIteratingLabelIndex >= (thisTaskLabelListWithDuplicateSize - 1)) {
+ maxIteratingLabelIndex = (thisTaskLabelListWithDuplicateSize - 1);
+ }
+
+ List<Task> processTaskList = new ArrayList<>();
+ // Check whether task exist in other label or not
+ for (Task currentTask : accessTaskList) {
+ // iterate through other smaller label
+ for (int i = currentLabelIndex + 1; i < maxIteratingLabelIndex + 1; i++) {
+ Label currentLabel = thisTaskLabelListWithDuplicate.get(i);
+ // if other smaller label does get accessed by currentTask, then we put it in a
+ // list
+ if (localLabelAccessTaskHash.get(currentLabel).contains(currentTask)) {
+ processTaskList.add(currentTask);
+ }
+ }
+ }
+
+ /**
+ * choose which task should we assign for thisLabel We should have a list that
+ * contain tasks that are also access smaller laber behind The list may be empty
+ * tbh (processTaskList)
+ */
+
+ // exclude tasks from processTaskList (cuz they are available in other label)
+ List<Task> accessTaskListPhase2 = new ArrayList<>(accessTaskList);
+ accessTaskListPhase2.removeAll(processTaskList);
+
+ // This step here to prevent from removing all entry if 2 task access same label
+ // -> accessListPhase2 empty (not good)
+ //
+ if (accessTaskListPhase2.isEmpty()) {
+ accessTaskListPhase2.addAll(processTaskList);
+ }
+
+ // only take task from potentialTaskList
+ accessTaskListPhase2.retainAll(potentialLowerPriorityTaskList);
+
+ // Pick the task from accessTaskListPhase 2 for thisLabel.
+ if (!accessTaskListPhase2.isEmpty()) {
+ Task pickedTask = accessTaskListPhase2.get(0);
+ Time pickedLabelAccessTime = getLabelAccessTimeWithTask(pickedTask, label, TimeType.WCET);
+ localLabelAccessBlockingTime = localLabelAccessBlockingTime.add(pickedLabelAccessTime);
+ // remove theTask from potentialTaskList
+ potentialLowerPriorityTaskList.remove(pickedTask);
+ }
+ }
+
+ return localLabelAccessBlockingTime;
+
+ }
+
+ /**
+ * Get task's labels that are accessed by task from other core
+ *
+ * @param thisTask
+ * @param diffCoreTaskList
+ * @return
+ */
+ private Time getGlobalCrossingLabelsAccessTime(Task thisTask, List<Task> diffCoreTaskList) {
+
+ // set of label of this task
+ Set<Label> thisTaskLabelList = SoftwareUtil.getAccessedLabelSet(thisTask, null);
+
+ Time crossingAccessTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+
+ // If thisTask doesn't access any label, then no blocking.
+ if (thisTaskLabelList.isEmpty()) {
+ return crossingAccessTime;
+ }
+ // if there aren't any task on other core then yeah don't do anything either
+ // (rarely occur)
+ if (diffCoreTaskList.isEmpty()) {
+ return crossingAccessTime;
+ }
+
+ for (Task diffTask : diffCoreTaskList) {
+ // get all label access by diffTask
+ HashMap<Task, List<Label>[]> taskLabelHash = getReadWriteLabelHash(diffTask);
+ List<Label> readLabelList = taskLabelHash.get(diffTask)[0];
+ // duplicateReadLabelList = list of label that both thisTask(don't care
+ // read/write ) and diffTask accessed to (diffTask read the label)
+ List<Label> duplicateReadLabelList = getDuplicateBetweenListAndSet(readLabelList, thisTaskLabelList);
+ for (Label readLabel : duplicateReadLabelList) {
+ // get access time for diffTask to read the label
+ Time readLabelTime = getLabelAccessTime(diffTask, readLabel, LabelAccessEnum.READ, TimeType.WCET);
+ crossingAccessTime = crossingAccessTime.add(readLabelTime);
+ log.debug("{} accumulateCrossingTime - {} time for task [{}] to theReadLabel {} ", crossingAccessTime,
+ readLabelTime, diffTask.getName(), readLabel.getName());
+ }
+ List<Label> writeLabelList = taskLabelHash.get(diffTask)[1];
+ // duplicateWriteLabelList = list of label that both thisTask (don't care
+ // read/write) and diffTask accessed to (diffTask write the label)
+ List<Label> duplicateWriteLabelList = getDuplicateBetweenListAndSet(writeLabelList, thisTaskLabelList);
+ for (Label writeLabel : duplicateWriteLabelList) {
+ // get access time for diffTask to write the label
+ Time writeLabelTime = getLabelAccessTime(diffTask, writeLabel, LabelAccessEnum.WRITE, TimeType.WCET);
+ crossingAccessTime = crossingAccessTime.add(writeLabelTime);
+ log.debug("{} accumulateCrossingTime - {} time for task [{}] to theWriteLabel {} ", crossingAccessTime,
+ writeLabelTime, diffTask.getName(), writeLabel.getName());
+ }
+ }
+
+ log.debug("{} crossing access time for task [{}]", crossingAccessTime, thisTask.getName());
+
+ return crossingAccessTime;
+
+ }
+
+ /**
+ * Mainly use for localCrossingLabelAccessTime Check label access time for
+ * thisLabel with thisTask Automatically check whether it is read/write access
+ * from thisTask to thisLabel, take the longer one if both occured
+ *
+ * @param thisTask
+ * @param thisLabel
+ * @param executionCase
+ * @return
+ */
+ private Time getLabelAccessTimeWithTask(Task thisTask, final Label thisLabel, TimeType executionCase) {
+ Time timeZero = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+
+ // check whether thisLabel is access by thisTask or not, THIS MIGHT BE
+ // UNNECESSARY
+ List<Label> thisTaskLabelListWithDuplicate = getAccessedLabelListWithDuplicate(thisTask);
+ if (!thisTaskLabelListWithDuplicate.contains(thisLabel)) {
+ return timeZero;
+ }
+
+ Time labelReadTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ Time labelWriteTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+
+ boolean readAccess = false;
+ boolean writeAccess = false;
+ // Check whether thisTask read or write thisLabel
+ List<Runnable> runnableList = SoftwareUtil.getRunnableList(thisTask, null);
+ for (Runnable run : runnableList) {
+ Set<Label> readSet = SoftwareUtil.getReadLabelSet(run, null);
+ if (readSet.contains(thisLabel)) {
+ readAccess = true;
+ }
+ Set<Label> writeSet = SoftwareUtil.getWriteLabelSet(run, null);
+ if (writeSet.contains(thisLabel)) {
+ writeAccess = true;
+ }
+ }
+
+ // Set read/write time if thisTask actually read/write thisLabel
+ if (readAccess) {
+ labelReadTime = getLabelAccessTime(thisTask, thisLabel, LabelAccessEnum.READ, executionCase);
+ log.debug("task [{}] read label [{}], access time = {}", thisTask.getName(), thisLabel.getName(),
+ labelReadTime);
+ }
+ if (writeAccess) {
+ labelWriteTime = getLabelAccessTime(thisTask, thisLabel, LabelAccessEnum.WRITE, executionCase);
+ log.debug("task [{}] write label [{}], access time = {}", thisTask.getName(), thisLabel.getName(),
+ labelWriteTime);
+ }
+
+ // take the bigger one as return result.
+ if (labelWriteTime.compareTo(labelReadTime) >= 0) {
+ timeZero = labelWriteTime;
+ log.debug("{} - take write label access cuz it's bigger than or equal to read ", timeZero);
+ } else if (labelWriteTime.compareTo(labelReadTime) < 0) {
+ timeZero = labelReadTime;
+ log.debug("{} - take read label access cuz it's bigger than write", timeZero);
+ }
+ return timeZero;
+ }
+
+ /**
+ * calculate read/write label access of thisTask on thisLabel
+ *
+ * @param thisTask
+ * @param thisLabel
+ * @param thisType
+ * @param executionCase
+ * @return Time labelAccessTime
+ */
+
+ private Time getLabelAccessTime(final Task thisTask, final Label thisLabel, final LabelAccessEnum thisType,
+ final TimeType executionCase) {
+
+ final Time labelAccessTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ double readLatency = 1;
+ double writeLatency = 1;
+ final int currentIndex = this.model.getSwModel().getTasks().indexOf(thisTask);
+ final int PUI = this.ia[currentIndex];
+ final List<ProcessingUnit> pul = CommonUtils.getPUs(this.model);
+ final ProcessingUnit pu = pul.get(PUI);
+ if (executionCase.equals(TimeType.WCET)) {
+ readLatency = pu.getAccessElements().get(0).getReadLatency().getUpperBound();
+ writeLatency = pu.getAccessElements().get(0).getWriteLatency().getUpperBound();
+ } else if (executionCase.equals(TimeType.BCET)) {
+ readLatency = pu.getAccessElements().get(0).getReadLatency().getLowerBound();
+ writeLatency = pu.getAccessElements().get(0).getWriteLatency().getLowerBound();
+ } else {
+ readLatency = pu.getAccessElements().get(0).getReadLatency().getAverage();
+ writeLatency = pu.getAccessElements().get(0).getWriteLatency().getAverage();
+ }
+ final double freq_pu = HardwareUtil.getFrequencyOfModuleInHz(pu);
+ final long labelSize = thisLabel.getSize().getNumberBytes();
+ final double labelCycle = (long) Math.ceil(labelSize / 64.0);
+
+ BigDecimal freqPU = BigDecimal.valueOf(freq_pu);
+ BigDecimal memAccessBD = BigDecimal.ZERO;
+ if (thisType.equals(LabelAccessEnum.READ)) {
+ memAccessBD = BigDecimal.valueOf(labelCycle).multiply(BigDecimal.valueOf(readLatency)).divide(freqPU, 15,
+ RoundingMode.CEILING);
+ } else if (thisType.equals(LabelAccessEnum.WRITE)) {
+ memAccessBD = BigDecimal.valueOf(labelCycle).multiply(BigDecimal.valueOf(writeLatency)).divide(freqPU, 15,
+ RoundingMode.CEILING);
+
+ }
+ BigDecimal pico = BigDecimal.valueOf(1000000000000l);
+ memAccessBD = memAccessBD.multiply(pico);
+ labelAccessTime.setValue(memAccessBD.toBigInteger());
+ return labelAccessTime;
+ }
+
+ /**
+ * get a list of Semaphore that access by thisTask
+ *
+ * @param thisTask
+ * @return List<Semaphore>
+ */
+ public List<Semaphore> getSemaphore(final Task thisTask) {
+ List<Semaphore> semaList = new ArrayList<>();
+ final List<Runnable> runnableList = SoftwareUtil.getRunnableList(thisTask, null);
+ for (final Runnable chosenRun : runnableList) {
+ final EList<ActivityGraphItem> runItemList = chosenRun.getRunnableItems();
+ for (final ActivityGraphItem currentItem : runItemList) {
+ if (currentItem instanceof SemaphoreAccess) {
+ semaList.add(((SemaphoreAccess) currentItem).getSemaphore());
+ }
+ }
+ }
+ semaList = semaList.stream().distinct().collect(Collectors.toList());
+
+ return semaList;
+ }
+
+ /**
+ * get critical section length that guarded by Semaphore thisSema for thisTask
+ * Calculated by get labelAccess time + ticks (if avaiable) between request and
+ * release semaphore.
+ *
+ * @param thisTask
+ * @param thisSema
+ * @param executionCase
+ * @return Time criticalSectiontime
+ */
+ public Time getSemaphoreTime(final Task thisTask, final Semaphore thisSema, final TimeType executionCase) {
+ Time semaphoreTime;
+
+ final List<Runnable> runnableList = SoftwareUtil.getRunnableList(thisTask, null);
+ semaphoreTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ final int currentIndex = this.model.getSwModel().getTasks().indexOf(thisTask);
+ final int PUI = this.ia[currentIndex];
+ final List<ProcessingUnit> pul = CommonUtils.getPUs(this.model);
+ final ProcessingUnit pu = pul.get(PUI);
+ for (final Runnable chosenRun : runnableList) {
+ final EList<ActivityGraphItem> runItemList = chosenRun.getRunnableItems();
+ final ArrayList<Integer> seList = new ArrayList<>();
+ for (int i = 0; i < runItemList.size(); i++) {
+ final ActivityGraphItem currentItem = runItemList.get(i);
+ if (currentItem instanceof SemaphoreAccess
+ && ((SemaphoreAccess) currentItem).getSemaphore().equals(thisSema)) {
+ seList.add(i);
+ }
+ }
+ final ArrayList<Integer> itemIndexList = new ArrayList<>();
+ Boolean request = true;
+ if (!seList.isEmpty()) { // Stupid
+ for (int j = 0; j < Collections.max(seList) + 1; j++) {
+ if (seList.contains(j)) {
+ request = !request;
+ }
+ if (!seList.contains(j) && !request) {
+ itemIndexList.add(j);
+ }
+ }
+
+ for (final Integer i : itemIndexList) {
+ final ActivityGraphItem currentItem = runItemList.get(i);
+ if (currentItem instanceof LabelAccess
+ && (((LabelAccess) currentItem).getAccess().equals(LabelAccessEnum.READ))) {
+ final Label thisLabel = ((LabelAccess) currentItem).getData();
+ final Time labelTime = getLabelAccessTime(thisTask, thisLabel, LabelAccessEnum.READ,
+ executionCase);
+ semaphoreTime = semaphoreTime.add(labelTime);
+ } else if (currentItem instanceof LabelAccess
+ && (((LabelAccess) currentItem).getAccess().equals(LabelAccessEnum.WRITE))) {
+ final Label thisLabel = ((LabelAccess) currentItem).getData();
+ final Time labelTime = getLabelAccessTime(thisTask, thisLabel, LabelAccessEnum.WRITE,
+ executionCase);
+ semaphoreTime = semaphoreTime.add(labelTime);
+ }
+
+ else if (currentItem instanceof Ticks) {
+ final Ticks thisTick = ((Ticks) currentItem);
+ final Time tickTime = RuntimeUtil.getExecutionTimeForTicks(thisTick, pu, TimeType.WCET);
+ semaphoreTime = semaphoreTime.add(tickTime);
+ }
+ }
+ }
+ }
+ return semaphoreTime;
+ }
+
+ /**
+ * Get a list of task that have same semaphore(s) with thisTask
+ *
+ * @param thisTask
+ * @return
+ */
+ private List<Task> groupSemaphoreLinkedTask(final Task thisTask) {
+ final List<Task> groupTask = groupTask(thisTask);
+ List<Task> newTaskList = new ArrayList<>();
+ final List<Semaphore> semaList = getSemaphore(thisTask);
+ for (final Task t : groupTask) {
+ final List<Semaphore> otherSemaList = getSemaphore(t);
+ for (final Semaphore sema : otherSemaList) {
+ if (semaList.contains(sema)) {
+ newTaskList.add(t);
+ }
+ }
+ }
+
+ newTaskList = newTaskList.stream().distinct().collect(Collectors.toList());
+ return newTaskList;
+
+ }
+
+ /**
+ * max priority task blocking time will be equal the direct blocked Semaphore on
+ * lower priority task. Use this task for reference and testing
+ *
+ * @param thisTask
+ * @param executionCase
+ * @return
+ */
+ public Time maxPriorTaskBlockingTime(final Task thisTask, final TimeType executionCase) {
+ Time blockingTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ final List<Task> groupTask = groupSemaphoreLinkedTask(thisTask);
+ final List<Semaphore> semaList = getSemaphore(thisTask);
+ Time tempTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ if (!groupTask.isEmpty() && groupTask.get(0).equals(thisTask)) {
+ for (final Semaphore sema : semaList) {
+ for (int i = 1; i < groupTask.size(); i++) {
+ final Time currentTime = getSemaphoreTime(groupTask.get(i), sema, executionCase);
+ if (currentTime.compareTo(tempTime) > 0) {
+ tempTime = currentTime;
+ }
+ }
+ }
+ blockingTime = tempTime;
+
+ }
+ return blockingTime;
+ }
+
+ /**
+ * normal prior task PCP calculation, for reference and testing
+ *
+ * @param thisTask
+ * @param executionCase
+ * @return
+ */
+ public Time otherPriorTaskBlockingTime(final Task thisTask, final TimeType executionCase) {
+ Time blockingTime;
+ final List<Task> groupTask = groupSemaphoreLinkedTask(thisTask);
+ final List<Semaphore> semaList = getSemaphore(thisTask);
+ Time tempTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ final int currentIndex = groupTask.indexOf(thisTask);
+
+ for (final Semaphore sema : semaList) {
+ for (int i = currentIndex + 1; i < groupTask.size(); i++) {
+ final Time currentTime = getSemaphoreTime(groupTask.get(i), sema, executionCase);
+ if (currentTime.compareTo(tempTime) > 0) {
+ tempTime = currentTime;
+ }
+ }
+ }
+ blockingTime = tempTime;
+ return blockingTime;
+ }
+
+ /**
+ * task with lowest priority will have no blocking time This task is used for
+ * reference and testing
+ *
+ * @param thisTask
+ * @return time
+ */
+ public Time minPriorTaskBlockingTime(final Task thisTask) {
+ final Time blockingTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ final List<Task> groupTask = groupSemaphoreLinkedTask(thisTask);
+ final int currentIndex = groupTask.indexOf(thisTask) + 1;
+ if (groupTask.size() == currentIndex) {
+ return blockingTime;
+ }
+ return blockingTime;
+ }
+
+ /**
+ * calculate Local blocking time of task using Priority Ceiling Protocol No
+ * nested Semaphore.
+ *
+ * @param thisTask
+ * @param executionCase
+ * @return Time local blocking time
+ */
+ public Time getLocalBlockingTime(final Task thisTask, final TimeType executionCase) {
+ Time blockingTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ Time zeroTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ Time tempTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ List<Task> sameCoreTaskList = groupTaskWithIA(thisTask, this.ia);
+ final List<Semaphore> semaList = getSemaphore(thisTask);
+ final List<Task> groupTask = groupSemaphoreLinkedTask(thisTask);
+
+ final List<Task> bigGroup = groupTask(thisTask);
+ final int taskIndex = bigGroup.indexOf(thisTask);
+ if (taskIndex == 0) {
+ for (final Semaphore sema : semaList) {
+
+ for (int i = 1; i < groupTask.size(); i++) {
+
+ final Time currentTime = getSemaphoreTime(groupTask.get(i), sema, executionCase);
+ if (currentTime.compareTo(tempTime) > 0) {
+ tempTime = currentTime;
+ }
+ }
+ }
+ blockingTime = tempTime;
+
+ if (blockingTime.compareTo(zeroTime) == 0) {
+ blockingTime = getLocalCrossingLabelAccessTime(thisTask, sameCoreTaskList);
+ log.debug(
+ "There aren't local semaphore blocking time for this task [{}] - use crossing label time for local blocking",
+ thisTask.getName());
+ }
+ log.info("{} local blocking time for task [{}] \n", blockingTime, thisTask.getName());
+ return blockingTime;
+
+ }
+
+ else if (taskIndex + 1 == bigGroup.size()) {
+
+ if (blockingTime.compareTo(zeroTime) == 0) {
+ log.debug(
+ "There aren't local semaphore blocking time for this task [{}] - use crossing label time for local blocking",
+ thisTask.getName());
+ blockingTime = getLocalCrossingLabelAccessTime(thisTask, sameCoreTaskList);
+ }
+ log.info("{} local blocking time for task [{}] \n", blockingTime, thisTask.getName());
+ return blockingTime;
+ }
+
+ else {
+ blockingTime = normalTaskBlockingTime(thisTask, executionCase);
+ if (blockingTime.compareTo(zeroTime) == 0) {
+ log.debug(
+ "There aren't local semaphore blocking time for this task [{}] - use crossing label time for local blocking",
+ thisTask.getName());
+ blockingTime = getLocalCrossingLabelAccessTime(thisTask, sameCoreTaskList);
+ }
+ log.info("{} local blocking time for task [{}] \n", blockingTime, thisTask.getName());
+ return blockingTime;
+ }
+ }
+
+ /**
+ * Calculate normal prior task blocking time For reference and testing purpose
+ * only
+ *
+ * @param thisTask
+ * @param executionCase
+ * @return
+ */
+ private Time normalTaskBlockingTime(final Task thisTask, final TimeType executionCase) {
+ Time blockingTime;
+ Time tempTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ final List<Task> bigGroup = groupTask(thisTask);
+ List<Semaphore> fullSemaList = new ArrayList<>();
+ final List<Semaphore> semaList = getSemaphore(thisTask);
+ final List<Task> groupTask = groupSemaphoreLinkedTask(thisTask);
+
+ final int thisTaskIndex = bigGroup.indexOf(thisTask);
+
+ for (final Task task : bigGroup) {
+ final List<Semaphore> taskSemaList = getSemaphore(task);
+ fullSemaList.addAll(taskSemaList);
+ }
+
+ fullSemaList = fullSemaList.stream().distinct().collect(Collectors.toList());
+
+ for (final Semaphore sema : fullSemaList) {
+ for (int i = 0; i < thisTaskIndex; i++) {
+ final List<Task> linkedTask = groupSemaphoreLinkedTask(bigGroup.get(i));
+ final List<Semaphore> linkedSema = getSemaphore(bigGroup.get(i));
+ for (final Task task2 : linkedTask) {
+ for (final Semaphore linksema : linkedSema) {
+ if (bigGroup.indexOf(task2) > thisTaskIndex) {
+ final Time currentTime = getSemaphoreTime(task2, linksema, executionCase);
+ if (currentTime.compareTo(tempTime) > 0) {
+ tempTime = currentTime;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ for (final Semaphore sema : semaList) {
+ for (int i = thisTaskIndex + 1; i < groupTask.size(); i++) {
+ final Time currentTime = getSemaphoreTime(groupTask.get(i), sema, executionCase);
+
+ if (currentTime.compareTo(tempTime) > 0) {
+ tempTime = currentTime;
+ }
+
+ }
+ }
+ blockingTime = tempTime;
+ return blockingTime;
+ }
+
+ /**
+ * return list of tasks that are not in the same core with thisTask
+ *
+ * @param thisTask
+ * @return List<Task>
+ */
+
+ private List<Task> groupOtherTask(final Task thisTask) {
+ final List<Task> groupOtherTask = new ArrayList<>();
+ final List<Task> groupTask = groupTask(thisTask);
+ final EList<Task> listTask = this.model.getSwModel().getTasks();
+
+ for (final Task currentTask : listTask) {
+ final int currentIndex = listTask.indexOf(currentTask);
+ if (!groupTask.contains(currentTask) && this.flagArray[currentIndex] == shottingIndexCnst
+ && this.ia[currentIndex] != gpuIndexCnst) {
+ groupOtherTask.add(currentTask);
+ }
+ }
+ return groupOtherTask;
+ }
+
+ /**
+ * Calculate globalBlockingTime for task base on Semaphore. No nested Semaphore.
+ * Single FIFO ordered queue.
+ *
+ * @author The Bao Bui
+ * @param Task
+ * @param executionCase
+ * @return Time globalBlockingTime
+ */
+ public Time getGlobalBlockingTime(final Task thisTask, final TimeType executionCase) {
+ Time globalBlockingTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ final EList<Task> listTask = this.model.getSwModel().getTasks();
+ final List<Semaphore> thisTaskSemaList = getSemaphore(thisTask);
+ final List<Task> groupOtherTask = groupOtherTask(thisTask);
+ final Time tempTime = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
+ boolean logDebug = log.isDebugEnabled();
+ for (final Semaphore sema : thisTaskSemaList) {
+ if (logDebug) {
+ log.debug("Get coreSemaphoreTime");
+ }
+
+ final HashMap<Integer, Time> coreSemaphoreTime = new HashMap<>();
+ for (final Task otherTask : groupOtherTask) {
+ final int otherTaskIndex = listTask.indexOf(otherTask);
+ final int otherTaskPUIndex = this.ia[otherTaskIndex];
+ coreSemaphoreTime.put(otherTaskPUIndex, tempTime);
+ }
+
+ for (final Task otherTask : groupOtherTask) {
+ final int otherTaskIndex = listTask.indexOf(otherTask);
+ final int otherTaskPUIndex = this.ia[otherTaskIndex];
+
+ final Time otherSemaTime = getSemaphoreTime(otherTask, sema, executionCase);
+ if (coreSemaphoreTime.get(otherTaskPUIndex).compareTo(otherSemaTime) < 0) {
+ coreSemaphoreTime.put(otherTaskPUIndex, otherSemaTime);
+ }
+
+ }
+
+ for (final Time semaTime : coreSemaphoreTime.values()) {
+ if (logDebug) {
+ log.debug("semaphore Time = {} ps", semaTime);
+ }
+ globalBlockingTime = globalBlockingTime.add(semaTime);
+ if (logDebug) {
+ log.debug("accumulated semaphore time = {} ps", globalBlockingTime);
+ }
+
+ }
+
+ }
+
+ if (globalBlockingTime.getValue().compareTo(BigInteger.ZERO) <= 0) {
+ log.debug(
+ "There aren't global semaphore blocking time for this task [{}] - use crossing label time for global blocking",
+ thisTask.getName());
+ List<Task> diffCoreTaskList = groupTaskFromOtherCore(thisTask, this.ia);
+ Time crossingLabelAccessTime = getGlobalCrossingLabelsAccessTime(thisTask, diffCoreTaskList);
+ log.debug("crossing label access time = {} ps", crossingLabelAccessTime);
+ globalBlockingTime = globalBlockingTime.add(crossingLabelAccessTime);
+ }
+
+ if (log.isInfoEnabled()) {
+ log.info("{} = global blocking time for task [{}] \n", globalBlockingTime, thisTask.getName());
+
+ }
+
+ return globalBlockingTime;
+ }
+
+ public static <T> List<T> removeDuplicates(List<T> list) {
+
+ // Create a new LinkedHashSet
+ Set<T> set = new LinkedHashSet<>();
+
+ // Add the elements to set
+ set.addAll(list);
+
+ // Clear the list
+ list.clear();
+
+ // add the elements of set
+ // with no duplicates to the list
+ list.addAll(set);
+
+ // return the list
+ return list;
+ }
+
+}