* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
+#define _ISOC99_SOURCE
+
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <errno.h>
+#include <math.h>
+#include <stdlib.h>
#include <string.h>
#include <unistd.h>
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
*
}
+/*
+ * 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()
*
projects / lttv.git / blobdiff