X-Git-Url: https://git.lttng.org/?a=blobdiff_plain;f=lttv%2Flttv%2Fsync%2Fevent_analysis_linreg.c;h=165f84e20873eb53004bcc73fb51e296ef9bafdc;hb=0a87ec9a018cc9731ce3b04309eaa4dcc77df6d2;hp=bda898740f4cf8d7ccb965e97fee3e0a46bc2f35;hpb=9c7696b8589e76aed870b15cabd09a162d468621;p=lttv.git diff --git a/lttv/lttv/sync/event_analysis_linreg.c b/lttv/lttv/sync/event_analysis_linreg.c index bda89874..165f84e2 100644 --- a/lttv/lttv/sync/event_analysis_linreg.c +++ b/lttv/lttv/sync/event_analysis_linreg.c @@ -36,27 +36,13 @@ static void initAnalysisLinReg(SyncState* const syncState); static void destroyAnalysisLinReg(SyncState* const syncState); static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const exchange); -static GArray* finalizeAnalysisLinReg(SyncState* const syncState); +static AllFactors* finalizeAnalysisLinReg(SyncState* const syncState); static void printAnalysisStatsLinReg(SyncState* const syncState); static void writeAnalysisGraphsPlotsLinReg(SyncState* const syncState, const unsigned int i, const unsigned int j); // Functions specific to this module static void finalizeLSA(SyncState* const syncState); -static void doGraphProcessing(SyncState* const syncState); -static GArray* calculateFactors(SyncState* const syncState); -static void shortestPath(Fit* const* const fitArray, const unsigned int - traceNum, const unsigned int traceNb, double* const distances, - unsigned int* const previousVertex); -static double sumDistances(const double* const distances, const unsigned int - traceNb); -static void reduceFactors(Fit* const* const fitArray, const unsigned int* const - previousVertex, const unsigned int traceNum, double* const drift, - double* const offset, double* const stDev); - -// Graph-related Glib functions -static void gfGraphDestroy(gpointer data, gpointer user_data); -static gint gcfGraphTraceCompare(gconstpointer a, gconstpointer b); static AnalysisModule analysisModuleLinReg= { @@ -146,9 +132,6 @@ static void destroyAnalysisLinReg(SyncState* const syncState) } free(analysisData->fitArray); - g_queue_foreach(analysisData->graphList, &gfGraphDestroy, NULL); - g_queue_free(analysisData->graphList); - if (syncState->stats) { free(analysisData->stDev); @@ -224,24 +207,38 @@ static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const ex * syncState container for synchronization data. * * Returns: - * Factors[traceNb] synchronization factors for each trace + * AllFactors* synchronization factors for each trace pair */ -static GArray* finalizeAnalysisLinReg(SyncState* const syncState) +static AllFactors* finalizeAnalysisLinReg(SyncState* const syncState) { - GArray* factors; + AllFactors* result; + unsigned int i, j; + AnalysisDataLinReg* analysisData= (AnalysisDataLinReg*) + syncState->analysisData; - // Finalize the processing finalizeLSA(syncState); - // Find a reference node and structure nodes in a graph - doGraphProcessing(syncState); + result= createAllFactors(syncState->traceNb); - /* Calculate the resulting offset and drift between each trace and its - * reference - */ - factors= calculateFactors(syncState); + for (i= 0; i < syncState->traceNb; i++) + { + for (j= 0; j < syncState->traceNb; j++) + { + if (i != j) + { + Fit* fit; + + fit= &analysisData->fitArray[i][j]; + result->pairFactors[i][j].type= APPROXIMATE; + result->pairFactors[i][j].approx= malloc(sizeof(Factors)); + result->pairFactors[i][j].approx->drift= 1. + fit->x; + result->pairFactors[i][j].approx->offset= fit->d0; + result->pairFactors[i][j].accuracy= fit->e; + } + } + } - return factors; + return result; } @@ -285,39 +282,6 @@ static void printAnalysisStatsLinReg(SyncState* const syncState) 0. ? '-' : '+', fabs(fit->x), fit->e); } } - - printf("\tTree:\n"); - for (i= 0; i < syncState->traceNb; i++) - { - GList* result; - - result= g_queue_find_custom(analysisData->graphList, &i, - &gcfGraphTraceCompare); - if (result != NULL) - { - Graph* graph; - - graph= (Graph*) result->data; - - printf("\t\ttrace %u reference %u previous vertex ", i, - graph->reference); - - if (i == graph->reference) - { - printf("- "); - } - else - { - printf("%u ", graph->previousVertex[i]); - } - - printf("stdev= %g\n", analysisData->stDev[i]); - } - else - { - g_error("Trace %d not part of a graph\n", i); - } - } } @@ -366,369 +330,6 @@ static void finalizeLSA(SyncState* const syncState) } -/* - * Structure nodes in graphs of nodes that had exchanges. Each graph has a - * reference node, the one that can reach the others with the smallest - * cummulative error. - * - * Args: - * syncState: container for synchronization data. - * This function allocates these analysisData members: - * graphList - */ -static void doGraphProcessing(SyncState* const syncState) -{ - unsigned int i, j; - double* distances; - unsigned int* previousVertex; - AnalysisDataLinReg* analysisData; - - analysisData= (AnalysisDataLinReg*) syncState->analysisData; - - distances= malloc(syncState->traceNb * sizeof(double)); - previousVertex= malloc(syncState->traceNb * sizeof(unsigned int)); - analysisData->graphList= g_queue_new(); - - for (i= 0; i < syncState->traceNb; i++) - { - double errorSum; - GList* result; - - // Perform shortest path search - g_debug("shortest path trace %d, distances: ", i); - shortestPath(analysisData->fitArray, i, syncState->traceNb, distances, - previousVertex); - - for (j= 0; j < syncState->traceNb; j++) - { - g_debug("%g, ", distances[j]); - } - g_debug("previousVertex: "); - for (j= 0; j < syncState->traceNb; j++) - { - g_debug("%u, ", previousVertex[j]); - } - - // Group in graphs nodes that have exchanges - errorSum= sumDistances(distances, syncState->traceNb); - result= g_queue_find_custom(analysisData->graphList, &i, - &gcfGraphTraceCompare); - if (result != NULL) - { - Graph* graph; - - g_debug("found graph"); - graph= (Graph*) result->data; - if (errorSum < graph->errorSum) - { - g_debug("new reference"); - graph->errorSum= errorSum; - free(graph->previousVertex); - graph->previousVertex= previousVertex; - graph->reference= i; - previousVertex= malloc(syncState->traceNb * sizeof(unsigned - int)); - } - } - else - { - Graph* newGraph; - - g_debug("creating new graph"); - newGraph= malloc(sizeof(Graph)); - newGraph->errorSum= errorSum; - newGraph->previousVertex= previousVertex; - newGraph->reference= i; - previousVertex= malloc(syncState->traceNb * sizeof(unsigned int)); - - g_queue_push_tail(analysisData->graphList, newGraph); - } - } - - free(previousVertex); - free(distances); -} - - -/* - * Calculate the resulting offset and drift between each trace and its - * reference. - * - * Args: - * syncState: container for synchronization data. - * - * Returns: - * Factors[traceNb] synchronization factors for each trace - */ -static GArray* calculateFactors(SyncState* const syncState) -{ - unsigned int i; - AnalysisDataLinReg* analysisData; - GArray* factors; - - analysisData= (AnalysisDataLinReg*) syncState->analysisData; - factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors), - syncState->traceNb); - g_array_set_size(factors, syncState->traceNb); - - // Calculate the resulting offset and drift between each trace and its - // reference - for (i= 0; i < syncState->traceNb; i++) - { - GList* result; - - result= g_queue_find_custom(analysisData->graphList, &i, - &gcfGraphTraceCompare); - if (result != NULL) - { - Graph* graph; - double stDev; - Factors* traceFactors; - - graph= (Graph*) result->data; - traceFactors= &g_array_index(factors, Factors, i); - - reduceFactors(analysisData->fitArray, graph->previousVertex, i, - &traceFactors->drift, &traceFactors->offset, &stDev); - - if (syncState->stats) - { - analysisData->stDev[i]= stDev; - } - } - else - { - g_error("Trace %d not part of a graph\n", i); - } - } - - return factors; -} - - -/* - * Single-source shortest path search to find the path with the lowest error to - * convert one node's time to another. - * Uses Dijkstra's algorithm - * - * Args: - * fitArray: array with the regression parameters - * traceNum: reference node - * traceNb: number of traces = number of nodes - * distances: array of computed distance from source node to node i, - * INFINITY if i is unreachable, preallocated to the number of - * nodes - * previousVertex: previous vertex from a node i on the way to the source, - * UINT_MAX if i is not on the way or is the source, - * preallocated to the number of nodes - */ -static void shortestPath(Fit* const* const fitArray, const unsigned int - traceNum, const unsigned int traceNb, double* const distances, unsigned - int* const previousVertex) -{ - bool* visited; - unsigned int i, j; - - visited= malloc(traceNb * sizeof(bool)); - - for (i= 0; i < traceNb; i++) - { - const Fit* fit; - - visited[i]= false; - - fit= &fitArray[traceNum][i]; - g_debug("fitArray[traceNum= %u][i= %u]->n = %u", traceNum, i, fit->n); - if (fit->n > 0) - { - distances[i]= fit->e; - previousVertex[i]= traceNum; - } - else - { - distances[i]= INFINITY; - previousVertex[i]= UINT_MAX; - } - } - visited[traceNum]= true; - - for (j= 0; j < traceNb; j++) - { - g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]); - } - - for (i= 0; i < traceNb - 2; i++) - { - unsigned int v; - double dvMin; - - dvMin= INFINITY; - for (j= 0; j < traceNb; j++) - { - if (visited[j] == false && distances[j] < dvMin) - { - v= j; - dvMin= distances[j]; - } - } - - g_debug("v= %u dvMin= %g", v, dvMin); - - if (dvMin != INFINITY) - { - visited[v]= true; - - for (j= 0; j < traceNb; j++) - { - const Fit* fit; - - fit= &fitArray[v][j]; - if (visited[j] == false && fit->n > 0 && distances[v] + fit->e - < distances[j]) - { - distances[j]= distances[v] + fit->e; - previousVertex[j]= v; - } - } - } - else - { - break; - } - - for (j= 0; j < traceNb; j++) - { - g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]); - } - } - - free(visited); -} - - -/* - * Cummulate the distances between a reference node and the other nodes - * reachable from it in a graph. - * - * Args: - * distances: array of shortest path distances, with UINT_MAX for - * unreachable nodes - * traceNb: number of nodes = number of traces - */ -static double sumDistances(const double* const distances, const unsigned int traceNb) -{ - unsigned int i; - double result; - - result= 0; - for (i= 0; i < traceNb; i++) - { - if (distances[i] != INFINITY) - { - result+= distances[i]; - } - } - - return result; -} - - -/* - * Cummulate the time correction factors between two nodes accross a graph - * - * With traceNum i, reference node r: - * tr= (1 + Xri) * ti + D0ri - * = drift * ti + offset - * - * Args: - * fitArray: array with the regression parameters - * previousVertex: previous vertex from a node i on the way to the source, - * UINT_MAX if i is not on the way or is the source, - * preallocated to the number of nodes - * traceNum: end node, the reference depends on previousVertex - * drift: drift factor - * offset: offset factor - */ -static void reduceFactors(Fit* const* const fitArray, const unsigned int* const - previousVertex, const unsigned int traceNum, double* const drift, double* - const offset, double* const stDev) -{ - if (previousVertex[traceNum] == UINT_MAX) - { - *drift= 1.; - *offset= 0.; - *stDev= 0.; - } - else - { - const Fit* fit; - double cummDrift, cummOffset, cummStDev; - unsigned int pv; - - pv= previousVertex[traceNum]; - - fit= &fitArray[pv][traceNum]; - reduceFactors(fitArray, previousVertex, pv, &cummDrift, &cummOffset, - &cummStDev); - - *drift= cummDrift * (1 + fit->x); - *offset= cummDrift * fit->d0 + cummOffset; - *stDev= fit->x * cummStDev + fit->e; - } -} - - -/* - * A GFunc for g_queue_foreach() - * - * Args: - * data Graph*, graph to destroy - * user_data NULL - */ -static void gfGraphDestroy(gpointer data, gpointer user_data) -{ - Graph* graph; - - graph= (Graph*) data; - - free(graph->previousVertex); - free(graph); -} - - -/* - * A GCompareFunc for g_queue_find_custom() - * - * Args: - * a: Graph* graph - * b: unsigned int* traceNum - * - * Returns: - * 0 if graph contains traceNum - */ -static gint gcfGraphTraceCompare(gconstpointer a, gconstpointer b) -{ - Graph* graph; - unsigned int traceNum; - - graph= (Graph*) a; - traceNum= *(unsigned int *) b; - - if (graph->previousVertex[traceNum] != UINT_MAX) - { - return 0; - } - else if (graph->reference == traceNum) - { - return 0; - } - else - { - return 1; - } -} - - /* * Write the analysis-specific graph lines in the gnuplot script. *