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"
35 // Functions common to all analysis modules
36 static void initAnalysisLinReg(SyncState
* const syncState
);
37 static void destroyAnalysisLinReg(SyncState
* const syncState
);
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
);
45 // Functions specific to this module
46 static void registerAnalysisLinReg() __attribute__((constructor (102)));
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
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
);
60 // Graph-related Glib functions
61 static void gfGraphDestroy(gpointer data
, gpointer user_data
);
62 static gint
gcfGraphTraceCompare(gconstpointer a
, gconstpointer b
);
65 static AnalysisModule analysisModuleLinReg
= {
67 .initAnalysis
= &initAnalysisLinReg
,
68 .destroyAnalysis
= &destroyAnalysisLinReg
,
69 .analyzeExchange
= &analyzeExchangeLinReg
,
70 .finalizeAnalysis
= &finalizeAnalysisLinReg
,
71 .printAnalysisStats
= &printAnalysisStatsLinReg
,
73 .writeTraceTraceForePlots
= &writeAnalysisGraphsPlotsLinReg
,
79 * Analysis module registering function
81 static void registerAnalysisLinReg()
83 g_queue_push_tail(&analysisModules
, &analysisModuleLinReg
);
88 * Analysis init function
90 * This function is called at the beginning of a synchronization run for a set
93 * Allocate some of the analysis specific data structures
96 * syncState container for synchronization data.
97 * This function allocates these analysisData members:
101 static void initAnalysisLinReg(SyncState
* const syncState
)
104 AnalysisDataLinReg
* analysisData
;
106 analysisData
= malloc(sizeof(AnalysisDataLinReg
));
107 syncState
->analysisData
= analysisData
;
109 analysisData
->fitArray
= malloc(syncState
->traceNb
* sizeof(Fit
*));
110 for (i
= 0; i
< syncState
->traceNb
; i
++)
112 analysisData
->fitArray
[i
]= calloc(syncState
->traceNb
, sizeof(Fit
));
115 if (syncState
->stats
)
117 analysisData
->stDev
= malloc(sizeof(double) * syncState
->traceNb
);
123 * Analysis destroy function
125 * Free the analysis specific data structures
128 * syncState container for synchronization data.
129 * This function deallocates these analysisData members:
134 static void destroyAnalysisLinReg(SyncState
* const syncState
)
137 AnalysisDataLinReg
* analysisData
;
139 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
141 if (analysisData
== NULL
)
146 for (i
= 0; i
< syncState
->traceNb
; i
++)
148 free(analysisData
->fitArray
[i
]);
150 free(analysisData
->fitArray
);
152 g_queue_foreach(analysisData
->graphList
, &gfGraphDestroy
, NULL
);
153 g_queue_free(analysisData
->graphList
);
155 if (syncState
->stats
)
157 free(analysisData
->stDev
);
160 free(syncState
->analysisData
);
161 syncState
->analysisData
= NULL
;
166 * Perform analysis on a series of event pairs.
169 * syncState container for synchronization data
170 * exchange structure containing the many events
172 static void analyzeExchangeLinReg(SyncState
* const syncState
, Exchange
* const exchange
)
178 Message
* ackedMessage
;
179 AnalysisDataLinReg
* analysisData
;
181 g_debug("Synchronization calculation, "
182 "%d acked packets - using last one,",
183 g_queue_get_length(exchange
->acks
));
185 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
186 ackedMessage
= g_queue_peek_tail(exchange
->acks
);
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
];
204 fit
->st2
+= pow(timoy
, 2);
206 fit
->sd2
+= pow(dji
, 2);
207 fit
->std
+= timoy
* dji
;
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
);
217 * Finalize the factor calculations
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
227 * syncState container for synchronization data.
230 * Factors[traceNb] synchronization factors for each trace
232 static GArray
* finalizeAnalysisLinReg(SyncState
* const syncState
)
236 // Finalize the processing
237 finalizeLSA(syncState
);
239 // Find a reference node and structure nodes in a graph
240 doGraphProcessing(syncState
);
242 /* Calculate the resulting offset and drift between each trace and its
245 factors
= calculateFactors(syncState
);
252 * Print statistics related to analysis. Must be called after
256 * syncState container for synchronization data.
258 static void printAnalysisStatsLinReg(SyncState
* const syncState
)
261 AnalysisDataLinReg
* analysisData
;
263 if (!syncState
->stats
)
268 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
270 printf("Linear regression analysis stats:\n");
272 printf("\tIndividual synchronization factors:\n");
274 for (j
= 0; j
< syncState
->traceNb
; j
++)
276 for (i
= 0; i
< j
; i
++)
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
);
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
);
293 for (i
= 0; i
< syncState
->traceNb
; i
++)
297 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
298 &gcfGraphTraceCompare
);
303 graph
= (Graph
*) result
->data
;
305 printf("\t\ttrace %u reference %u previous vertex ", i
,
308 if (i
== graph
->reference
)
314 printf("%u ", graph
->previousVertex
[i
]);
317 printf("stdev= %g\n", analysisData
->stDev
[i
]);
321 g_error("Trace %d not part of a graph\n", i
);
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.
333 * syncState: container for synchronization data.
335 static void finalizeLSA(SyncState
* const syncState
)
338 AnalysisDataLinReg
* analysisData
;
340 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
342 for (i
= 0; i
< syncState
->traceNb
; i
++)
344 for (j
= 0; j
< syncState
->traceNb
; j
++)
351 fit
= &analysisData
->fitArray
[i
][j
];
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));
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
));
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
378 * syncState: container for synchronization data.
379 * This function allocates these analysisData members:
382 static void doGraphProcessing(SyncState
* const syncState
)
386 unsigned int* previousVertex
;
387 AnalysisDataLinReg
* analysisData
;
389 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
391 distances
= malloc(syncState
->traceNb
* sizeof(double));
392 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned int));
393 analysisData
->graphList
= g_queue_new();
395 for (i
= 0; i
< syncState
->traceNb
; i
++)
400 // Perform shortest path search
401 g_debug("shortest path trace %d, distances: ", i
);
402 shortestPath(analysisData
->fitArray
, i
, syncState
->traceNb
, distances
,
405 for (j
= 0; j
< syncState
->traceNb
; j
++)
407 g_debug("%g, ", distances
[j
]);
409 g_debug("previousVertex: ");
410 for (j
= 0; j
< syncState
->traceNb
; j
++)
412 g_debug("%u, ", previousVertex
[j
]);
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
);
423 g_debug("found graph");
424 graph
= (Graph
*) result
->data
;
425 if (errorSum
< graph
->errorSum
)
427 g_debug("adding to graph");
428 graph
->errorSum
= errorSum
;
429 free(graph
->previousVertex
);
430 graph
->previousVertex
= previousVertex
;
432 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned
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));
447 g_queue_push_tail(analysisData
->graphList
, newGraph
);
451 free(previousVertex
);
457 * Calculate the resulting offset and drift between each trace and its
461 * syncState: container for synchronization data.
464 * Factors[traceNb] synchronization factors for each trace
466 static GArray
* calculateFactors(SyncState
* const syncState
)
469 AnalysisDataLinReg
* analysisData
;
472 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
473 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
475 g_array_set_size(factors
, syncState
->traceNb
);
477 // Calculate the resulting offset and drift between each trace and its
479 for (i
= 0; i
< syncState
->traceNb
; i
++)
483 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
484 &gcfGraphTraceCompare
);
489 Factors
* traceFactors
;
491 graph
= (Graph
*) result
->data
;
492 traceFactors
= &g_array_index(factors
, Factors
, i
);
494 reduceFactors(analysisData
->fitArray
, graph
->previousVertex
, i
,
495 &traceFactors
->drift
, &traceFactors
->offset
, &stDev
);
497 if (syncState
->stats
)
499 analysisData
->stDev
[i
]= stDev
;
504 g_error("Trace %d not part of a graph\n", i
);
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
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
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
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
)
535 visited
= malloc(traceNb
* sizeof(bool));
537 for (i
= 0; i
< traceNb
; i
++)
543 fit
= &fitArray
[traceNum
][i
];
544 g_debug("fitArray[traceNum= %u][i= %u]->n = %u", traceNum
, i
, fit
->n
);
547 distances
[i
]= fit
->e
;
548 previousVertex
[i
]= traceNum
;
552 distances
[i
]= INFINITY
;
553 previousVertex
[i
]= UINT_MAX
;
556 visited
[traceNum
]= true;
558 for (j
= 0; j
< traceNb
; j
++)
560 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
563 for (i
= 0; i
< traceNb
- 2; i
++)
569 for (j
= 0; j
< traceNb
; j
++)
571 if (visited
[j
] == false && distances
[j
] < dvMin
)
578 g_debug("v= %u dvMin= %g", v
, dvMin
);
580 if (dvMin
!= INFINITY
)
584 for (j
= 0; j
< traceNb
; j
++)
588 fit
= &fitArray
[v
][j
];
589 if (visited
[j
] == false && fit
->n
> 0 && distances
[v
] + fit
->e
592 distances
[j
]= distances
[v
] + fit
->e
;
593 previousVertex
[j
]= v
;
602 for (j
= 0; j
< traceNb
; j
++)
604 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
613 * Cummulate the distances between a reference node and the other nodes
614 * reachable from it in a graph.
617 * distances: array of shortest path distances, with UINT_MAX for
619 * traceNb: number of nodes = number of traces
621 static double sumDistances(const double* const distances
, const unsigned int traceNb
)
627 for (i
= 0; i
< traceNb
; i
++)
629 if (distances
[i
] != INFINITY
)
631 result
+= distances
[i
];
640 * Cummulate the time correction factors between two nodes accross a graph
642 * With traceNum i, reference node r:
643 * tr= (1 + Xri) * ti + D0ri
644 * = drift * ti + offset
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
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
)
659 if (previousVertex
[traceNum
] == UINT_MAX
)
668 double cummDrift
, cummOffset
, cummStDev
;
671 pv
= previousVertex
[traceNum
];
673 fit
= &fitArray
[pv
][traceNum
];
674 reduceFactors(fitArray
, previousVertex
, pv
, &cummDrift
, &cummOffset
,
677 *drift
= cummDrift
* (1 + fit
->x
);
678 *offset
= cummDrift
* fit
->d0
+ cummOffset
;
679 *stDev
= fit
->x
* cummStDev
+ fit
->e
;
685 * A GFunc for g_queue_foreach()
688 * data Graph*, graph to destroy
691 static void gfGraphDestroy(gpointer data
, gpointer user_data
)
695 graph
= (Graph
*) data
;
697 free(graph
->previousVertex
);
703 * A GCompareFunc for g_queue_find_custom()
707 * b: unsigned int* traceNum
710 * 0 if graph contains traceNum
712 static gint
gcfGraphTraceCompare(gconstpointer a
, gconstpointer b
)
715 unsigned int traceNum
;
718 traceNum
= *(unsigned int *) b
;
720 if (graph
->previousVertex
[traceNum
] != UINT_MAX
)
724 else if (graph
->reference
== traceNum
)
736 * Write the analysis-specific graph lines in the gnuplot script.
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
743 void writeAnalysisGraphsPlotsLinReg(SyncState
* const syncState
, const unsigned
744 int i
, const unsigned int j
)
746 AnalysisDataLinReg
* analysisData
;
749 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
750 fit
= &analysisData
->fitArray
[j
][i
];
752 fprintf(syncState
->graphsStream
,
754 "title \"Linreg conversion\" with lines "
755 "linecolor rgb \"gray60\" linetype 1, \\\n",
756 fit
->d0
, 1. + fit
->x
);