1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
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.
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.
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/>.
18 // for INFINITY in math.h
19 #define _ISOC99_SOURCE
29 #include "sync_chain.h"
31 #include "event_analysis_linreg.h"
34 // Functions common to all analysis modules
35 static void initAnalysisLinReg(SyncState
* const syncState
);
36 static void destroyAnalysisLinReg(SyncState
* const syncState
);
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
);
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
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
);
57 // Graph-related Glib functions
58 static void gfGraphDestroy(gpointer data
, gpointer user_data
);
59 static gint
gcfGraphTraceCompare(gconstpointer a
, gconstpointer b
);
62 static AnalysisModule analysisModuleLinReg
= {
64 .initAnalysis
= &initAnalysisLinReg
,
65 .destroyAnalysis
= &destroyAnalysisLinReg
,
66 .analyzeExchange
= &analyzeExchangeLinReg
,
67 .finalizeAnalysis
= &finalizeAnalysisLinReg
,
68 .printAnalysisStats
= &printAnalysisStatsLinReg
,
70 .writeTraceTraceForePlots
= &writeAnalysisGraphsPlotsLinReg
,
76 * Analysis module registering function
78 void registerAnalysisLinReg()
80 g_queue_push_tail(&analysisModules
, &analysisModuleLinReg
);
85 * Analysis init function
87 * This function is called at the beginning of a synchronization run for a set
90 * Allocate some of the analysis specific data structures
93 * syncState container for synchronization data.
94 * This function allocates these analysisData members:
98 static void initAnalysisLinReg(SyncState
* const syncState
)
101 AnalysisDataLinReg
* analysisData
;
103 analysisData
= malloc(sizeof(AnalysisDataLinReg
));
104 syncState
->analysisData
= analysisData
;
106 analysisData
->fitArray
= malloc(syncState
->traceNb
* sizeof(Fit
*));
107 for (i
= 0; i
< syncState
->traceNb
; i
++)
109 analysisData
->fitArray
[i
]= calloc(syncState
->traceNb
, sizeof(Fit
));
112 if (syncState
->stats
)
114 analysisData
->stDev
= malloc(sizeof(double) * syncState
->traceNb
);
120 * Analysis destroy function
122 * Free the analysis specific data structures
125 * syncState container for synchronization data.
126 * This function deallocates these analysisData members:
131 static void destroyAnalysisLinReg(SyncState
* const syncState
)
134 AnalysisDataLinReg
* analysisData
;
136 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
138 if (analysisData
== NULL
)
143 for (i
= 0; i
< syncState
->traceNb
; i
++)
145 free(analysisData
->fitArray
[i
]);
147 free(analysisData
->fitArray
);
149 g_queue_foreach(analysisData
->graphList
, &gfGraphDestroy
, NULL
);
150 g_queue_free(analysisData
->graphList
);
152 if (syncState
->stats
)
154 free(analysisData
->stDev
);
157 free(syncState
->analysisData
);
158 syncState
->analysisData
= NULL
;
163 * Perform analysis on a series of event pairs.
166 * syncState container for synchronization data
167 * exchange structure containing the many events
169 static void analyzeExchangeLinReg(SyncState
* const syncState
, Exchange
* const exchange
)
175 Message
* ackedMessage
;
176 AnalysisDataLinReg
* analysisData
;
178 g_debug("Synchronization calculation, "
179 "%d acked packets - using last one,",
180 g_queue_get_length(exchange
->acks
));
182 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
183 ackedMessage
= g_queue_peek_tail(exchange
->acks
);
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
];
201 fit
->st2
+= pow(timoy
, 2);
203 fit
->sd2
+= pow(dji
, 2);
204 fit
->std
+= timoy
* dji
;
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
);
214 * Finalize the factor calculations
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
224 * syncState container for synchronization data.
227 * Factors[traceNb] synchronization factors for each trace
229 static GArray
* finalizeAnalysisLinReg(SyncState
* const syncState
)
233 // Finalize the processing
234 finalizeLSA(syncState
);
236 // Find a reference node and structure nodes in a graph
237 doGraphProcessing(syncState
);
239 /* Calculate the resulting offset and drift between each trace and its
242 factors
= calculateFactors(syncState
);
249 * Print statistics related to analysis. Must be called after
253 * syncState container for synchronization data.
255 static void printAnalysisStatsLinReg(SyncState
* const syncState
)
258 AnalysisDataLinReg
* analysisData
;
260 if (!syncState
->stats
)
265 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
267 printf("Linear regression analysis stats:\n");
269 printf("\tIndividual synchronization factors:\n");
271 for (j
= 0; j
< syncState
->traceNb
; j
++)
273 for (i
= 0; i
< j
; i
++)
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
);
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
);
290 for (i
= 0; i
< syncState
->traceNb
; i
++)
294 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
295 &gcfGraphTraceCompare
);
300 graph
= (Graph
*) result
->data
;
302 printf("\t\ttrace %u reference %u previous vertex ", i
,
305 if (i
== graph
->reference
)
311 printf("%u ", graph
->previousVertex
[i
]);
314 printf("stdev= %g\n", analysisData
->stDev
[i
]);
318 g_error("Trace %d not part of a graph\n", i
);
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.
330 * syncState: container for synchronization data.
332 static void finalizeLSA(SyncState
* const syncState
)
335 AnalysisDataLinReg
* analysisData
;
337 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
339 for (i
= 0; i
< syncState
->traceNb
; i
++)
341 for (j
= 0; j
< syncState
->traceNb
; j
++)
348 fit
= &analysisData
->fitArray
[i
][j
];
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));
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
));
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
375 * syncState: container for synchronization data.
376 * This function allocates these analysisData members:
379 static void doGraphProcessing(SyncState
* const syncState
)
383 unsigned int* previousVertex
;
384 AnalysisDataLinReg
* analysisData
;
386 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
388 distances
= malloc(syncState
->traceNb
* sizeof(double));
389 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned int));
390 analysisData
->graphList
= g_queue_new();
392 for (i
= 0; i
< syncState
->traceNb
; i
++)
397 // Perform shortest path search
398 g_debug("shortest path trace %d, distances: ", i
);
399 shortestPath(analysisData
->fitArray
, i
, syncState
->traceNb
, distances
,
402 for (j
= 0; j
< syncState
->traceNb
; j
++)
404 g_debug("%g, ", distances
[j
]);
406 g_debug("previousVertex: ");
407 for (j
= 0; j
< syncState
->traceNb
; j
++)
409 g_debug("%u, ", previousVertex
[j
]);
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
);
420 g_debug("found graph");
421 graph
= (Graph
*) result
->data
;
422 if (errorSum
< graph
->errorSum
)
424 g_debug("adding to graph");
425 graph
->errorSum
= errorSum
;
426 free(graph
->previousVertex
);
427 graph
->previousVertex
= previousVertex
;
429 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned
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));
444 g_queue_push_tail(analysisData
->graphList
, newGraph
);
448 free(previousVertex
);
454 * Calculate the resulting offset and drift between each trace and its
458 * syncState: container for synchronization data.
461 * Factors[traceNb] synchronization factors for each trace
463 static GArray
* calculateFactors(SyncState
* const syncState
)
466 AnalysisDataLinReg
* analysisData
;
469 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
470 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
472 g_array_set_size(factors
, syncState
->traceNb
);
474 // Calculate the resulting offset and drift between each trace and its
476 for (i
= 0; i
< syncState
->traceNb
; i
++)
480 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
481 &gcfGraphTraceCompare
);
486 Factors
* traceFactors
;
488 graph
= (Graph
*) result
->data
;
489 traceFactors
= &g_array_index(factors
, Factors
, i
);
491 reduceFactors(analysisData
->fitArray
, graph
->previousVertex
, i
,
492 &traceFactors
->drift
, &traceFactors
->offset
, &stDev
);
494 if (syncState
->stats
)
496 analysisData
->stDev
[i
]= stDev
;
501 g_error("Trace %d not part of a graph\n", i
);
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
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
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
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
)
532 visited
= malloc(traceNb
* sizeof(bool));
534 for (i
= 0; i
< traceNb
; i
++)
540 fit
= &fitArray
[traceNum
][i
];
541 g_debug("fitArray[traceNum= %u][i= %u]->n = %u", traceNum
, i
, fit
->n
);
544 distances
[i
]= fit
->e
;
545 previousVertex
[i
]= traceNum
;
549 distances
[i
]= INFINITY
;
550 previousVertex
[i
]= UINT_MAX
;
553 visited
[traceNum
]= true;
555 for (j
= 0; j
< traceNb
; j
++)
557 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
560 for (i
= 0; i
< traceNb
- 2; i
++)
566 for (j
= 0; j
< traceNb
; j
++)
568 if (visited
[j
] == false && distances
[j
] < dvMin
)
575 g_debug("v= %u dvMin= %g", v
, dvMin
);
577 if (dvMin
!= INFINITY
)
581 for (j
= 0; j
< traceNb
; j
++)
585 fit
= &fitArray
[v
][j
];
586 if (visited
[j
] == false && fit
->n
> 0 && distances
[v
] + fit
->e
589 distances
[j
]= distances
[v
] + fit
->e
;
590 previousVertex
[j
]= v
;
599 for (j
= 0; j
< traceNb
; j
++)
601 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
610 * Cummulate the distances between a reference node and the other nodes
611 * reachable from it in a graph.
614 * distances: array of shortest path distances, with UINT_MAX for
616 * traceNb: number of nodes = number of traces
618 static double sumDistances(const double* const distances
, const unsigned int traceNb
)
624 for (i
= 0; i
< traceNb
; i
++)
626 if (distances
[i
] != INFINITY
)
628 result
+= distances
[i
];
637 * Cummulate the time correction factors between two nodes accross a graph
639 * With traceNum i, reference node r:
640 * tr= (1 + Xri) * ti + D0ri
641 * = drift * ti + offset
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
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
)
656 if (previousVertex
[traceNum
] == UINT_MAX
)
665 double cummDrift
, cummOffset
, cummStDev
;
668 pv
= previousVertex
[traceNum
];
670 fit
= &fitArray
[pv
][traceNum
];
671 reduceFactors(fitArray
, previousVertex
, pv
, &cummDrift
, &cummOffset
,
674 *drift
= cummDrift
* (1 + fit
->x
);
675 *offset
= cummDrift
* fit
->d0
+ cummOffset
;
676 *stDev
= fit
->x
* cummStDev
+ fit
->e
;
682 * A GFunc for g_queue_foreach()
685 * data Graph*, graph to destroy
688 static void gfGraphDestroy(gpointer data
, gpointer user_data
)
692 graph
= (Graph
*) data
;
694 free(graph
->previousVertex
);
700 * A GCompareFunc for g_queue_find_custom()
704 * b: unsigned int* traceNum
707 * 0 if graph contains traceNum
709 static gint
gcfGraphTraceCompare(gconstpointer a
, gconstpointer b
)
712 unsigned int traceNum
;
715 traceNum
= *(unsigned int *) b
;
717 if (graph
->previousVertex
[traceNum
] != UINT_MAX
)
721 else if (graph
->reference
== traceNum
)
733 * Write the analysis-specific graph lines in the gnuplot script.
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
740 void writeAnalysisGraphsPlotsLinReg(SyncState
* const syncState
, const unsigned
741 int i
, const unsigned int j
)
743 AnalysisDataLinReg
* analysisData
;
746 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
747 fit
= &analysisData
->fitArray
[j
][i
];
749 fprintf(syncState
->graphsStream
,
751 "title \"Linreg conversion\" with lines "
752 "linecolor rgb \"gray60\" linetype 1, \\\n",
753 fit
->d0
, 1. + fit
->x
);