org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/synchronization/SyncAlgorithmFullyIncremental.java

   1 /*******************************************************************************
   2  * Copyright (c) 2013 École Polytechnique de Montréal
   3  *
   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
   8  *
   9  * Contributors:
  10  *   Geneviève Bastien - Initial implementation and API
  11  *******************************************************************************/
  12
  13 package org.eclipse.linuxtools.tmf.core.synchronization;
  14
  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;
  23 import java.util.Map;
  24
  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;
  29
  30 /**
  31  * Class implementing fully incremental trace synchronization approach as
  32  * described in
  33  *
  34  * Masoume Jabbarifar, Michel Dagenais and Alireza Shameli-Sendi,
  35  * "Streaming Mode Incremental Clock Synchronization"
  36  *
  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
  39  * all traces.
  40  *
  41  * @author Geneviève Bastien
  42  * @since 3.0
  43  */
  44 public class SyncAlgorithmFullyIncremental extends SynchronizationAlgorithm {
  45
  46     /**
  47      * Auto-generated serial UID
  48      */
  49     private static final long serialVersionUID = -1782788842774838830L;
  50
  51     private static final MathContext fMc = MathContext.DECIMAL128;
  52
  53     private final List<ConvexHull> fSyncs;
  54
  55     /**
  56      * Initialization of the attributes
  57      */
  58     public SyncAlgorithmFullyIncremental() {
  59         fSyncs = new LinkedList<ConvexHull>();
  60     }
  61
  62     /**
  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
  65      * available
  66      */
  67     @Override
  68     public void matchingEnded() {
  69         getStats();
  70     }
  71
  72     @Override
  73     public void init(ITmfTrace[] fTraces) {
  74         fSyncs.clear();
  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());
  79                 fSyncs.add(algo);
  80             }
  81         }
  82     }
  83
  84     @Override
  85     protected void processMatch(TmfEventDependency match) {
  86         String trace1 = match.getSourceEvent().getTrace().getName();
  87         String trace2 = match.getDestinationEvent().getTrace().getName();
  88
  89         /* Process only if source and destination are different */
  90         if (trace1.equals(trace2)) {
  91             return;
  92         }
  93
  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)) {
  98                 algo = traceSync;
  99             }
 100         }
 101         if (algo == null) {
 102             algo = new ConvexHull(trace1, trace2);
 103             fSyncs.add(algo);
 104         }
 105         algo.processMatch(match);
 106
 107     }
 108
 109     @Override
 110     public ITmfTimestampTransform getTimestampTransform(ITmfTrace trace) {
 111         return getTimestampTransform(trace.getName());
 112     }
 113
 114     @Override
 115     public ITmfTimestampTransform getTimestampTransform(String name) {
 116         for (ConvexHull traceSync : fSyncs) {
 117             if (traceSync.isTraceSynced(name)) {
 118                 /*
 119                  * Since there are many traces, maybe the reference trace is
 120                  * also synchronized, so we need to chain sync formulas
 121                  */
 122                 ITmfTimestampTransform refTt = getTimestampTransform(traceSync.getReferenceTrace());
 123                 return refTt.composeWith(traceSync.getTimestampTransform(name));
 124             }
 125         }
 126         return TmfTimestampTransform.IDENTITY;
 127     }
 128
 129     @Override
 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();
 134             }
 135         }
 136         return SyncQuality.ABSENT;
 137     }
 138
 139     @Override
 140     public boolean isTraceSynced(String name) {
 141         boolean traceSynced = false;
 142         for (ConvexHull traceSync : fSyncs) {
 143             traceSynced = traceSynced || traceSync.isTraceSynced(name);
 144         }
 145         return traceSynced;
 146     }
 147
 148     /**
 149      * Rename one of the traces in the synchronization
 150      *
 151      * @param oldname
 152      *            The name of the original trace
 153      * @param newname
 154      *            The new name of the trace
 155      */
 156     @Override
 157     public void renameTrace(String oldname, String newname) {
 158         for (ConvexHull traceSync : fSyncs) {
 159             traceSync.renameTrace(oldname, newname);
 160         }
 161     }
 162
 163     @Override
 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$
 168         }
 169         return statmap;
 170     }
 171
 172     @Override
 173     public String toString() {
 174         StringBuilder b = new StringBuilder();
 175         b.append(getClass().getSimpleName() + " "); //$NON-NLS-1$
 176         b.append(fSyncs);
 177         return b.toString();
 178     }
 179
 180     /**
 181      * This is the actual synchronization algorithm between two traces using
 182      * convex hull
 183      */
 184     private class ConvexHull implements Serializable {
 185
 186         private static final long serialVersionUID = 8309351175030935291L;
 187
 188         /**
 189          * The list of meaningful points on the upper hull (received by the
 190          * reference trace, below in a graph)
 191          */
 192         private final LinkedList<SyncPoint> fUpperBoundList = new LinkedList<SyncPoint>();
 193
 194         /**
 195          * The list of meaninful points on the lower hull (sent by the reference
 196          * trace, above in a graph)
 197          */
 198         private final LinkedList<SyncPoint> fLowerBoundList = new LinkedList<SyncPoint>();
 199
 200         /** Points forming the line with maximum slope */
 201         private final SyncPoint[] fLmax;
 202
 203         /** Points forming the line with minimum slope */
 204         private final SyncPoint[] fLmin;
 205
 206         /**
 207          * Slopes and ordinate at origin of respectively fLmin, fLmax and the
 208          * bisector
 209          */
 210         private BigDecimal fAlphamin, fBetamax, fAlphamax, fBetamin, fAlpha, fBeta;
 211
 212         private int fNbMatches, fNbAccurateMatches;
 213         private String fReferenceTrace = "", fOtherTrace = ""; //$NON-NLS-1$//$NON-NLS-2$
 214         private SyncQuality fQuality;
 215
 216         private Map<String, Object> fStats = new LinkedHashMap<String, Object>();
 217
 218         /**
 219          * Initialization of the attributes
 220          *
 221          * @param trace1
 222          *            Name of the first trace
 223          * @param trace2
 224          *            Name of the second trace
 225          */
 226         public ConvexHull(String trace1, String trace2) {
 227             if (trace1.compareTo(trace2) > 0) {
 228                 fReferenceTrace = trace2;
 229                 fOtherTrace = trace1;
 230             } else {
 231                 fReferenceTrace = trace1;
 232                 fOtherTrace = trace2;
 233             }
 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;
 242             fNbMatches = 0;
 243             fNbAccurateMatches = 0;
 244             fQuality = SyncQuality.ABSENT;
 245         }
 246
 247         protected void processMatch(TmfEventDependency match) {
 248
 249             LinkedList<SyncPoint> boundList, otherBoundList;
 250
 251             SyncPoint[] line, otherLine;
 252             SyncPoint p;
 253             int inversionFactor = 1;
 254             boolean qualify = false;
 255             fNbMatches++;
 256
 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;
 261                 line = fLmin;
 262                 otherLine = fLmax;
 263                 p = new SyncPoint(match.getDestinationEvent(), match.getSourceEvent());
 264                 inversionFactor = 1;
 265             } else {
 266                 boundList = fLowerBoundList;
 267                 otherBoundList = fUpperBoundList;
 268                 line = fLmax;
 269                 otherLine = fLmin;
 270                 p = new SyncPoint(match.getSourceEvent(), match.getDestinationEvent());
 271                 inversionFactor = -1;
 272             }
 273
 274             /*
 275              * Does the message qualify for the hull, or is in on the wrong side
 276              * of the reference line
 277              */
 278             if ((line[0] == null) || (line[1] == null) || (p.crossProduct(line[0], line[1]) * inversionFactor > 0)) {
 279                 /*
 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
 283                  * anymore
 284                  */
 285                 fNbAccurateMatches++;
 286                 qualify = true;
 287                 removeUselessPoints(p, boundList, inversionFactor);
 288                 line[1] = p;
 289                 fStats.clear();
 290             }
 291
 292             /*
 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
 296              */
 297             adjustBound(line, otherBoundList, inversionFactor);
 298             if ((otherLine[1] != null) && !boundList.contains(otherLine[0])) {
 299                 adjustBound(otherLine, boundList, inversionFactor * -1);
 300             }
 301
 302             if (qualify) {
 303                 approximateSync();
 304             }
 305
 306         }
 307
 308         /**
 309          * Calculates slopes and ordinate at origin of fLmax and fLmin to obtain
 310          * and approximation of the synchronization at this time
 311          */
 312         private void approximateSync() {
 313             /**
 314              * Line slopes functions
 315              *
 316              * Lmax = alpha_max T + beta_min
 317              *
 318              * Lmin = alpha_min T + beta_max
 319              */
 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;
 329                 }
 330                 else if (fAlphamax.compareTo(fAlphamin) > 0) {
 331                     fQuality = SyncQuality.ACCURATE;
 332                 } else {
 333                     /* Lines intersect, not good */
 334                     fQuality = SyncQuality.FAIL;
 335                 }
 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;
 340             }
 341         }
 342
 343         /*
 344          * Verify if the line should be adjusted to be more accurate give the
 345          * hull
 346          */
 347         private void adjustBound(SyncPoint[] line, LinkedList<SyncPoint> otherBoundList, int inversionFactor) {
 348             SyncPoint minPoint = null, nextPoint;
 349             boolean finishedSearch = false;
 350
 351             /*
 352              * Find in the other bound, the origin point of the line, start from
 353              * the beginning if the point was lost
 354              */
 355             int i = Math.max(0, otherBoundList.indexOf(line[0]));
 356
 357             while ((i < otherBoundList.size() - 1) && !finishedSearch) {
 358                 minPoint = otherBoundList.get(i);
 359                 nextPoint = otherBoundList.get(i + 1);
 360
 361                 /*
 362                  * If the rotation (cross-product) is not optimal, move to next
 363                  * point as reference for the line (if available)
 364                  *
 365                  * Otherwise, the current minPoint is the minPoint of the line
 366                  */
 367                 if (minPoint.crossProduct(nextPoint, line[1]) * inversionFactor > 0) {
 368                     if (nextPoint.getTimeX() < line[1].getTimeX()) {
 369                         i++;
 370                     } else {
 371                         line[0] = null;
 372                         finishedSearch = true;
 373                     }
 374                 } else {
 375                     line[0] = minPoint;
 376                     finishedSearch = true;
 377                 }
 378             }
 379
 380             if (line[0] == null) {
 381                 line[0] = minPoint;
 382             }
 383
 384             /* Make sure point 0 is before point 1 */
 385             if ((line[0] != null) && (line[0].getTimeX() > line[1].getTimeX())) {
 386                 line[0] = null;
 387             }
 388         }
 389
 390         /*
 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
 393          */
 394         private void removeUselessPoints(final SyncPoint p, final LinkedList<SyncPoint> boundList, final int inversionFactor) {
 395
 396             boolean checkRemove = true;
 397
 398             while (checkRemove && boundList.size() >= 2) {
 399                 if (p.crossProduct(boundList.get(boundList.size() - 2), boundList.getLast()) * inversionFactor > 0) {
 400                     boundList.removeLast();
 401                 } else {
 402                     checkRemove = false;
 403                 }
 404             }
 405             boundList.addLast(p);
 406         }
 407
 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));
 412             }
 413             return TmfTimestampTransform.IDENTITY;
 414         }
 415
 416         public SyncQuality getQuality() {
 417             return fQuality;
 418         }
 419
 420         public Map<String, Object> getStats() {
 421             if (fStats.size() == 0) {
 422                 String syncQuality;
 423                 switch (fQuality) {
 424                 case ABSENT:
 425                     syncQuality = Messages.SyncAlgorithmFullyIncremental_absent;
 426                     break;
 427                 case ACCURATE:
 428                     syncQuality = Messages.SyncAlgorithmFullyIncremental_accurate;
 429                     break;
 430                 case APPROXIMATE:
 431                     syncQuality = Messages.SyncAlgorithmFullyIncremental_approx;
 432                     break;
 433                 case INCOMPLETE:
 434                     syncQuality = Messages.SyncAlgorithmFullyIncremental_incomplete;
 435                     break;
 436                 case FAIL:
 437                 default:
 438                     syncQuality = Messages.SyncAlgorithmFullyIncremental_fail;
 439                     break;
 440                 }
 441
 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()); // -
 450                                                                                                                           // fAlphamin);
 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);
 455             }
 456             return fStats;
 457
 458         }
 459
 460         public String getReferenceTrace() {
 461             return fReferenceTrace;
 462         }
 463
 464         public String getOtherTrace() {
 465             return fOtherTrace;
 466         }
 467
 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));
 471         }
 472
 473         public boolean isForTraces(String trace1, String trace2) {
 474             return ((fReferenceTrace.equals(trace1) && fOtherTrace.equals(trace2)) || (fReferenceTrace.equals(trace2) && fOtherTrace.equals(trace1)));
 475         }
 476
 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;
 482             }
 483         }
 484
 485         private void writeObject(ObjectOutputStream s)
 486                 throws IOException {
 487             /*
 488              * Remove calculation data because most of it is not serializable.
 489              * We have the statistics anyway
 490              */
 491             fUpperBoundList.clear();
 492             fLowerBoundList.clear();
 493             fLmin[0] = null;
 494             fLmin[1] = null;
 495             fLmax[0] = null;
 496             fLmax[1] = null;
 497             s.defaultWriteObject();
 498
 499         }
 500
 501         @SuppressWarnings("nls")
 502         @Override
 503         public String toString() {
 504             StringBuilder b = new StringBuilder();
 505             b.append("Between " + fReferenceTrace + " and " + fOtherTrace + " [");
 506             b.append(" alpha " + fAlpha + " beta " + fBeta + " ]");
 507             return b.toString();
 508         }
 509     }
 510
 511     /**
 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
 515      */
 516     private class SyncPoint {
 517         private final ITmfTimestamp x, y;
 518
 519         public SyncPoint(ITmfEvent ex, ITmfEvent ey) {
 520             x = ex.getTimestamp();
 521             y = ey.getTimestamp();
 522         }
 523
 524         public long getTimeX() {
 525             return x.getValue();
 526         }
 527
 528         /**
 529          * Calculate a cross product of 3 points:
 530          *
 531          * If the cross-product < 0, then p, pa, pb are clockwise
 532          *
 533          * If the cross-product > 0, then p, pa, pb are counter-clockwise
 534          *
 535          * If cross-product == 0, then they are in a line
 536          *
 537          * @param pa
 538          *            First point
 539          * @param pb
 540          *            Second point
 541          * @return The cross product
 542          */
 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()));
 545             return cp;
 546         }
 547
 548         /*
 549          * Gets the alpha (slope) between two points
 550          */
 551         public BigDecimal getAlpha(SyncPoint p1) {
 552             if (p1 == null) {
 553                 return BigDecimal.ONE;
 554             }
 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;
 559             }
 560             return deltay.divide(deltax, fMc);
 561         }
 562
 563         /*
 564          * Get the beta value (when x = 0) of the line given alpha
 565          */
 566         public BigDecimal getBeta(BigDecimal alpha) {
 567             return BigDecimal.valueOf(y.getValue()).subtract(alpha.multiply(BigDecimal.valueOf(x.getValue()), fMc));
 568         }
 569
 570     }
 571
 572 }