projects / lttv.git / blob
? search:


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