Perform factor reduction as a modular step

[lttv.git] / lttv / lttv / sync / factor_reduction_accuracy.c

/* This file is part of the Linux Trace Toolkit viewer
 * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
 *
 * This program is free software: you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 2.1 of the License, or (at
 * your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
#define _ISOC99_SOURCE

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <math.h>
#include <stdlib.h>

#include "sync_chain.h"

#include "factor_reduction_accuracy.h"


// Functions common to all reduction modules
static void initReductionAccuracy(SyncState* const syncState);
static void destroyReductionAccuracy(SyncState* const syncState);

static GArray* finalizeReductionAccuracy(SyncState* const syncState,
        AllFactors* allFactors);
static void printReductionStatsAccuracy(SyncState* const syncState);

// Functions specific to this module
static void floydWarshall(AllFactors* const allFactors, const unsigned int
        traceNb, double*** const distances, unsigned int*** const predecessors);
static void getFactors(AllFactors* const allFactors, unsigned int** const
        predecessors, unsigned int* const references, const unsigned int traceNum,
        Factors* const factors);


static ReductionModule reductionModuleAccuracy= {
        .name= "accuracy",
        .initReduction= &initReductionAccuracy,
        .destroyReduction= &destroyReductionAccuracy,
        .finalizeReduction= &finalizeReductionAccuracy,
        .printReductionStats= &printReductionStatsAccuracy,
        .graphFunctions= {},
};


/*
 * Reduction module registering function
 */
void registerReductionAccuracy()
{
        g_queue_push_tail(&reductionModules, &reductionModuleAccuracy);
}


/*
 * Reduction init function
 *
 * This function is called at the beginning of a synchronization run for a set
 * of traces.
 *
 * Allocate some reduction specific data structures
 *
 * Args:
 *   syncState     container for synchronization data.
 */
static void initReductionAccuracy(SyncState* const syncState)
{
        if (syncState->stats)
        {
                syncState->reductionData= calloc(1, sizeof(ReductionStatsAccuracy));
        }
}


/*
 * Reduction destroy function
 *
 * Free the analysis specific data structures
 *
 * Args:
 *   syncState     container for synchronization data.
 */
static void destroyReductionAccuracy(SyncState* const syncState)
{
        unsigned int i;

        if (syncState->stats)
        {
                ReductionStatsAccuracy* stats= syncState->reductionData;

                if (stats->predecessors)
                {
                        for (i= 0; i < syncState->traceNb; i++)
                        {
                                free(stats->predecessors[i]);
                        }
                        free(stats->predecessors);
                        free(stats->references);
                }
                free(stats);
        }
}


/*
 * Finalize the factor reduction
 *
 * Calculate a resulting offset and drift for each trace.
 *
 * Traces are assembled in groups. A group is an "island" of nodes/traces that
 * exchanged messages. A reference is determined for each group by using a
 * shortest path search based on the accuracy of the approximation. This also
 * forms a tree of the best way to relate each node's clock to the reference's
 * based on the accuracy. Sometimes it may be necessary or advantageous to
 * propagate the factors through intermediary clocks. Resulting factors for
 * each trace are determined based on this tree.
 *
 * This part was not the focus of my research. The algorithm used here is
 * inexact in some ways:
 * 1) The reference used may not actually be the best one to use. This is
 *    because the accuracy is not corrected based on the drift during the
 *    shortest path search.
 * 2) The min and max factors are not propagated and are no longer valid.
 * 3) Approximations of different types (ACCURATE and APPROXIMATE) are compared
 *    together. The "accuracy" parameters of these have different meanings and
 *    are not readily comparable.
 *
 * Nevertheless, the result is satisfactory. You just can't tell "how much" it
 * is.
 *
 * Two alternative (and subtly different) ways of propagating factors to
 * preserve min and max boundaries have been proposed, see:
 * [Duda, A., Harrus, G., Haddad, Y., and Bernard, G.: Estimating global time
 * in distributed systems, Proc. 7th Int. Conf. on Distributed Computing
 * Systems, Berlin, volume 18, 1987] p.304
 *
 * [Jezequel, J.M., and Jard, C.: Building a global clock for observing
 * computations in distributed memory parallel computers, Concurrency:
 * Practice and Experience 8(1), volume 8, John Wiley & Sons, Ltd Chichester,
 * 1996, 32] Section 5; which is mostly the same as
 * [Jezequel, J.M.: Building a global time on parallel machines, Proceedings
 * of the 3rd International Workshop on Distributed Algorithms, LNCS, volume
 * 392, 136–147, 1989] Section 5
 *
 * Args:
 *   syncState     container for synchronization data.
 *   allFactors    offset and drift between each pair of traces
 *
 * Returns:
 *   Factors[traceNb] synchronization factors for each trace

 */
