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/>.
18 // for INFINITY in math.h
19 #define _ISOC99_SOURCE
29 #include "sync_chain.h"
31 #include "event_analysis_linreg.h"
34 // Functions common to all analysis modules
35 static void initAnalysisLinReg(SyncState
* const syncState
);
36 static void destroyAnalysisLinReg(SyncState
* const syncState
);
38 static void analyzeExchangeLinReg(SyncState
* const syncState
, Exchange
* const exchange
);
39 static AllFactors
* finalizeAnalysisLinReg(SyncState
* const syncState
);
40 static void printAnalysisStatsLinReg(SyncState
* const syncState
);
41 static void writeAnalysisGraphsPlotsLinReg(SyncState
* const syncState
, const
42 unsigned int i
, const unsigned int j
);
44 // Functions specific to this module
45 static void finalizeLSA(SyncState
* const syncState
);
48 static AnalysisModule analysisModuleLinReg
= {
50 .initAnalysis
= &initAnalysisLinReg
,
51 .destroyAnalysis
= &destroyAnalysisLinReg
,
52 .analyzeExchange
= &analyzeExchangeLinReg
,
53 .finalizeAnalysis
= &finalizeAnalysisLinReg
,
54 .printAnalysisStats
= &printAnalysisStatsLinReg
,
56 .writeTraceTraceForePlots
= &writeAnalysisGraphsPlotsLinReg
,
62 * Analysis module registering function
64 void registerAnalysisLinReg()
66 g_queue_push_tail(&analysisModules
, &analysisModuleLinReg
);
71 * Analysis init function
73 * This function is called at the beginning of a synchronization run for a set
76 * Allocate some of the analysis specific data structures
79 * syncState container for synchronization data.
80 * This function allocates these analysisData members:
84 static void initAnalysisLinReg(SyncState
* const syncState
)
87 AnalysisDataLinReg
* analysisData
;
89 analysisData
= malloc(sizeof(AnalysisDataLinReg
));
90 syncState
->analysisData
= analysisData
;
92 analysisData
->fitArray
= malloc(syncState
->traceNb
* sizeof(Fit
*));
93 for (i
= 0; i
< syncState
->traceNb
; i
++)
95 analysisData
->fitArray
[i
]= calloc(syncState
->traceNb
, sizeof(Fit
));
100 analysisData
->stDev
= malloc(sizeof(double) * syncState
->traceNb
);
106 * Analysis destroy function
108 * Free the analysis specific data structures
111 * syncState container for synchronization data.
112 * This function deallocates these analysisData members:
117 static void destroyAnalysisLinReg(SyncState
* const syncState
)
120 AnalysisDataLinReg
* analysisData
;
122 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
124 if (analysisData
== NULL
)
129 for (i
= 0; i
< syncState
->traceNb
; i
++)
131 free(analysisData
->fitArray
[i
]);
133 free(analysisData
->fitArray
);
135 if (syncState
->stats
)
137 free(analysisData
->stDev
);
140 free(syncState
->analysisData
);
141 syncState
->analysisData
= NULL
;
146 * Perform analysis on a series of event pairs.
149 * syncState container for synchronization data
150 * exchange structure containing the many events
152 static void analyzeExchangeLinReg(SyncState
* const syncState
, Exchange
* const exchange
)
158 Message
* ackedMessage
;
159 AnalysisDataLinReg
* analysisData
;
161 g_debug("Synchronization calculation, "
162 "%d acked packets - using last one,",
163 g_queue_get_length(exchange
->acks
));
165 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
166 ackedMessage
= g_queue_peek_tail(exchange
->acks
);
168 // Calculate the intermediate values for the
169 // least-squares analysis
170 dji
= ((double) ackedMessage
->inE
->cpuTime
- (double) ackedMessage
->outE
->cpuTime
171 + (double) exchange
->message
->outE
->cpuTime
- (double)
172 exchange
->message
->inE
->cpuTime
) / 2;
173 timoy
= ((double) ackedMessage
->outE
->cpuTime
+ (double)
174 exchange
->message
->inE
->cpuTime
) / 2;
175 ni
= ackedMessage
->outE
->traceNum
;
176 nj
= ackedMessage
->inE
->traceNum
;
177 fit
= &analysisData
->fitArray
[nj
][ni
];
181 fit
->st2
+= pow(timoy
, 2);
183 fit
->sd2
+= pow(dji
, 2);
184 fit
->std
+= timoy
* dji
;
186 g_debug("intermediate values: dji= %f ti moy= %f "
187 "ni= %u nj= %u fit: n= %u st= %f st2= %f sd= %f "
188 "sd2= %f std= %f, ", dji
, timoy
, ni
, nj
, fit
->n
,
189 fit
->st
, fit
->st2
, fit
->sd
, fit
->sd2
, fit
->std
);
194 * Finalize the factor calculations
196 * The least squares analysis is finalized and finds the factors directly
197 * between each pair of traces that had events together. The traces are
198 * aranged in a graph, a reference trace is chosen and the factors between
199 * this reference and every other trace is calculated. Sometimes it is
200 * necessary to use many graphs when there are "islands" of independent
204 * syncState container for synchronization data.
207 * AllFactors* synchronization factors for each trace pair
209 static AllFactors
* finalizeAnalysisLinReg(SyncState
* const syncState
)
213 AnalysisDataLinReg
* analysisData
= (AnalysisDataLinReg
*)
214 syncState
->analysisData
;
216 finalizeLSA(syncState
);
218 result
= createAllFactors(syncState
->traceNb
);
220 for (i
= 0; i
< syncState
->traceNb
; i
++)
222 for (j
= 0; j
< syncState
->traceNb
; j
++)
228 fit
= &analysisData
->fitArray
[i
][j
];
229 result
->pairFactors
[i
][j
].type
= APPROXIMATE
;
230 result
->pairFactors
[i
][j
].approx
= malloc(sizeof(Factors
));
231 result
->pairFactors
[i
][j
].approx
->drift
= 1. + fit
->x
;
232 result
->pairFactors
[i
][j
].approx
->offset
= fit
->d0
;
233 result
->pairFactors
[i
][j
].accuracy
= fit
->e
;
243 * Print statistics related to analysis. Must be called after
247 * syncState container for synchronization data.
249 static void printAnalysisStatsLinReg(SyncState
* const syncState
)
252 AnalysisDataLinReg
* analysisData
;
254 if (!syncState
->stats
)
259 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
261 printf("Linear regression analysis stats:\n");
263 printf("\tIndividual synchronization factors:\n");
265 for (j
= 0; j
< syncState
->traceNb
; j
++)
267 for (i
= 0; i
< j
; i
++)
271 fit
= &analysisData
->fitArray
[j
][i
];
272 printf("\t\t%3d - %-3d: ", i
, j
);
273 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit
->d0
, fit
->x
<
274 0. ? '-' : '+', fabs(fit
->x
), fit
->e
);
276 fit
= &analysisData
->fitArray
[i
][j
];
277 printf("\t\t%3d - %-3d: ", j
, i
);
278 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit
->d0
, fit
->x
<
279 0. ? '-' : '+', fabs(fit
->x
), fit
->e
);
286 * Finalize the least-squares analysis. The intermediate values in the fit
287 * array are used to calculate the drift and the offset between each pair of
288 * nodes based on their exchanges.
291 * syncState: container for synchronization data.
293 static void finalizeLSA(SyncState
* const syncState
)
296 AnalysisDataLinReg
* analysisData
;
298 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
300 for (i
= 0; i
< syncState
->traceNb
; i
++)
302 for (j
= 0; j
< syncState
->traceNb
; j
++)
309 fit
= &analysisData
->fitArray
[i
][j
];
311 delta
= fit
->n
* fit
->st2
- pow(fit
->st
, 2);
312 fit
->x
= (fit
->n
* fit
->std
- fit
->st
* fit
->sd
) / delta
;
313 fit
->d0
= (fit
->st2
* fit
->sd
- fit
->st
* fit
->std
) / delta
;
314 fit
->e
= sqrt((fit
->sd2
- (fit
->n
* pow(fit
->std
, 2) +
315 pow(fit
->sd
, 2) * fit
->st2
- 2 * fit
->st
* fit
->sd
316 * fit
->std
) / delta
) / (fit
->n
- 2));
318 g_debug("[i= %u j= %u]", i
, j
);
319 g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g",
320 fit
->n
, fit
->st
, fit
->st2
, fit
->sd
, fit
->sd2
, fit
->std
);
321 g_debug("xij= %g d0ij= %g e= %g", fit
->x
, fit
->d0
, fit
->e
);
322 g_debug("(xji= %g d0ji= %g)", -fit
->x
/ (1 + fit
->x
),
323 -fit
->d0
/ (1 + fit
->x
));
331 * Write the analysis-specific graph lines in the gnuplot script.
334 * syncState: container for synchronization data
335 * i: first trace number, on the x axis
336 * j: second trace number, garanteed to be larger than i
338 void writeAnalysisGraphsPlotsLinReg(SyncState
* const syncState
, const unsigned
339 int i
, const unsigned int j
)
341 AnalysisDataLinReg
* analysisData
;
344 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
345 fit
= &analysisData
->fitArray
[j
][i
];
347 fprintf(syncState
->graphsStream
,
349 "title \"Linreg conversion\" with lines "
350 "linecolor rgb \"gray60\" linetype 1, \\\n",
351 fit
->d0
, 1. + fit
->x
);