From b2da0724a95cdb911c07640268b65bd9c5b92010 Mon Sep 17 00:00:00 2001 From: Benjamin Poirier Date: Thu, 25 Mar 2010 17:33:52 -0400 Subject: [PATCH] Perform factor reduction as a modular step Adds a fourth step of modular processing. After event processing, matching and analysis are completed, factor reduction is performed through a module. At the moment there is only one such module, the accuracy-based factor reduction that was already present, but new modules can be added and selected through a command line option. Signed-off-by: Benjamin Poirier --- lttv/lttv/Makefile.am | 3 + lttv/lttv/sync/Makefile.am | 8 +- lttv/lttv/sync/README | 52 ++- lttv/lttv/sync/data_structures.c | 6 +- lttv/lttv/sync/data_structures.h | 5 +- lttv/lttv/sync/event_analysis_chull.c | 8 +- lttv/lttv/sync/event_analysis_eval.c | 9 +- lttv/lttv/sync/event_matching_distributor.c | 3 +- lttv/lttv/sync/event_processing_text.c | 2 +- lttv/lttv/sync/factor_reduction.h | 41 ++ lttv/lttv/sync/factor_reduction_accuracy.c | 458 ++++++++++++++++++++ lttv/lttv/sync/factor_reduction_accuracy.h | 34 ++ lttv/lttv/sync/sync_chain.c | 359 +++------------ lttv/lttv/sync/sync_chain.h | 9 +- lttv/lttv/sync/sync_chain_lttv.c | 72 ++- lttv/lttv/sync/sync_chain_unittest.c | 41 +- lttv/modules/text/sync_chain_batch.c | 10 +- 17 files changed, 761 insertions(+), 359 deletions(-) create mode 100644 lttv/lttv/sync/factor_reduction.h create mode 100644 lttv/lttv/sync/factor_reduction_accuracy.c create mode 100644 lttv/lttv/sync/factor_reduction_accuracy.h diff --git a/lttv/lttv/Makefile.am b/lttv/lttv/Makefile.am index b661f658..30ead559 100644 --- a/lttv/lttv/Makefile.am +++ b/lttv/lttv/Makefile.am @@ -84,6 +84,9 @@ lttv_real_SOURCES = \ 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 = \ diff --git a/lttv/lttv/sync/Makefile.am b/lttv/lttv/sync/Makefile.am index e1820feb..e1d67756 100644 --- a/lttv/lttv/sync/Makefile.am +++ b/lttv/lttv/sync/Makefile.am @@ -11,17 +11,23 @@ unittest_SOURCES = \ 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 diff --git a/lttv/lttv/sync/README b/lttv/lttv/sync/README index fe242e97..9945c4d8 100644 --- a/lttv/lttv/sync/README +++ b/lttv/lttv/sync/README @@ -54,7 +54,10 @@ as seen with "-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 @@ -103,10 +106,11 @@ successful chull (one of the synchronization algorithms) run of two traces: 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 @@ -182,6 +186,19 @@ To see the output of this mode, run: 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: @@ -198,11 +215,11 @@ This part is specific to the framework in use: the program doing 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 @@ -285,12 +302,13 @@ I chose this approach because: 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. diff --git a/lttv/lttv/sync/data_structures.c b/lttv/lttv/sync/data_structures.c index c0dafb07..79b8963d 100644 --- a/lttv/lttv/sync/data_structures.c +++ b/lttv/lttv/sync/data_structures.c @@ -699,7 +699,6 @@ AllFactors* createAllFactors(const unsigned int traceNb) unsigned int i, j; allFactors= malloc(sizeof(AllFactors)); - allFactors->traceNb= traceNb; allFactors->refCount= 1; allFactors->pairFactors= malloc(traceNb * sizeof(PairFactors*)); factorsArray=allFactors->pairFactors; @@ -731,13 +730,12 @@ AllFactors* createAllFactors(const unsigned int traceNb) * 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--; diff --git a/lttv/lttv/sync/data_structures.h b/lttv/lttv/sync/data_structures.h index cc422a81..c4b0ff1f 100644 --- a/lttv/lttv/sync/data_structures.h +++ b/lttv/lttv/sync/data_structures.h @@ -22,6 +22,8 @@ #include #include +#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) + enum Direction { @@ -179,7 +181,6 @@ typedef struct typedef struct { unsigned int refCount; - unsigned int traceNb; PairFactors** pairFactors; } AllFactors; @@ -236,6 +237,6 @@ void destroyBroadcast(Broadcast* const broadcast); 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 diff --git a/lttv/lttv/sync/event_analysis_chull.c b/lttv/lttv/sync/event_analysis_chull.c index 1b15a030..223ea12f 100644 --- a/lttv/lttv/sync/event_analysis_chull.c +++ b/lttv/lttv/sync/event_analysis_chull.c @@ -322,7 +322,8 @@ static void destroyAnalysisCHull(SyncState* const syncState) { 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]); @@ -331,7 +332,7 @@ static void destroyAnalysisCHull(SyncState* const syncState) if (syncState->stats) { - freeAllFactors(analysisData->stats->allFactors); + freeAllFactors(analysisData->stats->allFactors, syncState->traceNb); free(analysisData->stats); } @@ -343,7 +344,8 @@ static void destroyAnalysisCHull(SyncState* const syncState) closeGraphFiles(syncState); } - freeAllFactors(analysisData->graphsData->allFactors); + freeAllFactors(analysisData->graphsData->allFactors, + syncState->traceNb); free(analysisData->graphsData); } diff --git a/lttv/lttv/sync/event_analysis_eval.c b/lttv/lttv/sync/event_analysis_eval.c index 27d877d8..4aa6a7a5 100644 --- a/lttv/lttv/sync/event_analysis_eval.c +++ b/lttv/lttv/sync/event_analysis_eval.c @@ -557,8 +557,8 @@ static void destroyAnalysisEval(SyncState* const syncState) 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); @@ -596,7 +596,7 @@ static void destroyAnalysisEval(SyncState* const syncState) if (!syncState->stats) { - freeAllFactors(graphs->lpFactorsArray); + freeAllFactors(graphs->lpFactorsArray, syncState->traceNb); } #endif @@ -1860,7 +1860,8 @@ static void finalizeAnalysisEvalLP(SyncState* const syncState) } #endif - freeAllFactors(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS)); + freeAllFactors(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS), + analysisData->chullSS->traceNb); } diff --git a/lttv/lttv/sync/event_matching_distributor.c b/lttv/lttv/sync/event_matching_distributor.c index c0381379..5df7cd41 100644 --- a/lttv/lttv/sync/event_matching_distributor.c +++ b/lttv/lttv/sync/event_matching_distributor.c @@ -394,7 +394,8 @@ void gfFinalize(gpointer data, gpointer user_data) { SyncState* parallelSS= data; - freeAllFactors(parallelSS->matchingModule->finalizeMatching(parallelSS)); + freeAllFactors(parallelSS->matchingModule->finalizeMatching(parallelSS), + parallelSS->traceNb); } diff --git a/lttv/lttv/sync/event_processing_text.c b/lttv/lttv/sync/event_processing_text.c index 3d65bf54..bcbea9b2 100644 --- a/lttv/lttv/sync/event_processing_text.c +++ b/lttv/lttv/sync/event_processing_text.c @@ -120,7 +120,7 @@ static void destroyProcessingText(SyncState* const syncState) if (syncState->stats && processingData->factors) { - freeAllFactors(processingData->factors); + freeAllFactors(processingData->factors, syncState->traceNb); } free(syncState->processingData); diff --git a/lttv/lttv/sync/factor_reduction.h b/lttv/lttv/sync/factor_reduction.h new file mode 100644 index 00000000..249b84ac --- /dev/null +++ b/lttv/lttv/sync/factor_reduction.h @@ -0,0 +1,41 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009, 2010 Benjamin Poirier + * + * 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 . + */ + +#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 diff --git a/lttv/lttv/sync/factor_reduction_accuracy.c b/lttv/lttv/sync/factor_reduction_accuracy.c new file mode 100644 index 00000000..578dd733 --- /dev/null +++ b/lttv/lttv/sync/factor_reduction_accuracy.c @@ -0,0 +1,458 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009, 2010 Benjamin Poirier + * + * 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 . + */ +#define _ISOC99_SOURCE + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include + +#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(); + } + } +} diff --git a/lttv/lttv/sync/factor_reduction_accuracy.h b/lttv/lttv/sync/factor_reduction_accuracy.h new file mode 100644 index 00000000..3a2e0f63 --- /dev/null +++ b/lttv/lttv/sync/factor_reduction_accuracy.h @@ -0,0 +1,34 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009, 2010 Benjamin Poirier + * + * 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 . + */ + +#ifndef FACTOR_REDUCTION_ACCURACY_H +#define FACTOR_REDUCTION_ACCURACY_H + +#include + +#include "data_structures.h" + + +typedef struct +{ + unsigned int** predecessors; + unsigned int* references; +} ReductionStatsAccuracy; + +void registerReductionAccuracy(); + +#endif diff --git a/lttv/lttv/sync/sync_chain.c b/lttv/lttv/sync/sync_chain.c index 08cc3cb3..a34a93b1 100644 --- a/lttv/lttv/sync/sync_chain.c +++ b/lttv/lttv/sync/sync_chain.c @@ -15,14 +15,11 @@ * along with this program. If not, see . */ -#define _ISOC99_SOURCE - #ifdef HAVE_CONFIG_H #include #endif #include -#include #include #include #include @@ -33,16 +30,10 @@ 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 * @@ -55,14 +46,21 @@ void printStats(SyncState* const syncState) { 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); + } } @@ -88,304 +86,6 @@ 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() * @@ -455,6 +155,29 @@ gint gcfCompareAnalysis(gconstpointer a, gconstpointer b) } +/* + * 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() * @@ -469,3 +192,19 @@ void gfAppendAnalysisName(gpointer data, gpointer user_data) 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, ", "); +} diff --git a/lttv/lttv/sync/sync_chain.h b/lttv/lttv/sync/sync_chain.h index 8a6977c8..e479f1e7 100644 --- a/lttv/lttv/sync/sync_chain.h +++ b/lttv/lttv/sync/sync_chain.h @@ -24,6 +24,7 @@ #include "event_processing.h" #include "event_matching.h" #include "event_analysis.h" +#include "factor_reduction.h" typedef struct _SyncState { @@ -38,6 +39,8 @@ typedef struct _SyncState void* matchingData; const AnalysisModule* analysisModule; void* analysisData; + const ReductionModule* reductionModule; + void* reductionData; } SyncState; typedef struct @@ -62,17 +65,19 @@ 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 diff --git a/lttv/lttv/sync/sync_chain_lttv.c b/lttv/lttv/sync/sync_chain_lttv.c index b9f87e91..95bef441 100644 --- a/lttv/lttv/sync/sync_chain_lttv.c +++ b/lttv/lttv/sync/sync_chain_lttv.c @@ -44,6 +44,7 @@ #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" @@ -75,6 +76,12 @@ static ModuleOption optionSyncAnalysis= { .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, @@ -96,6 +103,20 @@ static ModuleOption optionSyncGraphsDir= { 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"); @@ -117,15 +138,23 @@ static void 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) @@ -137,6 +166,7 @@ static void init() 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); @@ -155,10 +185,12 @@ static void destroy() 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); } @@ -256,11 +288,24 @@ bool syncTraceset(LttvTracesetContext* const traceSetContext) 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 @@ -271,8 +316,9 @@ bool syncTraceset(LttvTracesetContext* const traceSetContext) // 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 @@ -374,6 +420,10 @@ bool syncTraceset(LttvTracesetContext* const traceSetContext) { syncState->analysisModule->destroyAnalysis(syncState); } + if (syncState->reductionModule != NULL) + { + syncState->reductionModule->destroyReduction(syncState); + } free(syncState); diff --git a/lttv/lttv/sync/sync_chain_unittest.c b/lttv/lttv/sync/sync_chain_unittest.c index 652c3797..40302a0e 100644 --- a/lttv/lttv/sync/sync_chain_unittest.c +++ b/lttv/lttv/sync/sync_chain_unittest.c @@ -41,6 +41,7 @@ #include "event_analysis_chull.h" #include "event_analysis_linreg.h" #include "event_analysis_eval.h" +#include "factor_reduction_accuracy.h" #include "sync_chain.h" @@ -82,6 +83,12 @@ static ModuleOption optionSyncAnalysis= { .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", +}; /* @@ -105,6 +112,7 @@ int main(const int argc, char* const argv[]) bool stats; const char* testCaseName; GString* analysisModulesNames; + GString* reductionModulesNames; unsigned int id; AllFactors* allFactors; @@ -125,6 +133,8 @@ int main(const int argc, char* const argv[]) registerAnalysisLinReg(); registerAnalysisEval(); + registerReductionAccuracy(); + // Initialize data structures syncState= malloc(sizeof(SyncState)); @@ -139,6 +149,16 @@ int main(const int argc, char* const argv[]) 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) { @@ -146,6 +166,7 @@ int main(const int argc, char* const argv[]) } 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); @@ -153,6 +174,7 @@ int main(const int argc, char* const argv[]) testCaseName= processOptions(argc, argv); g_string_free(analysisModulesNames, TRUE); + g_string_free(reductionModulesNames, TRUE); if (optionSyncStats.present) { @@ -203,15 +225,29 @@ int main(const int argc, char* const argv[]) 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) @@ -244,6 +280,7 @@ int main(const int argc, char* const argv[]) syncState->processingModule->destroyProcessing(syncState); syncState->matchingModule->destroyMatching(syncState); syncState->analysisModule->destroyAnalysis(syncState); + syncState->reductionModule->destroyReduction(syncState); stats= syncState->stats; free(syncState); diff --git a/lttv/modules/text/sync_chain_batch.c b/lttv/modules/text/sync_chain_batch.c index 11c4f636..31fde5ec 100644 --- a/lttv/modules/text/sync_chain_batch.c +++ b/lttv/modules/text/sync_chain_batch.c @@ -306,6 +306,9 @@ void setupSyncChain(LttvTracesetContext* const traceSetContext) syncState->graphsDir= NULL; } + syncState->reductionData= NULL; + syncState->reductionModule= NULL; + syncState->analysisData= NULL; result= g_queue_find_custom(&analysisModules, "eval", &gcfCompareAnalysis); @@ -343,7 +346,8 @@ void teardownSyncChain(LttvTracesetContext* const traceSetContext) 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) @@ -367,6 +371,10 @@ void teardownSyncChain(LttvTracesetContext* const traceSetContext) { syncState->analysisModule->destroyAnalysis(syncState); } + if (syncState->reductionModule != NULL) + { + syncState->reductionModule->destroyReduction(syncState); + } free(syncState); -- 2.34.1