From ab6edc6a1a55aefe52cfd9e610b5f21ee2029544 Mon Sep 17 00:00:00 2001 From: Benjamin Poirier Date: Fri, 26 Mar 2010 16:31:25 -0400 Subject: [PATCH] Calculate synchronization accuracy within the chull module Move the linear programming-based synchronization accuracy code from the eval module to the chull module. This avoids having to break the chull module encapsulation to access the hull points from the eval module. As before, accuracy information is only available if the glpk library is available at build time. Signed-off-by: Benjamin Poirier --- lttv/lttv/sync/data_structures.c | 7 +- lttv/lttv/sync/data_structures.h | 12 +- lttv/lttv/sync/event_analysis_chull.c | 693 ++++++++++++++++++++++++-- lttv/lttv/sync/event_analysis_chull.h | 61 ++- lttv/lttv/sync/event_analysis_eval.c | 649 +----------------------- lttv/lttv/sync/event_analysis_eval.h | 26 - 6 files changed, 726 insertions(+), 722 deletions(-) diff --git a/lttv/lttv/sync/data_structures.c b/lttv/lttv/sync/data_structures.c index 79b8963d..acac9d72 100644 --- a/lttv/lttv/sync/data_structures.c +++ b/lttv/lttv/sync/data_structures.c @@ -46,7 +46,7 @@ const char* const approxNames[]= { [APPROXIMATE]= "Approximate", [INCOMPLETE]= "Incomplete", [ABSENT]= "Absent", - [SCREWED]= "Screwed", + [FAIL]= "Fail", }; @@ -737,6 +737,11 @@ void freeAllFactors(AllFactors* const allFactors, const unsigned int traceNb) { unsigned int i, j; + if (allFactors == NULL) + { + return; + } + allFactors->refCount--; if (allFactors->refCount == 0) diff --git a/lttv/lttv/sync/data_structures.h b/lttv/lttv/sync/data_structures.h index c4b0ff1f..627286cc 100644 --- a/lttv/lttv/sync/data_structures.h +++ b/lttv/lttv/sync/data_structures.h @@ -162,8 +162,8 @@ typedef enum * even no communication at all). approx and accuracy are NULL. */ - SCREWED, - /* The algorithms are screwed. All fields may be NULL. + FAIL, + /* The algorithms are defective. All fields may be NULL. */ APPROX_NB, // This must be the last member @@ -185,6 +185,14 @@ typedef struct } AllFactors; +// This structure is used to return a corrected time value with accuracy +// bounds +typedef struct +{ + uint64_t time, min, max; +} CorrectedTime; + + // ConnectionKey-related functions guint ghfConnectionKeyHash(gconstpointer key); diff --git a/lttv/lttv/sync/event_analysis_chull.c b/lttv/lttv/sync/event_analysis_chull.c index 223ea12f..154258e0 100644 --- a/lttv/lttv/sync/event_analysis_chull.c +++ b/lttv/lttv/sync/event_analysis_chull.c @@ -40,13 +40,21 @@ typedef enum UPPER } HullType; - typedef enum { MINIMUM, MAXIMUM } LineType; +#ifdef HAVE_LIBGLPK +struct LPAddRowInfo +{ + glp_prob* lp; + int boundType; + GArray* iArray, * jArray, * aArray; +}; +#endif + // Functions common to all analysis modules static void initAnalysisCHull(SyncState* const syncState); @@ -56,8 +64,8 @@ static void analyzeMessageCHull(SyncState* const syncState, Message* const message); 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); +static void writeAnalysisTraceTraceForePlotsCHull(SyncState* const syncState, + const unsigned int i, const unsigned int j); // Functions specific to this module static void openGraphFiles(SyncState* const syncState); @@ -65,16 +73,18 @@ static void closeGraphFiles(SyncState* const syncState); static void writeGraphFiles(SyncState* const syncState); static void gfDumpHullToFile(gpointer data, gpointer userData); +AllFactors* calculateAllFactors(struct _SyncState* const syncState); +void calculateFactorsMiddle(PairFactors* const factors); +static Factors* calculateFactorsExact(GQueue* const cu, GQueue* const cl, const + LineType lineType) __attribute__((pure)); +static void calculateFactorsFallback(GQueue* const cr, GQueue* const cs, + PairFactors* const result); static void grahamScan(GQueue* const hull, Point* const newPoint, const HullType type); static int jointCmp(const Point* const p1, const Point* const p2, const Point* const p3) __attribute__((pure)); static double crossProductK(const Point const* p1, const Point const* p2, const Point const* p3, const Point const* p4) __attribute__((pure)); -static Factors* calculateFactorsExact(GQueue* const cu, GQueue* const cl, const - LineType lineType) __attribute__((pure)); -static void calculateFactorsFallback(GQueue* const cr, GQueue* const cs, - 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) @@ -84,6 +94,36 @@ static double verticalDistance(Point* p1, Point* p2, Point* const point) static void gfPointDestroy(gpointer data, gpointer userData); +// The next group of functions is only needed when computing synchronization +// accuracy. +#ifdef HAVE_LIBGLPK +static AllFactors* finalizeAnalysisCHullLP(SyncState* const syncState); +static void writeAnalysisTraceTimeBackPlotsCHull(SyncState* const syncState, + const unsigned int i, const unsigned int j); +static void writeAnalysisTraceTimeForePlotsCHull(SyncState* const syncState, + const unsigned int i, const unsigned int j); +static void writeAnalysisTraceTraceBackPlotsCHull(SyncState* const syncState, + const unsigned int i, const unsigned int j); + +static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const + upperHull); +static void gfLPAddRow(gpointer data, gpointer user_data); +static Factors* calculateFactorsLP(glp_prob* const lp, const int direction); +static void calculateCompleteFactorsLP(glp_prob* const lp, PairFactors* + factors); +void timeCorrectionLP(glp_prob* const lp, const PairFactors* const lpFactors, + const uint64_t time, CorrectedTime* const correctedTime); + +static void gfAddAbsiscaToArray(gpointer data, gpointer user_data); +static gint gcfCompareUint64(gconstpointer a, gconstpointer b); +#else +static inline AllFactors* finalizeAnalysisCHullLP(SyncState* const syncState) +{ + return NULL; +} +#endif + + static AnalysisModule analysisModuleCHull= { .name= "chull", @@ -93,7 +133,12 @@ static AnalysisModule analysisModuleCHull= { .finalizeAnalysis= &finalizeAnalysisCHull, .printAnalysisStats= &printAnalysisStatsCHull, .graphFunctions= { - .writeTraceTraceForePlots= &writeAnalysisGraphsPlotsCHull, +#ifdef HAVE_LIBGLPK + .writeTraceTimeBackPlots= &writeAnalysisTraceTimeBackPlotsCHull, + .writeTraceTimeForePlots= &writeAnalysisTraceTimeForePlotsCHull, + .writeTraceTraceBackPlots= &writeAnalysisTraceTraceBackPlotsCHull, +#endif + .writeTraceTraceForePlots= &writeAnalysisTraceTraceForePlotsCHull, } }; @@ -140,19 +185,19 @@ static void initAnalysisCHull(SyncState* const syncState) analysisData->hullArray[i][j]= g_queue_new(); } } +#ifdef HAVE_LIBGLPK + analysisData->lps= NULL; +#endif if (syncState->stats) { - analysisData->stats= malloc(sizeof(AnalysisStatsCHull)); - analysisData->stats->dropped= 0; - analysisData->stats->allFactors= NULL; + analysisData->stats= calloc(1, sizeof(AnalysisStatsCHull)); } if (syncState->graphsStream) { - analysisData->graphsData= malloc(sizeof(AnalysisGraphsDataCHull)); + analysisData->graphsData= calloc(1, sizeof(AnalysisGraphsDataCHull)); openGraphFiles(syncState); - analysisData->graphsData->allFactors= NULL; } } @@ -330,22 +375,51 @@ static void destroyAnalysisCHull(SyncState* const syncState) } free(analysisData->hullArray); +#ifdef HAVE_LIBGLPK + if (analysisData->lps != NULL) + { + for (i= 0; i < syncState->traceNb; i++) + { + unsigned int j; + + for (j= 0; j < i; j++) + { + // There seems to be a memory leak in glpk, valgrind reports a + // loss (reachable) even if the problem is deleted + glp_delete_prob(analysisData->lps[i][j]); + } + free(analysisData->lps[i]); + } + free(analysisData->lps); + } +#endif + if (syncState->stats) { freeAllFactors(analysisData->stats->allFactors, syncState->traceNb); + freeAllFactors(analysisData->stats->geoFactors, syncState->traceNb); + +#ifdef HAVE_LIBGLPK + freeAllFactors(analysisData->stats->lpFactors, syncState->traceNb); +#endif free(analysisData->stats); } if (syncState->graphsStream) { - if (analysisData->graphsData->hullPoints != NULL) + AnalysisGraphsDataCHull* graphs= analysisData->graphsData; + + if (graphs->hullPoints != NULL) { closeGraphFiles(syncState); } - freeAllFactors(analysisData->graphsData->allFactors, - syncState->traceNb); + freeAllFactors(graphs->allFactors, syncState->traceNb); + +#ifdef HAVE_LIBGLPK + freeAllFactors(graphs->lpFactors, syncState->traceNb); +#endif free(analysisData->graphsData); } @@ -486,7 +560,7 @@ static void grahamScan(GQueue* const hull, Point* const newPoint, const static AllFactors* finalizeAnalysisCHull(SyncState* const syncState) { AnalysisDataCHull* analysisData; - AllFactors* allFactors; + AllFactors* geoFactors, * lpFactors; analysisData= (AnalysisDataCHull*) syncState->analysisData; @@ -496,21 +570,50 @@ static AllFactors* finalizeAnalysisCHull(SyncState* const syncState) closeGraphFiles(syncState); } - allFactors= calculateAllFactors(syncState); + geoFactors= calculateAllFactors(syncState); + lpFactors= finalizeAnalysisCHullLP(syncState); if (syncState->stats) { - allFactors->refCount++; - analysisData->stats->allFactors= allFactors; + geoFactors->refCount++; + analysisData->stats->geoFactors= geoFactors; + + if (lpFactors != NULL) + { + lpFactors->refCount++; + analysisData->stats->allFactors= lpFactors; + } + else + { + geoFactors->refCount++; + analysisData->stats->allFactors= geoFactors; + } } if (syncState->graphsStream) { - allFactors->refCount++; - analysisData->graphsData->allFactors= allFactors; + if (lpFactors != NULL) + { + lpFactors->refCount++; + analysisData->graphsData->allFactors= lpFactors; + } + else + { + geoFactors->refCount++; + analysisData->graphsData->allFactors= geoFactors; + } } - return allFactors; + if (lpFactors != NULL) + { + freeAllFactors(geoFactors, syncState->traceNb); + return lpFactors; + } + else + { + freeAllFactors(lpFactors, syncState->traceNb); + return geoFactors; + } } @@ -603,7 +706,7 @@ static void printAnalysisStatsCHull(SyncState* const syncState) 1.)); } } - else if (factorsCHull->type == SCREWED) + else if (factorsCHull->type == FAIL) { printf("\n"); @@ -632,6 +735,47 @@ static void printAnalysisStatsCHull(SyncState* const syncState) } } } + +#ifdef HAVE_LIBGLPK + printf("\tFactor comparison:\n" + "\t\tTrace pair Factors type Differences (lp - chull)\n" + "\t\t a0 a1\n" + "\t\t Min Max Min Max\n"); + + for (i= 0; i < syncState->traceNb; i++) + { + for (j= 0; j < i; j++) + { + PairFactors* geoFactors= + &analysisData->stats->geoFactors->pairFactors[i][j]; + PairFactors* lpFactors= + &analysisData->stats->lpFactors->pairFactors[i][j]; + + printf("\t\t%3d - %-3d ", i, j); + if (lpFactors->type == geoFactors->type) + { + if (lpFactors->type == ACCURATE) + { + printf("%-13s %-10.4g %-10.4g %-10.4g %.4g\n", + approxNames[lpFactors->type], + lpFactors->min->offset - geoFactors->min->offset, + lpFactors->max->offset - geoFactors->max->offset, + lpFactors->min->drift - geoFactors->min->drift, + lpFactors->max->drift - geoFactors->max->drift); + } + else if (lpFactors->type == ABSENT) + { + printf("%s\n", approxNames[lpFactors->type]); + } + } + else + { + printf("Different! %s and %s\n", approxNames[lpFactors->type], + approxNames[geoFactors->type]); + } + } + } +#endif } @@ -718,19 +862,19 @@ static double crossProductK(const Point const* p1, const Point const* p2, * syncState container for synchronization data. * * Returns: - * AllFactors*, see the documentation for the member allFactors of + * AllFactors*, see the documentation for the member geoFactors of * AnalysisStatsCHull. */ AllFactors* calculateAllFactors(SyncState* const syncState) { unsigned int traceNumA, traceNumB; - AllFactors* allFactors; + AllFactors* geoFactors; AnalysisDataCHull* analysisData; analysisData= (AnalysisDataCHull*) syncState->analysisData; - // Allocate allFactors and calculate min and max - allFactors= createAllFactors(syncState->traceNb); + // Allocate geoFactors and calculate min and max + geoFactors= createAllFactors(syncState->traceNb); for (traceNumA= 0; traceNumA < syncState->traceNb; traceNumA++) { for (traceNumB= 0; traceNumB < traceNumA; traceNumB++) @@ -751,14 +895,14 @@ AllFactors* calculateAllFactors(SyncState* const syncState) for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++) { - g_debug("allFactors[%u][%u].%s = calculateFactorsExact(cr= " + g_debug("geoFactors[%u][%u].%s = calculateFactorsExact(cr= " "hullArray[%u][%u], cs= hullArray[%u][%u], %s)", traceNumA, traceNumB, loopValues[i].factorsOffset == offsetof(PairFactors, min) ? "min" : "max", traceNumB, traceNumA, traceNumA, traceNumB, loopValues[i].lineType == MINIMUM ? "MINIMUM" : "MAXIMUM"); *((Factors**) ((void*) - &allFactors->pairFactors[traceNumA][traceNumB] + + &geoFactors->pairFactors[traceNumA][traceNumB] + loopValues[i].factorsOffset))= calculateFactorsExact(cr, cs, loopValues[i].lineType); } @@ -772,13 +916,13 @@ AllFactors* calculateAllFactors(SyncState* const syncState) { PairFactors* factorsCHull; - factorsCHull= &allFactors->pairFactors[traceNumA][traceNumB]; + factorsCHull= &geoFactors->pairFactors[traceNumA][traceNumB]; if (factorsCHull->min == NULL && factorsCHull->max == NULL) { factorsCHull->type= APPROXIMATE; calculateFactorsFallback(analysisData->hullArray[traceNumB][traceNumA], analysisData->hullArray[traceNumA][traceNumB], - &allFactors->pairFactors[traceNumA][traceNumB]); + &geoFactors->pairFactors[traceNumA][traceNumB]); } else if (factorsCHull->min != NULL && factorsCHull->max != NULL) { @@ -801,12 +945,12 @@ AllFactors* calculateAllFactors(SyncState* const syncState) else { //g_assert_not_reached(); - factorsCHull->type= SCREWED; + factorsCHull->type= FAIL; } } } - return allFactors; + return geoFactors; } @@ -1137,7 +1281,7 @@ static double intercept(const Point* const p1, const Point* const p2) * i: first trace number * j: second trace number, garanteed to be larger than i */ -void writeAnalysisGraphsPlotsCHull(SyncState* const syncState, const unsigned +void writeAnalysisTraceTraceForePlotsCHull(SyncState* const syncState, const unsigned int i, const unsigned int j) { AnalysisDataCHull* analysisData; @@ -1209,7 +1353,7 @@ void writeAnalysisGraphsPlotsCHull(SyncState* const syncState, const unsigned factorsCHull->max->offset, factorsCHull->max->drift); } } - else if (factorsCHull->type == SCREWED) + else if (factorsCHull->type == FAIL) { if (factorsCHull->min != NULL && factorsCHull->min->drift != -INFINITY) { @@ -1237,3 +1381,480 @@ void writeAnalysisGraphsPlotsCHull(SyncState* const syncState, const unsigned g_assert_not_reached(); } } + + +#ifdef HAVE_LIBGLPK +/* + * Create the linear programming problem containing the constraints defined by + * two half-hulls. The objective function and optimization directions are not + * written. + * + * Args: + * syncState: container for synchronization data + * i: first trace number + * j: second trace number, garanteed to be larger than i + * Returns: + * A new glp_prob*, this problem must be freed by the caller with + * glp_delete_prob() + */ +static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const + upperHull) +{ + unsigned int it; + const int zero= 0; + const double zeroD= 0.; + glp_prob* lp= glp_create_prob(); + unsigned int hullPointNb= g_queue_get_length(lowerHull) + + g_queue_get_length(upperHull); + GArray* iArray= g_array_sized_new(FALSE, FALSE, sizeof(int), hullPointNb + + 1); + GArray* jArray= g_array_sized_new(FALSE, FALSE, sizeof(int), hullPointNb + + 1); + GArray* aArray= g_array_sized_new(FALSE, FALSE, sizeof(double), + hullPointNb + 1); + struct { + GQueue* hull; + struct LPAddRowInfo rowInfo; + } loopValues[2]= { + {lowerHull, {lp, GLP_UP, iArray, jArray, aArray}}, + {upperHull, {lp, GLP_LO, iArray, jArray, aArray}}, + }; + + // Create the LP problem + glp_term_out(GLP_OFF); + if (hullPointNb > 0) + { + glp_add_rows(lp, hullPointNb); + } + glp_add_cols(lp, 2); + + glp_set_col_name(lp, 1, "a0"); + glp_set_col_bnds(lp, 1, GLP_FR, 0., 0.); + glp_set_col_name(lp, 2, "a1"); + glp_set_col_bnds(lp, 2, GLP_LO, 0., 0.); + + // Add row constraints + g_array_append_val(iArray, zero); + g_array_append_val(jArray, zero); + g_array_append_val(aArray, zeroD); + + for (it= 0; it < sizeof(loopValues) / sizeof(*loopValues); it++) + { + g_queue_foreach(loopValues[it].hull, &gfLPAddRow, + &loopValues[it].rowInfo); + } + + g_assert_cmpuint(iArray->len, ==, jArray->len); + g_assert_cmpuint(jArray->len, ==, aArray->len); + g_assert_cmpuint(aArray->len - 1, ==, hullPointNb * 2); + + glp_load_matrix(lp, aArray->len - 1, &g_array_index(iArray, int, 0), + &g_array_index(jArray, int, 0), &g_array_index(aArray, double, 0)); + + glp_scale_prob(lp, GLP_SF_AUTO); + + g_array_free(iArray, TRUE); + g_array_free(jArray, TRUE); + g_array_free(aArray, TRUE); + + return lp; +} + + +/* + * A GFunc for g_queue_foreach(). Add constraints and bounds for one row. + * + * Args: + * data Point*, synchronization point for which to add an LP row + * (a constraint) + * user_data LPAddRowInfo* + */ +static void gfLPAddRow(gpointer data, gpointer user_data) +{ + Point* p= data; + struct LPAddRowInfo* rowInfo= user_data; + int indexes[2]; + double constraints[2]; + + indexes[0]= g_array_index(rowInfo->iArray, int, rowInfo->iArray->len - 1) + 1; + indexes[1]= indexes[0]; + + if (rowInfo->boundType == GLP_UP) + { + glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_UP, 0., p->y); + } + else if (rowInfo->boundType == GLP_LO) + { + glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_LO, p->y, 0.); + } + else + { + g_assert_not_reached(); + } + + g_array_append_vals(rowInfo->iArray, indexes, 2); + indexes[0]= 1; + indexes[1]= 2; + g_array_append_vals(rowInfo->jArray, indexes, 2); + constraints[0]= 1.; + constraints[1]= p->x; + g_array_append_vals(rowInfo->aArray, constraints, 2); +} + + +/* + * Calculate min or max correction factors (as possible) using an LP problem. + * + * Args: + * lp: A linear programming problem with constraints and bounds + * initialized. + * direction: The type of factors desired. Use GLP_MAX for max + * approximation factors (a1, the drift or slope is the + * largest) and GLP_MIN in the other case. + * + * Returns: + * If the calculation was successful, a new Factors struct. Otherwise, NULL. + * The calculation will fail if the hull assumptions are not respected. + */ +static Factors* calculateFactorsLP(glp_prob* const lp, const int direction) +{ + int retval, status; + Factors* factors; + + glp_set_obj_coef(lp, 1, 0.); + glp_set_obj_coef(lp, 2, 1.); + + glp_set_obj_dir(lp, direction); + retval= glp_simplex(lp, NULL); + status= glp_get_status(lp); + + if (retval == 0 && status == GLP_OPT) + { + factors= malloc(sizeof(Factors)); + factors->offset= glp_get_col_prim(lp, 1); + factors->drift= glp_get_col_prim(lp, 2); + } + else + { + factors= NULL; + } + + return factors; +} + + +/* + * Calculate min, max and approx correction factors (as possible) using an LP + * problem. + * + * Args: + * lp A linear programming problem with constraints and bounds + * initialized. + * factors Resulting factors, must be preallocated + */ +static void calculateCompleteFactorsLP(glp_prob* const lp, PairFactors* factors) +{ + factors->min= calculateFactorsLP(lp, GLP_MIN); + factors->max= calculateFactorsLP(lp, GLP_MAX); + + if (factors->min && factors->max) + { + factors->type= ACCURATE; + calculateFactorsMiddle(factors); + } + else if (factors->min || factors->max) + { + factors->type= INCOMPLETE; + } + else + { + factors->type= ABSENT; + } +} + + +/* + * A GFunc for g_queue_foreach() + * + * Args: + * data Point*, a convex hull point + * user_data GArray*, an array of convex hull point absisca values, as + * uint64_t + */ +static void gfAddAbsiscaToArray(gpointer data, gpointer user_data) +{ + Point* p= data; + GArray* a= user_data; + uint64_t v= p->x; + + g_array_append_val(a, v); +} + + +/* + * A GCompareFunc for g_array_sort() + * + * Args: + * a, b uint64_t*, absisca values + * + * Returns: + * "returns less than zero for first arg is less than second arg, zero for + * equal, greater zero if first arg is greater than second arg" + * - the great glib documentation + */ +static gint gcfCompareUint64(gconstpointer a, gconstpointer b) +{ + if (*(uint64_t*) a < *(uint64_t*) b) + { + return -1; + } + else if (*(uint64_t*) a > *(uint64_t*) b) + { + return 1; + } + else + { + return 0; + } +} + + +/* + * Compute synchronization factors using a linear programming approach. + * + * Args: + * syncState: container for synchronization data + */ +static AllFactors* finalizeAnalysisCHullLP(SyncState* const syncState) +{ + AnalysisDataCHull* analysisData= syncState->analysisData; + unsigned int i, j; + AllFactors* lpFactorsArray; + + lpFactorsArray= createAllFactors(syncState->traceNb); + + analysisData->lps= malloc(syncState->traceNb * sizeof(glp_prob**)); + for (i= 0; i < syncState->traceNb; i++) + { + analysisData->lps[i]= malloc(i * sizeof(glp_prob*)); + } + + for (i= 0; i < syncState->traceNb; i++) + { + for (j= 0; j < i; j++) + { + glp_prob* lp; + unsigned int it; + GQueue*** hullArray= analysisData->hullArray; + PairFactors* lpFactors= &lpFactorsArray->pairFactors[i][j]; + + // Create the LP problem + lp= lpCreateProblem(hullArray[i][j], hullArray[j][i]); + analysisData->lps[i][j]= lp; + + // Use the LP problem to find the correction factors for this pair of + // traces + calculateCompleteFactorsLP(lp, lpFactors); + + // If possible, compute synchronization accuracy information for + // graphs + if (syncState->graphsStream && lpFactors->type == ACCURATE) + { + int retval; + char* cwd; + char fileName[43]; + FILE* fp; + GArray* xValues; + + // Open the data file + snprintf(fileName, sizeof(fileName), + "analysis_chull_accuracy-%03u_and_%03u.data", j, i); + fileName[sizeof(fileName) - 1]= '\0'; + + cwd= changeToGraphsDir(syncState->graphsDir); + + if ((fp= fopen(fileName, "w")) == NULL) + { + g_error(strerror(errno)); + } + fprintf(fp, "#%-24s %-25s %-25s %-25s\n", "x", "middle", "min", "max"); + + retval= chdir(cwd); + if (retval == -1) + { + g_error(strerror(errno)); + } + free(cwd); + + // Build the list of absisca values for the points in the accuracy graph + xValues= g_array_sized_new(FALSE, FALSE, sizeof(uint64_t), + g_queue_get_length(hullArray[i][j]) + + g_queue_get_length(hullArray[j][i])); + + g_queue_foreach(hullArray[i][j], &gfAddAbsiscaToArray, xValues); + g_queue_foreach(hullArray[j][i], &gfAddAbsiscaToArray, xValues); + + g_array_sort(xValues, &gcfCompareUint64); + + /* For each absisca value and each optimisation direction, solve the LP + * and write a line in the data file */ + for (it= 0; it < xValues->len; it++) + { + uint64_t time; + CorrectedTime correctedTime; + + time= g_array_index(xValues, uint64_t, it); + timeCorrectionLP(lp, lpFactors, time, &correctedTime); + fprintf(fp, "%24" PRIu64 " %24" PRIu64 " %24" PRIu64 + "%24" PRIu64 "\n", time, correctedTime.time, + correctedTime.min, correctedTime.max); + } + + g_array_free(xValues, TRUE); + fclose(fp); + } + } + } + + if (syncState->stats) + { + lpFactorsArray->refCount++; + analysisData->stats->lpFactors= lpFactorsArray; + } + + if (syncState->graphsStream) + { + lpFactorsArray->refCount++; + analysisData->graphsData->lpFactors= lpFactorsArray; + } + + return lpFactorsArray; +} + + +/* + * Perform correction on one time value and calculate accuracy bounds. + * + * Args: + * lp: Linear Programming problem containing the coefficients for + * the trace pair between which to perform time correction. + * lpFactors: Correction factors for this trace pair, the factors must be + * of type ACCURATE. + * time: Time value to correct. + * correctedTime: Result of the time correction, preallocated. + */ +void timeCorrectionLP(glp_prob* const lp, const PairFactors* const lpFactors, + const uint64_t time, CorrectedTime* const correctedTime) +{ + unsigned int it; + const struct + { + int direction; + size_t offset; + } loopValues[]= { + {GLP_MIN, offsetof(CorrectedTime, min)}, + {GLP_MAX, offsetof(CorrectedTime, max)} + }; + + glp_set_obj_coef(lp, 1, 1.); + glp_set_obj_coef(lp, 2, time); + + g_assert(lpFactors->type == ACCURATE); + + correctedTime->time= lpFactors->approx->offset + lpFactors->approx->drift + * time; + + for (it= 0; it < ARRAY_SIZE(loopValues); it++) + { + int status; + int retval; + + glp_set_obj_dir(lp, loopValues[it].direction); + retval= glp_simplex(lp, NULL); + status= glp_get_status(lp); + + g_assert(retval == 0 && status == GLP_OPT); + *(uint64_t*) ((void*) correctedTime + loopValues[it].offset)= + round(glp_get_obj_val(lp)); + } +} + + +/* + * Write the analysis-specific graph lines in the gnuplot script. + * + * Args: + * syncState: container for synchronization data + * i: first trace number + * j: second trace number, garanteed to be larger than i + */ +static void writeAnalysisTraceTimeBackPlotsCHull(SyncState* const syncState, + const unsigned int i, const unsigned int j) +{ + if (((AnalysisDataCHull*) + syncState->analysisData)->graphsData->lpFactors->pairFactors[j][i].type + == ACCURATE) + { + fprintf(syncState->graphsStream, + "\t\"analysis_chull_accuracy-%1$03u_and_%2$03u.data\" " + "using 1:(($3 - $2) / clock_freq_%2$u):(($4 - $2) / clock_freq_%2$u) " + "title \"Synchronization accuracy\" " + "with filledcurves linewidth 2 linetype 1 " + "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i, + j); + } +} + + +/* + * Write the analysis-specific graph lines in the gnuplot script. + * + * Args: + * syncState: container for synchronization data + * i: first trace number + * j: second trace number, garanteed to be larger than i + */ +static void writeAnalysisTraceTimeForePlotsCHull(SyncState* const syncState, + const unsigned int i, const unsigned int j) +{ + if (((AnalysisDataCHull*) + syncState->analysisData)->graphsData->lpFactors->pairFactors[j][i].type + == ACCURATE) + { + fprintf(syncState->graphsStream, + "\t\"analysis_chull_accuracy-%1$03u_and_%2$03u.data\" " + "using 1:(($3 - $2) / clock_freq_%2$u) notitle " + "with lines linewidth 2 linetype 1 " + "linecolor rgb \"gray60\", \\\n" + "\t\"analysis_chull_accuracy-%1$03u_and_%2$03u.data\" " + "using 1:(($4 - $2) / clock_freq_%2$u) notitle " + "with lines linewidth 2 linetype 1 " + "linecolor rgb \"gray60\", \\\n", i, j); + } +} + + +/* + * Write the analysis-specific graph lines in the gnuplot script. + * + * Args: + * syncState: container for synchronization data + * i: first trace number + * j: second trace number, garanteed to be larger than i + */ +static void writeAnalysisTraceTraceBackPlotsCHull(SyncState* const syncState, + const unsigned int i, const unsigned int j) +{ + if (((AnalysisDataCHull*) + syncState->analysisData)->graphsData->lpFactors->pairFactors[j][i].type + == ACCURATE) + { + fprintf(syncState->graphsStream, + "\t\"analysis_chull_accuracy-%1$03u_and_%2$03u.data\" " + "using 1:3:4 " + "title \"Synchronization accuracy\" " + "with filledcurves linewidth 2 linetype 1 " + "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i, j); + } +} +#endif diff --git a/lttv/lttv/sync/event_analysis_chull.h b/lttv/lttv/sync/event_analysis_chull.h index c1286d66..27dfea2b 100644 --- a/lttv/lttv/sync/event_analysis_chull.h +++ b/lttv/lttv/sync/event_analysis_chull.h @@ -22,6 +22,9 @@ #include "data_structures.h" +#ifdef HAVE_LIBGLPK +#include +#endif typedef struct { @@ -33,8 +36,8 @@ typedef struct { unsigned int dropped; - /* allFactors is divided into three parts depending on the position of an - * element allFactors->pairFactors[i][j]: + /* geoFactors is divided into three parts depending on the position of an + * element geoFactors->pairFactors[i][j]: * Lower triangular part of the matrix * i > j * This contains the factors between nodes i and j. These factors @@ -69,10 +72,39 @@ typedef struct * 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 + * FAIL, + * min and max are not available because the algorithms are defective. One * of min or max (but not both) is NULL. The other is initialized. */ + AllFactors* geoFactors; + +#ifdef HAVE_LIBGLPK + /* Synchronization factors, as calculated via LP, for comparison. Same + * structure as geoFactors. + * + * 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. + * + * 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 when the hulls do not respect + * assumptions. Also used for factors in the upper triangular matrix. + */ + AllFactors* lpFactors; +#endif + + /* This is AnalysisStatsCHull.lpFactors if it is available or else + * AnalysisStatsCHull.geoFactors. + */ AllFactors* allFactors; } AnalysisStatsCHull; @@ -90,9 +122,16 @@ typedef struct */ FILE*** hullPoints; - /* This is the same array as AnalysisStatsCHull.allFactors. + /* This is AnalysisStatsCHull.lpFactors if it is available or else + * AnalysisStatsCHull.geoFactors. */ AllFactors* allFactors; + +#ifdef HAVE_LIBGLPK + /* This is the same array as AnalysisStatsCHull.lpFactors. + */ + AllFactors* lpFactors; +#endif } AnalysisGraphsDataCHull; @@ -139,14 +178,18 @@ typedef struct */ GQueue*** hullArray; +#ifdef HAVE_LIBGLPK + /* glp_prob* lps[traceNum][traceNum] + * + * Only the lower triangular part of the matrix is allocated, that is + * lps[i][j] where i > j */ + glp_prob*** lps; +#endif + AnalysisStatsCHull* stats; AnalysisGraphsDataCHull* graphsData; } AnalysisDataCHull; void registerAnalysisCHull(); -AllFactors* calculateAllFactors(struct _SyncState* const syncState); - -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 4aa6a7a5..d5c3be29 100644 --- a/lttv/lttv/sync/event_analysis_eval.c +++ b/lttv/lttv/sync/event_analysis_eval.c @@ -35,7 +35,6 @@ #include "lookup3.h" #include "sync_chain.h" -#include "event_analysis_chull.h" #include "event_analysis_eval.h" @@ -46,15 +45,6 @@ struct WriteHistogramInfo FILE* graphsStream; }; -#ifdef HAVE_LIBGLPK -struct LPAddRowInfo -{ - glp_prob* lp; - int boundType; - GArray* iArray, * jArray, * aArray; -}; -#endif - // Functions common to all analysis modules static void initAnalysisEval(SyncState* const syncState); static void destroyAnalysisEval(SyncState* const syncState); @@ -67,14 +57,6 @@ static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const broadcast); 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); -static void writeAnalysisTraceTimeForePlotsEval(SyncState* const syncState, - const unsigned int i, const unsigned int j); -static void writeAnalysisTraceTraceBackPlotsEval(SyncState* const syncState, - const unsigned int i, const unsigned int j); -static void writeAnalysisTraceTraceForePlotsEval(SyncState* const syncState, - const unsigned int i, const unsigned int j); // Functions specific to this module static guint ghfRttKeyHash(gconstpointer key); @@ -109,23 +91,6 @@ static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey, static void updateBounds(Bounds** const bounds, Event* const e1, Event* const e2); -static void finalizeAnalysisEvalLP(SyncState* const syncState); -// The next group of functions is only needed when computing synchronization -// accuracy. -#ifdef HAVE_LIBGLPK -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, PairFactors* - factors); -static inline void finalizeAnalysisEvalLP(SyncState* const syncState); -static void gfAddAbsiscaToArray(gpointer data, gpointer user_data); -static gint gcfCompareDouble(gconstpointer a, gconstpointer b); -#else -static void finalizeAnalysisEvalLP(SyncState* const syncState); -#endif - // initialized in registerAnalysisEval() double binBase; @@ -139,12 +104,7 @@ static AnalysisModule analysisModuleEval= { .analyzeBroadcast= &analyzeBroadcastEval, .finalizeAnalysis= &finalizeAnalysisEval, .printAnalysisStats= &printAnalysisStatsEval, - .graphFunctions= { - .writeTraceTimeBackPlots= &writeAnalysisTraceTimeBackPlotsEval, - .writeTraceTimeForePlots= &writeAnalysisTraceTimeForePlotsEval, - .writeTraceTraceBackPlots= &writeAnalysisTraceTraceBackPlotsEval, - .writeTraceTraceForePlots= &writeAnalysisTraceTraceForePlotsEval, - } + .graphFunctions= {} }; static ModuleOption optionEvalRttFile= { @@ -223,11 +183,6 @@ static void initAnalysisEval(SyncState* const syncState) analysisData->stats->exchangeRtt= g_hash_table_new_full(&ghfRttKeyHash, &gefRttKeyEqual, &gdnDestroyRttKey, &gdnDestroyDouble); - -#ifdef HAVE_LIBGLPK - analysisData->stats->chFactorsArray= NULL; - analysisData->stats->lpFactorsArray= NULL; -#endif } if (syncState->graphsStream) @@ -250,25 +205,6 @@ static void initAnalysisEval(SyncState* const syncState) graphs->bounds[i][j].max= 0; } } - -#ifdef HAVE_LIBGLPK - graphs->lps= NULL; - graphs->lpFactorsArray= NULL; -#endif - } - - if (syncState->stats || syncState->graphsStream) - { - GList* result; - - analysisData->chullSS= malloc(sizeof(SyncState)); - memcpy(analysisData->chullSS, syncState, sizeof(SyncState)); - analysisData->chullSS->stats= false; - analysisData->chullSS->analysisData= NULL; - result= g_queue_find_custom(&analysisModules, "chull", - &gcfCompareAnalysis); - analysisData->chullSS->analysisModule= (AnalysisModule*) result->data; - analysisData->chullSS->analysisModule->initAnalysis(analysisData->chullSS); } } @@ -556,11 +492,6 @@ static void destroyAnalysisEval(SyncState* const syncState) g_hash_table_destroy(stats->exchangeRtt); -#ifdef HAVE_LIBGLPK - freeAllFactors(stats->chFactorsArray, syncState->traceNb); - freeAllFactors(stats->lpFactorsArray, syncState->traceNb); -#endif - free(stats); } @@ -579,36 +510,9 @@ static void destroyAnalysisEval(SyncState* const syncState) } free(graphs->bounds); -#ifdef HAVE_LIBGLPK - for (i= 0; i < syncState->traceNb; i++) - { - unsigned int j; - - for (j= 0; j < i; j++) - { - // There seems to be a memory leak in glpk, valgrind reports a - // loss (reachable) even if the problem is deleted - glp_delete_prob(graphs->lps[i][j]); - } - free(graphs->lps[i]); - } - free(graphs->lps); - - if (!syncState->stats) - { - freeAllFactors(graphs->lpFactorsArray, syncState->traceNb); - } -#endif - free(graphs); } - if (syncState->stats || syncState->graphsStream) - { - analysisData->chullSS->analysisModule->destroyAnalysis(analysisData->chullSS); - free(analysisData->chullSS); - } - free(syncState->analysisData); syncState->analysisData= NULL; } @@ -709,12 +613,6 @@ static void analyzeMessageEval(SyncState* const syncState, Message* const updateBounds(analysisData->graphs->bounds, message->inE, message->outE); } - - if (syncState->stats || syncState->graphsStream) - { - analysisData->chullSS->analysisModule->analyzeMessage(analysisData->chullSS, - message); - } } @@ -917,8 +815,6 @@ static AllFactors* finalizeAnalysisEval(SyncState* const syncState) analysisData->graphs->histograms= NULL; } - finalizeAnalysisEvalLP(syncState); - return createAllFactors(syncState->traceNb); } @@ -1022,47 +918,6 @@ static void printAnalysisStatsEval(SyncState* const syncState) "\t\tHost pair RTT from exchanges RTTs from file (ms)\n"); g_hash_table_foreach(analysisData->stats->exchangeRtt, &ghfPrintExchangeRtt, analysisData->rttInfo); - -#ifdef HAVE_LIBGLPK - printf("\tConvex hull factors comparisons:\n" - "\t\tTrace pair Factors type Differences (lp - chull)\n" - "\t\t a0 a1\n" - "\t\t Min Max Min Max\n"); - - for (i= 0; i < syncState->traceNb; i++) - { - for (j= 0; j < 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 == ACCURATE) - { - printf("%-13s %-10.4g %-10.4g %-10.4g %.4g\n", - approxNames[lpFactors->type], - lpFactors->min->offset - chFactors->min->offset, - lpFactors->max->offset - chFactors->max->offset, - lpFactors->min->drift - chFactors->min->drift, - lpFactors->max->drift - chFactors->max->drift); - } - else if (lpFactors->type == ABSENT) - { - printf("%s\n", approxNames[lpFactors->type]); - } - } - else - { - printf("Different! %s and %s\n", approxNames[lpFactors->type], - approxNames[chFactors->type]); - } - } - } -#endif } @@ -1537,505 +1392,3 @@ static void updateBounds(Bounds** const bounds, Event* const e1, Event* const tpBounds->max= messageTime; } } - - -#ifdef HAVE_LIBGLPK -/* - * Create the linear programming problem containing the constraints defined by - * two half-hulls. The objective function and optimization directions are not - * written. - * - * Args: - * syncState: container for synchronization data - * i: first trace number - * j: second trace number, garanteed to be larger than i - * Returns: - * A new glp_prob*, this problem must be freed by the caller with - * glp_delete_prob() - */ -static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const - upperHull) -{ - unsigned int it; - const int zero= 0; - const double zeroD= 0.; - glp_prob* lp= glp_create_prob(); - unsigned int hullPointNb= g_queue_get_length(lowerHull) + - g_queue_get_length(upperHull); - GArray* iArray= g_array_sized_new(FALSE, FALSE, sizeof(int), hullPointNb + - 1); - GArray* jArray= g_array_sized_new(FALSE, FALSE, sizeof(int), hullPointNb + - 1); - GArray* aArray= g_array_sized_new(FALSE, FALSE, sizeof(double), - hullPointNb + 1); - struct { - GQueue* hull; - struct LPAddRowInfo rowInfo; - } loopValues[2]= { - {lowerHull, {lp, GLP_UP, iArray, jArray, aArray}}, - {upperHull, {lp, GLP_LO, iArray, jArray, aArray}}, - }; - - // Create the LP problem - glp_term_out(GLP_OFF); - if (hullPointNb > 0) - { - glp_add_rows(lp, hullPointNb); - } - glp_add_cols(lp, 2); - - glp_set_col_name(lp, 1, "a0"); - glp_set_col_bnds(lp, 1, GLP_FR, 0., 0.); - glp_set_col_name(lp, 2, "a1"); - glp_set_col_bnds(lp, 2, GLP_LO, 0., 0.); - - // Add row constraints - g_array_append_val(iArray, zero); - g_array_append_val(jArray, zero); - g_array_append_val(aArray, zeroD); - - for (it= 0; it < sizeof(loopValues) / sizeof(*loopValues); it++) - { - g_queue_foreach(loopValues[it].hull, &gfLPAddRow, - &loopValues[it].rowInfo); - } - - g_assert_cmpuint(iArray->len, ==, jArray->len); - g_assert_cmpuint(jArray->len, ==, aArray->len); - g_assert_cmpuint(aArray->len - 1, ==, hullPointNb * 2); - - glp_load_matrix(lp, aArray->len - 1, &g_array_index(iArray, int, 0), - &g_array_index(jArray, int, 0), &g_array_index(aArray, double, 0)); - - glp_scale_prob(lp, GLP_SF_AUTO); - - g_array_free(iArray, TRUE); - g_array_free(jArray, TRUE); - g_array_free(aArray, TRUE); - - return lp; -} - - -/* - * A GFunc for g_queue_foreach(). Add constraints and bounds for one row. - * - * Args: - * data Point*, synchronization point for which to add an LP row - * (a constraint) - * user_data LPAddRowInfo* - */ -static void gfLPAddRow(gpointer data, gpointer user_data) -{ - Point* p= data; - struct LPAddRowInfo* rowInfo= user_data; - int indexes[2]; - double constraints[2]; - - indexes[0]= g_array_index(rowInfo->iArray, int, rowInfo->iArray->len - 1) + 1; - indexes[1]= indexes[0]; - - if (rowInfo->boundType == GLP_UP) - { - glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_UP, 0., p->y); - } - else if (rowInfo->boundType == GLP_LO) - { - glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_LO, p->y, 0.); - } - else - { - g_assert_not_reached(); - } - - g_array_append_vals(rowInfo->iArray, indexes, 2); - indexes[0]= 1; - indexes[1]= 2; - g_array_append_vals(rowInfo->jArray, indexes, 2); - constraints[0]= 1.; - constraints[1]= p->x; - g_array_append_vals(rowInfo->aArray, constraints, 2); -} - - -/* - * Calculate min or max correction factors (as possible) using an LP problem. - * - * Args: - * lp: A linear programming problem with constraints and bounds - * initialized. - * direction: The type of factors desired. Use GLP_MAX for max - * approximation factors (a1, the drift or slope is the - * largest) and GLP_MIN in the other case. - * - * Returns: - * If the calculation was successful, a new Factors struct. Otherwise, NULL. - * The calculation will fail if the hull assumptions are not respected. - */ -static Factors* calculateFactors(glp_prob* const lp, const int direction) -{ - int retval, status; - Factors* factors; - - glp_set_obj_coef(lp, 1, 0.); - glp_set_obj_coef(lp, 2, 1.); - - glp_set_obj_dir(lp, direction); - retval= glp_simplex(lp, NULL); - status= glp_get_status(lp); - - if (retval == 0 && status == GLP_OPT) - { - factors= malloc(sizeof(Factors)); - factors->offset= glp_get_col_prim(lp, 1); - factors->drift= glp_get_col_prim(lp, 2); - } - else - { - factors= NULL; - } - - return factors; -} - - -/* - * Calculate min, max and approx correction factors (as possible) using an LP - * problem. - * - * Args: - * lp: A linear programming problem with constraints and bounds - * initialized. - * - * Returns: - * 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, PairFactors* factors) -{ - factors->min= calculateFactors(lp, GLP_MIN); - factors->max= calculateFactors(lp, GLP_MAX); - - if (factors->min && factors->max) - { - factors->type= ACCURATE; - calculateFactorsMiddle(factors); - } - else if (factors->min || factors->max) - { - factors->type= INCOMPLETE; - factors->approx= NULL; - } - else - { - factors->type= ABSENT; - factors->approx= NULL; - } -} - - -/* - * A GFunc for g_queue_foreach() - * - * Args: - * data Point*, a convex hull point - * user_data GArray*, an array of convex hull point absisca values, as - * double - */ -static void gfAddAbsiscaToArray(gpointer data, gpointer user_data) -{ - Point* p= data; - GArray* a= user_data; - double v= p->x; - - g_array_append_val(a, v); -} - - -/* - * A GCompareFunc for g_array_sort() - * - * Args: - * a, b double*, absisca values - * - * Returns: - * "returns less than zero for first arg is less than second arg, zero for - * equal, greater zero if first arg is greater than second arg" - * - the great glib documentation - */ -static gint gcfCompareDouble(gconstpointer a, gconstpointer b) -{ - if (*(double*) a < *(double*) b) - { - return -1; - } - else if (*(double*) a > *(double*) b) - { - return 1; - } - else - { - return 0; - } -} -#endif - - -/* - * Compute synchronization factors using a linear programming approach. - * Compute the factors using analysis_chull. Compare the two. - * - * When the solver library, glpk, is not available at build time, only compute - * the factors using analysis_chull. This is to make sure that module runs its - * finalize function so that its graph functions can be called later. - * - * Args: - * syncState: container for synchronization data - */ -static void finalizeAnalysisEvalLP(SyncState* const syncState) -{ - AnalysisDataEval* analysisData= syncState->analysisData; -#ifdef HAVE_LIBGLPK - unsigned int i, j; - AnalysisDataCHull* chAnalysisData= analysisData->chullSS->analysisData; - AllFactors* lpFactorsArray; - - if (!syncState->stats && !syncState->graphsStream) - { - return; - } - - /* Because of matching_distributor, this analysis may be called twice. - * Only run it once */ - if ((syncState->graphsStream && analysisData->graphs->lps != NULL) || - (syncState->stats && analysisData->stats->chFactorsArray != NULL)) - { - return; - } - - lpFactorsArray= createAllFactors(syncState->traceNb); - - if (syncState->stats) - { - analysisData->stats->chFactorsArray= - calculateAllFactors(analysisData->chullSS); - analysisData->stats->lpFactorsArray= lpFactorsArray; - } - - if (syncState->graphsStream) - { - analysisData->graphs->lps= malloc(syncState->traceNb * - sizeof(glp_prob**)); - for (i= 0; i < syncState->traceNb; i++) - { - analysisData->graphs->lps[i]= malloc(i * sizeof(glp_prob*)); - } - analysisData->graphs->lpFactorsArray= lpFactorsArray; - } - - for (i= 0; i < syncState->traceNb; i++) - { - for (j= 0; j < i; j++) - { - glp_prob* lp; - - // Create the LP problem - lp= lpCreateProblem(chAnalysisData->hullArray[i][j], - chAnalysisData->hullArray[j][i]); - - // Use the LP problem to find the correction factors for this pair of - // traces - calculateCompleteFactors(lp, &lpFactorsArray->pairFactors[i][j]); - - if (syncState->graphsStream) - { - analysisData->graphs->lps[i][j]= lp; - } - else - { - glp_delete_prob(lp); - } - } - } -#endif - - freeAllFactors(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS), - analysisData->chullSS->traceNb); -} - - -/* - * Compute synchronization accuracy information using a linear programming - * approach. Write the neccessary data files and plot lines in the gnuplot - * script. - * - * When the solver library, glpk, is not available at build time nothing is - * actually produced. - * - * Args: - * syncState: container for synchronization data - * i: first trace number - * j: second trace number, garanteed to be larger than i - */ -static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState, - const unsigned int i, const unsigned int j) -{ -#ifdef HAVE_LIBGLPK - unsigned int it; - AnalysisDataEval* analysisData= syncState->analysisData; - AnalysisGraphsEval* graphs= analysisData->graphs; - GQueue*** hullArray= ((AnalysisDataCHull*) - analysisData->chullSS->analysisData)->hullArray; - PairFactors* lpFactors= &graphs->lpFactorsArray->pairFactors[j][i]; - glp_prob* lp= graphs->lps[j][i]; - - if (lpFactors->type == ACCURATE) - { - int retval; - char* cwd; - char fileName[40]; - FILE* fp; - GArray* xValues; - - // Open the data file - snprintf(fileName, 40, "analysis_eval_accuracy-%03u_and_%03u.data", i, j); - fileName[sizeof(fileName) - 1]= '\0'; - - cwd= changeToGraphsDir(syncState->graphsDir); - - if ((fp= fopen(fileName, "w")) == NULL) - { - g_error(strerror(errno)); - } - fprintf(fp, "#%-24s %-25s %-25s %-25s\n", "x", "middle", "min", "max"); - - retval= chdir(cwd); - if (retval == -1) - { - g_error(strerror(errno)); - } - free(cwd); - - // Build the list of absisca values for the points in the accuracy graph - xValues= g_array_sized_new(FALSE, FALSE, sizeof(double), - g_queue_get_length(hullArray[i][j]) + - g_queue_get_length(hullArray[j][i])); - - g_queue_foreach(hullArray[i][j], &gfAddAbsiscaToArray, xValues); - g_queue_foreach(hullArray[j][i], &gfAddAbsiscaToArray, xValues); - - g_array_sort(xValues, &gcfCompareDouble); - - /* For each absisca value and each optimisation direction, solve the LP - * and write a line in the data file */ - for (it= 0; it < xValues->len; it++) - { - unsigned int it2; - int directions[]= {GLP_MIN, GLP_MAX}; - glp_set_obj_coef(lp, 1, 1.); - glp_set_obj_coef(lp, 2, g_array_index(xValues, double, it)); - - fprintf(fp, "%25.9f %25.9f", g_array_index(xValues, double, it), - lpFactors->approx->offset + lpFactors->approx->drift * - g_array_index(xValues, double, it)); - for (it2= 0; it2 < sizeof(directions) / sizeof(*directions); it2++) - { - int status; - - glp_set_obj_dir(lp, directions[it2]); - retval= glp_simplex(lp, NULL); - status= glp_get_status(lp); - - g_assert(retval == 0 && status == GLP_OPT); - fprintf(fp, " %25.9f", glp_get_obj_val(lp)); - } - fprintf(fp, "\n"); - } - - g_array_free(xValues, TRUE); - fclose(fp); - - fprintf(syncState->graphsStream, - "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" " - "using 1:(($3 - $2) / clock_freq_%2$u):(($4 - $2) / clock_freq_%2$u) " - "title \"Synchronization accuracy\" " - "with filledcurves linewidth 2 linetype 1 " - "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i, - j); - } -#endif -} - - -/* - * Write the analysis-specific graph lines in the gnuplot script. - * - * When the solver library, glpk, is not available at build time nothing is - * actually produced. - * - * Args: - * syncState: container for synchronization data - * i: first trace number - * j: second trace number, garanteed to be larger than i - */ -static void writeAnalysisTraceTimeForePlotsEval(SyncState* const syncState, - const unsigned int i, const unsigned int j) -{ -#ifdef HAVE_LIBGLPK - if (((AnalysisDataEval*) - syncState->analysisData)->graphs->lpFactorsArray->pairFactors[j][i].type - == ACCURATE) - { - fprintf(syncState->graphsStream, - "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" " - "using 1:(($3 - $2) / clock_freq_%2$u) notitle " - "with lines linewidth 2 linetype 1 " - "linecolor rgb \"gray60\", \\\n" - "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" " - "using 1:(($4 - $2) / clock_freq_%2$u) notitle " - "with lines linewidth 2 linetype 1 " - "linecolor rgb \"gray60\", \\\n", i, j); - } -#endif -} - - -/* - * Write the analysis-specific graph lines in the gnuplot script. - * - * Args: - * syncState: container for synchronization data - * i: first trace number - * j: second trace number, garanteed to be larger than i - */ -static void writeAnalysisTraceTraceBackPlotsEval(SyncState* const syncState, - const unsigned int i, const unsigned int j) -{ -#ifdef HAVE_LIBGLPK - fprintf(syncState->graphsStream, - "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" " - "using 1:3:4 " - "title \"Synchronization accuracy\" " - "with filledcurves linewidth 2 linetype 1 " - "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i, j); -#endif -} - - -/* - * Write the analysis-specific graph lines in the gnuplot script. - * - * Args: - * syncState: container for synchronization data - * i: first trace number - * j: second trace number, garanteed to be larger than i - */ -static void writeAnalysisTraceTraceForePlotsEval(SyncState* const syncState, - const unsigned int i, const unsigned int j) -{ - AnalysisDataEval* analysisData= syncState->analysisData; - - analysisData->chullSS->analysisModule->graphFunctions.writeTraceTraceForePlots(analysisData->chullSS, - i, j); -} diff --git a/lttv/lttv/sync/event_analysis_eval.h b/lttv/lttv/sync/event_analysis_eval.h index dbd4ac95..d6d39c2f 100644 --- a/lttv/lttv/sync/event_analysis_eval.h +++ b/lttv/lttv/sync/event_analysis_eval.h @@ -23,9 +23,6 @@ #endif #include -#ifdef HAVE_LIBGLPK -#include -#endif #include "data_structures.h" @@ -61,12 +58,6 @@ typedef struct * For this table, saddr and daddr are swapped as necessary such that * saddr < daddr */ GHashTable* exchangeRtt; - -#ifdef HAVE_LIBGLPK - // Only the lower triangular part of theses matrixes is used - AllFactors* chFactorsArray; - AllFactors* lpFactorsArray; -#endif } AnalysisStatsEval; #define BIN_NB 1001 @@ -124,18 +115,6 @@ typedef struct * Only the lower triangular part of the matrix is allocated, that is * bounds[i][j] where i > j */ Bounds** bounds; - -#ifdef HAVE_LIBGLPK - /* glp_prob* lps[traceNum][traceNum] - * - * Only the lower triangular part of the matrix is allocated, that is - * lps[i][j] where i > j */ - glp_prob*** lps; - - /* Only the lower triangular part of the matrix is allocated, that is - * lpFactorsArray[i][j] where i > j */ - AllFactors* lpFactorsArray; -#endif } AnalysisGraphsEval; typedef struct @@ -143,11 +122,6 @@ typedef struct // double* rttInfo[RttKey] GHashTable* rttInfo; - /* The convex hull analysis is encapsulated and messages are passed to it - * so that it builds the convex hulls. These are reused in the linear - * program. */ - struct _SyncState* chullSS; - AnalysisStatsEval* stats; AnalysisGraphsEval* graphs; } AnalysisDataEval; -- 2.34.1