Perform trace factor reduction as a separate step
[lttv.git] / lttv / lttv / sync / event_analysis_linreg.c
CommitLineData
70407e86 1/* This file is part of the Linux Trace Toolkit viewer
277e5b53 2 * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
70407e86 3 *
277e5b53
BP
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.
70407e86 8 *
277e5b53
BP
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.
70407e86 13 *
277e5b53
BP
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/>.
70407e86
BP
16 */
17
18// for INFINITY in math.h
19#define _ISOC99_SOURCE
20
21#ifdef HAVE_CONFIG_H
22#include <config.h>
23#endif
24
25#include <math.h>
26#include <stdio.h>
27#include <stdlib.h>
28
2bd4b3e4 29#include "sync_chain.h"
70407e86
BP
30
31#include "event_analysis_linreg.h"
32
33
70407e86
BP
34// Functions common to all analysis modules
35static void initAnalysisLinReg(SyncState* const syncState);
36static void destroyAnalysisLinReg(SyncState* const syncState);
37
10341d26 38static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const exchange);
0a87ec9a 39static AllFactors* finalizeAnalysisLinReg(SyncState* const syncState);
70407e86 40static void printAnalysisStatsLinReg(SyncState* const syncState);
8d7d16dd
BP
41static void writeAnalysisGraphsPlotsLinReg(SyncState* const syncState, const
42 unsigned int i, const unsigned int j);
70407e86
BP
43
44// Functions specific to this module
70407e86 45static void finalizeLSA(SyncState* const syncState);
70407e86
BP
46
47
48static AnalysisModule analysisModuleLinReg= {
49 .name= "linreg",
50 .initAnalysis= &initAnalysisLinReg,
51 .destroyAnalysis= &destroyAnalysisLinReg,
70407e86
BP
52 .analyzeExchange= &analyzeExchangeLinReg,
53 .finalizeAnalysis= &finalizeAnalysisLinReg,
54 .printAnalysisStats= &printAnalysisStatsLinReg,
467066ee 55 .graphFunctions= {
c6356aa7 56 .writeTraceTraceForePlots= &writeAnalysisGraphsPlotsLinReg,
467066ee 57 }
70407e86
BP
58};
59
60
61/*
62 * Analysis module registering function
63 */
2f961b65 64void registerAnalysisLinReg()
70407e86
BP
65{
66 g_queue_push_tail(&analysisModules, &analysisModuleLinReg);
67}
68
69
70/*
71 * Analysis init function
72 *
73 * This function is called at the beginning of a synchronization run for a set
74 * of traces.
75 *
76 * Allocate some of the analysis specific data structures
77 *
78 * Args:
79 * syncState container for synchronization data.
80 * This function allocates these analysisData members:
81 * fitArray
82 * stDev
83 */
84static void initAnalysisLinReg(SyncState* const syncState)
85{
86 unsigned int i;
87 AnalysisDataLinReg* analysisData;
88
89 analysisData= malloc(sizeof(AnalysisDataLinReg));
90 syncState->analysisData= analysisData;
91
92 analysisData->fitArray= malloc(syncState->traceNb * sizeof(Fit*));
93 for (i= 0; i < syncState->traceNb; i++)
94 {
95 analysisData->fitArray[i]= calloc(syncState->traceNb, sizeof(Fit));
96 }
97
98 if (syncState->stats)
99 {
100 analysisData->stDev= malloc(sizeof(double) * syncState->traceNb);
101 }
102}
103
104
105/*
106 * Analysis destroy function
107 *
108 * Free the analysis specific data structures
109 *
110 * Args:
111 * syncState container for synchronization data.
112 * This function deallocates these analysisData members:
113 * fitArray
114 * graphList
115 * stDev
116 */
117static void destroyAnalysisLinReg(SyncState* const syncState)
118{
119 unsigned int i;
120 AnalysisDataLinReg* analysisData;
121
122 analysisData= (AnalysisDataLinReg*) syncState->analysisData;
123
124 if (analysisData == NULL)
125 {
126 return;
127 }
128
129 for (i= 0; i < syncState->traceNb; i++)
130 {
131 free(analysisData->fitArray[i]);
132 }
133 free(analysisData->fitArray);
134
70407e86
BP
135 if (syncState->stats)
136 {
137 free(analysisData->stDev);
138 }
139
140 free(syncState->analysisData);
141 syncState->analysisData= NULL;
142}
143
144
145/*
146 * Perform analysis on a series of event pairs.
147 *
70407e86
BP
148 * Args:
149 * syncState container for synchronization data
10341d26 150 * exchange structure containing the many events
70407e86 151 */
10341d26 152static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const exchange)
70407e86
BP
153{
154 unsigned int ni, nj;
155 double dji, eji;
156 double timoy;
157 Fit* fit;
10341d26 158 Message* ackedMessage;
70407e86
BP
159 AnalysisDataLinReg* analysisData;
160
d5b038ec
BP
161 g_debug("Synchronization calculation, "
162 "%d acked packets - using last one,",
10341d26 163 g_queue_get_length(exchange->acks));
70407e86
BP
164
165 analysisData= (AnalysisDataLinReg*) syncState->analysisData;
10341d26 166 ackedMessage= g_queue_peek_tail(exchange->acks);
70407e86
BP
167
168 // Calculate the intermediate values for the
169 // least-squares analysis
76be6fc2
BP
170 dji= ((double) ackedMessage->inE->cpuTime - (double) ackedMessage->outE->cpuTime
171 + (double) exchange->message->outE->cpuTime - (double)
172 exchange->message->inE->cpuTime) / 2;
173 eji= fabs((double) ackedMessage->inE->cpuTime - (double)
174 ackedMessage->outE->cpuTime - (double) exchange->message->outE->cpuTime +
175 (double) exchange->message->inE->cpuTime) / 2;
176 timoy= ((double) ackedMessage->outE->cpuTime + (double)
177 exchange->message->inE->cpuTime) / 2;
10341d26
BP
178 ni= ackedMessage->outE->traceNum;
179 nj= ackedMessage->inE->traceNum;
70407e86
BP
180 fit= &analysisData->fitArray[nj][ni];
181
182 fit->n++;
183 fit->st+= timoy;
184 fit->st2+= pow(timoy, 2);
185 fit->sd+= dji;
186 fit->sd2+= pow(dji, 2);
187 fit->std+= timoy * dji;
188
189 g_debug("intermediate values: dji= %f ti moy= %f "
190 "ni= %u nj= %u fit: n= %u st= %f st2= %f sd= %f "
191 "sd2= %f std= %f, ", dji, timoy, ni, nj, fit->n,
192 fit->st, fit->st2, fit->sd, fit->sd2, fit->std);
193}
194
195
196/*
197 * Finalize the factor calculations
198 *
199 * The least squares analysis is finalized and finds the factors directly
200 * between each pair of traces that had events together. The traces are
201 * aranged in a graph, a reference trace is chosen and the factors between
202 * this reference and every other trace is calculated. Sometimes it is
203 * necessary to use many graphs when there are "islands" of independent
204 * traces.
205 *
206 * Args:
207 * syncState container for synchronization data.
208 *
209 * Returns:
0a87ec9a 210 * AllFactors* synchronization factors for each trace pair
70407e86 211 */
0a87ec9a 212static AllFactors* finalizeAnalysisLinReg(SyncState* const syncState)
70407e86 213{
0a87ec9a
BP
214 AllFactors* result;
215 unsigned int i, j;
216 AnalysisDataLinReg* analysisData= (AnalysisDataLinReg*)
217 syncState->analysisData;
70407e86 218
70407e86
BP
219 finalizeLSA(syncState);
220
0a87ec9a 221 result= createAllFactors(syncState->traceNb);
70407e86 222
0a87ec9a
BP
223 for (i= 0; i < syncState->traceNb; i++)
224 {
225 for (j= 0; j < syncState->traceNb; j++)
226 {
227 if (i != j)
228 {
229 Fit* fit;
230
231 fit= &analysisData->fitArray[i][j];
232 result->pairFactors[i][j].type= APPROXIMATE;
233 result->pairFactors[i][j].approx= malloc(sizeof(Factors));
234 result->pairFactors[i][j].approx->drift= 1. + fit->x;
235 result->pairFactors[i][j].approx->offset= fit->d0;
236 result->pairFactors[i][j].accuracy= fit->e;
237 }
238 }
239 }
70407e86 240
0a87ec9a 241 return result;
70407e86
BP
242}
243
244
245/*
246 * Print statistics related to analysis. Must be called after
247 * finalizeAnalysis.
248 *
249 * Args:
250 * syncState container for synchronization data.
251 */
252static void printAnalysisStatsLinReg(SyncState* const syncState)
253{
254 unsigned int i, j;
255 AnalysisDataLinReg* analysisData;
256
257 if (!syncState->stats)
258 {
259 return;
260 }
261
262 analysisData= (AnalysisDataLinReg*) syncState->analysisData;
263
264 printf("Linear regression analysis stats:\n");
265
266 printf("\tIndividual synchronization factors:\n");
267
268 for (j= 0; j < syncState->traceNb; j++)
269 {
270 for (i= 0; i < j; i++)
271 {
272 Fit* fit;
273
274 fit= &analysisData->fitArray[j][i];
275 printf("\t\t%3d - %-3d: ", i, j);
276 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit->d0, fit->x <
277 0. ? '-' : '+', fabs(fit->x), fit->e);
278
279 fit= &analysisData->fitArray[i][j];
280 printf("\t\t%3d - %-3d: ", j, i);
281 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit->d0, fit->x <
282 0. ? '-' : '+', fabs(fit->x), fit->e);
283 }
284 }
70407e86
BP
285}
286
287
288/*
289 * Finalize the least-squares analysis. The intermediate values in the fit
290 * array are used to calculate the drift and the offset between each pair of
291 * nodes based on their exchanges.
292 *
293 * Args:
294 * syncState: container for synchronization data.
295 */
296static void finalizeLSA(SyncState* const syncState)
297{
298 unsigned int i, j;
299 AnalysisDataLinReg* analysisData;
300
301 analysisData= (AnalysisDataLinReg*) syncState->analysisData;
302
303 for (i= 0; i < syncState->traceNb; i++)
304 {
305 for (j= 0; j < syncState->traceNb; j++)
306 {
307 if (i != j)
308 {
309 Fit* fit;
310 double delta;
311
312 fit= &analysisData->fitArray[i][j];
313
314 delta= fit->n * fit->st2 - pow(fit->st, 2);
315 fit->x= (fit->n * fit->std - fit->st * fit->sd) / delta;
316 fit->d0= (fit->st2 * fit->sd - fit->st * fit->std) / delta;
317 fit->e= sqrt((fit->sd2 - (fit->n * pow(fit->std, 2) +
318 pow(fit->sd, 2) * fit->st2 - 2 * fit->st * fit->sd
319 * fit->std) / delta) / (fit->n - 2));
320
d5b038ec
BP
321 g_debug("[i= %u j= %u]", i, j);
322 g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g",
70407e86 323 fit->n, fit->st, fit->st2, fit->sd, fit->sd2, fit->std);
d5b038ec
BP
324 g_debug("xij= %g d0ij= %g e= %g", fit->x, fit->d0, fit->e);
325 g_debug("(xji= %g d0ji= %g)", -fit->x / (1 + fit->x),
70407e86
BP
326 -fit->d0 / (1 + fit->x));
327 }
328 }
329 }
330}
331
332
08365995
BP
333/*
334 * Write the analysis-specific graph lines in the gnuplot script.
335 *
336 * Args:
08365995
BP
337 * syncState: container for synchronization data
338 * i: first trace number, on the x axis
339 * j: second trace number, garanteed to be larger than i
340 */
8d7d16dd
BP
341void writeAnalysisGraphsPlotsLinReg(SyncState* const syncState, const unsigned
342 int i, const unsigned int j)
08365995
BP
343{
344 AnalysisDataLinReg* analysisData;
345 Fit* fit;
346
347 analysisData= (AnalysisDataLinReg*) syncState->analysisData;
348 fit= &analysisData->fitArray[j][i];
349
8d7d16dd 350 fprintf(syncState->graphsStream,
08365995
BP
351 "\t%7g + %7g * x "
352 "title \"Linreg conversion\" with lines "
353 "linecolor rgb \"gray60\" linetype 1, \\\n",
354 fit->d0, 1. + fit->x);
355}
This page took 0.038383 seconds and 4 git commands to generate.