static GArray* finalizeReductionAccuracy(SyncState* const syncState,
        AllFactors* allFactors)
{
        GArray* factors;
        double** distances;
        unsigned int** predecessors;
        double* distanceSums;
        unsigned int* references;
        unsigned int i, j;

        // Solve the all-pairs shortest path problem using the Floyd-Warshall
        // algorithm
        floydWarshall(allFactors, syncState->traceNb, &distances, &predecessors);

        /* Find the reference for each node
         *
         * First calculate, for each node, the sum of the distances to each other
         * node it can reach.
         *
         * Then, go through each "island" of traces to find the trace that has the
         * lowest distance sum. Assign this trace as the reference to each trace
         * of the island.
         */
        distanceSums= malloc(syncState->traceNb * sizeof(double));
        for (i= 0; i < syncState->traceNb; i++)
        {
                distanceSums[i]= 0.;
                for (j= 0; j < syncState->traceNb; j++)
                {
                        distanceSums[i]+= distances[i][j];
                }
        }

        references= malloc(syncState->traceNb * sizeof(unsigned int));
        for (i= 0; i < syncState->traceNb; i++)
        {
                references[i]= UINT_MAX;
        }
        for (i= 0; i < syncState->traceNb; i++)
        {
                if (references[i] == UINT_MAX)
                {
                        unsigned int reference;
                        double distanceSumMin;

                        // A node is its own reference by default
                        reference= i;
                        distanceSumMin= INFINITY;
                        for (j= 0; j < syncState->traceNb; j++)
                        {
                                if (distances[i][j] != INFINITY && distanceSums[j] <
                                        distanceSumMin)
                                {
                                        reference= j;
                                        distanceSumMin= distanceSums[j];
                                }
                        }
                        for (j= 0; j < syncState->traceNb; j++)
                        {
                                if (distances[i][j] != INFINITY)
                                {
                                        references[j]= reference;
                                }
                        }
                }
        }

        for (i= 0; i < syncState->traceNb; i++)
        {
                free(distances[i]);
        }
        free(distances);
        free(distanceSums);

        /* For each trace, calculate the factors based on their corresponding
         * tree. The tree is rooted at the reference and the shortest path to each
         * other nodes are the branches.
         */
        factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors),
                syncState->traceNb);
        g_array_set_size(factors, syncState->traceNb);
        for (i= 0; i < syncState->traceNb; i++)
        {
                getFactors(allFactors, predecessors, references, i, &g_array_index(factors,
                                Factors, i));
        }

        if (syncState->stats)
        {
                ReductionStatsAccuracy* stats= syncState->reductionData;

                stats->predecessors= predecessors;
                stats->references= references;
        }
        else
        {
                for (i= 0; i < syncState->traceNb; i++)
                {
                        free(predecessors[i]);
                }
                free(predecessors);
                free(references);
        }

        return factors;
}


/*
 * Print statistics related to reduction. Must be called after
 * finalizeReduction.
 *
 * Args:
 *   syncState     container for synchronization data.
 */
static void printReductionStatsAccuracy(SyncState* const syncState)
{
        unsigned int i;
        ReductionStatsAccuracy* stats= syncState->reductionData;

        printf("Accuracy-based factor reduction stats:\n");
        for (i= 0; i < syncState->traceNb; i++)
        {
                unsigned int reference= stats->references[i];

                if (i == reference)
                {
                        printf("\ttrace %u is a reference\n", i);
                }
                else
                {
                        printf("\ttrace %u: reference %u, predecessor %u\n", i,
                                reference,
                                stats->predecessors[reference][i]);
                }
        }
}


/*
 * Perform an all-source shortest path search using the Floyd-Warshall
 * algorithm.
 *
 * The algorithm is implemented accoding to the description here:
 * http://web.mit.edu/urban_or_book/www/book/chapter6/6.2.2.html
 *
 * Args:
 *   allFactors:   offset and drift between each pair of traces
 *   traceNb:      number of traces
 *   distances:    resulting matrix of the length of the shortest path between
 *                 two nodes. If there is no path between two nodes, the
 *                 length is INFINITY. distances[i][j] is the length of the
 *                 path from i to j.
 *   predecessors: resulting matrix of each node's predecessor on the shortest
 *                 path between two nodes. predecessors[i][j] is the
 *                 predecessor to j on the path from i to j.
 */
