projects / lttv.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Do not use __attribute__((constructor))
[lttv.git] / lttv / lttv / sync / event_analysis_linreg.c
1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009 Benjamin Poirier <benjamin.poirier@polymtl.ca>
3 *
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;
7 *
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.
12 *
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,
16 * MA 02111-1307, USA.
17 */
18
19 // for INFINITY in math.h
20 #define _ISOC99_SOURCE
21
22 #ifdef HAVE_CONFIG_H
23 #include <config.h>
24 #endif
25
26 #include <math.h>
27 #include <stdio.h>
28 #include <stdlib.h>
29
30 #include "sync_chain.h"
31
32 #include "event_analysis_linreg.h"
33
34
35 // Functions common to all analysis modules
36 static void initAnalysisLinReg(SyncState* const syncState);
37 static void destroyAnalysisLinReg(SyncState* const syncState);
38
39 static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const exchange);
40 static GArray* finalizeAnalysisLinReg(SyncState* const syncState);
41 static void printAnalysisStatsLinReg(SyncState* const syncState);
42 static void writeAnalysisGraphsPlotsLinReg(SyncState* const syncState, const
43 unsigned int i, const unsigned int j);
44
45 // Functions specific to this module
46 static void finalizeLSA(SyncState* const syncState);
47 static void doGraphProcessing(SyncState* const syncState);
48 static GArray* calculateFactors(SyncState* const syncState);
49 static void shortestPath(Fit* const* const fitArray, const unsigned int
50 traceNum, const unsigned int traceNb, double* const distances,
51 unsigned int* const previousVertex);
52 static double sumDistances(const double* const distances, const unsigned int
53 traceNb);
54 static void reduceFactors(Fit* const* const fitArray, const unsigned int* const
55 previousVertex, const unsigned int traceNum, double* const drift,
56 double* const offset, double* const stDev);
57
58 // Graph-related Glib functions
59 static void gfGraphDestroy(gpointer data, gpointer user_data);
60 static gint gcfGraphTraceCompare(gconstpointer a, gconstpointer b);
61
62
63 static AnalysisModule analysisModuleLinReg= {
64 .name= "linreg",
65 .initAnalysis= &initAnalysisLinReg,
66 .destroyAnalysis= &destroyAnalysisLinReg,
67 .analyzeExchange= &analyzeExchangeLinReg,
68 .finalizeAnalysis= &finalizeAnalysisLinReg,
69 .printAnalysisStats= &printAnalysisStatsLinReg,
70 .graphFunctions= {
71 .writeTraceTraceForePlots= &writeAnalysisGraphsPlotsLinReg,
72 }
73 };
74
75
76 /*
77 * Analysis module registering function
78 */
79 void registerAnalysisLinReg()
80 {
81 g_queue_push_tail(&analysisModules, &analysisModuleLinReg);
82 }
83
84
85 /*
86 * Analysis init function
87 *
88 * This function is called at the beginning of a synchronization run for a set
89 * of traces.
90 *
91 * Allocate some of the analysis specific data structures
92 *
93 * Args:
94 * syncState container for synchronization data.
95 * This function allocates these analysisData members:
96 * fitArray
97 * stDev
98 */
99 static void initAnalysisLinReg(SyncState* const syncState)
100 {
101 unsigned int i;
102 AnalysisDataLinReg* analysisData;
103
104 analysisData= malloc(sizeof(AnalysisDataLinReg));
105 syncState->analysisData= analysisData;
106
107 analysisData->fitArray= malloc(syncState->traceNb * sizeof(Fit*));
108 for (i= 0; i < syncState->traceNb; i++)
109 {
110 analysisData->fitArray[i]= calloc(syncState->traceNb, sizeof(Fit));
111 }
112
113 if (syncState->stats)
114 {
115 analysisData->stDev= malloc(sizeof(double) * syncState->traceNb);
116 }
117 }
118
119
120 /*
121 * Analysis destroy function
122 *
123 * Free the analysis specific data structures
124 *
125 * Args:
126 * syncState container for synchronization data.
127 * This function deallocates these analysisData members:
128 * fitArray
129 * graphList
130 * stDev
131 */
132 static void destroyAnalysisLinReg(SyncState* const syncState)
133 {
134 unsigned int i;
135 AnalysisDataLinReg* analysisData;
136
137 analysisData= (AnalysisDataLinReg*) syncState->analysisData;
138
139 if (analysisData == NULL)
140 {
141 return;
142 }
143
144 for (i= 0; i < syncState->traceNb; i++)
145 {
146 free(analysisData->fitArray[i]);
147 }
148 free(analysisData->fitArray);
149
150 g_queue_foreach(analysisData->graphList, &gfGraphDestroy, NULL);
151 g_queue_free(analysisData->graphList);
152
153 if (syncState->stats)
154 {
155 free(analysisData->stDev);
156 }
157
158 free(syncState->analysisData);
159 syncState->analysisData= NULL;
160 }
161
162
163 /*
164 * Perform analysis on a series of event pairs.
165 *
166 * Args:
167 * syncState container for synchronization data
168 * exchange structure containing the many events
169 */
170 static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const exchange)
171 {
172 unsigned int ni, nj;
173 double dji, eji;
174 double timoy;
175 Fit* fit;
176 Message* ackedMessage;
177 AnalysisDataLinReg* analysisData;
178
179 g_debug("Synchronization calculation, "
180 "%d acked packets - using last one,",
181 g_queue_get_length(exchange->acks));
182
183 analysisData= (AnalysisDataLinReg*) syncState->analysisData;
184 ackedMessage= g_queue_peek_tail(exchange->acks);
185
186 // Calculate the intermediate values for the
187 // least-squares analysis
188 dji= ((double) ackedMessage->inE->cpuTime - (double) ackedMessage->outE->cpuTime
189 + (double) exchange->message->outE->cpuTime - (double)
190 exchange->message->inE->cpuTime) / 2;
191 eji= fabs((double) ackedMessage->inE->cpuTime - (double)
192 ackedMessage->outE->cpuTime - (double) exchange->message->outE->cpuTime +
193 (double) exchange->message->inE->cpuTime) / 2;
194 timoy= ((double) ackedMessage->outE->cpuTime + (double)
195 exchange->message->inE->cpuTime) / 2;
196 ni= ackedMessage->outE->traceNum;
197 nj= ackedMessage->inE->traceNum;
198 fit= &analysisData->fitArray[nj][ni];
199
200 fit->n++;
201 fit->st+= timoy;
202 fit->st2+= pow(timoy, 2);
203 fit->sd+= dji;
204 fit->sd2+= pow(dji, 2);
205 fit->std+= timoy * dji;
206
207 g_debug("intermediate values: dji= %f ti moy= %f "
208 "ni= %u nj= %u fit: n= %u st= %f st2= %f sd= %f "
209 "sd2= %f std= %f, ", dji, timoy, ni, nj, fit->n,
210 fit->st, fit->st2, fit->sd, fit->sd2, fit->std);
211 }
212
213
214 /*
215 * Finalize the factor calculations
216 *
217 * The least squares analysis is finalized and finds the factors directly
218 * between each pair of traces that had events together. The traces are
219 * aranged in a graph, a reference trace is chosen and the factors between
220 * this reference and every other trace is calculated. Sometimes it is
221 * necessary to use many graphs when there are "islands" of independent
222 * traces.
223 *
224 * Args:
225 * syncState container for synchronization data.
226 *
227 * Returns:
228 * Factors[traceNb] synchronization factors for each trace
229 */
230 static GArray* finalizeAnalysisLinReg(SyncState* const syncState)
231 {
232 GArray* factors;
233
234 // Finalize the processing
235 finalizeLSA(syncState);
236
237 // Find a reference node and structure nodes in a graph
238 doGraphProcessing(syncState);
239
240 /* Calculate the resulting offset and drift between each trace and its
241 * reference
242 */
243 factors= calculateFactors(syncState);
244
245 return factors;
246 }
247
248
249 /*
250 * Print statistics related to analysis. Must be called after
251 * finalizeAnalysis.
252 *
253 * Args:
254 * syncState container for synchronization data.
255 */
256 static void printAnalysisStatsLinReg(SyncState* const syncState)
257 {
258 unsigned int i, j;
259 AnalysisDataLinReg* analysisData;
260
261 if (!syncState->stats)
262 {
263 return;
264 }
265
266 analysisData= (AnalysisDataLinReg*) syncState->analysisData;
267
268 printf("Linear regression analysis stats:\n");
269
270 printf("\tIndividual synchronization factors:\n");
271
272 for (j= 0; j < syncState->traceNb; j++)
273 {
274 for (i= 0; i < j; i++)
275 {
276 Fit* fit;
277
278 fit= &analysisData->fitArray[j][i];
279 printf("\t\t%3d - %-3d: ", i, j);
280 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit->d0, fit->x <
281 0. ? '-' : '+', fabs(fit->x), fit->e);
282
283 fit= &analysisData->fitArray[i][j];
284 printf("\t\t%3d - %-3d: ", j, i);
285 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit->d0, fit->x <
286 0. ? '-' : '+', fabs(fit->x), fit->e);
287 }
288 }
289
290 printf("\tTree:\n");
291 for (i= 0; i < syncState->traceNb; i++)
292 {
293 GList* result;
294
295 result= g_queue_find_custom(analysisData->graphList, &i,
296 &gcfGraphTraceCompare);
297 if (result != NULL)
298 {
299 Graph* graph;
300
301 graph= (Graph*) result->data;
302
303 printf("\t\ttrace %u reference %u previous vertex ", i,
304 graph->reference);
305
306 if (i == graph->reference)
307 {
308 printf("- ");
309 }
310 else
311 {
312 printf("%u ", graph->previousVertex[i]);
313 }
314
315 printf("stdev= %g\n", analysisData->stDev[i]);
316 }
317 else
318 {
319 g_error("Trace %d not part of a graph\n", i);
320 }
321 }
322 }
323
324
325 /*
326 * Finalize the least-squares analysis. The intermediate values in the fit
327 * array are used to calculate the drift and the offset between each pair of
328 * nodes based on their exchanges.
329 *
330 * Args:
331 * syncState: container for synchronization data.
332 */
333 static void finalizeLSA(SyncState* const syncState)
334 {
335 unsigned int i, j;
336 AnalysisDataLinReg* analysisData;
337
338 analysisData= (AnalysisDataLinReg*) syncState->analysisData;
339
340 for (i= 0; i < syncState->traceNb; i++)
341 {
342 for (j= 0; j < syncState->traceNb; j++)
343 {
344 if (i != j)
345 {
346 Fit* fit;
347 double delta;
348
349 fit= &analysisData->fitArray[i][j];
350
351 delta= fit->n * fit->st2 - pow(fit->st, 2);
352 fit->x= (fit->n * fit->std - fit->st * fit->sd) / delta;
353 fit->d0= (fit->st2 * fit->sd - fit->st * fit->std) / delta;
354 fit->e= sqrt((fit->sd2 - (fit->n * pow(fit->std, 2) +
355 pow(fit->sd, 2) * fit->st2 - 2 * fit->st * fit->sd
356 * fit->std) / delta) / (fit->n - 2));
357
358 g_debug("[i= %u j= %u]", i, j);
359 g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g",
360 fit->n, fit->st, fit->st2, fit->sd, fit->sd2, fit->std);
361 g_debug("xij= %g d0ij= %g e= %g", fit->x, fit->d0, fit->e);
362 g_debug("(xji= %g d0ji= %g)", -fit->x / (1 + fit->x),
363 -fit->d0 / (1 + fit->x));
364 }
365 }
366 }
367 }
368
369
370 /*
371 * Structure nodes in graphs of nodes that had exchanges. Each graph has a
372 * reference node, the one that can reach the others with the smallest
373 * cummulative error.
374 *
375 * Args:
376 * syncState: container for synchronization data.
377 * This function allocates these analysisData members:
378 * graphList
379 */
380 static void doGraphProcessing(SyncState* const syncState)
381 {
382 unsigned int i, j;
383 double* distances;
384 unsigned int* previousVertex;
385 AnalysisDataLinReg* analysisData;
386
387 analysisData= (AnalysisDataLinReg*) syncState->analysisData;
388
389 distances= malloc(syncState->traceNb * sizeof(double));
390 previousVertex= malloc(syncState->traceNb * sizeof(unsigned int));
391 analysisData->graphList= g_queue_new();
392
393 for (i= 0; i < syncState->traceNb; i++)
394 {
395 double errorSum;
396 GList* result;
397
398 // Perform shortest path search
399 g_debug("shortest path trace %d, distances: ", i);
400 shortestPath(analysisData->fitArray, i, syncState->traceNb, distances,
401 previousVertex);
402
403 for (j= 0; j < syncState->traceNb; j++)
404 {
405 g_debug("%g, ", distances[j]);
406 }
407 g_debug("previousVertex: ");
408 for (j= 0; j < syncState->traceNb; j++)
409 {
410 g_debug("%u, ", previousVertex[j]);
411 }
412
413 // Group in graphs nodes that have exchanges
414 errorSum= sumDistances(distances, syncState->traceNb);
415 result= g_queue_find_custom(analysisData->graphList, &i,
416 &gcfGraphTraceCompare);
417 if (result != NULL)
418 {
419 Graph* graph;
420
421 g_debug("found graph");
422 graph= (Graph*) result->data;
423 if (errorSum < graph->errorSum)
424 {
425 g_debug("adding to graph");
426 graph->errorSum= errorSum;
427 free(graph->previousVertex);
428 graph->previousVertex= previousVertex;
429 graph->reference= i;
430 previousVertex= malloc(syncState->traceNb * sizeof(unsigned
431 int));
432 }
433 }
434 else
435 {
436 Graph* newGraph;
437
438 g_debug("creating new graph");
439 newGraph= malloc(sizeof(Graph));
440 newGraph->errorSum= errorSum;
441 newGraph->previousVertex= previousVertex;
442 newGraph->reference= i;
443 previousVertex= malloc(syncState->traceNb * sizeof(unsigned int));
444
445 g_queue_push_tail(analysisData->graphList, newGraph);
446 }
447 }
448
449 free(previousVertex);
450 free(distances);
451 }
452
453
454 /*
455 * Calculate the resulting offset and drift between each trace and its
456 * reference.
457 *
458 * Args:
459 * syncState: container for synchronization data.
460 *
461 * Returns:
462 * Factors[traceNb] synchronization factors for each trace
463 */
464 static GArray* calculateFactors(SyncState* const syncState)
465 {
466 unsigned int i;
467 AnalysisDataLinReg* analysisData;
468 GArray* factors;
469
470 analysisData= (AnalysisDataLinReg*) syncState->analysisData;
471 factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors),
472 syncState->traceNb);
473 g_array_set_size(factors, syncState->traceNb);
474
475 // Calculate the resulting offset and drift between each trace and its
476 // reference
477 for (i= 0; i < syncState->traceNb; i++)
478 {
479 GList* result;
480
481 result= g_queue_find_custom(analysisData->graphList, &i,
482 &gcfGraphTraceCompare);
483 if (result != NULL)
484 {
485 Graph* graph;
486 double stDev;
487 Factors* traceFactors;
488
489 graph= (Graph*) result->data;
490 traceFactors= &g_array_index(factors, Factors, i);
491
492 reduceFactors(analysisData->fitArray, graph->previousVertex, i,
493 &traceFactors->drift, &traceFactors->offset, &stDev);
494
495 if (syncState->stats)
496 {
497 analysisData->stDev[i]= stDev;
498 }
499 }
500 else
501 {
502 g_error("Trace %d not part of a graph\n", i);
503 }
504 }
505
506 return factors;
507 }
508
509
510 /*
511 * Single-source shortest path search to find the path with the lowest error to
512 * convert one node's time to another.
513 * Uses Dijkstra's algorithm
514 *
515 * Args:
516 * fitArray: array with the regression parameters
517 * traceNum: reference node
518 * traceNb: number of traces = number of nodes
519 * distances: array of computed distance from source node to node i,
520 * INFINITY if i is unreachable, preallocated to the number of
521 * nodes
522 * previousVertex: previous vertex from a node i on the way to the source,
523 * UINT_MAX if i is not on the way or is the source,
524 * preallocated to the number of nodes
525 */
526 static void shortestPath(Fit* const* const fitArray, const unsigned int
527 traceNum, const unsigned int traceNb, double* const distances, unsigned
528 int* const previousVertex)
529 {
530 bool* visited;
531 unsigned int i, j;
532
533 visited= malloc(traceNb * sizeof(bool));
534
535 for (i= 0; i < traceNb; i++)
536 {
537 const Fit* fit;
538
539 visited[i]= false;
540
541 fit= &fitArray[traceNum][i];
542 g_debug("fitArray[traceNum= %u][i= %u]->n = %u", traceNum, i, fit->n);
543 if (fit->n > 0)
544 {
545 distances[i]= fit->e;
546 previousVertex[i]= traceNum;
547 }
548 else
549 {
550 distances[i]= INFINITY;
551 previousVertex[i]= UINT_MAX;
552 }
553 }
554 visited[traceNum]= true;
555
556 for (j= 0; j < traceNb; j++)
557 {
558 g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]);
559 }
560
561 for (i= 0; i < traceNb - 2; i++)
562 {
563 unsigned int v;
564 double dvMin;
565
566 dvMin= INFINITY;
567 for (j= 0; j < traceNb; j++)
568 {
569 if (visited[j] == false && distances[j] < dvMin)
570 {
571 v= j;
572 dvMin= distances[j];
573 }
574 }
575
576 g_debug("v= %u dvMin= %g", v, dvMin);
577
578 if (dvMin != INFINITY)
579 {
580 visited[v]= true;
581
582 for (j= 0; j < traceNb; j++)
583 {
584 const Fit* fit;
585
586 fit= &fitArray[v][j];
587 if (visited[j] == false && fit->n > 0 && distances[v] + fit->e
588 < distances[j])
589 {
590 distances[j]= distances[v] + fit->e;
591 previousVertex[j]= v;
592 }
593 }
594 }
595 else
596 {
597 break;
598 }
599
600 for (j= 0; j < traceNb; j++)
601 {
602 g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]);
603 }
604 }
605
606 free(visited);
607 }
608
609
610 /*
611 * Cummulate the distances between a reference node and the other nodes
612 * reachable from it in a graph.
613 *
614 * Args:
615 * distances: array of shortest path distances, with UINT_MAX for
616 * unreachable nodes
617 * traceNb: number of nodes = number of traces
618 */
619 static double sumDistances(const double* const distances, const unsigned int traceNb)
620 {
621 unsigned int i;
622 double result;
623
624 result= 0;
625 for (i= 0; i < traceNb; i++)
626 {
627 if (distances[i] != INFINITY)
628 {
629 result+= distances[i];
630 }
631 }
632
633 return result;
634 }
635
636
637 /*
638 * Cummulate the time correction factors between two nodes accross a graph
639 *
640 * With traceNum i, reference node r:
641 * tr= (1 + Xri) * ti + D0ri
642 * = drift * ti + offset
643 *
644 * Args:
645 * fitArray: array with the regression parameters
646 * previousVertex: previous vertex from a node i on the way to the source,
647 * UINT_MAX if i is not on the way or is the source,
648 * preallocated to the number of nodes
649 * traceNum: end node, the reference depends on previousVertex
650 * drift: drift factor
651 * offset: offset factor
652 */
653 static void reduceFactors(Fit* const* const fitArray, const unsigned int* const
654 previousVertex, const unsigned int traceNum, double* const drift, double*
655 const offset, double* const stDev)
656 {
657 if (previousVertex[traceNum] == UINT_MAX)
658 {
659 *drift= 1.;
660 *offset= 0.;
661 *stDev= 0.;
662 }
663 else
664 {
665 const Fit* fit;
666 double cummDrift, cummOffset, cummStDev;
667 unsigned int pv;
668
669 pv= previousVertex[traceNum];
670
671 fit= &fitArray[pv][traceNum];
672 reduceFactors(fitArray, previousVertex, pv, &cummDrift, &cummOffset,
673 &cummStDev);
674
675 *drift= cummDrift * (1 + fit->x);
676 *offset= cummDrift * fit->d0 + cummOffset;
677 *stDev= fit->x * cummStDev + fit->e;
678 }
679 }
680
681
682 /*
683 * A GFunc for g_queue_foreach()
684 *
685 * Args:
686 * data Graph*, graph to destroy
687 * user_data NULL
688 */
689 static void gfGraphDestroy(gpointer data, gpointer user_data)
690 {
691 Graph* graph;
692
693 graph= (Graph*) data;
694
695 free(graph->previousVertex);
696 free(graph);
697 }
698
699
700 /*
701 * A GCompareFunc for g_queue_find_custom()
702 *
703 * Args:
704 * a: Graph* graph
705 * b: unsigned int* traceNum
706 *
707 * Returns:
708 * 0 if graph contains traceNum
709 */
710 static gint gcfGraphTraceCompare(gconstpointer a, gconstpointer b)
711 {
712 Graph* graph;
713 unsigned int traceNum;
714
715 graph= (Graph*) a;
716 traceNum= *(unsigned int *) b;
717
718 if (graph->previousVertex[traceNum] != UINT_MAX)
719 {
720 return 0;
721 }
722 else if (graph->reference == traceNum)
723 {
724 return 0;
725 }
726 else
727 {
728 return 1;
729 }
730 }
731
732
733 /*
734 * Write the analysis-specific graph lines in the gnuplot script.
735 *
736 * Args:
737 * syncState: container for synchronization data
738 * i: first trace number, on the x axis
739 * j: second trace number, garanteed to be larger than i
740 */
741 void writeAnalysisGraphsPlotsLinReg(SyncState* const syncState, const unsigned
742 int i, const unsigned int j)
743 {
744 AnalysisDataLinReg* analysisData;
745 Fit* fit;
746
747 analysisData= (AnalysisDataLinReg*) syncState->analysisData;
748 fit= &analysisData->fitArray[j][i];
749
750 fprintf(syncState->graphsStream,
751 "\t%7g + %7g * x "
752 "title \"Linreg conversion\" with lines "
753 "linecolor rgb \"gray60\" linetype 1, \\\n",
754 fit->d0, 1. + fit->x);
755 }
LTTng 2.x Viewer (LTTV)
This page took 0.047207 seconds and 4 git commands to generate.