X-Git-Url: http://git.lttng.org/?a=blobdiff_plain;f=lttv%2Flttv%2Fsync%2Fevent_analysis_eval.c;h=27d877d8a7c3b407d04a65ebe5a213b0304163f7;hb=0a87ec9a018cc9731ce3b04309eaa4dcc77df6d2;hp=dd8310875dee737288137148a06ecd2f655a09a1;hpb=ffa21cfde7a086c1558b961ffa0fcbe75513a7f6;p=lttv.git

diff --git a/lttv/lttv/sync/event_analysis_eval.c b/lttv/lttv/sync/event_analysis_eval.c
index dd831087..27d877d8 100644
--- a/lttv/lttv/sync/event_analysis_eval.c
+++ b/lttv/lttv/sync/event_analysis_eval.c
@@ -1,19 +1,18 @@
 /* This file is part of the Linux Trace Toolkit viewer
- * Copyright (C) 2009 Benjamin Poirier <benjamin.poirier@polymtl.ca>
+ * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
  *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License Version 2 as
- * published by the Free Software Foundation;
+ * This program is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation, either version 2.1 of the License, or (at
+ * your option) any later version.
  *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
  *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
- * MA 02111-1307, USA.
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 #define _GNU_SOURCE
@@ -36,16 +35,25 @@
 
 #include "lookup3.h"
 #include "sync_chain.h"
+#include "event_analysis_chull.h"
 
 #include "event_analysis_eval.h"
 
 
-struct WriteGraphInfo
+struct WriteHistogramInfo
 {
 	GHashTable* rttInfo;
 	FILE* graphsStream;
 };
 
+#ifdef HAVE_LIBGLPK
+struct LPAddRowInfo
+{
+	glp_prob* lp;
+	int boundType;
+	GArray* iArray, * jArray, * aArray;
+};
+#endif
 
 // Functions common to all analysis modules
 static void initAnalysisEval(SyncState* const syncState);
@@ -57,11 +65,18 @@ static void analyzeExchangeEval(SyncState* const syncState, Exchange* const
 	exchange);
 static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const
 	broadcast);
-static GArray* finalizeAnalysisEval(SyncState* const syncState);
+static AllFactors* finalizeAnalysisEval(SyncState* const syncState);
 static void printAnalysisStatsEval(SyncState* const syncState);
+static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState,
+	const unsigned int i, const unsigned int j);
+static void writeAnalysisTraceTimeForePlotsEval(SyncState* const syncState,
+	const unsigned int i, const unsigned int j);
+static void writeAnalysisTraceTraceBackPlotsEval(SyncState* const syncState,
+	const unsigned int i, const unsigned int j);
+static void writeAnalysisTraceTraceForePlotsEval(SyncState* const syncState,
+	const unsigned int i, const unsigned int j);
 
 // Functions specific to this module
-static void registerAnalysisEval() __attribute__((constructor (102)));
 static guint ghfRttKeyHash(gconstpointer key);
 static gboolean gefRttKeyEqual(gconstpointer a, gconstpointer b);
 static void gdnDestroyRttKey(gpointer data);
@@ -71,23 +86,48 @@ static void positionStream(FILE* stream);
 
 static void gfSum(gpointer data, gpointer userData);
 static void gfSumSquares(gpointer data, gpointer userData);
-static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer user_data);
+static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer
+	user_data);
 
 static void hitBin(struct Bins* const bins, const double value);
 static unsigned int binNum(const double value) __attribute__((pure));
 static double binStart(const unsigned int binNum) __attribute__((pure));
 static double binEnd(const unsigned int binNum) __attribute__((pure));
+static uint32_t normalTotal(struct Bins* const bins) __attribute__((const));
 
-static AnalysisGraphEval* constructAnalysisGraphEval(const char* const
+static AnalysisHistogramEval* constructAnalysisHistogramEval(const char* const
 	graphsDir, const struct RttKey* const rttKey);
-static void destroyAnalysisGraphEval(AnalysisGraphEval* const graph);
-static void gdnDestroyAnalysisGraphEval(gpointer data);
-static void ghfWriteGraph(gpointer key, gpointer value, gpointer user_data);
+static void destroyAnalysisHistogramEval(AnalysisHistogramEval* const
+	histogram);
+static void gdnDestroyAnalysisHistogramEval(gpointer data);
+static void ghfWriteHistogram(gpointer key, gpointer value, gpointer
+	user_data);
 static void dumpBinToFile(const struct Bins* const bins, FILE* const file);
 static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey,
-	double* minRtt);
+	double* minRtt, AnalysisHistogramEval* const histogram);
+
+static void updateBounds(Bounds** const bounds, Event* const e1, Event* const
+	e2);
+
+static void finalizeAnalysisEvalLP(SyncState* const syncState);
+// The next group of functions is only needed when computing synchronization
+// accuracy.
+#ifdef HAVE_LIBGLPK
+static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const
+	upperHull);
+static void gfLPAddRow(gpointer data, gpointer user_data);
+static Factors* calculateFactors(glp_prob* const lp, const int direction);
+static void calculateCompleteFactors(glp_prob* const lp, PairFactors*
+	factors);
+static inline void finalizeAnalysisEvalLP(SyncState* const syncState);
+static void gfAddAbsiscaToArray(gpointer data, gpointer user_data);
+static gint gcfCompareDouble(gconstpointer a, gconstpointer b);
+#else
+static void finalizeAnalysisEvalLP(SyncState* const syncState);
+#endif
 
 
+// initialized in registerAnalysisEval()
 double binBase;
 
 static AnalysisModule analysisModuleEval= {
@@ -99,14 +139,17 @@ static AnalysisModule analysisModuleEval= {
 	.analyzeBroadcast= &analyzeBroadcastEval,
 	.finalizeAnalysis= &finalizeAnalysisEval,
 	.printAnalysisStats= &printAnalysisStatsEval,
-	.writeAnalysisGraphsPlots= NULL,
-	.writeAnalysisGraphsOptions= NULL,
+	.graphFunctions= {
+		.writeTraceTimeBackPlots= &writeAnalysisTraceTimeBackPlotsEval,
+		.writeTraceTimeForePlots= &writeAnalysisTraceTimeForePlotsEval,
+		.writeTraceTraceBackPlots= &writeAnalysisTraceTraceBackPlotsEval,
+		.writeTraceTraceForePlots= &writeAnalysisTraceTraceForePlotsEval,
+	}
 };
 
 static ModuleOption optionEvalRttFile= {
 	.longName= "eval-rtt-file",
 	.hasArg= REQUIRED_ARG,
-	{.arg= NULL},
 	.optionHelp= "specify the file containing RTT information",
 	.argHelp= "FILE",
 };
@@ -115,8 +158,10 @@ static ModuleOption optionEvalRttFile= {
 /*
  * Analysis module registering function
  */
-static void registerAnalysisEval()
+void registerAnalysisEval()
 {
+	binBase= exp10(6. / (BIN_NB - 3));
+
 	g_queue_push_tail(&analysisModules, &analysisModuleEval);
 	g_queue_push_tail(&moduleOptions, &optionEvalRttFile);
 }
