1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
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.
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.
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/>.
18 #define _ISOC99_SOURCE
30 #include "sync_chain.h"
33 GQueue processingModules
= G_QUEUE_INIT
;
34 GQueue matchingModules
= G_QUEUE_INIT
;
35 GQueue analysisModules
= G_QUEUE_INIT
;
36 GQueue moduleOptions
= G_QUEUE_INIT
;
39 static void floydWarshall(AllFactors
* const allFactors
, double*** const
40 distances
, unsigned int*** const predecessors
);
41 static void getFactors(AllFactors
* const allFactors
, unsigned int** const
42 predecessors
, unsigned int* const references
, const unsigned int traceNum
,
43 Factors
* const factors
);
47 * Call the statistics function of each module of a sync chain
50 * syncState: Container for synchronization data
52 void printStats(SyncState
* const syncState
)
54 if (syncState
->processingModule
->printProcessingStats
!= NULL
)
56 syncState
->processingModule
->printProcessingStats(syncState
);
58 if (syncState
->matchingModule
->printMatchingStats
!= NULL
)
60 syncState
->matchingModule
->printMatchingStats(syncState
);
62 if (syncState
->analysisModule
->printAnalysisStats
!= NULL
)
64 syncState
->analysisModule
->printAnalysisStats(syncState
);
70 * Calculate the elapsed time between two timeval values
73 * end: end time, result is also stored in this structure
76 void timeDiff(struct timeval
* const end
, const struct timeval
* const start
)
78 if (end
->tv_usec
>= start
->tv_usec
)
80 end
->tv_sec
-= start
->tv_sec
;
81 end
->tv_usec
-= start
->tv_usec
;
85 end
->tv_sec
= end
->tv_sec
- start
->tv_sec
- 1;
86 end
->tv_usec
= end
->tv_usec
- start
->tv_usec
+ 1e6
;
92 * Calculate a resulting offset and drift for each trace.
94 * Traces are assembled in groups. A group is an "island" of nodes/traces that
95 * exchanged messages. A reference is determined for each group by using a
96 * shortest path search based on the accuracy of the approximation. This also
97 * forms a tree of the best way to relate each node's clock to the reference's
98 * based on the accuracy. Sometimes it may be necessary or advantageous to
99 * propagate the factors through intermediary clocks. Resulting factors for
100 * each trace are determined based on this tree.
102 * This part was not the focus of my research. The algorithm used here is
103 * inexact in some ways:
104 * 1) The reference used may not actually be the best one to use. This is
105 * because the accuracy is not corrected based on the drift during the
106 * shortest path search.
107 * 2) The min and max factors are not propagated and are no longer valid.
108 * 3) Approximations of different types (ACCURATE and APPROXIMATE) are compared
109 * together. The "accuracy" parameters of these have different meanings and
110 * are not readily comparable.
112 * Nevertheless, the result is satisfactory. You just can't tell "how much" it
115 * Two alternative (and subtly different) ways of propagating factors to
116 * preserve min and max boundaries have been proposed, see:
117 * [Duda, A., Harrus, G., Haddad, Y., and Bernard, G.: Estimating global time
118 * in distributed systems, Proc. 7th Int. Conf. on Distributed Computing
119 * Systems, Berlin, volume 18, 1987] p.304
121 * [Jezequel, J.M., and Jard, C.: Building a global clock for observing
122 * computations in distributed memory parallel computers, Concurrency:
123 * Practice and Experience 8(1), volume 8, John Wiley & Sons, Ltd Chichester,
124 * 1996, 32] Section 5; which is mostly the same as
125 * [Jezequel, J.M.: Building a global time on parallel machines, Proceedings
126 * of the 3rd International Workshop on Distributed Algorithms, LNCS, volume
127 * 392, 136–147, 1989] Section 5
130 * allFactors: offset and drift between each pair of traces
133 * Factors[traceNb] synchronization factors for each trace
135 GArray
* reduceFactors(AllFactors
* const allFactors
)
139 unsigned int** predecessors
;
140 double* distanceSums
;
141 unsigned int* references
;
143 const unsigned int traceNb
= allFactors
->traceNb
;
145 // Solve the all-pairs shortest path problem using the Floyd-Warshall
147 floydWarshall(allFactors
, &distances
, &predecessors
);
149 /* Find the reference for each node
151 * First calculate, for each node, the sum of the distances to each other
154 * Then, go through each "island" of traces to find the trace that has the
155 * lowest distance sum. Assign this trace as the reference to each trace
158 distanceSums
= malloc(traceNb
* sizeof(double));
159 for (i
= 0; i
< traceNb
; i
++)
162 for (j
= 0; j
< traceNb
; j
++)
164 distanceSums
[i
]+= distances
[i
][j
];
168 references
= malloc(traceNb
* sizeof(unsigned int));
169 for (i
= 0; i
< traceNb
; i
++)
171 references
[i
]= UINT_MAX
;
173 for (i
= 0; i
< traceNb
; i
++)
175 if (references
[i
] == UINT_MAX
)
177 unsigned int reference
;
178 double distanceSumMin
;
180 // A node is its own reference by default
182 distanceSumMin
= INFINITY
;
183 for (j
= 0; j
< traceNb
; j
++)
185 if (distances
[i
][j
] != INFINITY
&& distanceSums
[j
] <
189 distanceSumMin
= distanceSums
[j
];
192 for (j
= 0; j
< traceNb
; j
++)
194 if (distances
[i
][j
] != INFINITY
)
196 references
[j
]= reference
;
202 for (i
= 0; i
< traceNb
; i
++)
209 /* For each trace, calculate the factors based on their corresponding
210 * tree. The tree is rooted at the reference and the shortest path to each
211 * other nodes are the branches.
213 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
215 g_array_set_size(factors
, traceNb
);
216 for (i
= 0; i
< traceNb
; i
++)
218 getFactors(allFactors
, predecessors
, references
, i
, &g_array_index(factors
,
222 for (i
= 0; i
< traceNb
; i
++)
224 free(predecessors
[i
]);
234 * Perform an all-source shortest path search using the Floyd-Warshall
237 * The algorithm is implemented accoding to the description here:
238 * http://web.mit.edu/urban_or_book/www/book/chapter6/6.2.2.html
241 * allFactors: offset and drift between each pair of traces
242 * distances: resulting matrix of the length of the shortest path between
243 * two nodes. If there is no path between two nodes, the
245 * predecessors: resulting matrix of each node's predecessor on the shortest
246 * path between two nodes
248 static void floydWarshall(AllFactors
* const allFactors
, double*** const
249 distances
, unsigned int*** const predecessors
)
251 unsigned int i
, j
, k
;
252 const unsigned int traceNb
= allFactors
->traceNb
;
253 PairFactors
** const pairFactors
= allFactors
->pairFactors
;
255 // Setup initial conditions
256 *distances
= malloc(traceNb
* sizeof(double*));
257 *predecessors
= malloc(traceNb
* sizeof(unsigned int*));
258 for (i
= 0; i
< traceNb
; i
++)
260 (*distances
)[i
]= malloc(traceNb
* sizeof(double));
261 for (j
= 0; j
< traceNb
; j
++)
265 g_assert(pairFactors
[i
][j
].type
== EXACT
);
267 (*distances
)[i
][j
]= 0.;
271 if (pairFactors
[i
][j
].type
== ACCURATE
||
272 pairFactors
[i
][j
].type
== APPROXIMATE
)
274 (*distances
)[i
][j
]= pairFactors
[i
][j
].accuracy
;
276 else if (pairFactors
[j
][i
].type
== ACCURATE
||
277 pairFactors
[j
][i
].type
== APPROXIMATE
)
279 (*distances
)[i
][j
]= pairFactors
[j
][i
].accuracy
;
283 (*distances
)[i
][j
]= INFINITY
;
288 (*predecessors
)[i
]= malloc(traceNb
* sizeof(unsigned int));
289 for (j
= 0; j
< traceNb
; j
++)
293 (*predecessors
)[i
][j
]= i
;
297 (*predecessors
)[i
][j
]= UINT_MAX
;
302 // Run the iterations
303 for (k
= 0; k
< traceNb
; k
++)
305 for (i
= 0; i
< traceNb
; i
++)
307 for (j
= 0; j
< traceNb
; j
++)
311 distanceMin
= MIN((*distances
)[i
][j
], (*distances
)[i
][k
] +
314 if (distanceMin
!= (*distances
)[i
][j
])
316 (*predecessors
)[i
][j
]= (*predecessors
)[k
][j
];
319 (*distances
)[i
][j
]= distanceMin
;
327 * Cummulate the time correction factors to convert a node's time to its
329 * This function recursively calls itself until it reaches the reference node.
332 * allFactors: offset and drift between each pair of traces
333 * predecessors: matrix of each node's predecessor on the shortest
334 * path between two nodes
335 * references: reference node for each node
336 * traceNum: node for which to find the factors
337 * factors: resulting factors
339 static void getFactors(AllFactors
* const allFactors
, unsigned int** const
340 predecessors
, unsigned int* const references
, const unsigned int traceNum
,
341 Factors
* const factors
)
343 unsigned int reference
;
344 PairFactors
** const pairFactors
= allFactors
->pairFactors
;
346 reference
= references
[traceNum
];
348 if (reference
== traceNum
)
355 Factors previousVertexFactors
;
357 getFactors(allFactors
, predecessors
, references
,
358 predecessors
[reference
][traceNum
], &previousVertexFactors
);
360 /* Convert the time from traceNum to reference;
361 * pairFactors[row][col] converts the time from col to row, invert the
362 * factors as necessary */
364 if (pairFactors
[reference
][traceNum
].approx
!= NULL
)
366 factors
->offset
= previousVertexFactors
.drift
*
367 pairFactors
[reference
][traceNum
].approx
->offset
+
368 previousVertexFactors
.offset
;
369 factors
->drift
= previousVertexFactors
.drift
*
370 pairFactors
[reference
][traceNum
].approx
->drift
;
372 else if (pairFactors
[traceNum
][reference
].approx
!= NULL
)
374 factors
->offset
= previousVertexFactors
.drift
* (-1. *
375 pairFactors
[traceNum
][reference
].approx
->offset
/
376 pairFactors
[traceNum
][reference
].approx
->drift
) +
377 previousVertexFactors
.offset
;
378 factors
->drift
= previousVertexFactors
.drift
* (1. /
379 pairFactors
[traceNum
][reference
].approx
->drift
);
383 g_assert_not_reached();
390 * A GCompareFunc for g_slist_find_custom()
393 * a: ProcessingModule*, element's data
394 * b: char*, user data to compare against
397 * 0 if the processing module a's name is b
399 gint
gcfCompareProcessing(gconstpointer a
, gconstpointer b
)
401 const ProcessingModule
* processingModule
;
404 processingModule
= (const ProcessingModule
*) a
;
405 name
= (const char*) b
;
407 return strncmp(processingModule
->name
, name
,
408 strlen(processingModule
->name
) + 1);
413 * A GCompareFunc for g_slist_find_custom()
416 * a: MatchingModule*, element's data
417 * b: char*, user data to compare against
420 * 0 if the matching module a's name is b
422 gint
gcfCompareMatching(gconstpointer a
, gconstpointer b
)
424 const MatchingModule
* matchingModule
;
427 matchingModule
= (const MatchingModule
*) a
;
428 name
= (const char*) b
;
430 return strncmp(matchingModule
->name
, name
, strlen(matchingModule
->name
) +
436 * A GCompareFunc for g_slist_find_custom()
439 * a: AnalysisModule*, element's data
440 * b: char*, user data to compare against
443 * 0 if the analysis module a's name is b
445 gint
gcfCompareAnalysis(gconstpointer a
, gconstpointer b
)
447 const AnalysisModule
* analysisModule
;
450 analysisModule
= (const AnalysisModule
*) a
;
451 name
= (const char*) b
;
453 return strncmp(analysisModule
->name
, name
, strlen(analysisModule
->name
) +
459 * A GFunc for g_queue_foreach()
461 * Concatenate analysis module names.
464 * data: AnalysisModule*
465 * user_data: GString*, concatenated names
467 void gfAppendAnalysisName(gpointer data
, gpointer user_data
)
469 g_string_append((GString
*) user_data
, ((AnalysisModule
*) data
)->name
);
470 g_string_append((GString
*) user_data
, ", ");