X-Git-Url: http://git.lttng.org/?a=blobdiff_plain;f=lttv%2Flttv%2Fsync%2Fevent_analysis_linreg.c;h=fbfc052260b33bebd04fb52edeae83712f1b7337;hb=e865422cc50d00cb57ec05ed07bba4cbe160904e;hp=07537780bcb8ae4ced81d91622c5bbad2920be3b;hpb=d5b038ec901e9753a8569f33516a49361c54254c;p=lttv.git diff --git a/lttv/lttv/sync/event_analysis_linreg.c b/lttv/lttv/sync/event_analysis_linreg.c index 07537780..fbfc0522 100644 --- a/lttv/lttv/sync/event_analysis_linreg.c +++ b/lttv/lttv/sync/event_analysis_linreg.c @@ -1,19 +1,18 @@ /* This file is part of the Linux Trace Toolkit viewer - * Copyright (C) 2009 Benjamin Poirier + * 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 General Public License Version 2 as - * published by the Free Software Foundation; + * 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 General Public License for more details. + * 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 General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, - * MA 02111-1307, USA. + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see . */ // for INFINITY in math.h @@ -37,29 +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 registerAnalysisLinReg() __attribute__((constructor (102))); - 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= { @@ -78,7 +61,7 @@ static AnalysisModule analysisModuleLinReg= { /* * Analysis module registering function */ -static void registerAnalysisLinReg() +void registerAnalysisLinReg() { g_queue_push_tail(&analysisModules, &analysisModuleLinReg); } @@ -149,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); @@ -172,7 +152,7 @@ static void destroyAnalysisLinReg(SyncState* const syncState) static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const exchange) { unsigned int ni, nj; - double dji, eji; + double dji; double timoy; Fit* fit; Message* ackedMessage; @@ -190,9 +170,6 @@ static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const ex dji= ((double) ackedMessage->inE->cpuTime - (double) ackedMessage->outE->cpuTime + (double) exchange->message->outE->cpuTime - (double) exchange->message->inE->cpuTime) / 2; - eji= fabs((double) ackedMessage->inE->cpuTime - (double) - ackedMessage->outE->cpuTime - (double) exchange->message->outE->cpuTime + - (double) exchange->message->inE->cpuTime) / 2; timoy= ((double) ackedMessage->outE->cpuTime + (double) exchange->message->inE->cpuTime) / 2; ni= ackedMessage->outE->traceNum; @@ -227,24 +204,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; } @@ -288,39 +279,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); - } - } } @@ -369,369 +327,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("adding to graph"); - 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. *