@@ -134,7 +179,7 @@ static void registerAnalysisEval()
 static void initAnalysisEval(SyncState* const syncState)
 {
 	AnalysisDataEval* analysisData;
-	unsigned int i;
+	unsigned int i, j;
 
 	analysisData= malloc(sizeof(AnalysisDataEval));
 	syncState->analysisData= analysisData;
@@ -164,7 +209,8 @@ static void initAnalysisEval(SyncState* const syncState)
 	if (syncState->stats)
 	{
 		analysisData->stats= calloc(1, sizeof(AnalysisStatsEval));
-		analysisData->stats->broadcastDiffSum= 0.;
+		analysisData->stats->broadcastRangeMin= INFINITY;
+		analysisData->stats->broadcastRangeMax= -INFINITY;
 
 		analysisData->stats->messageStats= malloc(syncState->traceNb *
 			sizeof(MessageStats*));
@@ -177,13 +223,52 @@ static void initAnalysisEval(SyncState* const syncState)
 		analysisData->stats->exchangeRtt=
 			g_hash_table_new_full(&ghfRttKeyHash, &gefRttKeyEqual,
 				&gdnDestroyRttKey, &gdnDestroyDouble);
+
+#ifdef HAVE_LIBGLPK
+		analysisData->stats->chFactorsArray= NULL;
+		analysisData->stats->lpFactorsArray= NULL;
+#endif
 	}
 
 	if (syncState->graphsStream)
 	{
-		binBase= exp10(6. / (BIN_NB - 3));
-		analysisData->graphs= g_hash_table_new_full(&ghfRttKeyHash,
-			&gefRttKeyEqual, &gdnDestroyRttKey, &gdnDestroyAnalysisGraphEval);
+		AnalysisGraphsEval* graphs= malloc(sizeof(AnalysisGraphsEval));
+
+		analysisData->graphs= graphs;
+
+		graphs->histograms= g_hash_table_new_full(&ghfRttKeyHash,
+			&gefRttKeyEqual, &gdnDestroyRttKey,
+			&gdnDestroyAnalysisHistogramEval);
+
+		graphs->bounds= malloc(syncState->traceNb * sizeof(Bounds*));
+		for (i= 0; i < syncState->traceNb; i++)
+		{
+			graphs->bounds[i]= malloc(i * sizeof(Bounds));
+			for (j= 0; j < i; j++)
+			{
+				graphs->bounds[i][j].min= UINT64_MAX;
+				graphs->bounds[i][j].max= 0;
+			}
+		}
+
+#ifdef HAVE_LIBGLPK
+		graphs->lps= NULL;
+		graphs->lpFactorsArray= NULL;
+#endif
+	}
+
+	if (syncState->stats || syncState->graphsStream)
+	{
+		GList* result;
+
+		analysisData->chullSS= malloc(sizeof(SyncState));
+		memcpy(analysisData->chullSS, syncState, sizeof(SyncState));
+		analysisData->chullSS->stats= false;
+		analysisData->chullSS->analysisData= NULL;
+		result= g_queue_find_custom(&analysisModules, "chull",
+			&gcfCompareAnalysis);
+		analysisData->chullSS->analysisModule= (AnalysisModule*) result->data;
+		analysisData->chullSS->analysisModule->initAnalysis(analysisData->chullSS);
 	}
 }
 
@@ -196,35 +281,35 @@ static void initAnalysisEval(SyncState* const syncState)
  *   graphsDir:    folder where to write files
  *   rttKey:       host pair, make sure saddr < daddr
  */
