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