1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009 Benjamin Poirier <benjamin.poirier@polymtl.ca>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License Version 2 as
6 * published by the Free Software Foundation;
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
19 // for INFINITY in math.h
20 #define _ISOC99_SOURCE
30 #include "sync_chain.h"
32 #include "event_analysis_linreg.h"
36 #define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format)
40 // Functions common to all analysis modules
41 static void initAnalysisLinReg(SyncState
* const syncState
);
42 static void destroyAnalysisLinReg(SyncState
* const syncState
);
44 static void analyzeExchangeLinReg(SyncState
* const syncState
, Exchange
* const exchange
);
45 static GArray
* finalizeAnalysisLinReg(SyncState
* const syncState
);
46 static void printAnalysisStatsLinReg(SyncState
* const syncState
);
47 static void writeAnalysisGraphsPlotsLinReg(FILE* stream
, SyncState
* const
48 syncState
, const unsigned int i
, const unsigned int j
);
50 // Functions specific to this module
51 static void registerAnalysisLinReg() __attribute__((constructor (102)));
53 static void finalizeLSA(SyncState
* const syncState
);
54 static void doGraphProcessing(SyncState
* const syncState
);
55 static GArray
* calculateFactors(SyncState
* const syncState
);
56 static void shortestPath(Fit
* const* const fitArray
, const unsigned int
57 traceNum
, const unsigned int traceNb
, double* const distances
,
58 unsigned int* const previousVertex
);
59 static double sumDistances(const double* const distances
, const unsigned int
61 static void reduceFactors(Fit
* const* const fitArray
, const unsigned int* const
62 previousVertex
, const unsigned int traceNum
, double* const drift
,
63 double* const offset
, double* const stDev
);
65 // Graph-related Glib functions
66 static void gfGraphDestroy(gpointer data
, gpointer user_data
);
67 static gint
gcfGraphTraceCompare(gconstpointer a
, gconstpointer b
);
70 static AnalysisModule analysisModuleLinReg
= {
72 .initAnalysis
= &initAnalysisLinReg
,
73 .destroyAnalysis
= &destroyAnalysisLinReg
,
74 .analyzeMessage
= NULL
,
75 .analyzeExchange
= &analyzeExchangeLinReg
,
76 .analyzeBroadcast
= NULL
,
77 .finalizeAnalysis
= &finalizeAnalysisLinReg
,
78 .printAnalysisStats
= &printAnalysisStatsLinReg
,
79 .writeAnalysisGraphsPlots
= &writeAnalysisGraphsPlotsLinReg
,
80 .writeAnalysisGraphsOptions
= NULL
,
85 * Analysis module registering function
87 static void registerAnalysisLinReg()
89 g_queue_push_tail(&analysisModules
, &analysisModuleLinReg
);
94 * Analysis init function
96 * This function is called at the beginning of a synchronization run for a set
99 * Allocate some of the analysis specific data structures
102 * syncState container for synchronization data.
103 * This function allocates these analysisData members:
107 static void initAnalysisLinReg(SyncState
* const syncState
)
110 AnalysisDataLinReg
* analysisData
;
112 analysisData
= malloc(sizeof(AnalysisDataLinReg
));
113 syncState
->analysisData
= analysisData
;
115 analysisData
->fitArray
= malloc(syncState
->traceNb
* sizeof(Fit
*));
116 for (i
= 0; i
< syncState
->traceNb
; i
++)
118 analysisData
->fitArray
[i
]= calloc(syncState
->traceNb
, sizeof(Fit
));
121 if (syncState
->stats
)
123 analysisData
->stDev
= malloc(sizeof(double) * syncState
->traceNb
);
129 * Analysis destroy function
131 * Free the analysis specific data structures
134 * syncState container for synchronization data.
135 * This function deallocates these analysisData members:
140 static void destroyAnalysisLinReg(SyncState
* const syncState
)
143 AnalysisDataLinReg
* analysisData
;
145 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
147 if (analysisData
== NULL
)
152 for (i
= 0; i
< syncState
->traceNb
; i
++)
154 free(analysisData
->fitArray
[i
]);
156 free(analysisData
->fitArray
);
158 g_queue_foreach(analysisData
->graphList
, &gfGraphDestroy
, NULL
);
159 g_queue_free(analysisData
->graphList
);
161 if (syncState
->stats
)
163 free(analysisData
->stDev
);
166 free(syncState
->analysisData
);
167 syncState
->analysisData
= NULL
;
172 * Perform analysis on a series of event pairs.
175 * syncState container for synchronization data
176 * exchange structure containing the many events
178 static void analyzeExchangeLinReg(SyncState
* const syncState
, Exchange
* const exchange
)
184 Message
* ackedMessage
;
185 AnalysisDataLinReg
* analysisData
;
187 g_debug("Synchronization calculation, ");
188 g_debug("%d acked packets - using last one, ",
189 g_queue_get_length(exchange
->acks
));
191 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
192 ackedMessage
= g_queue_peek_tail(exchange
->acks
);
194 // Calculate the intermediate values for the
195 // least-squares analysis
196 dji
= ((double) ackedMessage
->inE
->cpuTime
- (double) ackedMessage
->outE
->cpuTime
197 + (double) exchange
->message
->outE
->cpuTime
- (double)
198 exchange
->message
->inE
->cpuTime
) / 2;
199 eji
= fabs((double) ackedMessage
->inE
->cpuTime
- (double)
200 ackedMessage
->outE
->cpuTime
- (double) exchange
->message
->outE
->cpuTime
+
201 (double) exchange
->message
->inE
->cpuTime
) / 2;
202 timoy
= ((double) ackedMessage
->outE
->cpuTime
+ (double)
203 exchange
->message
->inE
->cpuTime
) / 2;
204 ni
= ackedMessage
->outE
->traceNum
;
205 nj
= ackedMessage
->inE
->traceNum
;
206 fit
= &analysisData
->fitArray
[nj
][ni
];
210 fit
->st2
+= pow(timoy
, 2);
212 fit
->sd2
+= pow(dji
, 2);
213 fit
->std
+= timoy
* dji
;
215 g_debug("intermediate values: dji= %f ti moy= %f "
216 "ni= %u nj= %u fit: n= %u st= %f st2= %f sd= %f "
217 "sd2= %f std= %f, ", dji
, timoy
, ni
, nj
, fit
->n
,
218 fit
->st
, fit
->st2
, fit
->sd
, fit
->sd2
, fit
->std
);
223 * Finalize the factor calculations
225 * The least squares analysis is finalized and finds the factors directly
226 * between each pair of traces that had events together. The traces are
227 * aranged in a graph, a reference trace is chosen and the factors between
228 * this reference and every other trace is calculated. Sometimes it is
229 * necessary to use many graphs when there are "islands" of independent
233 * syncState container for synchronization data.
236 * Factors[traceNb] synchronization factors for each trace
238 static GArray
* finalizeAnalysisLinReg(SyncState
* const syncState
)
242 // Finalize the processing
243 finalizeLSA(syncState
);
245 // Find a reference node and structure nodes in a graph
246 doGraphProcessing(syncState
);
248 /* Calculate the resulting offset and drift between each trace and its
251 factors
= calculateFactors(syncState
);
258 * Print statistics related to analysis. Must be called after
262 * syncState container for synchronization data.
264 static void printAnalysisStatsLinReg(SyncState
* const syncState
)
267 AnalysisDataLinReg
* analysisData
;
269 if (!syncState
->stats
)
274 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
276 printf("Linear regression analysis stats:\n");
278 printf("\tIndividual synchronization factors:\n");
280 for (j
= 0; j
< syncState
->traceNb
; j
++)
282 for (i
= 0; i
< j
; i
++)
286 fit
= &analysisData
->fitArray
[j
][i
];
287 printf("\t\t%3d - %-3d: ", i
, j
);
288 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit
->d0
, fit
->x
<
289 0. ? '-' : '+', fabs(fit
->x
), fit
->e
);
291 fit
= &analysisData
->fitArray
[i
][j
];
292 printf("\t\t%3d - %-3d: ", j
, i
);
293 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit
->d0
, fit
->x
<
294 0. ? '-' : '+', fabs(fit
->x
), fit
->e
);
299 for (i
= 0; i
< syncState
->traceNb
; i
++)
303 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
304 &gcfGraphTraceCompare
);
309 graph
= (Graph
*) result
->data
;
311 printf("\t\ttrace %u reference %u previous vertex ", i
,
314 if (i
== graph
->reference
)
320 printf("%u ", graph
->previousVertex
[i
]);
323 printf("stdev= %g\n", analysisData
->stDev
[i
]);
327 g_error("Trace %d not part of a graph\n", i
);
334 * Finalize the least-squares analysis. The intermediate values in the fit
335 * array are used to calculate the drift and the offset between each pair of
336 * nodes based on their exchanges.
339 * syncState: container for synchronization data.
341 static void finalizeLSA(SyncState
* const syncState
)
344 AnalysisDataLinReg
* analysisData
;
346 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
348 for (i
= 0; i
< syncState
->traceNb
; i
++)
350 for (j
= 0; j
< syncState
->traceNb
; j
++)
357 fit
= &analysisData
->fitArray
[i
][j
];
359 delta
= fit
->n
* fit
->st2
- pow(fit
->st
, 2);
360 fit
->x
= (fit
->n
* fit
->std
- fit
->st
* fit
->sd
) / delta
;
361 fit
->d0
= (fit
->st2
* fit
->sd
- fit
->st
* fit
->std
) / delta
;
362 fit
->e
= sqrt((fit
->sd2
- (fit
->n
* pow(fit
->std
, 2) +
363 pow(fit
->sd
, 2) * fit
->st2
- 2 * fit
->st
* fit
->sd
364 * fit
->std
) / delta
) / (fit
->n
- 2));
366 g_debug("[i= %u j= %u]\n", i
, j
);
367 g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g\n",
368 fit
->n
, fit
->st
, fit
->st2
, fit
->sd
, fit
->sd2
, fit
->std
);
369 g_debug("xij= %g d0ij= %g e= %g\n", fit
->x
, fit
->d0
, fit
->e
);
370 g_debug("(xji= %g d0ji= %g)\n", -fit
->x
/ (1 + fit
->x
),
371 -fit
->d0
/ (1 + fit
->x
));
379 * Structure nodes in graphs of nodes that had exchanges. Each graph has a
380 * reference node, the one that can reach the others with the smallest
384 * syncState: container for synchronization data.
385 * This function allocates these analysisData members:
388 static void doGraphProcessing(SyncState
* const syncState
)
392 unsigned int* previousVertex
;
393 AnalysisDataLinReg
* analysisData
;
395 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
397 distances
= malloc(syncState
->traceNb
* sizeof(double));
398 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned int));
399 analysisData
->graphList
= g_queue_new();
401 for (i
= 0; i
< syncState
->traceNb
; i
++)
406 // Perform shortest path search
407 g_debug("shortest path trace %d\ndistances: ", i
);
408 shortestPath(analysisData
->fitArray
, i
, syncState
->traceNb
, distances
,
411 for (j
= 0; j
< syncState
->traceNb
; j
++)
413 g_debug("%g, ", distances
[j
]);
415 g_debug("\npreviousVertex: ");
416 for (j
= 0; j
< syncState
->traceNb
; j
++)
418 g_debug("%u, ", previousVertex
[j
]);
422 // Group in graphs nodes that have exchanges
423 errorSum
= sumDistances(distances
, syncState
->traceNb
);
424 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
425 &gcfGraphTraceCompare
);
430 g_debug("found graph\n");
431 graph
= (Graph
*) result
->data
;
432 if (errorSum
< graph
->errorSum
)
434 g_debug("adding to graph\n");
435 graph
->errorSum
= errorSum
;
436 free(graph
->previousVertex
);
437 graph
->previousVertex
= previousVertex
;
439 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned
447 g_debug("creating new graph\n");
448 newGraph
= malloc(sizeof(Graph
));
449 newGraph
->errorSum
= errorSum
;
450 newGraph
->previousVertex
= previousVertex
;
451 newGraph
->reference
= i
;
452 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned int));
454 g_queue_push_tail(analysisData
->graphList
, newGraph
);
458 free(previousVertex
);
464 * Calculate the resulting offset and drift between each trace and its
468 * syncState: container for synchronization data.
471 * Factors[traceNb] synchronization factors for each trace
473 static GArray
* calculateFactors(SyncState
* const syncState
)
476 AnalysisDataLinReg
* analysisData
;
479 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
480 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
482 g_array_set_size(factors
, syncState
->traceNb
);
484 // Calculate the resulting offset and drift between each trace and its
486 for (i
= 0; i
< syncState
->traceNb
; i
++)
490 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
491 &gcfGraphTraceCompare
);
496 Factors
* traceFactors
;
498 graph
= (Graph
*) result
->data
;
499 traceFactors
= &g_array_index(factors
, Factors
, i
);
501 reduceFactors(analysisData
->fitArray
, graph
->previousVertex
, i
,
502 &traceFactors
->drift
, &traceFactors
->offset
, &stDev
);
504 if (syncState
->stats
)
506 analysisData
->stDev
[i
]= stDev
;
511 g_error("Trace %d not part of a graph\n", i
);
520 * Single-source shortest path search to find the path with the lowest error to
521 * convert one node's time to another.
522 * Uses Dijkstra's algorithm
525 * fitArray: array with the regression parameters
526 * traceNum: reference node
527 * traceNb: number of traces = number of nodes
528 * distances: array of computed distance from source node to node i,
529 * INFINITY if i is unreachable, preallocated to the number of
531 * previousVertex: previous vertex from a node i on the way to the source,
532 * UINT_MAX if i is not on the way or is the source,
533 * preallocated to the number of nodes
535 static void shortestPath(Fit
* const* const fitArray
, const unsigned int
536 traceNum
, const unsigned int traceNb
, double* const distances
, unsigned
537 int* const previousVertex
)
542 visited
= malloc(traceNb
* sizeof(bool));
544 for (i
= 0; i
< traceNb
; i
++)
550 fit
= &fitArray
[traceNum
][i
];
551 g_debug("fitArray[traceNum= %u][i= %u]->n = %u\n", traceNum
, i
, fit
->n
);
554 distances
[i
]= fit
->e
;
555 previousVertex
[i
]= traceNum
;
559 distances
[i
]= INFINITY
;
560 previousVertex
[i
]= UINT_MAX
;
563 visited
[traceNum
]= true;
565 for (j
= 0; j
< traceNb
; j
++)
567 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
571 for (i
= 0; i
< traceNb
- 2; i
++)
577 for (j
= 0; j
< traceNb
; j
++)
579 if (visited
[j
] == false && distances
[j
] < dvMin
)
586 g_debug("v= %u dvMin= %g\n", v
, dvMin
);
588 if (dvMin
!= INFINITY
)
592 for (j
= 0; j
< traceNb
; j
++)
596 fit
= &fitArray
[v
][j
];
597 if (visited
[j
] == false && fit
->n
> 0 && distances
[v
] + fit
->e
600 distances
[j
]= distances
[v
] + fit
->e
;
601 previousVertex
[j
]= v
;
610 for (j
= 0; j
< traceNb
; j
++)
612 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
622 * Cummulate the distances between a reference node and the other nodes
623 * reachable from it in a graph.
626 * distances: array of shortest path distances, with UINT_MAX for
628 * traceNb: number of nodes = number of traces
630 static double sumDistances(const double* const distances
, const unsigned int traceNb
)
636 for (i
= 0; i
< traceNb
; i
++)
638 if (distances
[i
] != INFINITY
)
640 result
+= distances
[i
];
649 * Cummulate the time correction factors between two nodes accross a graph
651 * With traceNum i, reference node r:
652 * tr= (1 + Xri) * ti + D0ri
653 * = drift * ti + offset
656 * fitArray: array with the regression parameters
657 * previousVertex: previous vertex from a node i on the way to the source,
658 * UINT_MAX if i is not on the way or is the source,
659 * preallocated to the number of nodes
660 * traceNum: end node, the reference depends on previousVertex
661 * drift: drift factor
662 * offset: offset factor
664 static void reduceFactors(Fit
* const* const fitArray
, const unsigned int* const
665 previousVertex
, const unsigned int traceNum
, double* const drift
, double*
666 const offset
, double* const stDev
)
668 if (previousVertex
[traceNum
] == UINT_MAX
)
677 double cummDrift
, cummOffset
, cummStDev
;
680 pv
= previousVertex
[traceNum
];
682 fit
= &fitArray
[pv
][traceNum
];
683 reduceFactors(fitArray
, previousVertex
, pv
, &cummDrift
, &cummOffset
,
686 *drift
= cummDrift
* (1 + fit
->x
);
687 *offset
= cummDrift
* fit
->d0
+ cummOffset
;
688 *stDev
= fit
->x
* cummStDev
+ fit
->e
;
694 * A GFunc for g_queue_foreach()
697 * data Graph*, graph to destroy
700 static void gfGraphDestroy(gpointer data
, gpointer user_data
)
704 graph
= (Graph
*) data
;
706 free(graph
->previousVertex
);
712 * A GCompareFunc for g_queue_find_custom()
716 * b: unsigned int* traceNum
719 * 0 if graph contains traceNum
721 static gint
gcfGraphTraceCompare(gconstpointer a
, gconstpointer b
)
724 unsigned int traceNum
;
727 traceNum
= *(unsigned int *) b
;
729 if (graph
->previousVertex
[traceNum
] != UINT_MAX
)
733 else if (graph
->reference
== traceNum
)
745 * Write the analysis-specific graph lines in the gnuplot script.
748 * stream: stream where to write the data
749 * syncState: container for synchronization data
750 * i: first trace number, on the x axis
751 * j: second trace number, garanteed to be larger than i
753 void writeAnalysisGraphsPlotsLinReg(FILE* stream
, SyncState
* const syncState
,
754 const unsigned int i
, const unsigned int j
)
756 AnalysisDataLinReg
* analysisData
;
759 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
760 fit
= &analysisData
->fitArray
[j
][i
];
764 "title \"Linreg conversion\" with lines "
765 "linecolor rgb \"gray60\" linetype 1, \\\n",
766 fit
->d0
, 1. + fit
->x
);