sync/event_analysis_eval.h\
sync/event_analysis_linreg.c\
sync/event_analysis_linreg.h\
+ sync/factor_reduction.h\
+ sync/factor_reduction_accuracy.c\
+ sync/factor_reduction_accuracy.h\
sync/lookup3.h
lttvinclude_HEADERS = \
sync_chain.c\
sync_chain.h\
sync_chain_unittest.c\
+ event_processing.h\
event_processing_text.c\
event_processing_text.h\
+ event_matching.h\
event_matching_broadcast.c\
event_matching_broadcast.h\
event_matching_distributor.c\
event_matching_distributor.h\
event_matching_tcp.c\
event_matching_tcp.h\
+ event_analysis.h\
event_analysis_chull.c\
event_analysis_chull.h\
event_analysis_eval.c\
event_analysis_eval.h\
event_analysis_linreg.c\
- event_analysis_linreg.h
+ event_analysis_linreg.h\
+ factor_reduction.h\
+ factor_reduction_accuracy.c\
+ factor_reduction_accuracy.h
is mostly for performance evaluation
--sync-analysis - argument: chull, linreg, eval
specify the algorithm to use for event analysis. See the
- section "Alogrithms".
+ section "Synchronization Alogrithms".
+--sync-reduction - argument: accuracy
+ specify the algorithm to use for factor reduction. See
+ the section "Reduction Algorithms".
--sync-graphs
output gnuplot graph showing synchronization points
--sync-graphs-dir - argument: DIRECTORY
user time: 0.112007
system time: 0.000000
-++ Algorithms
+++ Synchronization Algorithms
The synchronization framework is extensible and already includes two
-algorithms: chull and linreg. You can choose which analysis algorithm to use
-with the --sync-analysis option.
+algorithms: chull and linreg. (There is also a special "eval" module
+available.) You can choose which analysis algorithm to use with the
+--sync-analysis option.
+++ Convex Hull
chull, the default analysis module, can provide a garantee that there are no
lttv -m sync_chain_batch --eval-graphs [usual options, ex: -t traces/node1 -t
traces/node2 --sync ...]
++ Reduction Algorithms
+Event analysis yields time correction factors between trace pairs. For groups
+of more than two traces, an extra step is necessary to identify a reference
+trace and calculate correction factors for each trace relative to this
+reference. There are usually many possibilities and so this step is called
+"factor reduction".
+
+++ Accuracy
+At the moment, only one algorithm is available to do this, the "accuracy"
+algorithm. This algorithm tries to choose the reference and the factors that
+yield the best accuracy. See the function header comments in
+factor_reduction_accuracy.c for more details.
+
+ Design
This part describes the design of the synchronization framework. This is to
help programmers interested in:
synchronization, the executable linking to the event_*.o
eg. LTTV, unittest
-This reads parameters, creates SyncState and calls the processing init
-function. The "sync chain" is the set of event-* modules. At the moment there
-is only one module at each stage. However, as more module are added, it will
-become relevant to have many modules at the same stage simultaneously. This
-will require some modifications. It is already partly supported at the
+This reads parameters, creates SyncState and calls the init functions of the
+modules to be used. The "sync chain" is this set of modules. At the moment
+there is only one module at each stage. However, as more modules are added, it
+will become relevant to have many modules at the same stage simultaneously.
+This will require some modifications. It is already partly supported at the
matching stage through encapsulation of other matching modules.
sync_chain_unitest:main() provides a fairly simple example of sync chain
Data from traces flows "down" from processing to matching to analysis. Factors
come back up.
+++ Stage 4: Factor reduction
+This stage reduces the pair-wise synchronization factors to time correction
+factors for each trace. It is most useful when synchronizing more than two
+traces.
+
++ Evolution and adaptation
-It is possible to change/add another sync chain and to add other event_*
-modules. It has been done. New types of events may need to be added to
-data_structures.h. This is only to link between Event-* modules. If the data
-does not have to be shared, data_structures.h does not have to be modified.
-
-At the moment there is some code duplication in the last steps of linreg and
-chull analysis: the code to propagate the factors when there are more than two
-nodes. Maybe there could be a Stage 4 that does that?
+It is possible to change/add another sync chain and to add other modules. It
+has been done. New types of events may need to be added to data_structures.h.
+This is only to link between Event-* modules. If the data does not have to be
+shared, data_structures.h does not have to be modified.
unsigned int i, j;
allFactors= malloc(sizeof(AllFactors));
- allFactors->traceNb= traceNb;
allFactors->refCount= 1;
allFactors->pairFactors= malloc(traceNb * sizeof(PairFactors*));
factorsArray=allFactors->pairFactors;
* Free a container of PairFactors
*
* Args:
- * traceNb: number of traces
* allFactors: container of PairFactors
+ * traceNb: number of traces
*/
-void freeAllFactors(AllFactors* const allFactors)
+void freeAllFactors(AllFactors* const allFactors, const unsigned int traceNb)
{
unsigned int i, j;
- const unsigned int traceNb= allFactors->traceNb;
allFactors->refCount--;
#include <stdbool.h>
#include <stdint.h>
+#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
+
enum Direction
{
typedef struct
{
unsigned int refCount;
- unsigned int traceNb;
PairFactors** pairFactors;
} AllFactors;
void destroyPairFactors(PairFactors* factorsCHull);
AllFactors* createAllFactors(const unsigned int traceNb);
-void freeAllFactors(AllFactors* const allFactors);
+void freeAllFactors(AllFactors* const allFactors, const unsigned int traceNb);
#endif
{
for (j= 0; j < syncState->traceNb; j++)
{
- g_queue_foreach(analysisData->hullArray[i][j], gfPointDestroy, NULL);
+ g_queue_foreach(analysisData->hullArray[i][j], gfPointDestroy,
+ NULL);
g_queue_free(analysisData->hullArray[i][j]);
}
free(analysisData->hullArray[i]);
if (syncState->stats)
{
- freeAllFactors(analysisData->stats->allFactors);
+ freeAllFactors(analysisData->stats->allFactors, syncState->traceNb);
free(analysisData->stats);
}
closeGraphFiles(syncState);
}
- freeAllFactors(analysisData->graphsData->allFactors);
+ freeAllFactors(analysisData->graphsData->allFactors,
+ syncState->traceNb);
free(analysisData->graphsData);
}
g_hash_table_destroy(stats->exchangeRtt);
#ifdef HAVE_LIBGLPK
- freeAllFactors(stats->chFactorsArray);
- freeAllFactors(stats->lpFactorsArray);
+ freeAllFactors(stats->chFactorsArray, syncState->traceNb);
+ freeAllFactors(stats->lpFactorsArray, syncState->traceNb);
#endif
free(stats);
if (!syncState->stats)
{
- freeAllFactors(graphs->lpFactorsArray);
+ freeAllFactors(graphs->lpFactorsArray, syncState->traceNb);
}
#endif
}
#endif
- freeAllFactors(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS));
+ freeAllFactors(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS),
+ analysisData->chullSS->traceNb);
}
{
SyncState* parallelSS= data;
- freeAllFactors(parallelSS->matchingModule->finalizeMatching(parallelSS));
+ freeAllFactors(parallelSS->matchingModule->finalizeMatching(parallelSS),
+ parallelSS->traceNb);
}
if (syncState->stats && processingData->factors)
{
- freeAllFactors(processingData->factors);
+ freeAllFactors(processingData->factors, syncState->traceNb);
}
free(syncState->processingData);
--- /dev/null
+/* This file is part of the Linux Trace Toolkit viewer
+ * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
+ *
+ * This program is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation, either version 2.1 of the License, or (at
+ * your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef FACTOR_REDUCTION_H
+#define FACTOR_REDUCTION_H
+
+#include "data_structures.h"
+#include "graph_functions.h"
+
+
+struct _SyncState;
+
+typedef struct
+{
+ char* name;
+
+ void (*initReduction)(struct _SyncState* const syncState);
+ void (*destroyReduction)(struct _SyncState* const syncState);
+
+ GArray* (*finalizeReduction)(struct _SyncState* const syncState,
+ AllFactors* allFactors);
+
+ void (*printReductionStats)(struct _SyncState* const syncState);
+ GraphFunctions graphFunctions;
+} ReductionModule;
+
+#endif
--- /dev/null
+/* This file is part of the Linux Trace Toolkit viewer
+ * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
+ *
+ * This program is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation, either version 2.1 of the License, or (at
+ * your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+#define _ISOC99_SOURCE
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <math.h>
+#include <stdlib.h>
+
+#include "sync_chain.h"
+
+#include "factor_reduction_accuracy.h"
+
+
+// Functions common to all reduction modules
+static void initReductionAccuracy(SyncState* const syncState);
+static void destroyReductionAccuracy(SyncState* const syncState);
+
+static GArray* finalizeReductionAccuracy(SyncState* const syncState,
+ AllFactors* allFactors);
+static void printReductionStatsAccuracy(SyncState* const syncState);
+
+// Functions specific to this module
+static void floydWarshall(AllFactors* const allFactors, const unsigned int
+ traceNb, 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);
+
+
+static ReductionModule reductionModuleAccuracy= {
+ .name= "accuracy",
+ .initReduction= &initReductionAccuracy,
+ .destroyReduction= &destroyReductionAccuracy,
+ .finalizeReduction= &finalizeReductionAccuracy,
+ .printReductionStats= &printReductionStatsAccuracy,
+ .graphFunctions= {},
+};
+
+
+/*
+ * Reduction module registering function
+ */
+void registerReductionAccuracy()
+{
+ g_queue_push_tail(&reductionModules, &reductionModuleAccuracy);
+}
+
+
+/*
+ * Reduction init function
+ *
+ * This function is called at the beginning of a synchronization run for a set
+ * of traces.
+ *
+ * Allocate some reduction specific data structures
+ *
+ * Args:
+ * syncState container for synchronization data.
+ */
+static void initReductionAccuracy(SyncState* const syncState)
+{
+ if (syncState->stats)
+ {
+ syncState->reductionData= calloc(1, sizeof(ReductionStatsAccuracy));
+ }
+}
+
+
+/*
+ * Reduction destroy function
+ *
+ * Free the analysis specific data structures
+ *
+ * Args:
+ * syncState container for synchronization data.
+ */
+static void destroyReductionAccuracy(SyncState* const syncState)
+{
+ unsigned int i;
+
+ if (syncState->stats)
+ {
+ ReductionStatsAccuracy* stats= syncState->reductionData;
+
+ if (stats->predecessors)
+ {
+ for (i= 0; i < syncState->traceNb; i++)
+ {
+ free(stats->predecessors[i]);
+ }
+ free(stats->predecessors);
+ free(stats->references);
+ }
+ free(stats);
+ }
+}
+
+
+/*
+ * Finalize the factor reduction
+ *
+ * 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:
+ * syncState container for synchronization data.
+ * allFactors offset and drift between each pair of traces
+ *
+ * Returns:
+ * Factors[traceNb] synchronization factors for each trace
+
+ */
+static GArray* finalizeReductionAccuracy(SyncState* const syncState,
+ AllFactors* 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(allFactors, syncState->traceNb, &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));
+ }
+
+ if (syncState->stats)
+ {
+ ReductionStatsAccuracy* stats= syncState->reductionData;
+
+ stats->predecessors= predecessors;
+ stats->references= references;
+ }
+ else
+ {
+ for (i= 0; i < syncState->traceNb; i++)
+ {
+ free(predecessors[i]);
+ }
+ free(predecessors);
+ free(references);
+ }
+
+ return factors;
+}
+
+
+/*
+ * Print statistics related to reduction. Must be called after
+ * finalizeReduction.
+ *
+ * Args:
+ * syncState container for synchronization data.
+ */
+static void printReductionStatsAccuracy(SyncState* const syncState)
+{
+ unsigned int i;
+ ReductionStatsAccuracy* stats= syncState->reductionData;
+
+ printf("Accuracy-based factor reduction stats:\n");
+ for (i= 0; i < syncState->traceNb; i++)
+ {
+ unsigned int reference= stats->references[i];
+
+ if (i == reference)
+ {
+ printf("\ttrace %u is a reference\n", i);
+ }
+ else
+ {
+ printf("\ttrace %u: reference %u, predecessor %u\n", i,
+ reference,
+ stats->predecessors[reference][i]);
+ }
+ }
+}
+
+
+/*
+ * 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
+ * traceNb: number 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. distances[i][j] is the length of the
+ * path from i to j.
+ * predecessors: resulting matrix of each node's predecessor on the shortest
+ * path between two nodes. predecessors[i][j] is the
+ * predecessor to j on the path from i to j.
+ */
+static void floydWarshall(AllFactors* const allFactors, const unsigned int
+ traceNb, double*** const distances, unsigned int*** const predecessors)
+{
+ unsigned int i, j, k;
+ 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();
+ }
+ }
+}
--- /dev/null
+/* This file is part of the Linux Trace Toolkit viewer
+ * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
+ *
+ * This program is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation, either version 2.1 of the License, or (at
+ * your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef FACTOR_REDUCTION_ACCURACY_H
+#define FACTOR_REDUCTION_ACCURACY_H
+
+#include <glib.h>
+
+#include "data_structures.h"
+
+
+typedef struct
+{
+ unsigned int** predecessors;
+ unsigned int* references;
+} ReductionStatsAccuracy;
+
+void registerReductionAccuracy();
+
+#endif
* 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 processingModules= G_QUEUE_INIT;
GQueue matchingModules= G_QUEUE_INIT;
GQueue analysisModules= G_QUEUE_INIT;
+GQueue reductionModules= 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
*
{
syncState->processingModule->printProcessingStats(syncState);
}
- if (syncState->matchingModule->printMatchingStats != NULL)
+ if (syncState->matchingModule != NULL &&
+ syncState->matchingModule->printMatchingStats != NULL)
{
syncState->matchingModule->printMatchingStats(syncState);
}
- if (syncState->analysisModule->printAnalysisStats != NULL)
+ if (syncState->analysisModule != NULL &&
+ syncState->analysisModule->printAnalysisStats != NULL)
{
syncState->analysisModule->printAnalysisStats(syncState);
}
+ if (syncState->reductionModule != NULL &&
+ syncState->reductionModule->printReductionStats != NULL)
+ {
+ syncState->reductionModule->printReductionStats(syncState);
+ }
}
}
-/*
- * 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()
*
}
+/*
+ * A GCompareFunc for g_slist_find_custom()
+ *
+ * Args:
+ * a: ReductionModule*, element's data
+ * b: char*, user data to compare against
+ *
+ * Returns:
+ * 0 if the reduction module a's name is b
+ */
+gint gcfCompareReduction(gconstpointer a, gconstpointer b)
+{
+ const ReductionModule* reductionModule;
+ const char* name;
+
+ reductionModule= (const ReductionModule*) a;
+ name= (const char*) b;
+
+ return strncmp(reductionModule->name, name, strlen(reductionModule->name) +
+ 1);
+}
+
+
/*
* A GFunc for g_queue_foreach()
*
g_string_append((GString*) user_data, ((AnalysisModule*) data)->name);
g_string_append((GString*) user_data, ", ");
}
+
+
+/*
+ * A GFunc for g_queue_foreach()
+ *
+ * Concatenate reduction module names.
+ *
+ * Args:
+ * data: ReductionModule*
+ * user_data: GString*, concatenated names
+ */
+void gfAppendReductionName(gpointer data, gpointer user_data)
+{
+ g_string_append((GString*) user_data, ((ReductionModule*) data)->name);
+ g_string_append((GString*) user_data, ", ");
+}
#include "event_processing.h"
#include "event_matching.h"
#include "event_analysis.h"
+#include "factor_reduction.h"
typedef struct _SyncState
{
void* matchingData;
const AnalysisModule* analysisModule;
void* analysisData;
+ const ReductionModule* reductionModule;
+ void* reductionData;
} SyncState;
typedef struct
extern GQueue processingModules;
extern GQueue matchingModules;
extern GQueue analysisModules;
+extern GQueue reductionModules;
+
extern GQueue moduleOptions;
void printStats(SyncState* const syncState);
void timeDiff(struct timeval* const end, const struct timeval* const start);
-GArray* reduceFactors(AllFactors* allFactors);
-
gint gcfCompareProcessing(gconstpointer a, gconstpointer b);
gint gcfCompareMatching(gconstpointer a, gconstpointer b);
gint gcfCompareAnalysis(gconstpointer a, gconstpointer b);
+gint gcfCompareReduction(gconstpointer a, gconstpointer b);
void gfAppendAnalysisName(gpointer data, gpointer user_data);
+void gfAppendReductionName(gpointer data, gpointer user_data);
#endif
#include "event_analysis_chull.h"
#include "event_analysis_linreg.h"
#include "event_analysis_eval.h"
+#include "factor_reduction_accuracy.h"
#include "sync_chain.h"
#include "sync_chain_lttv.h"
.hasArg= REQUIRED_ARG,
.optionHelp= "specify the algorithm to use for event analysis",
};
+static GString* reductionModulesNames;
+static ModuleOption optionSyncReduction= {
+ .longName= "sync-reduction",
+ .hasArg= REQUIRED_ARG,
+ .optionHelp= "specify the algorithm to use for factor reduction",
+};
static ModuleOption optionSyncGraphs= {
.longName= "sync-graphs",
.hasArg= NO_ARG,
static void init()
{
int retval;
+ unsigned int i;
+ const struct
+ {
+ GQueue* modules;
+ ModuleOption* option;
+ size_t nameOffset;
+ GString** names;
+ void (*gfAppendName)(gpointer data, gpointer user_data);
+ } loopValues[]= {
+ {&analysisModules, &optionSyncAnalysis, offsetof(AnalysisModule,
+ name), &analysisModulesNames, &gfAppendAnalysisName},
+ {&reductionModules, &optionSyncReduction, offsetof(ReductionModule,
+ name), &reductionModulesNames, &gfAppendReductionName},
+ };
g_debug("Sync init");
registerAnalysisLinReg();
registerAnalysisEval();
- g_assert(g_queue_get_length(&analysisModules) > 0);
- optionSyncAnalysis.arg= ((AnalysisModule*)
- g_queue_peek_head(&analysisModules))->name;
- analysisModulesNames= g_string_new("");
- g_queue_foreach(&analysisModules, &gfAppendAnalysisName,
- analysisModulesNames);
- // remove the last ", "
- g_string_truncate(analysisModulesNames, analysisModulesNames->len - 2);
- optionSyncAnalysis.argHelp= analysisModulesNames->str;
+ registerReductionAccuracy();
+
+ // Build module names lists for option and help string
+ for (i= 0; i < ARRAY_SIZE(loopValues); i++)
+ {
+ g_assert(g_queue_get_length(loopValues[i].modules) > 0);
+ loopValues[i].option->arg= (char*)(*(void**)
+ g_queue_peek_head(loopValues[i].modules) +
+ loopValues[i].nameOffset);
+ *loopValues[i].names= g_string_new("");
+ g_queue_foreach(loopValues[i].modules, loopValues[i].gfAppendName,
+ *loopValues[i].names);
+ // remove the last ", "
+ g_string_truncate(*loopValues[i].names, (*loopValues[i].names)->len -
+ 2);
+ loopValues[i].option->argHelp= (*loopValues[i].names)->str;
+ }
retval= snprintf(graphsDir, sizeof(graphsDir), "graphs-%d", getpid());
if (retval > sizeof(graphsDir) - 1)
g_queue_push_head(&moduleOptions, &optionSyncGraphsDir);
g_queue_push_head(&moduleOptions, &optionSyncGraphs);
+ g_queue_push_head(&moduleOptions, &optionSyncReduction);
g_queue_push_head(&moduleOptions, &optionSyncAnalysis);
g_queue_push_head(&moduleOptions, &optionSyncNull);
g_queue_push_head(&moduleOptions, &optionSyncStats);
g_queue_foreach(&moduleOptions, &gfRemoveModuleOption, NULL);
g_string_free(analysisModulesNames, TRUE);
+ g_string_free(reductionModulesNames, TRUE);
g_queue_clear(&processingModules);
g_queue_clear(&matchingModules);
g_queue_clear(&analysisModules);
+ g_queue_clear(&reductionModules);
g_queue_clear(&moduleOptions);
}
g_error("Analysis module '%s' not found", optionSyncAnalysis.arg);
}
+ syncState->reductionData= NULL;
+ result= g_queue_find_custom(&reductionModules, optionSyncReduction.arg,
+ &gcfCompareReduction);
+ if (result != NULL)
+ {
+ syncState->reductionModule= (ReductionModule*) result->data;
+ }
+ else
+ {
+ g_error("Reduction module '%s' not found", optionSyncReduction.arg);
+ }
+
syncState->processingModule->initProcessing(syncState, traceSetContext);
if (!optionSyncNull.present)
{
syncState->matchingModule->initMatching(syncState);
syncState->analysisModule->initAnalysis(syncState);
+ syncState->reductionModule->initReduction(syncState);
}
// Process traceset
// Obtain, reduce, adjust and set correction factors
allFactors= syncState->processingModule->finalizeProcessing(syncState);
- factors= reduceFactors(allFactors);
- freeAllFactors(allFactors);
+ factors= syncState->reductionModule->finalizeReduction(syncState,
+ allFactors);
+ freeAllFactors(allFactors, syncState->traceNb);
/* The offsets are adjusted so the lowest one is 0. This is done because
* of a Lttv specific limitation: events cannot have negative times. By
{
syncState->analysisModule->destroyAnalysis(syncState);
}
+ if (syncState->reductionModule != NULL)
+ {
+ syncState->reductionModule->destroyReduction(syncState);
+ }
free(syncState);
#include "event_analysis_chull.h"
#include "event_analysis_linreg.h"
#include "event_analysis_eval.h"
+#include "factor_reduction_accuracy.h"
#include "sync_chain.h"
.hasArg= REQUIRED_ARG,
.optionHelp= "Specify which algorithm to use for event analysis",
};
+static ModuleOption optionSyncReduction= {
+ .shortName= 'r',
+ .longName= "sync-reduction",
+ .hasArg= REQUIRED_ARG,
+ .optionHelp= "Specify which algorithm to use for factor reduction",
+};
/*
bool stats;
const char* testCaseName;
GString* analysisModulesNames;
+ GString* reductionModulesNames;
unsigned int id;
AllFactors* allFactors;
registerAnalysisLinReg();
registerAnalysisEval();
+ registerReductionAccuracy();
+
// Initialize data structures
syncState= malloc(sizeof(SyncState));
g_string_truncate(analysisModulesNames, analysisModulesNames->len - 2);
optionSyncAnalysis.argHelp= analysisModulesNames->str;
+ g_assert(g_queue_get_length(&reductionModules) > 0);
+ optionSyncReduction.arg= ((ReductionModule*)
+ g_queue_peek_head(&reductionModules))->name;
+ reductionModulesNames= g_string_new("Available modules: ");
+ g_queue_foreach(&reductionModules, &gfAppendReductionName,
+ reductionModulesNames);
+ // remove the last ", "
+ g_string_truncate(reductionModulesNames, reductionModulesNames->len - 2);
+ optionSyncReduction.argHelp= reductionModulesNames->str;
+
retval= snprintf(graphsDir, sizeof(graphsDir), "graphs-%d", getpid());
if (retval > sizeof(graphsDir) - 1)
{
}
optionSyncGraphs.arg= graphsDir;
+ g_queue_push_head(&moduleOptions, &optionSyncReduction);
g_queue_push_head(&moduleOptions, &optionSyncAnalysis);
g_queue_push_head(&moduleOptions, &optionSyncGraphs);
g_queue_push_head(&moduleOptions, &optionSyncStats);
testCaseName= processOptions(argc, argv);
g_string_free(analysisModulesNames, TRUE);
+ g_string_free(reductionModulesNames, TRUE);
if (optionSyncStats.present)
{
g_error("Analysis module '%s' not found", optionSyncAnalysis.arg);
}
+ syncState->reductionData= NULL;
+ result= g_queue_find_custom(&reductionModules, optionSyncReduction.arg,
+ &gcfCompareReduction);
+ if (result != NULL)
+ {
+ syncState->reductionModule= (ReductionModule*) result->data;
+ }
+ else
+ {
+ g_error("Reduction module '%s' not found", optionSyncReduction.arg);
+ }
+
// Initialize modules
syncState->processingModule->initProcessing(syncState, testCaseName);
syncState->matchingModule->initMatching(syncState);
syncState->analysisModule->initAnalysis(syncState);
+ syncState->reductionModule->initReduction(syncState);
// Process traceset
allFactors= syncState->processingModule->finalizeProcessing(syncState);
- factors= reduceFactors(allFactors);
- freeAllFactors(allFactors);
+ factors= syncState->reductionModule->finalizeReduction(syncState,
+ allFactors);
+ freeAllFactors(allFactors, syncState->traceNb);
// Write graphs file
if (syncState->graphsStream)
syncState->processingModule->destroyProcessing(syncState);
syncState->matchingModule->destroyMatching(syncState);
syncState->analysisModule->destroyAnalysis(syncState);
+ syncState->reductionModule->destroyReduction(syncState);
stats= syncState->stats;
free(syncState);
syncState->graphsDir= NULL;
}
+ syncState->reductionData= NULL;
+ syncState->reductionModule= NULL;
+
syncState->analysisData= NULL;
result= g_queue_find_custom(&analysisModules, "eval",
&gcfCompareAnalysis);
tracesetChainState= g_hash_table_lookup(tracesetChainStates, traceSetContext);
syncState= tracesetChainState->syncState;
- freeAllFactors(syncState->processingModule->finalizeProcessing(syncState));
+ freeAllFactors(syncState->processingModule->finalizeProcessing(syncState),
+ syncState->traceNb);
// Write graphs file
if (optionEvalGraphs)
{
syncState->analysisModule->destroyAnalysis(syncState);
}
+ if (syncState->reductionModule != NULL)
+ {
+ syncState->reductionModule->destroyReduction(syncState);
+ }
free(syncState);
projects / lttv.git / commitdiff
