X-Git-Url: http://git.liburcu.org/?a=blobdiff_plain;f=lttv%2Flttv%2Fsync%2Fsync_chain.c;h=08cc3cb33b2b8f137e993b9eb7214fa548079091;hb=0a87ec9a018cc9731ce3b04309eaa4dcc77df6d2;hp=be915b08474ba4acba68f2d5e4087e1e9eb3a06e;hpb=9c7696b8589e76aed870b15cabd09a162d468621;p=lttv.git
diff --git a/lttv/lttv/sync/sync_chain.c b/lttv/lttv/sync/sync_chain.c
index be915b08..08cc3cb3 100644
--- a/lttv/lttv/sync/sync_chain.c
+++ b/lttv/lttv/sync/sync_chain.c
@@ -15,11 +15,15 @@
* along with this program. If not, see .
*/
+#define _ISOC99_SOURCE
+
#ifdef HAVE_CONFIG_H
#include
#endif
#include
+#include
+#include
#include
#include
@@ -32,6 +36,13 @@ GQueue analysisModules= G_QUEUE_INIT;
GQueue moduleOptions= G_QUEUE_INIT;
+static void floydWarshall(AllFactors* const allFactors, double*** const
+ distances, unsigned int*** const predecessors);
+static void getFactors(AllFactors* const allFactors, unsigned int** const
+ predecessors, unsigned int* const references, const unsigned int traceNum,
+ Factors* const factors);
+
+
/*
* Call the statistics function of each module of a sync chain
*
@@ -77,6 +88,304 @@ void timeDiff(struct timeval* const end, const struct timeval* const start)
}
+/*
+ * Calculate a resulting offset and drift for each trace.
+ *
+ * Traces are assembled in groups. A group is an "island" of nodes/traces that
+ * exchanged messages. A reference is determined for each group by using a
+ * shortest path search based on the accuracy of the approximation. This also
+ * forms a tree of the best way to relate each node's clock to the reference's
+ * based on the accuracy. Sometimes it may be necessary or advantageous to
+ * propagate the factors through intermediary clocks. Resulting factors for
+ * each trace are determined based on this tree.
+ *
+ * This part was not the focus of my research. The algorithm used here is
+ * inexact in some ways:
+ * 1) The reference used may not actually be the best one to use. This is
+ * because the accuracy is not corrected based on the drift during the
+ * shortest path search.
+ * 2) The min and max factors are not propagated and are no longer valid.
+ * 3) Approximations of different types (ACCURATE and APPROXIMATE) are compared
+ * together. The "accuracy" parameters of these have different meanings and
+ * are not readily comparable.
+ *
+ * Nevertheless, the result is satisfactory. You just can't tell "how much" it
+ * is.
+ *
+ * Two alternative (and subtly different) ways of propagating factors to
+ * preserve min and max boundaries have been proposed, see:
+ * [Duda, A., Harrus, G., Haddad, Y., and Bernard, G.: Estimating global time
+ * in distributed systems, Proc. 7th Int. Conf. on Distributed Computing
+ * Systems, Berlin, volume 18, 1987] p.304
+ *
+ * [Jezequel, J.M., and Jard, C.: Building a global clock for observing
+ * computations in distributed memory parallel computers, Concurrency:
+ * Practice and Experience 8(1), volume 8, John Wiley & Sons, Ltd Chichester,
+ * 1996, 32] Section 5; which is mostly the same as
+ * [Jezequel, J.M.: Building a global time on parallel machines, Proceedings
+ * of the 3rd International Workshop on Distributed Algorithms, LNCS, volume
+ * 392, 136â147, 1989] Section 5
+ *
+ * Args:
+ * allFactors: offset and drift between each pair of traces
+ *
+ * Returns:
+ * Factors[traceNb] synchronization factors for each trace
+ */
+GArray* reduceFactors(AllFactors* const allFactors)
+{
+ GArray* factors;
+ double** distances;
+ unsigned int** predecessors;
+ double* distanceSums;
+ unsigned int* references;
+ unsigned int i, j;
+ const unsigned int traceNb= allFactors->traceNb;
+
+ // Solve the all-pairs shortest path problem using the Floyd-Warshall
+ // algorithm
+ floydWarshall(allFactors, &distances, &predecessors);
+
+ /* Find the reference for each node
+ *
+ * First calculate, for each node, the sum of the distances to each other
+ * node it can reach.
+ *
+ * Then, go through each "island" of traces to find the trace that has the
+ * lowest distance sum. Assign this trace as the reference to each trace
+ * of the island.
+ */
+ distanceSums= malloc(traceNb * sizeof(double));
+ for (i= 0; i < traceNb; i++)
+ {
+ distanceSums[i]= 0.;
+ for (j= 0; j < traceNb; j++)
+ {
+ distanceSums[i]+= distances[i][j];
+ }
+ }
+
+ references= malloc(traceNb * sizeof(unsigned int));
+ for (i= 0; i < traceNb; i++)
+ {
+ references[i]= UINT_MAX;
+ }
+ for (i= 0; i < traceNb; i++)
+ {
+ if (references[i] == UINT_MAX)
+ {
+ unsigned int reference;
+ double distanceSumMin;
+
+ // A node is its own reference by default
+ reference= i;
+ distanceSumMin= INFINITY;
+ for (j= 0; j < traceNb; j++)
+ {
+ if (distances[i][j] != INFINITY && distanceSums[j] <
+ distanceSumMin)
+ {
+ reference= j;
+ distanceSumMin= distanceSums[j];
+ }
+ }
+ for (j= 0; j < traceNb; j++)
+ {
+ if (distances[i][j] != INFINITY)
+ {
+ references[j]= reference;
+ }
+ }
+ }
+ }
+
+ for (i= 0; i < traceNb; i++)
+ {
+ free(distances[i]);
+ }
+ free(distances);
+ free(distanceSums);
+
+ /* For each trace, calculate the factors based on their corresponding
+ * tree. The tree is rooted at the reference and the shortest path to each
+ * other nodes are the branches.
+ */
+ factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors),
+ traceNb);
+ g_array_set_size(factors, traceNb);
+ for (i= 0; i < traceNb; i++)
+ {
+ getFactors(allFactors, predecessors, references, i, &g_array_index(factors,
+ Factors, i));
+ }
+
+ for (i= 0; i < traceNb; i++)
+ {
+ free(predecessors[i]);
+ }
+ free(predecessors);
+ free(references);
+
+ return factors;
+}
+
+
+/*
+ * Perform an all-source shortest path search using the Floyd-Warshall
+ * algorithm.
+ *
+ * The algorithm is implemented accoding to the description here:
+ * http://web.mit.edu/urban_or_book/www/book/chapter6/6.2.2.html
+ *
+ * Args:
+ * allFactors: offset and drift between each pair of traces
+ * distances: resulting matrix of the length of the shortest path between
+ * two nodes. If there is no path between two nodes, the
+ * length is INFINITY
+ * predecessors: resulting matrix of each node's predecessor on the shortest
+ * path between two nodes
+ */
+static void floydWarshall(AllFactors* const allFactors, double*** const
+ distances, unsigned int*** const predecessors)
+{
+ unsigned int i, j, k;
+ const unsigned int traceNb= allFactors->traceNb;
+ PairFactors** const pairFactors= allFactors->pairFactors;
+
+ // Setup initial conditions
+ *distances= malloc(traceNb * sizeof(double*));
+ *predecessors= malloc(traceNb * sizeof(unsigned int*));
+ for (i= 0; i < traceNb; i++)
+ {
+ (*distances)[i]= malloc(traceNb * sizeof(double));
+ for (j= 0; j < traceNb; j++)
+ {
+ if (i == j)
+ {
+ g_assert(pairFactors[i][j].type == EXACT);
+
+ (*distances)[i][j]= 0.;
+ }
+ else
+ {
+ if (pairFactors[i][j].type == ACCURATE ||
+ pairFactors[i][j].type == APPROXIMATE)
+ {
+ (*distances)[i][j]= pairFactors[i][j].accuracy;
+ }
+ else if (pairFactors[j][i].type == ACCURATE ||
+ pairFactors[j][i].type == APPROXIMATE)
+ {
+ (*distances)[i][j]= pairFactors[j][i].accuracy;
+ }
+ else
+ {
+ (*distances)[i][j]= INFINITY;
+ }
+ }
+ }
+
+ (*predecessors)[i]= malloc(traceNb * sizeof(unsigned int));
+ for (j= 0; j < traceNb; j++)
+ {
+ if (i != j)
+ {
+ (*predecessors)[i][j]= i;
+ }
+ else
+ {
+ (*predecessors)[i][j]= UINT_MAX;
+ }
+ }
+ }
+
+ // Run the iterations
+ for (k= 0; k < traceNb; k++)
+ {
+ for (i= 0; i < traceNb; i++)
+ {
+ for (j= 0; j < traceNb; j++)
+ {
+ double distanceMin;
+
+ distanceMin= MIN((*distances)[i][j], (*distances)[i][k] +
+ (*distances)[k][j]);
+
+ if (distanceMin != (*distances)[i][j])
+ {
+ (*predecessors)[i][j]= (*predecessors)[k][j];
+ }
+
+ (*distances)[i][j]= distanceMin;
+ }
+ }
+ }
+}
+
+
+/*
+ * Cummulate the time correction factors to convert a node's time to its
+ * reference's time.
+ * This function recursively calls itself until it reaches the reference node.
+ *
+ * Args:
+ * allFactors: offset and drift between each pair of traces
+ * predecessors: matrix of each node's predecessor on the shortest
+ * path between two nodes
+ * references: reference node for each node
+ * traceNum: node for which to find the factors
+ * factors: resulting factors
+ */
+static void getFactors(AllFactors* const allFactors, unsigned int** const
+ predecessors, unsigned int* const references, const unsigned int traceNum,
+ Factors* const factors)
+{
+ unsigned int reference;
+ PairFactors** const pairFactors= allFactors->pairFactors;
+
+ reference= references[traceNum];
+
+ if (reference == traceNum)
+ {
+ factors->offset= 0.;
+ factors->drift= 1.;
+ }
+ else
+ {
+ Factors previousVertexFactors;
+
+ getFactors(allFactors, predecessors, references,
+ predecessors[reference][traceNum], &previousVertexFactors);
+
+ /* Convert the time from traceNum to reference;
+ * pairFactors[row][col] converts the time from col to row, invert the
+ * factors as necessary */
+
+ if (pairFactors[reference][traceNum].approx != NULL)
+ {
+ factors->offset= previousVertexFactors.drift *
+ pairFactors[reference][traceNum].approx->offset +
+ previousVertexFactors.offset;
+ factors->drift= previousVertexFactors.drift *
+ pairFactors[reference][traceNum].approx->drift;
+ }
+ else if (pairFactors[traceNum][reference].approx != NULL)
+ {
+ factors->offset= previousVertexFactors.drift * (-1. *
+ pairFactors[traceNum][reference].approx->offset /
+ pairFactors[traceNum][reference].approx->drift) +
+ previousVertexFactors.offset;
+ factors->drift= previousVertexFactors.drift * (1. /
+ pairFactors[traceNum][reference].approx->drift);
+ }
+ else
+ {
+ g_assert_not_reached();
+ }
+ }
+}
+
+
/*
* A GCompareFunc for g_slist_find_custom()
*