-static AnalysisGraphEval* constructAnalysisGraphEval(const char* const
+static AnalysisHistogramEval* constructAnalysisHistogramEval(const char* const
 	graphsDir, const struct RttKey* const rttKey)
 {
 	int retval;
 	unsigned int i;
 	char* cwd;
 	char name[60], saddr[16], daddr[16];
-	AnalysisGraphEval* graph= calloc(1, sizeof(*graph));
+	AnalysisHistogramEval* histogram= calloc(1, sizeof(*histogram));
 	const struct {
 		size_t pointsOffset;
 		const char* fileName;
 		const char* host1, *host2;
 	} loopValues[]= {
-		{offsetof(AnalysisGraphEval, ttSendPoints), "analysis_eval_tt-%s_to_%s.data",
-			saddr, daddr},
-		{offsetof(AnalysisGraphEval, ttRecvPoints), "analysis_eval_tt-%s_to_%s.data",
-			daddr, saddr},
-		{offsetof(AnalysisGraphEval, hrttPoints), "analysis_eval_hrtt-%s_and_%s.data",
-			saddr, daddr},
+		{offsetof(AnalysisHistogramEval, ttSendPoints),
+			"analysis_eval_tt-%s_to_%s.data", saddr, daddr},
+		{offsetof(AnalysisHistogramEval, ttRecvPoints),
+			"analysis_eval_tt-%s_to_%s.data", daddr, saddr},
+		{offsetof(AnalysisHistogramEval, hrttPoints),
+			"analysis_eval_hrtt-%s_and_%s.data", saddr, daddr},
 	};
 
-	graph->ttSendBins.max= BIN_NB - 1;
-	graph->ttRecvBins.max= BIN_NB - 1;
-	graph->hrttBins.max= BIN_NB - 1;
+	histogram->ttSendBins.min= BIN_NB - 1;
+	histogram->ttRecvBins.min= BIN_NB - 1;
+	histogram->hrttBins.min= BIN_NB - 1;
 
 	convertIP(saddr, rttKey->saddr);
 	convertIP(daddr, rttKey->daddr);
 
-	cwd= changeToGraphDir(graphsDir);
+	cwd= changeToGraphsDir(graphsDir);
 
 	for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
 	{
@@ -234,7 +319,7 @@ static AnalysisGraphEval* constructAnalysisGraphEval(const char* const
 		{
 			name[sizeof(name) - 1]= '\0';
 		}
-		if ((*(FILE**)((void*) graph + loopValues[i].pointsOffset)=
+		if ((*(FILE**)((void*) histogram + loopValues[i].pointsOffset)=
 				fopen(name, "w")) == NULL)
 		{
 			g_error(strerror(errno));
@@ -248,7 +333,7 @@ static AnalysisGraphEval* constructAnalysisGraphEval(const char* const
 	}
 	free(cwd);
 
-	return graph;
+	return histogram;
 }
 
 
@@ -259,26 +344,29 @@ static AnalysisGraphEval* constructAnalysisGraphEval(const char* const
  *   graphsDir:    folder where to write files
  *   rttKey:       host pair, make sure saddr < daddr
  */
-static void destroyAnalysisGraphEval(AnalysisGraphEval* const graph)
+static void destroyAnalysisHistogramEval(AnalysisHistogramEval* const
+	histogram)
 {
 	unsigned int i;
 	int retval;
 	const struct {
 		size_t pointsOffset;
 	} loopValues[]= {
-		{offsetof(AnalysisGraphEval, ttSendPoints)},
-		{offsetof(AnalysisGraphEval, ttRecvPoints)},
-		{offsetof(AnalysisGraphEval, hrttPoints)},
+		{offsetof(AnalysisHistogramEval, ttSendPoints)},
+		{offsetof(AnalysisHistogramEval, ttRecvPoints)},
+		{offsetof(AnalysisHistogramEval, hrttPoints)},
 	};
 
 	for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
 	{
-		retval= fclose(*(FILE**)((void*) graph + loopValues[i].pointsOffset));
+		retval= fclose(*(FILE**)((void*) histogram + loopValues[i].pointsOffset));
 		if (retval != 0)
 		{
 			g_error(strerror(errno));
 		}
 	}
+
+	free(histogram);
 }
 
 
@@ -286,11 +374,11 @@ static void destroyAnalysisGraphEval(AnalysisGraphEval* const graph)
  * A GDestroyNotify function for g_hash_table_new_full()
  *
  * Args:
- *   data:         AnalysisGraphEval*
+ *   data:         AnalysisHistogramEval*
  */
-static void gdnDestroyAnalysisGraphEval(gpointer data)
+static void gdnDestroyAnalysisHistogramEval(gpointer data)
 {
-	destroyAnalysisGraphEval(data);
+	destroyAnalysisHistogramEval(data);
 }
 
 
@@ -299,17 +387,17 @@ static void gdnDestroyAnalysisGraphEval(gpointer data)
  *
  * Args:
  *   key:          RttKey* where saddr < daddr
- *   value:        AnalysisGraphEval*
- *   user_data     struct WriteGraphInfo*
+ *   value:        AnalysisHistogramEval*
+ *   user_data     struct WriteHistogramInfo*
  */
-static void ghfWriteGraph(gpointer key, gpointer value, gpointer user_data)
+static void ghfWriteHistogram(gpointer key, gpointer value, gpointer user_data)
 {
 	double* rtt1, * rtt2;
 	struct RttKey* rttKey= key;
 	struct RttKey oppositeRttKey= {.saddr= rttKey->daddr, .daddr=
 		rttKey->saddr};
-	AnalysisGraphEval* graph= value;
-	struct WriteGraphInfo* info= user_data;
+	AnalysisHistogramEval* histogram= value;
+	struct WriteHistogramInfo* info= user_data;
 
 	rtt1= g_hash_table_lookup(info->rttInfo, rttKey);
 	rtt2= g_hash_table_lookup(info->rttInfo, &oppositeRttKey);
@@ -323,10 +411,10 @@ static void ghfWriteGraph(gpointer key, gpointer value, gpointer user_data)
 		rtt1= MIN(rtt1, rtt2);
 	}
 
-	dumpBinToFile(&graph->ttSendBins, graph->ttSendPoints);
-	dumpBinToFile(&graph->ttRecvBins, graph->ttRecvPoints);
-	dumpBinToFile(&graph->hrttBins, graph->hrttPoints);
-	writeHistogram(info->graphsStream, rttKey, rtt1);
+	dumpBinToFile(&histogram->ttSendBins, histogram->ttSendPoints);
+	dumpBinToFile(&histogram->ttRecvBins, histogram->ttRecvPoints);
+	dumpBinToFile(&histogram->hrttBins, histogram->hrttPoints);
+	writeHistogram(info->graphsStream, rttKey, rtt1, histogram);
 }
 
 
@@ -361,9 +449,11 @@ static void dumpBinToFile(const struct Bins* const bins, FILE* const file)
  *   graphsStream: write to this file
  *   rttKey:       must be sorted such that saddr < daddr
  *   minRtt:       if available, else NULL
+ *   histogram:    struct that contains the bins for the pair of traces
+ *                 identified by rttKey
  */
 static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey,
-	double* minRtt)
+	double* minRtt, AnalysisHistogramEval* const histogram)
 {
 	char saddr[16], daddr[16];
 
@@ -371,7 +461,7 @@ static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey,
 	convertIP(daddr, rttKey->daddr);
 
 	fprintf(graphsStream,
-		"reset\n"
+		"\nreset\n"
 		"set output \"histogram-%s-%s.eps\"\n"
 		"set title \"\"\n"
 		"set xlabel \"Message Latency (s)\"\n"
@@ -381,20 +471,54 @@ static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey,
 	{
 		fprintf(graphsStream,
 			"set arrow from %.9f, 0 rto 0, graph 1 "
-			"nohead linetype 3 linewidth 3 linecolor rgb \"black\"\n", *minRtt / 2);
+			"nohead linetype 3 linewidth 3 linecolor rgb \"black\"\n", *minRtt
+			/ 2);
 	}
 
-	fprintf(graphsStream,
-		"plot \\\n"
-		"\t\"analysis_eval_hrtt-%1$s_and_%2$s.data\" "
-			"title \"RTT/2\" with linespoints linetype 1 linewidth 2 "
-			"linecolor rgb \"black\" pointtype 6 pointsize 1,\\\n"
-		"\t\"analysis_eval_tt-%1$s_to_%2$s.data\" "
-			"title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 "
-			"linecolor rgb \"gray60\" pointtype 6 pointsize 1,\\\n"
-		"\t\"analysis_eval_tt-%2$s_to_%1$s.data\" "
-			"title \"%2$s to %1$s\" with linespoints linetype 4 linewidth 2 "
-			"linecolor rgb \"gray30\" pointtype 6 pointsize 1\n", saddr, daddr);
+	if (normalTotal(&histogram->ttSendBins) ||
+		normalTotal(&histogram->ttRecvBins) ||
+		normalTotal(&histogram->hrttBins))
+	{
+		fprintf(graphsStream, "plot \\\n");
+
+		if (normalTotal(&histogram->hrttBins))
+		{
+			fprintf(graphsStream,
+				"\t\"analysis_eval_hrtt-%s_and_%s.data\" "
+					"title \"RTT/2\" with linespoints linetype 1 linewidth 2 "
+					"linecolor rgb \"black\" pointtype 6 pointsize 1,\\\n",
+					saddr, daddr);
+		}
+
+		if (normalTotal(&histogram->ttSendBins))
+		{
+			fprintf(graphsStream,
+				"\t\"analysis_eval_tt-%1$s_to_%2$s.data\" "
+					"title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 "
+					"linecolor rgb \"gray60\" pointtype 6 pointsize 1,\\\n",
+					saddr, daddr);
+		}
+
+		if (normalTotal(&histogram->ttRecvBins))
+		{
+			fprintf(graphsStream,
+				"\t\"analysis_eval_tt-%1$s_to_%2$s.data\" "
+					"title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 "
+					"linecolor rgb \"gray30\" pointtype 6 pointsize 1,\\\n",
+					daddr, saddr);
+		}
+
+		// Remove the ",\\\n" from the last graph plot line
+		if (ftruncate(fileno(graphsStream), ftell(graphsStream) - 3) == -1)
+		{
+			g_error(strerror(errno));
+		}
+		if (fseek(graphsStream, 0, SEEK_END) == -1)
+		{
+			g_error(strerror(errno));
+		}
+		fprintf(graphsStream, "\n");
+	}
 }
 
 
@@ -413,30 +537,76 @@ static void destroyAnalysisEval(SyncState* const syncState)
 
 	analysisData= (AnalysisDataEval*) syncState->analysisData;
 
-	if (analysisData == NULL || analysisData->rttInfo == NULL)
+	if (analysisData == NULL)
 	{
 		return;
 	}
 
 	g_hash_table_destroy(analysisData->rttInfo);
-	analysisData->rttInfo= NULL;
 
 	if (syncState->stats)
 	{
+		AnalysisStatsEval* stats= analysisData->stats;
+
+		for (i= 0; i < syncState->traceNb; i++)
+		{
+			free(stats->messageStats[i]);
+		}
+		free(stats->messageStats);
+
+		g_hash_table_destroy(stats->exchangeRtt);
+
+#ifdef HAVE_LIBGLPK
+		freeAllFactors(stats->chFactorsArray);
+		freeAllFactors(stats->lpFactorsArray);
+#endif
+
+		free(stats);
+	}
+
+	if (syncState->graphsStream)
+	{
+		AnalysisGraphsEval* graphs= analysisData->graphs;
+
+		if (graphs->histograms)
+		{
+			g_hash_table_destroy(graphs->histograms);
+		}
+
 		for (i= 0; i < syncState->traceNb; i++)
 		{
-			free(analysisData->stats->messageStats[i]);
+			free(graphs->bounds[i]);
 		}
-		free(analysisData->stats->messageStats);
+		free(graphs->bounds);
+
+#ifdef HAVE_LIBGLPK
+		for (i= 0; i < syncState->traceNb; i++)
+		{
+			unsigned int j;
 
-		g_hash_table_destroy(analysisData->stats->exchangeRtt);
+			for (j= 0; j < i; j++)
+			{
+				// There seems to be a memory leak in glpk, valgrind reports a
+				// loss (reachable) even if the problem is deleted
+				glp_delete_prob(graphs->lps[i][j]);
+			}
+			free(graphs->lps[i]);
+		}
+		free(graphs->lps);
 
-		free(analysisData->stats);
+		if (!syncState->stats)
+		{
+			freeAllFactors(graphs->lpFactorsArray);
+		}
+#endif
+
+		free(graphs);
 	}
 
-	if (syncState->graphsStream && analysisData->graphs)
+	if (syncState->stats || syncState->graphsStream)
 	{
-		g_hash_table_destroy(analysisData->graphs);
+		analysisData->chullSS->analysisModule->destroyAnalysis(analysisData->chullSS);
+		free(analysisData->chullSS);
 	}
 
 	free(syncState->analysisData);
@@ -453,28 +623,31 @@ static void destroyAnalysisEval(SyncState* const syncState)
  *   syncState     container for synchronization data
  *   message       structure containing the events
  */
-static void analyzeMessageEval(SyncState* const syncState, Message* const message)
+static void analyzeMessageEval(SyncState* const syncState, Message* const
+	message)
 {
 	AnalysisDataEval* analysisData= syncState->analysisData;
-	MessageStats* messageStats=
-		&analysisData->stats->messageStats[message->outE->traceNum][message->inE->traceNum];;
+	MessageStats* messageStats;
 	double* rtt;
 	double tt;
 	struct RttKey rttKey;
 
-	if (!syncState->stats)
-	{
-		return;
-	}
-
 	g_assert(message->inE->type == TCP);
 
-	messageStats->total++;
+	if (syncState->stats)
+	{
+		messageStats=
+			&analysisData->stats->messageStats[message->outE->traceNum][message->inE->traceNum];
+		messageStats->total++;
+	}
 
 	tt= wallTimeSub(&message->inE->wallTime, &message->outE->wallTime);
 	if (tt <= 0)
 	{
-		messageStats->inversionNb++;
+		if (syncState->stats)
+		{
+			messageStats->inversionNb++;
+		}
 	}
 	else if (syncState->graphsStream)
 	{
@@ -484,48 +657,63 @@ static void analyzeMessageEval(SyncState* const syncState, Message* const messag
 			.daddr=MAX(message->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
 				message->inE->event.tcpEvent->segmentKey->connectionKey.daddr),
 		};
-		AnalysisGraphEval* graph= g_hash_table_lookup(analysisData->graphs,
-			&rttKey);
+		AnalysisHistogramEval* histogram=
+			g_hash_table_lookup(analysisData->graphs->histograms, &rttKey);
 
-		if (graph == NULL)
+		if (histogram == NULL)
 		{
 			struct RttKey* tableKey= malloc(sizeof(*tableKey));
 
-			graph= constructAnalysisGraphEval(syncState->graphsDir, &rttKey);
+			histogram= constructAnalysisHistogramEval(syncState->graphsDir, &rttKey);
 			memcpy(tableKey, &rttKey, sizeof(*tableKey));
-			g_hash_table_insert(analysisData->graphs, tableKey, graph);
+			g_hash_table_insert(analysisData->graphs->histograms, tableKey, histogram);
 		}
 
 		if (message->inE->event.udpEvent->datagramKey->saddr <
 			message->inE->event.udpEvent->datagramKey->daddr)
 		{
-			hitBin(&graph->ttSendBins, tt);
+			hitBin(&histogram->ttSendBins, tt);
 		}
 		else
 		{
-			hitBin(&graph->ttRecvBins, tt);
+			hitBin(&histogram->ttRecvBins, tt);
 		}
 	}
 
-	rttKey.saddr=
-		message->inE->event.tcpEvent->segmentKey->connectionKey.saddr;
-	rttKey.daddr=
-		message->inE->event.tcpEvent->segmentKey->connectionKey.daddr;
-	rtt= g_hash_table_lookup(analysisData->rttInfo, &rttKey);
-	g_debug("rttInfo, looking up (%u, %u)->(%f)", rttKey.saddr,
-		rttKey.daddr, rtt ? *rtt : NAN);
-
-	if (rtt)
+	if (syncState->stats)
 	{
-		g_debug("rttInfo, tt: %f rtt / 2: %f", tt, *rtt / 2.);
-		if (tt < *rtt / 2.)
+		rttKey.saddr=
+			message->inE->event.tcpEvent->segmentKey->connectionKey.saddr;
+		rttKey.daddr=
+			message->inE->event.tcpEvent->segmentKey->connectionKey.daddr;
+		rtt= g_hash_table_lookup(analysisData->rttInfo, &rttKey);
+		g_debug("rttInfo, looking up (%u, %u)->(%f)", rttKey.saddr,
+			rttKey.daddr, rtt ? *rtt : NAN);
+
+		if (rtt)
 		{
-			messageStats->tooFastNb++;
+			g_debug("rttInfo, tt: %f rtt / 2: %f", tt, *rtt / 2.);
+			if (tt < *rtt / 2.)
+			{
+				messageStats->tooFastNb++;
+			}
+		}
+		else
+		{
+			messageStats->noRTTInfoNb++;
 		}
 	}
-	else
+
+	if (syncState->graphsStream)
+	{
+		updateBounds(analysisData->graphs->bounds, message->inE,
+			message->outE);
+	}
+
+	if (syncState->stats || syncState->graphsStream)
 	{
-		messageStats->noRTTInfoNb++;
+		analysisData->chullSS->analysisModule->analyzeMessage(analysisData->chullSS,
+			message);
 	}
 }
 
@@ -539,7 +727,8 @@ static void analyzeMessageEval(SyncState* const syncState, Message* const messag
  *   syncState     container for synchronization data
  *   exchange      structure containing the messages
  */
-static void analyzeExchangeEval(SyncState* const syncState, Exchange* const exchange)
+static void analyzeExchangeEval(SyncState* const syncState, Exchange* const
+	exchange)
 {
 	AnalysisDataEval* analysisData= syncState->analysisData;
 	Message* m1= g_queue_peek_tail(exchange->acks);
@@ -547,11 +736,6 @@ static void analyzeExchangeEval(SyncState* const syncState, Exchange* const exch
 	struct RttKey* rttKey;
 	double* rtt, * exchangeRtt;
 
-	if (!syncState->stats)
-	{
-		return;
-	}
-
 	g_assert(m1->inE->type == TCP);
 
 	// (T2 - T1) - (T3 - T4)
@@ -569,34 +753,49 @@ static void analyzeExchangeEval(SyncState* const syncState, Exchange* const exch
 
 	if (syncState->graphsStream)
 	{
-		AnalysisGraphEval* graph= g_hash_table_lookup(analysisData->graphs,
-			rttKey);
+		AnalysisHistogramEval* histogram=
+			g_hash_table_lookup(analysisData->graphs->histograms, rttKey);
 
-		if (graph == NULL)
+		if (histogram == NULL)
 		{
 			struct RttKey* tableKey= malloc(sizeof(*tableKey));
 
-			graph= constructAnalysisGraphEval(syncState->graphsDir, rttKey);
+			histogram= constructAnalysisHistogramEval(syncState->graphsDir,
+				rttKey);
 			memcpy(tableKey, rttKey, sizeof(*tableKey));
-			g_hash_table_insert(analysisData->graphs, tableKey, graph);
+			g_hash_table_insert(analysisData->graphs->histograms, tableKey,
+				histogram);
 		}
 
-		hitBin(&graph->hrttBins, *rtt / 2);
+		hitBin(&histogram->hrttBins, *rtt / 2);
 	}
 
-	exchangeRtt= g_hash_table_lookup(analysisData->stats->exchangeRtt,
-		rttKey);
-
-	if (exchangeRtt)
+	if (syncState->stats)
 	{
-		if (*rtt < *exchangeRtt)
+		exchangeRtt= g_hash_table_lookup(analysisData->stats->exchangeRtt,
+			rttKey);
+
+		if (exchangeRtt)
 		{
-			g_hash_table_replace(analysisData->stats->exchangeRtt, rttKey, rtt);
+			if (*rtt < *exchangeRtt)
+			{
+				g_hash_table_replace(analysisData->stats->exchangeRtt, rttKey, rtt);
+			}
+			else
+			{
+				free(rttKey);
+				free(rtt);
+			}
+		}
+		else
+		{
+			g_hash_table_insert(analysisData->stats->exchangeRtt, rttKey, rtt);
 		}
 	}
 	else
 	{
-		g_hash_table_insert(analysisData->stats->exchangeRtt, rttKey, rtt);
+		free(rttKey);
+		free(rtt);
 	}
 }
 
@@ -610,73 +809,117 @@ static void analyzeExchangeEval(SyncState* const syncState, Exchange* const exch
  *   syncState     container for synchronization data
  *   broadcast     structure containing the events
  */
-static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const broadcast)
+static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const
+	broadcast)
 {
-	AnalysisDataEval* analysisData;
-	double sum= 0, squaresSum= 0;
-	double y;
+	AnalysisDataEval* analysisData= syncState->analysisData;
 
-	if (!syncState->stats)
+	if (syncState->stats)
 	{
-		return;
-	}
+		double sum= 0, squaresSum= 0;
+		double y;
 
-	analysisData= (AnalysisDataEval*) syncState->analysisData;
+		g_queue_foreach(broadcast->events, &gfSum, &sum);
+		g_queue_foreach(broadcast->events, &gfSumSquares, &squaresSum);
 
-	g_queue_foreach(broadcast->events, &gfSum, &sum);
-	g_queue_foreach(broadcast->events, &gfSumSquares, &squaresSum);
+		analysisData->stats->broadcastNb++;
+		// Because of numerical errors, this can at times be < 0
+		y= squaresSum / g_queue_get_length(broadcast->events) - pow(sum /
+			g_queue_get_length(broadcast->events), 2.);
+		if (y > 0)
+		{
+			analysisData->stats->broadcastStdevSum+= sqrt(y);
+		}
 
-	analysisData->stats->broadcastNb++;
-	// Because of numerical errors, this can at times be < 0
-	y= squaresSum / g_queue_get_length(broadcast->events) - pow(sum /
-		g_queue_get_length(broadcast->events), 2.);
-	if (y > 0)
+		if (syncState->traceNb == 2 && g_queue_get_length(broadcast->events)
+			== 2)
+		{
+			Event* e0, * e1;
+			double dd;
+
+			e0= g_queue_peek_head(broadcast->events);
+			e1= g_queue_peek_tail(broadcast->events);
+			if (e0->traceNum > e1->traceNum)
+			{
+				Event* tmp;
+
+				tmp= e0;
+				e0= e1;
+				e1= tmp;
+			}
+
+			dd= wallTimeSub(&e1->wallTime, &e0->wallTime);
+
+			analysisData->stats->broadcastPairNb++;
+			if (dd < analysisData->stats->broadcastRangeMin)
+			{
+				analysisData->stats->broadcastRangeMin= dd;
+			}
+			if (dd > analysisData->stats->broadcastRangeMax)
+			{
+				analysisData->stats->broadcastRangeMax= dd;
+			}
+
+			analysisData->stats->broadcastSum+= dd;
+			analysisData->stats->broadcastSumSquares+= pow(dd, 2);
+		}
+	}
+
+	if (syncState->graphsStream)
 	{
-		analysisData->stats->broadcastDiffSum+= sqrt(y);
+		unsigned int i, j;
+		GArray* events;
+		unsigned int eventNb= broadcast->events->length;
+
+		events= g_array_sized_new(FALSE, FALSE, sizeof(Event*), eventNb);
+		g_queue_foreach(broadcast->events, &gfAddEventToArray, events);
+
+		for (i= 0; i < eventNb; i++)
+		{
+			for (j= 0; j < eventNb; j++)
+			{
+				Event* eventI= g_array_index(events, Event*, i), * eventJ=
+					g_array_index(events, Event*, j);
+
+				if (eventI->traceNum < eventJ->traceNum)
+				{
+					updateBounds(analysisData->graphs->bounds, eventI, eventJ);
+				}
+			}
+		}
+
+		g_array_free(events, TRUE);
 	}
 }
 
 
 /*
- * Finalize the factor calculations
- *
- * Since this module does not really calculate factors, identity factors are
- * returned.
+ * Finalize the factor calculations. Since this module does not really
+ * calculate factors, absent factors are returned. Instead, histograms are
+ * written out and histogram structures are freed.
  *
  * Args:
  *   syncState     container for synchronization data.
  *
  * Returns:
- *   Factors[traceNb] identity factors for each trace
+ *   AllFactors*   synchronization factors for each trace pair
  */
-static GArray* finalizeAnalysisEval(SyncState* const syncState)
+static AllFactors* finalizeAnalysisEval(SyncState* const syncState)
 {
-	GArray* factors;
-	unsigned int i;
 	AnalysisDataEval* analysisData= syncState->analysisData;
 
-	if (syncState->graphsStream && analysisData->graphs)
+	if (syncState->graphsStream && analysisData->graphs->histograms)
 	{
-		g_hash_table_foreach(analysisData->graphs, &ghfWriteGraph, &(struct
-				WriteGraphInfo) {.rttInfo= analysisData->rttInfo,
-			.graphsStream= syncState->graphsStream});
-		g_hash_table_destroy(analysisData->graphs);
-		analysisData->graphs= NULL;
+		g_hash_table_foreach(analysisData->graphs->histograms,
+			&ghfWriteHistogram, &(struct WriteHistogramInfo) {.rttInfo=
+			analysisData->rttInfo, .graphsStream= syncState->graphsStream});
+		g_hash_table_destroy(analysisData->graphs->histograms);
+		analysisData->graphs->histograms= NULL;
 	}
 
-	factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors),
-		syncState->traceNb);
-	g_array_set_size(factors, syncState->traceNb);
-	for (i= 0; i < syncState->traceNb; i++)
-	{
-		Factors* e;
+	finalizeAnalysisEvalLP(syncState);
 
-		e= &g_array_index(factors, Factors, i);
-		e->drift= 1.;
-		e->offset= 0.;
-	}
-
-	return factors;
+	return createAllFactors(syncState->traceNb);
 }
 
 
@@ -704,11 +947,27 @@ static void printAnalysisStatsEval(SyncState* const syncState)
 	printf("Synchronization evaluation analysis stats:\n");
 	if (analysisData->stats->broadcastNb)
 	{
-		printf("\tsum of broadcast differential delays: %g\n",
-			analysisData->stats->broadcastDiffSum);
-		printf("\taverage broadcast differential delays: %g\n",
-			analysisData->stats->broadcastDiffSum /
+		printf("\tBroadcast differential delay:\n");
+		printf("\t\tsum of standard deviations: %g\n",
+			analysisData->stats->broadcastStdevSum);
+		printf("\t\taverage standard deviation: %g\n",
+			analysisData->stats->broadcastStdevSum /
 			analysisData->stats->broadcastNb);
+
+		if (syncState->traceNb == 2)
+		{
+			printf("\t\tdifferential delay range: [ %g .. %g ]\n",
+				analysisData->stats->broadcastRangeMin,
+				analysisData->stats->broadcastRangeMax);
+			printf("\t\tdifferential delay average: %g\n",
+				analysisData->stats->broadcastSum /
+				analysisData->stats->broadcastPairNb);
+			printf("\t\tdifferential delay standard deviation: %g\n",
+				sqrt(analysisData->stats->broadcastSumSquares /
+					analysisData->stats->broadcastPairNb -
+					pow(analysisData->stats->broadcastSum /
+						analysisData->stats->broadcastPairNb, 2)));
+		}
 	}
 
 	printf("\tIndividual evaluation:\n"
@@ -732,13 +991,13 @@ static void printAnalysisStatsEval(SyncState* const syncState)
 					&analysisData->stats->messageStats[loopValues[k].t1][loopValues[k].t2];
 
 				printf("\t\t%3d - %-3d   ", loopValues[k].t1, loopValues[k].t2);
-				printf("%u (%u%%)%n", messageStats->inversionNb, (unsigned
-						int) ceil((double) messageStats->inversionNb /
-						messageStats->total * 100), &charNb);
+				printf("%u (%.2f%%)%n", messageStats->inversionNb, (double)
+					messageStats->inversionNb / messageStats->total * 100,
+					&charNb);
 				printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ");
-				printf("%u (%u%%)%n", messageStats->tooFastNb, (unsigned int)
-					ceil((double) messageStats->tooFastNb /
-						messageStats->total * 100), &charNb);
+				printf("%u (%.2f%%)%n", messageStats->tooFastNb, (double)
+					messageStats->tooFastNb / messageStats->total * 100,
+					&charNb);
 				printf("%*s%-10u   %u\n", 17 - charNb > 0 ? 17 - charNb + 1:
 					1, " ", messageStats->noRTTInfoNb, messageStats->total);
 
@@ -751,11 +1010,11 @@ static void printAnalysisStatsEval(SyncState* const syncState)
 	}
 
 	printf("\t\t  total     ");
-	printf("%u (%u%%)%n", totInversion, (unsigned int) ceil((double)
-			totInversion / totTotal * 100), &charNb);
+	printf("%u (%.2f%%)%n", totInversion, (double) totInversion / totTotal *
+		100, &charNb);
 	printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ");
-	printf("%u (%u%%)%n", totTooFast, (unsigned int) ceil((double) totTooFast
-			/ totTotal * 100), &charNb);
+	printf("%u (%.2f%%)%n", totTooFast, (double) totTooFast / totTotal * 100,
+		&charNb);
 	printf("%*s%-10u   %u\n", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ",
 		totNoInfo, totTotal);
 
@@ -763,6 +1022,47 @@ static void printAnalysisStatsEval(SyncState* const syncState)
 		"\t\tHost pair                          RTT from exchanges  RTTs from file (ms)\n");
 	g_hash_table_foreach(analysisData->stats->exchangeRtt,
 		&ghfPrintExchangeRtt, analysisData->rttInfo);
+
+#ifdef HAVE_LIBGLPK
+	printf("\tConvex hull factors comparisons:\n"
+		"\t\tTrace pair  Factors type  Differences (lp - chull)\n"
+		"\t\t                          a0                    a1\n"
+		"\t\t                          Min        Max        Min        Max\n");
+
+	for (i= 0; i < syncState->traceNb; i++)
+	{
+		for (j= 0; j < i; j++)
+		{
+			PairFactors* chFactors=
+				&analysisData->stats->chFactorsArray->pairFactors[i][j];
+			PairFactors* lpFactors=
+				&analysisData->stats->lpFactorsArray->pairFactors[i][j];
+
+			printf("\t\t%3d - %-3d   ", i, j);
+			if (lpFactors->type == chFactors->type)
+			{
+				if (lpFactors->type == ACCURATE)
+				{
+					printf("%-13s %-10.4g %-10.4g %-10.4g %.4g\n",
+						approxNames[lpFactors->type],
+						lpFactors->min->offset - chFactors->min->offset,
+						lpFactors->max->offset - chFactors->max->offset,
+						lpFactors->min->drift - chFactors->min->drift,
+						lpFactors->max->drift - chFactors->max->drift);
+				}
+				else if (lpFactors->type == ABSENT)
+				{
+					printf("%s\n", approxNames[lpFactors->type]);
+				}
+			}
+			else
+			{
+				printf("Different! %s and %s\n", approxNames[lpFactors->type],
+					approxNames[chFactors->type]);
+			}
+		}
+	}
+#endif
 }
 
 
@@ -774,7 +1074,8 @@ static void printAnalysisStatsEval(SyncState* const syncState)
  *   value:        double*, RTT estimated from exchanges
  *   user_data     GHashTable* rttInfo
  */
-static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer user_data)
+static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer
+	user_data)
 {
 	char addr1[16], addr2[16];
 	struct RttKey* rttKey1= key;
@@ -1185,3 +1486,555 @@ static double binEnd(const unsigned int binNum)
 		return INFINITY;
 	}
 }
