projects / lttv.git / blob
? search:


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