projects / lttv.git / blob
? search:


50bb7ab5d6dba2654d0ba5a73596b7bf9b96e2db
[lttv.git] / lttv / lttv / sync / event_analysis_chull.c
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 #define _ISOC99_SOURCE
19
20 #ifdef HAVE_CONFIG_H
21 #include <config.h>
22 #endif
23
24 #include <errno.h>
25 #include <math.h>
26 #include <float.h>
27 #include <stdlib.h>
28 #include <stdio.h>
29 #include <unistd.h>
30
31 #include "sync_chain.h"
32
33 #include "event_analysis_chull.h"
34
35
36 #ifndef g_info
37 #define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format)
38 #endif
39
40
41 typedef enum
42 {
43 LOWER,
44 UPPER
45 } HullType;
46
47
48 typedef enum
49 {
50 MINIMUM,
51 MAXIMUM
52 } LineType;
53
54
55 // Functions common to all analysis modules
56 static void initAnalysisCHull(SyncState* const syncState);
57 static void destroyAnalysisCHull(SyncState* const syncState);
58
59 static void analyzeMessageCHull(SyncState* const syncState, Message* const
60 message);
61 static GArray* finalizeAnalysisCHull(SyncState* const syncState);
62 static void printAnalysisStatsCHull(SyncState* const syncState);
63 static void writeAnalysisGraphsPlotsCHull(SyncState* const syncState, const
64 unsigned int i, const unsigned int j);
65
66 // Functions specific to this module
67 static void registerAnalysisCHull() __attribute__((constructor (101)));
68
69 static void openGraphFiles(SyncState* const syncState);
70 static void closeGraphFiles(SyncState* const syncState);
71 static void writeGraphFiles(SyncState* const syncState);
72 static void gfDumpHullToFile(gpointer data, gpointer userData);
73
74 static void grahamScan(GQueue* const hull, Point* const newPoint, const
75 HullType type);
76 static int jointCmp(const Point* const p1, const Point* const p2, const Point*
77 const p3) __attribute__((pure));
78 static double crossProductK(const Point const* p1, const Point const* p2,
79 const Point const* p3, const Point const* p4) __attribute__((pure));
80 static Factors* calculateFactorsExact(GQueue* const cu, GQueue* const cl, const
81 LineType lineType) __attribute__((pure));
82 static void calculateFactorsFallback(GQueue* const cr, GQueue* const cs,
83 FactorsCHull* const result);
84 static double slope(const Point* const p1, const Point* const p2)
85 __attribute__((pure));
86 static double intercept(const Point* const p1, const Point* const p2)
87 __attribute__((pure));
88 static GArray* reduceFactors(SyncState* const syncState, FactorsCHull**
89 allFactors);
90 static double verticalDistance(Point* p1, Point* p2, Point* const point)
91 __attribute__((pure));
92 static void floydWarshall(SyncState* const syncState, FactorsCHull** const
93 allFactors, double*** const distances, unsigned int*** const
94 predecessors);
95 static void getFactors(FactorsCHull** const allFactors, unsigned int** const
96 predecessors, unsigned int* const references, const unsigned int traceNum,
97 Factors* const factors);
98
99 static void gfPointDestroy(gpointer data, gpointer userData);
100
101
102 static AnalysisModule analysisModuleCHull= {
103 .name= "chull",
104 .initAnalysis= &initAnalysisCHull,
105 .destroyAnalysis= &destroyAnalysisCHull,
106 .analyzeMessage= &analyzeMessageCHull,
107 .finalizeAnalysis= &finalizeAnalysisCHull,
108 .printAnalysisStats= &printAnalysisStatsCHull,
109 .graphFunctions= {
110 .writeTraceTracePlots= &writeAnalysisGraphsPlotsCHull,
111 }
112 };
113
114 const char* const approxNames[]= {
115 [EXACT]= "Exact",
116 [MIDDLE]= "Middle",
117 [FALLBACK]= "Fallback",
118 [INCOMPLETE]= "Incomplete",
119 [ABSENT]= "Absent",
120 [SCREWED]= "Screwed",
121 };
122
123 /*
124 * Analysis module registering function
125 */
126 static void registerAnalysisCHull()
127 {
128 g_queue_push_tail(&analysisModules, &analysisModuleCHull);
129 }
130
131
132 /*
133 * Analysis init function
134 *
135 * This function is called at the beginning of a synchronization run for a set
136 * of traces.
137 *
138 * Allocate some of the analysis specific data structures
139 *
140 * Args:
141 * syncState container for synchronization data.
142 * This function allocates or initializes these analysisData
143 * members:
144 * hullArray
145 * dropped
146 */
147 static void initAnalysisCHull(SyncState* const syncState)
148 {
149 unsigned int i, j;
150 AnalysisDataCHull* analysisData;
151
152 analysisData= malloc(sizeof(AnalysisDataCHull));
153 syncState->analysisData= analysisData;
154
155 analysisData->hullArray= malloc(syncState->traceNb * sizeof(GQueue**));
156 for (i= 0; i < syncState->traceNb; i++)
157 {
158 analysisData->hullArray[i]= malloc(syncState->traceNb * sizeof(GQueue*));
159
160 for (j= 0; j < syncState->traceNb; j++)
161 {
162 analysisData->hullArray[i][j]= g_queue_new();
163 }
164 }
165
166 if (syncState->stats)
167 {
168 analysisData->stats= malloc(sizeof(AnalysisStatsCHull));
169 analysisData->stats->dropped= 0;
170 analysisData->stats->allFactors= NULL;
171 }
172
173 if (syncState->graphsStream)
174 {
175 analysisData->graphsData= malloc(sizeof(AnalysisGraphsDataCHull));
176 openGraphFiles(syncState);
177 analysisData->graphsData->allFactors= NULL;
178 }
179 }
180
181
182 /*
183 * Create and open files used to store convex hull points to genereate
184 * graphs. Allocate and populate array to store file pointers.
185 *
186 * Args:
187 * syncState: container for synchronization data
188 */
189 static void openGraphFiles(SyncState* const syncState)
190 {
191 unsigned int i, j;
192 int retval;
193 char* cwd;
194 char name[31];
195 AnalysisDataCHull* analysisData;
196
197 analysisData= (AnalysisDataCHull*) syncState->analysisData;
198
199 cwd= changeToGraphDir(syncState->graphsDir);
200
201 analysisData->graphsData->hullPoints= malloc(syncState->traceNb *
202 sizeof(FILE**));
203 for (i= 0; i < syncState->traceNb; i++)
204 {
205 analysisData->graphsData->hullPoints[i]= malloc(syncState->traceNb *
206 sizeof(FILE*));
207 for (j= 0; j < syncState->traceNb; j++)
208 {
209 if (i != j)
210 {
211 retval= snprintf(name, sizeof(name),
212 "analysis_chull-%03u_to_%03u.data", j, i);
213 if (retval > sizeof(name) - 1)
214 {
215 name[sizeof(name) - 1]= '\0';
216 }
217 if ((analysisData->graphsData->hullPoints[i][j]= fopen(name, "w")) ==
218 NULL)
219 {
220 g_error(strerror(errno));
221 }
222 }
223 }
224 }
225
226 retval= chdir(cwd);
227 if (retval == -1)
228 {
229 g_error(strerror(errno));
230 }
231 free(cwd);
232 }
233
234
235 /*
236 * Write hull points to files to generate graphs.
237 *
238 * Args:
239 * syncState: container for synchronization data
240 */
241 static void writeGraphFiles(SyncState* const syncState)
242 {
243 unsigned int i, j;
244 AnalysisDataCHull* analysisData;
245
246 analysisData= (AnalysisDataCHull*) syncState->analysisData;
247
248 for (i= 0; i < syncState->traceNb; i++)
249 {
250 for (j= 0; j < syncState->traceNb; j++)
251 {
252 if (i != j)
253 {
254 g_queue_foreach(analysisData->hullArray[i][j],
255 &gfDumpHullToFile,
256 analysisData->graphsData->hullPoints[i][j]);
257 }
258 }
259 }
260 }
261
262
263 /*
264 * A GFunc for g_queue_foreach. Write a hull point to a file used to generate
265 * graphs
266 *
267 * Args:
268 * data: Point*, point to write to the file
269 * userData: FILE*, file pointer where to write the point
270 */
271 static void gfDumpHullToFile(gpointer data, gpointer userData)
272 {
273 Point* point;
274
275 point= (Point*) data;
276 fprintf((FILE*) userData, "%20llu %20llu\n", point->x, point->y);
277 }
278
279
280 /*
281 * Close files used to store convex hull points to generate graphs.
282 * Deallocate array to store file pointers.
283 *
284 * Args:
285 * syncState: container for synchronization data
286 */
287 static void closeGraphFiles(SyncState* const syncState)
288 {
289 unsigned int i, j;
290 AnalysisDataCHull* analysisData;
291 int retval;
292
293 analysisData= (AnalysisDataCHull*) syncState->analysisData;
294
295 if (analysisData->graphsData->hullPoints == NULL)
296 {
297 return;
298 }
299
300 for (i= 0; i < syncState->traceNb; i++)
301 {
302 for (j= 0; j < syncState->traceNb; j++)
303 {
304 if (i != j)
305 {
306 retval= fclose(analysisData->graphsData->hullPoints[i][j]);
307 if (retval != 0)
308 {
309 g_error(strerror(errno));
310 }
311 }
312 }
313 free(analysisData->graphsData->hullPoints[i]);
314 }
315 free(analysisData->graphsData->hullPoints);
316 analysisData->graphsData->hullPoints= NULL;
317 }
318
319
320 /*
321 * Analysis destroy function
322 *
323 * Free the analysis specific data structures
324 *
325 * Args:
326 * syncState container for synchronization data.
327 * This function deallocates these analysisData members:
328 * hullArray
329 * stDev
330 */
331 static void destroyAnalysisCHull(SyncState* const syncState)
332 {
333 unsigned int i, j;
334 AnalysisDataCHull* analysisData;
335
336 analysisData= (AnalysisDataCHull*) syncState->analysisData;
337
338 if (analysisData == NULL)
339 {
340 return;
341 }
342
343 for (i= 0; i < syncState->traceNb; i++)
344 {
345 for (j= 0; j < syncState->traceNb; j++)
346 {
347 g_queue_foreach(analysisData->hullArray[i][j], gfPointDestroy, NULL);
348 }
349 free(analysisData->hullArray[i]);
350 }
351 free(analysisData->hullArray);
352
353 if (syncState->stats)
354 {
355 if (analysisData->stats->allFactors != NULL)
356 {
357 freeAllFactors(syncState->traceNb, analysisData->stats->allFactors);
358 }
359
360 free(analysisData->stats);
361 }
362
363 if (syncState->graphsStream)
364 {
365 if (analysisData->graphsData->hullPoints != NULL)
366 {
367 closeGraphFiles(syncState);
368 }
369
370 if (!syncState->stats && analysisData->graphsData->allFactors != NULL)
371 {
372 freeAllFactors(syncState->traceNb, analysisData->graphsData->allFactors);
373 }
374
375 free(analysisData->graphsData);
376 }
377
378 free(syncState->analysisData);
379 syncState->analysisData= NULL;
380 }
381
382
383 /*
384 * Perform analysis on an event pair.
385 *
386 * Args:
387 * syncState container for synchronization data
388 * message structure containing the events
389 */
390 static void analyzeMessageCHull(SyncState* const syncState, Message* const message)
391 {
392 AnalysisDataCHull* analysisData;
393 Point* newPoint;
394 HullType hullType;
395 GQueue* hull;
396
397 analysisData= (AnalysisDataCHull*) syncState->analysisData;
398
399 newPoint= malloc(sizeof(Point));
400 if (message->inE->traceNum < message->outE->traceNum)
401 {
402 // CA is inE->traceNum
403 newPoint->x= message->inE->cpuTime;
404 newPoint->y= message->outE->cpuTime;
405 hullType= UPPER;
406 g_debug("Reception point hullArray[%lu][%lu] x= inE->time= %llu y= outE->time= %llu",
407 message->inE->traceNum, message->outE->traceNum, newPoint->x,
408 newPoint->y);
409 }
410 else
411 {
412 // CA is outE->traceNum
413 newPoint->x= message->outE->cpuTime;
414 newPoint->y= message->inE->cpuTime;
415 hullType= LOWER;
416 g_debug("Send point hullArray[%lu][%lu] x= inE->time= %llu y= outE->time= %llu",
417 message->inE->traceNum, message->outE->traceNum, newPoint->x,
418 newPoint->y);
419 }
420
421 hull=
422 analysisData->hullArray[message->inE->traceNum][message->outE->traceNum];
423
424 if (hull->length >= 1 && newPoint->x < ((Point*)
425 g_queue_peek_tail(hull))->x)
426 {
427 if (syncState->stats)
428 {
429 analysisData->stats->dropped++;
430 }
431
432 free(newPoint);
433 }
434 else
435 {
436 grahamScan(hull, newPoint, hullType);
437 }
438 }
439
440
441 /*
442 * Construct one half of a convex hull from abscissa-sorted points
443 *
444 * Args:
445 * hull: the points already in the hull
446 * newPoint: a new point to consider
447 * type: which half of the hull to construct
448 */
449 static void grahamScan(GQueue* const hull, Point* const newPoint, const
450 HullType type)
451 {
452 int inversionFactor;
453
454 g_debug("grahamScan(hull (length: %u), newPoint, %s)", hull->length, type
455 == LOWER ? "LOWER" : "UPPER");
456
457 if (type == LOWER)
458 {
459 inversionFactor= 1;
460 }
461 else
462 {
463 inversionFactor= -1;
464 }
465
466 if (hull->length >= 2)
467 {
468 g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d",
469 hull->length - 2,
470 hull->length - 1,
471 jointCmp(g_queue_peek_nth(hull, hull->length - 2),
472 g_queue_peek_tail(hull), newPoint),
473 inversionFactor,
474 jointCmp(g_queue_peek_nth(hull, hull->length - 2),
475 g_queue_peek_tail(hull), newPoint) * inversionFactor);
476 }
477 while (hull->length >= 2 && jointCmp(g_queue_peek_nth(hull, hull->length -
478 2), g_queue_peek_tail(hull), newPoint) * inversionFactor <= 0)
479 {
480 g_debug("Removing hull[%u]", hull->length);
481 free((Point*) g_queue_pop_tail(hull));
482
483 if (hull->length >= 2)
484 {
485 g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d",
486 hull->length - 2,
487 hull->length - 1,
488 jointCmp(g_queue_peek_nth(hull, hull->length - 2),
489 g_queue_peek_tail(hull), newPoint),
490 inversionFactor,
491 jointCmp(g_queue_peek_nth(hull, hull->length - 2),
492 g_queue_peek_tail(hull), newPoint) * inversionFactor);
493 }
494 }
495 g_queue_push_tail(hull, newPoint);
496 }
497
498
499 /*
500 * Finalize the factor calculations
501 *
502 * Args:
503 * syncState container for synchronization data.
504 *
505 * Returns:
506 * Factors[traceNb] synchronization factors for each trace
507 */
508 static GArray* finalizeAnalysisCHull(SyncState* const syncState)
509 {
510 AnalysisDataCHull* analysisData;
511 GArray* factors;
512 FactorsCHull** allFactors;
513
514 analysisData= (AnalysisDataCHull*) syncState->analysisData;
515
516 if (syncState->graphsStream && analysisData->graphsData->hullPoints != NULL)
517 {
518 writeGraphFiles(syncState);
519 closeGraphFiles(syncState);
520 }
521
522 allFactors= calculateAllFactors(syncState);
523
524 factors= reduceFactors(syncState, allFactors);
525
526 if (syncState->stats || syncState->graphsStream)
527 {
528 if (syncState->stats)
529 {
530 analysisData->stats->allFactors= allFactors;
531 }
532
533 if (syncState->graphsStream)
534 {
535 analysisData->graphsData->allFactors= allFactors;
536 }
537 }
538 else
539 {
540 freeAllFactors(syncState->traceNb, allFactors);
541 }
542
543 return factors;
544 }
545
546
547 /*
548 * Print statistics related to analysis. Must be called after
549 * finalizeAnalysis.
550 *
551 * Args:
552 * syncState container for synchronization data.
553 */
554 static void printAnalysisStatsCHull(SyncState* const syncState)
555 {
556 AnalysisDataCHull* analysisData;
557 unsigned int i, j;
558
559 if (!syncState->stats)
560 {
561 return;
562 }
563
564 analysisData= (AnalysisDataCHull*) syncState->analysisData;
565
566 printf("Convex hull analysis stats:\n");
567 printf("\tout of order packets dropped from analysis: %u\n",
568 analysisData->stats->dropped);
569
570 printf("\tNumber of points in convex hulls:\n");
571
572 for (i= 0; i < syncState->traceNb; i++)
573 {
574 for (j= i + 1; j < syncState->traceNb; j++)
575 {
576 printf("\t\t%3d - %-3d: lower half-hull %-5u upper half-hull %-5u\n",
577 i, j, analysisData->hullArray[j][i]->length,
578 analysisData->hullArray[i][j]->length);
579 }
580 }
581
582 printf("\tIndividual synchronization factors:\n");
583
584 for (i= 0; i < syncState->traceNb; i++)
585 {
586 for (j= i + 1; j < syncState->traceNb; j++)
587 {
588 FactorsCHull* factorsCHull;
589
590 factorsCHull= &analysisData->stats->allFactors[j][i];
591 printf("\t\t%3d - %-3d: ", i, j);
592
593 if (factorsCHull->type == EXACT)
594 {
595 printf("Exact a0= % 7g a1= 1 %c %7g\n",
596 factorsCHull->approx->offset,
597 factorsCHull->approx->drift < 0. ? '-' : '+',
598 fabs(factorsCHull->approx->drift));
599 }
600 else if (factorsCHull->type == MIDDLE)
601 {
602 printf("Middle a0= % 7g a1= 1 %c %7g accuracy %7g\n",
603 factorsCHull->approx->offset, factorsCHull->approx->drift
604 - 1. < 0. ? '-' : '+', fabs(factorsCHull->approx->drift -
605 1.), factorsCHull->accuracy);
606 printf("\t\t a0: % 7g to % 7g (delta= %7g)\n",
607 factorsCHull->max->offset, factorsCHull->min->offset,
608 factorsCHull->min->offset - factorsCHull->max->offset);
609 printf("\t\t a1: 1 %+7g to %+7g (delta= %7g)\n",
610 factorsCHull->min->drift - 1., factorsCHull->max->drift -
611 1., factorsCHull->max->drift - factorsCHull->min->drift);
612 }
613 else if (factorsCHull->type == FALLBACK)
614 {
615 printf("Fallback a0= % 7g a1= 1 %c %7g error= %7g\n",
616 factorsCHull->approx->offset, factorsCHull->approx->drift
617 - 1. < 0. ? '-' : '+', fabs(factorsCHull->approx->drift -
618 1.), factorsCHull->accuracy);
619 }
620 else if (factorsCHull->type == INCOMPLETE)
621 {
622 printf("Incomplete\n");
623
624 if (factorsCHull->min->drift != -INFINITY)
625 {
626 printf("\t\t min: a0: % 7g a1: 1 %c %7g\n",
627 factorsCHull->min->offset, factorsCHull->min->drift -
628 1. < 0 ? '-' : '+', fabs(factorsCHull->min->drift -
629 1.));
630 }
631 if (factorsCHull->max->drift != INFINITY)
632 {
633 printf("\t\t max: a0: % 7g a1: 1 %c %7g\n",
634 factorsCHull->max->offset, factorsCHull->max->drift -
635 1. < 0 ? '-' : '+', fabs(factorsCHull->max->drift -
636 1.));
637 }
638 }
639 else if (factorsCHull->type == SCREWED)
640 {
641 printf("Screwed\n");
642
643 if (factorsCHull->min != NULL && factorsCHull->min->drift != -INFINITY)
644 {
645 printf("\t\t min: a0: % 7g a1: 1 %c %7g\n",
646 factorsCHull->min->offset, factorsCHull->min->drift -
647 1. < 0 ? '-' : '+', fabs(factorsCHull->min->drift -
648 1.));
649 }
650 if (factorsCHull->max != NULL && factorsCHull->max->drift != INFINITY)
651 {
652 printf("\t\t max: a0: % 7g a1: 1 %c %7g\n",
653 factorsCHull->max->offset, factorsCHull->max->drift -
654 1. < 0 ? '-' : '+', fabs(factorsCHull->max->drift -
655 1.));
656 }
657 }
658 else if (factorsCHull->type == ABSENT)
659 {
660 printf("Absent\n");
661 }
662 else
663 {
664 g_assert_not_reached();
665 }
666 }
667 }
668 }
669
670
671 /*
672 * A GFunc for g_queue_foreach()
673 *
674 * Args:
675 * data Point*, point to destroy
676 * user_data NULL
677 */
678 static void gfPointDestroy(gpointer data, gpointer userData)
679 {
680 Point* point;
681
682 point= (Point*) data;
683 free(point);
684 }
685
686
687 /*
688 * Find out if a sequence of three points constitutes a "left turn" or a
689 * "right turn".
690 *
691 * Args:
692 * p1, p2, p3: The three points.
693 *
694 * Returns:
695 * < 0 right turn
696 * 0 colinear (unlikely result since this uses floating point
697 * arithmetic)
698 * > 0 left turn
699 */
700 static int jointCmp(const Point const* p1, const Point const* p2, const
701 Point const* p3)
702 {
703 double result;
704 const double fuzzFactor= 0.;
705
706 result= crossProductK(p1, p2, p1, p3);
707 g_debug("crossProductK(p1= (%llu, %llu), p2= (%llu, %llu), p1= (%llu, %llu), p3= (%llu, %llu))= %g",
708 p1->x, p1->y, p2->x, p2->y, p1->x, p1->y, p3->x, p3->y, result);
709 if (result < fuzzFactor)
710 {
711 return -1;
712 }
713 else if (result > fuzzFactor)
714 {
715 return 1;
716 }
717 else
718 {
719 return 0;
720 }
721 }
722
723
724 /*
725 * Calculate the k component of the cross product of two vectors.
726 *
727 * Args:
728 * p1, p2: start and end points of the first vector
729 * p3, p4: start and end points of the second vector
730 *
731 * Returns:
732 * the k component of the cross product when considering the two vectors to
733 * be in the i-j plane. The direction (sign) of the result can be useful to
734 * determine the relative orientation of the two vectors.
735 */
736 static double crossProductK(const Point const* p1, const Point const* p2,
737 const Point const* p3, const Point const* p4)
738 {
739 return ((double) p2->x - p1->x) * ((double) p4->y - p3->y) - ((double)
740 p2->y - p1->y) * ((double) p4->x - p3->x);
741 }
742
743
744 /*
745 * Free a container of FactorsCHull
746 *
747 * Args:
748 * traceNb: number of traces
749 * allFactors: container of FactorsCHull
750 */
751 void freeAllFactors(const unsigned int traceNb, FactorsCHull** const
752 allFactors)
753 {
754 unsigned int i, j;
755
756 for (i= 0; i < traceNb; i++)
757 {
758 for (j= 0; j <= i; j++)
759 {
760 destroyFactorsCHull(&allFactors[i][j]);
761 }
762 free(allFactors[i]);
763 }
764 free(allFactors);
765 }
766
767
768 /*
769 * Free a FactorsCHull
770 *
771 * Args:
772 * factorsCHull: container of Factors
773 */
774 void destroyFactorsCHull(FactorsCHull* factorsCHull)
775 {
776 if (factorsCHull->type == MIDDLE || factorsCHull->type ==
777 INCOMPLETE || factorsCHull->type == ABSENT)
778 {
779 free(factorsCHull->min);
780 free(factorsCHull->max);
781 }
782 else if (factorsCHull->type == SCREWED)
783 {
784 if (factorsCHull->min != NULL)
785 {
786 free(factorsCHull->min);
787 }
788 if (factorsCHull->max != NULL)
789 {
790 free(factorsCHull->max);
791 }
792 }
793
794 if (factorsCHull->type == EXACT || factorsCHull->type == MIDDLE ||
795 factorsCHull->type == FALLBACK)
796 {
797 free(factorsCHull->approx);
798 }
799 }
800
801
802 /*
803 * Analyze the convex hulls to determine the synchronization factors between
804 * each pair of trace.
805 *
806 * Args:
807 * syncState container for synchronization data.
808 *
809 * Returns:
810 * FactorsCHull*[TraceNum][TraceNum] array. See the documentation for the
811 * member allFactors of AnalysisStatsCHull.
812 */
813 FactorsCHull** calculateAllFactors(SyncState* const syncState)
814 {
815 unsigned int traceNumA, traceNumB;
816 FactorsCHull** allFactors;
817 AnalysisDataCHull* analysisData;
818
819 analysisData= (AnalysisDataCHull*) syncState->analysisData;
820
821 // Allocate allFactors and calculate min and max
822 allFactors= malloc(syncState->traceNb * sizeof(FactorsCHull*));
823 for (traceNumA= 0; traceNumA < syncState->traceNb; traceNumA++)
824 {
825 allFactors[traceNumA]= malloc((traceNumA + 1) * sizeof(FactorsCHull));
826
827 allFactors[traceNumA][traceNumA].type= EXACT;
828 allFactors[traceNumA][traceNumA].approx= malloc(sizeof(Factors));
829 allFactors[traceNumA][traceNumA].approx->drift= 1.;
830 allFactors[traceNumA][traceNumA].approx->offset= 0.;
831
832 for (traceNumB= 0; traceNumB < traceNumA; traceNumB++)
833 {
834 unsigned int i;
835 GQueue* cs, * cr;
836 const struct
837 {
838 LineType lineType;
839 size_t factorsOffset;
840 } loopValues[]= {
841 {MINIMUM, offsetof(FactorsCHull, min)},
842 {MAXIMUM, offsetof(FactorsCHull, max)}
843 };
844
845 cr= analysisData->hullArray[traceNumB][traceNumA];
846 cs= analysisData->hullArray[traceNumA][traceNumB];
847
848 for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
849 {
850 g_debug("allFactors[%u][%u].%s = calculateFactorsExact(cr= hullArray[%u][%u], cs= hullArray[%u][%u], %s)",
851 traceNumA, traceNumB, loopValues[i].factorsOffset ==
852 offsetof(FactorsCHull, min) ? "min" : "max", traceNumB,
853 traceNumA, traceNumA, traceNumB, loopValues[i].lineType ==
854 MINIMUM ? "MINIMUM" : "MAXIMUM");
855 *((Factors**) ((void*) &allFactors[traceNumA][traceNumB] +
856 loopValues[i].factorsOffset))=
857 calculateFactorsExact(cr, cs, loopValues[i].lineType);
858 }
859 }
860 }
861
862 // Calculate approx when possible
863 for (traceNumA= 0; traceNumA < syncState->traceNb; traceNumA++)
864 {
865 for (traceNumB= 0; traceNumB < traceNumA; traceNumB++)
866 {
867 FactorsCHull* factorsCHull;
868
869 factorsCHull= &allFactors[traceNumA][traceNumB];
870 if (factorsCHull->min == NULL && factorsCHull->max == NULL)
871 {
872 factorsCHull->type= FALLBACK;
873 calculateFactorsFallback(analysisData->hullArray[traceNumB][traceNumA],
874 analysisData->hullArray[traceNumA][traceNumB],
875 &allFactors[traceNumA][traceNumB]);
876 }
877 else if (factorsCHull->min != NULL && factorsCHull->max != NULL)
878 {
879 if (factorsCHull->min->drift != -INFINITY &&
880 factorsCHull->max->drift != INFINITY)
881 {
882 factorsCHull->type= MIDDLE;
883 calculateFactorsMiddle(factorsCHull);
884 }
885 else if (factorsCHull->min->drift != -INFINITY ||
886 factorsCHull->max->drift != INFINITY)
887 {
888 factorsCHull->type= INCOMPLETE;
889 }
890 else
891 {
892 factorsCHull->type= ABSENT;
893 }
894 }
895 else
896 {
897 //g_assert_not_reached();
898 factorsCHull->type= SCREWED;
899 }
900 }
901 }
902
903 return allFactors;
904 }
905
906
907 /* Calculate approximative factors based on minimum and maximum limits. The
908 * best approximation to make is the interior bissector of the angle formed by
909 * the minimum and maximum lines.
910 *
911 * The formulae used come from [Haddad, Yoram: Performance dans les systèmes
912 * répartis: des outils pour les mesures, Université de Paris-Sud, Centre
913 * d'Orsay, September 1988] Section 6.1 p.44
914 *
915 * The reasoning for choosing this estimator comes from [Duda, A., Harrus, G.,
916 * Haddad, Y., and Bernard, G.: Estimating global time in distributed systems,
917 * Proc. 7th Int. Conf. on Distributed Computing Systems, Berlin, volume 18,
918 * 1987] p.303
919 *
920 * Args:
921 * factors: contains the min and max limits, used to store the result
922 */
923 void calculateFactorsMiddle(FactorsCHull* const factors)
924 {
925 double amin, amax, bmin, bmax, bhat;
926
927 amin= factors->max->offset;
928 amax= factors->min->offset;
929 bmin= factors->min->drift;
930 bmax= factors->max->drift;
931
932 g_assert_cmpfloat(bmax, >, bmin);
933
934 factors->approx= malloc(sizeof(Factors));
935 bhat= (bmax * bmin - 1. + sqrt(1. + pow(bmax, 2.) * pow(bmin, 2.) +
936 pow(bmax, 2.) + pow(bmin, 2.))) / (bmax + bmin);
937 factors->approx->offset= amax - (amax - amin) / 2. * (pow(bhat, 2.) + 1.)
938 / (1. + bhat * bmax);
939 factors->approx->drift= bhat;
940 factors->accuracy= bmax - bmin;
941 }
942
943
944 /*
945 * Analyze the convex hulls to determine the minimum or maximum
946 * synchronization factors between one pair of trace.
947 *
948 * This implements and improves upon the algorithm in [Haddad, Yoram:
949 * Performance dans les systèmes répartis: des outils pour les mesures,
950 * Université de Paris-Sud, Centre d'Orsay, September 1988] Section 6.2 p.47
951 *
952 * Some degenerate cases are possible:
953 * 1) the result is unbounded. In that case, when searching for the maximum
954 * factors, result->drift= INFINITY; result->offset= -INFINITY. When
955 * searching for the minimum factors, it is the opposite. It is not
956 * possible to improve the situation with this data.
957 * 2) no line can be above the upper hull and below the lower hull. This is
958 * because the hulls intersect each other or are reversed. This means that
959 * an assertion was false. Most probably, the clocks are not linear. It is
960 * possible to repeat the search with another algorithm that will find a
961 * "best effort" approximation. See calculateFactorsApprox().
962 *
963 * Args:
964 * cu: the upper half-convex hull, the line must pass above this
965 * and touch it in one point
966 * cl: the lower half-convex hull, the line must pass below this
967 * and touch it in one point
968 * lineType: search for minimum or maximum factors
969 *
970 * Returns:
971 * If a result is found, a struct Factors is allocated, filed with the
972 * result and returned
973 * NULL otherwise, degenerate case 2 is in effect
974 */
975 static Factors* calculateFactorsExact(GQueue* const cu, GQueue* const cl, const
976 LineType lineType)
977 {
978 GQueue* c1, * c2;
979 unsigned int i1, i2;
980 Point* p1, * p2;
981 double inversionFactor;
982 Factors* result;
983
984 g_debug("calculateFactorsExact(cu= %p, cl= %p, %s)", cu, cl, lineType ==
985 MINIMUM ? "MINIMUM" : "MAXIMUM");
986
987 if (lineType == MINIMUM)
988 {
989 c1= cl;
990 c2= cu;
991 inversionFactor= -1.;
992 }
993 else
994 {
995 c1= cu;
996 c2= cl;
997 inversionFactor= 1.;
998 }
999
1000 i1= 0;
1001 i2= c2->length - 1;
1002
1003 // Check for degenerate case 1
1004 if (c1->length == 0 || c2->length == 0 || ((Point*) g_queue_peek_nth(c1,
1005 i1))->x >= ((Point*) g_queue_peek_nth(c2, i2))->x)
1006 {
1007 result= malloc(sizeof(Factors));
1008 if (lineType == MINIMUM)
1009 {
1010 result->drift= -INFINITY;
1011 result->offset= INFINITY;
1012 }
1013 else
1014 {
1015 result->drift= INFINITY;
1016 result->offset= -INFINITY;
1017 }
1018
1019 return result;
1020 }
1021
1022 do
1023 {
1024 while
1025 (
1026 (int) i2 - 1 > 0
1027 && crossProductK(
1028 g_queue_peek_nth(c1, i1),
1029 g_queue_peek_nth(c2, i2),
1030 g_queue_peek_nth(c1, i1),
1031 g_queue_peek_nth(c2, i2 - 1)) * inversionFactor < 0.
1032 )
1033 {
1034 if (((Point*) g_queue_peek_nth(c1, i1))->x
1035 < ((Point*) g_queue_peek_nth(c2, i2 - 1))->x)
1036 {
1037 i2--;
1038 }
1039 else
1040 {
1041 // Degenerate case 2
1042 return NULL;
1043 }
1044 }
1045 while
1046 (
1047 i1 + 1 < c1->length - 1
1048 && crossProductK(
1049 g_queue_peek_nth(c1, i1),
1050 g_queue_peek_nth(c2, i2),
1051 g_queue_peek_nth(c1, i1 + 1),
1052 g_queue_peek_nth(c2, i2)) * inversionFactor < 0.
1053 )
1054 {
1055 if (((Point*) g_queue_peek_nth(c1, i1 + 1))->x
1056 < ((Point*) g_queue_peek_nth(c2, i2))->x)
1057 {
1058 i1++;
1059 }
1060 else
1061 {
1062 // Degenerate case 2
1063 return NULL;
1064 }
1065 }
1066 } while
1067 (
1068 (int) i2 - 1 > 0
1069 && crossProductK(
1070 g_queue_peek_nth(c1, i1),
1071 g_queue_peek_nth(c2, i2),
1072 g_queue_peek_nth(c1, i1),
1073 g_queue_peek_nth(c2, i2 - 1)) * inversionFactor < 0.
1074 );
1075
1076 p1= g_queue_peek_nth(c1, i1);
1077 p2= g_queue_peek_nth(c2, i2);
1078
1079 g_debug("Resulting points are: c1[i1]: x= %llu y= %llu c2[i2]: x= %llu y= %llu",
1080 p1->x, p1->y, p2->x, p2->y);
1081
1082 result= malloc(sizeof(Factors));
1083 result->drift= slope(p1, p2);
1084 result->offset= intercept(p1, p2);
1085
1086 g_debug("Resulting factors are: drift= %g offset= %g", result->drift, result->offset);
1087
1088 return result;
1089 }
1090
1091
1092 /*
1093 * Analyze the convex hulls to determine approximate synchronization factors
1094 * between one pair of trace when there is no line that can fit in the
1095 * corridor separating them.
1096 *
1097 * This implements the algorithm in [Ashton, P.: Algorithms for Off-line Clock
1098 * Synchronisation, University of Canterbury, December 1995, 26] Section 4.2.2
1099 * p.7
1100 *
1101 * For each point p1 in cr
1102 * For each point p2 in cs
1103 * errorMin= 0
1104 * Calculate the line paramaters
1105 * For each point p3 in each convex hull
1106 * If p3 is on the wrong side of the line
1107 * error+= distance
1108 * If error < errorMin
1109 * Update results
1110 *
1111 * Args:
1112 * cr: the upper half-convex hull
1113 * cs: the lower half-convex hull
1114 * result: a pointer to the pre-allocated struct where the results
1115 * will be stored
1116 */
1117 static void calculateFactorsFallback(GQueue* const cr, GQueue* const cs,
1118 FactorsCHull* const result)
1119 {
1120 unsigned int i, j, k;
1121 double errorMin;
1122 Factors* approx;
1123
1124 errorMin= INFINITY;
1125 approx= malloc(sizeof(Factors));
1126
1127 for (i= 0; i < cs->length; i++)
1128 {
1129 for (j= 0; j < cr->length; j++)
1130 {
1131 double error;
1132 Point p1, p2;
1133
1134 error= 0.;
1135
1136 if (((Point*) g_queue_peek_nth(cs, i))->x < ((Point*)g_queue_peek_nth(cr, j))->x)
1137 {
1138 p1= *(Point*)g_queue_peek_nth(cs, i);
1139 p2= *(Point*)g_queue_peek_nth(cr, j);
1140 }
1141 else
1142 {
1143 p1= *(Point*)g_queue_peek_nth(cr, j);
1144 p2= *(Point*)g_queue_peek_nth(cs, i);
1145 }
1146
1147 // The lower hull should be above the point
1148 for (k= 0; k < cs->length; k++)
1149 {
1150 if (jointCmp(&p1, &p2, g_queue_peek_nth(cs, k)) < 0.)
1151 {
1152 error+= verticalDistance(&p1, &p2, g_queue_peek_nth(cs, k));
1153 }
1154 }
1155
1156 // The upper hull should be below the point
1157 for (k= 0; k < cr->length; k++)
1158 {
1159 if (jointCmp(&p1, &p2, g_queue_peek_nth(cr, k)) > 0.)
1160 {
1161 error+= verticalDistance(&p1, &p2, g_queue_peek_nth(cr, k));
1162 }
1163 }
1164
1165 if (error < errorMin)
1166 {
1167 g_debug("Fallback: i= %u j= %u is a better match (error= %g)", i, j, error);
1168 approx->drift= slope(&p1, &p2);
1169 approx->offset= intercept(&p1, &p2);
1170 errorMin= error;
1171 }
1172 }
1173 }
1174
1175 result->approx= approx;
1176 result->accuracy= errorMin;
1177 }
1178
1179
1180 /*
1181 * Calculate the vertical distance between a line and a point
1182 *
1183 * Args:
1184 * p1, p2: Two points defining the line
1185 * point: a point
1186 *
1187 * Return:
1188 * the vertical distance
1189 */
1190 static double verticalDistance(Point* p1, Point* p2, Point* const point)
1191 {
1192 return fabs(slope(p1, p2) * point->x + intercept(p1, p2) - point->y);
1193 }
1194
1195
1196 /*
1197 * Calculate the slope between two points
1198 *
1199 * Args:
1200 * p1, p2 the two points
1201 *
1202 * Returns:
1203 * the slope
1204 */
1205 static double slope(const Point* const p1, const Point* const p2)
1206 {
1207 return ((double) p2->y - p1->y) / (p2->x - p1->x);
1208 }
1209
1210
1211 /* Calculate the y-intercept of a line that passes by two points
1212 *
1213 * Args:
1214 * p1, p2 the two points
1215 *
1216 * Returns:
1217 * the y-intercept
1218 */
1219 static double intercept(const Point* const p1, const Point* const p2)
1220 {
1221 return ((double) p2->y * p1->x - (double) p1->y * p2->x) / ((double) p1->x - p2->x);
1222 }
1223
1224
1225 /*
1226 * Calculate a resulting offset and drift for each trace.
1227 *
1228 * Traces are assembled in groups. A group is an "island" of nodes/traces that
1229 * exchanged messages. A reference is determined for each group by using a
1230 * shortest path search based on the accuracy of the approximation. This also
1231 * forms a tree of the best way to relate each node's clock to the reference's
1232 * based on the accuracy. Sometimes it may be necessary or advantageous to
1233 * propagate the factors through intermediary clocks. Resulting factors for
1234 * each trace are determined based on this tree.
1235 *
1236 * This part was not the focus of my research. The algorithm used here is
1237 * inexact in some ways:
1238 * 1) The reference used may not actually be the best one to use. This is
1239 * because the accuracy is not corrected based on the drift during the
1240 * shortest path search.
1241 * 2) The min and max factors are not propagated and are no longer valid.
1242 * 3) Approximations of different types (MIDDLE and FALLBACK) are compared
1243 * together. The "accuracy" parameters of these have different meanings and
1244 * are not readily comparable.
1245 *
1246 * Nevertheless, the result is satisfactory. You just can't tell "how much" it
1247 * is.
1248 *
1249 * Two alternative (and subtly different) ways of propagating factors to
1250 * preserve min and max bondaries have been proposed, see:
1251 * [Duda, A., Harrus, G., Haddad, Y., and Bernard, G.: Estimating global time
1252 * in distributed systems, Proc. 7th Int. Conf. on Distributed Computing
1253 * Systems, Berlin, volume 18, 1987] p.304
1254 *
1255 * [Jezequel, J.M., and Jard, C.: Building a global clock for observing
1256 * computations in distributed memory parallel computers, Concurrency:
1257 * Practice and Experience 8(1), volume 8, John Wiley & Sons, Ltd Chichester,
1258 * 1996, 32] Section 5; which is mostly the same as
1259 * [Jezequel, J.M.: Building a global time on parallel machines, Proceedings
1260 * of the 3rd International Workshop on Distributed Algorithms, LNCS, volume
1261 * 392, 136–147, 1989] Section 5
1262 *
1263 * Args:
1264 * syncState: container for synchronization data.
1265 * allFactors: offset and drift between each pair of traces
1266 *
1267 * Returns:
1268 * Factors[traceNb] synchronization factors for each trace
1269 */
1270 static GArray* reduceFactors(SyncState* const syncState, FactorsCHull** const
1271 allFactors)
1272 {
1273 GArray* factors;
1274 double** distances;
1275 unsigned int** predecessors;
1276 double* distanceSums;
1277 unsigned int* references;
1278 unsigned int i, j;
1279
1280 // Solve the all-pairs shortest path problem using the Floyd-Warshall
1281 // algorithm
1282 floydWarshall(syncState, allFactors, &distances, &predecessors);
1283
1284 /* Find the reference for each node
1285 *
1286 * First calculate, for each node, the sum of the distances to each other
1287 * node it can reach.
1288 *
1289 * Then, go through each "island" of traces to find the trace that has the
1290 * lowest distance sum. Assign this trace as the reference to each trace
1291 * of the island.
1292 */
1293 distanceSums= malloc(syncState->traceNb * sizeof(double));
1294 for (i= 0; i < syncState->traceNb; i++)
1295 {
1296 distanceSums[i]= 0.;
1297 for (j= 0; j < syncState->traceNb; j++)
1298 {
1299 distanceSums[i]+= distances[i][j];
1300 }
1301 }
1302
1303 references= malloc(syncState->traceNb * sizeof(unsigned int));
1304 for (i= 0; i < syncState->traceNb; i++)
1305 {
1306 references[i]= UINT_MAX;
1307 }
1308 for (i= 0; i < syncState->traceNb; i++)
1309 {
1310 if (references[i] == UINT_MAX)
1311 {
1312 unsigned int reference;
1313 double distanceSumMin;
1314
1315 // A node is its own reference by default
1316 reference= i;
1317 distanceSumMin= INFINITY;
1318 for (j= 0; j < syncState->traceNb; j++)
1319 {
1320 if (distances[i][j] != INFINITY && distanceSums[j] <
1321 distanceSumMin)
1322 {
1323 reference= j;
1324 distanceSumMin= distanceSums[j];
1325 }
1326 }
1327 for (j= 0; j < syncState->traceNb; j++)
1328 {
1329 if (distances[i][j] != INFINITY)
1330 {
1331 references[j]= reference;
1332 }
1333 }
1334 }
1335 }
1336
1337 for (i= 0; i < syncState->traceNb; i++)
1338 {
1339 free(distances[i]);
1340 }
1341 free(distances);
1342 free(distanceSums);
1343
1344 /* For each trace, calculate the factors based on their corresponding
1345 * tree. The tree is rooted at the reference and the shortest path to each
1346 * other nodes are the branches.
1347 */
1348 factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors),
1349 syncState->traceNb);
1350 g_array_set_size(factors, syncState->traceNb);
1351 for (i= 0; i < syncState->traceNb; i++)
1352 {
1353 getFactors(allFactors, predecessors, references, i, &g_array_index(factors,
1354 Factors, i));
1355 }
1356
1357 for (i= 0; i < syncState->traceNb; i++)
1358 {
1359 free(predecessors[i]);
1360 }
1361 free(predecessors);
1362 free(references);
1363
1364 return factors;
1365 }
1366
1367
1368 /*
1369 * Perform an all-source shortest path search using the Floyd-Warshall
1370 * algorithm.
1371 *
1372 * The algorithm is implemented accoding to the description here:
1373 * http://web.mit.edu/urban_or_book/www/book/chapter6/6.2.2.html
1374 *
1375 * Args:
1376 * syncState: container for synchronization data.
1377 * allFactors: offset and drift between each pair of traces
1378 * distances: resulting matrix of the length of the shortest path between
1379 * two nodes. If there is no path between two nodes, the
1380 * length is INFINITY
1381 * predecessors: resulting matrix of each node's predecessor on the shortest
1382 * path between two nodes
1383 */
1384 static void floydWarshall(SyncState* const syncState, FactorsCHull** const
1385 allFactors, double*** const distances, unsigned int*** const
1386 predecessors)
1387 {
1388 unsigned int i, j, k;
1389
1390 // Setup initial conditions
1391 *distances= malloc(syncState->traceNb * sizeof(double*));
1392 *predecessors= malloc(syncState->traceNb * sizeof(unsigned int*));
1393 for (i= 0; i < syncState->traceNb; i++)
1394 {
1395 (*distances)[i]= malloc(syncState->traceNb * sizeof(double));
1396 for (j= 0; j < syncState->traceNb; j++)
1397 {
1398 if (i == j)
1399 {
1400 g_assert(allFactors[i][j].type == EXACT);
1401
1402 (*distances)[i][j]= 0.;
1403 }
1404 else
1405 {
1406 unsigned int row, col;
1407
1408 if (i > j)
1409 {
1410 row= i;
1411 col= j;
1412 }
1413 else if (i < j)
1414 {
1415 row= j;
1416 col= i;
1417 }
1418
1419 if (allFactors[row][col].type == MIDDLE ||
1420 allFactors[row][col].type == FALLBACK)
1421 {
1422 (*distances)[i][j]= allFactors[row][col].accuracy;
1423 }
1424 else if (allFactors[row][col].type == INCOMPLETE ||
1425 allFactors[row][col].type == SCREWED ||
1426 allFactors[row][col].type == ABSENT)
1427 {
1428 (*distances)[i][j]= INFINITY;
1429 }
1430 else
1431 {
1432 g_assert_not_reached();
1433 }
1434 }
1435 }
1436
1437 (*predecessors)[i]= malloc(syncState->traceNb * sizeof(unsigned int));
1438 for (j= 0; j < syncState->traceNb; j++)
1439 {
1440 if (i != j)
1441 {
1442 (*predecessors)[i][j]= i;
1443 }
1444 else
1445 {
1446 (*predecessors)[i][j]= UINT_MAX;
1447 }
1448 }
1449 }
1450
1451 // Run the iterations
1452 for (k= 0; k < syncState->traceNb; k++)
1453 {
1454 for (i= 0; i < syncState->traceNb; i++)
1455 {
1456 for (j= 0; j < syncState->traceNb; j++)
1457 {
1458 double distanceMin;
1459
1460 distanceMin= MIN((*distances)[i][j], (*distances)[i][k] +
1461 (*distances)[k][j]);
1462
1463 if (distanceMin != (*distances)[i][j])
1464 {
1465 (*predecessors)[i][j]= (*predecessors)[k][j];
1466 }
1467
1468 (*distances)[i][j]= distanceMin;
1469 }
1470 }
1471 }
1472 }
1473
1474
1475 /*
1476 * Cummulate the time correction factors to convert a node's time to its
1477 * reference's time.
1478 * This function recursively calls itself until it reaches the reference node.
1479 *
1480 * Args:
1481 * allFactors: offset and drift between each pair of traces
1482 * predecessors: matrix of each node's predecessor on the shortest
1483 * path between two nodes
1484 * references: reference node for each node
1485 * traceNum: node for which to find the factors
1486 * factors: resulting factors
1487 */
1488 static void getFactors(FactorsCHull** const allFactors, unsigned int** const
1489 predecessors, unsigned int* const references, const unsigned int traceNum,
1490 Factors* const factors)
1491 {
1492 unsigned int reference;
1493
1494 reference= references[traceNum];
1495
1496 if (reference == traceNum)
1497 {
1498 factors->offset= 0.;
1499 factors->drift= 1.;
1500 }
1501 else
1502 {
1503 Factors previousVertexFactors;
1504
1505 getFactors(allFactors, predecessors, references,
1506 predecessors[reference][traceNum], &previousVertexFactors);
1507
1508 // convertir de traceNum à reference
1509
1510 // allFactors convertit de col à row
1511
1512 if (reference > traceNum)
1513 {
1514 factors->offset= previousVertexFactors.drift *
1515 allFactors[reference][traceNum].approx->offset +
1516 previousVertexFactors.offset;
1517 factors->drift= previousVertexFactors.drift *
1518 allFactors[reference][traceNum].approx->drift;
1519 }
1520 else
1521 {
1522 factors->offset= previousVertexFactors.drift * (-1. *
1523 allFactors[traceNum][reference].approx->offset /
1524 allFactors[traceNum][reference].approx->drift) +
1525 previousVertexFactors.offset;
1526 factors->drift= previousVertexFactors.drift * (1. /
1527 allFactors[traceNum][reference].approx->drift);
1528 }
1529 }
1530 }
1531
1532
1533 /*
1534 * Write the analysis-specific graph lines in the gnuplot script.
1535 *
1536 * Args:
1537 * syncState: container for synchronization data
1538 * i: first trace number
1539 * j: second trace number, garanteed to be larger than i
1540 */
1541 void writeAnalysisGraphsPlotsCHull(SyncState* const syncState, const unsigned
1542 int i, const unsigned int j)
1543 {
1544 AnalysisDataCHull* analysisData;
1545 FactorsCHull* factorsCHull;
1546
1547 analysisData= (AnalysisDataCHull*) syncState->analysisData;
1548
1549 fprintf(syncState->graphsStream,
1550 "\t\"analysis_chull-%1$03d_to_%2$03d.data\" "
1551 "title \"Lower half-hull\" with linespoints "
1552 "linecolor rgb \"#015a01\" linetype 4 pointtype 8 pointsize 0.8, \\\n"
1553 "\t\"analysis_chull-%2$03d_to_%1$03d.data\" "
1554 "title \"Upper half-hull\" with linespoints "
1555 "linecolor rgb \"#003366\" linetype 4 pointtype 10 pointsize 0.8, \\\n",
1556 i, j);
1557
1558 factorsCHull= &analysisData->graphsData->allFactors[j][i];
1559 if (factorsCHull->type == EXACT)
1560 {
1561 fprintf(syncState->graphsStream,
1562 "\t%7g + %7g * x "
1563 "title \"Exact conversion\" with lines "
1564 "linecolor rgb \"black\" linetype 1, \\\n",
1565 factorsCHull->approx->offset, factorsCHull->approx->drift);
1566 }
1567 else if (factorsCHull->type == MIDDLE)
1568 {
1569 fprintf(syncState->graphsStream,
1570 "\t%.2f + %.10f * x "
1571 "title \"Min conversion\" with lines "
1572 "linecolor rgb \"black\" linetype 5, \\\n",
1573 factorsCHull->min->offset, factorsCHull->min->drift);
1574 fprintf(syncState->graphsStream,
1575 "\t%.2f + %.10f * x "
1576 "title \"Max conversion\" with lines "
1577 "linecolor rgb \"black\" linetype 8, \\\n",
1578 factorsCHull->max->offset, factorsCHull->max->drift);
1579 fprintf(syncState->graphsStream,
1580 "\t%.2f + %.10f * x "
1581 "title \"Middle conversion\" with lines "
1582 "linecolor rgb \"black\" linetype 1, \\\n",
1583 factorsCHull->approx->offset, factorsCHull->approx->drift);
1584 }
1585 else if (factorsCHull->type == FALLBACK)
1586 {
1587 fprintf(syncState->graphsStream,
1588 "\t%.2f + %.10f * x "
1589 "title \"Fallback conversion\" with lines "
1590 "linecolor rgb \"gray60\" linetype 1, \\\n",
1591 factorsCHull->approx->offset, factorsCHull->approx->drift);
1592 }
1593 else if (factorsCHull->type == INCOMPLETE)
1594 {
1595 if (factorsCHull->min->drift != -INFINITY)
1596 {
1597 fprintf(syncState->graphsStream,
1598 "\t%.2f + %.10f * x "
1599 "title \"Min conversion\" with lines "
1600 "linecolor rgb \"black\" linetype 5, \\\n",
1601 factorsCHull->min->offset, factorsCHull->min->drift);
1602 }
1603
1604 if (factorsCHull->max->drift != INFINITY)
1605 {
1606 fprintf(syncState->graphsStream,
1607 "\t%.2f + %.10f * x "
1608 "title \"Max conversion\" with lines "
1609 "linecolor rgb \"black\" linetype 8, \\\n",
1610 factorsCHull->max->offset, factorsCHull->max->drift);
1611 }
1612 }
1613 else if (factorsCHull->type == SCREWED)
1614 {
1615 if (factorsCHull->min != NULL && factorsCHull->min->drift != -INFINITY)
1616 {
1617 fprintf(syncState->graphsStream,
1618 "\t%.2f + %.10f * x "
1619 "title \"Min conversion\" with lines "
1620 "linecolor rgb \"black\" linetype 5, \\\n",
1621 factorsCHull->min->offset, factorsCHull->min->drift);
1622 }
1623
1624 if (factorsCHull->max != NULL && factorsCHull->max->drift != INFINITY)
1625 {
1626 fprintf(syncState->graphsStream,
1627 "\t%.2f + %.10f * x "
1628 "title \"Max conversion\" with lines "
1629 "linecolor rgb \"black\" linetype 8, \\\n",
1630 factorsCHull->max->offset, factorsCHull->max->drift);
1631 }
1632 }
1633 else if (factorsCHull->type == ABSENT)
1634 {
1635 }
1636 else
1637 {
1638 g_assert_not_reached();
1639 }
1640 }
LTTng 2.x Viewer (LTTV)
This page took 0.060465 seconds and 3 git commands to generate.