*
* Contributors:
* Geneviève Bastien - Initial implementation and API
+ * Francis Giraldeau - Transform computation using synchronization graph
*******************************************************************************/
package org.eclipse.linuxtools.tmf.core.synchronization;
import java.util.List;
import java.util.Map;
+import org.eclipse.linuxtools.internal.tmf.core.synchronization.graph.SyncSpanningTree;
import org.eclipse.linuxtools.tmf.core.event.ITmfEvent;
import org.eclipse.linuxtools.tmf.core.event.matching.TmfEventDependency;
import org.eclipse.linuxtools.tmf.core.timestamp.ITmfTimestamp;
private static final MathContext fMc = MathContext.DECIMAL128;
+ /** @Serial */
private final List<ConvexHull> fSyncs;
+ private SyncSpanningTree fTree = null;
+
/**
* Initialization of the attributes
*/
ITmfTrace[] traceArr = traces.toArray(new ITmfTrace[traces.size()]);
fSyncs.clear();
/* Create a convex hull for all trace pairs */
+ // FIXME: is it necessary to make ConvexHull for every pairs up-front?
+ // The ConvexHull seems to be created on the fly in processMatch().
for (int i = 0; i < traceArr.length; i++) {
for (int j = i + 1; j < traceArr.length; j++) {
ConvexHull algo = new ConvexHull(traceArr[i].getHostId(), traceArr[j].getHostId());
fSyncs.add(algo);
}
algo.processMatch(match);
+ invalidateSyncGraph();
+ }
+ private void invalidateSyncGraph() {
+ fTree = null;
}
@Override
@Override
public ITmfTimestampTransform getTimestampTransform(String hostId) {
- for (ConvexHull traceSync : fSyncs) {
- if (traceSync.isTraceSynced(hostId)) {
- /*
- * Since there are many traces, maybe the reference trace is
- * also synchronized, so we need to chain sync formulas
- */
- ITmfTimestampTransform refTt = getTimestampTransform(traceSync.getReferenceHost());
- return refTt.composeWith(traceSync.getTimestampTransform(hostId));
+ SyncSpanningTree tree = getSyncTree();
+ return tree.getTimestampTransform(hostId);
+ }
+
+ /**
+ * Each convex hull computes the synchronization between 2 given hosts. A
+ * synchronization can be done on multiple hosts that may not all
+ * communicate with each other. We must use another algorithm to determine
+ * which host will be the reference node and what synchronization formula
+ * will be used between each host and this reference node.
+ *
+ * For example, take traces a, b and c where a and c talk to b but do not
+ * know each other ({@literal a <-> b <-> c}). The convex hulls will contain
+ * the formulae between their 2 traces, but if a is the reference node, then
+ * the resulting formula of c would be the composition of {@literal a <-> b}
+ * and {@literal b <-> c}
+ *
+ * @return The synchronization spanning tree for this synchronization
+ */
+ private SyncSpanningTree getSyncTree() {
+ if (fTree == null) {
+ fTree = new SyncSpanningTree();
+ for (ConvexHull traceSync : fSyncs) {
+ SyncQuality q = traceSync.getQuality();
+ if (q == SyncQuality.ACCURATE || q == SyncQuality.APPROXIMATE) {
+ String from = traceSync.getReferenceHost();
+ String to = traceSync.getOtherHost();
+ fTree.addSynchronization(from, to, traceSync.getTimestampTransform(to), traceSync.getAccuracy());
+ }
}
}
- return TimestampTransformFactory.getDefaultTransform();
+ return fTree;
}
@Override
@Override
public boolean isTraceSynced(String hostId) {
- boolean traceSynced = false;
- for (ConvexHull traceSync : fSyncs) {
- traceSynced = traceSynced || traceSync.isTraceSynced(hostId);
- }
- return traceSynced;
+ ITmfTimestampTransform t = getTimestampTransform(hostId);
+ return !t.equals(TimestampTransformFactory.getDefaultTransform());
}
@Override
public Map<String, Map<String, Object>> getStats() {
+ /*
+ * TODO: Stats, while still accurate, may be misleading now that the
+ * sync tree changes synchronization formula. The stats should use the
+ * tree instead
+ */
Map<String, Map<String, Object>> statmap = new LinkedHashMap<>();
for (ConvexHull traceSync : fSyncs) {
statmap.put(traceSync.getReferenceHost() + " <==> " + traceSync.getOtherHost(), traceSync.getStats()); //$NON-NLS-1$
fBetamin = BigDecimal.ZERO;
fNbMatches = 0;
fNbAccurateMatches = 0;
- fQuality = SyncQuality.ABSENT;
+ fQuality = SyncQuality.ABSENT; // default quality
}
protected void processMatch(TmfEventDependency match) {
* and approximation of the synchronization at this time
*/
private void approximateSync() {
+
/**
* Line slopes functions
*
fAlpha = fAlphamax.add(fAlphamin).divide(BigDecimal.valueOf(2), fMc);
fBeta = fBetamin.add(fBetamax).divide(BigDecimal.valueOf(2), fMc);
if ((fLmax[0] == null) || (fLmin[0] == null)) {
- fQuality = SyncQuality.APPROXIMATE;
+ setQuality(SyncQuality.APPROXIMATE);
}
else if (fAlphamax.compareTo(fAlphamin) > 0) {
- fQuality = SyncQuality.ACCURATE;
+ setQuality(SyncQuality.ACCURATE);
} else {
/* Lines intersect, not good */
- fQuality = SyncQuality.FAIL;
+ setQuality(SyncQuality.FAIL);
}
} else if (((fLmax[0] == null) && (fLmin[1] == null))
|| ((fLmax[1] == null) && (fLmin[0] == null))) {
/* Either there is no upper hull point or no lower hull */
- fQuality = SyncQuality.INCOMPLETE;
+ setQuality(SyncQuality.INCOMPLETE);
}
}
}
public ITmfTimestampTransform getTimestampTransform(String hostId) {
- if (hostId.equals(fOtherHost) && (fQuality == SyncQuality.ACCURATE || fQuality == SyncQuality.APPROXIMATE || fQuality == SyncQuality.FAIL)) {
+ if (hostId.equals(fOtherHost) && (getQuality() == SyncQuality.ACCURATE || getQuality() == SyncQuality.APPROXIMATE || getQuality() == SyncQuality.FAIL)) {
/* alpha: beta => 1 / fAlpha, -1 * fBeta / fAlpha); */
return TimestampTransformFactory.createLinear(BigDecimal.ONE.divide(fAlpha, fMc), BigDecimal.valueOf(-1).multiply(fBeta).divide(fAlpha, fMc));
}
return fQuality;
}
+ public BigDecimal getAccuracy() {
+ return fAlphamax.subtract(fAlphamin);
+ }
+
public Map<String, Object> getStats() {
if (fStats.size() == 0) {
String syncQuality;
- switch (fQuality) {
+ switch (getQuality()) {
case ABSENT:
syncQuality = Messages.SyncAlgorithmFullyIncremental_absent;
break;
fStats.put(Messages.SyncAlgorithmFullyIncremental_beta, fBeta);
fStats.put(Messages.SyncAlgorithmFullyIncremental_ub, (fUpperBoundList.size() == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fUpperBoundList.size());
fStats.put(Messages.SyncAlgorithmFullyIncremental_lb, (fLowerBoundList.size() == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fLowerBoundList.size());
- fStats.put(Messages.SyncAlgorithmFullyIncremental_accuracy, fAlphamax.subtract(fAlphamin).doubleValue()); // -
- // fAlphamin);
+ fStats.put(Messages.SyncAlgorithmFullyIncremental_accuracy, getAccuracy().doubleValue());
fStats.put(Messages.SyncAlgorithmFullyIncremental_nbmatch, (fNbMatches == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fNbMatches);
fStats.put(Messages.SyncAlgorithmFullyIncremental_nbacc, (fNbAccurateMatches == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fNbAccurateMatches);
fStats.put(Messages.SyncAlgorithmFullyIncremental_refformula, Messages.SyncAlgorithmFullyIncremental_T_ + fReferenceHost);
return fOtherHost;
}
- public boolean isTraceSynced(String hostId) {
- /* Returns true if the timestamp transform is not identity */
- return (hostId.equals(fOtherHost) && (fQuality == SyncQuality.ACCURATE || fQuality == SyncQuality.APPROXIMATE || fQuality == SyncQuality.FAIL));
- }
-
public boolean isForHosts(String hostId1, String hostId2) {
return ((fReferenceHost.equals(hostId1) && fOtherHost.equals(hostId2)) || (fReferenceHost.equals(hostId2) && fOtherHost.equals(hostId1)));
}
fLmax[0] = null;
fLmax[1] = null;
s.defaultWriteObject();
-
}
@SuppressWarnings("nls")
b.append(" alpha " + fAlpha + " beta " + fBeta + " ]");
return b.toString();
}
+
+ private void setQuality(SyncQuality fQuality) {
+ this.fQuality = fQuality;
+ }
+
}
/**
return BigDecimal.valueOf(y.getValue()).subtract(alpha.multiply(BigDecimal.valueOf(x.getValue()), fMc));
}
+ @Override
+ public String toString() {
+ return String.format("%s (%s, %s)", this.getClass().getCanonicalName(), x, y); //$NON-NLS-1$
+ }
+ }
+
+ private void writeObject(ObjectOutputStream s)
+ throws IOException {
+ /*
+ * Remove the tree because it is not serializable
+ */
+ fTree = null;
+ s.defaultWriteObject();
}
}
projects / deliverable / tracecompass.git / blobdiff