Commit | Line | Data |
---|---|---|
1d597550 | 1 | /* This file is part of the Linux Trace Toolkit viewer |
277e5b53 | 2 | * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca> |
1d597550 | 3 | * |
277e5b53 BP |
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. | |
1d597550 | 8 | * |
277e5b53 BP |
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. | |
1d597550 | 13 | * |
277e5b53 BP |
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/>. | |
1d597550 BP |
16 | */ |
17 | ||
0a87ec9a BP |
18 | #define _ISOC99_SOURCE |
19 | ||
1d597550 BP |
20 | #ifdef HAVE_CONFIG_H |
21 | #include <config.h> | |
22 | #endif | |
23 | ||
24 | #include <errno.h> | |
0a87ec9a BP |
25 | #include <math.h> |
26 | #include <stdlib.h> | |
2f076594 | 27 | #include <string.h> |
1d597550 BP |
28 | #include <unistd.h> |
29 | ||
30 | #include "sync_chain.h" | |
31 | ||
32 | ||
33 | GQueue processingModules= G_QUEUE_INIT; | |
34 | GQueue matchingModules= G_QUEUE_INIT; | |
35 | GQueue analysisModules= G_QUEUE_INIT; | |
36 | GQueue moduleOptions= G_QUEUE_INIT; | |
37 | ||
38 | ||
0a87ec9a BP |
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); | |
44 | ||
45 | ||
1ed11971 | 46 | /* |
9c7696b8 | 47 | * Call the statistics function of each module of a sync chain |
1ed11971 BP |
48 | * |
49 | * Args: | |
50 | * syncState: Container for synchronization data | |
51 | */ | |
52 | void printStats(SyncState* const syncState) | |
53 | { | |
54 | if (syncState->processingModule->printProcessingStats != NULL) | |
55 | { | |
56 | syncState->processingModule->printProcessingStats(syncState); | |
57 | } | |
58 | if (syncState->matchingModule->printMatchingStats != NULL) | |
59 | { | |
60 | syncState->matchingModule->printMatchingStats(syncState); | |
61 | } | |
62 | if (syncState->analysisModule->printAnalysisStats != NULL) | |
63 | { | |
64 | syncState->analysisModule->printAnalysisStats(syncState); | |
65 | } | |
66 | } | |
67 | ||
68 | ||
1d597550 BP |
69 | /* |
70 | * Calculate the elapsed time between two timeval values | |
71 | * | |
72 | * Args: | |
73 | * end: end time, result is also stored in this structure | |
74 | * start: start time | |
75 | */ | |
76 | void timeDiff(struct timeval* const end, const struct timeval* const start) | |
77 | { | |
78 | if (end->tv_usec >= start->tv_usec) | |
79 | { | |
80 | end->tv_sec-= start->tv_sec; | |
81 | end->tv_usec-= start->tv_usec; | |
82 | } | |
83 | else | |
84 | { | |
85 | end->tv_sec= end->tv_sec - start->tv_sec - 1; | |
86 | end->tv_usec= end->tv_usec - start->tv_usec + 1e6; | |
87 | } | |
88 | } | |
89 | ||
90 | ||
0a87ec9a BP |
91 | /* |
92 | * Calculate a resulting offset and drift for each trace. | |
93 | * | |
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. | |
101 | * | |
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. | |
111 | * | |
112 | * Nevertheless, the result is satisfactory. You just can't tell "how much" it | |
113 | * is. | |
114 | * | |
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 | |
120 | * | |
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 | |
128 | * | |
129 | * Args: | |
130 | * allFactors: offset and drift between each pair of traces | |
131 | * | |
132 | * Returns: | |
133 | * Factors[traceNb] synchronization factors for each trace | |
134 | */ | |
135 | GArray* reduceFactors(AllFactors* const allFactors) | |
136 | { | |
137 | GArray* factors; | |
138 | double** distances; | |
139 | unsigned int** predecessors; | |
140 | double* distanceSums; | |
141 | unsigned int* references; | |
142 | unsigned int i, j; | |
143 | const unsigned int traceNb= allFactors->traceNb; | |
144 | ||
145 | // Solve the all-pairs shortest path problem using the Floyd-Warshall | |
146 | // algorithm | |
147 | floydWarshall(allFactors, &distances, &predecessors); | |
148 | ||
149 | /* Find the reference for each node | |
150 | * | |
151 | * First calculate, for each node, the sum of the distances to each other | |
152 | * node it can reach. | |
153 | * | |
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 | |
156 | * of the island. | |
157 | */ | |
158 | distanceSums= malloc(traceNb * sizeof(double)); | |
159 | for (i= 0; i < traceNb; i++) | |
160 | { | |
161 | distanceSums[i]= 0.; | |
162 | for (j= 0; j < traceNb; j++) | |
163 | { | |
164 | distanceSums[i]+= distances[i][j]; | |
165 | } | |
166 | } | |
167 | ||
168 | references= malloc(traceNb * sizeof(unsigned int)); | |
169 | for (i= 0; i < traceNb; i++) | |
170 | { | |
171 | references[i]= UINT_MAX; | |
172 | } | |
173 | for (i= 0; i < traceNb; i++) | |
174 | { | |
175 | if (references[i] == UINT_MAX) | |
176 | { | |
177 | unsigned int reference; | |
178 | double distanceSumMin; | |
179 | ||
180 | // A node is its own reference by default | |
181 | reference= i; | |
182 | distanceSumMin= INFINITY; | |
183 | for (j= 0; j < traceNb; j++) | |
184 | { | |
185 | if (distances[i][j] != INFINITY && distanceSums[j] < | |
186 | distanceSumMin) | |
187 | { | |
188 | reference= j; | |
189 | distanceSumMin= distanceSums[j]; | |
190 | } | |
191 | } | |
192 | for (j= 0; j < traceNb; j++) | |
193 | { | |
194 | if (distances[i][j] != INFINITY) | |
195 | { | |
196 | references[j]= reference; | |
197 | } | |
198 | } | |
199 | } | |
200 | } | |
201 | ||
202 | for (i= 0; i < traceNb; i++) | |
203 | { | |
204 | free(distances[i]); | |
205 | } | |
206 | free(distances); | |
207 | free(distanceSums); | |
208 | ||
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. | |
212 | */ | |
213 | factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors), | |
214 | traceNb); | |
215 | g_array_set_size(factors, traceNb); | |
216 | for (i= 0; i < traceNb; i++) | |
217 | { | |
218 | getFactors(allFactors, predecessors, references, i, &g_array_index(factors, | |
219 | Factors, i)); | |
220 | } | |
221 | ||
222 | for (i= 0; i < traceNb; i++) | |
223 | { | |
224 | free(predecessors[i]); | |
225 | } | |
226 | free(predecessors); | |
227 | free(references); | |
228 | ||
229 | return factors; | |
230 | } | |
231 | ||
232 | ||
233 | /* | |
234 | * Perform an all-source shortest path search using the Floyd-Warshall | |
235 | * algorithm. | |
236 | * | |
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 | |
239 | * | |
240 | * Args: | |
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 | |
244 | * length is INFINITY | |
245 | * predecessors: resulting matrix of each node's predecessor on the shortest | |
246 | * path between two nodes | |
247 | */ | |
248 | static void floydWarshall(AllFactors* const allFactors, double*** const | |
249 | distances, unsigned int*** const predecessors) | |
250 | { | |
251 | unsigned int i, j, k; | |
252 | const unsigned int traceNb= allFactors->traceNb; | |
253 | PairFactors** const pairFactors= allFactors->pairFactors; | |
254 | ||
255 | // Setup initial conditions | |
256 | *distances= malloc(traceNb * sizeof(double*)); | |
257 | *predecessors= malloc(traceNb * sizeof(unsigned int*)); | |
258 | for (i= 0; i < traceNb; i++) | |
259 | { | |
260 | (*distances)[i]= malloc(traceNb * sizeof(double)); | |
261 | for (j= 0; j < traceNb; j++) | |
262 | { | |
263 | if (i == j) | |
264 | { | |
265 | g_assert(pairFactors[i][j].type == EXACT); | |
266 | ||
267 | (*distances)[i][j]= 0.; | |
268 | } | |
269 | else | |
270 | { | |
271 | if (pairFactors[i][j].type == ACCURATE || | |
272 | pairFactors[i][j].type == APPROXIMATE) | |
273 | { | |
274 | (*distances)[i][j]= pairFactors[i][j].accuracy; | |
275 | } | |
276 | else if (pairFactors[j][i].type == ACCURATE || | |
277 | pairFactors[j][i].type == APPROXIMATE) | |
278 | { | |
279 | (*distances)[i][j]= pairFactors[j][i].accuracy; | |
280 | } | |
281 | else | |
282 | { | |
283 | (*distances)[i][j]= INFINITY; | |
284 | } | |
285 | } | |
286 | } | |
287 | ||
288 | (*predecessors)[i]= malloc(traceNb * sizeof(unsigned int)); | |
289 | for (j= 0; j < traceNb; j++) | |
290 | { | |
291 | if (i != j) | |
292 | { | |
293 | (*predecessors)[i][j]= i; | |
294 | } | |
295 | else | |
296 | { | |
297 | (*predecessors)[i][j]= UINT_MAX; | |
298 | } | |
299 | } | |
300 | } | |
301 | ||
302 | // Run the iterations | |
303 | for (k= 0; k < traceNb; k++) | |
304 | { | |
305 | for (i= 0; i < traceNb; i++) | |
306 | { | |
307 | for (j= 0; j < traceNb; j++) | |
308 | { | |
309 | double distanceMin; | |
310 | ||
311 | distanceMin= MIN((*distances)[i][j], (*distances)[i][k] + | |
312 | (*distances)[k][j]); | |
313 | ||
314 | if (distanceMin != (*distances)[i][j]) | |
315 | { | |
316 | (*predecessors)[i][j]= (*predecessors)[k][j]; | |
317 | } | |
318 | ||
319 | (*distances)[i][j]= distanceMin; | |
320 | } | |
321 | } | |
322 | } | |
323 | } | |
324 | ||
325 | ||
326 | /* | |
327 | * Cummulate the time correction factors to convert a node's time to its | |
328 | * reference's time. | |
329 | * This function recursively calls itself until it reaches the reference node. | |
330 | * | |
331 | * Args: | |
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 | |
338 | */ | |
339 | static void getFactors(AllFactors* const allFactors, unsigned int** const | |
340 | predecessors, unsigned int* const references, const unsigned int traceNum, | |
341 | Factors* const factors) | |
342 | { | |
343 | unsigned int reference; | |
344 | PairFactors** const pairFactors= allFactors->pairFactors; | |
345 | ||
346 | reference= references[traceNum]; | |
347 | ||
348 | if (reference == traceNum) | |
349 | { | |
350 | factors->offset= 0.; | |
351 | factors->drift= 1.; | |
352 | } | |
353 | else | |
354 | { | |
355 | Factors previousVertexFactors; | |
356 | ||
357 | getFactors(allFactors, predecessors, references, | |
358 | predecessors[reference][traceNum], &previousVertexFactors); | |
359 | ||
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 */ | |
363 | ||
364 | if (pairFactors[reference][traceNum].approx != NULL) | |
365 | { | |
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; | |
371 | } | |
372 | else if (pairFactors[traceNum][reference].approx != NULL) | |
373 | { | |
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); | |
380 | } | |
381 | else | |
382 | { | |
383 | g_assert_not_reached(); | |
384 | } | |
385 | } | |
386 | } | |
387 | ||
388 | ||
1d597550 BP |
389 | /* |
390 | * A GCompareFunc for g_slist_find_custom() | |
391 | * | |
392 | * Args: | |
393 | * a: ProcessingModule*, element's data | |
394 | * b: char*, user data to compare against | |
395 | * | |
396 | * Returns: | |
397 | * 0 if the processing module a's name is b | |
398 | */ | |
399 | gint gcfCompareProcessing(gconstpointer a, gconstpointer b) | |
400 | { | |
401 | const ProcessingModule* processingModule; | |
402 | const char* name; | |
403 | ||
404 | processingModule= (const ProcessingModule*) a; | |
405 | name= (const char*) b; | |
406 | ||
407 | return strncmp(processingModule->name, name, | |
408 | strlen(processingModule->name) + 1); | |
409 | } | |
410 | ||
411 | ||
412 | /* | |
413 | * A GCompareFunc for g_slist_find_custom() | |
414 | * | |
415 | * Args: | |
416 | * a: MatchingModule*, element's data | |
417 | * b: char*, user data to compare against | |
418 | * | |
419 | * Returns: | |
420 | * 0 if the matching module a's name is b | |
421 | */ | |
422 | gint gcfCompareMatching(gconstpointer a, gconstpointer b) | |
423 | { | |
424 | const MatchingModule* matchingModule; | |
425 | const char* name; | |
426 | ||
427 | matchingModule= (const MatchingModule*) a; | |
428 | name= (const char*) b; | |
429 | ||
430 | return strncmp(matchingModule->name, name, strlen(matchingModule->name) + | |
431 | 1); | |
432 | } | |
433 | ||
434 | ||
435 | /* | |
436 | * A GCompareFunc for g_slist_find_custom() | |
437 | * | |
438 | * Args: | |
439 | * a: AnalysisModule*, element's data | |
440 | * b: char*, user data to compare against | |
441 | * | |
442 | * Returns: | |
443 | * 0 if the analysis module a's name is b | |
444 | */ | |
445 | gint gcfCompareAnalysis(gconstpointer a, gconstpointer b) | |
446 | { | |
447 | const AnalysisModule* analysisModule; | |
448 | const char* name; | |
449 | ||
450 | analysisModule= (const AnalysisModule*) a; | |
451 | name= (const char*) b; | |
452 | ||
453 | return strncmp(analysisModule->name, name, strlen(analysisModule->name) + | |
454 | 1); | |
455 | } | |
49c335f1 BP |
456 | |
457 | ||
458 | /* | |
459 | * A GFunc for g_queue_foreach() | |
460 | * | |
461 | * Concatenate analysis module names. | |
462 | * | |
463 | * Args: | |
464 | * data: AnalysisModule* | |
465 | * user_data: GString*, concatenated names | |
466 | */ | |
467 | void gfAppendAnalysisName(gpointer data, gpointer user_data) | |
468 | { | |
469 | g_string_append((GString*) user_data, ((AnalysisModule*) data)->name); | |
470 | g_string_append((GString*) user_data, ", "); | |
471 | } |