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= {
}
free(analysisData->fitArray);
- g_queue_foreach(analysisData->graphList, &gfGraphDestroy, NULL);
- g_queue_free(analysisData->graphList);
-
if (syncState->stats)
{
free(analysisData->stDev);
* 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;
}
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);
- }
- }
}
}
-/*
- * 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.
*
projects / lttv.git / blobdiff