static void floydWarshall(AllFactors* const allFactors, const unsigned int
        traceNb, double*** const distances, unsigned int*** const predecessors)
{
        unsigned int i, j, k;
        PairFactors** const pairFactors= allFactors->pairFactors;

        // Setup initial conditions
        *distances= malloc(traceNb * sizeof(double*));
        *predecessors= malloc(traceNb * sizeof(unsigned int*));
        for (i= 0; i < traceNb; i++)
        {
                (*distances)[i]= malloc(traceNb * sizeof(double));
                for (j= 0; j < traceNb; j++)
                {
                        if (i == j)
                        {
                                g_assert(pairFactors[i][j].type == EXACT);

                                (*distances)[i][j]= 0.;
                        }
                        else
                        {
                                if (pairFactors[i][j].type == ACCURATE ||
                                        pairFactors[i][j].type == APPROXIMATE)
                                {
                                        (*distances)[i][j]= pairFactors[i][j].accuracy;
                                }
                                else if (pairFactors[j][i].type == ACCURATE ||
                                        pairFactors[j][i].type == APPROXIMATE)
                                {
                                        (*distances)[i][j]= pairFactors[j][i].accuracy;
                                }
                                else
                                {
                                        (*distances)[i][j]= INFINITY;
                                }
                        }
                }

                (*predecessors)[i]= malloc(traceNb * sizeof(unsigned int));
                for (j= 0; j < traceNb; j++)
                {
                        if (i != j)
                        {
                                (*predecessors)[i][j]= i;
                        }
                        else
                        {
                                (*predecessors)[i][j]= UINT_MAX;
                        }
                }
        }

        // Run the iterations
        for (k= 0; k < traceNb; k++)
        {
                for (i= 0; i < traceNb; i++)
                {
                        for (j= 0; j < traceNb; j++)
                        {
                                double distanceMin;

                                distanceMin= MIN((*distances)[i][j], (*distances)[i][k] +
                                        (*distances)[k][j]);

                                if (distanceMin != (*distances)[i][j])
                                {
                                        (*predecessors)[i][j]= (*predecessors)[k][j];
                                }

                                (*distances)[i][j]= distanceMin;
                        }
                }
        }
}


/*
 * Cummulate the time correction factors to convert a node's time to its
 * reference's time.
 * This function recursively calls itself until it reaches the reference node.
 *
 * Args:
 *   allFactors:   offset and drift between each pair of traces
 *   predecessors: matrix of each node's predecessor on the shortest
 *                 path between two nodes
 *   references:   reference node for each node
 *   traceNum:     node for which to find the factors
 *   factors:      resulting factors
 */
static void getFactors(AllFactors* const allFactors, unsigned int** const
        predecessors, unsigned int* const references, const unsigned int traceNum,
        Factors* const factors)
{
        unsigned int reference;
        PairFactors** const pairFactors= allFactors->pairFactors;

        reference= references[traceNum];

        if (reference == traceNum)
        {
                factors->offset= 0.;
                factors->drift= 1.;
        }
        else
        {
                Factors previousVertexFactors;

                getFactors(allFactors, predecessors, references,
                        predecessors[reference][traceNum], &previousVertexFactors);

                /* Convert the time from traceNum to reference;
                 * pairFactors[row][col] converts the time from col to row, invert the
                 * factors as necessary */

                if (pairFactors[reference][traceNum].approx != NULL)
                {
                        factors->offset= previousVertexFactors.drift *
                                pairFactors[reference][traceNum].approx->offset +
                                previousVertexFactors.offset;
                        factors->drift= previousVertexFactors.drift *
                                pairFactors[reference][traceNum].approx->drift;
                }
                else if (pairFactors[traceNum][reference].approx != NULL)
                {
                        factors->offset= previousVertexFactors.drift * (-1. *
                                pairFactors[traceNum][reference].approx->offset /
                                pairFactors[traceNum][reference].approx->drift) +
                                previousVertexFactors.offset;
                        factors->drift= previousVertexFactors.drift * (1. /
                                pairFactors[traceNum][reference].approx->drift);
                }
                else
                {
                        g_assert_not_reached();
                }
        }
}