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