lttv/lttv/sync/event_analysis_chull.h

   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 #ifndef EVENT_ANALYSIS_CHULL_H
  19 #define EVENT_ANALYSIS_CHULL_H
  20
  21 #include <glib.h>
  22
  23 #include "data_structures.h"
  24
  25 #ifdef HAVE_LIBGLPK
  26 #include <glpk.h>
  27 #endif
  28
  29 typedef struct
  30 {
  31         uint64_t x, y;
  32 } Point;
  33
  34
  35 typedef struct
  36 {
  37         unsigned int dropped;
  38
  39         /* geoFactors is divided into three parts depending on the position of an
  40          * element geoFactors->pairFactors[i][j]:
  41          *   Lower triangular part of the matrix
  42          *     i > j
  43          *     This contains the factors between nodes i and j. These factors
  44          *     convert the time values of j to time values of i.
  45          *   Diagonal part of the matrix
  46          *     i = j
  47          *     This contains identity factors (a0= 0, a1= 1).
  48          *   Upper triangular part of the matrix
  49          *     i < j
  50          *     These factors are absent
  51          *
  52          * Factor types are used as follows:
  53          * EXACT,
  54          * Used for identity factors (a0= 0, a1= 1) that map a trace to itself. In
  55          * this case, min, max and accuracy are not initialized.
  56          *
  57          * ACCURATE,
  58          * The approximation is the middle of the min and max limits.
  59          *
  60          * APPROXIMATE,
  61          * min and max are not available because the hulls do not respect
  62          * assumptions (hulls should not intersect and the upper half-hull should
  63          * be below the lower half-hull). The approximation is a "best effort".
  64          * All fields are initialized but min and max are NULL.
  65          *
  66          * INCOMPLETE,
  67          * min or max is available but not both. The hulls respected assumptions
  68          * but all receives took place after all sends or vice versa.
  69          *
  70          * ABSENT,
  71          * The pair of trace did not have communications in both directions (maybe
  72          * even no communication at all). Also used for factors in the upper
  73          * triangular matrix.
  74          *
  75          * FAIL,
  76          * min and max are not available because the algorithms are defective. One
  77          * of min or max (but not both) is NULL. The other is initialized.
  78          */
  79         AllFactors* geoFactors;
  80
  81 #ifdef HAVE_LIBGLPK
  82         /* Synchronization factors, as calculated via LP, for comparison. Same
  83          * structure as geoFactors.
  84          *
  85          * Factor types are used as follows:
  86          * EXACT,
  87          * Used for identity factors (a0= 0, a1= 1) that map a trace to itself. In
  88          * this case, min, max and accuracy are not initialized.
  89          *
  90          * ACCURATE,
  91          * The approximation is the middle of the min and max limits.
  92          *
  93          * INCOMPLETE,
  94          * min or max is available but not both. The hulls respected assumptions
  95          * but all receives took place after all sends or vice versa.
  96          *
  97          * ABSENT,
  98          * The pair of trace did not have communications in both directions (maybe
  99          * even no communication at all). Also used when the hulls do not respect
 100          * assumptions. Also used for factors in the upper triangular matrix.
 101          */
 102         AllFactors* lpFactors;
 103 #endif
 104
 105         /* This is AnalysisStatsCHull.lpFactors if it is available or else
 106          * AnalysisStatsCHull.geoFactors.
 107          */
 108         AllFactors* allFactors;
 109 } AnalysisStatsCHull;
 110
 111
 112 typedef struct
 113 {
 114         /* This array contains file pointers to files where hull points x-y data
 115          * is outputed. Each trace-pair has two files, one for each message
 116          * direction. The structure of the array is the same as for hullArray,
 117          * hullPoints[row][col] where:
 118          *   row= inE->traceNum
 119          *   col= outE->traceNum
 120          *
 121          * The elements on the diagonal are not initialized.
 122          */
 123         FILE*** hullPoints;
 124
 125         /* This is AnalysisStatsCHull.lpFactors if it is available or else
 126          * AnalysisStatsCHull.geoFactors.
 127          */
 128         AllFactors* allFactors;
 129
 130 #ifdef HAVE_LIBGLPK
 131         /* This is the same array as AnalysisStatsCHull.lpFactors.
 132          */
 133         AllFactors* lpFactors;
 134 #endif
 135 } AnalysisGraphsDataCHull;
 136
 137
 138 typedef struct
 139 {
 140         /* Point* hullArray[traceNb][traceNb][]
 141          *
 142          * A message comes from two traces. The lowest numbered trace is
 143          * considered to be the reference clock, CA. The other is CB. The
 144          * direction of messages (sent or received) is relative to CA. Points are
 145          * formed such that their abscissa comes from CA and their ordinate from
 146          * CB.
 147          *
 148          * hullArray is divided into three parts depending on the position of an
 149          * element hullArray[i][j]:
 150          *   Lower triangular part of the matrix
 151          *     i > j
 152          *     This contains the points that form lower hulls, therefore that
 153          *     represent "sent" messages.
 154          *   Upper triangular part of the matrix
 155          *     i < j
 156          *     This contains the points that form upper hulls, therefore that
 157          *     represent "received" messages.
 158          *   Diagonal part of the matrix
 159          *     i = j
 160          *     This contains empty lists
 161          *
 162          * When a message is such that:
 163          *   inE->traceNum < outE->traceNum
 164          *     CA is inE->traceNum, therefore the message was received and may
 165          *     generate a point in the upper hull. Upper hulls are such that i <
 166          *     j, therefore, i= inE->traceNum and j= outE->traceNum.
 167          *   inE->traceNum > outE->traceNum
 168          *     CA is outE->traceNum, therefore the message was sent and may
 169          *     generate a point in the lower hull. Lower hulls are such that i >
 170          *     j, therefore, i= inE->traceNum and j= outE->traceNum. Hence, we
 171          *     always have:
 172          *       i= inE->traceNum
 173          *       j= outE->traceNum
 174          *
 175          * Do not let yourself get confused! Always remember that the "lower hull"
 176          * is in fact the "lower half" of a hull. When assumptions are respected,
 177          * the lower half is above the upper half.
 178          */
 179         GQueue*** hullArray;
 180
 181 #ifdef HAVE_LIBGLPK
 182         /* glp_prob* lps[traceNum][traceNum]
 183          *
 184          * Only the lower triangular part of the matrix is allocated, that is
 185          * lps[i][j] where i > j */
 186         glp_prob*** lps;
 187 #endif
 188
 189         AnalysisStatsCHull* stats;
 190         AnalysisGraphsDataCHull* graphsData;
 191 } AnalysisDataCHull;
 192
 193 void registerAnalysisCHull();
 194
 195 #endif