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(SyncState
* const syncState
, const
48 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 .analyzeExchange
= &analyzeExchangeLinReg
,
75 .finalizeAnalysis
= &finalizeAnalysisLinReg
,
76 .printAnalysisStats
= &printAnalysisStatsLinReg
,
78 .writeTraceTracePlots
= &writeAnalysisGraphsPlotsLinReg
,
84 * Analysis module registering function
86 static void registerAnalysisLinReg()
88 g_queue_push_tail(&analysisModules
, &analysisModuleLinReg
);
93 * Analysis init function
95 * This function is called at the beginning of a synchronization run for a set
98 * Allocate some of the analysis specific data structures
101 * syncState container for synchronization data.
102 * This function allocates these analysisData members:
106 static void initAnalysisLinReg(SyncState
* const syncState
)
109 AnalysisDataLinReg
* analysisData
;
111 analysisData
= malloc(sizeof(AnalysisDataLinReg
));
112 syncState
->analysisData
= analysisData
;
114 analysisData
->fitArray
= malloc(syncState
->traceNb
* sizeof(Fit
*));
115 for (i
= 0; i
< syncState
->traceNb
; i
++)
117 analysisData
->fitArray
[i
]= calloc(syncState
->traceNb
, sizeof(Fit
));
120 if (syncState
->stats
)
122 analysisData
->stDev
= malloc(sizeof(double) * syncState
->traceNb
);
128 * Analysis destroy function
130 * Free the analysis specific data structures
133 * syncState container for synchronization data.
134 * This function deallocates these analysisData members:
139 static void destroyAnalysisLinReg(SyncState
* const syncState
)
142 AnalysisDataLinReg
* analysisData
;
144 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
146 if (analysisData
== NULL
)
151 for (i
= 0; i
< syncState
->traceNb
; i
++)
153 free(analysisData
->fitArray
[i
]);
155 free(analysisData
->fitArray
);
157 g_queue_foreach(analysisData
->graphList
, &gfGraphDestroy
, NULL
);
158 g_queue_free(analysisData
->graphList
);
160 if (syncState
->stats
)
162 free(analysisData
->stDev
);
165 free(syncState
->analysisData
);
166 syncState
->analysisData
= NULL
;
171 * Perform analysis on a series of event pairs.
174 * syncState container for synchronization data
175 * exchange structure containing the many events
177 static void analyzeExchangeLinReg(SyncState
* const syncState
, Exchange
* const exchange
)
183 Message
* ackedMessage
;
184 AnalysisDataLinReg
* analysisData
;
186 g_debug("Synchronization calculation, ");
187 g_debug("%d acked packets - using last one, ",
188 g_queue_get_length(exchange
->acks
));
190 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
191 ackedMessage
= g_queue_peek_tail(exchange
->acks
);
193 // Calculate the intermediate values for the
194 // least-squares analysis
195 dji
= ((double) ackedMessage
->inE
->cpuTime
- (double) ackedMessage
->outE
->cpuTime
196 + (double) exchange
->message
->outE
->cpuTime
- (double)
197 exchange
->message
->inE
->cpuTime
) / 2;
198 eji
= fabs((double) ackedMessage
->inE
->cpuTime
- (double)
199 ackedMessage
->outE
->cpuTime
- (double) exchange
->message
->outE
->cpuTime
+
200 (double) exchange
->message
->inE
->cpuTime
) / 2;
201 timoy
= ((double) ackedMessage
->outE
->cpuTime
+ (double)
202 exchange
->message
->inE
->cpuTime
) / 2;
203 ni
= ackedMessage
->outE
->traceNum
;
204 nj
= ackedMessage
->inE
->traceNum
;
205 fit
= &analysisData
->fitArray
[nj
][ni
];
209 fit
->st2
+= pow(timoy
, 2);
211 fit
->sd2
+= pow(dji
, 2);
212 fit
->std
+= timoy
* dji
;
214 g_debug("intermediate values: dji= %f ti moy= %f "
215 "ni= %u nj= %u fit: n= %u st= %f st2= %f sd= %f "
216 "sd2= %f std= %f, ", dji
, timoy
, ni
, nj
, fit
->n
,
217 fit
->st
, fit
->st2
, fit
->sd
, fit
->sd2
, fit
->std
);
222 * Finalize the factor calculations
224 * The least squares analysis is finalized and finds the factors directly
225 * between each pair of traces that had events together. The traces are
226 * aranged in a graph, a reference trace is chosen and the factors between
227 * this reference and every other trace is calculated. Sometimes it is
228 * necessary to use many graphs when there are "islands" of independent
232 * syncState container for synchronization data.
235 * Factors[traceNb] synchronization factors for each trace
237 static GArray
* finalizeAnalysisLinReg(SyncState
* const syncState
)
241 // Finalize the processing
242 finalizeLSA(syncState
);
244 // Find a reference node and structure nodes in a graph
245 doGraphProcessing(syncState
);
247 /* Calculate the resulting offset and drift between each trace and its
250 factors
= calculateFactors(syncState
);
257 * Print statistics related to analysis. Must be called after
261 * syncState container for synchronization data.
263 static void printAnalysisStatsLinReg(SyncState
* const syncState
)
266 AnalysisDataLinReg
* analysisData
;
268 if (!syncState
->stats
)
273 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
275 printf("Linear regression analysis stats:\n");
277 printf("\tIndividual synchronization factors:\n");
279 for (j
= 0; j
< syncState
->traceNb
; j
++)
281 for (i
= 0; i
< j
; i
++)
285 fit
= &analysisData
->fitArray
[j
][i
];
286 printf("\t\t%3d - %-3d: ", i
, j
);
287 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit
->d0
, fit
->x
<
288 0. ? '-' : '+', fabs(fit
->x
), fit
->e
);
290 fit
= &analysisData
->fitArray
[i
][j
];
291 printf("\t\t%3d - %-3d: ", j
, i
);
292 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit
->d0
, fit
->x
<
293 0. ? '-' : '+', fabs(fit
->x
), fit
->e
);
298 for (i
= 0; i
< syncState
->traceNb
; i
++)
302 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
303 &gcfGraphTraceCompare
);
308 graph
= (Graph
*) result
->data
;
310 printf("\t\ttrace %u reference %u previous vertex ", i
,
313 if (i
== graph
->reference
)
319 printf("%u ", graph
->previousVertex
[i
]);
322 printf("stdev= %g\n", analysisData
->stDev
[i
]);
326 g_error("Trace %d not part of a graph\n", i
);
333 * Finalize the least-squares analysis. The intermediate values in the fit
334 * array are used to calculate the drift and the offset between each pair of
335 * nodes based on their exchanges.
338 * syncState: container for synchronization data.
340 static void finalizeLSA(SyncState
* const syncState
)
343 AnalysisDataLinReg
* analysisData
;
345 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
347 for (i
= 0; i
< syncState
->traceNb
; i
++)
349 for (j
= 0; j
< syncState
->traceNb
; j
++)
356 fit
= &analysisData
->fitArray
[i
][j
];
358 delta
= fit
->n
* fit
->st2
- pow(fit
->st
, 2);
359 fit
->x
= (fit
->n
* fit
->std
- fit
->st
* fit
->sd
) / delta
;
360 fit
->d0
= (fit
->st2
* fit
->sd
- fit
->st
* fit
->std
) / delta
;
361 fit
->e
= sqrt((fit
->sd2
- (fit
->n
* pow(fit
->std
, 2) +
362 pow(fit
->sd
, 2) * fit
->st2
- 2 * fit
->st
* fit
->sd
363 * fit
->std
) / delta
) / (fit
->n
- 2));
365 g_debug("[i= %u j= %u]\n", i
, j
);
366 g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g\n",
367 fit
->n
, fit
->st
, fit
->st2
, fit
->sd
, fit
->sd2
, fit
->std
);
368 g_debug("xij= %g d0ij= %g e= %g\n", fit
->x
, fit
->d0
, fit
->e
);
369 g_debug("(xji= %g d0ji= %g)\n", -fit
->x
/ (1 + fit
->x
),
370 -fit
->d0
/ (1 + fit
->x
));
378 * Structure nodes in graphs of nodes that had exchanges. Each graph has a
379 * reference node, the one that can reach the others with the smallest
383 * syncState: container for synchronization data.
384 * This function allocates these analysisData members:
387 static void doGraphProcessing(SyncState
* const syncState
)
391 unsigned int* previousVertex
;
392 AnalysisDataLinReg
* analysisData
;
394 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
396 distances
= malloc(syncState
->traceNb
* sizeof(double));
397 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned int));
398 analysisData
->graphList
= g_queue_new();
400 for (i
= 0; i
< syncState
->traceNb
; i
++)
405 // Perform shortest path search
406 g_debug("shortest path trace %d\ndistances: ", i
);
407 shortestPath(analysisData
->fitArray
, i
, syncState
->traceNb
, distances
,
410 for (j
= 0; j
< syncState
->traceNb
; j
++)
412 g_debug("%g, ", distances
[j
]);
414 g_debug("\npreviousVertex: ");
415 for (j
= 0; j
< syncState
->traceNb
; j
++)
417 g_debug("%u, ", previousVertex
[j
]);
421 // Group in graphs nodes that have exchanges
422 errorSum
= sumDistances(distances
, syncState
->traceNb
);
423 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
424 &gcfGraphTraceCompare
);
429 g_debug("found graph\n");
430 graph
= (Graph
*) result
->data
;
431 if (errorSum
< graph
->errorSum
)
433 g_debug("adding to graph\n");
434 graph
->errorSum
= errorSum
;
435 free(graph
->previousVertex
);
436 graph
->previousVertex
= previousVertex
;
438 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned
446 g_debug("creating new graph\n");
447 newGraph
= malloc(sizeof(Graph
));
448 newGraph
->errorSum
= errorSum
;
449 newGraph
->previousVertex
= previousVertex
;
450 newGraph
->reference
= i
;
451 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned int));
453 g_queue_push_tail(analysisData
->graphList
, newGraph
);
457 free(previousVertex
);
463 * Calculate the resulting offset and drift between each trace and its
467 * syncState: container for synchronization data.
470 * Factors[traceNb] synchronization factors for each trace
472 static GArray
* calculateFactors(SyncState
* const syncState
)
475 AnalysisDataLinReg
* analysisData
;
478 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
479 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
481 g_array_set_size(factors
, syncState
->traceNb
);
483 // Calculate the resulting offset and drift between each trace and its
485 for (i
= 0; i
< syncState
->traceNb
; i
++)
489 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
490 &gcfGraphTraceCompare
);
495 Factors
* traceFactors
;
497 graph
= (Graph
*) result
->data
;
498 traceFactors
= &g_array_index(factors
, Factors
, i
);
500 reduceFactors(analysisData
->fitArray
, graph
->previousVertex
, i
,
501 &traceFactors
->drift
, &traceFactors
->offset
, &stDev
);
503 if (syncState
->stats
)
505 analysisData
->stDev
[i
]= stDev
;
510 g_error("Trace %d not part of a graph\n", i
);
519 * Single-source shortest path search to find the path with the lowest error to
520 * convert one node's time to another.
521 * Uses Dijkstra's algorithm
524 * fitArray: array with the regression parameters
525 * traceNum: reference node
526 * traceNb: number of traces = number of nodes
527 * distances: array of computed distance from source node to node i,
528 * INFINITY if i is unreachable, preallocated to the number of
530 * previousVertex: previous vertex from a node i on the way to the source,
531 * UINT_MAX if i is not on the way or is the source,
532 * preallocated to the number of nodes
534 static void shortestPath(Fit
* const* const fitArray
, const unsigned int
535 traceNum
, const unsigned int traceNb
, double* const distances
, unsigned
536 int* const previousVertex
)
541 visited
= malloc(traceNb
* sizeof(bool));
543 for (i
= 0; i
< traceNb
; i
++)
549 fit
= &fitArray
[traceNum
][i
];
550 g_debug("fitArray[traceNum= %u][i= %u]->n = %u\n", traceNum
, i
, fit
->n
);
553 distances
[i
]= fit
->e
;
554 previousVertex
[i
]= traceNum
;
558 distances
[i
]= INFINITY
;
559 previousVertex
[i
]= UINT_MAX
;
562 visited
[traceNum
]= true;
564 for (j
= 0; j
< traceNb
; j
++)
566 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
570 for (i
= 0; i
< traceNb
- 2; i
++)
576 for (j
= 0; j
< traceNb
; j
++)
578 if (visited
[j
] == false && distances
[j
] < dvMin
)
585 g_debug("v= %u dvMin= %g\n", v
, dvMin
);
587 if (dvMin
!= INFINITY
)
591 for (j
= 0; j
< traceNb
; j
++)
595 fit
= &fitArray
[v
][j
];
596 if (visited
[j
] == false && fit
->n
> 0 && distances
[v
] + fit
->e
599 distances
[j
]= distances
[v
] + fit
->e
;
600 previousVertex
[j
]= v
;
609 for (j
= 0; j
< traceNb
; j
++)
611 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
621 * Cummulate the distances between a reference node and the other nodes
622 * reachable from it in a graph.
625 * distances: array of shortest path distances, with UINT_MAX for
627 * traceNb: number of nodes = number of traces
629 static double sumDistances(const double* const distances
, const unsigned int traceNb
)
635 for (i
= 0; i
< traceNb
; i
++)
637 if (distances
[i
] != INFINITY
)
639 result
+= distances
[i
];
648 * Cummulate the time correction factors between two nodes accross a graph
650 * With traceNum i, reference node r:
651 * tr= (1 + Xri) * ti + D0ri
652 * = drift * ti + offset
655 * fitArray: array with the regression parameters
656 * previousVertex: previous vertex from a node i on the way to the source,
657 * UINT_MAX if i is not on the way or is the source,
658 * preallocated to the number of nodes
659 * traceNum: end node, the reference depends on previousVertex
660 * drift: drift factor
661 * offset: offset factor
663 static void reduceFactors(Fit
* const* const fitArray
, const unsigned int* const
664 previousVertex
, const unsigned int traceNum
, double* const drift
, double*
665 const offset
, double* const stDev
)
667 if (previousVertex
[traceNum
] == UINT_MAX
)
676 double cummDrift
, cummOffset
, cummStDev
;
679 pv
= previousVertex
[traceNum
];
681 fit
= &fitArray
[pv
][traceNum
];
682 reduceFactors(fitArray
, previousVertex
, pv
, &cummDrift
, &cummOffset
,
685 *drift
= cummDrift
* (1 + fit
->x
);
686 *offset
= cummDrift
* fit
->d0
+ cummOffset
;
687 *stDev
= fit
->x
* cummStDev
+ fit
->e
;
693 * A GFunc for g_queue_foreach()
696 * data Graph*, graph to destroy
699 static void gfGraphDestroy(gpointer data
, gpointer user_data
)
703 graph
= (Graph
*) data
;
705 free(graph
->previousVertex
);
711 * A GCompareFunc for g_queue_find_custom()
715 * b: unsigned int* traceNum
718 * 0 if graph contains traceNum
720 static gint
gcfGraphTraceCompare(gconstpointer a
, gconstpointer b
)
723 unsigned int traceNum
;
726 traceNum
= *(unsigned int *) b
;
728 if (graph
->previousVertex
[traceNum
] != UINT_MAX
)
732 else if (graph
->reference
== traceNum
)
744 * Write the analysis-specific graph lines in the gnuplot script.
747 * syncState: container for synchronization data
748 * i: first trace number, on the x axis
749 * j: second trace number, garanteed to be larger than i
751 void writeAnalysisGraphsPlotsLinReg(SyncState
* const syncState
, const unsigned
752 int i
, const unsigned int j
)
754 AnalysisDataLinReg
* analysisData
;
757 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
758 fit
= &analysisData
->fitArray
[j
][i
];
760 fprintf(syncState
->graphsStream
,
762 "title \"Linreg conversion\" with lines "
763 "linecolor rgb \"gray60\" linetype 1, \\\n",
764 fit
->d0
, 1. + fit
->x
);