projects / lttv.git / blob
? search:


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