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/>.
17 #define _ISOC99_SOURCE
26 #include "sync_chain.h"
28 #include "factor_reduction_accuracy.h"
31 // Functions common to all reduction modules
32 static void initReductionAccuracy(SyncState
* const syncState
);
33 static void destroyReductionAccuracy(SyncState
* const syncState
);
35 static GArray
* finalizeReductionAccuracy(SyncState
* const syncState
,
36 AllFactors
* allFactors
);
37 static void printReductionStatsAccuracy(SyncState
* const syncState
);
39 // Functions specific to this module
40 static void floydWarshall(AllFactors
* const allFactors
, const unsigned int
41 traceNb
, double*** const distances
, unsigned int*** const predecessors
);
42 static void getFactors(AllFactors
* const allFactors
, unsigned int** const
43 predecessors
, unsigned int* const references
, const unsigned int traceNum
,
44 Factors
* const factors
);
47 static ReductionModule reductionModuleAccuracy
= {
49 .initReduction
= &initReductionAccuracy
,
50 .destroyReduction
= &destroyReductionAccuracy
,
51 .finalizeReduction
= &finalizeReductionAccuracy
,
52 .printReductionStats
= &printReductionStatsAccuracy
,
58 * Reduction module registering function
60 void registerReductionAccuracy()
62 g_queue_push_tail(&reductionModules
, &reductionModuleAccuracy
);
67 * Reduction init function
69 * This function is called at the beginning of a synchronization run for a set
72 * Allocate some reduction specific data structures
75 * syncState container for synchronization data.
77 static void initReductionAccuracy(SyncState
* const syncState
)
81 syncState
->reductionData
= calloc(1, sizeof(ReductionStatsAccuracy
));
87 * Reduction destroy function
89 * Free the reduction specific data structures
92 * syncState container for synchronization data.
94 static void destroyReductionAccuracy(SyncState
* const syncState
)
100 ReductionStatsAccuracy
* stats
= syncState
->reductionData
;
102 if (stats
->predecessors
)
104 for (i
= 0; i
< syncState
->traceNb
; i
++)
106 free(stats
->predecessors
[i
]);
108 free(stats
->predecessors
);
109 free(stats
->references
);
117 * Finalize the factor reduction
119 * Calculate a resulting offset and drift for each trace.
121 * Traces are assembled in groups. A group is an "island" of nodes/traces that
122 * exchanged messages. A reference is determined for each group by using a
123 * shortest path search based on the accuracy of the approximation. This also
124 * forms a tree of the best way to relate each node's clock to the reference's
125 * based on the accuracy. Sometimes it may be necessary or advantageous to
126 * propagate the factors through intermediary clocks. Resulting factors for
127 * each trace are determined based on this tree.
129 * This part was not the focus of my research. The algorithm used here is
130 * inexact in some ways:
131 * 1) The reference used may not actually be the best one to use. This is
132 * because the accuracy is not corrected based on the drift during the
133 * shortest path search.
134 * 2) The min and max factors are not propagated and are no longer valid.
135 * 3) Approximations of different types (ACCURATE and APPROXIMATE) are compared
136 * together. The "accuracy" parameters of these have different meanings and
137 * are not readily comparable.
139 * Nevertheless, the result is satisfactory. You just can't tell "how much" it
142 * Two alternative (and subtly different) ways of propagating factors to
143 * preserve min and max boundaries have been proposed, see:
144 * [Duda, A., Harrus, G., Haddad, Y., and Bernard, G.: Estimating global time
145 * in distributed systems, Proc. 7th Int. Conf. on Distributed Computing
146 * Systems, Berlin, volume 18, 1987] p.304
148 * [Jezequel, J.M., and Jard, C.: Building a global clock for observing
149 * computations in distributed memory parallel computers, Concurrency:
150 * Practice and Experience 8(1), volume 8, John Wiley & Sons, Ltd Chichester,
151 * 1996, 32] Section 5; which is mostly the same as
152 * [Jezequel, J.M.: Building a global time on parallel machines, Proceedings
153 * of the 3rd International Workshop on Distributed Algorithms, LNCS, volume
154 * 392, 136–147, 1989] Section 5
157 * syncState container for synchronization data.
158 * allFactors offset and drift between each pair of traces
161 * Factors[traceNb] synchronization factors for each trace
164 static GArray
* finalizeReductionAccuracy(SyncState
* const syncState
,
165 AllFactors
* allFactors
)
169 unsigned int** predecessors
;
170 double* distanceSums
;
171 unsigned int* references
;
174 // Solve the all-pairs shortest path problem using the Floyd-Warshall
176 floydWarshall(allFactors
, syncState
->traceNb
, &distances
, &predecessors
);
178 /* Find the reference for each node
180 * First calculate, for each node, the sum of the distances to each other
183 * Then, go through each "island" of traces to find the trace that has the
184 * lowest distance sum. Assign this trace as the reference to each trace
187 distanceSums
= malloc(syncState
->traceNb
* sizeof(double));
188 for (i
= 0; i
< syncState
->traceNb
; i
++)
191 for (j
= 0; j
< syncState
->traceNb
; j
++)
193 distanceSums
[i
]+= distances
[i
][j
];
197 references
= malloc(syncState
->traceNb
* sizeof(unsigned int));
198 for (i
= 0; i
< syncState
->traceNb
; i
++)
200 references
[i
]= UINT_MAX
;
202 for (i
= 0; i
< syncState
->traceNb
; i
++)
204 if (references
[i
] == UINT_MAX
)
206 unsigned int reference
;
207 double distanceSumMin
;
209 // A node is its own reference by default
211 distanceSumMin
= INFINITY
;
212 for (j
= 0; j
< syncState
->traceNb
; j
++)
214 if (distances
[i
][j
] != INFINITY
&& distanceSums
[j
] <
218 distanceSumMin
= distanceSums
[j
];
221 for (j
= 0; j
< syncState
->traceNb
; j
++)
223 if (distances
[i
][j
] != INFINITY
)
225 references
[j
]= reference
;
231 for (i
= 0; i
< syncState
->traceNb
; i
++)
238 /* For each trace, calculate the factors based on their corresponding
239 * tree. The tree is rooted at the reference and the shortest path to each
240 * other nodes are the branches.
242 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
244 g_array_set_size(factors
, syncState
->traceNb
);
245 for (i
= 0; i
< syncState
->traceNb
; i
++)
247 getFactors(allFactors
, predecessors
, references
, i
, &g_array_index(factors
,
251 if (syncState
->stats
)
253 ReductionStatsAccuracy
* stats
= syncState
->reductionData
;
255 stats
->predecessors
= predecessors
;
256 stats
->references
= references
;
260 for (i
= 0; i
< syncState
->traceNb
; i
++)
262 free(predecessors
[i
]);
273 * Print statistics related to reduction. Must be called after
277 * syncState container for synchronization data.
279 static void printReductionStatsAccuracy(SyncState
* const syncState
)
282 ReductionStatsAccuracy
* stats
= syncState
->reductionData
;
284 printf("Accuracy-based factor reduction stats:\n");
285 for (i
= 0; i
< syncState
->traceNb
; i
++)
287 unsigned int reference
= stats
->references
[i
];
291 printf("\ttrace %u is a reference\n", i
);
295 printf("\ttrace %u: reference %u, predecessor %u\n", i
,
297 stats
->predecessors
[reference
][i
]);
304 * Perform an all-source shortest path search using the Floyd-Warshall
307 * The algorithm is implemented accoding to the description here:
308 * http://web.mit.edu/urban_or_book/www/book/chapter6/6.2.2.html
311 * allFactors: offset and drift between each pair of traces
312 * traceNb: number of traces
313 * distances: resulting matrix of the length of the shortest path between
314 * two nodes. If there is no path between two nodes, the
315 * length is INFINITY. distances[i][j] is the length of the
317 * predecessors: resulting matrix of each node's predecessor on the shortest
318 * path between two nodes. predecessors[i][j] is the
319 * predecessor to j on the path from i to j.
321 static void floydWarshall(AllFactors
* const allFactors
, const unsigned int
322 traceNb
, double*** const distances
, unsigned int*** const predecessors
)
324 unsigned int i
, j
, k
;
325 PairFactors
** const pairFactors
= allFactors
->pairFactors
;
327 // Setup initial conditions
328 *distances
= malloc(traceNb
* sizeof(double*));
329 *predecessors
= malloc(traceNb
* sizeof(unsigned int*));
330 for (i
= 0; i
< traceNb
; i
++)
332 (*distances
)[i
]= malloc(traceNb
* sizeof(double));
333 for (j
= 0; j
< traceNb
; j
++)
337 g_assert(pairFactors
[i
][j
].type
== EXACT
);
339 (*distances
)[i
][j
]= 0.;
343 if (pairFactors
[i
][j
].type
== ACCURATE
||
344 pairFactors
[i
][j
].type
== APPROXIMATE
)
346 (*distances
)[i
][j
]= pairFactors
[i
][j
].accuracy
;
348 else if (pairFactors
[j
][i
].type
== ACCURATE
||
349 pairFactors
[j
][i
].type
== APPROXIMATE
)
351 (*distances
)[i
][j
]= pairFactors
[j
][i
].accuracy
;
355 (*distances
)[i
][j
]= INFINITY
;
360 (*predecessors
)[i
]= malloc(traceNb
* sizeof(unsigned int));
361 for (j
= 0; j
< traceNb
; j
++)
365 (*predecessors
)[i
][j
]= i
;
369 (*predecessors
)[i
][j
]= UINT_MAX
;
374 // Run the iterations
375 for (k
= 0; k
< traceNb
; k
++)
377 for (i
= 0; i
< traceNb
; i
++)
379 for (j
= 0; j
< traceNb
; j
++)
383 distanceMin
= MIN((*distances
)[i
][j
], (*distances
)[i
][k
] +
386 if (distanceMin
!= (*distances
)[i
][j
])
388 (*predecessors
)[i
][j
]= (*predecessors
)[k
][j
];
391 (*distances
)[i
][j
]= distanceMin
;
399 * Cummulate the time correction factors to convert a node's time to its
401 * This function recursively calls itself until it reaches the reference node.
404 * allFactors: offset and drift between each pair of traces
405 * predecessors: matrix of each node's predecessor on the shortest
406 * path between two nodes
407 * references: reference node for each node
408 * traceNum: node for which to find the factors
409 * factors: resulting factors
411 static void getFactors(AllFactors
* const allFactors
, unsigned int** const
412 predecessors
, unsigned int* const references
, const unsigned int traceNum
,
413 Factors
* const factors
)
415 unsigned int reference
;
416 PairFactors
** const pairFactors
= allFactors
->pairFactors
;
418 reference
= references
[traceNum
];
420 if (reference
== traceNum
)
427 Factors previousVertexFactors
;
429 getFactors(allFactors
, predecessors
, references
,
430 predecessors
[reference
][traceNum
], &previousVertexFactors
);
432 /* Convert the time from traceNum to reference;
433 * pairFactors[row][col] converts the time from col to row, invert the
434 * factors as necessary */
436 if (pairFactors
[reference
][traceNum
].approx
!= NULL
)
438 factors
->offset
= previousVertexFactors
.drift
*
439 pairFactors
[reference
][traceNum
].approx
->offset
+
440 previousVertexFactors
.offset
;
441 factors
->drift
= previousVertexFactors
.drift
*
442 pairFactors
[reference
][traceNum
].approx
->drift
;
444 else if (pairFactors
[traceNum
][reference
].approx
!= NULL
)
446 factors
->offset
= previousVertexFactors
.drift
* (-1. *
447 pairFactors
[traceNum
][reference
].approx
->offset
/
448 pairFactors
[traceNum
][reference
].approx
->drift
) +
449 previousVertexFactors
.offset
;
450 factors
->drift
= previousVertexFactors
.drift
* (1. /
451 pairFactors
[traceNum
][reference
].approx
->drift
);
455 g_assert_not_reached();