/* This file is part of the Linux Trace Toolkit viewer
- * Copyright (C) 2009 Benjamin Poirier <benjamin.poirier@polymtl.ca>
+ * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
*
- * 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 <http://www.gnu.org/licenses/>.
*/
// for INFINITY in math.h
#include "event_analysis_linreg.h"
-#ifndef g_info
-#define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format)
-#endif
-
-
// Functions common to all analysis modules
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= {
.name= "linreg",
.initAnalysis= &initAnalysisLinReg,
.destroyAnalysis= &destroyAnalysisLinReg,
- .analyzeMessage= NULL,
.analyzeExchange= &analyzeExchangeLinReg,
- .analyzeBroadcast= NULL,
.finalizeAnalysis= &finalizeAnalysisLinReg,
.printAnalysisStats= &printAnalysisStatsLinReg,
- .writeAnalysisGraphsPlots= &writeAnalysisGraphsPlotsLinReg,
- .writeAnalysisGraphsOptions= NULL,
+ .graphFunctions= {
+ .writeTraceTraceForePlots= &writeAnalysisGraphsPlotsLinReg,
+ }
};
/*
* Analysis module registering function
*/
-static void registerAnalysisLinReg()
+void registerAnalysisLinReg()
{
g_queue_push_tail(&analysisModules, &analysisModuleLinReg);
}
}
free(analysisData->fitArray);
- g_queue_foreach(analysisData->graphList, &gfGraphDestroy, NULL);
- g_queue_free(analysisData->graphList);
-
if (syncState->stats)
{
free(analysisData->stDev);
static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const exchange)
{
unsigned int ni, nj;
- double dji, eji;
+ double dji;
double timoy;
Fit* fit;
Message* ackedMessage;
AnalysisDataLinReg* analysisData;
- g_debug("Synchronization calculation, ");
- g_debug("%d acked packets - using last one, ",
+ g_debug("Synchronization calculation, "
+ "%d acked packets - using last one,",
g_queue_get_length(exchange->acks));
analysisData= (AnalysisDataLinReg*) syncState->analysisData;
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;
* 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;
- return factors;
+ 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 result;
}
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);
- }
- }
}
pow(fit->sd, 2) * fit->st2 - 2 * fit->st * fit->sd
* fit->std) / delta) / (fit->n - 2));
- g_debug("[i= %u j= %u]\n", i, j);
- g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g\n",
+ g_debug("[i= %u j= %u]", i, j);
+ g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g",
fit->n, fit->st, fit->st2, fit->sd, fit->sd2, fit->std);
- g_debug("xij= %g d0ij= %g e= %g\n", fit->x, fit->d0, fit->e);
- g_debug("(xji= %g d0ji= %g)\n", -fit->x / (1 + fit->x),
+ g_debug("xij= %g d0ij= %g e= %g", fit->x, fit->d0, fit->e);
+ g_debug("(xji= %g d0ji= %g)", -fit->x / (1 + fit->x),
-fit->d0 / (1 + fit->x));
}
}
}
-/*
- * 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\ndistances: ", i);
- shortestPath(analysisData->fitArray, i, syncState->traceNb, distances,
- previousVertex);
-
- for (j= 0; j < syncState->traceNb; j++)
- {
- g_debug("%g, ", distances[j]);
- }
- g_debug("\npreviousVertex: ");
- for (j= 0; j < syncState->traceNb; j++)
- {
- g_debug("%u, ", previousVertex[j]);
- }
- g_debug("\n");
-
- // 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\n");
- graph= (Graph*) result->data;
- if (errorSum < graph->errorSum)
- {
- g_debug("adding to graph\n");
- 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\n");
- 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\n", 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]);
- }
- g_debug("\n");
-
- 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\n", 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]);
- }
- g_debug("\n");
- }
-
- 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.
*