1 /*******************************************************************************
2 * Copyright (c) 2015 École Polytechnique de Montréal
4 * All rights reserved. This program and the accompanying materials are
5 * made available under the terms of the Eclipse Public License v1.0 which
6 * accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
8 *******************************************************************************/
10 package org
.eclipse
.tracecompass
.internal
.analysis
.graph
.core
.criticalpath
;
12 import static org
.eclipse
.tracecompass
.common
.core
.NonNullUtils
.checkNotNull
;
14 import java
.util
.Collections
;
15 import java
.util
.LinkedList
;
16 import java
.util
.List
;
17 import java
.util
.Stack
;
19 import org
.eclipse
.jdt
.annotation
.Nullable
;
20 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.IGraphWorker
;
21 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfEdge
;
22 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfGraph
;
23 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfVertex
;
24 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfVertex
.EdgeDirection
;
25 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.criticalpath
.CriticalPathAlgorithmException
;
28 * Critical path bounded algorithm: backward resolution of blocking limited to
31 * This algorithm is described in
33 * F. Giraldeau and M.Dagenais, Wait analysis of distributed systems using
34 * kernel tracing, IEEE Transactions on Parallel and Distributed Systems
36 * @author Francis Giraldeau
38 public class CriticalPathAlgorithmBounded
extends AbstractCriticalPathAlgorithm
{
44 * The graph on which to calculate the critical path
46 public CriticalPathAlgorithmBounded(TmfGraph graph
) {
51 public TmfGraph
compute(TmfVertex start
, @Nullable TmfVertex end
) throws CriticalPathAlgorithmException
{
52 /* Create new graph for the critical path result */
53 TmfGraph criticalPath
= new TmfGraph();
55 /* Get the main graph from which to get critical path */
56 TmfGraph graph
= getGraph();
59 * Calculate path starting from the object the start vertex belongs to
61 IGraphWorker parent
= checkNotNull(graph
.getParentOf(start
));
62 criticalPath
.add(parent
, new TmfVertex(start
));
63 TmfVertex currentVertex
= start
;
64 TmfEdge nextEdge
= currentVertex
.getEdge(EdgeDirection
.OUTGOING_HORIZONTAL_EDGE
);
66 long endTime
= Long
.MAX_VALUE
;
68 endTime
= end
.getTs();
72 * Run through all horizontal edges from this object and resolve each
73 * blocking as they come
75 while (nextEdge
!= null) {
76 TmfVertex nextVertex
= nextEdge
.getVertexTo();
77 if (nextVertex
.getTs() >= endTime
) {
80 switch (nextEdge
.getType()) {
89 * This edge is not blocked, so nothing to resolve, just add the
90 * edge to the critical path
93 * TODO: Normally, the parent of the link's vertex to should be
94 * the object itself, verify if that is true
96 IGraphWorker parentTo
= checkNotNull(graph
.getParentOf(nextEdge
.getVertexTo()));
97 if (parentTo
!= parent
) {
98 throw new CriticalPathAlgorithmException("no, the parents of horizontal edges are not always identical... shouldn't they be?"); //$NON-NLS-1$
100 criticalPath
.append(parentTo
, new TmfVertex(nextEdge
.getVertexTo()), nextEdge
.getType());
104 List
<TmfEdge
> links
= resolveBlockingBounded(nextEdge
, nextEdge
.getVertexFrom());
105 Collections
.reverse(links
);
106 appendPathComponent(criticalPath
, graph
, currentVertex
, links
);
109 if (nextEdge
.getDuration() != 0) {
110 throw new CriticalPathAlgorithmException("epsilon duration is not zero " + nextEdge
); //$NON-NLS-1$
114 throw new CriticalPathAlgorithmException("Illegal link type " + nextEdge
.getType()); //$NON-NLS-1$
119 currentVertex
= nextVertex
;
120 nextEdge
= currentVertex
.getEdge(EdgeDirection
.OUTGOING_HORIZONTAL_EDGE
);
125 /** Add the links to the critical path, with currentVertex to glue to */
126 private void appendPathComponent(TmfGraph criticalPath
, TmfGraph graph
, TmfVertex currentVertex
, List
<TmfEdge
> links
) {
127 IGraphWorker currentActor
= checkNotNull(graph
.getParentOf(currentVertex
));
128 if (links
.isEmpty()) {
130 * The next vertex should not be null, since we glue only after
131 * resolve of the blocking of the edge to that vertex
133 TmfEdge next
= currentVertex
.getEdge(EdgeDirection
.OUTGOING_HORIZONTAL_EDGE
);
137 criticalPath
.append(currentActor
, new TmfVertex(next
.getVertexTo()), next
.getType());
140 // FIXME: assert last link.to actor == currentActor
142 // attach subpath to b1
143 TmfVertex b1
= checkNotNull(criticalPath
.getTail(currentActor
));
146 TmfEdge lnk
= links
.get(0);
147 TmfVertex anchor
= null;
148 IGraphWorker objSrc
= checkNotNull(graph
.getParentOf(lnk
.getVertexFrom()));
149 if (objSrc
.equals( currentActor
)) {
152 anchor
= new TmfVertex(currentVertex
);
153 criticalPath
.add(objSrc
, anchor
);
154 b1
.linkVertical(anchor
);
155 /* fill any gap with UNKNOWN */
156 if (lnk
.getVertexFrom().compareTo(anchor
) > 0) {
157 anchor
= new TmfVertex(lnk
.getVertexFrom());
158 TmfEdge edge
= checkNotNull(criticalPath
.append(objSrc
, anchor
));
159 edge
.setType(TmfEdge
.EdgeType
.UNKNOWN
);
165 for (TmfEdge link
: links
) {
166 // check connectivity
167 if (prev
!= null && prev
.getVertexTo() != link
.getVertexFrom()) {
168 anchor
= copyLink(criticalPath
, graph
, anchor
, prev
.getVertexTo(), link
.getVertexFrom(),
169 prev
.getVertexTo().getTs(), TmfEdge
.EdgeType
.DEFAULT
);
171 anchor
= copyLink(criticalPath
, graph
, anchor
, link
.getVertexFrom(), link
.getVertexTo(),
172 link
.getVertexTo().getTs(), link
.getType());
178 * Resolve a blocking by going through the graph vertically from the
181 * FIXME: build a tree with partial subpath in order to return the best
182 * path, not the last one traversed
187 * The vertex that limits the boundary until which to resolve the
189 * @return The list of non-blocking edges
191 private List
<TmfEdge
> resolveBlockingBounded(TmfEdge blocking
, TmfVertex bound
) {
193 LinkedList
<TmfEdge
> subPath
= new LinkedList
<>();
194 TmfVertex junction
= findIncoming(blocking
.getVertexTo(), EdgeDirection
.OUTGOING_HORIZONTAL_EDGE
);
195 /* if wake-up source is not found, return empty list */
196 if (junction
== null) {
200 TmfEdge down
= checkNotNull(junction
.getEdge(EdgeDirection
.INCOMING_VERTICAL_EDGE
));
202 TmfVertex vertexFrom
= down
.getVertexFrom();
204 TmfVertex currentBound
= bound
.compareTo(blocking
.getVertexFrom()) < 0 ? blocking
.getVertexFrom() : bound
;
206 Stack
<TmfVertex
> stack
= new Stack
<>();
207 while (vertexFrom
!= null && vertexFrom
.compareTo(currentBound
) > 0) {
208 /* shortcut for down link that goes beyond the blocking */
209 TmfEdge inVerticalEdge
= vertexFrom
.getEdge(EdgeDirection
.INCOMING_VERTICAL_EDGE
);
210 if (inVerticalEdge
!= null && inVerticalEdge
.getVertexFrom().compareTo(currentBound
) <= 0) {
211 subPath
.add(inVerticalEdge
);
216 * Add DOWN links to explore stack in case dead-end occurs. Here is
217 * an example to illustrate the procedure.
220 * -------------------------
222 * -------------------------
226 * +--------------------+
227 * +-------+ INTERRUPT +--------+
228 * +--------------------+
235 * The event wake-up is followed backward. The edge 4 will never be
236 * visited (it cannot be the cause of the wake-up, because it occurs
237 * after it). The edge 3 will not be explored, because it is
238 * outgoing. The edges 2 and 1 will be pushed on the stack. When the
239 * beginning of the interrupt is reached, then the edges on the
240 * stack will be explored.
242 * If a dead-end is reached, while the stack is not empty, the
243 * accumulated path is rewinded, and a different incoming edge is
244 * tried. The backward traversal ends if there is nothing left to
245 * explore, or if the start of the blocking window start is reached.
247 * Do not add if left is BLOCKED, because this link would be visited
250 TmfEdge incomingEdge
= vertexFrom
.getEdge(EdgeDirection
.INCOMING_HORIZONTAL_EDGE
);
251 if (inVerticalEdge
!= null &&
252 (incomingEdge
== null ||
253 incomingEdge
.getType() != TmfEdge
.EdgeType
.BLOCKED
||
254 incomingEdge
.getType() != TmfEdge
.EdgeType
.NETWORK
)) {
255 stack
.push(vertexFrom
);
257 if (incomingEdge
!= null) {
258 if (incomingEdge
.getType() == TmfEdge
.EdgeType
.BLOCKED
|| incomingEdge
.getType() == TmfEdge
.EdgeType
.NETWORK
) {
259 subPath
.addAll(resolveBlockingBounded(incomingEdge
, currentBound
));
261 subPath
.add(incomingEdge
);
263 vertexFrom
= incomingEdge
.getVertexFrom();
265 if (!stack
.isEmpty()) {
266 TmfVertex v
= stack
.pop();
268 while (!subPath
.isEmpty() && subPath
.getLast().getVertexFrom() != v
) {
269 subPath
.removeLast();
271 TmfEdge edge
= v
.getEdge(EdgeDirection
.INCOMING_VERTICAL_EDGE
);
274 vertexFrom
= edge
.getVertexFrom();