From 0a87ec9a018cc9731ce3b04309eaa4dcc77df6d2 Mon Sep 17 00:00:00 2001 From: Benjamin Poirier Date: Mon, 22 Mar 2010 17:27:22 -0400 Subject: [PATCH] Perform trace factor reduction as a separate step This avoids duplicating the factor reduction (or "propagation") code in every analysis module. Instead, analysis modules return synchronization factors for every pair of traces and reduction is performed separately from the analysis. If a trace pair doesn't have factors but the inverse pair does (ie. no factors to convert the time from trace 1 to 0 but there are factors to convert the time from trace 0 to 1), the factors from the inverted pair are used (after being inverted themselves). Signed-off-by: Benjamin Poirier --- lttv/lttv/sync/data_structures.c | 106 ++++ lttv/lttv/sync/data_structures.h | 61 ++- lttv/lttv/sync/event_analysis.h | 2 +- lttv/lttv/sync/event_analysis_chull.c | 493 ++---------------- lttv/lttv/sync/event_analysis_chull.h | 98 ++-- lttv/lttv/sync/event_analysis_eval.c | 91 +--- lttv/lttv/sync/event_analysis_eval.h | 16 +- lttv/lttv/sync/event_analysis_linreg.c | 451 +--------------- lttv/lttv/sync/event_analysis_linreg.h | 10 - lttv/lttv/sync/event_matching.h | 2 +- lttv/lttv/sync/event_matching_broadcast.c | 6 +- lttv/lttv/sync/event_matching_distributor.c | 30 +- lttv/lttv/sync/event_matching_tcp.c | 6 +- lttv/lttv/sync/event_processing.h | 2 +- lttv/lttv/sync/event_processing_lttng_null.c | 10 +- .../sync/event_processing_lttng_standard.c | 6 +- lttv/lttv/sync/event_processing_text.c | 35 +- lttv/lttv/sync/event_processing_text.h | 4 +- lttv/lttv/sync/sync_chain.c | 309 +++++++++++ lttv/lttv/sync/sync_chain.h | 2 + lttv/lttv/sync/sync_chain_lttv.c | 7 +- lttv/lttv/sync/sync_chain_unittest.c | 22 +- lttv/modules/text/sync_chain_batch.c | 16 +- 23 files changed, 665 insertions(+), 1120 deletions(-) diff --git a/lttv/lttv/sync/data_structures.c b/lttv/lttv/sync/data_structures.c index a8cc337b..c0dafb07 100644 --- a/lttv/lttv/sync/data_structures.c +++ b/lttv/lttv/sync/data_structures.c @@ -40,6 +40,15 @@ #define SEQ_GT(a,b) ((int32_t)((a)-(b)) > 0) #define SEQ_GEQ(a,b) ((int32_t)((a)-(b)) >= 0) +const char* const approxNames[]= { + [EXACT]= "Exact", + [ACCURATE]= "Accurate", + [APPROXIMATE]= "Approximate", + [INCOMPLETE]= "Incomplete", + [ABSENT]= "Absent", + [SCREWED]= "Screwed", +}; + /* * Compare two ConnectionKey structures @@ -649,3 +658,100 @@ void gfAddEventToArray(gpointer data, gpointer user_data) { g_array_append_val((GArray*) user_data, data); } + + +/* + * Free a PairFactors + * + * Args: + * factorsCHull: container of Factors + */ +void destroyPairFactors(PairFactors* pairFactors) +{ + if (pairFactors->min != NULL) + { + free(pairFactors->min); + } + if (pairFactors->max != NULL) + { + free(pairFactors->max); + } + if (pairFactors->approx != NULL) + { + free(pairFactors->approx); + } +} + + +/* + * Create and initialize a container of PairFactors + * + * Args: + * traceNb: number of traces + * + * Returns: + * A new array, which can be freed with freeAllFactors() + */ +AllFactors* createAllFactors(const unsigned int traceNb) +{ + AllFactors* allFactors; + PairFactors** factorsArray; + unsigned int i, j; + + allFactors= malloc(sizeof(AllFactors)); + allFactors->traceNb= traceNb; + allFactors->refCount= 1; + allFactors->pairFactors= malloc(traceNb * sizeof(PairFactors*)); + factorsArray=allFactors->pairFactors; + for (i= 0; i < traceNb; i++) + { + factorsArray[i]= calloc(traceNb, sizeof(PairFactors)); + + for (j= 0; j < traceNb; j++) + { + if (i == j) + { + factorsArray[i][i].type= EXACT; + factorsArray[i][i].approx= malloc(sizeof(Factors)); + factorsArray[i][i].approx->drift= 1.; + factorsArray[i][i].approx->offset= 0.; + } + else + { + factorsArray[i][j].type= ABSENT; + } + } + } + + return allFactors; +} + + +/* + * Free a container of PairFactors + * + * Args: + * traceNb: number of traces + * allFactors: container of PairFactors + */ +void freeAllFactors(AllFactors* const allFactors) +{ + unsigned int i, j; + const unsigned int traceNb= allFactors->traceNb; + + allFactors->refCount--; + + if (allFactors->refCount == 0) + { + for (i= 0; i < traceNb; i++) + { + for (j= 0; j < traceNb; j++) + { + destroyPairFactors(&allFactors->pairFactors[i][j]); + } + free(allFactors->pairFactors[i]); + } + free(allFactors->pairFactors); + free(allFactors); + } +} diff --git a/lttv/lttv/sync/data_structures.h b/lttv/lttv/sync/data_structures.h index 7ed3bfc1..cc422a81 100644 --- a/lttv/lttv/sync/data_structures.h +++ b/lttv/lttv/sync/data_structures.h @@ -124,12 +124,65 @@ typedef struct GQueue* events; } Broadcast; -// One set of factors for each trace, this is the result of synchronization +// Stage 4: These structures contain correction factors +/* Correction factors for each trace, this is the final result of + * synchronization */ typedef struct { double drift, offset; } Factors; +// Correction factors between trace pairs, to be used for reduction +typedef enum +{ + EXACT, + /* Used for identity factors (a0= 0, a1= 1) that map a trace to itself. In + * this case, min, max and accuracy are NULL. + */ + + ACCURATE, + /* The approximation is the middle of the min and max limits. All fields + * are initialized. + */ + + APPROXIMATE, + /* min and max are not available. The approximation is a "best effort". + * min and max are NULL. + */ + + INCOMPLETE, + /* min or max is available but not both. approx and accuracy are not + * NULL. + */ + + ABSENT, + /* The pair of trace did not have communications in both directions (maybe + * even no communication at all). approx and accuracy are NULL. + */ + + SCREWED, + /* The algorithms are screwed. All fields may be NULL. + */ + + APPROX_NB, // This must be the last member +} ApproxType; + +extern const char* const approxNames[APPROX_NB]; + +typedef struct +{ + Factors* min, * max, * approx; + ApproxType type; + double accuracy; +} PairFactors; + +typedef struct +{ + unsigned int refCount; + unsigned int traceNb; + PairFactors** pairFactors; +} AllFactors; + // ConnectionKey-related functions guint ghfConnectionKeyHash(gconstpointer key); @@ -179,4 +232,10 @@ void destroyTCPExchange(Exchange* const exchange); void gdnDestroyBroadcast(gpointer data); void destroyBroadcast(Broadcast* const broadcast); +// Factor-related functions +void destroyPairFactors(PairFactors* factorsCHull); + +AllFactors* createAllFactors(const unsigned int traceNb); +void freeAllFactors(AllFactors* const allFactors); + #endif diff --git a/lttv/lttv/sync/event_analysis.h b/lttv/lttv/sync/event_analysis.h index 95f713e1..146b9b62 100644 --- a/lttv/lttv/sync/event_analysis.h +++ b/lttv/lttv/sync/event_analysis.h @@ -40,7 +40,7 @@ typedef struct exchange); void (*analyzeBroadcast)(struct _SyncState* const syncState, Broadcast* const broadcast); - GArray* (*finalizeAnalysis)(struct _SyncState* const syncState); + AllFactors* (*finalizeAnalysis)(struct _SyncState* const syncState); void (*printAnalysisStats)(struct _SyncState* const syncState); GraphFunctions graphFunctions; diff --git a/lttv/lttv/sync/event_analysis_chull.c b/lttv/lttv/sync/event_analysis_chull.c index 12c3d85f..1b15a030 100644 --- a/lttv/lttv/sync/event_analysis_chull.c +++ b/lttv/lttv/sync/event_analysis_chull.c @@ -54,7 +54,7 @@ static void destroyAnalysisCHull(SyncState* const syncState); static void analyzeMessageCHull(SyncState* const syncState, Message* const message); -static GArray* finalizeAnalysisCHull(SyncState* const syncState); +static AllFactors* finalizeAnalysisCHull(SyncState* const syncState); static void printAnalysisStatsCHull(SyncState* const syncState); static void writeAnalysisGraphsPlotsCHull(SyncState* const syncState, const unsigned int i, const unsigned int j); @@ -74,21 +74,13 @@ static double crossProductK(const Point const* p1, const Point const* p2, static Factors* calculateFactorsExact(GQueue* const cu, GQueue* const cl, const LineType lineType) __attribute__((pure)); static void calculateFactorsFallback(GQueue* const cr, GQueue* const cs, - FactorsCHull* const result); + PairFactors* const result); static double slope(const Point* const p1, const Point* const p2) __attribute__((pure)); static double intercept(const Point* const p1, const Point* const p2) __attribute__((pure)); -static GArray* reduceFactors(SyncState* const syncState, FactorsCHull** - allFactors); static double verticalDistance(Point* p1, Point* p2, Point* const point) __attribute__((pure)); -static void floydWarshall(SyncState* const syncState, FactorsCHull** const - allFactors, double*** const distances, unsigned int*** const - predecessors); -static void getFactors(FactorsCHull** const allFactors, unsigned int** const - predecessors, unsigned int* const references, const unsigned int traceNum, - Factors* const factors); static void gfPointDestroy(gpointer data, gpointer userData); @@ -105,15 +97,6 @@ static AnalysisModule analysisModuleCHull= { } }; -const char* const approxNames[]= { - [EXACT]= "Exact", - [MIDDLE]= "Middle", - [FALLBACK]= "Fallback", - [INCOMPLETE]= "Incomplete", - [ABSENT]= "Absent", - [SCREWED]= "Screwed", -}; - /* * Analysis module registering function @@ -348,10 +331,7 @@ static void destroyAnalysisCHull(SyncState* const syncState) if (syncState->stats) { - if (analysisData->stats->allFactors != NULL) - { - freeAllFactors(syncState->traceNb, analysisData->stats->allFactors); - } + freeAllFactors(analysisData->stats->allFactors); free(analysisData->stats); } @@ -363,10 +343,7 @@ static void destroyAnalysisCHull(SyncState* const syncState) closeGraphFiles(syncState); } - if (!syncState->stats && analysisData->graphsData->allFactors != NULL) - { - freeAllFactors(syncState->traceNb, analysisData->graphsData->allFactors); - } + freeAllFactors(analysisData->graphsData->allFactors); free(analysisData->graphsData); } @@ -501,13 +478,13 @@ static void grahamScan(GQueue* const hull, Point* const newPoint, const * syncState container for synchronization data. * * Returns: - * Factors[traceNb] synchronization factors for each trace + * AllFactors* synchronization factors for each trace pair, the caller is + * responsible for freeing the structure */ -static GArray* finalizeAnalysisCHull(SyncState* const syncState) +static AllFactors* finalizeAnalysisCHull(SyncState* const syncState) { AnalysisDataCHull* analysisData; - GArray* factors; - FactorsCHull** allFactors; + AllFactors* allFactors; analysisData= (AnalysisDataCHull*) syncState->analysisData; @@ -519,26 +496,19 @@ static GArray* finalizeAnalysisCHull(SyncState* const syncState) allFactors= calculateAllFactors(syncState); - factors= reduceFactors(syncState, allFactors); - - if (syncState->stats || syncState->graphsStream) + if (syncState->stats) { - if (syncState->stats) - { - analysisData->stats->allFactors= allFactors; - } - - if (syncState->graphsStream) - { - analysisData->graphsData->allFactors= allFactors; - } + allFactors->refCount++; + analysisData->stats->allFactors= allFactors; } - else + + if (syncState->graphsStream) { - freeAllFactors(syncState->traceNb, allFactors); + allFactors->refCount++; + analysisData->graphsData->allFactors= allFactors; } - return factors; + return allFactors; } @@ -583,9 +553,9 @@ static void printAnalysisStatsCHull(SyncState* const syncState) { for (j= i + 1; j < syncState->traceNb; j++) { - FactorsCHull* factorsCHull; + PairFactors* factorsCHull; - factorsCHull= &analysisData->stats->allFactors[j][i]; + factorsCHull= &analysisData->stats->allFactors->pairFactors[j][i]; printf("\t\t%3d - %-3d: %s", i, j, approxNames[factorsCHull->type]); @@ -596,20 +566,16 @@ static void printAnalysisStatsCHull(SyncState* const syncState) factorsCHull->approx->drift < 0. ? '-' : '+', fabs(factorsCHull->approx->drift)); } - else if (factorsCHull->type == MIDDLE) + else if (factorsCHull->type == ACCURATE) { - printf(" a0= % 7g a1= 1 %c %7g accuracy %7g\n", - factorsCHull->approx->offset, factorsCHull->approx->drift - - 1. < 0. ? '-' : '+', fabs(factorsCHull->approx->drift - - 1.), factorsCHull->accuracy); - printf("\t\t a0: % 7g to % 7g (delta= %7g)\n", + printf("\n\t\t a0: % 7g to % 7g (delta= %7g)\n", factorsCHull->max->offset, factorsCHull->min->offset, factorsCHull->min->offset - factorsCHull->max->offset); printf("\t\t a1: 1 %+7g to %+7g (delta= %7g)\n", factorsCHull->min->drift - 1., factorsCHull->max->drift - 1., factorsCHull->max->drift - factorsCHull->min->drift); } - else if (factorsCHull->type == FALLBACK) + else if (factorsCHull->type == APPROXIMATE) { printf(" a0= % 7g a1= 1 %c %7g error= %7g\n", factorsCHull->approx->offset, factorsCHull->approx->drift @@ -742,64 +708,6 @@ static double crossProductK(const Point const* p1, const Point const* p2, } -/* - * Free a container of FactorsCHull - * - * Args: - * traceNb: number of traces - * allFactors: container of FactorsCHull - */ -void freeAllFactors(const unsigned int traceNb, FactorsCHull** const - allFactors) -{ - unsigned int i, j; - - for (i= 0; i < traceNb; i++) - { - for (j= 0; j <= i; j++) - { - destroyFactorsCHull(&allFactors[i][j]); - } - free(allFactors[i]); - } - free(allFactors); -} - - -/* - * Free a FactorsCHull - * - * Args: - * factorsCHull: container of Factors - */ -void destroyFactorsCHull(FactorsCHull* factorsCHull) -{ - if (factorsCHull->type == MIDDLE || factorsCHull->type == - INCOMPLETE || factorsCHull->type == ABSENT) - { - free(factorsCHull->min); - free(factorsCHull->max); - } - else if (factorsCHull->type == SCREWED) - { - if (factorsCHull->min != NULL) - { - free(factorsCHull->min); - } - if (factorsCHull->max != NULL) - { - free(factorsCHull->max); - } - } - - if (factorsCHull->type == EXACT || factorsCHull->type == MIDDLE || - factorsCHull->type == FALLBACK) - { - free(factorsCHull->approx); - } -} - - /* * Analyze the convex hulls to determine the synchronization factors between * each pair of trace. @@ -808,28 +716,21 @@ void destroyFactorsCHull(FactorsCHull* factorsCHull) * syncState container for synchronization data. * * Returns: - * FactorsCHull*[TraceNum][TraceNum] array. See the documentation for the - * member allFactors of AnalysisStatsCHull. + * AllFactors*, see the documentation for the member allFactors of + * AnalysisStatsCHull. */ -FactorsCHull** calculateAllFactors(SyncState* const syncState) +AllFactors* calculateAllFactors(SyncState* const syncState) { unsigned int traceNumA, traceNumB; - FactorsCHull** allFactors; + AllFactors* allFactors; AnalysisDataCHull* analysisData; analysisData= (AnalysisDataCHull*) syncState->analysisData; // Allocate allFactors and calculate min and max - allFactors= malloc(syncState->traceNb * sizeof(FactorsCHull*)); + allFactors= createAllFactors(syncState->traceNb); for (traceNumA= 0; traceNumA < syncState->traceNb; traceNumA++) { - allFactors[traceNumA]= malloc((traceNumA + 1) * sizeof(FactorsCHull)); - - allFactors[traceNumA][traceNumA].type= EXACT; - allFactors[traceNumA][traceNumA].approx= malloc(sizeof(Factors)); - allFactors[traceNumA][traceNumA].approx->drift= 1.; - allFactors[traceNumA][traceNumA].approx->offset= 0.; - for (traceNumB= 0; traceNumB < traceNumA; traceNumB++) { unsigned int i; @@ -839,8 +740,8 @@ FactorsCHull** calculateAllFactors(SyncState* const syncState) LineType lineType; size_t factorsOffset; } loopValues[]= { - {MINIMUM, offsetof(FactorsCHull, min)}, - {MAXIMUM, offsetof(FactorsCHull, max)} + {MINIMUM, offsetof(PairFactors, min)}, + {MAXIMUM, offsetof(PairFactors, max)} }; cr= analysisData->hullArray[traceNumB][traceNumA]; @@ -848,12 +749,14 @@ FactorsCHull** calculateAllFactors(SyncState* const syncState) for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++) { - g_debug("allFactors[%u][%u].%s = calculateFactorsExact(cr= hullArray[%u][%u], cs= hullArray[%u][%u], %s)", + g_debug("allFactors[%u][%u].%s = calculateFactorsExact(cr= " + "hullArray[%u][%u], cs= hullArray[%u][%u], %s)", traceNumA, traceNumB, loopValues[i].factorsOffset == - offsetof(FactorsCHull, min) ? "min" : "max", traceNumB, + offsetof(PairFactors, min) ? "min" : "max", traceNumB, traceNumA, traceNumA, traceNumB, loopValues[i].lineType == MINIMUM ? "MINIMUM" : "MAXIMUM"); - *((Factors**) ((void*) &allFactors[traceNumA][traceNumB] + + *((Factors**) ((void*) + &allFactors->pairFactors[traceNumA][traceNumB] + loopValues[i].factorsOffset))= calculateFactorsExact(cr, cs, loopValues[i].lineType); } @@ -865,22 +768,22 @@ FactorsCHull** calculateAllFactors(SyncState* const syncState) { for (traceNumB= 0; traceNumB < traceNumA; traceNumB++) { - FactorsCHull* factorsCHull; + PairFactors* factorsCHull; - factorsCHull= &allFactors[traceNumA][traceNumB]; + factorsCHull= &allFactors->pairFactors[traceNumA][traceNumB]; if (factorsCHull->min == NULL && factorsCHull->max == NULL) { - factorsCHull->type= FALLBACK; + factorsCHull->type= APPROXIMATE; calculateFactorsFallback(analysisData->hullArray[traceNumB][traceNumA], analysisData->hullArray[traceNumA][traceNumB], - &allFactors[traceNumA][traceNumB]); + &allFactors->pairFactors[traceNumA][traceNumB]); } else if (factorsCHull->min != NULL && factorsCHull->max != NULL) { if (factorsCHull->min->drift != -INFINITY && factorsCHull->max->drift != INFINITY) { - factorsCHull->type= MIDDLE; + factorsCHull->type= ACCURATE; calculateFactorsMiddle(factorsCHull); } else if (factorsCHull->min->drift != -INFINITY || @@ -921,7 +824,7 @@ FactorsCHull** calculateAllFactors(SyncState* const syncState) * Args: * factors: contains the min and max limits, used to store the result */ -void calculateFactorsMiddle(FactorsCHull* const factors) +void calculateFactorsMiddle(PairFactors* const factors) { double amin, amax, bmin, bmax, bhat; @@ -1117,7 +1020,7 @@ static Factors* calculateFactorsExact(GQueue* const cu, GQueue* const cl, const * will be stored */ static void calculateFactorsFallback(GQueue* const cr, GQueue* const cs, - FactorsCHull* const result) + PairFactors* const result) { unsigned int i, j, k; double errorMin; @@ -1224,314 +1127,6 @@ static double intercept(const Point* const p1, const Point* const p2) } -/* - * 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 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* 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); - } - } -} - - /* * Write the analysis-specific graph lines in the gnuplot script. * @@ -1544,7 +1139,7 @@ void writeAnalysisGraphsPlotsCHull(SyncState* const syncState, const unsigned int i, const unsigned int j) { AnalysisDataCHull* analysisData; - FactorsCHull* factorsCHull; + PairFactors* factorsCHull; analysisData= (AnalysisDataCHull*) syncState->analysisData; @@ -1557,7 +1152,7 @@ void writeAnalysisGraphsPlotsCHull(SyncState* const syncState, const unsigned "linecolor rgb \"#003366\" linetype 4 pointtype 10 pointsize 0.8, \\\n", i, j); - factorsCHull= &analysisData->graphsData->allFactors[j][i]; + factorsCHull= &analysisData->graphsData->allFactors->pairFactors[j][i]; if (factorsCHull->type == EXACT) { fprintf(syncState->graphsStream, @@ -1566,7 +1161,7 @@ void writeAnalysisGraphsPlotsCHull(SyncState* const syncState, const unsigned "linecolor rgb \"black\" linetype 1, \\\n", factorsCHull->approx->offset, factorsCHull->approx->drift); } - else if (factorsCHull->type == MIDDLE) + else if (factorsCHull->type == ACCURATE) { fprintf(syncState->graphsStream, "\t%.2f + %.10f * x " @@ -1584,7 +1179,7 @@ void writeAnalysisGraphsPlotsCHull(SyncState* const syncState, const unsigned "linecolor rgb \"black\" linetype 1, \\\n", factorsCHull->approx->offset, factorsCHull->approx->drift); } - else if (factorsCHull->type == FALLBACK) + else if (factorsCHull->type == APPROXIMATE) { fprintf(syncState->graphsStream, "\t%.2f + %.10f * x " diff --git a/lttv/lttv/sync/event_analysis_chull.h b/lttv/lttv/sync/event_analysis_chull.h index c96dcae2..c1286d66 100644 --- a/lttv/lttv/sync/event_analysis_chull.h +++ b/lttv/lttv/sync/event_analysis_chull.h @@ -29,63 +29,12 @@ typedef struct } Point; -typedef enum -{ - EXACT, - /* Used for identity factors (a0= 0, a1= 1) that map a trace to itself. In - * this case, min, max and accuracy are not initialized. - */ - - MIDDLE, - /* The approximation is the middle of the min and max limits, all fields - * are initialized. - */ - - FALLBACK, - /* min and max are not available because the hulls do not respect - * assumptions (hulls should not intersect and the upper half-hull should - * be below the lower half-hull). The approximation is a "best effort". - * All fields are initialized but min and max are NULL. - */ - - INCOMPLETE, - /* min or max is available but not both. The hulls respected assumptions - * but all receives took place after all sends or vice versa. approx and - * accuracy are not initialized. - */ - - ABSENT, - /* The pair of trace did not have communications in both directions (maybe - * even no communication at all). approx and accuracy are not initialized. - */ - - SCREWED, - /* min and max are not available because the algorithms are screwed. One - * of min or max (but not both) is NULL. The other is initialized. Approx - * is not initialized. - */ - - APPROX_NB, // This must be the last member -} ApproxType; - -extern const char* const approxNames[APPROX_NB]; - -typedef struct -{ - Factors* min, * max, * approx; - ApproxType type; - double accuracy; -} FactorsCHull; - - typedef struct { unsigned int dropped; - /* FactorsCHull allFactors[traceNb][traceNb] - * - * allFactors is divided into three parts depending on the position of an - * element allFactors[i][j]: + /* allFactors is divided into three parts depending on the position of an + * element allFactors->pairFactors[i][j]: * Lower triangular part of the matrix * i > j * This contains the factors between nodes i and j. These factors @@ -95,9 +44,36 @@ typedef struct * This contains identity factors (a0= 0, a1= 1). * Upper triangular part of the matrix * i < j - * This area is not allocated. + * These factors are absent + * + * Factor types are used as follows: + * EXACT, + * Used for identity factors (a0= 0, a1= 1) that map a trace to itself. In + * this case, min, max and accuracy are not initialized. + * + * ACCURATE, + * The approximation is the middle of the min and max limits. + * + * APPROXIMATE, + * min and max are not available because the hulls do not respect + * assumptions (hulls should not intersect and the upper half-hull should + * be below the lower half-hull). The approximation is a "best effort". + * All fields are initialized but min and max are NULL. + * + * INCOMPLETE, + * min or max is available but not both. The hulls respected assumptions + * but all receives took place after all sends or vice versa. + * + * ABSENT, + * The pair of trace did not have communications in both directions (maybe + * even no communication at all). Also used for factors in the upper + * triangular matrix. + * + * SCREWED, + * min and max are not available because the algorithms are screwed. One + * of min or max (but not both) is NULL. The other is initialized. */ - FactorsCHull** allFactors; + AllFactors* allFactors; } AnalysisStatsCHull; @@ -114,10 +90,9 @@ typedef struct */ FILE*** hullPoints; - /* FactorsCHull allFactors[traceNb][traceNb] - * This is the same array as AnalysisStatsCHull.allFactors. + /* This is the same array as AnalysisStatsCHull.allFactors. */ - FactorsCHull** allFactors; + AllFactors* allFactors; } AnalysisGraphsDataCHull; @@ -170,11 +145,8 @@ typedef struct void registerAnalysisCHull(); -FactorsCHull** calculateAllFactors(struct _SyncState* const syncState); -void freeAllFactors(const unsigned int traceNb, FactorsCHull** const - allFactors); +AllFactors* calculateAllFactors(struct _SyncState* const syncState); -void calculateFactorsMiddle(FactorsCHull* const factors); -void destroyFactorsCHull(FactorsCHull* factorsCHull); +void calculateFactorsMiddle(PairFactors* const factors); #endif diff --git a/lttv/lttv/sync/event_analysis_eval.c b/lttv/lttv/sync/event_analysis_eval.c index 45bad57c..27d877d8 100644 --- a/lttv/lttv/sync/event_analysis_eval.c +++ b/lttv/lttv/sync/event_analysis_eval.c @@ -65,7 +65,7 @@ static void analyzeExchangeEval(SyncState* const syncState, Exchange* const exchange); static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const broadcast); -static GArray* finalizeAnalysisEval(SyncState* const syncState); +static AllFactors* finalizeAnalysisEval(SyncState* const syncState); static void printAnalysisStatsEval(SyncState* const syncState); static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState, const unsigned int i, const unsigned int j); @@ -117,9 +117,8 @@ static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const upperHull); static void gfLPAddRow(gpointer data, gpointer user_data); static Factors* calculateFactors(glp_prob* const lp, const int direction); -static void calculateCompleteFactors(glp_prob* const lp, FactorsCHull* +static void calculateCompleteFactors(glp_prob* const lp, PairFactors* factors); -static FactorsCHull** createAllFactors(const unsigned int traceNb); static inline void finalizeAnalysisEvalLP(SyncState* const syncState); static void gfAddAbsiscaToArray(gpointer data, gpointer user_data); static gint gcfCompareDouble(gconstpointer a, gconstpointer b); @@ -558,8 +557,8 @@ static void destroyAnalysisEval(SyncState* const syncState) g_hash_table_destroy(stats->exchangeRtt); #ifdef HAVE_LIBGLPK - freeAllFactors(syncState->traceNb, stats->chFactorsArray); - freeAllFactors(syncState->traceNb, stats->lpFactorsArray); + freeAllFactors(stats->chFactorsArray); + freeAllFactors(stats->lpFactorsArray); #endif free(stats); @@ -597,7 +596,7 @@ static void destroyAnalysisEval(SyncState* const syncState) if (!syncState->stats) { - freeAllFactors(syncState->traceNb, graphs->lpFactorsArray); + freeAllFactors(graphs->lpFactorsArray); } #endif @@ -896,19 +895,17 @@ static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const /* * Finalize the factor calculations. Since this module does not really - * calculate factors, identity factors are returned. Instead, histograms are + * calculate factors, absent factors are returned. Instead, histograms are * written out and histogram structures are freed. * * Args: * syncState container for synchronization data. * * Returns: - * Factors[traceNb] identity factors for each trace + * AllFactors* synchronization factors for each trace pair */ -static GArray* finalizeAnalysisEval(SyncState* const syncState) +static AllFactors* finalizeAnalysisEval(SyncState* const syncState) { - GArray* factors; - unsigned int i; AnalysisDataEval* analysisData= syncState->analysisData; if (syncState->graphsStream && analysisData->graphs->histograms) @@ -922,19 +919,7 @@ static GArray* finalizeAnalysisEval(SyncState* const syncState) finalizeAnalysisEvalLP(syncState); - 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++) - { - Factors* e; - - e= &g_array_index(factors, Factors, i); - e->drift= 1.; - e->offset= 0.; - } - - return factors; + return createAllFactors(syncState->traceNb); } @@ -1048,13 +1033,15 @@ static void printAnalysisStatsEval(SyncState* const syncState) { for (j= 0; j < i; j++) { - FactorsCHull* chFactors= &analysisData->stats->chFactorsArray[i][j]; - FactorsCHull* lpFactors= &analysisData->stats->lpFactorsArray[i][j]; + PairFactors* chFactors= + &analysisData->stats->chFactorsArray->pairFactors[i][j]; + PairFactors* lpFactors= + &analysisData->stats->lpFactorsArray->pairFactors[i][j]; printf("\t\t%3d - %-3d ", i, j); if (lpFactors->type == chFactors->type) { - if (lpFactors->type == MIDDLE) + if (lpFactors->type == ACCURATE) { printf("%-13s %-10.4g %-10.4g %-10.4g %.4g\n", approxNames[lpFactors->type], @@ -1721,18 +1708,18 @@ static Factors* calculateFactors(glp_prob* const lp, const int direction) * initialized. * * Returns: - * Please note that the approximation type may be MIDDLE, INCOMPLETE or + * Please note that the approximation type may be ACCURATE, INCOMPLETE or * ABSENT. Unlike in analysis_chull, ABSENT is also used when the hulls do * not respect assumptions. */ -static void calculateCompleteFactors(glp_prob* const lp, FactorsCHull* factors) +static void calculateCompleteFactors(glp_prob* const lp, PairFactors* factors) { factors->min= calculateFactors(lp, GLP_MIN); factors->max= calculateFactors(lp, GLP_MAX); if (factors->min && factors->max) { - factors->type= MIDDLE; + factors->type= ACCURATE; calculateFactorsMiddle(factors); } else if (factors->min || factors->max) @@ -1748,35 +1735,6 @@ static void calculateCompleteFactors(glp_prob* const lp, FactorsCHull* factors) } -/* - * Create and initialize an array like AnalysisStatsCHull.allFactors - * - * Args: - * traceNb: number of traces - * - * Returns: - * A new array, which can be freed with freeAllFactors() - */ -static FactorsCHull** createAllFactors(const unsigned int traceNb) -{ - FactorsCHull** factorsArray; - unsigned int i; - - factorsArray= malloc(traceNb * sizeof(FactorsCHull*)); - for (i= 0; i < traceNb; i++) - { - factorsArray[i]= calloc((i + 1), sizeof(FactorsCHull)); - - factorsArray[i][i].type= EXACT; - factorsArray[i][i].approx= malloc(sizeof(Factors)); - factorsArray[i][i].approx->drift= 1.; - factorsArray[i][i].approx->offset= 0.; - } - - return factorsArray; -} - - /* * A GFunc for g_queue_foreach() * @@ -1841,7 +1799,7 @@ static void finalizeAnalysisEvalLP(SyncState* const syncState) #ifdef HAVE_LIBGLPK unsigned int i, j; AnalysisDataCHull* chAnalysisData= analysisData->chullSS->analysisData; - FactorsCHull** lpFactorsArray; + AllFactors* lpFactorsArray; if (!syncState->stats && !syncState->graphsStream) { @@ -1888,7 +1846,7 @@ static void finalizeAnalysisEvalLP(SyncState* const syncState) // Use the LP problem to find the correction factors for this pair of // traces - calculateCompleteFactors(lp, &lpFactorsArray[i][j]); + calculateCompleteFactors(lp, &lpFactorsArray->pairFactors[i][j]); if (syncState->graphsStream) { @@ -1902,8 +1860,7 @@ static void finalizeAnalysisEvalLP(SyncState* const syncState) } #endif - g_array_free(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS), - TRUE); + freeAllFactors(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS)); } @@ -1929,10 +1886,10 @@ static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState, AnalysisGraphsEval* graphs= analysisData->graphs; GQueue*** hullArray= ((AnalysisDataCHull*) analysisData->chullSS->analysisData)->hullArray; - FactorsCHull* lpFactors= &graphs->lpFactorsArray[j][i]; + PairFactors* lpFactors= &graphs->lpFactorsArray->pairFactors[j][i]; glp_prob* lp= graphs->lps[j][i]; - if (lpFactors->type == MIDDLE) + if (lpFactors->type == ACCURATE) { int retval; char* cwd; @@ -2026,8 +1983,8 @@ static void writeAnalysisTraceTimeForePlotsEval(SyncState* const syncState, { #ifdef HAVE_LIBGLPK if (((AnalysisDataEval*) - syncState->analysisData)->graphs->lpFactorsArray[j][i].type == - MIDDLE) + syncState->analysisData)->graphs->lpFactorsArray->pairFactors[j][i].type + == ACCURATE) { fprintf(syncState->graphsStream, "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" " diff --git a/lttv/lttv/sync/event_analysis_eval.h b/lttv/lttv/sync/event_analysis_eval.h index eca5da9d..dbd4ac95 100644 --- a/lttv/lttv/sync/event_analysis_eval.h +++ b/lttv/lttv/sync/event_analysis_eval.h @@ -63,13 +63,9 @@ typedef struct GHashTable* exchangeRtt; #ifdef HAVE_LIBGLPK - /* FactorsCHull** chFactorsArray[traceNum][traceNum] - * FactorsCHull** lpFactorsArray[traceNum][traceNum] - * - * As usual, only the lower triangular part of theses matrixes is - * allocated */ - FactorsCHull** chFactorsArray; - FactorsCHull** lpFactorsArray; + // Only the lower triangular part of theses matrixes is used + AllFactors* chFactorsArray; + AllFactors* lpFactorsArray; #endif } AnalysisStatsEval; @@ -136,11 +132,9 @@ typedef struct * lps[i][j] where i > j */ glp_prob*** lps; - /* Factors lpFactors[traceNum][traceNum] - * - * Only the lower triangular part of the matrix is allocated, that is + /* Only the lower triangular part of the matrix is allocated, that is * lpFactorsArray[i][j] where i > j */ - FactorsCHull** lpFactorsArray; + AllFactors* lpFactorsArray; #endif } AnalysisGraphsEval; diff --git a/lttv/lttv/sync/event_analysis_linreg.c b/lttv/lttv/sync/event_analysis_linreg.c index bda89874..165f84e2 100644 --- a/lttv/lttv/sync/event_analysis_linreg.c +++ b/lttv/lttv/sync/event_analysis_linreg.c @@ -36,27 +36,13 @@ static void initAnalysisLinReg(SyncState* const syncState); static void destroyAnalysisLinReg(SyncState* const syncState); static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const exchange); -static GArray* finalizeAnalysisLinReg(SyncState* const syncState); +static AllFactors* finalizeAnalysisLinReg(SyncState* const syncState); static void printAnalysisStatsLinReg(SyncState* const syncState); static void writeAnalysisGraphsPlotsLinReg(SyncState* const syncState, const unsigned int i, const unsigned int j); // Functions specific to this module static void finalizeLSA(SyncState* const syncState); -static void doGraphProcessing(SyncState* const syncState); -static GArray* calculateFactors(SyncState* const syncState); -static void shortestPath(Fit* const* const fitArray, const unsigned int - traceNum, const unsigned int traceNb, double* const distances, - unsigned int* const previousVertex); -static double sumDistances(const double* const distances, const unsigned int - traceNb); -static void reduceFactors(Fit* const* const fitArray, const unsigned int* const - previousVertex, const unsigned int traceNum, double* const drift, - double* const offset, double* const stDev); - -// Graph-related Glib functions -static void gfGraphDestroy(gpointer data, gpointer user_data); -static gint gcfGraphTraceCompare(gconstpointer a, gconstpointer b); static AnalysisModule analysisModuleLinReg= { @@ -146,9 +132,6 @@ static void destroyAnalysisLinReg(SyncState* const syncState) } free(analysisData->fitArray); - g_queue_foreach(analysisData->graphList, &gfGraphDestroy, NULL); - g_queue_free(analysisData->graphList); - if (syncState->stats) { free(analysisData->stDev); @@ -224,24 +207,38 @@ static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const ex * syncState container for synchronization data. * * Returns: - * Factors[traceNb] synchronization factors for each trace + * AllFactors* synchronization factors for each trace pair */ -static GArray* finalizeAnalysisLinReg(SyncState* const syncState) +static AllFactors* finalizeAnalysisLinReg(SyncState* const syncState) { - GArray* factors; + AllFactors* result; + unsigned int i, j; + AnalysisDataLinReg* analysisData= (AnalysisDataLinReg*) + syncState->analysisData; - // Finalize the processing finalizeLSA(syncState); - // Find a reference node and structure nodes in a graph - doGraphProcessing(syncState); + result= createAllFactors(syncState->traceNb); - /* Calculate the resulting offset and drift between each trace and its - * reference - */ - factors= calculateFactors(syncState); + for (i= 0; i < syncState->traceNb; i++) + { + for (j= 0; j < syncState->traceNb; j++) + { + if (i != j) + { + Fit* fit; + + fit= &analysisData->fitArray[i][j]; + result->pairFactors[i][j].type= APPROXIMATE; + result->pairFactors[i][j].approx= malloc(sizeof(Factors)); + result->pairFactors[i][j].approx->drift= 1. + fit->x; + result->pairFactors[i][j].approx->offset= fit->d0; + result->pairFactors[i][j].accuracy= fit->e; + } + } + } - return factors; + return result; } @@ -285,39 +282,6 @@ static void printAnalysisStatsLinReg(SyncState* const syncState) 0. ? '-' : '+', fabs(fit->x), fit->e); } } - - printf("\tTree:\n"); - for (i= 0; i < syncState->traceNb; i++) - { - GList* result; - - result= g_queue_find_custom(analysisData->graphList, &i, - &gcfGraphTraceCompare); - if (result != NULL) - { - Graph* graph; - - graph= (Graph*) result->data; - - printf("\t\ttrace %u reference %u previous vertex ", i, - graph->reference); - - if (i == graph->reference) - { - printf("- "); - } - else - { - printf("%u ", graph->previousVertex[i]); - } - - printf("stdev= %g\n", analysisData->stDev[i]); - } - else - { - g_error("Trace %d not part of a graph\n", i); - } - } } @@ -366,369 +330,6 @@ static void finalizeLSA(SyncState* const syncState) } -/* - * Structure nodes in graphs of nodes that had exchanges. Each graph has a - * reference node, the one that can reach the others with the smallest - * cummulative error. - * - * Args: - * syncState: container for synchronization data. - * This function allocates these analysisData members: - * graphList - */ -static void doGraphProcessing(SyncState* const syncState) -{ - unsigned int i, j; - double* distances; - unsigned int* previousVertex; - AnalysisDataLinReg* analysisData; - - analysisData= (AnalysisDataLinReg*) syncState->analysisData; - - distances= malloc(syncState->traceNb * sizeof(double)); - previousVertex= malloc(syncState->traceNb * sizeof(unsigned int)); - analysisData->graphList= g_queue_new(); - - for (i= 0; i < syncState->traceNb; i++) - { - double errorSum; - GList* result; - - // Perform shortest path search - g_debug("shortest path trace %d, distances: ", i); - shortestPath(analysisData->fitArray, i, syncState->traceNb, distances, - previousVertex); - - for (j= 0; j < syncState->traceNb; j++) - { - g_debug("%g, ", distances[j]); - } - g_debug("previousVertex: "); - for (j= 0; j < syncState->traceNb; j++) - { - g_debug("%u, ", previousVertex[j]); - } - - // Group in graphs nodes that have exchanges - errorSum= sumDistances(distances, syncState->traceNb); - result= g_queue_find_custom(analysisData->graphList, &i, - &gcfGraphTraceCompare); - if (result != NULL) - { - Graph* graph; - - g_debug("found graph"); - graph= (Graph*) result->data; - if (errorSum < graph->errorSum) - { - g_debug("new reference"); - graph->errorSum= errorSum; - free(graph->previousVertex); - graph->previousVertex= previousVertex; - graph->reference= i; - previousVertex= malloc(syncState->traceNb * sizeof(unsigned - int)); - } - } - else - { - Graph* newGraph; - - g_debug("creating new graph"); - newGraph= malloc(sizeof(Graph)); - newGraph->errorSum= errorSum; - newGraph->previousVertex= previousVertex; - newGraph->reference= i; - previousVertex= malloc(syncState->traceNb * sizeof(unsigned int)); - - g_queue_push_tail(analysisData->graphList, newGraph); - } - } - - free(previousVertex); - free(distances); -} - - -/* - * Calculate the resulting offset and drift between each trace and its - * reference. - * - * Args: - * syncState: container for synchronization data. - * - * Returns: - * Factors[traceNb] synchronization factors for each trace - */ -static GArray* calculateFactors(SyncState* const syncState) -{ - unsigned int i; - AnalysisDataLinReg* analysisData; - GArray* factors; - - analysisData= (AnalysisDataLinReg*) syncState->analysisData; - factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors), - syncState->traceNb); - g_array_set_size(factors, syncState->traceNb); - - // Calculate the resulting offset and drift between each trace and its - // reference - for (i= 0; i < syncState->traceNb; i++) - { - GList* result; - - result= g_queue_find_custom(analysisData->graphList, &i, - &gcfGraphTraceCompare); - if (result != NULL) - { - Graph* graph; - double stDev; - Factors* traceFactors; - - graph= (Graph*) result->data; - traceFactors= &g_array_index(factors, Factors, i); - - reduceFactors(analysisData->fitArray, graph->previousVertex, i, - &traceFactors->drift, &traceFactors->offset, &stDev); - - if (syncState->stats) - { - analysisData->stDev[i]= stDev; - } - } - else - { - g_error("Trace %d not part of a graph\n", i); - } - } - - return factors; -} - - -/* - * Single-source shortest path search to find the path with the lowest error to - * convert one node's time to another. - * Uses Dijkstra's algorithm - * - * Args: - * fitArray: array with the regression parameters - * traceNum: reference node - * traceNb: number of traces = number of nodes - * distances: array of computed distance from source node to node i, - * INFINITY if i is unreachable, preallocated to the number of - * nodes - * previousVertex: previous vertex from a node i on the way to the source, - * UINT_MAX if i is not on the way or is the source, - * preallocated to the number of nodes - */ -static void shortestPath(Fit* const* const fitArray, const unsigned int - traceNum, const unsigned int traceNb, double* const distances, unsigned - int* const previousVertex) -{ - bool* visited; - unsigned int i, j; - - visited= malloc(traceNb * sizeof(bool)); - - for (i= 0; i < traceNb; i++) - { - const Fit* fit; - - visited[i]= false; - - fit= &fitArray[traceNum][i]; - g_debug("fitArray[traceNum= %u][i= %u]->n = %u", traceNum, i, fit->n); - if (fit->n > 0) - { - distances[i]= fit->e; - previousVertex[i]= traceNum; - } - else - { - distances[i]= INFINITY; - previousVertex[i]= UINT_MAX; - } - } - visited[traceNum]= true; - - for (j= 0; j < traceNb; j++) - { - g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]); - } - - for (i= 0; i < traceNb - 2; i++) - { - unsigned int v; - double dvMin; - - dvMin= INFINITY; - for (j= 0; j < traceNb; j++) - { - if (visited[j] == false && distances[j] < dvMin) - { - v= j; - dvMin= distances[j]; - } - } - - g_debug("v= %u dvMin= %g", v, dvMin); - - if (dvMin != INFINITY) - { - visited[v]= true; - - for (j= 0; j < traceNb; j++) - { - const Fit* fit; - - fit= &fitArray[v][j]; - if (visited[j] == false && fit->n > 0 && distances[v] + fit->e - < distances[j]) - { - distances[j]= distances[v] + fit->e; - previousVertex[j]= v; - } - } - } - else - { - break; - } - - for (j= 0; j < traceNb; j++) - { - g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]); - } - } - - free(visited); -} - - -/* - * Cummulate the distances between a reference node and the other nodes - * reachable from it in a graph. - * - * Args: - * distances: array of shortest path distances, with UINT_MAX for - * unreachable nodes - * traceNb: number of nodes = number of traces - */ -static double sumDistances(const double* const distances, const unsigned int traceNb) -{ - unsigned int i; - double result; - - result= 0; - for (i= 0; i < traceNb; i++) - { - if (distances[i] != INFINITY) - { - result+= distances[i]; - } - } - - return result; -} - - -/* - * Cummulate the time correction factors between two nodes accross a graph - * - * With traceNum i, reference node r: - * tr= (1 + Xri) * ti + D0ri - * = drift * ti + offset - * - * Args: - * fitArray: array with the regression parameters - * previousVertex: previous vertex from a node i on the way to the source, - * UINT_MAX if i is not on the way or is the source, - * preallocated to the number of nodes - * traceNum: end node, the reference depends on previousVertex - * drift: drift factor - * offset: offset factor - */ -static void reduceFactors(Fit* const* const fitArray, const unsigned int* const - previousVertex, const unsigned int traceNum, double* const drift, double* - const offset, double* const stDev) -{ - if (previousVertex[traceNum] == UINT_MAX) - { - *drift= 1.; - *offset= 0.; - *stDev= 0.; - } - else - { - const Fit* fit; - double cummDrift, cummOffset, cummStDev; - unsigned int pv; - - pv= previousVertex[traceNum]; - - fit= &fitArray[pv][traceNum]; - reduceFactors(fitArray, previousVertex, pv, &cummDrift, &cummOffset, - &cummStDev); - - *drift= cummDrift * (1 + fit->x); - *offset= cummDrift * fit->d0 + cummOffset; - *stDev= fit->x * cummStDev + fit->e; - } -} - - -/* - * A GFunc for g_queue_foreach() - * - * Args: - * data Graph*, graph to destroy - * user_data NULL - */ -static void gfGraphDestroy(gpointer data, gpointer user_data) -{ - Graph* graph; - - graph= (Graph*) data; - - free(graph->previousVertex); - free(graph); -} - - -/* - * A GCompareFunc for g_queue_find_custom() - * - * Args: - * a: Graph* graph - * b: unsigned int* traceNum - * - * Returns: - * 0 if graph contains traceNum - */ -static gint gcfGraphTraceCompare(gconstpointer a, gconstpointer b) -{ - Graph* graph; - unsigned int traceNum; - - graph= (Graph*) a; - traceNum= *(unsigned int *) b; - - if (graph->previousVertex[traceNum] != UINT_MAX) - { - return 0; - } - else if (graph->reference == traceNum) - { - return 0; - } - else - { - return 1; - } -} - - /* * Write the analysis-specific graph lines in the gnuplot script. * diff --git a/lttv/lttv/sync/event_analysis_linreg.h b/lttv/lttv/sync/event_analysis_linreg.h index 7c9a2359..ce5a0811 100644 --- a/lttv/lttv/sync/event_analysis_linreg.h +++ b/lttv/lttv/sync/event_analysis_linreg.h @@ -30,20 +30,10 @@ typedef struct double st, st2, sd, sd2, std, x, d0, e; } Fit; -typedef struct -{ - double errorSum; - unsigned int* previousVertex; - unsigned int reference; -} Graph; - typedef struct { Fit** fitArray; - // Graph[] - GQueue* graphList; - // for statistics double* stDev; } AnalysisDataLinReg; diff --git a/lttv/lttv/sync/event_matching.h b/lttv/lttv/sync/event_matching.h index f7f1cf9d..e4c37732 100644 --- a/lttv/lttv/sync/event_matching.h +++ b/lttv/lttv/sync/event_matching.h @@ -35,7 +35,7 @@ typedef struct void (*matchEvent)(struct _SyncState* const syncState, Event* const event); - GArray* (*finalizeMatching)(struct _SyncState* const syncState); + AllFactors* (*finalizeMatching)(struct _SyncState* const syncState); void (*printMatchingStats)(struct _SyncState* const syncState); GraphFunctions graphFunctions; diff --git a/lttv/lttv/sync/event_matching_broadcast.c b/lttv/lttv/sync/event_matching_broadcast.c index c50fe4a8..9c83d9c6 100644 --- a/lttv/lttv/sync/event_matching_broadcast.c +++ b/lttv/lttv/sync/event_matching_broadcast.c @@ -36,7 +36,7 @@ static void initMatchingBroadcast(SyncState* const syncState); static void destroyMatchingBroadcast(SyncState* const syncState); static void matchEventBroadcast(SyncState* const syncState, Event* const event); -static GArray* finalizeMatchingBroadcast(SyncState* const syncState); +static AllFactors* finalizeMatchingBroadcast(SyncState* const syncState); static void printMatchingStatsBroadcast(SyncState* const syncState); static void writeMatchingGraphsPlotsBroadcast(SyncState* const syncState, const unsigned int i, const unsigned int j); @@ -295,9 +295,9 @@ static void matchEventBroadcast(SyncState* const syncState, Event* const event) * syncState container for synchronization data. * * Returns: - * Factors[traceNb] synchronization factors for each trace + * AllFactors* synchronization factors for each trace pair */ -static GArray* finalizeMatchingBroadcast(SyncState* const syncState) +static AllFactors* finalizeMatchingBroadcast(SyncState* const syncState) { MatchingDataBroadcast* matchingData; diff --git a/lttv/lttv/sync/event_matching_distributor.c b/lttv/lttv/sync/event_matching_distributor.c index c83187d4..c0381379 100644 --- a/lttv/lttv/sync/event_matching_distributor.c +++ b/lttv/lttv/sync/event_matching_distributor.c @@ -51,7 +51,7 @@ static void destroyMatchingDistributor(SyncState* const syncState); static void matchEventDistributor(SyncState* const syncState, Event* const event); -static GArray* finalizeMatchingDistributor(SyncState* const syncState); +static AllFactors* finalizeMatchingDistributor(SyncState* const syncState); static void printMatchingStatsDistributor(SyncState* const syncState); static void writeMatchingTraceTraceForePlotsDistributor(SyncState* const syncState, const unsigned int i, const unsigned int j); @@ -144,7 +144,7 @@ static void destroyMatchingDistributor(SyncState* const syncState) g_queue_foreach(matchingData->distributedModules, &gfDestroyModule, NULL); - g_queue_clear(matchingData->distributedModules); + g_queue_free(matchingData->distributedModules); free(syncState->matchingData); syncState->matchingData= NULL; } @@ -168,35 +168,21 @@ static void matchEventDistributor(SyncState* const syncState, Event* const event /* - * Call the distributed finalization functions and return identity factors + * Call the distributed finalization functions and return absent factors * * Args: * syncState container for synchronization data. * * Returns: - * Factors[traceNb] identity factors for each trace + * AllFactors* synchronization factors for each trace pair */ -static GArray* finalizeMatchingDistributor(SyncState* const syncState) +static AllFactors* finalizeMatchingDistributor(SyncState* const syncState) { - GArray* factors; - unsigned int i; MatchingDataDistributor* matchingData= syncState->matchingData; g_queue_foreach(matchingData->distributedModules, &gfFinalize, NULL); - 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++) - { - Factors* e; - - e= &g_array_index(factors, Factors, i); - e->drift= 1.; - e->offset= 0.; - } - - return factors; + return createAllFactors(syncState->traceNb); } @@ -406,11 +392,9 @@ void gfMatchEvent(gpointer data, gpointer user_data) */ void gfFinalize(gpointer data, gpointer user_data) { - GArray* factors; SyncState* parallelSS= data; - factors= parallelSS->matchingModule->finalizeMatching(parallelSS); - g_array_free(factors, TRUE); + freeAllFactors(parallelSS->matchingModule->finalizeMatching(parallelSS)); } diff --git a/lttv/lttv/sync/event_matching_tcp.c b/lttv/lttv/sync/event_matching_tcp.c index 64078acc..3662769a 100644 --- a/lttv/lttv/sync/event_matching_tcp.c +++ b/lttv/lttv/sync/event_matching_tcp.c @@ -36,7 +36,7 @@ static void initMatchingTCP(SyncState* const syncState); static void destroyMatchingTCP(SyncState* const syncState); static void matchEventTCP(SyncState* const syncState, Event* const event); -static GArray* finalizeMatchingTCP(SyncState* const syncState); +static AllFactors* finalizeMatchingTCP(SyncState* const syncState); static void printMatchingStatsTCP(SyncState* const syncState); static void writeMatchingGraphsPlotsTCPMessages(SyncState* const syncState, const unsigned int i, const unsigned int j); @@ -256,9 +256,9 @@ static void matchEventTCP(SyncState* const syncState, Event* const event) * syncState container for synchronization data. * * Returns: - * Factors[traceNb] synchronization factors for each trace + * AllFactors* synchronization factors for each trace pair */ -static GArray* finalizeMatchingTCP(SyncState* const syncState) +static AllFactors* finalizeMatchingTCP(SyncState* const syncState) { partialDestroyMatchingTCP(syncState); diff --git a/lttv/lttv/sync/event_processing.h b/lttv/lttv/sync/event_processing.h index 5ed1d91c..c3815bd7 100644 --- a/lttv/lttv/sync/event_processing.h +++ b/lttv/lttv/sync/event_processing.h @@ -32,7 +32,7 @@ typedef struct char* name; void (*initProcessing)(struct _SyncState* const syncStateLttv, ...); - GArray* (*finalizeProcessing)(struct _SyncState* const syncState); + AllFactors* (*finalizeProcessing)(struct _SyncState* const syncState); void (*printProcessingStats)(struct _SyncState* const syncState); void (*destroyProcessing)(struct _SyncState* const syncState); GraphFunctions graphFunctions; diff --git a/lttv/lttv/sync/event_processing_lttng_null.c b/lttv/lttv/sync/event_processing_lttng_null.c index b9eecbf3..5eff4acb 100644 --- a/lttv/lttv/sync/event_processing_lttng_null.c +++ b/lttv/lttv/sync/event_processing_lttng_null.c @@ -32,7 +32,7 @@ static void initProcessingLTTVNull(SyncState* const syncState, ...); static void destroyProcessingLTTVNull(SyncState* const syncState); -static GArray* finalizeProcessingLTTVNull(SyncState* const syncState); +static AllFactors* finalizeProcessingLTTVNull(SyncState* const syncState); // Functions specific to this module static gboolean processEventLTTVNull(void* hookData, void* callData); @@ -96,12 +96,12 @@ static void initProcessingLTTVNull(SyncState* const syncState, ...) * syncState container for synchronization data. * * Returns: - * Factors[traceNb] synchronization factors for each trace, empty in this - * case + * AllFactors synchronization factors for each trace pair, all of them + * ABSENT */ -static GArray* finalizeProcessingLTTVNull(SyncState* const syncState) +static AllFactors* finalizeProcessingLTTVNull(SyncState* const syncState) { - return g_array_new(FALSE, FALSE, sizeof(Factors)); + return createAllFactors(syncState->traceNb); } diff --git a/lttv/lttv/sync/event_processing_lttng_standard.c b/lttv/lttv/sync/event_processing_lttng_standard.c index 02354043..d37d357c 100644 --- a/lttv/lttv/sync/event_processing_lttng_standard.c +++ b/lttv/lttv/sync/event_processing_lttng_standard.c @@ -40,7 +40,7 @@ static void initProcessingLTTVStandard(SyncState* const syncState, ...); static void destroyProcessingLTTVStandard(SyncState* const syncState); -static GArray* finalizeProcessingLTTVStandard(SyncState* const syncState); +static AllFactors* finalizeProcessingLTTVStandard(SyncState* const syncState); static void printProcessingStatsLTTVStandard(SyncState* const syncState); static void writeProcessingGraphVariablesLTTVStandard(SyncState* const syncState, const unsigned int i); @@ -165,9 +165,9 @@ static void initProcessingLTTVStandard(SyncState* const syncState, ...) * syncState container for synchronization data. * * Returns: - * Factors[traceNb] synchronization factors for each trace + * AllFactors synchronization factors for each trace pair */ -static GArray* finalizeProcessingLTTVStandard(SyncState* const syncState) +static AllFactors* finalizeProcessingLTTVStandard(SyncState* const syncState) { ProcessingDataLTTVStandard* processingData; diff --git a/lttv/lttv/sync/event_processing_text.c b/lttv/lttv/sync/event_processing_text.c index 37f4194e..3d65bf54 100644 --- a/lttv/lttv/sync/event_processing_text.c +++ b/lttv/lttv/sync/event_processing_text.c @@ -37,8 +37,7 @@ // Functions common to all processing modules static void initProcessingText(SyncState* const syncState, ...); static void destroyProcessingText(SyncState* const syncState); -static GArray* finalizeProcessingText(SyncState* const syncState); -static void printProcessingStatsText(SyncState* const syncState); +static AllFactors* finalizeProcessingText(SyncState* const syncState); static void writeProcessingTraceTimeOptionsText(SyncState* const syncState, const unsigned int i, const unsigned int j); static void writeProcessingTraceTraceOptionsText(SyncState* const syncState, @@ -56,7 +55,6 @@ static ProcessingModule processingModuleText = { .initProcessing= &initProcessingText, .destroyProcessing= &destroyProcessingText, .finalizeProcessing= &finalizeProcessingText, - .printProcessingStats= &printProcessingStatsText, .graphFunctions= { .writeVariables= &writeProcessingGraphVariablesText, .writeTraceTraceOptions= &writeProcessingTraceTraceOptionsText, @@ -122,7 +120,7 @@ static void destroyProcessingText(SyncState* const syncState) if (syncState->stats && processingData->factors) { - g_array_free(processingData->factors, TRUE); + freeAllFactors(processingData->factors); } free(syncState->processingData); @@ -138,13 +136,13 @@ static void destroyProcessingText(SyncState* const syncState) * syncState: container for synchronization data. * * Returns: - * Factors[traceNb] synchronization factors for each trace + * AllFactors synchronization factors for each trace pair */ -static GArray* finalizeProcessingText(SyncState* const syncState) +static AllFactors* finalizeProcessingText(SyncState* const syncState) { int retval; unsigned int* seq; - GArray* factors; + AllFactors* factors; ProcessingDataText* processingData= (ProcessingDataText*) syncState->processingData; FILE* testCase= processingData->testCase; @@ -285,29 +283,6 @@ static GArray* finalizeProcessingText(SyncState* const syncState) } -/* - * Print statistics related to processing. Must be called after - * finalizeProcessing. - * - * Args: - * syncState container for synchronization data. - */ -static void printProcessingStatsText(SyncState* const syncState) -{ - unsigned int i; - - printf("Resulting synchronization factors:\n"); - for (i= 0; i < syncState->traceNb; i++) - { - Factors* factors= &g_array_index(((ProcessingDataText*) - syncState->processingData)->factors, Factors, i); - - printf("\ttrace %u drift= %g offset= %g (%f)\n", i, factors->drift, - factors->offset, factors->offset / CPU_FREQ); - } -} - - /* * Read trace number from the test case stream. The trace number should be the * first non-comment line and should be an unsigned int by itself on a line. diff --git a/lttv/lttv/sync/event_processing_text.h b/lttv/lttv/sync/event_processing_text.h index e4faa911..906f46cf 100644 --- a/lttv/lttv/sync/event_processing_text.h +++ b/lttv/lttv/sync/event_processing_text.h @@ -22,8 +22,8 @@ typedef struct { - // Factors factors[traceNb], only used for stats - GArray* factors; + // Only used for stats + AllFactors* factors; FILE* testCase; } ProcessingDataText; 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() * diff --git a/lttv/lttv/sync/sync_chain.h b/lttv/lttv/sync/sync_chain.h index 076d1960..8a6977c8 100644 --- a/lttv/lttv/sync/sync_chain.h +++ b/lttv/lttv/sync/sync_chain.h @@ -68,6 +68,8 @@ 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); diff --git a/lttv/lttv/sync/sync_chain_lttv.c b/lttv/lttv/sync/sync_chain_lttv.c index 0180e3b0..b9f87e91 100644 --- a/lttv/lttv/sync/sync_chain_lttv.c +++ b/lttv/lttv/sync/sync_chain_lttv.c @@ -181,6 +181,7 @@ bool syncTraceset(LttvTracesetContext* const traceSetContext) struct rusage startUsage, endUsage; GList* result; unsigned int i; + AllFactors* allFactors; GArray* factors; double minOffset, minDrift; unsigned int refFreqTrace; @@ -268,8 +269,10 @@ bool syncTraceset(LttvTracesetContext* const traceSetContext) G_MAXULONG, NULL); lttv_process_traceset_seek_time(traceSetContext, ltt_time_zero); - // Obtain, adjust and set correction factors - factors= syncState->processingModule->finalizeProcessing(syncState); + // Obtain, reduce, adjust and set correction factors + allFactors= syncState->processingModule->finalizeProcessing(syncState); + factors= reduceFactors(allFactors); + freeAllFactors(allFactors); /* 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 diff --git a/lttv/lttv/sync/sync_chain_unittest.c b/lttv/lttv/sync/sync_chain_unittest.c index 50c9f395..652c3797 100644 --- a/lttv/lttv/sync/sync_chain_unittest.c +++ b/lttv/lttv/sync/sync_chain_unittest.c @@ -100,12 +100,13 @@ int main(const int argc, char* const argv[]) struct timeval startTime, endTime; struct rusage startUsage, endUsage; GList* result; + GArray* factors; int retval; bool stats; const char* testCaseName; GString* analysisModulesNames; unsigned int id; - GArray* factors; + AllFactors* allFactors; /* * Initialize event modules @@ -208,8 +209,9 @@ int main(const int argc, char* const argv[]) syncState->analysisModule->initAnalysis(syncState); // Process traceset - factors= syncState->processingModule->finalizeProcessing(syncState); - g_array_free(factors, TRUE); + allFactors= syncState->processingModule->finalizeProcessing(syncState); + factors= reduceFactors(allFactors); + freeAllFactors(allFactors); // Write graphs file if (syncState->graphsStream) @@ -223,9 +225,19 @@ int main(const int argc, char* const argv[]) } // Print statistics - if (syncState->stats) + if (optionSyncStats.present) { + unsigned int i; + printStats(syncState); + + printf("Resulting synchronization factors:\n"); + for (i= 0; i < factors->len; i++) + { + Factors* traceFactors= &g_array_index(factors, Factors, i); + printf("\ttrace %u drift= %g offset= %g\n", i, + traceFactors->drift, traceFactors->offset); + } } // Destroy modules and clean up @@ -263,7 +275,7 @@ int main(const int argc, char* const argv[]) /* - * Read program arguments dans update ModuleOptions structures + * Read program arguments and update ModuleOptions structures * * Args: * argc, argv: standard argument arrays diff --git a/lttv/modules/text/sync_chain_batch.c b/lttv/modules/text/sync_chain_batch.c index 23d3e05f..11c4f636 100644 --- a/lttv/modules/text/sync_chain_batch.c +++ b/lttv/modules/text/sync_chain_batch.c @@ -338,13 +338,12 @@ void teardownSyncChain(LttvTracesetContext* const traceSetContext) SyncState* syncState; struct timeval endTime; struct rusage endUsage; - unsigned int i; int retval; tracesetChainState= g_hash_table_lookup(tracesetChainStates, traceSetContext); syncState= tracesetChainState->syncState; - syncState->processingModule->finalizeProcessing(syncState); + freeAllFactors(syncState->processingModule->finalizeProcessing(syncState)); // Write graphs file if (optionEvalGraphs) @@ -359,19 +358,6 @@ void teardownSyncChain(LttvTracesetContext* const traceSetContext) printStats(syncState); - printf("Resulting synchronization factors:\n"); - for (i= 0; i < syncState->traceNb; i++) - { - LttTrace* t; - - t= traceSetContext->traces[i]->t; - - printf("\ttrace %u drift= %g offset= %g (%f) start time= %ld.%09ld\n", - i, t->drift, t->offset, (double) tsc_to_uint64(t->freq_scale, - t->start_freq, t->offset) / NANOSECONDS_PER_SECOND, - t->start_time_from_tsc.tv_sec, t->start_time_from_tsc.tv_nsec); - } - syncState->processingModule->destroyProcessing(syncState); if (syncState->matchingModule != NULL) { -- 2.34.1