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
31 #include "sync_chain.h"
33 #include "event_analysis_chull.h"
37 #define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format)
55 // Functions common to all analysis modules
56 static void initAnalysisCHull(SyncState
* const syncState
);
57 static void destroyAnalysisCHull(SyncState
* const syncState
);
59 static void analyzePacketCHull(SyncState
* const syncState
, Packet
* const packet
);
60 static GArray
* finalizeAnalysisCHull(SyncState
* const syncState
);
61 static void printAnalysisStatsCHull(SyncState
* const syncState
);
62 static void writeAnalysisGraphsPlotsCHull(FILE* stream
, SyncState
* const
63 syncState
, const unsigned int i
, const unsigned int j
);
65 // Functions specific to this module
66 static void registerAnalysisCHull() __attribute__((constructor (101)));
68 static void openGraphFiles(SyncState
* const syncState
);
69 static void closeGraphFiles(SyncState
* const syncState
);
70 static void writeGraphFiles(SyncState
* const syncState
);
71 static void gfDumpHullToFile(gpointer data
, gpointer userData
);
73 static void grahamScan(GQueue
* const hull
, Point
* const newPoint
, const
75 static int jointCmp(const Point
* const p1
, const Point
* const p2
, const Point
*
76 const p3
) __attribute__((pure
));
77 static double crossProductK(const Point
const* p1
, const Point
const* p2
,
78 const Point
const* p3
, const Point
const* p4
) __attribute__((pure
));
79 static FactorsCHull
** calculateAllFactors(SyncState
* const syncState
);
80 static Factors
* calculateFactorsExact(GQueue
* const cu
, GQueue
* const cl
, const
81 LineType lineType
) __attribute__((pure
));
82 static void calculateFactorsMiddle(FactorsCHull
* factors
);
83 static void calculateFactorsFallback(GQueue
* const cr
, GQueue
* const cs
,
84 FactorsCHull
* const result
);
85 static double slope(const Point
* const p1
, const Point
* const p2
)
86 __attribute__((pure
));
87 static double intercept(const Point
* const p1
, const Point
* const p2
)
88 __attribute__((pure
));
89 static GArray
* reduceFactors(SyncState
* const syncState
, FactorsCHull
**
91 static void freeAllFactors(const SyncState
* const syncState
, FactorsCHull
**
93 static double verticalDistance(Point
* p1
, Point
* p2
, Point
* const point
)
94 __attribute__((pure
));
95 static void floydWarshall(SyncState
* const syncState
, FactorsCHull
** const
96 allFactors
, double*** const distances
, unsigned int*** const
98 static void getFactors(FactorsCHull
** const allFactors
, unsigned int** const
99 predecessors
, unsigned int* const references
, const unsigned int traceNum
,
100 Factors
* const factors
);
102 static void gfPointDestroy(gpointer data
, gpointer userData
);
105 static AnalysisModule analysisModuleCHull
= {
107 .initAnalysis
= &initAnalysisCHull
,
108 .destroyAnalysis
= &destroyAnalysisCHull
,
109 .analyzePacket
= &analyzePacketCHull
,
110 .analyzeExchange
= NULL
,
111 .finalizeAnalysis
= &finalizeAnalysisCHull
,
112 .printAnalysisStats
= &printAnalysisStatsCHull
,
113 .writeAnalysisGraphsPlots
= &writeAnalysisGraphsPlotsCHull
,
114 .writeAnalysisGraphsOptions
= NULL
,
119 * Analysis module registering function
121 static void registerAnalysisCHull()
123 g_queue_push_tail(&analysisModules
, &analysisModuleCHull
);
128 * Analysis init function
130 * This function is called at the beginning of a synchronization run for a set
133 * Allocate some of the analysis specific data structures
136 * syncState container for synchronization data.
137 * This function allocates or initializes these analysisData
142 static void initAnalysisCHull(SyncState
* const syncState
)
145 AnalysisDataCHull
* analysisData
;
147 analysisData
= malloc(sizeof(AnalysisDataCHull
));
148 syncState
->analysisData
= analysisData
;
150 analysisData
->hullArray
= malloc(syncState
->traceNb
* sizeof(GQueue
**));
151 for (i
= 0; i
< syncState
->traceNb
; i
++)
153 analysisData
->hullArray
[i
]= malloc(syncState
->traceNb
* sizeof(GQueue
*));
155 for (j
= 0; j
< syncState
->traceNb
; j
++)
157 analysisData
->hullArray
[i
][j
]= g_queue_new();
161 if (syncState
->stats
)
163 analysisData
->stats
= malloc(sizeof(AnalysisStatsCHull
));
164 analysisData
->stats
->dropped
= 0;
165 analysisData
->stats
->allFactors
= NULL
;
168 if (syncState
->graphs
)
170 analysisData
->graphsData
= malloc(sizeof(AnalysisGraphsDataCHull
));
171 openGraphFiles(syncState
);
172 analysisData
->graphsData
->allFactors
= NULL
;
178 * Create and open files used to store convex hull points to genereate
179 * graphs. Allocate and populate array to store file pointers.
182 * syncState: container for synchronization data
184 static void openGraphFiles(SyncState
* const syncState
)
190 AnalysisDataCHull
* analysisData
;
192 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
194 cwd
= changeToGraphDir(syncState
->graphs
);
196 analysisData
->graphsData
->hullPoints
= malloc(syncState
->traceNb
*
198 for (i
= 0; i
< syncState
->traceNb
; i
++)
200 analysisData
->graphsData
->hullPoints
[i
]= malloc(syncState
->traceNb
*
202 for (j
= 0; j
< syncState
->traceNb
; j
++)
206 retval
= snprintf(name
, sizeof(name
),
207 "analysis_chull-%03u_to_%03u.data", j
, i
);
208 if (retval
> sizeof(name
) - 1)
210 name
[sizeof(name
) - 1]= '\0';
212 if ((analysisData
->graphsData
->hullPoints
[i
][j
]= fopen(name
, "w")) ==
215 g_error(strerror(errno
));
224 g_error(strerror(errno
));
231 * Write hull points to files to generate graphs.
234 * syncState: container for synchronization data
236 static void writeGraphFiles(SyncState
* const syncState
)
239 AnalysisDataCHull
* analysisData
;
241 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
243 for (i
= 0; i
< syncState
->traceNb
; i
++)
245 for (j
= 0; j
< syncState
->traceNb
; j
++)
249 g_queue_foreach(analysisData
->hullArray
[i
][j
],
251 analysisData
->graphsData
->hullPoints
[i
][j
]);
259 * A GFunc for g_queue_foreach. Write a hull point to a file used to generate
263 * data: Point*, point to write to the file
264 * userData: FILE*, file pointer where to write the point
266 static void gfDumpHullToFile(gpointer data
, gpointer userData
)
270 point
= (Point
*) data
;
271 fprintf((FILE*) userData
, "%20llu %20llu\n", point
->x
, point
->y
);
276 * Close files used to store convex hull points to generate graphs.
277 * Deallocate array to store file pointers.
280 * syncState: container for synchronization data
282 static void closeGraphFiles(SyncState
* const syncState
)
285 AnalysisDataCHull
* analysisData
;
288 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
290 if (analysisData
->graphsData
->hullPoints
== NULL
)
295 for (i
= 0; i
< syncState
->traceNb
; i
++)
297 for (j
= 0; j
< syncState
->traceNb
; j
++)
301 retval
= fclose(analysisData
->graphsData
->hullPoints
[i
][j
]);
304 g_error(strerror(errno
));
308 free(analysisData
->graphsData
->hullPoints
[i
]);
310 free(analysisData
->graphsData
->hullPoints
);
311 analysisData
->graphsData
->hullPoints
= NULL
;
316 * Analysis destroy function
318 * Free the analysis specific data structures
321 * syncState container for synchronization data.
322 * This function deallocates these analysisData members:
326 static void destroyAnalysisCHull(SyncState
* const syncState
)
329 AnalysisDataCHull
* analysisData
;
331 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
333 if (analysisData
== NULL
)
338 for (i
= 0; i
< syncState
->traceNb
; i
++)
340 for (j
= 0; j
< syncState
->traceNb
; j
++)
342 g_queue_foreach(analysisData
->hullArray
[i
][j
], gfPointDestroy
, NULL
);
344 free(analysisData
->hullArray
[i
]);
346 free(analysisData
->hullArray
);
348 if (syncState
->stats
)
350 if (analysisData
->stats
->allFactors
!= NULL
)
352 freeAllFactors(syncState
, analysisData
->stats
->allFactors
);
355 free(analysisData
->stats
);
358 if (syncState
->graphs
)
360 if (analysisData
->graphsData
->hullPoints
!= NULL
)
362 closeGraphFiles(syncState
);
365 if (!syncState
->stats
&& analysisData
->graphsData
->allFactors
!= NULL
)
367 freeAllFactors(syncState
, analysisData
->graphsData
->allFactors
);
370 free(analysisData
->graphsData
);
373 free(syncState
->analysisData
);
374 syncState
->analysisData
= NULL
;
379 * Perform analysis on an event pair.
382 * syncState container for synchronization data
383 * packet structure containing the events
385 static void analyzePacketCHull(SyncState
* const syncState
, Packet
* const packet
)
387 AnalysisDataCHull
* analysisData
;
392 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
394 newPoint
= malloc(sizeof(Point
));
395 if (packet
->inE
->traceNum
< packet
->outE
->traceNum
)
397 // CA is inE->traceNum
398 newPoint
->x
= packet
->inE
->tsc
;
399 newPoint
->y
= packet
->outE
->tsc
;
401 g_debug("Reception point hullArray[%lu][%lu] x= inE->tsc= %llu y= outE->tsc= %llu",
402 packet
->inE
->traceNum
, packet
->outE
->traceNum
, newPoint
->x
,
407 // CA is outE->traceNum
408 newPoint
->x
= packet
->outE
->tsc
;
409 newPoint
->y
= packet
->inE
->tsc
;
411 g_debug("Send point hullArray[%lu][%lu] x= inE->tsc= %llu y= outE->tsc= %llu",
412 packet
->inE
->traceNum
, packet
->outE
->traceNum
, newPoint
->x
,
417 analysisData
->hullArray
[packet
->inE
->traceNum
][packet
->outE
->traceNum
];
419 if (hull
->length
>= 1 && newPoint
->x
< ((Point
*)
420 g_queue_peek_tail(hull
))->x
)
422 if (syncState
->stats
)
424 analysisData
->stats
->dropped
++;
431 grahamScan(hull
, newPoint
, hullType
);
437 * Construct one half of a convex hull from abscissa-sorted points
440 * hull: the points already in the hull
441 * newPoint: a new point to consider
442 * type: which half of the hull to construct
444 static void grahamScan(GQueue
* const hull
, Point
* const newPoint
, const
449 g_debug("grahamScan(hull (length: %u), newPoint, %s)", hull
->length
, type
450 == LOWER
? "LOWER" : "UPPER");
461 if (hull
->length
>= 2)
463 g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d",
466 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
467 g_queue_peek_tail(hull
), newPoint
),
469 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
470 g_queue_peek_tail(hull
), newPoint
) * inversionFactor
);
472 while (hull
->length
>= 2 && jointCmp(g_queue_peek_nth(hull
, hull
->length
-
473 2), g_queue_peek_tail(hull
), newPoint
) * inversionFactor
<= 0)
475 g_debug("Removing hull[%u]", hull
->length
);
476 free((Point
*) g_queue_pop_tail(hull
));
478 if (hull
->length
>= 2)
480 g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d",
483 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
484 g_queue_peek_tail(hull
), newPoint
),
486 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
487 g_queue_peek_tail(hull
), newPoint
) * inversionFactor
);
490 g_queue_push_tail(hull
, newPoint
);
495 * Finalize the factor calculations
498 * syncState container for synchronization data.
501 * Factors[traceNb] synchronization factors for each trace
503 static GArray
* finalizeAnalysisCHull(SyncState
* const syncState
)
505 AnalysisDataCHull
* analysisData
;
507 FactorsCHull
** allFactors
;
509 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
511 if (syncState
->graphs
)
513 writeGraphFiles(syncState
);
514 closeGraphFiles(syncState
);
517 allFactors
= calculateAllFactors(syncState
);
519 factors
= reduceFactors(syncState
, allFactors
);
521 if (syncState
->stats
|| syncState
->graphs
)
523 if (syncState
->stats
)
525 analysisData
->stats
->allFactors
= allFactors
;
528 if (syncState
->graphs
)
530 analysisData
->graphsData
->allFactors
= allFactors
;
535 freeAllFactors(syncState
, allFactors
);
543 * Print statistics related to analysis. Must be called after
547 * syncState container for synchronization data.
549 static void printAnalysisStatsCHull(SyncState
* const syncState
)
551 AnalysisDataCHull
* analysisData
;
554 if (!syncState
->stats
)
559 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
561 printf("Convex hull analysis stats:\n");
562 printf("\tout of order packets dropped from analysis: %u\n",
563 analysisData
->stats
->dropped
);
565 printf("\tNumber of points in convex hulls:\n");
567 for (i
= 0; i
< syncState
->traceNb
; i
++)
569 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
571 printf("\t\t%3d - %-3d: lower half-hull %-5u upper half-hull %-5u\n",
572 i
, j
, analysisData
->hullArray
[j
][i
]->length
,
573 analysisData
->hullArray
[i
][j
]->length
);
577 printf("\tIndividual synchronization factors:\n");
579 for (i
= 0; i
< syncState
->traceNb
; i
++)
581 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
583 FactorsCHull
* factorsCHull
;
585 factorsCHull
= &analysisData
->stats
->allFactors
[j
][i
];
586 printf("\t\t%3d - %-3d: ", i
, j
);
588 if (factorsCHull
->type
== EXACT
)
590 printf("Exact a0= % 7g a1= 1 %c %7g\n",
591 factorsCHull
->approx
->offset
,
592 factorsCHull
->approx
->drift
< 0. ? '-' : '+',
593 fabs(factorsCHull
->approx
->drift
));
595 else if (factorsCHull
->type
== MIDDLE
)
597 printf("Middle a0= % 7g a1= 1 %c %7g accuracy %7g\n",
598 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
599 - 1. < 0. ? '-' : '+', fabs(factorsCHull
->approx
->drift
-
600 1.), factorsCHull
->accuracy
);
601 printf("\t\t a0: % 7g to % 7g (delta= %7g)\n",
602 factorsCHull
->max
->offset
, factorsCHull
->min
->offset
,
603 factorsCHull
->min
->offset
- factorsCHull
->max
->offset
);
604 printf("\t\t a1: 1 %+7g to %+7g (delta= %7g)\n",
605 factorsCHull
->min
->drift
- 1., factorsCHull
->max
->drift
-
606 1., factorsCHull
->max
->drift
- factorsCHull
->min
->drift
);
608 else if (factorsCHull
->type
== FALLBACK
)
610 printf("Fallback a0= % 7g a1= 1 %c %7g error= %7g\n",
611 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
612 - 1. < 0. ? '-' : '+', fabs(factorsCHull
->approx
->drift
-
613 1.), factorsCHull
->accuracy
);
615 else if (factorsCHull
->type
== INCOMPLETE
)
617 printf("Incomplete\n");
619 if (factorsCHull
->min
->drift
!= -INFINITY
)
621 printf("\t\t min: a0: % 7g a1: 1 %c %7g\n",
622 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
-
623 1. < 0 ? '-' : '+', fabs(factorsCHull
->min
->drift
-
626 if (factorsCHull
->max
->drift
!= INFINITY
)
628 printf("\t\t max: a0: % 7g a1: 1 %c %7g\n",
629 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
-
630 1. < 0 ? '-' : '+', fabs(factorsCHull
->max
->drift
-
634 else if (factorsCHull
->type
== SCREWED
)
638 if (factorsCHull
->min
!= NULL
&& factorsCHull
->min
->drift
!= -INFINITY
)
640 printf("\t\t min: a0: % 7g a1: 1 %c %7g\n",
641 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
-
642 1. < 0 ? '-' : '+', fabs(factorsCHull
->min
->drift
-
645 if (factorsCHull
->max
!= NULL
&& factorsCHull
->max
->drift
!= INFINITY
)
647 printf("\t\t max: a0: % 7g a1: 1 %c %7g\n",
648 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
-
649 1. < 0 ? '-' : '+', fabs(factorsCHull
->max
->drift
-
653 else if (factorsCHull
->type
== ABSENT
)
659 g_assert_not_reached();
667 * A GFunc for g_queue_foreach()
670 * data Point*, point to destroy
673 static void gfPointDestroy(gpointer data
, gpointer userData
)
677 point
= (Point
*) data
;
683 * Find out if a sequence of three points constitutes a "left turn" or a
687 * p1, p2, p3: The three points.
691 * 0 colinear (unlikely result since this uses floating point
695 static int jointCmp(const Point
const* p1
, const Point
const* p2
, const
699 const double fuzzFactor
= 0.;
701 result
= crossProductK(p1
, p2
, p1
, p3
);
702 g_debug("crossProductK(p1= (%llu, %llu), p2= (%llu, %llu), p1= (%llu, %llu), p3= (%llu, %llu))= %g",
703 p1
->x
, p1
->y
, p2
->x
, p2
->y
, p1
->x
, p1
->y
, p3
->x
, p3
->y
, result
);
704 if (result
< fuzzFactor
)
708 else if (result
> fuzzFactor
)
720 * Calculate the k component of the cross product of two vectors.
723 * p1, p2: start and end points of the first vector
724 * p3, p4: start and end points of the second vector
727 * the k component of the cross product when considering the two vectors to
728 * be in the i-j plane. The direction (sign) of the result can be useful to
729 * determine the relative orientation of the two vectors.
731 static double crossProductK(const Point
const* p1
, const Point
const* p2
,
732 const Point
const* p3
, const Point
const* p4
)
734 return ((double) p2
->x
- p1
->x
) * ((double) p4
->y
- p3
->y
) - ((double)
735 p2
->y
- p1
->y
) * ((double) p4
->x
- p3
->x
);
740 * Free a container of FactorsCHull
743 * syncState: container for synchronization data.
744 * allFactors: container of Factors
746 static void freeAllFactors(const SyncState
* const syncState
, FactorsCHull
**
751 for (i
= 0; i
< syncState
->traceNb
; i
++)
753 for (j
= 0; j
<= i
; j
++)
755 FactorsCHull
* factorsCHull
;
757 factorsCHull
= &allFactors
[i
][j
];
758 if (factorsCHull
->type
== MIDDLE
|| factorsCHull
->type
==
759 INCOMPLETE
|| factorsCHull
->type
== ABSENT
)
761 free(factorsCHull
->min
);
762 free(factorsCHull
->max
);
764 else if (factorsCHull
->type
== SCREWED
)
766 if (factorsCHull
->min
!= NULL
)
768 free(factorsCHull
->min
);
770 if (factorsCHull
->max
!= NULL
)
772 free(factorsCHull
->max
);
776 if (factorsCHull
->type
== EXACT
|| factorsCHull
->type
== MIDDLE
||
777 factorsCHull
->type
== FALLBACK
)
779 free(factorsCHull
->approx
);
789 * Analyze the convex hulls to determine the synchronization factors between
790 * each pair of trace.
793 * syncState container for synchronization data.
796 * FactorsCHull*[TraceNum][TraceNum] array. See the documentation for the
797 * member allFactors of AnalysisStatsCHull.
799 static FactorsCHull
** calculateAllFactors(SyncState
* const syncState
)
801 unsigned int traceNumA
, traceNumB
;
802 FactorsCHull
** allFactors
;
803 AnalysisDataCHull
* analysisData
;
805 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
807 // Allocate allFactors and calculate min and max
808 allFactors
= malloc(syncState
->traceNb
* sizeof(FactorsCHull
*));
809 for (traceNumA
= 0; traceNumA
< syncState
->traceNb
; traceNumA
++)
811 allFactors
[traceNumA
]= malloc((traceNumA
+ 1) * sizeof(FactorsCHull
));
813 allFactors
[traceNumA
][traceNumA
].type
= EXACT
;
814 allFactors
[traceNumA
][traceNumA
].approx
= malloc(sizeof(Factors
));
815 allFactors
[traceNumA
][traceNumA
].approx
->drift
= 1.;
816 allFactors
[traceNumA
][traceNumA
].approx
->offset
= 0.;
818 for (traceNumB
= 0; traceNumB
< traceNumA
; traceNumB
++)
825 size_t factorsOffset
;
827 {MINIMUM
, offsetof(FactorsCHull
, min
)},
828 {MAXIMUM
, offsetof(FactorsCHull
, max
)}
831 cr
= analysisData
->hullArray
[traceNumB
][traceNumA
];
832 cs
= analysisData
->hullArray
[traceNumA
][traceNumB
];
834 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
836 g_debug("allFactors[%u][%u].%s = calculateFactorsExact(cr= hullArray[%u][%u], cs= hullArray[%u][%u], %s)",
837 traceNumA
, traceNumB
, loopValues
[i
].factorsOffset
==
838 offsetof(FactorsCHull
, min
) ? "min" : "max", traceNumB
,
839 traceNumA
, traceNumA
, traceNumB
, loopValues
[i
].lineType
==
840 MINIMUM
? "MINIMUM" : "MAXIMUM");
841 *((Factors
**) ((void*) &allFactors
[traceNumA
][traceNumB
] +
842 loopValues
[i
].factorsOffset
))=
843 calculateFactorsExact(cr
, cs
, loopValues
[i
].lineType
);
848 // Calculate approx when possible
849 for (traceNumA
= 0; traceNumA
< syncState
->traceNb
; traceNumA
++)
851 for (traceNumB
= 0; traceNumB
< traceNumA
; traceNumB
++)
853 FactorsCHull
* factorsCHull
;
855 factorsCHull
= &allFactors
[traceNumA
][traceNumB
];
856 if (factorsCHull
->min
== NULL
&& factorsCHull
->max
== NULL
)
858 factorsCHull
->type
= FALLBACK
;
859 calculateFactorsFallback(analysisData
->hullArray
[traceNumB
][traceNumA
],
860 analysisData
->hullArray
[traceNumA
][traceNumB
],
861 &allFactors
[traceNumA
][traceNumB
]);
863 else if (factorsCHull
->min
!= NULL
&& factorsCHull
->max
!= NULL
)
865 if (factorsCHull
->min
->drift
!= -INFINITY
&&
866 factorsCHull
->max
->drift
!= INFINITY
)
868 factorsCHull
->type
= MIDDLE
;
869 calculateFactorsMiddle(factorsCHull
);
871 else if (factorsCHull
->min
->drift
!= -INFINITY
||
872 factorsCHull
->max
->drift
!= INFINITY
)
874 factorsCHull
->type
= INCOMPLETE
;
878 factorsCHull
->type
= ABSENT
;
883 //g_assert_not_reached();
884 factorsCHull
->type
= SCREWED
;
893 /* Calculate approximative factors based on minimum and maximum limits. The
894 * best approximation to make is the interior bissector of the angle formed by
895 * the minimum and maximum lines.
897 * The formulae used come from [Haddad, Yoram: Performance dans les systèmes
898 * répartis: des outils pour les mesures, Université de Paris-Sud, Centre
899 * d'Orsay, September 1988] Section 6.1 p.44
901 * The reasoning for choosing this estimator comes from [Duda, A., Harrus, G.,
902 * Haddad, Y., and Bernard, G.: Estimating global time in distributed systems,
903 * Proc. 7th Int. Conf. on Distributed Computing Systems, Berlin, volume 18,
907 * factors: contains the min and max limits, used to store the result
909 static void calculateFactorsMiddle(FactorsCHull
* factors
)
911 double amin
, amax
, bmin
, bmax
, bhat
;
913 amin
= factors
->max
->offset
;
914 amax
= factors
->min
->offset
;
915 bmin
= factors
->min
->drift
;
916 bmax
= factors
->max
->drift
;
918 g_assert_cmpfloat(bmax
, >, bmin
);
920 factors
->approx
= malloc(sizeof(Factors
));
921 bhat
= (bmax
* bmin
- 1. + sqrt(1. + pow(bmax
, 2.) * pow(bmin
, 2.) +
922 pow(bmax
, 2.) + pow(bmin
, 2.))) / (bmax
+ bmin
);
923 factors
->approx
->offset
= amax
- (amax
- amin
) / 2. * (pow(bhat
, 2.) + 1.)
924 / (1. + bhat
* bmax
);
925 factors
->approx
->drift
= bhat
;
926 factors
->accuracy
= bmax
- bmin
;
931 * Analyze the convex hulls to determine the minimum or maximum
932 * synchronization factors between one pair of trace.
934 * This implements and improves upon the algorithm in [Haddad, Yoram:
935 * Performance dans les systèmes répartis: des outils pour les mesures,
936 * Université de Paris-Sud, Centre d'Orsay, September 1988] Section 6.2 p.47
938 * Some degenerate cases are possible:
939 * 1) the result is unbounded. In that case, when searching for the maximum
940 * factors, result->drift= INFINITY; result->offset= -INFINITY. When
941 * searching for the minimum factors, it is the opposite. It is not
942 * possible to improve the situation with this data.
943 * 2) no line can be above the upper hull and below the lower hull. This is
944 * because the hulls intersect each other or are reversed. This means that
945 * an assertion was false. Most probably, the clocks are not linear. It is
946 * possible to repeat the search with another algorithm that will find a
947 * "best effort" approximation. See calculateFactorsApprox().
950 * cu: the upper half-convex hull, the line must pass above this
951 * and touch it in one point
952 * cl: the lower half-convex hull, the line must pass below this
953 * and touch it in one point
954 * lineType: search for minimum or maximum factors
957 * If a result is found, a struct Factors is allocated, filed with the
958 * result and returned
959 * NULL otherwise, degenerate case 2 is in effect
961 static Factors
* calculateFactorsExact(GQueue
* const cu
, GQueue
* const cl
, const
967 double inversionFactor
;
970 g_debug("calculateFactorsExact(cu= %p, cl= %p, %s)", cu
, cl
, lineType
==
971 MINIMUM
? "MINIMUM" : "MAXIMUM");
973 if (lineType
== MINIMUM
)
977 inversionFactor
= -1.;
989 // Check for degenerate case 1
990 if (c1
->length
== 0 || c2
->length
== 0 || ((Point
*) g_queue_peek_nth(c1
,
991 i1
))->x
>= ((Point
*) g_queue_peek_nth(c2
, i2
))->x
)
993 result
= malloc(sizeof(Factors
));
994 if (lineType
== MINIMUM
)
996 result
->drift
= -INFINITY
;
997 result
->offset
= INFINITY
;
1001 result
->drift
= INFINITY
;
1002 result
->offset
= -INFINITY
;
1014 g_queue_peek_nth(c1
, i1
),
1015 g_queue_peek_nth(c2
, i2
),
1016 g_queue_peek_nth(c1
, i1
),
1017 g_queue_peek_nth(c2
, i2
- 1)) * inversionFactor
< 0.
1020 if (((Point
*) g_queue_peek_nth(c1
, i1
))->x
1021 < ((Point
*) g_queue_peek_nth(c2
, i2
- 1))->x
)
1027 // Degenerate case 2
1033 i1
+ 1 < c1
->length
- 1
1035 g_queue_peek_nth(c1
, i1
),
1036 g_queue_peek_nth(c2
, i2
),
1037 g_queue_peek_nth(c1
, i1
+ 1),
1038 g_queue_peek_nth(c2
, i2
)) * inversionFactor
< 0.
1041 if (((Point
*) g_queue_peek_nth(c1
, i1
+ 1))->x
1042 < ((Point
*) g_queue_peek_nth(c2
, i2
))->x
)
1048 // Degenerate case 2
1056 g_queue_peek_nth(c1
, i1
),
1057 g_queue_peek_nth(c2
, i2
),
1058 g_queue_peek_nth(c1
, i1
),
1059 g_queue_peek_nth(c2
, i2
- 1)) * inversionFactor
< 0.
1062 p1
= g_queue_peek_nth(c1
, i1
);
1063 p2
= g_queue_peek_nth(c2
, i2
);
1065 g_debug("Resulting points are: c1[i1]: x= %llu y= %llu c2[i2]: x= %llu y= %llu",
1066 p1
->x
, p1
->y
, p2
->x
, p2
->y
);
1068 result
= malloc(sizeof(Factors
));
1069 result
->drift
= slope(p1
, p2
);
1070 result
->offset
= intercept(p1
, p2
);
1072 g_debug("Resulting factors are: drift= %g offset= %g", result
->drift
, result
->offset
);
1079 * Analyze the convex hulls to determine approximate synchronization factors
1080 * between one pair of trace when there is no line that can fit in the
1081 * corridor separating them.
1083 * This implements the algorithm in [Ashton, P.: Algorithms for Off-line Clock
1084 * Synchronisation, University of Canterbury, December 1995, 26] Section 4.2.2
1087 * For each point p1 in cr
1088 * For each point p2 in cs
1090 * Calculate the line paramaters
1091 * For each point p3 in each convex hull
1092 * If p3 is on the wrong side of the line
1094 * If error < errorMin
1098 * cr: the upper half-convex hull
1099 * cs: the lower half-convex hull
1100 * result: a pointer to the pre-allocated struct where the results
1103 static void calculateFactorsFallback(GQueue
* const cr
, GQueue
* const cs
,
1104 FactorsCHull
* const result
)
1106 unsigned int i
, j
, k
;
1111 approx
= malloc(sizeof(Factors
));
1113 for (i
= 0; i
< cs
->length
; i
++)
1115 for (j
= 0; j
< cr
->length
; j
++)
1122 if (((Point
*) g_queue_peek_nth(cs
, i
))->x
< ((Point
*)g_queue_peek_nth(cr
, j
))->x
)
1124 p1
= *(Point
*)g_queue_peek_nth(cs
, i
);
1125 p2
= *(Point
*)g_queue_peek_nth(cr
, j
);
1129 p1
= *(Point
*)g_queue_peek_nth(cr
, j
);
1130 p2
= *(Point
*)g_queue_peek_nth(cs
, i
);
1133 // The lower hull should be above the point
1134 for (k
= 0; k
< cs
->length
; k
++)
1136 if (jointCmp(&p1
, &p2
, g_queue_peek_nth(cs
, k
)) < 0.)
1138 error
+= verticalDistance(&p1
, &p2
, g_queue_peek_nth(cs
, k
));
1142 // The upper hull should be below the point
1143 for (k
= 0; k
< cr
->length
; k
++)
1145 if (jointCmp(&p1
, &p2
, g_queue_peek_nth(cr
, k
)) > 0.)
1147 error
+= verticalDistance(&p1
, &p2
, g_queue_peek_nth(cr
, k
));
1151 if (error
< errorMin
)
1153 g_debug("Fallback: i= %u j= %u is a better match (error= %g)", i
, j
, error
);
1154 approx
->drift
= slope(&p1
, &p2
);
1155 approx
->offset
= intercept(&p1
, &p2
);
1161 result
->approx
= approx
;
1162 result
->accuracy
= errorMin
;
1167 * Calculate the vertical distance between a line and a point
1170 * p1, p2: Two points defining the line
1174 * the vertical distance
1176 static double verticalDistance(Point
* p1
, Point
* p2
, Point
* const point
)
1178 return fabs(slope(p1
, p2
) * point
->x
+ intercept(p1
, p2
) - point
->y
);
1183 * Calculate the slope between two points
1186 * p1, p2 the two points
1191 static double slope(const Point
* const p1
, const Point
* const p2
)
1193 return ((double) p2
->y
- p1
->y
) / (p2
->x
- p1
->x
);
1197 /* Calculate the y-intercept of a line that passes by two points
1200 * p1, p2 the two points
1205 static double intercept(const Point
* const p1
, const Point
* const p2
)
1207 return ((double) p2
->y
* p1
->x
- (double) p1
->y
* p2
->x
) / ((double) p1
->x
- p2
->x
);
1212 * Calculate a resulting offset and drift for each trace.
1214 * Traces are assembled in groups. A group is an "island" of nodes/traces that
1215 * exchanged messages. A reference is determined for each group by using a
1216 * shortest path search based on the accuracy of the approximation. This also
1217 * forms a tree of the best way to relate each node's clock to the reference's
1218 * based on the accuracy. Sometimes it may be necessary or advantageous to
1219 * propagate the factors through intermediary clocks. Resulting factors for
1220 * each trace are determined based on this tree.
1222 * This part was not the focus of my research. The algorithm used here is
1223 * inexact in some ways:
1224 * 1) The reference used may not actually be the best one to use. This is
1225 * because the accuracy is not corrected based on the drift during the
1226 * shortest path search.
1227 * 2) The min and max factors are not propagated and are no longer valid.
1228 * 3) Approximations of different types (MIDDLE and FALLBACK) are compared
1229 * together. The "accuracy" parameters of these have different meanings and
1230 * are not readily comparable.
1232 * Nevertheless, the result is satisfactory. You just can't tell "how much" it
1235 * Two alternative (and subtly different) ways of propagating factors to
1236 * preserve min and max bondaries have been proposed, see:
1237 * [Duda, A., Harrus, G., Haddad, Y., and Bernard, G.: Estimating global time
1238 * in distributed systems, Proc. 7th Int. Conf. on Distributed Computing
1239 * Systems, Berlin, volume 18, 1987] p.304
1241 * [Jezequel, J.M., and Jard, C.: Building a global clock for observing
1242 * computations in distributed memory parallel computers, Concurrency:
1243 * Practice and Experience 8(1), volume 8, John Wiley & Sons, Ltd Chichester,
1244 * 1996, 32] Section 5; which is mostly the same as
1245 * [Jezequel, J.M.: Building a global time on parallel machines, Proceedings
1246 * of the 3rd International Workshop on Distributed Algorithms, LNCS, volume
1247 * 392, 136–147, 1989] Section 5
1250 * syncState: container for synchronization data.
1251 * allFactors: offset and drift between each pair of traces
1254 * Factors[traceNb] synchronization factors for each trace
1256 static GArray
* reduceFactors(SyncState
* const syncState
, FactorsCHull
** const
1261 unsigned int** predecessors
;
1262 double* distanceSums
;
1263 unsigned int* references
;
1266 // Solve the all-pairs shortest path problem using the Floyd-Warshall
1268 floydWarshall(syncState
, allFactors
, &distances
, &predecessors
);
1270 /* Find the reference for each node
1272 * First calculate, for each node, the sum of the distances to each other
1273 * node it can reach.
1275 * Then, go through each "island" of traces to find the trace that has the
1276 * lowest distance sum. Assign this trace as the reference to each trace
1279 distanceSums
= malloc(syncState
->traceNb
* sizeof(double));
1280 for (i
= 0; i
< syncState
->traceNb
; i
++)
1282 distanceSums
[i
]= 0.;
1283 for (j
= 0; j
< syncState
->traceNb
; j
++)
1285 distanceSums
[i
]+= distances
[i
][j
];
1289 references
= malloc(syncState
->traceNb
* sizeof(unsigned int));
1290 for (i
= 0; i
< syncState
->traceNb
; i
++)
1292 references
[i
]= UINT_MAX
;
1294 for (i
= 0; i
< syncState
->traceNb
; i
++)
1296 if (references
[i
] == UINT_MAX
)
1298 unsigned int reference
;
1299 double distanceSumMin
;
1301 // A node is its own reference by default
1303 distanceSumMin
= INFINITY
;
1304 for (j
= 0; j
< syncState
->traceNb
; j
++)
1306 if (distances
[i
][j
] != INFINITY
&& distanceSums
[j
] <
1310 distanceSumMin
= distanceSums
[j
];
1313 for (j
= 0; j
< syncState
->traceNb
; j
++)
1315 if (distances
[i
][j
] != INFINITY
)
1317 references
[j
]= reference
;
1323 for (i
= 0; i
< syncState
->traceNb
; i
++)
1330 /* For each trace, calculate the factors based on their corresponding
1331 * tree. The tree is rooted at the reference and the shortest path to each
1332 * other nodes are the branches.
1334 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
1335 syncState
->traceNb
);
1336 g_array_set_size(factors
, syncState
->traceNb
);
1337 for (i
= 0; i
< syncState
->traceNb
; i
++)
1339 getFactors(allFactors
, predecessors
, references
, i
, &g_array_index(factors
,
1343 for (i
= 0; i
< syncState
->traceNb
; i
++)
1345 free(predecessors
[i
]);
1355 * Perform an all-source shortest path search using the Floyd-Warshall
1358 * The algorithm is implemented accoding to the description here:
1359 * http://web.mit.edu/urban_or_book/www/book/chapter6/6.2.2.html
1362 * syncState: container for synchronization data.
1363 * allFactors: offset and drift between each pair of traces
1364 * distances: resulting matrix of the length of the shortest path between
1365 * two nodes. If there is no path between two nodes, the
1366 * length is INFINITY
1367 * predecessors: resulting matrix of each node's predecessor on the shortest
1368 * path between two nodes
1370 static void floydWarshall(SyncState
* const syncState
, FactorsCHull
** const
1371 allFactors
, double*** const distances
, unsigned int*** const
1374 unsigned int i
, j
, k
;
1376 // Setup initial conditions
1377 *distances
= malloc(syncState
->traceNb
* sizeof(double*));
1378 *predecessors
= malloc(syncState
->traceNb
* sizeof(unsigned int*));
1379 for (i
= 0; i
< syncState
->traceNb
; i
++)
1381 (*distances
)[i
]= malloc(syncState
->traceNb
* sizeof(double));
1382 for (j
= 0; j
< syncState
->traceNb
; j
++)
1386 g_assert(allFactors
[i
][j
].type
== EXACT
);
1388 (*distances
)[i
][j
]= 0.;
1392 unsigned int row
, col
;
1405 if (allFactors
[row
][col
].type
== MIDDLE
||
1406 allFactors
[row
][col
].type
== FALLBACK
)
1408 (*distances
)[i
][j
]= allFactors
[row
][col
].accuracy
;
1410 else if (allFactors
[row
][col
].type
== INCOMPLETE
||
1411 allFactors
[row
][col
].type
== SCREWED
||
1412 allFactors
[row
][col
].type
== ABSENT
)
1414 (*distances
)[i
][j
]= INFINITY
;
1418 g_assert_not_reached();
1423 (*predecessors
)[i
]= malloc(syncState
->traceNb
* sizeof(unsigned int));
1424 for (j
= 0; j
< syncState
->traceNb
; j
++)
1428 (*predecessors
)[i
][j
]= i
;
1432 (*predecessors
)[i
][j
]= UINT_MAX
;
1437 // Run the iterations
1438 for (k
= 0; k
< syncState
->traceNb
; k
++)
1440 for (i
= 0; i
< syncState
->traceNb
; i
++)
1442 for (j
= 0; j
< syncState
->traceNb
; j
++)
1446 distanceMin
= MIN((*distances
)[i
][j
], (*distances
)[i
][k
] +
1447 (*distances
)[k
][j
]);
1449 if (distanceMin
!= (*distances
)[i
][j
])
1451 (*predecessors
)[i
][j
]= (*predecessors
)[k
][j
];
1454 (*distances
)[i
][j
]= distanceMin
;
1462 * Cummulate the time correction factors to convert a node's time to its
1464 * This function recursively calls itself until it reaches the reference node.
1467 * allFactors: offset and drift between each pair of traces
1468 * predecessors: matrix of each node's predecessor on the shortest
1469 * path between two nodes
1470 * references: reference node for each node
1471 * traceNum: node for which to find the factors
1472 * factors: resulting factors
1474 static void getFactors(FactorsCHull
** const allFactors
, unsigned int** const
1475 predecessors
, unsigned int* const references
, const unsigned int traceNum
,
1476 Factors
* const factors
)
1478 unsigned int reference
;
1480 reference
= references
[traceNum
];
1482 if (reference
== traceNum
)
1484 factors
->offset
= 0.;
1489 Factors previousVertexFactors
;
1491 getFactors(allFactors
, predecessors
, references
,
1492 predecessors
[reference
][traceNum
], &previousVertexFactors
);
1494 // convertir de traceNum à reference
1496 // allFactors convertit de col à row
1498 if (reference
> traceNum
)
1500 factors
->offset
= previousVertexFactors
.drift
*
1501 allFactors
[reference
][traceNum
].approx
->offset
+
1502 previousVertexFactors
.offset
;
1503 factors
->drift
= previousVertexFactors
.drift
*
1504 allFactors
[reference
][traceNum
].approx
->drift
;
1508 factors
->offset
= previousVertexFactors
.drift
* (-1. *
1509 allFactors
[traceNum
][reference
].approx
->offset
/
1510 allFactors
[traceNum
][reference
].approx
->drift
) +
1511 previousVertexFactors
.offset
;
1512 factors
->drift
= previousVertexFactors
.drift
* (1. /
1513 allFactors
[traceNum
][reference
].approx
->drift
);
1520 * Write the analysis-specific graph lines in the gnuplot script.
1523 * stream: stream where to write the data
1524 * syncState: container for synchronization data
1525 * i: first trace number
1526 * j: second trace number, garanteed to be larger than i
1528 void writeAnalysisGraphsPlotsCHull(FILE* stream
, SyncState
* const syncState
,
1529 const unsigned int i
, const unsigned int j
)
1531 AnalysisDataCHull
* analysisData
;
1532 FactorsCHull
* factorsCHull
;
1534 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
1537 "\t\"analysis_chull-%1$03d_to_%2$03d.data\" "
1538 "title \"Lower half-hull\" with linespoints "
1539 "linecolor rgb \"#015a01\" linetype 4 pointtype 8 pointsize 0.8, \\\n"
1540 "\t\"analysis_chull-%2$03d_to_%1$03d.data\" "
1541 "title \"Upper half-hull\" with linespoints "
1542 "linecolor rgb \"#003366\" linetype 4 pointtype 10 pointsize 0.8, \\\n",
1545 factorsCHull
= &analysisData
->graphsData
->allFactors
[j
][i
];
1546 if (factorsCHull
->type
== EXACT
)
1550 "title \"Exact conversion\" with lines "
1551 "linecolor rgb \"black\" linetype 1, \\\n",
1552 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
);
1554 else if (factorsCHull
->type
== MIDDLE
)
1557 "\t%.2f + %.10f * x "
1558 "title \"Min conversion\" with lines "
1559 "linecolor rgb \"black\" linetype 5, \\\n",
1560 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
);
1562 "\t%.2f + %.10f * x "
1563 "title \"Max conversion\" with lines "
1564 "linecolor rgb \"black\" linetype 8, \\\n",
1565 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
);
1567 "\t%.2f + %.10f * x "
1568 "title \"Middle conversion\" with lines "
1569 "linecolor rgb \"gray60\" linetype 1, \\\n",
1570 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
);
1572 else if (factorsCHull
->type
== FALLBACK
)
1575 "\t%.2f + %.10f * x "
1576 "title \"Fallback conversion\" with lines "
1577 "linecolor rgb \"gray60\" linetype 1, \\\n",
1578 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
);
1580 else if (factorsCHull
->type
== INCOMPLETE
)
1582 if (factorsCHull
->min
->drift
!= -INFINITY
)
1585 "\t%.2f + %.10f * x "
1586 "title \"Min conversion\" with lines "
1587 "linecolor rgb \"black\" linetype 5, \\\n",
1588 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
);
1591 if (factorsCHull
->max
->drift
!= INFINITY
)
1594 "\t%.2f + %.10f * x "
1595 "title \"Max conversion\" with lines "
1596 "linecolor rgb \"black\" linetype 8, \\\n",
1597 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
);
1600 else if (factorsCHull
->type
== SCREWED
)
1602 if (factorsCHull
->min
!= NULL
&& factorsCHull
->min
->drift
!= -INFINITY
)
1605 "\t%.2f + %.10f * x "
1606 "title \"Min conversion\" with lines "
1607 "linecolor rgb \"black\" linetype 5, \\\n",
1608 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
);
1611 if (factorsCHull
->max
!= NULL
&& factorsCHull
->max
->drift
!= INFINITY
)
1614 "\t%.2f + %.10f * x "
1615 "title \"Max conversion\" with lines "
1616 "linecolor rgb \"black\" linetype 8, \\\n",
1617 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
);
1620 else if (factorsCHull
->type
== ABSENT
)
1625 g_assert_not_reached();