Benjamin Poirier
benjamin.poirier@polymtl.ca
-2009
+2009, 2010
+ About time synchronization
This framework performs offline time synchronization. This means that the
is mostly for performance evaluation
--sync-analysis - argument: chull, linreg, eval
specify the algorithm to use for event analysis. See the
- section "Alogrithms".
+ section "Synchronization Alogrithms".
+--sync-reduction - argument: accuracy
+ specify the algorithm to use for factor reduction. See
+ the section "Reduction Algorithms".
--sync-graphs
output gnuplot graph showing synchronization points
--sync-graphs-dir - argument: DIRECTORY
user time: 0.112007
system time: 0.000000
-++ Algorithms
+++ Synchronization Algorithms
The synchronization framework is extensible and already includes two
-algorithms: chull and linreg. You can choose which analysis algorithm to use
-with the --sync-analysis option.
+algorithms: chull and linreg. (There is also a special "eval" module
+available.) You can choose which analysis algorithm to use with the
+--sync-analysis option.
+++ Convex Hull
chull, the default analysis module, can provide a garantee that there are no
event_analysis_chull.h.
+++ Linear Regression
-linreg sometimes gives more accurate results than chull but it provides no
+linreg sometimes gives more precise results than chull but it provides no
garantee
+++ Synchronization evaluation
it calculates and prints different metrics about how well traces are
synchronized. Although it can be run like other analysis modules, it is most
useful when run in a postprocessing step, after another synchronization module
-has been run. Eval is most common run in text mode. To do this, run:
+has been run. Eval is most commonly run in text mode. To do this, run:
lttv -m sync_chain_batch [usual options, ex: -t traces/node1 -t traces/node2
--sync ...]
It can also be run from the lttv source tree via runlttv:
Many commands can be used to measure the RTT, for example:
ping -s 8 -A -c 8000 -w 10 192.168.112.57
-Note that this must be repeated in both directions in the file.
+Note that this must be repeated in both directions in the file, that is:
+192.168.112.49 192.168.112.50 0.057
+192.168.112.50 192.168.112.49 0.050
++++ Linear Programming and GLPK
The synchronization evaluation can optionally perform an analysis similar to
the graph output).
This is enabled by default at configure time (--with-glpk) if the GNU Linear
-Programming Kit is available (libglpk).
+Programming Kit is available (libglpk). On Debian-like systems (ex. Ubuntu),
+install the package "libglpk-dev".
+
+To see the output of this mode, run:
+lttv -m sync_chain_batch --eval-graphs [usual options, ex: -t traces/node1 -t
+traces/node2 --sync ...]
+
++ Reduction Algorithms
+Event analysis yields time correction factors between trace pairs. For groups
+of more than two traces, an extra step is necessary to identify a reference
+trace and calculate correction factors for each trace relative to this
+reference. There are usually many possibilities and so this step is called
+"factor reduction".
+
+++ Accuracy
+At the moment, only one algorithm is available to do this, the "accuracy"
+algorithm. This algorithm tries to choose the reference and the factors that
+yield the best accuracy. See the function header comments in
+factor_reduction_accuracy.c for more details.
+ Design
This part describes the design of the synchronization framework. This is to
synchronization, the executable linking to the event_*.o
eg. LTTV, unittest
-This reads parameters, creates SyncState and calls the processing init
-function. The "sync chain" is the set of event-* modules. At the moment there
-is only one module at each stage. However, as more module are added, it will
-become relevant to have many modules at the same stage simultaneously. This
-will require some modifications. It is already partly supported at the
+This reads parameters, creates SyncState and calls the init functions of the
+modules to be used. The "sync chain" is this set of modules. At the moment
+there is only one module at each stage. However, as more modules are added, it
+will become relevant to have many modules at the same stage simultaneously.
+This will require some modifications. It is already partly supported at the
matching stage through encapsulation of other matching modules.
sync_chain_unitest:main() provides a fairly simple example of sync chain
to deduce synchronization factors.
eg. convex hull, linear regression, broadcast Maximum Likelihood Estimator
+This module should return a set of synchronization factors for each trace
+pair. Some trace pairs may have no factors, their approxType should be set to
+ABSENT.
+
Instead of having one analyzeEvents() function that can receive any sort of
grouping of events, there are three prototypes: analyzeMessage(),
analyzeExchange() and analyzeBroadcast(). A module implements only the
3) we'll see which one of the two approaches works best and we can adapt
later.
-++ Data flow
-Data from traces flows "down" from processing to matching to analysis. Factors
-come back up.
+++ Stage 4: Factor reduction
+This stage reduces the pair-wise synchronization factors obtained in step 3 to
+time correction factors for each trace. It is most useful when synchronizing
+more than two traces.
++ Evolution and adaptation
-It is possible to change/add another sync chain and to add other event_*
-modules. It has been done. New types of events may need to be added to
-data_structures.h. This is only to link between Event-* modules. If the data
-does not have to be shared, data_structures.h does not have to be modified.
-
-At the moment there is some code duplication in the last steps of linreg and
-chull analysis: the code to propagate the factors when there are more than two
-nodes. Maybe there could be a Stage 4 that does that?
+It is possible to change/add another sync chain and to add other modules. It
+has been done. New types of events may need to be added to data_structures.h.
+This is only to link between Event-* modules. If the data does not have to be
+shared, data_structures.h does not have to be modified.
projects / lttv.git / blobdiff