lttv/lttv/sync/event_analysis_linreg.c

   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 }