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 finalizeLSA(SyncState
* const syncState
);
47 static void doGraphProcessing(SyncState
* const syncState
);
48 static GArray
* calculateFactors(SyncState
* const syncState
);
49 static void shortestPath(Fit
* const* const fitArray
, const unsigned int
50 traceNum
, const unsigned int traceNb
, double* const distances
,
51 unsigned int* const previousVertex
);
52 static double sumDistances(const double* const distances
, const unsigned int
54 static void reduceFactors(Fit
* const* const fitArray
, const unsigned int* const
55 previousVertex
, const unsigned int traceNum
, double* const drift
,
56 double* const offset
, double* const stDev
);
58 // Graph-related Glib functions
59 static void gfGraphDestroy(gpointer data
, gpointer user_data
);
60 static gint
gcfGraphTraceCompare(gconstpointer a
, gconstpointer b
);
63 static AnalysisModule analysisModuleLinReg
= {
65 .initAnalysis
= &initAnalysisLinReg
,
66 .destroyAnalysis
= &destroyAnalysisLinReg
,
67 .analyzeExchange
= &analyzeExchangeLinReg
,
68 .finalizeAnalysis
= &finalizeAnalysisLinReg
,
69 .printAnalysisStats
= &printAnalysisStatsLinReg
,
71 .writeTraceTraceForePlots
= &writeAnalysisGraphsPlotsLinReg
,
77 * Analysis module registering function
79 void registerAnalysisLinReg()
81 g_queue_push_tail(&analysisModules
, &analysisModuleLinReg
);
86 * Analysis init function
88 * This function is called at the beginning of a synchronization run for a set
91 * Allocate some of the analysis specific data structures
94 * syncState container for synchronization data.
95 * This function allocates these analysisData members:
99 static void initAnalysisLinReg(SyncState
* const syncState
)
102 AnalysisDataLinReg
* analysisData
;
104 analysisData
= malloc(sizeof(AnalysisDataLinReg
));
105 syncState
->analysisData
= analysisData
;
107 analysisData
->fitArray
= malloc(syncState
->traceNb
* sizeof(Fit
*));
108 for (i
= 0; i
< syncState
->traceNb
; i
++)
110 analysisData
->fitArray
[i
]= calloc(syncState
->traceNb
, sizeof(Fit
));
113 if (syncState
->stats
)
115 analysisData
->stDev
= malloc(sizeof(double) * syncState
->traceNb
);
121 * Analysis destroy function
123 * Free the analysis specific data structures
126 * syncState container for synchronization data.
127 * This function deallocates these analysisData members:
132 static void destroyAnalysisLinReg(SyncState
* const syncState
)
135 AnalysisDataLinReg
* analysisData
;
137 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
139 if (analysisData
== NULL
)
144 for (i
= 0; i
< syncState
->traceNb
; i
++)
146 free(analysisData
->fitArray
[i
]);
148 free(analysisData
->fitArray
);
150 g_queue_foreach(analysisData
->graphList
, &gfGraphDestroy
, NULL
);
151 g_queue_free(analysisData
->graphList
);
153 if (syncState
->stats
)
155 free(analysisData
->stDev
);
158 free(syncState
->analysisData
);
159 syncState
->analysisData
= NULL
;
164 * Perform analysis on a series of event pairs.
167 * syncState container for synchronization data
168 * exchange structure containing the many events
170 static void analyzeExchangeLinReg(SyncState
* const syncState
, Exchange
* const exchange
)
176 Message
* ackedMessage
;
177 AnalysisDataLinReg
* analysisData
;
179 g_debug("Synchronization calculation, "
180 "%d acked packets - using last one,",
181 g_queue_get_length(exchange
->acks
));
183 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
184 ackedMessage
= g_queue_peek_tail(exchange
->acks
);
186 // Calculate the intermediate values for the
187 // least-squares analysis
188 dji
= ((double) ackedMessage
->inE
->cpuTime
- (double) ackedMessage
->outE
->cpuTime
189 + (double) exchange
->message
->outE
->cpuTime
- (double)
190 exchange
->message
->inE
->cpuTime
) / 2;
191 eji
= fabs((double) ackedMessage
->inE
->cpuTime
- (double)
192 ackedMessage
->outE
->cpuTime
- (double) exchange
->message
->outE
->cpuTime
+
193 (double) exchange
->message
->inE
->cpuTime
) / 2;
194 timoy
= ((double) ackedMessage
->outE
->cpuTime
+ (double)
195 exchange
->message
->inE
->cpuTime
) / 2;
196 ni
= ackedMessage
->outE
->traceNum
;
197 nj
= ackedMessage
->inE
->traceNum
;
198 fit
= &analysisData
->fitArray
[nj
][ni
];
202 fit
->st2
+= pow(timoy
, 2);
204 fit
->sd2
+= pow(dji
, 2);
205 fit
->std
+= timoy
* dji
;
207 g_debug("intermediate values: dji= %f ti moy= %f "
208 "ni= %u nj= %u fit: n= %u st= %f st2= %f sd= %f "
209 "sd2= %f std= %f, ", dji
, timoy
, ni
, nj
, fit
->n
,
210 fit
->st
, fit
->st2
, fit
->sd
, fit
->sd2
, fit
->std
);
215 * Finalize the factor calculations
217 * The least squares analysis is finalized and finds the factors directly
218 * between each pair of traces that had events together. The traces are
219 * aranged in a graph, a reference trace is chosen and the factors between
220 * this reference and every other trace is calculated. Sometimes it is
221 * necessary to use many graphs when there are "islands" of independent
225 * syncState container for synchronization data.
228 * Factors[traceNb] synchronization factors for each trace
230 static GArray
* finalizeAnalysisLinReg(SyncState
* const syncState
)
234 // Finalize the processing
235 finalizeLSA(syncState
);
237 // Find a reference node and structure nodes in a graph
238 doGraphProcessing(syncState
);
240 /* Calculate the resulting offset and drift between each trace and its
243 factors
= calculateFactors(syncState
);
250 * Print statistics related to analysis. Must be called after
254 * syncState container for synchronization data.
256 static void printAnalysisStatsLinReg(SyncState
* const syncState
)
259 AnalysisDataLinReg
* analysisData
;
261 if (!syncState
->stats
)
266 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
268 printf("Linear regression analysis stats:\n");
270 printf("\tIndividual synchronization factors:\n");
272 for (j
= 0; j
< syncState
->traceNb
; j
++)
274 for (i
= 0; i
< j
; i
++)
278 fit
= &analysisData
->fitArray
[j
][i
];
279 printf("\t\t%3d - %-3d: ", i
, j
);
280 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit
->d0
, fit
->x
<
281 0. ? '-' : '+', fabs(fit
->x
), fit
->e
);
283 fit
= &analysisData
->fitArray
[i
][j
];
284 printf("\t\t%3d - %-3d: ", j
, i
);
285 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit
->d0
, fit
->x
<
286 0. ? '-' : '+', fabs(fit
->x
), fit
->e
);
291 for (i
= 0; i
< syncState
->traceNb
; i
++)
295 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
296 &gcfGraphTraceCompare
);
301 graph
= (Graph
*) result
->data
;
303 printf("\t\ttrace %u reference %u previous vertex ", i
,
306 if (i
== graph
->reference
)
312 printf("%u ", graph
->previousVertex
[i
]);
315 printf("stdev= %g\n", analysisData
->stDev
[i
]);
319 g_error("Trace %d not part of a graph\n", i
);
326 * Finalize the least-squares analysis. The intermediate values in the fit
327 * array are used to calculate the drift and the offset between each pair of
328 * nodes based on their exchanges.
331 * syncState: container for synchronization data.
333 static void finalizeLSA(SyncState
* const syncState
)
336 AnalysisDataLinReg
* analysisData
;
338 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
340 for (i
= 0; i
< syncState
->traceNb
; i
++)
342 for (j
= 0; j
< syncState
->traceNb
; j
++)
349 fit
= &analysisData
->fitArray
[i
][j
];
351 delta
= fit
->n
* fit
->st2
- pow(fit
->st
, 2);
352 fit
->x
= (fit
->n
* fit
->std
- fit
->st
* fit
->sd
) / delta
;
353 fit
->d0
= (fit
->st2
* fit
->sd
- fit
->st
* fit
->std
) / delta
;
354 fit
->e
= sqrt((fit
->sd2
- (fit
->n
* pow(fit
->std
, 2) +
355 pow(fit
->sd
, 2) * fit
->st2
- 2 * fit
->st
* fit
->sd
356 * fit
->std
) / delta
) / (fit
->n
- 2));
358 g_debug("[i= %u j= %u]", i
, j
);
359 g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g",
360 fit
->n
, fit
->st
, fit
->st2
, fit
->sd
, fit
->sd2
, fit
->std
);
361 g_debug("xij= %g d0ij= %g e= %g", fit
->x
, fit
->d0
, fit
->e
);
362 g_debug("(xji= %g d0ji= %g)", -fit
->x
/ (1 + fit
->x
),
363 -fit
->d0
/ (1 + fit
->x
));
371 * Structure nodes in graphs of nodes that had exchanges. Each graph has a
372 * reference node, the one that can reach the others with the smallest
376 * syncState: container for synchronization data.
377 * This function allocates these analysisData members:
380 static void doGraphProcessing(SyncState
* const syncState
)
384 unsigned int* previousVertex
;
385 AnalysisDataLinReg
* analysisData
;
387 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
389 distances
= malloc(syncState
->traceNb
* sizeof(double));
390 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned int));
391 analysisData
->graphList
= g_queue_new();
393 for (i
= 0; i
< syncState
->traceNb
; i
++)
398 // Perform shortest path search
399 g_debug("shortest path trace %d, distances: ", i
);
400 shortestPath(analysisData
->fitArray
, i
, syncState
->traceNb
, distances
,
403 for (j
= 0; j
< syncState
->traceNb
; j
++)
405 g_debug("%g, ", distances
[j
]);
407 g_debug("previousVertex: ");
408 for (j
= 0; j
< syncState
->traceNb
; j
++)
410 g_debug("%u, ", previousVertex
[j
]);
413 // Group in graphs nodes that have exchanges
414 errorSum
= sumDistances(distances
, syncState
->traceNb
);
415 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
416 &gcfGraphTraceCompare
);
421 g_debug("found graph");
422 graph
= (Graph
*) result
->data
;
423 if (errorSum
< graph
->errorSum
)
425 g_debug("adding to graph");
426 graph
->errorSum
= errorSum
;
427 free(graph
->previousVertex
);
428 graph
->previousVertex
= previousVertex
;
430 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned
438 g_debug("creating new graph");
439 newGraph
= malloc(sizeof(Graph
));
440 newGraph
->errorSum
= errorSum
;
441 newGraph
->previousVertex
= previousVertex
;
442 newGraph
->reference
= i
;
443 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned int));
445 g_queue_push_tail(analysisData
->graphList
, newGraph
);
449 free(previousVertex
);
455 * Calculate the resulting offset and drift between each trace and its
459 * syncState: container for synchronization data.
462 * Factors[traceNb] synchronization factors for each trace
464 static GArray
* calculateFactors(SyncState
* const syncState
)
467 AnalysisDataLinReg
* analysisData
;
470 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
471 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
473 g_array_set_size(factors
, syncState
->traceNb
);
475 // Calculate the resulting offset and drift between each trace and its
477 for (i
= 0; i
< syncState
->traceNb
; i
++)
481 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
482 &gcfGraphTraceCompare
);
487 Factors
* traceFactors
;
489 graph
= (Graph
*) result
->data
;
490 traceFactors
= &g_array_index(factors
, Factors
, i
);
492 reduceFactors(analysisData
->fitArray
, graph
->previousVertex
, i
,
493 &traceFactors
->drift
, &traceFactors
->offset
, &stDev
);
495 if (syncState
->stats
)
497 analysisData
->stDev
[i
]= stDev
;
502 g_error("Trace %d not part of a graph\n", i
);
511 * Single-source shortest path search to find the path with the lowest error to
512 * convert one node's time to another.
513 * Uses Dijkstra's algorithm
516 * fitArray: array with the regression parameters
517 * traceNum: reference node
518 * traceNb: number of traces = number of nodes
519 * distances: array of computed distance from source node to node i,
520 * INFINITY if i is unreachable, preallocated to the number of
522 * previousVertex: previous vertex from a node i on the way to the source,
523 * UINT_MAX if i is not on the way or is the source,
524 * preallocated to the number of nodes
526 static void shortestPath(Fit
* const* const fitArray
, const unsigned int
527 traceNum
, const unsigned int traceNb
, double* const distances
, unsigned
528 int* const previousVertex
)
533 visited
= malloc(traceNb
* sizeof(bool));
535 for (i
= 0; i
< traceNb
; i
++)
541 fit
= &fitArray
[traceNum
][i
];
542 g_debug("fitArray[traceNum= %u][i= %u]->n = %u", traceNum
, i
, fit
->n
);
545 distances
[i
]= fit
->e
;
546 previousVertex
[i
]= traceNum
;
550 distances
[i
]= INFINITY
;
551 previousVertex
[i
]= UINT_MAX
;
554 visited
[traceNum
]= true;
556 for (j
= 0; j
< traceNb
; j
++)
558 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
561 for (i
= 0; i
< traceNb
- 2; i
++)
567 for (j
= 0; j
< traceNb
; j
++)
569 if (visited
[j
] == false && distances
[j
] < dvMin
)
576 g_debug("v= %u dvMin= %g", v
, dvMin
);
578 if (dvMin
!= INFINITY
)
582 for (j
= 0; j
< traceNb
; j
++)
586 fit
= &fitArray
[v
][j
];
587 if (visited
[j
] == false && fit
->n
> 0 && distances
[v
] + fit
->e
590 distances
[j
]= distances
[v
] + fit
->e
;
591 previousVertex
[j
]= v
;
600 for (j
= 0; j
< traceNb
; j
++)
602 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
611 * Cummulate the distances between a reference node and the other nodes
612 * reachable from it in a graph.
615 * distances: array of shortest path distances, with UINT_MAX for
617 * traceNb: number of nodes = number of traces
619 static double sumDistances(const double* const distances
, const unsigned int traceNb
)
625 for (i
= 0; i
< traceNb
; i
++)
627 if (distances
[i
] != INFINITY
)
629 result
+= distances
[i
];
638 * Cummulate the time correction factors between two nodes accross a graph
640 * With traceNum i, reference node r:
641 * tr= (1 + Xri) * ti + D0ri
642 * = drift * ti + offset
645 * fitArray: array with the regression parameters
646 * previousVertex: previous vertex from a node i on the way to the source,
647 * UINT_MAX if i is not on the way or is the source,
648 * preallocated to the number of nodes
649 * traceNum: end node, the reference depends on previousVertex
650 * drift: drift factor
651 * offset: offset factor
653 static void reduceFactors(Fit
* const* const fitArray
, const unsigned int* const
654 previousVertex
, const unsigned int traceNum
, double* const drift
, double*
655 const offset
, double* const stDev
)
657 if (previousVertex
[traceNum
] == UINT_MAX
)
666 double cummDrift
, cummOffset
, cummStDev
;
669 pv
= previousVertex
[traceNum
];
671 fit
= &fitArray
[pv
][traceNum
];
672 reduceFactors(fitArray
, previousVertex
, pv
, &cummDrift
, &cummOffset
,
675 *drift
= cummDrift
* (1 + fit
->x
);
676 *offset
= cummDrift
* fit
->d0
+ cummOffset
;
677 *stDev
= fit
->x
* cummStDev
+ fit
->e
;
683 * A GFunc for g_queue_foreach()
686 * data Graph*, graph to destroy
689 static void gfGraphDestroy(gpointer data
, gpointer user_data
)
693 graph
= (Graph
*) data
;
695 free(graph
->previousVertex
);
701 * A GCompareFunc for g_queue_find_custom()
705 * b: unsigned int* traceNum
708 * 0 if graph contains traceNum
710 static gint
gcfGraphTraceCompare(gconstpointer a
, gconstpointer b
)
713 unsigned int traceNum
;
716 traceNum
= *(unsigned int *) b
;
718 if (graph
->previousVertex
[traceNum
] != UINT_MAX
)
722 else if (graph
->reference
== traceNum
)
734 * Write the analysis-specific graph lines in the gnuplot script.
737 * syncState: container for synchronization data
738 * i: first trace number, on the x axis
739 * j: second trace number, garanteed to be larger than i
741 void writeAnalysisGraphsPlotsLinReg(SyncState
* const syncState
, const unsigned
742 int i
, const unsigned int j
)
744 AnalysisDataLinReg
* analysisData
;
747 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
748 fit
= &analysisData
->fitArray
[j
][i
];
750 fprintf(syncState
->graphsStream
,
752 "title \"Linreg conversion\" with lines "
753 "linecolor rgb \"gray60\" linetype 1, \\\n",
754 fit
->d0
, 1. + fit
->x
);