1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009 Benjamin Poirier <benjamin.poirier@polymtl.ca>
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;
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.
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,
18 #define _ISOC99_SOURCE
33 #include "sync_chain.h"
35 #include "event_analysis_chull.h"
52 // Functions common to all analysis modules
53 static void initAnalysisCHull(SyncState
* const syncState
);
54 static void destroyAnalysisCHull(SyncState
* const syncState
);
56 static void analyzeMessageCHull(SyncState
* const syncState
, Message
* const
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
);
63 // Functions specific to this module
64 static void registerAnalysisCHull() __attribute__((constructor (101)));
66 static void openGraphFiles(SyncState
* const syncState
);
67 static void closeGraphFiles(SyncState
* const syncState
);
68 static void writeGraphFiles(SyncState
* const syncState
);
69 static void gfDumpHullToFile(gpointer data
, gpointer userData
);
71 static void grahamScan(GQueue
* const hull
, Point
* const newPoint
, const
73 static int jointCmp(const Point
* const p1
, const Point
* const p2
, const Point
*
74 const p3
) __attribute__((pure
));
75 static double crossProductK(const Point
const* p1
, const Point
const* p2
,
76 const Point
const* p3
, const Point
const* p4
) __attribute__((pure
));
77 static Factors
* calculateFactorsExact(GQueue
* const cu
, GQueue
* const cl
, const
78 LineType lineType
) __attribute__((pure
));
79 static void calculateFactorsFallback(GQueue
* const cr
, GQueue
* const cs
,
80 FactorsCHull
* const result
);
81 static double slope(const Point
* const p1
, const Point
* const p2
)
82 __attribute__((pure
));
83 static double intercept(const Point
* const p1
, const Point
* const p2
)
84 __attribute__((pure
));
85 static GArray
* reduceFactors(SyncState
* const syncState
, FactorsCHull
**
87 static double verticalDistance(Point
* p1
, Point
* p2
, Point
* const point
)
88 __attribute__((pure
));
89 static void floydWarshall(SyncState
* const syncState
, FactorsCHull
** const
90 allFactors
, double*** const distances
, unsigned int*** const
92 static void getFactors(FactorsCHull
** const allFactors
, unsigned int** const
93 predecessors
, unsigned int* const references
, const unsigned int traceNum
,
94 Factors
* const factors
);
96 static void gfPointDestroy(gpointer data
, gpointer userData
);
99 static AnalysisModule analysisModuleCHull
= {
101 .initAnalysis
= &initAnalysisCHull
,
102 .destroyAnalysis
= &destroyAnalysisCHull
,
103 .analyzeMessage
= &analyzeMessageCHull
,
104 .finalizeAnalysis
= &finalizeAnalysisCHull
,
105 .printAnalysisStats
= &printAnalysisStatsCHull
,
107 .writeTraceTraceForePlots
= &writeAnalysisGraphsPlotsCHull
,
111 const char* const approxNames
[]= {
114 [FALLBACK
]= "Fallback",
115 [INCOMPLETE
]= "Incomplete",
117 [SCREWED
]= "Screwed",
122 * Analysis module registering function
124 static void registerAnalysisCHull()
126 g_queue_push_tail(&analysisModules
, &analysisModuleCHull
);
131 * Analysis init function
133 * This function is called at the beginning of a synchronization run for a set
136 * Allocate some of the analysis specific data structures
139 * syncState container for synchronization data.
140 * This function allocates or initializes these analysisData
145 static void initAnalysisCHull(SyncState
* const syncState
)
148 AnalysisDataCHull
* analysisData
;
150 analysisData
= malloc(sizeof(AnalysisDataCHull
));
151 syncState
->analysisData
= analysisData
;
153 analysisData
->hullArray
= malloc(syncState
->traceNb
* sizeof(GQueue
**));
154 for (i
= 0; i
< syncState
->traceNb
; i
++)
156 analysisData
->hullArray
[i
]= malloc(syncState
->traceNb
* sizeof(GQueue
*));
158 for (j
= 0; j
< syncState
->traceNb
; j
++)
160 analysisData
->hullArray
[i
][j
]= g_queue_new();
164 if (syncState
->stats
)
166 analysisData
->stats
= malloc(sizeof(AnalysisStatsCHull
));
167 analysisData
->stats
->dropped
= 0;
168 analysisData
->stats
->allFactors
= NULL
;
171 if (syncState
->graphsStream
)
173 analysisData
->graphsData
= malloc(sizeof(AnalysisGraphsDataCHull
));
174 openGraphFiles(syncState
);
175 analysisData
->graphsData
->allFactors
= NULL
;
181 * Create and open files used to store convex hull points to genereate
182 * graphs. Allocate and populate array to store file pointers.
185 * syncState: container for synchronization data
187 static void openGraphFiles(SyncState
* const syncState
)
193 AnalysisDataCHull
* analysisData
;
195 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
197 cwd
= changeToGraphsDir(syncState
->graphsDir
);
199 analysisData
->graphsData
->hullPoints
= malloc(syncState
->traceNb
*
201 for (i
= 0; i
< syncState
->traceNb
; i
++)
203 analysisData
->graphsData
->hullPoints
[i
]= malloc(syncState
->traceNb
*
205 for (j
= 0; j
< syncState
->traceNb
; j
++)
209 retval
= snprintf(name
, sizeof(name
),
210 "analysis_chull-%03u_to_%03u.data", j
, i
);
211 if (retval
> sizeof(name
) - 1)
213 name
[sizeof(name
) - 1]= '\0';
215 if ((analysisData
->graphsData
->hullPoints
[i
][j
]= fopen(name
, "w")) ==
218 g_error(strerror(errno
));
227 g_error(strerror(errno
));
234 * Write hull points to files to generate graphs.
237 * syncState: container for synchronization data
239 static void writeGraphFiles(SyncState
* const syncState
)
242 AnalysisDataCHull
* analysisData
;
244 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
246 for (i
= 0; i
< syncState
->traceNb
; i
++)
248 for (j
= 0; j
< syncState
->traceNb
; j
++)
252 g_queue_foreach(analysisData
->hullArray
[i
][j
],
254 analysisData
->graphsData
->hullPoints
[i
][j
]);
262 * A GFunc for g_queue_foreach. Write a hull point to a file used to generate
266 * data: Point*, point to write to the file
267 * userData: FILE*, file pointer where to write the point
269 static void gfDumpHullToFile(gpointer data
, gpointer userData
)
273 point
= (Point
*) data
;
274 fprintf((FILE*) userData
, "%20" PRIu64
" %20" PRIu64
"\n", point
->x
, point
->y
);
279 * Close files used to store convex hull points to generate graphs.
280 * Deallocate array to store file pointers.
283 * syncState: container for synchronization data
285 static void closeGraphFiles(SyncState
* const syncState
)
288 AnalysisDataCHull
* analysisData
;
291 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
293 if (analysisData
->graphsData
->hullPoints
== NULL
)
298 for (i
= 0; i
< syncState
->traceNb
; i
++)
300 for (j
= 0; j
< syncState
->traceNb
; j
++)
304 retval
= fclose(analysisData
->graphsData
->hullPoints
[i
][j
]);
307 g_error(strerror(errno
));
311 free(analysisData
->graphsData
->hullPoints
[i
]);
313 free(analysisData
->graphsData
->hullPoints
);
314 analysisData
->graphsData
->hullPoints
= NULL
;
319 * Analysis destroy function
321 * Free the analysis specific data structures
324 * syncState container for synchronization data.
325 * This function deallocates these analysisData members:
329 static void destroyAnalysisCHull(SyncState
* const syncState
)
332 AnalysisDataCHull
* analysisData
;
334 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
336 if (analysisData
== NULL
)
341 for (i
= 0; i
< syncState
->traceNb
; i
++)
343 for (j
= 0; j
< syncState
->traceNb
; j
++)
345 g_queue_foreach(analysisData
->hullArray
[i
][j
], gfPointDestroy
, NULL
);
346 g_queue_free(analysisData
->hullArray
[i
][j
]);
348 free(analysisData
->hullArray
[i
]);
350 free(analysisData
->hullArray
);
352 if (syncState
->stats
)
354 if (analysisData
->stats
->allFactors
!= NULL
)
356 freeAllFactors(syncState
->traceNb
, analysisData
->stats
->allFactors
);
359 free(analysisData
->stats
);
362 if (syncState
->graphsStream
)
364 if (analysisData
->graphsData
->hullPoints
!= NULL
)
366 closeGraphFiles(syncState
);
369 if (!syncState
->stats
&& analysisData
->graphsData
->allFactors
!= NULL
)
371 freeAllFactors(syncState
->traceNb
, analysisData
->graphsData
->allFactors
);
374 free(analysisData
->graphsData
);
377 free(syncState
->analysisData
);
378 syncState
->analysisData
= NULL
;
383 * Perform analysis on an event pair.
386 * syncState container for synchronization data
387 * message structure containing the events
389 static void analyzeMessageCHull(SyncState
* const syncState
, Message
* const message
)
391 AnalysisDataCHull
* analysisData
;
396 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
398 newPoint
= malloc(sizeof(Point
));
399 if (message
->inE
->traceNum
< message
->outE
->traceNum
)
401 // CA is inE->traceNum
402 newPoint
->x
= message
->inE
->cpuTime
;
403 newPoint
->y
= message
->outE
->cpuTime
;
405 g_debug("Reception point hullArray[%lu][%lu] "
406 "x= inE->time= %" PRIu64
" y= outE->time= %" PRIu64
,
407 message
->inE
->traceNum
, message
->outE
->traceNum
, newPoint
->x
,
412 // CA is outE->traceNum
413 newPoint
->x
= message
->outE
->cpuTime
;
414 newPoint
->y
= message
->inE
->cpuTime
;
416 g_debug("Send point hullArray[%lu][%lu] "
417 "x= inE->time= %" PRIu64
" y= outE->time= %" PRIu64
,
418 message
->inE
->traceNum
, message
->outE
->traceNum
, newPoint
->x
,
423 analysisData
->hullArray
[message
->inE
->traceNum
][message
->outE
->traceNum
];
425 if (hull
->length
>= 1 && newPoint
->x
< ((Point
*)
426 g_queue_peek_tail(hull
))->x
)
428 if (syncState
->stats
)
430 analysisData
->stats
->dropped
++;
437 grahamScan(hull
, newPoint
, hullType
);
443 * Construct one half of a convex hull from abscissa-sorted points
446 * hull: the points already in the hull
447 * newPoint: a new point to consider
448 * type: which half of the hull to construct
450 static void grahamScan(GQueue
* const hull
, Point
* const newPoint
, const
455 g_debug("grahamScan(hull (length: %u), newPoint, %s)", hull
->length
, type
456 == LOWER
? "LOWER" : "UPPER");
467 if (hull
->length
>= 2)
469 g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d",
472 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
473 g_queue_peek_tail(hull
), newPoint
),
475 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
476 g_queue_peek_tail(hull
), newPoint
) * inversionFactor
);
478 while (hull
->length
>= 2 && jointCmp(g_queue_peek_nth(hull
, hull
->length
-
479 2), g_queue_peek_tail(hull
), newPoint
) * inversionFactor
<= 0)
481 g_debug("Removing hull[%u]", hull
->length
);
482 free((Point
*) g_queue_pop_tail(hull
));
484 if (hull
->length
>= 2)
486 g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d",
489 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
490 g_queue_peek_tail(hull
), newPoint
),
492 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
493 g_queue_peek_tail(hull
), newPoint
) * inversionFactor
);
496 g_queue_push_tail(hull
, newPoint
);
501 * Finalize the factor calculations
504 * syncState container for synchronization data.
507 * Factors[traceNb] synchronization factors for each trace
509 static GArray
* finalizeAnalysisCHull(SyncState
* const syncState
)
511 AnalysisDataCHull
* analysisData
;
513 FactorsCHull
** allFactors
;
515 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
517 if (syncState
->graphsStream
&& analysisData
->graphsData
->hullPoints
!= NULL
)
519 writeGraphFiles(syncState
);
520 closeGraphFiles(syncState
);
523 allFactors
= calculateAllFactors(syncState
);
525 factors
= reduceFactors(syncState
, allFactors
);
527 if (syncState
->stats
|| syncState
->graphsStream
)
529 if (syncState
->stats
)
531 analysisData
->stats
->allFactors
= allFactors
;
534 if (syncState
->graphsStream
)
536 analysisData
->graphsData
->allFactors
= allFactors
;
541 freeAllFactors(syncState
->traceNb
, allFactors
);
549 * Print statistics related to analysis. Must be called after
553 * syncState container for synchronization data.
555 static void printAnalysisStatsCHull(SyncState
* const syncState
)
557 AnalysisDataCHull
* analysisData
;
560 if (!syncState
->stats
)
565 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
567 printf("Convex hull analysis stats:\n");
568 printf("\tout of order packets dropped from analysis: %u\n",
569 analysisData
->stats
->dropped
);
571 printf("\tNumber of points in convex hulls:\n");
573 for (i
= 0; i
< syncState
->traceNb
; i
++)
575 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
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
);
583 printf("\tIndividual synchronization factors:\n");
585 for (i
= 0; i
< syncState
->traceNb
; i
++)
587 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
589 FactorsCHull
* factorsCHull
;
591 factorsCHull
= &analysisData
->stats
->allFactors
[j
][i
];
592 printf("\t\t%3d - %-3d: %s", i
, j
,
593 approxNames
[factorsCHull
->type
]);
595 if (factorsCHull
->type
== EXACT
)
597 printf(" a0= % 7g a1= 1 %c %7g\n",
598 factorsCHull
->approx
->offset
,
599 factorsCHull
->approx
->drift
< 0. ? '-' : '+',
600 fabs(factorsCHull
->approx
->drift
));
602 else if (factorsCHull
->type
== MIDDLE
)
604 printf(" a0= % 7g a1= 1 %c %7g accuracy %7g\n",
605 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
606 - 1. < 0. ? '-' : '+', fabs(factorsCHull
->approx
->drift
-
607 1.), factorsCHull
->accuracy
);
608 printf("\t\t a0: % 7g to % 7g (delta= %7g)\n",
609 factorsCHull
->max
->offset
, factorsCHull
->min
->offset
,
610 factorsCHull
->min
->offset
- factorsCHull
->max
->offset
);
611 printf("\t\t a1: 1 %+7g to %+7g (delta= %7g)\n",
612 factorsCHull
->min
->drift
- 1., factorsCHull
->max
->drift
-
613 1., factorsCHull
->max
->drift
- factorsCHull
->min
->drift
);
615 else if (factorsCHull
->type
== FALLBACK
)
617 printf(" a0= % 7g a1= 1 %c %7g error= %7g\n",
618 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
619 - 1. < 0. ? '-' : '+', fabs(factorsCHull
->approx
->drift
-
620 1.), factorsCHull
->accuracy
);
622 else if (factorsCHull
->type
== INCOMPLETE
)
626 if (factorsCHull
->min
->drift
!= -INFINITY
)
628 printf("\t\t min: a0: % 7g a1: 1 %c %7g\n",
629 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
-
630 1. < 0 ? '-' : '+', fabs(factorsCHull
->min
->drift
-
633 if (factorsCHull
->max
->drift
!= INFINITY
)
635 printf("\t\t max: a0: % 7g a1: 1 %c %7g\n",
636 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
-
637 1. < 0 ? '-' : '+', fabs(factorsCHull
->max
->drift
-
641 else if (factorsCHull
->type
== SCREWED
)
645 if (factorsCHull
->min
!= NULL
&& factorsCHull
->min
->drift
!= -INFINITY
)
647 printf("\t\t min: a0: % 7g a1: 1 %c %7g\n",
648 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
-
649 1. < 0 ? '-' : '+', fabs(factorsCHull
->min
->drift
-
652 if (factorsCHull
->max
!= NULL
&& factorsCHull
->max
->drift
!= INFINITY
)
654 printf("\t\t max: a0: % 7g a1: 1 %c %7g\n",
655 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
-
656 1. < 0 ? '-' : '+', fabs(factorsCHull
->max
->drift
-
660 else if (factorsCHull
->type
== ABSENT
)
666 g_assert_not_reached();
674 * A GFunc for g_queue_foreach()
677 * data Point*, point to destroy
680 static void gfPointDestroy(gpointer data
, gpointer userData
)
684 point
= (Point
*) data
;
690 * Find out if a sequence of three points constitutes a "left turn" or a
694 * p1, p2, p3: The three points.
698 * 0 colinear (unlikely result since this uses floating point
702 static int jointCmp(const Point
const* p1
, const Point
const* p2
, const
706 const double fuzzFactor
= 0.;
708 result
= crossProductK(p1
, p2
, p1
, p3
);
709 g_debug("crossProductK(p1= (%" PRIu64
", %" PRIu64
"), "
710 "p2= (%" PRIu64
", %" PRIu64
"), p1= (%" PRIu64
", %" PRIu64
"), "
711 "p3= (%" PRIu64
", %" PRIu64
"))= %g",
712 p1
->x
, p1
->y
, p2
->x
, p2
->y
, p1
->x
, p1
->y
, p3
->x
, p3
->y
, result
);
713 if (result
< fuzzFactor
)
717 else if (result
> fuzzFactor
)
729 * Calculate the k component of the cross product of two vectors.
732 * p1, p2: start and end points of the first vector
733 * p3, p4: start and end points of the second vector
736 * the k component of the cross product when considering the two vectors to
737 * be in the i-j plane. The direction (sign) of the result can be useful to
738 * determine the relative orientation of the two vectors.
740 static double crossProductK(const Point
const* p1
, const Point
const* p2
,
741 const Point
const* p3
, const Point
const* p4
)
743 return ((double) p2
->x
- p1
->x
) * ((double) p4
->y
- p3
->y
) - ((double)
744 p2
->y
- p1
->y
) * ((double) p4
->x
- p3
->x
);
749 * Free a container of FactorsCHull
752 * traceNb: number of traces
753 * allFactors: container of FactorsCHull
755 void freeAllFactors(const unsigned int traceNb
, FactorsCHull
** const
760 for (i
= 0; i
< traceNb
; i
++)
762 for (j
= 0; j
<= i
; j
++)
764 destroyFactorsCHull(&allFactors
[i
][j
]);
773 * Free a FactorsCHull
776 * factorsCHull: container of Factors
778 void destroyFactorsCHull(FactorsCHull
* factorsCHull
)
780 if (factorsCHull
->type
== MIDDLE
|| factorsCHull
->type
==
781 INCOMPLETE
|| factorsCHull
->type
== ABSENT
)
783 free(factorsCHull
->min
);
784 free(factorsCHull
->max
);
786 else if (factorsCHull
->type
== SCREWED
)
788 if (factorsCHull
->min
!= NULL
)
790 free(factorsCHull
->min
);
792 if (factorsCHull
->max
!= NULL
)
794 free(factorsCHull
->max
);
798 if (factorsCHull
->type
== EXACT
|| factorsCHull
->type
== MIDDLE
||
799 factorsCHull
->type
== FALLBACK
)
801 free(factorsCHull
->approx
);
807 * Analyze the convex hulls to determine the synchronization factors between
808 * each pair of trace.
811 * syncState container for synchronization data.
814 * FactorsCHull*[TraceNum][TraceNum] array. See the documentation for the
815 * member allFactors of AnalysisStatsCHull.
817 FactorsCHull
** calculateAllFactors(SyncState
* const syncState
)
819 unsigned int traceNumA
, traceNumB
;
820 FactorsCHull
** allFactors
;
821 AnalysisDataCHull
* analysisData
;
823 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
825 // Allocate allFactors and calculate min and max
826 allFactors
= malloc(syncState
->traceNb
* sizeof(FactorsCHull
*));
827 for (traceNumA
= 0; traceNumA
< syncState
->traceNb
; traceNumA
++)
829 allFactors
[traceNumA
]= malloc((traceNumA
+ 1) * sizeof(FactorsCHull
));
831 allFactors
[traceNumA
][traceNumA
].type
= EXACT
;
832 allFactors
[traceNumA
][traceNumA
].approx
= malloc(sizeof(Factors
));
833 allFactors
[traceNumA
][traceNumA
].approx
->drift
= 1.;
834 allFactors
[traceNumA
][traceNumA
].approx
->offset
= 0.;
836 for (traceNumB
= 0; traceNumB
< traceNumA
; traceNumB
++)
843 size_t factorsOffset
;
845 {MINIMUM
, offsetof(FactorsCHull
, min
)},
846 {MAXIMUM
, offsetof(FactorsCHull
, max
)}
849 cr
= analysisData
->hullArray
[traceNumB
][traceNumA
];
850 cs
= analysisData
->hullArray
[traceNumA
][traceNumB
];
852 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
854 g_debug("allFactors[%u][%u].%s = calculateFactorsExact(cr= hullArray[%u][%u], cs= hullArray[%u][%u], %s)",
855 traceNumA
, traceNumB
, loopValues
[i
].factorsOffset
==
856 offsetof(FactorsCHull
, min
) ? "min" : "max", traceNumB
,
857 traceNumA
, traceNumA
, traceNumB
, loopValues
[i
].lineType
==
858 MINIMUM
? "MINIMUM" : "MAXIMUM");
859 *((Factors
**) ((void*) &allFactors
[traceNumA
][traceNumB
] +
860 loopValues
[i
].factorsOffset
))=
861 calculateFactorsExact(cr
, cs
, loopValues
[i
].lineType
);
866 // Calculate approx when possible
867 for (traceNumA
= 0; traceNumA
< syncState
->traceNb
; traceNumA
++)
869 for (traceNumB
= 0; traceNumB
< traceNumA
; traceNumB
++)
871 FactorsCHull
* factorsCHull
;
873 factorsCHull
= &allFactors
[traceNumA
][traceNumB
];
874 if (factorsCHull
->min
== NULL
&& factorsCHull
->max
== NULL
)
876 factorsCHull
->type
= FALLBACK
;
877 calculateFactorsFallback(analysisData
->hullArray
[traceNumB
][traceNumA
],
878 analysisData
->hullArray
[traceNumA
][traceNumB
],
879 &allFactors
[traceNumA
][traceNumB
]);
881 else if (factorsCHull
->min
!= NULL
&& factorsCHull
->max
!= NULL
)
883 if (factorsCHull
->min
->drift
!= -INFINITY
&&
884 factorsCHull
->max
->drift
!= INFINITY
)
886 factorsCHull
->type
= MIDDLE
;
887 calculateFactorsMiddle(factorsCHull
);
889 else if (factorsCHull
->min
->drift
!= -INFINITY
||
890 factorsCHull
->max
->drift
!= INFINITY
)
892 factorsCHull
->type
= INCOMPLETE
;
896 factorsCHull
->type
= ABSENT
;
901 //g_assert_not_reached();
902 factorsCHull
->type
= SCREWED
;
911 /* Calculate approximative factors based on minimum and maximum limits. The
912 * best approximation to make is the interior bissector of the angle formed by
913 * the minimum and maximum lines.
915 * The formulae used come from [Haddad, Yoram: Performance dans les systèmes
916 * répartis: des outils pour les mesures, Université de Paris-Sud, Centre
917 * d'Orsay, September 1988] Section 6.1 p.44
919 * The reasoning for choosing this estimator comes from [Duda, A., Harrus, G.,
920 * Haddad, Y., and Bernard, G.: Estimating global time in distributed systems,
921 * Proc. 7th Int. Conf. on Distributed Computing Systems, Berlin, volume 18,
925 * factors: contains the min and max limits, used to store the result
927 void calculateFactorsMiddle(FactorsCHull
* const factors
)
929 double amin
, amax
, bmin
, bmax
, bhat
;
931 amin
= factors
->max
->offset
;
932 amax
= factors
->min
->offset
;
933 bmin
= factors
->min
->drift
;
934 bmax
= factors
->max
->drift
;
936 g_assert_cmpfloat(bmax
, >=, bmin
);
938 factors
->approx
= malloc(sizeof(Factors
));
939 bhat
= (bmax
* bmin
- 1. + sqrt(1. + pow(bmax
, 2.) * pow(bmin
, 2.) +
940 pow(bmax
, 2.) + pow(bmin
, 2.))) / (bmax
+ bmin
);
941 factors
->approx
->offset
= amax
- (amax
- amin
) / 2. * (pow(bhat
, 2.) + 1.)
942 / (1. + bhat
* bmax
);
943 factors
->approx
->drift
= bhat
;
944 factors
->accuracy
= bmax
- bmin
;
949 * Analyze the convex hulls to determine the minimum or maximum
950 * synchronization factors between one pair of trace.
952 * This implements and improves upon the algorithm in [Haddad, Yoram:
953 * Performance dans les systèmes répartis: des outils pour les mesures,
954 * Université de Paris-Sud, Centre d'Orsay, September 1988] Section 6.2 p.47
956 * Some degenerate cases are possible:
957 * 1) the result is unbounded. In that case, when searching for the maximum
958 * factors, result->drift= INFINITY; result->offset= -INFINITY. When
959 * searching for the minimum factors, it is the opposite. It is not
960 * possible to improve the situation with this data.
961 * 2) no line can be above the upper hull and below the lower hull. This is
962 * because the hulls intersect each other or are reversed. This means that
963 * an assertion was false. Most probably, the clocks are not linear. It is
964 * possible to repeat the search with another algorithm that will find a
965 * "best effort" approximation. See calculateFactorsApprox().
968 * cu: the upper half-convex hull, the line must pass above this
969 * and touch it in one point
970 * cl: the lower half-convex hull, the line must pass below this
971 * and touch it in one point
972 * lineType: search for minimum or maximum factors
975 * If a result is found, a struct Factors is allocated, filed with the
976 * result and returned
977 * NULL otherwise, degenerate case 2 is in effect
979 static Factors
* calculateFactorsExact(GQueue
* const cu
, GQueue
* const cl
, const
985 double inversionFactor
;
988 g_debug("calculateFactorsExact(cu= %p, cl= %p, %s)", cu
, cl
, lineType
==
989 MINIMUM
? "MINIMUM" : "MAXIMUM");
991 if (lineType
== MINIMUM
)
995 inversionFactor
= -1.;
1001 inversionFactor
= 1.;
1007 // Check for degenerate case 1
1008 if (c1
->length
== 0 || c2
->length
== 0 || ((Point
*) g_queue_peek_nth(c1
,
1009 i1
))->x
>= ((Point
*) g_queue_peek_nth(c2
, i2
))->x
)
1011 result
= malloc(sizeof(Factors
));
1012 if (lineType
== MINIMUM
)
1014 result
->drift
= -INFINITY
;
1015 result
->offset
= INFINITY
;
1019 result
->drift
= INFINITY
;
1020 result
->offset
= -INFINITY
;
1032 g_queue_peek_nth(c1
, i1
),
1033 g_queue_peek_nth(c2
, i2
),
1034 g_queue_peek_nth(c1
, i1
),
1035 g_queue_peek_nth(c2
, i2
- 1)) * inversionFactor
< 0.
1038 if (((Point
*) g_queue_peek_nth(c1
, i1
))->x
1039 < ((Point
*) g_queue_peek_nth(c2
, i2
- 1))->x
)
1045 // Degenerate case 2
1051 i1
+ 1 < c1
->length
- 1
1053 g_queue_peek_nth(c1
, i1
),
1054 g_queue_peek_nth(c2
, i2
),
1055 g_queue_peek_nth(c1
, i1
+ 1),
1056 g_queue_peek_nth(c2
, i2
)) * inversionFactor
< 0.
1059 if (((Point
*) g_queue_peek_nth(c1
, i1
+ 1))->x
1060 < ((Point
*) g_queue_peek_nth(c2
, i2
))->x
)
1066 // Degenerate case 2
1074 g_queue_peek_nth(c1
, i1
),
1075 g_queue_peek_nth(c2
, i2
),
1076 g_queue_peek_nth(c1
, i1
),
1077 g_queue_peek_nth(c2
, i2
- 1)) * inversionFactor
< 0.
1080 p1
= g_queue_peek_nth(c1
, i1
);
1081 p2
= g_queue_peek_nth(c2
, i2
);
1083 g_debug("Resulting points are: c1[i1]: x= %" PRIu64
" y= %" PRIu64
1084 " c2[i2]: x= %" PRIu64
" y= %" PRIu64
"", p1
->x
, p1
->y
, p2
->x
, p2
->y
);
1086 result
= malloc(sizeof(Factors
));
1087 result
->drift
= slope(p1
, p2
);
1088 result
->offset
= intercept(p1
, p2
);
1090 g_debug("Resulting factors are: drift= %g offset= %g", result
->drift
,
1098 * Analyze the convex hulls to determine approximate synchronization factors
1099 * between one pair of trace when there is no line that can fit in the
1100 * corridor separating them.
1102 * This implements the algorithm in [Ashton, P.: Algorithms for Off-line Clock
1103 * Synchronisation, University of Canterbury, December 1995, 26] Section 4.2.2
1106 * For each point p1 in cr
1107 * For each point p2 in cs
1109 * Calculate the line paramaters
1110 * For each point p3 in each convex hull
1111 * If p3 is on the wrong side of the line
1113 * If error < errorMin
1117 * cr: the upper half-convex hull
1118 * cs: the lower half-convex hull
1119 * result: a pointer to the pre-allocated struct where the results
1122 static void calculateFactorsFallback(GQueue
* const cr
, GQueue
* const cs
,
1123 FactorsCHull
* const result
)
1125 unsigned int i
, j
, k
;
1130 approx
= malloc(sizeof(Factors
));
1132 for (i
= 0; i
< cs
->length
; i
++)
1134 for (j
= 0; j
< cr
->length
; j
++)
1141 if (((Point
*) g_queue_peek_nth(cs
, i
))->x
< ((Point
*)g_queue_peek_nth(cr
, j
))->x
)
1143 p1
= *(Point
*)g_queue_peek_nth(cs
, i
);
1144 p2
= *(Point
*)g_queue_peek_nth(cr
, j
);
1148 p1
= *(Point
*)g_queue_peek_nth(cr
, j
);
1149 p2
= *(Point
*)g_queue_peek_nth(cs
, i
);
1152 // The lower hull should be above the point
1153 for (k
= 0; k
< cs
->length
; k
++)
1155 if (jointCmp(&p1
, &p2
, g_queue_peek_nth(cs
, k
)) < 0.)
1157 error
+= verticalDistance(&p1
, &p2
, g_queue_peek_nth(cs
, k
));
1161 // The upper hull should be below the point
1162 for (k
= 0; k
< cr
->length
; k
++)
1164 if (jointCmp(&p1
, &p2
, g_queue_peek_nth(cr
, k
)) > 0.)
1166 error
+= verticalDistance(&p1
, &p2
, g_queue_peek_nth(cr
, k
));
1170 if (error
< errorMin
)
1172 g_debug("Fallback: i= %u j= %u is a better match (error= %g)", i
, j
, error
);
1173 approx
->drift
= slope(&p1
, &p2
);
1174 approx
->offset
= intercept(&p1
, &p2
);
1180 result
->approx
= approx
;
1181 result
->accuracy
= errorMin
;
1186 * Calculate the vertical distance between a line and a point
1189 * p1, p2: Two points defining the line
1193 * the vertical distance
1195 static double verticalDistance(Point
* p1
, Point
* p2
, Point
* const point
)
1197 return fabs(slope(p1
, p2
) * point
->x
+ intercept(p1
, p2
) - point
->y
);
1202 * Calculate the slope between two points
1205 * p1, p2 the two points
1210 static double slope(const Point
* const p1
, const Point
* const p2
)
1212 return ((double) p2
->y
- p1
->y
) / (p2
->x
- p1
->x
);
1216 /* Calculate the y-intercept of a line that passes by two points
1219 * p1, p2 the two points
1224 static double intercept(const Point
* const p1
, const Point
* const p2
)
1226 return ((double) p2
->y
* p1
->x
- (double) p1
->y
* p2
->x
) / ((double) p1
->x
- p2
->x
);
1231 * Calculate a resulting offset and drift for each trace.
1233 * Traces are assembled in groups. A group is an "island" of nodes/traces that
1234 * exchanged messages. A reference is determined for each group by using a
1235 * shortest path search based on the accuracy of the approximation. This also
1236 * forms a tree of the best way to relate each node's clock to the reference's
1237 * based on the accuracy. Sometimes it may be necessary or advantageous to
1238 * propagate the factors through intermediary clocks. Resulting factors for
1239 * each trace are determined based on this tree.
1241 * This part was not the focus of my research. The algorithm used here is
1242 * inexact in some ways:
1243 * 1) The reference used may not actually be the best one to use. This is
1244 * because the accuracy is not corrected based on the drift during the
1245 * shortest path search.
1246 * 2) The min and max factors are not propagated and are no longer valid.
1247 * 3) Approximations of different types (MIDDLE and FALLBACK) are compared
1248 * together. The "accuracy" parameters of these have different meanings and
1249 * are not readily comparable.
1251 * Nevertheless, the result is satisfactory. You just can't tell "how much" it
1254 * Two alternative (and subtly different) ways of propagating factors to
1255 * preserve min and max bondaries have been proposed, see:
1256 * [Duda, A., Harrus, G., Haddad, Y., and Bernard, G.: Estimating global time
1257 * in distributed systems, Proc. 7th Int. Conf. on Distributed Computing
1258 * Systems, Berlin, volume 18, 1987] p.304
1260 * [Jezequel, J.M., and Jard, C.: Building a global clock for observing
1261 * computations in distributed memory parallel computers, Concurrency:
1262 * Practice and Experience 8(1), volume 8, John Wiley & Sons, Ltd Chichester,
1263 * 1996, 32] Section 5; which is mostly the same as
1264 * [Jezequel, J.M.: Building a global time on parallel machines, Proceedings
1265 * of the 3rd International Workshop on Distributed Algorithms, LNCS, volume
1266 * 392, 136–147, 1989] Section 5
1269 * syncState: container for synchronization data.
1270 * allFactors: offset and drift between each pair of traces
1273 * Factors[traceNb] synchronization factors for each trace
1275 static GArray
* reduceFactors(SyncState
* const syncState
, FactorsCHull
** const
1280 unsigned int** predecessors
;
1281 double* distanceSums
;
1282 unsigned int* references
;
1285 // Solve the all-pairs shortest path problem using the Floyd-Warshall
1287 floydWarshall(syncState
, allFactors
, &distances
, &predecessors
);
1289 /* Find the reference for each node
1291 * First calculate, for each node, the sum of the distances to each other
1292 * node it can reach.
1294 * Then, go through each "island" of traces to find the trace that has the
1295 * lowest distance sum. Assign this trace as the reference to each trace
1298 distanceSums
= malloc(syncState
->traceNb
* sizeof(double));
1299 for (i
= 0; i
< syncState
->traceNb
; i
++)
1301 distanceSums
[i
]= 0.;
1302 for (j
= 0; j
< syncState
->traceNb
; j
++)
1304 distanceSums
[i
]+= distances
[i
][j
];
1308 references
= malloc(syncState
->traceNb
* sizeof(unsigned int));
1309 for (i
= 0; i
< syncState
->traceNb
; i
++)
1311 references
[i
]= UINT_MAX
;
1313 for (i
= 0; i
< syncState
->traceNb
; i
++)
1315 if (references
[i
] == UINT_MAX
)
1317 unsigned int reference
;
1318 double distanceSumMin
;
1320 // A node is its own reference by default
1322 distanceSumMin
= INFINITY
;
1323 for (j
= 0; j
< syncState
->traceNb
; j
++)
1325 if (distances
[i
][j
] != INFINITY
&& distanceSums
[j
] <
1329 distanceSumMin
= distanceSums
[j
];
1332 for (j
= 0; j
< syncState
->traceNb
; j
++)
1334 if (distances
[i
][j
] != INFINITY
)
1336 references
[j
]= reference
;
1342 for (i
= 0; i
< syncState
->traceNb
; i
++)
1349 /* For each trace, calculate the factors based on their corresponding
1350 * tree. The tree is rooted at the reference and the shortest path to each
1351 * other nodes are the branches.
1353 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
1354 syncState
->traceNb
);
1355 g_array_set_size(factors
, syncState
->traceNb
);
1356 for (i
= 0; i
< syncState
->traceNb
; i
++)
1358 getFactors(allFactors
, predecessors
, references
, i
, &g_array_index(factors
,
1362 for (i
= 0; i
< syncState
->traceNb
; i
++)
1364 free(predecessors
[i
]);
1374 * Perform an all-source shortest path search using the Floyd-Warshall
1377 * The algorithm is implemented accoding to the description here:
1378 * http://web.mit.edu/urban_or_book/www/book/chapter6/6.2.2.html
1381 * syncState: container for synchronization data.
1382 * allFactors: offset and drift between each pair of traces
1383 * distances: resulting matrix of the length of the shortest path between
1384 * two nodes. If there is no path between two nodes, the
1385 * length is INFINITY
1386 * predecessors: resulting matrix of each node's predecessor on the shortest
1387 * path between two nodes
1389 static void floydWarshall(SyncState
* const syncState
, FactorsCHull
** const
1390 allFactors
, double*** const distances
, unsigned int*** const
1393 unsigned int i
, j
, k
;
1395 // Setup initial conditions
1396 *distances
= malloc(syncState
->traceNb
* sizeof(double*));
1397 *predecessors
= malloc(syncState
->traceNb
* sizeof(unsigned int*));
1398 for (i
= 0; i
< syncState
->traceNb
; i
++)
1400 (*distances
)[i
]= malloc(syncState
->traceNb
* sizeof(double));
1401 for (j
= 0; j
< syncState
->traceNb
; j
++)
1405 g_assert(allFactors
[i
][j
].type
== EXACT
);
1407 (*distances
)[i
][j
]= 0.;
1411 unsigned int row
, col
;
1424 if (allFactors
[row
][col
].type
== MIDDLE
||
1425 allFactors
[row
][col
].type
== FALLBACK
)
1427 (*distances
)[i
][j
]= allFactors
[row
][col
].accuracy
;
1429 else if (allFactors
[row
][col
].type
== INCOMPLETE
||
1430 allFactors
[row
][col
].type
== SCREWED
||
1431 allFactors
[row
][col
].type
== ABSENT
)
1433 (*distances
)[i
][j
]= INFINITY
;
1437 g_assert_not_reached();
1442 (*predecessors
)[i
]= malloc(syncState
->traceNb
* sizeof(unsigned int));
1443 for (j
= 0; j
< syncState
->traceNb
; j
++)
1447 (*predecessors
)[i
][j
]= i
;
1451 (*predecessors
)[i
][j
]= UINT_MAX
;
1456 // Run the iterations
1457 for (k
= 0; k
< syncState
->traceNb
; k
++)
1459 for (i
= 0; i
< syncState
->traceNb
; i
++)
1461 for (j
= 0; j
< syncState
->traceNb
; j
++)
1465 distanceMin
= MIN((*distances
)[i
][j
], (*distances
)[i
][k
] +
1466 (*distances
)[k
][j
]);
1468 if (distanceMin
!= (*distances
)[i
][j
])
1470 (*predecessors
)[i
][j
]= (*predecessors
)[k
][j
];
1473 (*distances
)[i
][j
]= distanceMin
;
1481 * Cummulate the time correction factors to convert a node's time to its
1483 * This function recursively calls itself until it reaches the reference node.
1486 * allFactors: offset and drift between each pair of traces
1487 * predecessors: matrix of each node's predecessor on the shortest
1488 * path between two nodes
1489 * references: reference node for each node
1490 * traceNum: node for which to find the factors
1491 * factors: resulting factors
1493 static void getFactors(FactorsCHull
** const allFactors
, unsigned int** const
1494 predecessors
, unsigned int* const references
, const unsigned int traceNum
,
1495 Factors
* const factors
)
1497 unsigned int reference
;
1499 reference
= references
[traceNum
];
1501 if (reference
== traceNum
)
1503 factors
->offset
= 0.;
1508 Factors previousVertexFactors
;
1510 getFactors(allFactors
, predecessors
, references
,
1511 predecessors
[reference
][traceNum
], &previousVertexFactors
);
1513 // convertir de traceNum à reference
1515 // allFactors convertit de col à row
1517 if (reference
> traceNum
)
1519 factors
->offset
= previousVertexFactors
.drift
*
1520 allFactors
[reference
][traceNum
].approx
->offset
+
1521 previousVertexFactors
.offset
;
1522 factors
->drift
= previousVertexFactors
.drift
*
1523 allFactors
[reference
][traceNum
].approx
->drift
;
1527 factors
->offset
= previousVertexFactors
.drift
* (-1. *
1528 allFactors
[traceNum
][reference
].approx
->offset
/
1529 allFactors
[traceNum
][reference
].approx
->drift
) +
1530 previousVertexFactors
.offset
;
1531 factors
->drift
= previousVertexFactors
.drift
* (1. /
1532 allFactors
[traceNum
][reference
].approx
->drift
);
1539 * Write the analysis-specific graph lines in the gnuplot script.
1542 * syncState: container for synchronization data
1543 * i: first trace number
1544 * j: second trace number, garanteed to be larger than i
1546 void writeAnalysisGraphsPlotsCHull(SyncState
* const syncState
, const unsigned
1547 int i
, const unsigned int j
)
1549 AnalysisDataCHull
* analysisData
;
1550 FactorsCHull
* factorsCHull
;
1552 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
1554 fprintf(syncState
->graphsStream
,
1555 "\t\"analysis_chull-%1$03d_to_%2$03d.data\" "
1556 "title \"Lower half-hull\" with linespoints "
1557 "linecolor rgb \"#015a01\" linetype 4 pointtype 8 pointsize 0.8, \\\n"
1558 "\t\"analysis_chull-%2$03d_to_%1$03d.data\" "
1559 "title \"Upper half-hull\" with linespoints "
1560 "linecolor rgb \"#003366\" linetype 4 pointtype 10 pointsize 0.8, \\\n",
1563 factorsCHull
= &analysisData
->graphsData
->allFactors
[j
][i
];
1564 if (factorsCHull
->type
== EXACT
)
1566 fprintf(syncState
->graphsStream
,
1568 "title \"Exact conversion\" with lines "
1569 "linecolor rgb \"black\" linetype 1, \\\n",
1570 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
);
1572 else if (factorsCHull
->type
== MIDDLE
)
1574 fprintf(syncState
->graphsStream
,
1575 "\t%.2f + %.10f * x "
1576 "title \"Min conversion\" with lines "
1577 "linecolor rgb \"black\" linetype 5, \\\n",
1578 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
);
1579 fprintf(syncState
->graphsStream
,
1580 "\t%.2f + %.10f * x "
1581 "title \"Max conversion\" with lines "
1582 "linecolor rgb \"black\" linetype 8, \\\n",
1583 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
);
1584 fprintf(syncState
->graphsStream
,
1585 "\t%.2f + %.10f * x "
1586 "title \"Middle conversion\" with lines "
1587 "linecolor rgb \"black\" linetype 1, \\\n",
1588 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
);
1590 else if (factorsCHull
->type
== FALLBACK
)
1592 fprintf(syncState
->graphsStream
,
1593 "\t%.2f + %.10f * x "
1594 "title \"Fallback conversion\" with lines "
1595 "linecolor rgb \"gray60\" linetype 1, \\\n",
1596 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
);
1598 else if (factorsCHull
->type
== INCOMPLETE
)
1600 if (factorsCHull
->min
->drift
!= -INFINITY
)
1602 fprintf(syncState
->graphsStream
,
1603 "\t%.2f + %.10f * x "
1604 "title \"Min conversion\" with lines "
1605 "linecolor rgb \"black\" linetype 5, \\\n",
1606 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
);
1609 if (factorsCHull
->max
->drift
!= INFINITY
)
1611 fprintf(syncState
->graphsStream
,
1612 "\t%.2f + %.10f * x "
1613 "title \"Max conversion\" with lines "
1614 "linecolor rgb \"black\" linetype 8, \\\n",
1615 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
);
1618 else if (factorsCHull
->type
== SCREWED
)
1620 if (factorsCHull
->min
!= NULL
&& factorsCHull
->min
->drift
!= -INFINITY
)
1622 fprintf(syncState
->graphsStream
,
1623 "\t%.2f + %.10f * x "
1624 "title \"Min conversion\" with lines "
1625 "linecolor rgb \"black\" linetype 5, \\\n",
1626 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
);
1629 if (factorsCHull
->max
!= NULL
&& factorsCHull
->max
->drift
!= INFINITY
)
1631 fprintf(syncState
->graphsStream
,
1632 "\t%.2f + %.10f * x "
1633 "title \"Max conversion\" with lines "
1634 "linecolor rgb \"black\" linetype 8, \\\n",
1635 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
);
1638 else if (factorsCHull
->type
== ABSENT
)
1643 g_assert_not_reached();