1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
4 * This program is free software: you can redistribute it and/or modify it
5 * under the terms of the GNU Lesser General Public License as published by
6 * the Free Software Foundation, either version 2.1 of the License, or (at
7 * your option) any later version.
9 * This program is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
12 * License for more details.
14 * You should have received a copy of the GNU Lesser General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 #define _ISOC99_SOURCE
32 #include "sync_chain.h"
34 #include "event_analysis_chull.h"
54 GArray
* iArray
, * jArray
, * aArray
;
59 // Functions common to all analysis modules
60 static void initAnalysisCHull(SyncState
* const syncState
);
61 static void destroyAnalysisCHull(SyncState
* const syncState
);
63 static void analyzeMessageCHull(SyncState
* const syncState
, Message
* const
65 static AllFactors
* finalizeAnalysisCHull(SyncState
* const syncState
);
66 static void printAnalysisStatsCHull(SyncState
* const syncState
);
67 static void writeAnalysisTraceTraceForePlotsCHull(SyncState
* const syncState
,
68 const unsigned int i
, const unsigned int j
);
70 // Functions specific to this module
71 static void openGraphFiles(SyncState
* const syncState
);
72 static void closeGraphFiles(SyncState
* const syncState
);
73 static void writeGraphFiles(SyncState
* const syncState
);
74 static void gfDumpHullToFile(gpointer data
, gpointer userData
);
76 AllFactors
* calculateAllFactors(struct _SyncState
* const syncState
);
77 void calculateFactorsMiddle(PairFactors
* const factors
);
78 static Factors
* calculateFactorsExact(GQueue
* const cu
, GQueue
* const cl
, const
79 LineType lineType
) __attribute__((pure
));
80 static void calculateFactorsFallback(GQueue
* const cr
, GQueue
* const cs
,
81 PairFactors
* const result
);
82 static void grahamScan(GQueue
* const hull
, Point
* const newPoint
, const
84 static int jointCmp(const Point
* const p1
, const Point
* const p2
, const Point
*
85 const p3
) __attribute__((pure
));
86 static double crossProductK(const Point
const* p1
, const Point
const* p2
,
87 const Point
const* p3
, const Point
const* p4
) __attribute__((pure
));
88 static double slope(const Point
* const p1
, const Point
* const p2
)
89 __attribute__((pure
));
90 static double intercept(const Point
* const p1
, const Point
* const p2
)
91 __attribute__((pure
));
92 static double verticalDistance(Point
* p1
, Point
* p2
, Point
* const point
)
93 __attribute__((pure
));
95 static void gfPointDestroy(gpointer data
, gpointer userData
);
97 // The next group of functions is only needed when computing synchronization
100 static AllFactors
* finalizeAnalysisCHullLP(SyncState
* const syncState
);
101 static void writeAnalysisTraceTimeBackPlotsCHull(SyncState
* const syncState
,
102 const unsigned int i
, const unsigned int j
);
103 static void writeAnalysisTraceTimeForePlotsCHull(SyncState
* const syncState
,
104 const unsigned int i
, const unsigned int j
);
105 static void writeAnalysisTraceTraceBackPlotsCHull(SyncState
* const syncState
,
106 const unsigned int i
, const unsigned int j
);
108 static glp_prob
* lpCreateProblem(GQueue
* const lowerHull
, GQueue
* const
110 static void gfLPAddRow(gpointer data
, gpointer user_data
);
111 static Factors
* calculateFactorsLP(glp_prob
* const lp
, const int direction
);
112 static void calculateCompleteFactorsLP(glp_prob
* const lp
, PairFactors
*
114 void timeCorrectionLP(glp_prob
* const lp
, const PairFactors
* const lpFactors
,
115 const uint64_t time
, CorrectedTime
* const correctedTime
);
117 static void gfAddAbsiscaToArray(gpointer data
, gpointer user_data
);
118 static gint
gcfCompareUint64(gconstpointer a
, gconstpointer b
);
120 static inline AllFactors
* finalizeAnalysisCHullLP(SyncState
* const syncState
)
128 static AnalysisModule analysisModuleCHull
= {
130 .initAnalysis
= &initAnalysisCHull
,
131 .destroyAnalysis
= &destroyAnalysisCHull
,
132 .analyzeMessage
= &analyzeMessageCHull
,
133 .finalizeAnalysis
= &finalizeAnalysisCHull
,
134 .printAnalysisStats
= &printAnalysisStatsCHull
,
137 .writeTraceTimeBackPlots
= &writeAnalysisTraceTimeBackPlotsCHull
,
138 .writeTraceTimeForePlots
= &writeAnalysisTraceTimeForePlotsCHull
,
139 .writeTraceTraceBackPlots
= &writeAnalysisTraceTraceBackPlotsCHull
,
141 .writeTraceTraceForePlots
= &writeAnalysisTraceTraceForePlotsCHull
,
147 * Analysis module registering function
149 void registerAnalysisCHull()
151 g_queue_push_tail(&analysisModules
, &analysisModuleCHull
);
156 * Analysis init function
158 * This function is called at the beginning of a synchronization run for a set
161 * Allocate some of the analysis specific data structures
164 * syncState container for synchronization data.
165 * This function allocates or initializes these analysisData
170 static void initAnalysisCHull(SyncState
* const syncState
)
173 AnalysisDataCHull
* analysisData
;
175 analysisData
= malloc(sizeof(AnalysisDataCHull
));
176 syncState
->analysisData
= analysisData
;
178 analysisData
->hullArray
= malloc(syncState
->traceNb
* sizeof(GQueue
**));
179 for (i
= 0; i
< syncState
->traceNb
; i
++)
181 analysisData
->hullArray
[i
]= malloc(syncState
->traceNb
* sizeof(GQueue
*));
183 for (j
= 0; j
< syncState
->traceNb
; j
++)
185 analysisData
->hullArray
[i
][j
]= g_queue_new();
189 analysisData
->lps
= NULL
;
192 if (syncState
->stats
)
194 analysisData
->stats
= calloc(1, sizeof(AnalysisStatsCHull
));
197 if (syncState
->graphsStream
)
199 analysisData
->graphsData
= calloc(1, sizeof(AnalysisGraphsDataCHull
));
200 openGraphFiles(syncState
);
206 * Create and open files used to store convex hull points to genereate
207 * graphs. Allocate and populate array to store file pointers.
210 * syncState: container for synchronization data
212 static void openGraphFiles(SyncState
* const syncState
)
218 AnalysisDataCHull
* analysisData
;
220 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
222 cwd
= changeToGraphsDir(syncState
->graphsDir
);
224 analysisData
->graphsData
->hullPoints
= malloc(syncState
->traceNb
*
226 for (i
= 0; i
< syncState
->traceNb
; i
++)
228 analysisData
->graphsData
->hullPoints
[i
]= malloc(syncState
->traceNb
*
230 for (j
= 0; j
< syncState
->traceNb
; j
++)
234 retval
= snprintf(name
, sizeof(name
),
235 "analysis_chull-%03u_to_%03u.data", j
, i
);
236 if (retval
> sizeof(name
) - 1)
238 name
[sizeof(name
) - 1]= '\0';
240 if ((analysisData
->graphsData
->hullPoints
[i
][j
]= fopen(name
, "w")) ==
243 g_error(strerror(errno
));
252 g_error(strerror(errno
));
259 * Write hull points to files to generate graphs.
262 * syncState: container for synchronization data
264 static void writeGraphFiles(SyncState
* const syncState
)
267 AnalysisDataCHull
* analysisData
;
269 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
271 for (i
= 0; i
< syncState
->traceNb
; i
++)
273 for (j
= 0; j
< syncState
->traceNb
; j
++)
277 g_queue_foreach(analysisData
->hullArray
[i
][j
],
279 analysisData
->graphsData
->hullPoints
[i
][j
]);
287 * A GFunc for g_queue_foreach. Write a hull point to a file used to generate
291 * data: Point*, point to write to the file
292 * userData: FILE*, file pointer where to write the point
294 static void gfDumpHullToFile(gpointer data
, gpointer userData
)
298 point
= (Point
*) data
;
299 fprintf((FILE*) userData
, "%20" PRIu64
" %20" PRIu64
"\n", point
->x
, point
->y
);
304 * Close files used to store convex hull points to generate graphs.
305 * Deallocate array to store file pointers.
308 * syncState: container for synchronization data
310 static void closeGraphFiles(SyncState
* const syncState
)
313 AnalysisDataCHull
* analysisData
;
316 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
318 if (analysisData
->graphsData
->hullPoints
== NULL
)
323 for (i
= 0; i
< syncState
->traceNb
; i
++)
325 for (j
= 0; j
< syncState
->traceNb
; j
++)
329 retval
= fclose(analysisData
->graphsData
->hullPoints
[i
][j
]);
332 g_error(strerror(errno
));
336 free(analysisData
->graphsData
->hullPoints
[i
]);
338 free(analysisData
->graphsData
->hullPoints
);
339 analysisData
->graphsData
->hullPoints
= NULL
;
344 * Analysis destroy function
346 * Free the analysis specific data structures
349 * syncState container for synchronization data.
350 * This function deallocates these analysisData members:
354 static void destroyAnalysisCHull(SyncState
* const syncState
)
357 AnalysisDataCHull
* analysisData
;
359 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
361 if (analysisData
== NULL
)
366 for (i
= 0; i
< syncState
->traceNb
; i
++)
368 for (j
= 0; j
< syncState
->traceNb
; j
++)
370 g_queue_foreach(analysisData
->hullArray
[i
][j
], gfPointDestroy
,
372 g_queue_free(analysisData
->hullArray
[i
][j
]);
374 free(analysisData
->hullArray
[i
]);
376 free(analysisData
->hullArray
);
379 if (analysisData
->lps
!= NULL
)
381 for (i
= 0; i
< syncState
->traceNb
; i
++)
385 for (j
= 0; j
< i
; j
++)
387 // There seems to be a memory leak in glpk, valgrind reports a
388 // loss (reachable) even if the problem is deleted
389 glp_delete_prob(analysisData
->lps
[i
][j
]);
391 free(analysisData
->lps
[i
]);
393 free(analysisData
->lps
);
397 if (syncState
->stats
)
399 freeAllFactors(analysisData
->stats
->allFactors
, syncState
->traceNb
);
400 freeAllFactors(analysisData
->stats
->geoFactors
, syncState
->traceNb
);
403 freeAllFactors(analysisData
->stats
->lpFactors
, syncState
->traceNb
);
406 free(analysisData
->stats
);
409 if (syncState
->graphsStream
)
411 AnalysisGraphsDataCHull
* graphs
= analysisData
->graphsData
;
413 if (graphs
->hullPoints
!= NULL
)
415 closeGraphFiles(syncState
);
418 freeAllFactors(graphs
->allFactors
, syncState
->traceNb
);
421 freeAllFactors(graphs
->lpFactors
, syncState
->traceNb
);
424 free(analysisData
->graphsData
);
427 free(syncState
->analysisData
);
428 syncState
->analysisData
= NULL
;
433 * Perform analysis on an event pair.
436 * syncState container for synchronization data
437 * message structure containing the events
439 static void analyzeMessageCHull(SyncState
* const syncState
, Message
* const message
)
441 AnalysisDataCHull
* analysisData
;
446 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
448 newPoint
= malloc(sizeof(Point
));
449 if (message
->inE
->traceNum
< message
->outE
->traceNum
)
451 // CA is inE->traceNum
452 newPoint
->x
= message
->inE
->cpuTime
;
453 newPoint
->y
= message
->outE
->cpuTime
;
455 g_debug("Reception point hullArray[%lu][%lu] "
456 "x= inE->time= %" PRIu64
" y= outE->time= %" PRIu64
,
457 message
->inE
->traceNum
, message
->outE
->traceNum
, newPoint
->x
,
462 // CA is outE->traceNum
463 newPoint
->x
= message
->outE
->cpuTime
;
464 newPoint
->y
= message
->inE
->cpuTime
;
466 g_debug("Send point hullArray[%lu][%lu] "
467 "x= inE->time= %" PRIu64
" y= outE->time= %" PRIu64
,
468 message
->inE
->traceNum
, message
->outE
->traceNum
, newPoint
->x
,
473 analysisData
->hullArray
[message
->inE
->traceNum
][message
->outE
->traceNum
];
475 if (hull
->length
>= 1 && newPoint
->x
< ((Point
*)
476 g_queue_peek_tail(hull
))->x
)
478 if (syncState
->stats
)
480 analysisData
->stats
->dropped
++;
487 grahamScan(hull
, newPoint
, hullType
);
493 * Construct one half of a convex hull from abscissa-sorted points
496 * hull: the points already in the hull
497 * newPoint: a new point to consider
498 * type: which half of the hull to construct
500 static void grahamScan(GQueue
* const hull
, Point
* const newPoint
, const
505 g_debug("grahamScan(hull (length: %u), newPoint, %s)", hull
->length
, type
506 == LOWER
? "LOWER" : "UPPER");
517 if (hull
->length
>= 2)
519 g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d",
522 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
523 g_queue_peek_tail(hull
), newPoint
),
525 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
526 g_queue_peek_tail(hull
), newPoint
) * inversionFactor
);
528 while (hull
->length
>= 2 && jointCmp(g_queue_peek_nth(hull
, hull
->length
-
529 2), g_queue_peek_tail(hull
), newPoint
) * inversionFactor
<= 0)
531 g_debug("Removing hull[%u]", hull
->length
);
532 free((Point
*) g_queue_pop_tail(hull
));
534 if (hull
->length
>= 2)
536 g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d",
539 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
540 g_queue_peek_tail(hull
), newPoint
),
542 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
543 g_queue_peek_tail(hull
), newPoint
) * inversionFactor
);
546 g_queue_push_tail(hull
, newPoint
);
551 * Finalize the factor calculations
554 * syncState container for synchronization data.
557 * AllFactors* synchronization factors for each trace pair, the caller is
558 * responsible for freeing the structure
560 static AllFactors
* finalizeAnalysisCHull(SyncState
* const syncState
)
562 AnalysisDataCHull
* analysisData
;
563 AllFactors
* geoFactors
, * lpFactors
;
565 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
567 if (syncState
->graphsStream
&& analysisData
->graphsData
->hullPoints
!= NULL
)
569 writeGraphFiles(syncState
);
570 closeGraphFiles(syncState
);
573 geoFactors
= calculateAllFactors(syncState
);
574 lpFactors
= finalizeAnalysisCHullLP(syncState
);
576 if (syncState
->stats
)
578 geoFactors
->refCount
++;
579 analysisData
->stats
->geoFactors
= geoFactors
;
581 if (lpFactors
!= NULL
)
583 lpFactors
->refCount
++;
584 analysisData
->stats
->allFactors
= lpFactors
;
588 geoFactors
->refCount
++;
589 analysisData
->stats
->allFactors
= geoFactors
;
593 if (syncState
->graphsStream
)
595 if (lpFactors
!= NULL
)
597 lpFactors
->refCount
++;
598 analysisData
->graphsData
->allFactors
= lpFactors
;
602 geoFactors
->refCount
++;
603 analysisData
->graphsData
->allFactors
= geoFactors
;
607 if (lpFactors
!= NULL
)
609 freeAllFactors(geoFactors
, syncState
->traceNb
);
614 freeAllFactors(lpFactors
, syncState
->traceNb
);
621 * Print statistics related to analysis. Must be called after
625 * syncState container for synchronization data.
627 static void printAnalysisStatsCHull(SyncState
* const syncState
)
629 AnalysisDataCHull
* analysisData
;
632 if (!syncState
->stats
)
637 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
639 printf("Convex hull analysis stats:\n");
640 printf("\tout of order packets dropped from analysis: %u\n",
641 analysisData
->stats
->dropped
);
643 printf("\tNumber of points in convex hulls:\n");
645 for (i
= 0; i
< syncState
->traceNb
; i
++)
647 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
649 printf("\t\t%3d - %-3d: lower half-hull %-5u upper half-hull %-5u\n",
650 i
, j
, analysisData
->hullArray
[j
][i
]->length
,
651 analysisData
->hullArray
[i
][j
]->length
);
655 printf("\tIndividual synchronization factors:\n");
657 for (i
= 0; i
< syncState
->traceNb
; i
++)
659 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
661 PairFactors
* factorsCHull
;
663 factorsCHull
= &analysisData
->stats
->allFactors
->pairFactors
[j
][i
];
664 printf("\t\t%3d - %-3d: %s", i
, j
,
665 approxNames
[factorsCHull
->type
]);
667 if (factorsCHull
->type
== EXACT
)
669 printf(" a0= % 7g a1= 1 %c %7g\n",
670 factorsCHull
->approx
->offset
,
671 factorsCHull
->approx
->drift
< 0. ? '-' : '+',
672 fabs(factorsCHull
->approx
->drift
));
674 else if (factorsCHull
->type
== ACCURATE
)
676 printf("\n\t\t a0: % 7g to % 7g (delta= %7g)\n",
677 factorsCHull
->max
->offset
, factorsCHull
->min
->offset
,
678 factorsCHull
->min
->offset
- factorsCHull
->max
->offset
);
679 printf("\t\t a1: 1 %+7g to %+7g (delta= %7g)\n",
680 factorsCHull
->min
->drift
- 1., factorsCHull
->max
->drift
-
681 1., factorsCHull
->max
->drift
- factorsCHull
->min
->drift
);
683 else if (factorsCHull
->type
== APPROXIMATE
)
685 printf(" a0= % 7g a1= 1 %c %7g error= %7g\n",
686 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
687 - 1. < 0. ? '-' : '+', fabs(factorsCHull
->approx
->drift
-
688 1.), factorsCHull
->accuracy
);
690 else if (factorsCHull
->type
== INCOMPLETE
)
694 if (factorsCHull
->min
->drift
!= -INFINITY
)
696 printf("\t\t min: a0: % 7g a1: 1 %c %7g\n",
697 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
-
698 1. < 0 ? '-' : '+', fabs(factorsCHull
->min
->drift
-
701 if (factorsCHull
->max
->drift
!= INFINITY
)
703 printf("\t\t max: a0: % 7g a1: 1 %c %7g\n",
704 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
-
705 1. < 0 ? '-' : '+', fabs(factorsCHull
->max
->drift
-
709 else if (factorsCHull
->type
== FAIL
)
713 if (factorsCHull
->min
!= NULL
&& factorsCHull
->min
->drift
!= -INFINITY
)
715 printf("\t\t min: a0: % 7g a1: 1 %c %7g\n",
716 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
-
717 1. < 0 ? '-' : '+', fabs(factorsCHull
->min
->drift
-
720 if (factorsCHull
->max
!= NULL
&& factorsCHull
->max
->drift
!= INFINITY
)
722 printf("\t\t max: a0: % 7g a1: 1 %c %7g\n",
723 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
-
724 1. < 0 ? '-' : '+', fabs(factorsCHull
->max
->drift
-
728 else if (factorsCHull
->type
== ABSENT
)
734 g_assert_not_reached();
740 printf("\tFactor comparison:\n"
741 "\t\tTrace pair Factors type Differences (lp - chull)\n"
743 "\t\t Min Max Min Max\n");
745 for (i
= 0; i
< syncState
->traceNb
; i
++)
747 for (j
= 0; j
< i
; j
++)
749 PairFactors
* geoFactors
=
750 &analysisData
->stats
->geoFactors
->pairFactors
[i
][j
];
751 PairFactors
* lpFactors
=
752 &analysisData
->stats
->lpFactors
->pairFactors
[i
][j
];
754 printf("\t\t%3d - %-3d ", i
, j
);
755 if (lpFactors
->type
== geoFactors
->type
)
757 if (lpFactors
->type
== ACCURATE
)
759 printf("%-13s %-10.4g %-10.4g %-10.4g %.4g\n",
760 approxNames
[lpFactors
->type
],
761 lpFactors
->min
->offset
- geoFactors
->min
->offset
,
762 lpFactors
->max
->offset
- geoFactors
->max
->offset
,
763 lpFactors
->min
->drift
- geoFactors
->min
->drift
,
764 lpFactors
->max
->drift
- geoFactors
->max
->drift
);
766 else if (lpFactors
->type
== ABSENT
)
768 printf("%s\n", approxNames
[lpFactors
->type
]);
773 printf("Different! %s and %s\n", approxNames
[lpFactors
->type
],
774 approxNames
[geoFactors
->type
]);
783 * A GFunc for g_queue_foreach()
786 * data Point*, point to destroy
789 static void gfPointDestroy(gpointer data
, gpointer userData
)
793 point
= (Point
*) data
;
799 * Find out if a sequence of three points constitutes a "left turn" or a
803 * p1, p2, p3: The three points.
807 * 0 colinear (unlikely result since this uses floating point
811 static int jointCmp(const Point
const* p1
, const Point
const* p2
, const
815 const double fuzzFactor
= 0.;
817 result
= crossProductK(p1
, p2
, p1
, p3
);
818 g_debug("crossProductK(p1= (%" PRIu64
", %" PRIu64
"), "
819 "p2= (%" PRIu64
", %" PRIu64
"), p1= (%" PRIu64
", %" PRIu64
"), "
820 "p3= (%" PRIu64
", %" PRIu64
"))= %g",
821 p1
->x
, p1
->y
, p2
->x
, p2
->y
, p1
->x
, p1
->y
, p3
->x
, p3
->y
, result
);
822 if (result
< fuzzFactor
)
826 else if (result
> fuzzFactor
)
838 * Calculate the k component of the cross product of two vectors.
841 * p1, p2: start and end points of the first vector
842 * p3, p4: start and end points of the second vector
845 * the k component of the cross product when considering the two vectors to
846 * be in the i-j plane. The direction (sign) of the result can be useful to
847 * determine the relative orientation of the two vectors.
849 static double crossProductK(const Point
const* p1
, const Point
const* p2
,
850 const Point
const* p3
, const Point
const* p4
)
852 return ((double) p2
->x
- p1
->x
) * ((double) p4
->y
- p3
->y
) - ((double)
853 p2
->y
- p1
->y
) * ((double) p4
->x
- p3
->x
);
858 * Analyze the convex hulls to determine the synchronization factors between
859 * each pair of trace.
862 * syncState container for synchronization data.
865 * AllFactors*, see the documentation for the member geoFactors of
866 * AnalysisStatsCHull.
868 AllFactors
* calculateAllFactors(SyncState
* const syncState
)
870 unsigned int traceNumA
, traceNumB
;
871 AllFactors
* geoFactors
;
872 AnalysisDataCHull
* analysisData
;
874 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
876 // Allocate geoFactors and calculate min and max
877 geoFactors
= createAllFactors(syncState
->traceNb
);
878 for (traceNumA
= 0; traceNumA
< syncState
->traceNb
; traceNumA
++)
880 for (traceNumB
= 0; traceNumB
< traceNumA
; traceNumB
++)
887 size_t factorsOffset
;
889 {MINIMUM
, offsetof(PairFactors
, min
)},
890 {MAXIMUM
, offsetof(PairFactors
, max
)}
893 cr
= analysisData
->hullArray
[traceNumB
][traceNumA
];
894 cs
= analysisData
->hullArray
[traceNumA
][traceNumB
];
896 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
898 g_debug("geoFactors[%u][%u].%s = calculateFactorsExact(cr= "
899 "hullArray[%u][%u], cs= hullArray[%u][%u], %s)",
900 traceNumA
, traceNumB
, loopValues
[i
].factorsOffset
==
901 offsetof(PairFactors
, min
) ? "min" : "max", traceNumB
,
902 traceNumA
, traceNumA
, traceNumB
, loopValues
[i
].lineType
==
903 MINIMUM
? "MINIMUM" : "MAXIMUM");
904 *((Factors
**) ((void*)
905 &geoFactors
->pairFactors
[traceNumA
][traceNumB
] +
906 loopValues
[i
].factorsOffset
))=
907 calculateFactorsExact(cr
, cs
, loopValues
[i
].lineType
);
912 // Calculate approx when possible
913 for (traceNumA
= 0; traceNumA
< syncState
->traceNb
; traceNumA
++)
915 for (traceNumB
= 0; traceNumB
< traceNumA
; traceNumB
++)
917 PairFactors
* factorsCHull
;
919 factorsCHull
= &geoFactors
->pairFactors
[traceNumA
][traceNumB
];
920 if (factorsCHull
->min
== NULL
&& factorsCHull
->max
== NULL
)
922 factorsCHull
->type
= APPROXIMATE
;
923 calculateFactorsFallback(analysisData
->hullArray
[traceNumB
][traceNumA
],
924 analysisData
->hullArray
[traceNumA
][traceNumB
],
925 &geoFactors
->pairFactors
[traceNumA
][traceNumB
]);
927 else if (factorsCHull
->min
!= NULL
&& factorsCHull
->max
!= NULL
)
929 if (factorsCHull
->min
->drift
!= -INFINITY
&&
930 factorsCHull
->max
->drift
!= INFINITY
)
932 factorsCHull
->type
= ACCURATE
;
933 calculateFactorsMiddle(factorsCHull
);
935 else if (factorsCHull
->min
->drift
!= -INFINITY
||
936 factorsCHull
->max
->drift
!= INFINITY
)
938 factorsCHull
->type
= INCOMPLETE
;
942 factorsCHull
->type
= ABSENT
;
947 //g_assert_not_reached();
948 factorsCHull
->type
= FAIL
;
957 /* Calculate approximative factors based on minimum and maximum limits. The
958 * best approximation to make is the interior bissector of the angle formed by
959 * the minimum and maximum lines.
961 * The formulae used come from [Haddad, Yoram: Performance dans les systèmes
962 * répartis: des outils pour les mesures, Université de Paris-Sud, Centre
963 * d'Orsay, September 1988] Section 6.1 p.44
965 * The reasoning for choosing this estimator comes from [Duda, A., Harrus, G.,
966 * Haddad, Y., and Bernard, G.: Estimating global time in distributed systems,
967 * Proc. 7th Int. Conf. on Distributed Computing Systems, Berlin, volume 18,
971 * factors: contains the min and max limits, used to store the result
973 void calculateFactorsMiddle(PairFactors
* const factors
)
975 double amin
, amax
, bmin
, bmax
, bhat
;
977 amin
= factors
->max
->offset
;
978 amax
= factors
->min
->offset
;
979 bmin
= factors
->min
->drift
;
980 bmax
= factors
->max
->drift
;
982 g_assert_cmpfloat(bmax
, >=, bmin
);
984 factors
->approx
= malloc(sizeof(Factors
));
985 bhat
= (bmax
* bmin
- 1. + sqrt(1. + pow(bmax
, 2.) * pow(bmin
, 2.) +
986 pow(bmax
, 2.) + pow(bmin
, 2.))) / (bmax
+ bmin
);
987 factors
->approx
->offset
= amax
- (amax
- amin
) / 2. * (pow(bhat
, 2.) + 1.)
988 / (1. + bhat
* bmax
);
989 factors
->approx
->drift
= bhat
;
990 factors
->accuracy
= bmax
- bmin
;
995 * Analyze the convex hulls to determine the minimum or maximum
996 * synchronization factors between one pair of trace.
998 * This implements and improves upon the algorithm in [Haddad, Yoram:
999 * Performance dans les systèmes répartis: des outils pour les mesures,
1000 * Université de Paris-Sud, Centre d'Orsay, September 1988] Section 6.2 p.47
1002 * Some degenerate cases are possible:
1003 * 1) the result is unbounded. In that case, when searching for the maximum
1004 * factors, result->drift= INFINITY; result->offset= -INFINITY. When
1005 * searching for the minimum factors, it is the opposite. It is not
1006 * possible to improve the situation with this data.
1007 * 2) no line can be above the upper hull and below the lower hull. This is
1008 * because the hulls intersect each other or are reversed. This means that
1009 * an assertion was false. Most probably, the clocks are not linear. It is
1010 * possible to repeat the search with another algorithm that will find a
1011 * "best effort" approximation. See calculateFactorsApprox().
1014 * cu: the upper half-convex hull, the line must pass above this
1015 * and touch it in one point
1016 * cl: the lower half-convex hull, the line must pass below this
1017 * and touch it in one point
1018 * lineType: search for minimum or maximum factors
1021 * If a result is found, a struct Factors is allocated, filed with the
1022 * result and returned
1023 * NULL otherwise, degenerate case 2 is in effect
1025 static Factors
* calculateFactorsExact(GQueue
* const cu
, GQueue
* const cl
, const
1029 unsigned int i1
, i2
;
1031 double inversionFactor
;
1034 g_debug("calculateFactorsExact(cu= %p, cl= %p, %s)", cu
, cl
, lineType
==
1035 MINIMUM
? "MINIMUM" : "MAXIMUM");
1037 if (lineType
== MINIMUM
)
1041 inversionFactor
= -1.;
1047 inversionFactor
= 1.;
1053 // Check for degenerate case 1
1054 if (c1
->length
== 0 || c2
->length
== 0 || ((Point
*) g_queue_peek_nth(c1
,
1055 i1
))->x
>= ((Point
*) g_queue_peek_nth(c2
, i2
))->x
)
1057 result
= malloc(sizeof(Factors
));
1058 if (lineType
== MINIMUM
)
1060 result
->drift
= -INFINITY
;
1061 result
->offset
= INFINITY
;
1065 result
->drift
= INFINITY
;
1066 result
->offset
= -INFINITY
;
1078 g_queue_peek_nth(c1
, i1
),
1079 g_queue_peek_nth(c2
, i2
),
1080 g_queue_peek_nth(c1
, i1
),
1081 g_queue_peek_nth(c2
, i2
- 1)) * inversionFactor
< 0.
1084 if (((Point
*) g_queue_peek_nth(c1
, i1
))->x
1085 < ((Point
*) g_queue_peek_nth(c2
, i2
- 1))->x
)
1091 // Degenerate case 2
1097 i1
+ 1 < c1
->length
- 1
1099 g_queue_peek_nth(c1
, i1
),
1100 g_queue_peek_nth(c2
, i2
),
1101 g_queue_peek_nth(c1
, i1
+ 1),
1102 g_queue_peek_nth(c2
, i2
)) * inversionFactor
< 0.
1105 if (((Point
*) g_queue_peek_nth(c1
, i1
+ 1))->x
1106 < ((Point
*) g_queue_peek_nth(c2
, i2
))->x
)
1112 // Degenerate case 2
1120 g_queue_peek_nth(c1
, i1
),
1121 g_queue_peek_nth(c2
, i2
),
1122 g_queue_peek_nth(c1
, i1
),
1123 g_queue_peek_nth(c2
, i2
- 1)) * inversionFactor
< 0.
1126 p1
= g_queue_peek_nth(c1
, i1
);
1127 p2
= g_queue_peek_nth(c2
, i2
);
1129 g_debug("Resulting points are: c1[i1]: x= %" PRIu64
" y= %" PRIu64
1130 " c2[i2]: x= %" PRIu64
" y= %" PRIu64
"", p1
->x
, p1
->y
, p2
->x
, p2
->y
);
1132 result
= malloc(sizeof(Factors
));
1133 result
->drift
= slope(p1
, p2
);
1134 result
->offset
= intercept(p1
, p2
);
1136 g_debug("Resulting factors are: drift= %g offset= %g", result
->drift
,
1144 * Analyze the convex hulls to determine approximate synchronization factors
1145 * between one pair of trace when there is no line that can fit in the
1146 * corridor separating them.
1148 * This implements the algorithm in [Ashton, P.: Algorithms for Off-line Clock
1149 * Synchronisation, University of Canterbury, December 1995, 26] Section 4.2.2
1152 * For each point p1 in cr
1153 * For each point p2 in cs
1155 * Calculate the line paramaters
1156 * For each point p3 in each convex hull
1157 * If p3 is on the wrong side of the line
1159 * If error < errorMin
1163 * cr: the upper half-convex hull
1164 * cs: the lower half-convex hull
1165 * result: a pointer to the pre-allocated struct where the results
1168 static void calculateFactorsFallback(GQueue
* const cr
, GQueue
* const cs
,
1169 PairFactors
* const result
)
1171 unsigned int i
, j
, k
;
1176 approx
= malloc(sizeof(Factors
));
1178 for (i
= 0; i
< cs
->length
; i
++)
1180 for (j
= 0; j
< cr
->length
; j
++)
1187 if (((Point
*) g_queue_peek_nth(cs
, i
))->x
< ((Point
*)g_queue_peek_nth(cr
, j
))->x
)
1189 p1
= *(Point
*)g_queue_peek_nth(cs
, i
);
1190 p2
= *(Point
*)g_queue_peek_nth(cr
, j
);
1194 p1
= *(Point
*)g_queue_peek_nth(cr
, j
);
1195 p2
= *(Point
*)g_queue_peek_nth(cs
, i
);
1198 // The lower hull should be above the point
1199 for (k
= 0; k
< cs
->length
; k
++)
1201 if (jointCmp(&p1
, &p2
, g_queue_peek_nth(cs
, k
)) < 0.)
1203 error
+= verticalDistance(&p1
, &p2
, g_queue_peek_nth(cs
, k
));
1207 // The upper hull should be below the point
1208 for (k
= 0; k
< cr
->length
; k
++)
1210 if (jointCmp(&p1
, &p2
, g_queue_peek_nth(cr
, k
)) > 0.)
1212 error
+= verticalDistance(&p1
, &p2
, g_queue_peek_nth(cr
, k
));
1216 if (error
< errorMin
)
1218 g_debug("Fallback: i= %u j= %u is a better match (error= %g)", i
, j
, error
);
1219 approx
->drift
= slope(&p1
, &p2
);
1220 approx
->offset
= intercept(&p1
, &p2
);
1226 result
->approx
= approx
;
1227 result
->accuracy
= errorMin
;
1232 * Calculate the vertical distance between a line and a point
1235 * p1, p2: Two points defining the line
1239 * the vertical distance
1241 static double verticalDistance(Point
* p1
, Point
* p2
, Point
* const point
)
1243 return fabs(slope(p1
, p2
) * point
->x
+ intercept(p1
, p2
) - point
->y
);
1248 * Calculate the slope between two points
1251 * p1, p2 the two points
1256 static double slope(const Point
* const p1
, const Point
* const p2
)
1258 return ((double) p2
->y
- p1
->y
) / (p2
->x
- p1
->x
);
1262 /* Calculate the y-intercept of a line that passes by two points
1265 * p1, p2 the two points
1270 static double intercept(const Point
* const p1
, const Point
* const p2
)
1272 return ((double) p2
->y
* p1
->x
- (double) p1
->y
* p2
->x
) / ((double) p1
->x
- p2
->x
);
1277 * Write the analysis-specific graph lines in the gnuplot script.
1280 * syncState: container for synchronization data
1281 * i: first trace number
1282 * j: second trace number, garanteed to be larger than i
1284 void writeAnalysisTraceTraceForePlotsCHull(SyncState
* const syncState
, const unsigned
1285 int i
, const unsigned int j
)
1287 AnalysisDataCHull
* analysisData
;
1288 PairFactors
* factorsCHull
;
1290 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
1292 fprintf(syncState
->graphsStream
,
1293 "\t\"analysis_chull-%1$03d_to_%2$03d.data\" "
1294 "title \"Lower half-hull\" with linespoints "
1295 "linecolor rgb \"#015a01\" linetype 4 pointtype 8 pointsize 0.8, \\\n"
1296 "\t\"analysis_chull-%2$03d_to_%1$03d.data\" "
1297 "title \"Upper half-hull\" with linespoints "
1298 "linecolor rgb \"#003366\" linetype 4 pointtype 10 pointsize 0.8, \\\n",
1301 factorsCHull
= &analysisData
->graphsData
->allFactors
->pairFactors
[j
][i
];
1302 if (factorsCHull
->type
== EXACT
)
1304 fprintf(syncState
->graphsStream
,
1306 "title \"Exact conversion\" with lines "
1307 "linecolor rgb \"black\" linetype 1, \\\n",
1308 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
);
1310 else if (factorsCHull
->type
== ACCURATE
)
1312 fprintf(syncState
->graphsStream
,
1313 "\t%.2f + %.10f * x "
1314 "title \"Min conversion\" with lines "
1315 "linecolor rgb \"black\" linetype 5, \\\n",
1316 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
);
1317 fprintf(syncState
->graphsStream
,
1318 "\t%.2f + %.10f * x "
1319 "title \"Max conversion\" with lines "
1320 "linecolor rgb \"black\" linetype 8, \\\n",
1321 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
);
1322 fprintf(syncState
->graphsStream
,
1323 "\t%.2f + %.10f * x "
1324 "title \"Middle conversion\" with lines "
1325 "linecolor rgb \"black\" linetype 1, \\\n",
1326 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
);
1328 else if (factorsCHull
->type
== APPROXIMATE
)
1330 fprintf(syncState
->graphsStream
,
1331 "\t%.2f + %.10f * x "
1332 "title \"Fallback conversion\" with lines "
1333 "linecolor rgb \"gray60\" linetype 1, \\\n",
1334 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
);
1336 else if (factorsCHull
->type
== INCOMPLETE
)
1338 if (factorsCHull
->min
->drift
!= -INFINITY
)
1340 fprintf(syncState
->graphsStream
,
1341 "\t%.2f + %.10f * x "
1342 "title \"Min conversion\" with lines "
1343 "linecolor rgb \"black\" linetype 5, \\\n",
1344 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
);
1347 if (factorsCHull
->max
->drift
!= INFINITY
)
1349 fprintf(syncState
->graphsStream
,
1350 "\t%.2f + %.10f * x "
1351 "title \"Max conversion\" with lines "
1352 "linecolor rgb \"black\" linetype 8, \\\n",
1353 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
);
1356 else if (factorsCHull
->type
== FAIL
)
1358 if (factorsCHull
->min
!= NULL
&& factorsCHull
->min
->drift
!= -INFINITY
)
1360 fprintf(syncState
->graphsStream
,
1361 "\t%.2f + %.10f * x "
1362 "title \"Min conversion\" with lines "
1363 "linecolor rgb \"black\" linetype 5, \\\n",
1364 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
);
1367 if (factorsCHull
->max
!= NULL
&& factorsCHull
->max
->drift
!= INFINITY
)
1369 fprintf(syncState
->graphsStream
,
1370 "\t%.2f + %.10f * x "
1371 "title \"Max conversion\" with lines "
1372 "linecolor rgb \"black\" linetype 8, \\\n",
1373 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
);
1376 else if (factorsCHull
->type
== ABSENT
)
1381 g_assert_not_reached();
1388 * Create the linear programming problem containing the constraints defined by
1389 * two half-hulls. The objective function and optimization directions are not
1393 * syncState: container for synchronization data
1394 * i: first trace number
1395 * j: second trace number, garanteed to be larger than i
1397 * A new glp_prob*, this problem must be freed by the caller with
1400 static glp_prob
* lpCreateProblem(GQueue
* const lowerHull
, GQueue
* const
1405 const double zeroD
= 0.;
1406 glp_prob
* lp
= glp_create_prob();
1407 unsigned int hullPointNb
= g_queue_get_length(lowerHull
) +
1408 g_queue_get_length(upperHull
);
1409 GArray
* iArray
= g_array_sized_new(FALSE
, FALSE
, sizeof(int), hullPointNb
+
1411 GArray
* jArray
= g_array_sized_new(FALSE
, FALSE
, sizeof(int), hullPointNb
+
1413 GArray
* aArray
= g_array_sized_new(FALSE
, FALSE
, sizeof(double),
1417 struct LPAddRowInfo rowInfo
;
1419 {lowerHull
, {lp
, GLP_UP
, iArray
, jArray
, aArray
}},
1420 {upperHull
, {lp
, GLP_LO
, iArray
, jArray
, aArray
}},
1423 // Create the LP problem
1424 glp_term_out(GLP_OFF
);
1425 if (hullPointNb
> 0)
1427 glp_add_rows(lp
, hullPointNb
);
1429 glp_add_cols(lp
, 2);
1431 glp_set_col_name(lp
, 1, "a0");
1432 glp_set_col_bnds(lp
, 1, GLP_FR
, 0., 0.);
1433 glp_set_col_name(lp
, 2, "a1");
1434 glp_set_col_bnds(lp
, 2, GLP_LO
, 0., 0.);
1436 // Add row constraints
1437 g_array_append_val(iArray
, zero
);
1438 g_array_append_val(jArray
, zero
);
1439 g_array_append_val(aArray
, zeroD
);
1441 for (it
= 0; it
< sizeof(loopValues
) / sizeof(*loopValues
); it
++)
1443 g_queue_foreach(loopValues
[it
].hull
, &gfLPAddRow
,
1444 &loopValues
[it
].rowInfo
);
1447 g_assert_cmpuint(iArray
->len
, ==, jArray
->len
);
1448 g_assert_cmpuint(jArray
->len
, ==, aArray
->len
);
1449 g_assert_cmpuint(aArray
->len
- 1, ==, hullPointNb
* 2);
1451 glp_load_matrix(lp
, aArray
->len
- 1, &g_array_index(iArray
, int, 0),
1452 &g_array_index(jArray
, int, 0), &g_array_index(aArray
, double, 0));
1454 glp_scale_prob(lp
, GLP_SF_AUTO
);
1456 g_array_free(iArray
, TRUE
);
1457 g_array_free(jArray
, TRUE
);
1458 g_array_free(aArray
, TRUE
);
1465 * A GFunc for g_queue_foreach(). Add constraints and bounds for one row.
1468 * data Point*, synchronization point for which to add an LP row
1470 * user_data LPAddRowInfo*
1472 static void gfLPAddRow(gpointer data
, gpointer user_data
)
1475 struct LPAddRowInfo
* rowInfo
= user_data
;
1477 double constraints
[2];
1479 indexes
[0]= g_array_index(rowInfo
->iArray
, int, rowInfo
->iArray
->len
- 1) + 1;
1480 indexes
[1]= indexes
[0];
1482 if (rowInfo
->boundType
== GLP_UP
)
1484 glp_set_row_bnds(rowInfo
->lp
, indexes
[0], GLP_UP
, 0., p
->y
);
1486 else if (rowInfo
->boundType
== GLP_LO
)
1488 glp_set_row_bnds(rowInfo
->lp
, indexes
[0], GLP_LO
, p
->y
, 0.);
1492 g_assert_not_reached();
1495 g_array_append_vals(rowInfo
->iArray
, indexes
, 2);
1498 g_array_append_vals(rowInfo
->jArray
, indexes
, 2);
1500 constraints
[1]= p
->x
;
1501 g_array_append_vals(rowInfo
->aArray
, constraints
, 2);
1506 * Calculate min or max correction factors (as possible) using an LP problem.
1509 * lp: A linear programming problem with constraints and bounds
1511 * direction: The type of factors desired. Use GLP_MAX for max
1512 * approximation factors (a1, the drift or slope is the
1513 * largest) and GLP_MIN in the other case.
1516 * If the calculation was successful, a new Factors struct. Otherwise, NULL.
1517 * The calculation will fail if the hull assumptions are not respected.
1519 static Factors
* calculateFactorsLP(glp_prob
* const lp
, const int direction
)
1524 glp_set_obj_coef(lp
, 1, 0.);
1525 glp_set_obj_coef(lp
, 2, 1.);
1527 glp_set_obj_dir(lp
, direction
);
1528 retval
= glp_simplex(lp
, NULL
);
1529 status
= glp_get_status(lp
);
1531 if (retval
== 0 && status
== GLP_OPT
)
1533 factors
= malloc(sizeof(Factors
));
1534 factors
->offset
= glp_get_col_prim(lp
, 1);
1535 factors
->drift
= glp_get_col_prim(lp
, 2);
1547 * Calculate min, max and approx correction factors (as possible) using an LP
1551 * lp A linear programming problem with constraints and bounds
1553 * factors Resulting factors, must be preallocated
1555 static void calculateCompleteFactorsLP(glp_prob
* const lp
, PairFactors
* factors
)
1557 factors
->min
= calculateFactorsLP(lp
, GLP_MIN
);
1558 factors
->max
= calculateFactorsLP(lp
, GLP_MAX
);
1560 if (factors
->min
&& factors
->max
)
1562 factors
->type
= ACCURATE
;
1563 calculateFactorsMiddle(factors
);
1565 else if (factors
->min
|| factors
->max
)
1567 factors
->type
= INCOMPLETE
;
1571 factors
->type
= ABSENT
;
1577 * A GFunc for g_queue_foreach()
1580 * data Point*, a convex hull point
1581 * user_data GArray*, an array of convex hull point absisca values, as
1584 static void gfAddAbsiscaToArray(gpointer data
, gpointer user_data
)
1587 GArray
* a
= user_data
;
1590 g_array_append_val(a
, v
);
1595 * A GCompareFunc for g_array_sort()
1598 * a, b uint64_t*, absisca values
1601 * "returns less than zero for first arg is less than second arg, zero for
1602 * equal, greater zero if first arg is greater than second arg"
1603 * - the great glib documentation
1605 static gint
gcfCompareUint64(gconstpointer a
, gconstpointer b
)
1607 if (*(uint64_t*) a
< *(uint64_t*) b
)
1611 else if (*(uint64_t*) a
> *(uint64_t*) b
)
1623 * Compute synchronization factors using a linear programming approach.
1626 * syncState: container for synchronization data
1628 static AllFactors
* finalizeAnalysisCHullLP(SyncState
* const syncState
)
1630 AnalysisDataCHull
* analysisData
= syncState
->analysisData
;
1632 AllFactors
* lpFactorsArray
;
1634 lpFactorsArray
= createAllFactors(syncState
->traceNb
);
1636 analysisData
->lps
= malloc(syncState
->traceNb
* sizeof(glp_prob
**));
1637 for (i
= 0; i
< syncState
->traceNb
; i
++)
1639 analysisData
->lps
[i
]= malloc(i
* sizeof(glp_prob
*));
1642 for (i
= 0; i
< syncState
->traceNb
; i
++)
1644 for (j
= 0; j
< i
; j
++)
1648 GQueue
*** hullArray
= analysisData
->hullArray
;
1649 PairFactors
* lpFactors
= &lpFactorsArray
->pairFactors
[i
][j
];
1651 // Create the LP problem
1652 lp
= lpCreateProblem(hullArray
[i
][j
], hullArray
[j
][i
]);
1653 analysisData
->lps
[i
][j
]= lp
;
1655 // Use the LP problem to find the correction factors for this pair of
1657 calculateCompleteFactorsLP(lp
, lpFactors
);
1659 // If possible, compute synchronization accuracy information for
1661 if (syncState
->graphsStream
&& lpFactors
->type
== ACCURATE
)
1669 // Open the data file
1670 snprintf(fileName
, sizeof(fileName
),
1671 "analysis_chull_accuracy-%03u_and_%03u.data", j
, i
);
1672 fileName
[sizeof(fileName
) - 1]= '\0';
1674 cwd
= changeToGraphsDir(syncState
->graphsDir
);
1676 if ((fp
= fopen(fileName
, "w")) == NULL
)
1678 g_error(strerror(errno
));
1680 fprintf(fp
, "#%-24s %-25s %-25s %-25s\n", "x", "middle", "min", "max");
1685 g_error(strerror(errno
));
1689 // Build the list of absisca values for the points in the accuracy graph
1690 xValues
= g_array_sized_new(FALSE
, FALSE
, sizeof(uint64_t),
1691 g_queue_get_length(hullArray
[i
][j
]) +
1692 g_queue_get_length(hullArray
[j
][i
]));
1694 g_queue_foreach(hullArray
[i
][j
], &gfAddAbsiscaToArray
, xValues
);
1695 g_queue_foreach(hullArray
[j
][i
], &gfAddAbsiscaToArray
, xValues
);
1697 g_array_sort(xValues
, &gcfCompareUint64
);
1699 /* For each absisca value and each optimisation direction, solve the LP
1700 * and write a line in the data file */
1701 for (it
= 0; it
< xValues
->len
; it
++)
1704 CorrectedTime correctedTime
;
1706 time
= g_array_index(xValues
, uint64_t, it
);
1707 timeCorrectionLP(lp
, lpFactors
, time
, &correctedTime
);
1708 fprintf(fp
, "%24" PRIu64
" %24" PRIu64
" %24" PRIu64
1709 "%24" PRIu64
"\n", time
, correctedTime
.time
,
1710 correctedTime
.min
, correctedTime
.max
);
1713 g_array_free(xValues
, TRUE
);
1719 if (syncState
->stats
)
1721 lpFactorsArray
->refCount
++;
1722 analysisData
->stats
->lpFactors
= lpFactorsArray
;
1725 if (syncState
->graphsStream
)
1727 lpFactorsArray
->refCount
++;
1728 analysisData
->graphsData
->lpFactors
= lpFactorsArray
;
1731 return lpFactorsArray
;
1736 * Perform correction on one time value and calculate accuracy bounds.
1739 * lp: Linear Programming problem containing the coefficients for
1740 * the trace pair between which to perform time correction.
1741 * lpFactors: Correction factors for this trace pair, the factors must be
1743 * time: Time value to correct.
1744 * correctedTime: Result of the time correction, preallocated.
1746 void timeCorrectionLP(glp_prob
* const lp
, const PairFactors
* const lpFactors
,
1747 const uint64_t time
, CorrectedTime
* const correctedTime
)
1755 {GLP_MIN
, offsetof(CorrectedTime
, min
)},
1756 {GLP_MAX
, offsetof(CorrectedTime
, max
)}
1759 glp_set_obj_coef(lp
, 1, 1.);
1760 glp_set_obj_coef(lp
, 2, time
);
1762 g_assert(lpFactors
->type
== ACCURATE
);
1764 correctedTime
->time
= lpFactors
->approx
->offset
+ lpFactors
->approx
->drift
1767 for (it
= 0; it
< ARRAY_SIZE(loopValues
); it
++)
1772 glp_set_obj_dir(lp
, loopValues
[it
].direction
);
1773 retval
= glp_simplex(lp
, NULL
);
1774 status
= glp_get_status(lp
);
1776 g_assert(retval
== 0 && status
== GLP_OPT
);
1777 *(uint64_t*) ((void*) correctedTime
+ loopValues
[it
].offset
)=
1778 round(glp_get_obj_val(lp
));
1784 * Write the analysis-specific graph lines in the gnuplot script.
1787 * syncState: container for synchronization data
1788 * i: first trace number
1789 * j: second trace number, garanteed to be larger than i
1791 static void writeAnalysisTraceTimeBackPlotsCHull(SyncState
* const syncState
,
1792 const unsigned int i
, const unsigned int j
)
1794 if (((AnalysisDataCHull
*)
1795 syncState
->analysisData
)->graphsData
->lpFactors
->pairFactors
[j
][i
].type
1798 fprintf(syncState
->graphsStream
,
1799 "\t\"analysis_chull_accuracy-%1$03u_and_%2$03u.data\" "
1800 "using 1:(($3 - $2) / clock_freq_%2$u):(($4 - $2) / clock_freq_%2$u) "
1801 "title \"Synchronization accuracy\" "
1802 "with filledcurves linewidth 2 linetype 1 "
1803 "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i
,
1810 * Write the analysis-specific graph lines in the gnuplot script.
1813 * syncState: container for synchronization data
1814 * i: first trace number
1815 * j: second trace number, garanteed to be larger than i
1817 static void writeAnalysisTraceTimeForePlotsCHull(SyncState
* const syncState
,
1818 const unsigned int i
, const unsigned int j
)
1820 if (((AnalysisDataCHull
*)
1821 syncState
->analysisData
)->graphsData
->lpFactors
->pairFactors
[j
][i
].type
1824 fprintf(syncState
->graphsStream
,
1825 "\t\"analysis_chull_accuracy-%1$03u_and_%2$03u.data\" "
1826 "using 1:(($3 - $2) / clock_freq_%2$u) notitle "
1827 "with lines linewidth 2 linetype 1 "
1828 "linecolor rgb \"gray60\", \\\n"
1829 "\t\"analysis_chull_accuracy-%1$03u_and_%2$03u.data\" "
1830 "using 1:(($4 - $2) / clock_freq_%2$u) notitle "
1831 "with lines linewidth 2 linetype 1 "
1832 "linecolor rgb \"gray60\", \\\n", i
, j
);
1838 * Write the analysis-specific graph lines in the gnuplot script.
1841 * syncState: container for synchronization data
1842 * i: first trace number
1843 * j: second trace number, garanteed to be larger than i
1845 static void writeAnalysisTraceTraceBackPlotsCHull(SyncState
* const syncState
,
1846 const unsigned int i
, const unsigned int j
)
1848 if (((AnalysisDataCHull
*)
1849 syncState
->analysisData
)->graphsData
->lpFactors
->pairFactors
[j
][i
].type
1852 fprintf(syncState
->graphsStream
,
1853 "\t\"analysis_chull_accuracy-%1$03u_and_%2$03u.data\" "
1855 "title \"Synchronization accuracy\" "
1856 "with filledcurves linewidth 2 linetype 1 "
1857 "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i
, j
);