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, eji;
 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         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;
 178         ni= ackedMessage->outE->traceNum;
 179         nj= ackedMessage->inE->traceNum;
 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:
 210  *   AllFactors*   synchronization factors for each trace pair
 211  */
 212 static AllFactors* finalizeAnalysisLinReg(SyncState* const syncState)
 213 {
 214         AllFactors* result;
 215         unsigned int i, j;
 216         AnalysisDataLinReg* analysisData= (AnalysisDataLinReg*)
 217                 syncState->analysisData;
 218
 219         finalizeLSA(syncState);
 220
 221         result= createAllFactors(syncState->traceNb);
 222
 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         }
 240
 241         return result;
 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  */
 252 static 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         }
 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  */
 296 static 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
 321                                 g_debug("[i= %u j= %u]", i, j);
 322                                 g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g",
 323                                         fit->n, fit->st, fit->st2, fit->sd, fit->sd2, fit->std);
 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),
 326                                         -fit->d0 / (1 + fit->x));
 327                         }
 328                 }
 329         }
 330 }
 331
 332
 333 /*
 334  * Write the analysis-specific graph lines in the gnuplot script.
 335  *
 336  * Args:
 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  */
 341 void writeAnalysisGraphsPlotsLinReg(SyncState* const syncState, const unsigned
 342         int i, const unsigned int j)
 343 {
 344         AnalysisDataLinReg* analysisData;
 345         Fit* fit;
 346
 347         analysisData= (AnalysisDataLinReg*) syncState->analysisData;
 348         fit= &analysisData->fitArray[j][i];
 349
 350         fprintf(syncState->graphsStream,
 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 }