Commit | Line | Data |
---|---|---|
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 |
35 | static void initAnalysisLinReg(SyncState* const syncState); | |
36 | static void destroyAnalysisLinReg(SyncState* const syncState); | |
37 | ||
10341d26 | 38 | static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const exchange); |
0a87ec9a | 39 | static AllFactors* finalizeAnalysisLinReg(SyncState* const syncState); |
70407e86 | 40 | static void printAnalysisStatsLinReg(SyncState* const syncState); |
8d7d16dd BP |
41 | static void writeAnalysisGraphsPlotsLinReg(SyncState* const syncState, const |
42 | unsigned int i, const unsigned int j); | |
70407e86 BP |
43 | |
44 | // Functions specific to this module | |
70407e86 | 45 | static void finalizeLSA(SyncState* const syncState); |
70407e86 BP |
46 | |
47 | ||
48 | static 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 | 64 | void 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 | */ | |
84 | static 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 | */ | |
117 | static 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 | 152 | static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const exchange) |
70407e86 BP |
153 | { |
154 | unsigned int ni, nj; | |
e865422c | 155 | double dji; |
70407e86 BP |
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; | |
76be6fc2 BP |
173 | timoy= ((double) ackedMessage->outE->cpuTime + (double) |
174 | exchange->message->inE->cpuTime) / 2; | |
10341d26 BP |
175 | ni= ackedMessage->outE->traceNum; |
176 | nj= ackedMessage->inE->traceNum; | |
70407e86 BP |
177 | fit= &analysisData->fitArray[nj][ni]; |
178 | ||
179 | fit->n++; | |
180 | fit->st+= timoy; | |
181 | fit->st2+= pow(timoy, 2); | |
182 | fit->sd+= dji; | |
183 | fit->sd2+= pow(dji, 2); | |
184 | fit->std+= timoy * dji; | |
185 | ||
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); | |
190 | } | |
191 | ||
192 | ||
193 | /* | |
194 | * Finalize the factor calculations | |
195 | * | |
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 | |
201 | * traces. | |
202 | * | |
203 | * Args: | |
204 | * syncState container for synchronization data. | |
205 | * | |
206 | * Returns: | |
0a87ec9a | 207 | * AllFactors* synchronization factors for each trace pair |
70407e86 | 208 | */ |
0a87ec9a | 209 | static AllFactors* finalizeAnalysisLinReg(SyncState* const syncState) |
70407e86 | 210 | { |
0a87ec9a BP |
211 | AllFactors* result; |
212 | unsigned int i, j; | |
213 | AnalysisDataLinReg* analysisData= (AnalysisDataLinReg*) | |
214 | syncState->analysisData; | |
70407e86 | 215 | |
70407e86 BP |
216 | finalizeLSA(syncState); |
217 | ||
0a87ec9a | 218 | result= createAllFactors(syncState->traceNb); |
70407e86 | 219 | |
0a87ec9a BP |
220 | for (i= 0; i < syncState->traceNb; i++) |
221 | { | |
222 | for (j= 0; j < syncState->traceNb; j++) | |
223 | { | |
224 | if (i != j) | |
225 | { | |
226 | Fit* fit; | |
227 | ||
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; | |
234 | } | |
235 | } | |
236 | } | |
70407e86 | 237 | |
0a87ec9a | 238 | return result; |
70407e86 BP |
239 | } |
240 | ||
241 | ||
242 | /* | |
243 | * Print statistics related to analysis. Must be called after | |
244 | * finalizeAnalysis. | |
245 | * | |
246 | * Args: | |
247 | * syncState container for synchronization data. | |
248 | */ | |
249 | static void printAnalysisStatsLinReg(SyncState* const syncState) | |
250 | { | |
251 | unsigned int i, j; | |
252 | AnalysisDataLinReg* analysisData; | |
253 | ||
254 | if (!syncState->stats) | |
255 | { | |
256 | return; | |
257 | } | |
258 | ||
259 | analysisData= (AnalysisDataLinReg*) syncState->analysisData; | |
260 | ||
261 | printf("Linear regression analysis stats:\n"); | |
262 | ||
263 | printf("\tIndividual synchronization factors:\n"); | |
264 | ||
265 | for (j= 0; j < syncState->traceNb; j++) | |
266 | { | |
267 | for (i= 0; i < j; i++) | |
268 | { | |
269 | Fit* fit; | |
270 | ||
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); | |
275 | ||
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); | |
280 | } | |
281 | } | |
70407e86 BP |
282 | } |
283 | ||
284 | ||
285 | /* | |
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. | |
289 | * | |
290 | * Args: | |
291 | * syncState: container for synchronization data. | |
292 | */ | |
293 | static void finalizeLSA(SyncState* const syncState) | |
294 | { | |
295 | unsigned int i, j; | |
296 | AnalysisDataLinReg* analysisData; | |
297 | ||
298 | analysisData= (AnalysisDataLinReg*) syncState->analysisData; | |
299 | ||
300 | for (i= 0; i < syncState->traceNb; i++) | |
301 | { | |
302 | for (j= 0; j < syncState->traceNb; j++) | |
303 | { | |
304 | if (i != j) | |
305 | { | |
306 | Fit* fit; | |
307 | double delta; | |
308 | ||
309 | fit= &analysisData->fitArray[i][j]; | |
310 | ||
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)); | |
317 | ||
d5b038ec BP |
318 | g_debug("[i= %u j= %u]", i, j); |
319 | g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g", | |
70407e86 | 320 | fit->n, fit->st, fit->st2, fit->sd, fit->sd2, fit->std); |
d5b038ec BP |
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), | |
70407e86 BP |
323 | -fit->d0 / (1 + fit->x)); |
324 | } | |
325 | } | |
326 | } | |
327 | } | |
328 | ||
329 | ||
08365995 BP |
330 | /* |
331 | * Write the analysis-specific graph lines in the gnuplot script. | |
332 | * | |
333 | * Args: | |
08365995 BP |
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 | |
337 | */ | |
8d7d16dd BP |
338 | void writeAnalysisGraphsPlotsLinReg(SyncState* const syncState, const unsigned |
339 | int i, const unsigned int j) | |
08365995 BP |
340 | { |
341 | AnalysisDataLinReg* analysisData; | |
342 | Fit* fit; | |
343 | ||
344 | analysisData= (AnalysisDataLinReg*) syncState->analysisData; | |
345 | fit= &analysisData->fitArray[j][i]; | |
346 | ||
8d7d16dd | 347 | fprintf(syncState->graphsStream, |
08365995 BP |
348 | "\t%7g + %7g * x " |
349 | "title \"Linreg conversion\" with lines " | |
350 | "linecolor rgb \"gray60\" linetype 1, \\\n", | |
351 | fit->d0, 1. + fit->x); | |
352 | } |