projects / lttv.git / blob
? search:


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