-/*
- * 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 (MIDDLE and FALLBACK) 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 bondaries 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:
- * syncState: container for synchronization data.
- * allFactors: offset and drift between each pair of traces
- *
- * Returns:
- * Factors[traceNb] synchronization factors for each trace
- */
-static GArray* reduceFactors(SyncState* const syncState, FactorsCHull** const
- allFactors)
-{
- GArray* factors;
- double** distances;
- unsigned int** predecessors;
- double* distanceSums;
- unsigned int* references;
- unsigned int i, j;
-
- // Solve the all-pairs shortest path problem using the Floyd-Warshall
- // algorithm
- floydWarshall(syncState, 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(syncState->traceNb * sizeof(double));
- for (i= 0; i < syncState->traceNb; i++)
- {
- distanceSums[i]= 0.;
- for (j= 0; j < syncState->traceNb; j++)
- {
- distanceSums[i]+= distances[i][j];
- }
- }
-
- references= malloc(syncState->traceNb * sizeof(unsigned int));
- for (i= 0; i < syncState->traceNb; i++)
- {
- references[i]= UINT_MAX;
- }
- for (i= 0; i < syncState->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 < syncState->traceNb; j++)
- {
- if (distances[i][j] != INFINITY && distanceSums[j] <
- distanceSumMin)
- {
- reference= j;
- distanceSumMin= distanceSums[j];
- }
- }
- for (j= 0; j < syncState->traceNb; j++)
- {
- if (distances[i][j] != INFINITY)
- {
- references[j]= reference;
- }
- }
- }
- }
-
- for (i= 0; i < syncState->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),
- syncState->traceNb);
- g_array_set_size(factors, syncState->traceNb);
- for (i= 0; i < syncState->traceNb; i++)
- {
- getFactors(allFactors, predecessors, references, i, &g_array_index(factors,
- Factors, i));
- }
-
- for (i= 0; i < syncState->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:
- * syncState: container for synchronization data.
- * 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(SyncState* const syncState, FactorsCHull** const
- allFactors, double*** const distances, unsigned int*** const
- predecessors)
-{
- unsigned int i, j, k;
-
- // Setup initial conditions
- *distances= malloc(syncState->traceNb * sizeof(double*));
- *predecessors= malloc(syncState->traceNb * sizeof(unsigned int*));
- for (i= 0; i < syncState->traceNb; i++)
- {
- (*distances)[i]= malloc(syncState->traceNb * sizeof(double));
- for (j= 0; j < syncState->traceNb; j++)
- {
- if (i == j)
- {
- g_assert(allFactors[i][j].type == EXACT);
-
- (*distances)[i][j]= 0.;
- }
- else
- {
- unsigned int row, col;
-
- if (i > j)
- {
- row= i;
- col= j;
- }
- else if (i < j)
- {
- row= j;
- col= i;
- }
-
- if (allFactors[row][col].type == MIDDLE ||
- allFactors[row][col].type == FALLBACK)
- {
- (*distances)[i][j]= allFactors[row][col].accuracy;
- }
- else if (allFactors[row][col].type == INCOMPLETE ||
- allFactors[row][col].type == SCREWED ||
- allFactors[row][col].type == ABSENT)
- {
- (*distances)[i][j]= INFINITY;
- }
- else
- {
- g_assert_not_reached();
- }
- }
- }
-
- (*predecessors)[i]= malloc(syncState->traceNb * sizeof(unsigned int));
- for (j= 0; j < syncState->traceNb; j++)
- {
- if (i != j)
- {
- (*predecessors)[i][j]= i;
- }
- else
- {
- (*predecessors)[i][j]= UINT_MAX;
- }
- }
- }
-
- // Run the iterations
- for (k= 0; k < syncState->traceNb; k++)
- {
- for (i= 0; i < syncState->traceNb; i++)
- {
- for (j= 0; j < syncState->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(FactorsCHull** const allFactors, unsigned int** const
- predecessors, unsigned int* const references, const unsigned int traceNum,
- Factors* const factors)
-{
- unsigned int reference;
-
- reference= references[traceNum];
-
- if (reference == traceNum)
- {
- factors->offset= 0.;
- factors->drift= 1.;
- }
- else
- {
- Factors previousVertexFactors;
-
- getFactors(allFactors, predecessors, references,
- predecessors[reference][traceNum], &previousVertexFactors);
-
- // convertir de traceNum à reference
-
- // allFactors convertit de col à row
-
- if (reference > traceNum)
- {
- factors->offset= previousVertexFactors.drift *
- allFactors[reference][traceNum].approx->offset +
- previousVertexFactors.offset;
- factors->drift= previousVertexFactors.drift *
- allFactors[reference][traceNum].approx->drift;
- }
- else
- {
- factors->offset= previousVertexFactors.drift * (-1. *
- allFactors[traceNum][reference].approx->offset /
- allFactors[traceNum][reference].approx->drift) +
- previousVertexFactors.offset;
- factors->drift= previousVertexFactors.drift * (1. /
- allFactors[traceNum][reference].approx->drift);
- }
- }
-}
-
-