1 /*******************************************************************************
2 * Copyright (c) 2013 École Polytechnique de Montréal
4 * All rights reserved. This program and the accompanying materials are made
5 * 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
10 * Geneviève Bastien - Initial implementation and API
11 *******************************************************************************/
13 package org
.eclipse
.linuxtools
.tmf
.core
.synchronization
;
15 import java
.io
.IOException
;
16 import java
.io
.ObjectOutputStream
;
17 import java
.io
.Serializable
;
18 import java
.math
.BigDecimal
;
19 import java
.math
.MathContext
;
20 import java
.util
.LinkedHashMap
;
21 import java
.util
.LinkedList
;
22 import java
.util
.List
;
25 import org
.eclipse
.linuxtools
.tmf
.core
.event
.ITmfEvent
;
26 import org
.eclipse
.linuxtools
.tmf
.core
.event
.matching
.TmfEventDependency
;
27 import org
.eclipse
.linuxtools
.tmf
.core
.timestamp
.ITmfTimestamp
;
28 import org
.eclipse
.linuxtools
.tmf
.core
.trace
.ITmfTrace
;
31 * Class implementing fully incremental trace synchronization approach as
34 * Masoume Jabbarifar, Michel Dagenais and Alireza Shameli-Sendi,
35 * "Streaming Mode Incremental Clock Synchronization"
37 * Since the algorithm itself applies to two traces, it is implemented in a
38 * private class, while this public class manages the synchronization between
41 * @author Geneviève Bastien
44 public class SyncAlgorithmFullyIncremental
extends SynchronizationAlgorithm
{
47 * Auto-generated serial UID
49 private static final long serialVersionUID
= -1782788842774838830L;
51 private static final MathContext fMc
= MathContext
.DECIMAL128
;
53 private final List
<ConvexHull
> fSyncs
;
56 * Initialization of the attributes
58 public SyncAlgorithmFullyIncremental() {
59 fSyncs
= new LinkedList
<ConvexHull
>();
63 * Function called after all matching has been done, to do any post-match
64 * treatment. For this class, it calculates stats, while the data is
68 public void matchingEnded() {
73 public void init(ITmfTrace
[] fTraces
) {
75 /* Create a convex hull for all trace pairs */
76 for (int i
= 0; i
< fTraces
.length
; i
++) {
77 for (int j
= i
+ 1; j
< fTraces
.length
; j
++) {
78 ConvexHull algo
= new ConvexHull(fTraces
[i
].getName(), fTraces
[j
].getName());
85 protected void processMatch(TmfEventDependency match
) {
86 String trace1
= match
.getSourceEvent().getTrace().getName();
87 String trace2
= match
.getDestinationEvent().getTrace().getName();
89 /* Process only if source and destination are different */
90 if (trace1
.equals(trace2
)) {
94 /* Check if a convex hull algorithm already exists for these 2 traces */
95 ConvexHull algo
= null;
96 for (ConvexHull traceSync
: fSyncs
) {
97 if (traceSync
.isForTraces(trace1
, trace2
)) {
102 algo
= new ConvexHull(trace1
, trace2
);
105 algo
.processMatch(match
);
110 public ITmfTimestampTransform
getTimestampTransform(ITmfTrace trace
) {
111 return getTimestampTransform(trace
.getName());
115 public ITmfTimestampTransform
getTimestampTransform(String name
) {
116 for (ConvexHull traceSync
: fSyncs
) {
117 if (traceSync
.isTraceSynced(name
)) {
119 * Since there are many traces, maybe the reference trace is
120 * also synchronized, so we need to chain sync formulas
122 ITmfTimestampTransform refTt
= getTimestampTransform(traceSync
.getReferenceTrace());
123 return refTt
.composeWith(traceSync
.getTimestampTransform(name
));
126 return TmfTimestampTransform
.IDENTITY
;
130 public SyncQuality
getSynchronizationQuality(ITmfTrace trace1
, ITmfTrace trace2
) {
131 for (ConvexHull traceSync
: fSyncs
) {
132 if (traceSync
.isForTraces(trace1
.getName(), trace2
.getName())) {
133 return traceSync
.getQuality();
136 return SyncQuality
.ABSENT
;
140 public boolean isTraceSynced(String name
) {
141 boolean traceSynced
= false;
142 for (ConvexHull traceSync
: fSyncs
) {
143 traceSynced
= traceSynced
|| traceSync
.isTraceSynced(name
);
149 * Rename one of the traces in the synchronization
152 * The name of the original trace
154 * The new name of the trace
157 public void renameTrace(String oldname
, String newname
) {
158 for (ConvexHull traceSync
: fSyncs
) {
159 traceSync
.renameTrace(oldname
, newname
);
164 public Map
<String
, Map
<String
, Object
>> getStats() {
165 Map
<String
, Map
<String
, Object
>> statmap
= new LinkedHashMap
<String
, Map
<String
, Object
>>();
166 for (ConvexHull traceSync
: fSyncs
) {
167 statmap
.put(traceSync
.getReferenceTrace() + " <==> " + traceSync
.getOtherTrace(), traceSync
.getStats()); //$NON-NLS-1$
173 public String
toString() {
174 StringBuilder b
= new StringBuilder();
175 b
.append(getClass().getSimpleName() + " "); //$NON-NLS-1$
181 * This is the actual synchronization algorithm between two traces using
184 private class ConvexHull
implements Serializable
{
186 private static final long serialVersionUID
= 8309351175030935291L;
189 * The list of meaningful points on the upper hull (received by the
190 * reference trace, below in a graph)
192 private final LinkedList
<SyncPoint
> fUpperBoundList
= new LinkedList
<SyncPoint
>();
195 * The list of meaninful points on the lower hull (sent by the reference
196 * trace, above in a graph)
198 private final LinkedList
<SyncPoint
> fLowerBoundList
= new LinkedList
<SyncPoint
>();
200 /** Points forming the line with maximum slope */
201 private final SyncPoint
[] fLmax
;
203 /** Points forming the line with minimum slope */
204 private final SyncPoint
[] fLmin
;
207 * Slopes and ordinate at origin of respectively fLmin, fLmax and the
210 private BigDecimal fAlphamin
, fBetamax
, fAlphamax
, fBetamin
, fAlpha
, fBeta
;
212 private int fNbMatches
, fNbAccurateMatches
;
213 private String fReferenceTrace
= "", fOtherTrace
= ""; //$NON-NLS-1$//$NON-NLS-2$
214 private SyncQuality fQuality
;
216 private Map
<String
, Object
> fStats
= new LinkedHashMap
<String
, Object
>();
219 * Initialization of the attributes
222 * Name of the first trace
224 * Name of the second trace
226 public ConvexHull(String trace1
, String trace2
) {
227 if (trace1
.compareTo(trace2
) > 0) {
228 fReferenceTrace
= trace2
;
229 fOtherTrace
= trace1
;
231 fReferenceTrace
= trace1
;
232 fOtherTrace
= trace2
;
234 fLmax
= new SyncPoint
[2];
235 fLmin
= new SyncPoint
[2];
236 fAlpha
= BigDecimal
.ONE
;
237 fAlphamax
= BigDecimal
.ONE
;
238 fAlphamin
= BigDecimal
.ONE
;
239 fBeta
= BigDecimal
.ZERO
;
240 fBetamax
= BigDecimal
.ZERO
;
241 fBetamin
= BigDecimal
.ZERO
;
243 fNbAccurateMatches
= 0;
244 fQuality
= SyncQuality
.ABSENT
;
247 protected void processMatch(TmfEventDependency match
) {
249 LinkedList
<SyncPoint
> boundList
, otherBoundList
;
251 SyncPoint
[] line
, otherLine
;
253 int inversionFactor
= 1;
254 boolean qualify
= false;
257 /* Initialize data depending on the which hull the match is part of */
258 if (match
.getSourceEvent().getTrace().getName().compareTo(match
.getDestinationEvent().getTrace().getName()) > 0) {
259 boundList
= fUpperBoundList
;
260 otherBoundList
= fLowerBoundList
;
263 p
= new SyncPoint(match
.getDestinationEvent(), match
.getSourceEvent());
266 boundList
= fLowerBoundList
;
267 otherBoundList
= fUpperBoundList
;
270 p
= new SyncPoint(match
.getSourceEvent(), match
.getDestinationEvent());
271 inversionFactor
= -1;
275 * Does the message qualify for the hull, or is in on the wrong side
276 * of the reference line
278 if ((line
[0] == null) || (line
[1] == null) || (p
.crossProduct(line
[0], line
[1]) * inversionFactor
> 0)) {
280 * If message qualifies, verify if points need to be removed
281 * from the hull and add the new point as the maximum reference
282 * point for the line. Also clear the stats that are not good
285 fNbAccurateMatches
++;
287 removeUselessPoints(p
, boundList
, inversionFactor
);
293 * Adjust the boundary of the reference line and if one of the
294 * reference point of the other line was removed from the hull, also
295 * adjust the other line
297 adjustBound(line
, otherBoundList
, inversionFactor
);
298 if ((otherLine
[1] != null) && !boundList
.contains(otherLine
[0])) {
299 adjustBound(otherLine
, boundList
, inversionFactor
* -1);
309 * Calculates slopes and ordinate at origin of fLmax and fLmin to obtain
310 * and approximation of the synchronization at this time
312 private void approximateSync() {
314 * Line slopes functions
316 * Lmax = alpha_max T + beta_min
318 * Lmin = alpha_min T + beta_max
320 if ((fLmax
[0] != null) || (fLmin
[0] != null)) {
321 fAlphamax
= fLmax
[1].getAlpha(fLmax
[0]);
322 fBetamin
= fLmax
[1].getBeta(fAlphamax
);
323 fAlphamin
= fLmin
[1].getAlpha(fLmin
[0]);
324 fBetamax
= fLmin
[1].getBeta(fAlphamin
);
325 fAlpha
= fAlphamax
.add(fAlphamin
).divide(BigDecimal
.valueOf(2), fMc
);
326 fBeta
= fBetamin
.add(fBetamax
).divide(BigDecimal
.valueOf(2), fMc
);
327 if ((fLmax
[0] == null) || (fLmin
[0] == null)) {
328 fQuality
= SyncQuality
.APPROXIMATE
;
330 else if (fAlphamax
.compareTo(fAlphamin
) > 0) {
331 fQuality
= SyncQuality
.ACCURATE
;
333 /* Lines intersect, not good */
334 fQuality
= SyncQuality
.FAIL
;
336 } else if (((fLmax
[0] == null) && (fLmin
[1] == null))
337 || ((fLmax
[1] == null) && (fLmin
[0] == null))) {
338 /* Either there is no upper hull point or no lower hull */
339 fQuality
= SyncQuality
.INCOMPLETE
;
344 * Verify if the line should be adjusted to be more accurate give the
347 private void adjustBound(SyncPoint
[] line
, LinkedList
<SyncPoint
> otherBoundList
, int inversionFactor
) {
348 SyncPoint minPoint
= null, nextPoint
;
349 boolean finishedSearch
= false;
352 * Find in the other bound, the origin point of the line, start from
353 * the beginning if the point was lost
355 int i
= Math
.max(0, otherBoundList
.indexOf(line
[0]));
357 while ((i
< otherBoundList
.size() - 1) && !finishedSearch
) {
358 minPoint
= otherBoundList
.get(i
);
359 nextPoint
= otherBoundList
.get(i
+ 1);
362 * If the rotation (cross-product) is not optimal, move to next
363 * point as reference for the line (if available)
365 * Otherwise, the current minPoint is the minPoint of the line
367 if (minPoint
.crossProduct(nextPoint
, line
[1]) * inversionFactor
> 0) {
368 if (nextPoint
.getTimeX() < line
[1].getTimeX()) {
372 finishedSearch
= true;
376 finishedSearch
= true;
380 if (line
[0] == null) {
384 /* Make sure point 0 is before point 1 */
385 if ((line
[0] != null) && (line
[0].getTimeX() > line
[1].getTimeX())) {
391 * When a point qualifies to be in a hull, we verify if any of the
392 * existing points need to be removed from the hull
394 private void removeUselessPoints(final SyncPoint p
, final LinkedList
<SyncPoint
> boundList
, final int inversionFactor
) {
396 boolean checkRemove
= true;
398 while (checkRemove
&& boundList
.size() >= 2) {
399 if (p
.crossProduct(boundList
.get(boundList
.size() - 2), boundList
.getLast()) * inversionFactor
> 0) {
400 boundList
.removeLast();
405 boundList
.addLast(p
);
408 public ITmfTimestampTransform
getTimestampTransform(String name
) {
409 if (name
.equals(fOtherTrace
) && (fQuality
== SyncQuality
.ACCURATE
|| fQuality
== SyncQuality
.APPROXIMATE
|| fQuality
== SyncQuality
.FAIL
)) {
410 /* alpha: beta => 1 / fAlpha, -1 * fBeta / fAlpha); */
411 return new TmfTimestampTransformLinear(BigDecimal
.ONE
.divide(fAlpha
, fMc
), BigDecimal
.valueOf(-1).multiply(fBeta
).divide(fAlpha
, fMc
));
413 return TmfTimestampTransform
.IDENTITY
;
416 public SyncQuality
getQuality() {
420 public Map
<String
, Object
> getStats() {
421 if (fStats
.size() == 0) {
425 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_absent
;
428 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_accurate
;
431 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_approx
;
434 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_incomplete
;
438 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_fail
;
442 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_reftrace
, fReferenceTrace
);
443 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_othertrace
, fOtherTrace
);
444 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_quality
, syncQuality
);
445 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_alpha
, fAlpha
);
446 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_beta
, fBeta
);
447 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_ub
, (fUpperBoundList
.size() == 0) ? Messages
.SyncAlgorithmFullyIncremental_NA
: fUpperBoundList
.size());
448 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_lb
, (fLowerBoundList
.size() == 0) ? Messages
.SyncAlgorithmFullyIncremental_NA
: fLowerBoundList
.size());
449 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_accuracy
, fAlphamax
.subtract(fAlphamin
).doubleValue()); // -
451 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_nbmatch
, (fNbMatches
== 0) ? Messages
.SyncAlgorithmFullyIncremental_NA
: fNbMatches
);
452 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_nbacc
, (fNbAccurateMatches
== 0) ? Messages
.SyncAlgorithmFullyIncremental_NA
: fNbAccurateMatches
);
453 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_refformula
, Messages
.SyncAlgorithmFullyIncremental_T_
+ fReferenceTrace
);
454 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_otherformula
, fAlpha
+ Messages
.SyncAlgorithmFullyIncremental_mult
+ Messages
.SyncAlgorithmFullyIncremental_T_
+ fReferenceTrace
+ Messages
.SyncAlgorithmFullyIncremental_add
+ fBeta
);
460 public String
getReferenceTrace() {
461 return fReferenceTrace
;
464 public String
getOtherTrace() {
468 public boolean isTraceSynced(String name
) {
469 /* Returns true if the timestamp transform is not identity */
470 return (name
.equals(fOtherTrace
) && (fQuality
== SyncQuality
.ACCURATE
|| fQuality
== SyncQuality
.APPROXIMATE
|| fQuality
== SyncQuality
.FAIL
));
473 public boolean isForTraces(String trace1
, String trace2
) {
474 return ((fReferenceTrace
.equals(trace1
) && fOtherTrace
.equals(trace2
)) || (fReferenceTrace
.equals(trace2
) && fOtherTrace
.equals(trace1
)));
477 public void renameTrace(String oldname
, String newname
) {
478 if (oldname
.equals(fOtherTrace
)) {
479 fOtherTrace
= newname
;
480 } else if (oldname
.equals(fReferenceTrace
)) {
481 fReferenceTrace
= newname
;
485 private void writeObject(ObjectOutputStream s
)
488 * Remove calculation data because most of it is not serializable.
489 * We have the statistics anyway
491 fUpperBoundList
.clear();
492 fLowerBoundList
.clear();
497 s
.defaultWriteObject();
501 @SuppressWarnings("nls")
503 public String
toString() {
504 StringBuilder b
= new StringBuilder();
505 b
.append("Between " + fReferenceTrace
+ " and " + fOtherTrace
+ " [");
506 b
.append(" alpha " + fAlpha
+ " beta " + fBeta
+ " ]");
512 * Private class representing a point to synchronize on a graph. The x axis
513 * is the timestamp of the event from the reference trace while the y axis
514 * is the timestamp of the event on the other trace
516 private class SyncPoint
{
517 private final ITmfTimestamp x
, y
;
519 public SyncPoint(ITmfEvent ex
, ITmfEvent ey
) {
520 x
= ex
.getTimestamp();
521 y
= ey
.getTimestamp();
524 public long getTimeX() {
529 * Calculate a cross product of 3 points:
531 * If the cross-product < 0, then p, pa, pb are clockwise
533 * If the cross-product > 0, then p, pa, pb are counter-clockwise
535 * If cross-product == 0, then they are in a line
541 * @return The cross product
543 public long crossProduct(SyncPoint pa
, SyncPoint pb
) {
544 long cp
= ((pa
.x
.getValue() - x
.getValue()) * (pb
.y
.getValue() - y
.getValue()) - (pa
.y
.getValue() - y
.getValue()) * (pb
.x
.getValue() - x
.getValue()));
549 * Gets the alpha (slope) between two points
551 public BigDecimal
getAlpha(SyncPoint p1
) {
553 return BigDecimal
.ONE
;
555 BigDecimal deltay
= BigDecimal
.valueOf(y
.getValue() - p1
.y
.getValue());
556 BigDecimal deltax
= BigDecimal
.valueOf(x
.getValue() - p1
.x
.getValue());
557 if (deltax
.equals(BigDecimal
.ZERO
)) {
558 return BigDecimal
.ONE
;
560 return deltay
.divide(deltax
, fMc
);
564 * Get the beta value (when x = 0) of the line given alpha
566 public BigDecimal
getBeta(BigDecimal alpha
) {
567 return BigDecimal
.valueOf(y
.getValue()).subtract(alpha
.multiply(BigDecimal
.valueOf(x
.getValue()), fMc
));