| 1 | /* This file is part of the Linux Trace Toolkit viewer |
| 2 | * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca> |
| 3 | * |
| 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. |
| 8 | * |
| 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. |
| 13 | * |
| 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/>. |
| 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 | |
| 29 | #include "sync_chain.h" |
| 30 | |
| 31 | #include "event_analysis_linreg.h" |
| 32 | |
| 33 | |
| 34 | // Functions common to all analysis modules |
| 35 | static void initAnalysisLinReg(SyncState* const syncState); |
| 36 | static void destroyAnalysisLinReg(SyncState* const syncState); |
| 37 | |
| 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); |
| 43 | |
| 44 | // Functions specific to this module |
| 45 | static void finalizeLSA(SyncState* const syncState); |
| 46 | |
| 47 | |
| 48 | static AnalysisModule analysisModuleLinReg= { |
| 49 | .name= "linreg", |
| 50 | .initAnalysis= &initAnalysisLinReg, |
| 51 | .destroyAnalysis= &destroyAnalysisLinReg, |
| 52 | .analyzeExchange= &analyzeExchangeLinReg, |
| 53 | .finalizeAnalysis= &finalizeAnalysisLinReg, |
| 54 | .printAnalysisStats= &printAnalysisStatsLinReg, |
| 55 | .graphFunctions= { |
| 56 | .writeTraceTraceForePlots= &writeAnalysisGraphsPlotsLinReg, |
| 57 | } |
| 58 | }; |
| 59 | |
| 60 | |
| 61 | /* |
| 62 | * Analysis module registering function |
| 63 | */ |
| 64 | void registerAnalysisLinReg() |
| 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 | |
| 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 | * |
| 148 | * Args: |
| 149 | * syncState container for synchronization data |
| 150 | * exchange structure containing the many events |
| 151 | */ |
| 152 | static void analyzeExchangeLinReg(SyncState* const syncState, Exchange* const exchange) |
| 153 | { |
| 154 | unsigned int ni, nj; |
| 155 | double dji; |
| 156 | double timoy; |
| 157 | Fit* fit; |
| 158 | Message* ackedMessage; |
| 159 | AnalysisDataLinReg* analysisData; |
| 160 | |
| 161 | g_debug("Synchronization calculation, " |
| 162 | "%d acked packets - using last one,", |
| 163 | g_queue_get_length(exchange->acks)); |
| 164 | |
| 165 | analysisData= (AnalysisDataLinReg*) syncState->analysisData; |
| 166 | ackedMessage= g_queue_peek_tail(exchange->acks); |
| 167 | |
| 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]; |
| 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: |
| 207 | * AllFactors* synchronization factors for each trace pair |
| 208 | */ |
| 209 | static AllFactors* finalizeAnalysisLinReg(SyncState* const syncState) |
| 210 | { |
| 211 | AllFactors* result; |
| 212 | unsigned int i, j; |
| 213 | AnalysisDataLinReg* analysisData= (AnalysisDataLinReg*) |
| 214 | syncState->analysisData; |
| 215 | |
| 216 | finalizeLSA(syncState); |
| 217 | |
| 218 | result= createAllFactors(syncState->traceNb); |
| 219 | |
| 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 | } |
| 237 | |
| 238 | return result; |
| 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 | } |
| 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 | |
| 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)); |
| 324 | } |
| 325 | } |
| 326 | } |
| 327 | } |
| 328 | |
| 329 | |
| 330 | /* |
| 331 | * Write the analysis-specific graph lines in the gnuplot script. |
| 332 | * |
| 333 | * Args: |
| 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 | */ |
| 338 | void writeAnalysisGraphsPlotsLinReg(SyncState* const syncState, const unsigned |
| 339 | int i, const unsigned int j) |
| 340 | { |
| 341 | AnalysisDataLinReg* analysisData; |
| 342 | Fit* fit; |
| 343 | |
| 344 | analysisData= (AnalysisDataLinReg*) syncState->analysisData; |
| 345 | fit= &analysisData->fitArray[j][i]; |
| 346 | |
| 347 | fprintf(syncState->graphsStream, |
| 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 | } |