+
+
+/*
+ * Return the total number of elements in the "normal" bins (not underflow or
+ * overflow)
+ *
+ * Args:
+ *   bins:         the structure containing bins to build a histrogram
+ */
+static uint32_t normalTotal(struct Bins* const bins)
+{
+	return bins->total - bins->bin[0] - bins->bin[BIN_NB - 1];
+}
+
+
+/* Update the bounds between two traces
+ *
+ * Args:
+ *   bounds:       the array containing all the trace-pair bounds
+ *   e1, e2:       the two related events
+ */
+static void updateBounds(Bounds** const bounds, Event* const e1, Event* const
+	e2)
+{
+	unsigned int traceI, traceJ;
+	uint64_t messageTime;
+	Bounds* tpBounds;
+
+	if (e1->traceNum < e2->traceNum)
+	{
+		traceI= e2->traceNum;
+		traceJ= e1->traceNum;
+		messageTime= e1->cpuTime;
+	}
+	else
+	{
+		traceI= e1->traceNum;
+		traceJ= e2->traceNum;
+		messageTime= e2->cpuTime;
+	}
+	tpBounds= &bounds[traceI][traceJ];
+
+	if (messageTime < tpBounds->min)
+	{
+		tpBounds->min= messageTime;
+	}
+	if (messageTime > tpBounds->max)
+	{
+		tpBounds->max= messageTime;
+	}
+}
+
+
+#ifdef HAVE_LIBGLPK
+/*
+ * Create the linear programming problem containing the constraints defined by
+ * two half-hulls. The objective function and optimization directions are not
+ * written.
+ *
+ * Args:
+ *   syncState:    container for synchronization data
+ *   i:            first trace number
+ *   j:            second trace number, garanteed to be larger than i
+ * Returns:
+ *   A new glp_prob*, this problem must be freed by the caller with
+ *   glp_delete_prob()
+ */
+static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const
+	upperHull)
+{
+	unsigned int it;
+	const int zero= 0;
+	const double zeroD= 0.;
+	glp_prob* lp= glp_create_prob();
+	unsigned int hullPointNb= g_queue_get_length(lowerHull) +
+		g_queue_get_length(upperHull);
+	GArray* iArray= g_array_sized_new(FALSE, FALSE, sizeof(int), hullPointNb +
+		1);
+	GArray* jArray= g_array_sized_new(FALSE, FALSE, sizeof(int), hullPointNb +
+		1);
+	GArray* aArray= g_array_sized_new(FALSE, FALSE, sizeof(double),
+		hullPointNb + 1);
+	struct {
+		GQueue* hull;
+		struct LPAddRowInfo rowInfo;
+	} loopValues[2]= {
+		{lowerHull, {lp, GLP_UP, iArray, jArray, aArray}},
+		{upperHull, {lp, GLP_LO, iArray, jArray, aArray}},
+	};
+
+	// Create the LP problem
+	glp_term_out(GLP_OFF);
+	if (hullPointNb > 0)
+	{
+		glp_add_rows(lp, hullPointNb);
+	}
+	glp_add_cols(lp, 2);
+
+	glp_set_col_name(lp, 1, "a0");
+	glp_set_col_bnds(lp, 1, GLP_FR, 0., 0.);
+	glp_set_col_name(lp, 2, "a1");
+	glp_set_col_bnds(lp, 2, GLP_LO, 0., 0.);
+
+	// Add row constraints
+	g_array_append_val(iArray, zero);
+	g_array_append_val(jArray, zero);
+	g_array_append_val(aArray, zeroD);
+
+	for (it= 0; it < sizeof(loopValues) / sizeof(*loopValues); it++)
+	{
+		g_queue_foreach(loopValues[it].hull, &gfLPAddRow,
+			&loopValues[it].rowInfo);
+	}
+
+	g_assert_cmpuint(iArray->len, ==, jArray->len);
+	g_assert_cmpuint(jArray->len, ==, aArray->len);
+	g_assert_cmpuint(aArray->len - 1, ==, hullPointNb * 2);
+
+	glp_load_matrix(lp, aArray->len - 1, &g_array_index(iArray, int, 0),
+		&g_array_index(jArray, int, 0), &g_array_index(aArray, double, 0));
+
+	glp_scale_prob(lp, GLP_SF_AUTO);
+
+	g_array_free(iArray, TRUE);
+	g_array_free(jArray, TRUE);
+	g_array_free(aArray, TRUE);
+
+	return lp;
+}
+
+
+/*
+ * A GFunc for g_queue_foreach(). Add constraints and bounds for one row.
+ *
+ * Args:
+ *   data          Point*, synchronization point for which to add an LP row
+ *                 (a constraint)
+ *   user_data     LPAddRowInfo*
+ */
+static void gfLPAddRow(gpointer data, gpointer user_data)
+{
+	Point* p= data;
+	struct LPAddRowInfo* rowInfo= user_data;
+	int indexes[2];
+	double constraints[2];
+
+	indexes[0]= g_array_index(rowInfo->iArray, int, rowInfo->iArray->len - 1) + 1;
+	indexes[1]= indexes[0];
+
+	if (rowInfo->boundType == GLP_UP)
+	{
+		glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_UP, 0., p->y);
+	}
+	else if (rowInfo->boundType == GLP_LO)
+	{
+		glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_LO, p->y, 0.);
+	}
+	else
+	{
+		g_assert_not_reached();
+	}
+
+	g_array_append_vals(rowInfo->iArray, indexes, 2);
+	indexes[0]= 1;
+	indexes[1]= 2;
+	g_array_append_vals(rowInfo->jArray, indexes, 2);
+	constraints[0]= 1.;
+	constraints[1]= p->x;
+	g_array_append_vals(rowInfo->aArray, constraints, 2);
+}
+
+
+/*
+ * Calculate min or max correction factors (as possible) using an LP problem.
+ *
+ * Args:
+ *   lp:           A linear programming problem with constraints and bounds
+ *                 initialized.
+ *   direction:    The type of factors desired. Use GLP_MAX for max
+ *                 approximation factors (a1, the drift or slope is the
+ *                 largest) and GLP_MIN in the other case.
+ *
+ * Returns:
+ *   If the calculation was successful, a new Factors struct. Otherwise, NULL.
+ *   The calculation will fail if the hull assumptions are not respected.
+ */
+static Factors* calculateFactors(glp_prob* const lp, const int direction)
+{
+	int retval, status;
+	Factors* factors;
+
+	glp_set_obj_coef(lp, 1, 0.);
+	glp_set_obj_coef(lp, 2, 1.);
+
+	glp_set_obj_dir(lp, direction);
+	retval= glp_simplex(lp, NULL);
+	status= glp_get_status(lp);
+
+	if (retval == 0 && status == GLP_OPT)
+	{
+		factors= malloc(sizeof(Factors));
+		factors->offset= glp_get_col_prim(lp, 1);
+		factors->drift= glp_get_col_prim(lp, 2);
+	}
+	else
+	{
+		factors= NULL;
+	}
+
+	return factors;
+}
+
+
+/*
+ * Calculate min, max and approx correction factors (as possible) using an LP
+ * problem.
+ *
+ * Args:
+ *   lp:           A linear programming problem with constraints and bounds
+ *                 initialized.
+ *
+ * Returns:
+ *   Please note that the approximation type may be ACCURATE, INCOMPLETE or
+ *   ABSENT. Unlike in analysis_chull, ABSENT is also used when the hulls do
+ *   not respect assumptions.
+ */
+static void calculateCompleteFactors(glp_prob* const lp, PairFactors* factors)
+{
+	factors->min= calculateFactors(lp, GLP_MIN);
+	factors->max= calculateFactors(lp, GLP_MAX);
+
+	if (factors->min && factors->max)
+	{
+		factors->type= ACCURATE;
+		calculateFactorsMiddle(factors);
+	}
+	else if (factors->min || factors->max)
+	{
+		factors->type= INCOMPLETE;
+		factors->approx= NULL;
+	}
+	else
+	{
+		factors->type= ABSENT;
+		factors->approx= NULL;
+	}
+}
+
+
+/*
+ * A GFunc for g_queue_foreach()
+ *
+ * Args:
+ *   data          Point*, a convex hull point
+ *   user_data     GArray*, an array of convex hull point absisca values, as
+ *                 double
+ */
+static void gfAddAbsiscaToArray(gpointer data, gpointer user_data)
+{
+	Point* p= data;
+	GArray* a= user_data;
+	double v= p->x;
+
+	g_array_append_val(a, v);
+}
+
+
+/*
+ * A GCompareFunc for g_array_sort()
+ *
+ * Args:
+ *   a, b          double*, absisca values
+ *
+ * Returns:
+ *   "returns less than zero for first arg is less than second arg, zero for
+ *   equal, greater zero if first arg is greater than second arg"
+ *   - the great glib documentation
+ */
+static gint gcfCompareDouble(gconstpointer a, gconstpointer b)
+{
+	if (*(double*) a < *(double*) b)
+	{
+		return -1;
+	}
+	else if (*(double*) a > *(double*) b)
+	{
+		return 1;
+	}
+	else
+	{
+		return 0;
+	}
+}
+#endif
+
+
+/*
+ * Compute synchronization factors using a linear programming approach.
+ * Compute the factors using analysis_chull. Compare the two.
+ *
+ * When the solver library, glpk, is not available at build time, only compute
+ * the factors using analysis_chull. This is to make sure that module runs its
+ * finalize function so that its graph functions can be called later.
+ *
+ * Args:
+ *   syncState:    container for synchronization data
+ */
+static void finalizeAnalysisEvalLP(SyncState* const syncState)
+{
+	AnalysisDataEval* analysisData= syncState->analysisData;
+#ifdef HAVE_LIBGLPK
+	unsigned int i, j;
+	AnalysisDataCHull* chAnalysisData= analysisData->chullSS->analysisData;
+	AllFactors* lpFactorsArray;
+
+	if (!syncState->stats && !syncState->graphsStream)
+	{
+		return;
+	}
+
+	/* Because of matching_distributor, this analysis may be called twice.
+	 * Only run it once */
+	if ((syncState->graphsStream && analysisData->graphs->lps != NULL) ||
+		(syncState->stats && analysisData->stats->chFactorsArray != NULL))
+	{
+		return;
+	}
+
+	lpFactorsArray= createAllFactors(syncState->traceNb);
+
+	if (syncState->stats)
+	{
+		analysisData->stats->chFactorsArray=
+			calculateAllFactors(analysisData->chullSS);
+		analysisData->stats->lpFactorsArray= lpFactorsArray;
+	}
+
+	if (syncState->graphsStream)
+	{
+		analysisData->graphs->lps= malloc(syncState->traceNb *
+			sizeof(glp_prob**));
+		for (i= 0; i < syncState->traceNb; i++)
+		{
+			analysisData->graphs->lps[i]= malloc(i * sizeof(glp_prob*));
+		}
+		analysisData->graphs->lpFactorsArray= lpFactorsArray;
+	}
+
+	for (i= 0; i < syncState->traceNb; i++)
+	{
+		for (j= 0; j < i; j++)
+		{
+			glp_prob* lp;
+
+			// Create the LP problem
+			lp= lpCreateProblem(chAnalysisData->hullArray[i][j],
+				chAnalysisData->hullArray[j][i]);
+
+			// Use the LP problem to find the correction factors for this pair of
+			// traces
+			calculateCompleteFactors(lp, &lpFactorsArray->pairFactors[i][j]);
+
+			if (syncState->graphsStream)
+			{
+				analysisData->graphs->lps[i][j]= lp;
+			}
+			else
+			{
+				glp_delete_prob(lp);
+			}
+		}
+	}
+#endif
+
+	freeAllFactors(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS));
+}
+
+
+/*
+ * Compute synchronization accuracy information using a linear programming
+ * approach. Write the neccessary data files and plot lines in the gnuplot
+ * script.
+ *
+ * When the solver library, glpk, is not available at build time nothing is
+ * actually produced.
+ *
+ * Args:
+ *   syncState:    container for synchronization data
+ *   i:            first trace number
+ *   j:            second trace number, garanteed to be larger than i
+ */
+static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState,
+	const unsigned int i, const unsigned int j)
+{
+#ifdef HAVE_LIBGLPK
+	unsigned int it;
+	AnalysisDataEval* analysisData= syncState->analysisData;
+	AnalysisGraphsEval* graphs= analysisData->graphs;
+	GQueue*** hullArray= ((AnalysisDataCHull*)
+		analysisData->chullSS->analysisData)->hullArray;
+	PairFactors* lpFactors= &graphs->lpFactorsArray->pairFactors[j][i];
+	glp_prob* lp= graphs->lps[j][i];
+
+	if (lpFactors->type == ACCURATE)
+	{
+		int retval;
+		char* cwd;
+		char fileName[40];
+		FILE* fp;
+		GArray* xValues;
+
+		// Open the data file
+		snprintf(fileName, 40, "analysis_eval_accuracy-%03u_and_%03u.data", i, j);
+		fileName[sizeof(fileName) - 1]= '\0';
+
+		cwd= changeToGraphsDir(syncState->graphsDir);
+
+		if ((fp= fopen(fileName, "w")) == NULL)
+		{
+			g_error(strerror(errno));
+		}
+		fprintf(fp, "#%-24s %-25s %-25s %-25s\n", "x", "middle", "min", "max");
+
+		retval= chdir(cwd);
+		if (retval == -1)
+		{
+			g_error(strerror(errno));
+		}
+		free(cwd);
+
+		// Build the list of absisca values for the points in the accuracy graph
+		xValues= g_array_sized_new(FALSE, FALSE, sizeof(double),
+			g_queue_get_length(hullArray[i][j]) +
+			g_queue_get_length(hullArray[j][i]));
+
+		g_queue_foreach(hullArray[i][j], &gfAddAbsiscaToArray, xValues);
+		g_queue_foreach(hullArray[j][i], &gfAddAbsiscaToArray, xValues);
+
+		g_array_sort(xValues, &gcfCompareDouble);
+
+		/* For each absisca value and each optimisation direction, solve the LP
+		 * and write a line in the data file */
+		for (it= 0; it < xValues->len; it++)
+		{
+			unsigned int it2;
+			int directions[]= {GLP_MIN, GLP_MAX};
+			glp_set_obj_coef(lp, 1, 1.);
+			glp_set_obj_coef(lp, 2, g_array_index(xValues, double, it));
+
+			fprintf(fp, "%25.9f %25.9f", g_array_index(xValues, double, it),
+				lpFactors->approx->offset + lpFactors->approx->drift *
+				g_array_index(xValues, double, it));
+			for (it2= 0; it2 < sizeof(directions) / sizeof(*directions); it2++)
+			{
+				int status;
+
+				glp_set_obj_dir(lp, directions[it2]);
+				retval= glp_simplex(lp, NULL);
+				status= glp_get_status(lp);
+
+				g_assert(retval == 0 && status == GLP_OPT);
+				fprintf(fp, " %25.9f", glp_get_obj_val(lp));
+			}
+			fprintf(fp, "\n");
+		}
+
+		g_array_free(xValues, TRUE);
+		fclose(fp);
+
+		fprintf(syncState->graphsStream,
+			"\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
+				"using 1:(($3 - $2) / clock_freq_%2$u):(($4 - $2) / clock_freq_%2$u) "
+				"title \"Synchronization accuracy\" "
+				"with filledcurves linewidth 2 linetype 1 "
+				"linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i,
+				j);
+	}
+#endif
+}
+
+
+/*
+ * Write the analysis-specific graph lines in the gnuplot script.
+ *
+ * When the solver library, glpk, is not available at build time nothing is
+ * actually produced.
+ *
+ * Args:
+ *   syncState:    container for synchronization data
+ *   i:            first trace number
+ *   j:            second trace number, garanteed to be larger than i
+ */
+static void writeAnalysisTraceTimeForePlotsEval(SyncState* const syncState,
+	const unsigned int i, const unsigned int j)
+{
+#ifdef HAVE_LIBGLPK
+	if (((AnalysisDataEval*)
+			syncState->analysisData)->graphs->lpFactorsArray->pairFactors[j][i].type
+		== ACCURATE)
+	{
+		fprintf(syncState->graphsStream,
+			"\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
+				"using 1:(($3 - $2) / clock_freq_%2$u) notitle "
+				"with lines linewidth 2 linetype 1 "
+				"linecolor rgb \"gray60\", \\\n"
+			"\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
+				"using 1:(($4 - $2) / clock_freq_%2$u) notitle "
+				"with lines linewidth 2 linetype 1 "
+				"linecolor rgb \"gray60\", \\\n", i, j);
+	}
+#endif
+}
+
+
+/*
+ * Write the analysis-specific graph lines in the gnuplot script.
+ *
+ * Args:
+ *   syncState:    container for synchronization data
+ *   i:            first trace number
+ *   j:            second trace number, garanteed to be larger than i
+ */
+static void writeAnalysisTraceTraceBackPlotsEval(SyncState* const syncState,
+	const unsigned int i, const unsigned int j)
+{
+#ifdef HAVE_LIBGLPK
+	fprintf(syncState->graphsStream,
+		"\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
+		"using 1:3:4 "
+		"title \"Synchronization accuracy\" "
+		"with filledcurves linewidth 2 linetype 1 "
+		"linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i, j);
+#endif
+}
+
+
+/*
+ * Write the analysis-specific graph lines in the gnuplot script.
+ *
+ * Args:
+ *   syncState:    container for synchronization data
+ *   i:            first trace number
+ *   j:            second trace number, garanteed to be larger than i
+ */
+static void writeAnalysisTraceTraceForePlotsEval(SyncState* const syncState,
+	const unsigned int i, const unsigned int j)
+{
+	AnalysisDataEval* analysisData= syncState->analysisData;
+
+	analysisData->chullSS->analysisModule->graphFunctions.writeTraceTraceForePlots(analysisData->chullSS,
+		i, j);
+}