From mboxrd@z Thu Jan 1 00:00:00 1970 From: masoume.jabbarifar@polymtl.ca (Masoume Jabbarifar) Date: Wed, 15 Sep 2010 12:36:58 -0400 Subject: [ltt-dev] [PATCH] Add time reduction option to synchronisation Message-ID: <1284568618-23814-1-git-send-email-masoume.jabbarifar@polymtl.ca> --- lttv/lttv/Makefile.am | 2 + lttv/lttv/sync/Makefile.am | 4 +- lttv/lttv/sync/data_structures.c | 2 - lttv/lttv/sync/event_matching_tcp.c | 87 +++++- lttv/lttv/sync/event_matching_tcp.h | 1 + lttv/lttv/sync/event_processing_text.c | 4 + lttv/lttv/sync/factor_reduction.h | 6 + lttv/lttv/sync/factor_reduction_time.c | 514 ++++++++++++++++++++++++++++++++ lttv/lttv/sync/factor_reduction_time.h | 53 ++++ lttv/lttv/sync/sync_chain_lttv.c | 6 + lttv/lttv/sync/sync_chain_unittest.c | 2 + 11 files changed, 664 insertions(+), 17 deletions(-) create mode 100644 lttv/lttv/sync/factor_reduction_time.c create mode 100644 lttv/lttv/sync/factor_reduction_time.h diff --git a/lttv/lttv/Makefile.am b/lttv/lttv/Makefile.am index 30ead55..750f2d2 100644 --- a/lttv/lttv/Makefile.am +++ b/lttv/lttv/Makefile.am @@ -87,6 +87,8 @@ lttv_real_SOURCES = \ sync/factor_reduction.h\ sync/factor_reduction_accuracy.c\ sync/factor_reduction_accuracy.h\ + sync/factor_reduction_time.c\ + sync/factor_reduction_time.h\ sync/lookup3.h lttvinclude_HEADERS = \ diff --git a/lttv/lttv/sync/Makefile.am b/lttv/lttv/sync/Makefile.am index e1d6775..7a5417d 100644 --- a/lttv/lttv/sync/Makefile.am +++ b/lttv/lttv/sync/Makefile.am @@ -30,4 +30,6 @@ unittest_SOURCES = \ event_analysis_linreg.h\ factor_reduction.h\ factor_reduction_accuracy.c\ - factor_reduction_accuracy.h + factor_reduction_accuracy.h\ + factor_reduction_time.c\ + factor_reduction_time.h diff --git a/lttv/lttv/sync/data_structures.c b/lttv/lttv/sync/data_structures.c index acac9d7..c5fe736 100644 --- a/lttv/lttv/sync/data_structures.c +++ b/lttv/lttv/sync/data_structures.c @@ -271,8 +271,6 @@ void destroyTCPSegment(Message* const segment) { TCPEvent* inE, *outE; - segment->print(segment); - g_assert(segment->inE != NULL && segment->outE != NULL); g_assert(segment->inE->type == TCP && segment->outE->type == TCP); inE= segment->inE->event.tcpEvent; diff --git a/lttv/lttv/sync/event_matching_tcp.c b/lttv/lttv/sync/event_matching_tcp.c index 90d6c43..678a334 100644 --- a/lttv/lttv/sync/event_matching_tcp.c +++ b/lttv/lttv/sync/event_matching_tcp.c @@ -56,7 +56,8 @@ static void buildReversedConnectionKey(ConnectionKey* const static void openGraphDataFiles(SyncState* const syncState); static void closeGraphDataFiles(SyncState* const syncState); static void writeMessagePoint(FILE* stream, const Message* const message); - +static void gfPacketDestroy(gpointer data, gpointer userData); +static void gfExchangeDestroy(gpointer data, gpointer userData); static MatchingModule matchingModuleTCP = { .name= "TCP", @@ -101,6 +102,7 @@ void registerMatchingTCP() static void initMatchingTCP(SyncState* const syncState) { MatchingDataTCP* matchingData; + int i, j; matchingData= malloc(sizeof(MatchingDataTCP)); syncState->matchingData= matchingData; @@ -113,8 +115,7 @@ static void initMatchingTCP(SyncState* const syncState) &gefConnectionKeyEqual, &gdnConnectionKeyDestroy, &gdnTCPSegmentListDestroy); - if (syncState->stats) - { + if (syncState->reductionModule->preProcessReduction != NULL || syncState->stats) { unsigned int i; matchingData->stats= calloc(1, sizeof(MatchingStatsTCP)); @@ -139,6 +140,20 @@ static void initMatchingTCP(SyncState* const syncState) { matchingData->messagePoints= NULL; } + if (syncState->reductionModule->preProcessReduction != NULL) { + matchingData->packetArray= malloc(syncState->traceNb * sizeof(GQueue**)); + for (i= 0; i < syncState->traceNb; i++) { + matchingData->packetArray[i]= malloc(syncState->traceNb * sizeof(GQueue*)); + + for (j= 0; j < syncState->traceNb; j++) { + matchingData->packetArray[i][j]= g_queue_new(); + } + } + } + else + { + matchingData->packetArray= NULL; + } } @@ -155,6 +170,7 @@ static void initMatchingTCP(SyncState* const syncState) static void destroyMatchingTCP(SyncState* const syncState) { MatchingDataTCP* matchingData; + int i, j; matchingData= (MatchingDataTCP*) syncState->matchingData; @@ -165,8 +181,7 @@ static void destroyMatchingTCP(SyncState* const syncState) partialDestroyMatchingTCP(syncState); - if (syncState->stats) - { + if (syncState->reductionModule->preProcessReduction != NULL || syncState->stats) { unsigned int i; for (i= 0; i < syncState->traceNb; i++) @@ -179,6 +194,17 @@ static void destroyMatchingTCP(SyncState* const syncState) free(syncState->matchingData); syncState->matchingData= NULL; + if (syncState->reductionModule->preProcessReduction != NULL) { + for (i= 0; i < syncState->traceNb; i++) { + for (j= 0; j < syncState->traceNb; j++) + if (syncState->analysisModule->analyzeMessage != NULL) + g_queue_foreach(matchingData->packetArray[i][j], gfPacketDestroy, NULL); + else + g_queue_foreach(matchingData->packetArray[i][j], gfExchangeDestroy, NULL); + free(matchingData->packetArray[i]); + } + free(matchingData->packetArray); + } } @@ -335,6 +361,7 @@ static void matchEvents(SyncState* const syncState, Event* const event, Message* packet; MatchingDataTCP* matchingData; GQueue* conUnAcked; + GQueue* packetMatching; matchingData= (MatchingDataTCP*) syncState->matchingData; @@ -354,10 +381,11 @@ static void matchEvents(SyncState* const syncState, Event* const event, packet->outE->event.tcpEvent->segmentKey= packet->inE->event.tcpEvent->segmentKey; if (syncState->stats) - { matchingData->stats->totPacket++; + + if (syncState->reductionModule->preProcessReduction != NULL || syncState->stats) matchingData->stats->totMessageArray[packet->inE->traceNum][packet->outE->traceNum]++; - } + // Discard loopback traffic if (packet->inE->traceNum == packet->outE->traceNum) @@ -371,17 +399,24 @@ static void matchEvents(SyncState* const syncState, Event* const event, writeMessagePoint(matchingData->messagePoints[packet->inE->traceNum][packet->outE->traceNum], packet); } - - if (syncState->analysisModule->analyzeMessage != NULL) - { - syncState->analysisModule->analyzeMessage(syncState, packet); + if (syncState->analysisModule->analyzeMessage != NULL) { + if (syncState->reductionModule->preProcessReduction == NULL) + syncState->analysisModule->analyzeMessage(syncState, packet); + else { + packetMatching= + matchingData->packetArray[packet->inE->traceNum][packet->outE->traceNum]; + g_queue_push_tail(packetMatching, packet); + } + } // We can skip the rest of the algorithm if the analysis module is not // interested in exchanges if (syncState->analysisModule->analyzeExchange == NULL) { - destroyTCPSegment(packet); + if (syncState->reductionModule->preProcessReduction == NULL) + destroyTCPSegment(packet); + return; } @@ -452,8 +487,14 @@ static void matchEvents(SyncState* const syncState, Event* const event, matchingData->stats->totExchangeSync++; } - syncState->analysisModule->analyzeExchange(syncState, - exchange); + if (syncState->reductionModule->preProcessReduction == NULL) + syncState->analysisModule->analyzeExchange(syncState, exchange); + else + { + packetMatching= + matchingData->packetArray[packet->inE->traceNum][packet->outE->traceNum]; + g_queue_push_tail(packetMatching, exchange); + } } exchange->message= NULL; @@ -707,3 +748,21 @@ static void writeMatchingGraphsPlotsTCPMessages(SyncState* const syncState, "title \"Received messages\" with points linetype 4 " "linecolor rgb \"#6699cc\" pointtype 11 pointsize 2, \\\n", i, j); } +static void gfPacketDestroy(gpointer data, gpointer userData) +{ + Message* packet; + + packet= (Message*) data; + destroyTCPSegment(packet); + +} + +static void gfExchangeDestroy(gpointer data, gpointer userData) +{ + Exchange* exchange; + + exchange= (Exchange*) data; + exchange->message= NULL; + destroyTCPExchange(exchange); + +} diff --git a/lttv/lttv/sync/event_matching_tcp.h b/lttv/lttv/sync/event_matching_tcp.h index 6f9b072..e7d1d12 100644 --- a/lttv/lttv/sync/event_matching_tcp.h +++ b/lttv/lttv/sync/event_matching_tcp.h @@ -57,6 +57,7 @@ typedef struct * The elements on the diagonal are not initialized. */ FILE*** messagePoints; + GQueue*** packetArray; } MatchingDataTCP; void registerMatchingTCP(); diff --git a/lttv/lttv/sync/event_processing_text.c b/lttv/lttv/sync/event_processing_text.c index bcbea9b..894f71c 100644 --- a/lttv/lttv/sync/event_processing_text.c +++ b/lttv/lttv/sync/event_processing_text.c @@ -273,6 +273,10 @@ static AllFactors* finalizeProcessingText(SyncState* const syncState) free(line); } + if (syncState->reductionModule->preProcessReduction != NULL) { + syncState->reductionModule->preProcessReduction(syncState); + } + factors= syncState->matchingModule->finalizeMatching(syncState); if (syncState->stats) { diff --git a/lttv/lttv/sync/factor_reduction.h b/lttv/lttv/sync/factor_reduction.h index 561df6b..e971ea6 100644 --- a/lttv/lttv/sync/factor_reduction.h +++ b/lttv/lttv/sync/factor_reduction.h @@ -39,6 +39,12 @@ typedef struct */ void (*destroyReduction)(struct _SyncState* const syncState); + /* This function is called when time reduction is needed and + * removes useless communication links and finds Spanning Tree + * of nodes in the network and then sends packets to synchronization + */ + void (*preProcessReduction)(struct _SyncState* const syncState); + /* * Convert trace pair synchronization factors to a resulting offset and * drift for each trace. diff --git a/lttv/lttv/sync/factor_reduction_time.c b/lttv/lttv/sync/factor_reduction_time.c new file mode 100644 index 0000000..2bd37bf --- /dev/null +++ b/lttv/lttv/sync/factor_reduction_time.c @@ -0,0 +1,514 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2010 Masoume Jabbarifar + * + * 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 . + */ +#define _ISOC99_SOURCE + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include +#include +#include +#include + + +#include "event_analysis.h" +#include "event_matching.h" +#include "sync_chain.h" + +#include "factor_reduction_time.h" +#include "event_matching_tcp.h" + + +/* Functions common to all reduction modules */ +static void initReductionTime(SyncState* const syncState); +static void destroyReductionTime(SyncState* const syncState); +static void preProcessReductionTime(SyncState* const syncState); + +static GArray* finalizeReductionTime(SyncState* const syncState, + AllFactors* allFactors); +static void printReductionStatsTime(SyncState* const syncState); + +/* Functions specific to this module */ +static void getFactors(SyncState* const syncState,AllFactors* const allFactors, + const unsigned int traceNum, + Factors* const factors); +static void maximumSpanningTree(SyncState* const syncState); +static void maximumCommunicationPacket(SyncState* const syncState); +static void floodingSyncExecute(SyncState* const syncState); +void updateDistances(int target,ReductionData* reductionData,SyncState* const syncState); +void sumCommunicationPackets(SyncState* const syncState); +void proposeRefNode(int** connectionArray, int* refNodes, int n); +void SyncExecute(int refNode,SyncState* const syncState); +int findParent(SyncState* const syncState, int root, int node); + + +static ReductionModule reductionModuleTime= { + .name= "time", + .initReduction= &initReductionTime, + .destroyReduction= &destroyReductionTime, + .preProcessReduction= &preProcessReductionTime, + .finalizeReduction= &finalizeReductionTime, + .printReductionStats= &printReductionStatsTime, + .graphFunctions= {}, +}; + + +/* + * Reduction module registering function + */ +void registerReductionTime() +{ + g_queue_push_tail(&reductionModules, &reductionModuleTime); +} + + +/* + * 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 initReductionTime(SyncState* const syncState) +{ + int i; + + ReductionData* reductionData; + + reductionData= malloc(sizeof(ReductionData)); + syncState->reductionData= reductionData; + + + reductionData->routed= malloc(syncState->traceNb * sizeof(char*)); + + reductionData->distance= malloc(syncState->traceNb * sizeof(int*)); + + reductionData->neighbour= malloc(syncState->traceNb * sizeof(int*)); + + reductionData->totMessageArray= malloc(syncState->traceNb * sizeof(unsigned int*)); + + for (i= 0; i < syncState->traceNb; i++) { + reductionData->totMessageArray[i]= + calloc(syncState->traceNb, sizeof(unsigned int)); + } + + reductionData->totMSTMessageArray= malloc(syncState->traceNb * sizeof(unsigned int*)); + + for (i= 0; i < syncState->traceNb; i++) { + reductionData->totMSTMessageArray[i]= + calloc(syncState->traceNb, sizeof(unsigned int)); + } + + reductionData->totMSTAnalysisArray= malloc(syncState->traceNb * sizeof(unsigned int*)); + + for (i= 0; i < syncState->traceNb; i++) { + reductionData->totMSTAnalysisArray[i]= + calloc(syncState->traceNb, sizeof(unsigned int)); + } + + reductionData->maxRoot= malloc(syncState->traceNb * sizeof(int*)); + reductionData->maxRootMST= malloc(syncState->traceNb * sizeof(int*)); +} + +static void preProcessReductionTime(SyncState* const syncState) +{ + + sumCommunicationPackets(syncState); + maximumCommunicationPacket(syncState); + maximumSpanningTree(syncState); + floodingSyncExecute(syncState); +} +/* Finding best path in the network that has more interaction among the + * nodes and synchronisation trough this path + * + * Maximum Spanning Tree function based on Prim's Algorithm + * + * The algorithm is implemented according to the code here: + * http://snippets.dzone.com/posts/show/4743 + * +*/ +static void maximumSpanningTree(SyncState* const syncState) +{ + int i, j; + int total= 0; + int treeSize, max; + ReductionData* reductionData; + + reductionData= syncState->reductionData; + + /* Initialise distance with 0 */ + for (i= 0; i < syncState->traceNb ; ++i) + reductionData->distance[i]= 0; + + /* Mark all nodes as NOT beeing in the maximum spanning tree */ + for (i= 0; i < syncState->traceNb; ++i) + reductionData->routed[i]= 0; + + /* Add the first node to the tree */ + if (reductionData->referenceNode < 0) return; + g_debug("Adding node %d\n", reductionData->referenceNode); + reductionData->routed[reductionData->referenceNode]= 1; + updateDistances(reductionData->referenceNode, reductionData, syncState); + + for (treeSize= 1; treeSize < syncState->traceNb; ++treeSize) { + /* Find the node with the bigest distance to the tree */ + max= -1; + for (i= 0; i < syncState->traceNb; ++i) + if (!reductionData->routed[i]) + if ((max == -1) || (reductionData->distance[max] < reductionData->distance[i])) + max= i; + + /* And add it */ + reductionData->totMSTMessageArray[max][reductionData->neighbour[max]]= reductionData->distance[max]; + reductionData->totMSTMessageArray[reductionData->neighbour[max]][max]= reductionData->distance[max]; + + reductionData->totMSTAnalysisArray[max][reductionData->neighbour[max]]= reductionData->distance[max]; + reductionData->totMSTAnalysisArray[reductionData->neighbour[max]][max]= reductionData->distance[max]; + + g_debug("Adding edge %i-MAX(%i)-D(%i)\n", reductionData->neighbour[max], max, reductionData->distance[max]); + reductionData->routed[max]= 1; + total+= reductionData->distance[max]; + + updateDistances(max, reductionData, syncState); + } + + + for ( i=0 ; i < syncState->traceNb ; i++) { + for (j= 0 ; j < syncState->traceNb ; j++) + g_debug("\t%d ", reductionData->totMSTMessageArray[i][j]); + g_debug("\n"); + } + g_debug("Total distance: %d\n", total); + +} + + +void updateDistances(int target, ReductionData* reductionData, SyncState* const syncState) { + + int i; + g_debug("Update[%i]= ", target); + for (i= 0; i < syncState->traceNb; ++i) { + if ((reductionData->totMessageArray[target][i] != 0) && (reductionData->distance[i] <= reductionData->totMessageArray[target][i])) { + if (reductionData->distance[i] != reductionData->totMessageArray[target][i]) { + reductionData->distance[i]= reductionData->totMessageArray[target][i]; + reductionData->neighbour[i]= target; + } + else if (reductionData->distance[i] == reductionData->totMessageArray[target][i] && target == reductionData->referenceNode) { + reductionData->distance[i]= reductionData->totMessageArray[target][i]; + reductionData->neighbour[i]= target; + } + } + g_debug("%iD(%i)N(%i)", i, reductionData->distance[i], reductionData->neighbour[i]); + } + g_debug("\n------------------------------------------------------------\n"); +} + + +static void maximumCommunicationPacket(SyncState* const syncState) +{ + + ReductionData* reductionData; + + reductionData= syncState->reductionData; + proposeRefNode(reductionData->totMessageArray, reductionData->maxRoot, syncState->traceNb); + reductionData->referenceNode= reductionData->maxRoot[0]; + g_debug("Best RefNODE is : %i\n", reductionData->referenceNode); + +} + +/* Symmetrical matrix of packet communications */ + +void sumCommunicationPackets(SyncState* const syncState) { + int i, j, sum; + + MatchingDataTCP* matchingData; + + matchingData= syncState->matchingData; + + ReductionData* reductionData; + + reductionData= syncState->reductionData; + + + for (i= 0; i < syncState->traceNb; ++i) + for (j= 0; j < syncState->traceNb; ++j){ + sum= matchingData->stats->totMessageArray[i][j] + matchingData->stats->totMessageArray[j][i]; + reductionData->totMessageArray[i][j]= sum; + reductionData->totMessageArray[j][i]= sum; + } + +} + +/* Finding the node who has more interaction */ + +void proposeRefNode(int** connectionArray, int* refNodes, int n){ + + int* sumPacket; + int i, j, index=0; + int maxSumPacket=0; + + sumPacket= malloc(n* sizeof(int)); + + for (i= 0; i < n; ++i) { + sumPacket[i]= 0; + for (j= 0;j < n; ++j) + sumPacket[i]+= connectionArray[i][j]; + g_debug("sum(%i)=%i\n", i, sumPacket[i]); + if (sumPacket[i] > maxSumPacket) + maxSumPacket= sumPacket[i]; + } + g_debug("proposed Reference Node: "); + for (i= 0 ; i < n ; ++i) { + if (sumPacket[i] == maxSumPacket) { + refNodes[index++]= i; + g_debug("%i \t", i); + } + } + refNodes[index]= -1; + g_debug("\n"); + free(sumPacket); +} + +void floodingSyncExecute(SyncState* const syncState) { + + ReductionData* reductionData; + reductionData= syncState->reductionData; + SyncExecute(reductionData->referenceNode, syncState); + +} + + +/* First root and all of nodes who has connection with it (it's childs) + * must be synchronised then function will be run for the childs recursively + */ + +void SyncExecute(int refNode, SyncState* const syncState) { + + unsigned int i, j; + GQueue* packetSync; + Message* packet; + Exchange* exchange; + + ReductionData* reductionData; + + reductionData= syncState->reductionData; + + MatchingDataTCP* matchingData; + + matchingData= syncState->matchingData; + + for (i= 0 ; i < syncState->traceNb ; ++i) + if (reductionData->totMSTMessageArray[refNode][i] != 0){ + packetSync= matchingData->packetArray[refNode][i]; + + for (j= 0 ; j < packetSync->length ; ++j){ + if (syncState->analysisModule->analyzeMessage != NULL) { + packet= g_queue_peek_nth(packetSync, j); + syncState->analysisModule->analyzeMessage(syncState, packet); + } + else { + exchange= g_queue_peek_nth(packetSync, j); + syncState->analysisModule->analyzeExchange(syncState, exchange); + } + } + + packetSync= matchingData->packetArray[i][refNode]; + + for (j= 0 ;j < packetSync->length ; ++j){ + if (syncState->analysisModule->analyzeMessage != NULL) { + packet= g_queue_peek_nth(packetSync, j); + syncState->analysisModule->analyzeMessage(syncState, packet); + } + else { + exchange= g_queue_peek_nth(packetSync, j); + syncState->analysisModule->analyzeExchange(syncState, exchange); + } + } + + reductionData->totMSTMessageArray[i][refNode]= 0; + reductionData->totMSTMessageArray[refNode][i]= 0; + SyncExecute(i, syncState); + } + return; +} +/* + * Reduction destroy function + * + * Free the analysis specific data structures + * + * Args: + * syncState container for synchronization data. + */ +static void destroyReductionTime(SyncState* const syncState) +{ + int i; + ReductionData* reductionData; + reductionData= (ReductionData*) syncState->reductionData; + + if (reductionData == NULL) return; + + for (i= 0; i < syncState->traceNb; i++) { + free(reductionData->totMessageArray[i]); + free(reductionData->totMSTMessageArray[i]); + free(reductionData->totMSTAnalysisArray[i]); + } + free(reductionData->totMessageArray); + free(reductionData->totMSTMessageArray); + free(reductionData->totMSTAnalysisArray); + free(reductionData->routed); + free(reductionData->distance); + free(reductionData->neighbour); + free(reductionData->maxRoot); + free(reductionData->maxRootMST); + free(syncState->reductionData); + syncState->reductionData= NULL; +} + + +/* + * Finalize the factor reduction + * + * Calculate a resulting offset and drift for each trace. + * + * 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* finalizeReductionTime(SyncState* const syncState, + AllFactors* allFactors) +{ + int i, j; + GArray* factors; + + 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(syncState, allFactors, i, &g_array_index(factors, + Factors, i)); + } + + return factors; +} + + +/* + * Print statistics related to reduction. Must be called after + * finalizeReduction. + * + * Args: + * syncState container for synchronization data. + */ +static void printReductionStatsTime(SyncState* const syncState) +{ +} + +/* + * 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(SyncState* const syncState, AllFactors* const allFactors, const unsigned int traceNum, + Factors* const factors) +{ + unsigned int reference; + PairFactors** const pairFactors= allFactors->pairFactors; + int parent, i; + + ReductionData* reductionData; + reductionData= syncState->reductionData; + + if (traceNum == reductionData->referenceNode) + reference= traceNum; + else if (reductionData->totMSTAnalysisArray[reductionData->referenceNode][traceNum] != 0) + reference= reductionData->referenceNode; + else + reference= findParent(syncState, -1, traceNum); + + if (reference == traceNum) { + factors->offset= 0.; + factors->drift= 1.; + } + else { + Factors previousVertexFactors; + + getFactors(syncState, allFactors, reference, &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(); + } + } +} + +int findParent(SyncState* const syncState, int root, int node) +{ + + int i; + int result; + ReductionData* reductionData; + + reductionData= syncState->reductionData; + for (i= 0; i < syncState->traceNb; i++) + if (reductionData->totMSTAnalysisArray[node][i] != 0 && i == reductionData->referenceNode) + return 1; + + for (i= 0; i < syncState->traceNb; i++) + if (reductionData->totMSTAnalysisArray[node][i] != 0) + if (i != root) { + result= findParent(syncState, node, i); + if (result == 1 && root == -1) return i; + if (result == 1) return 1; + } + return 0; +} diff --git a/lttv/lttv/sync/factor_reduction_time.h b/lttv/lttv/sync/factor_reduction_time.h new file mode 100644 index 0000000..c46cbd1 --- /dev/null +++ b/lttv/lttv/sync/factor_reduction_time.h @@ -0,0 +1,53 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2010 Masoume Jabbarifar + * + * 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 . + */ + +#ifndef FACTOR_REDUCTION_TIME_H +#define FACTOR_REDUCTION_TIME_H + +#include + +#include "data_structures.h" + + +typedef struct { + + char* routed; /* routed[i] is 1 when we have concidered the node i in the maximum + spanning tree; otherwise it is 0 */ + + int* distance; /* distance[i] is the distance between node i and the maximum + spanning tree; this is initially 0; if i is + already in the tree, then d[i] is undefined; + this is just a temporary variable. It's not necessary but speeds + up execution considerably (by a factor of n) */ + + int* neighbour; /* neighbour[i] holds the index of the node i would have to be + linked to in order to get a distance of d[i] */ + + int referenceNode; /*referenceNode is one of networks node whose time will be + considered as reference time*/ + + unsigned int** totMessageArray; + unsigned int** totMSTMessageArray; /*Maximum spanning tree is saved in totMSTMessageArray*/ + unsigned int** totMSTAnalysisArray; + int* maxRoot; + int* maxRootMST; + +} ReductionData; + +void registerReductionTime(); + +#endif diff --git a/lttv/lttv/sync/sync_chain_lttv.c b/lttv/lttv/sync/sync_chain_lttv.c index 95bef44..c60e8ac 100644 --- a/lttv/lttv/sync/sync_chain_lttv.c +++ b/lttv/lttv/sync/sync_chain_lttv.c @@ -45,6 +45,7 @@ #include "event_analysis_linreg.h" #include "event_analysis_eval.h" #include "factor_reduction_accuracy.h" +#include "factor_reduction_time.h" #include "sync_chain.h" #include "sync_chain_lttv.h" @@ -139,6 +140,7 @@ static void init() registerAnalysisEval(); registerReductionAccuracy(); + registerReductionTime(); // Build module names lists for option and help string for (i= 0; i < ARRAY_SIZE(loopValues); i++) @@ -313,6 +315,10 @@ bool syncTraceset(LttvTracesetContext* const traceSetContext) lttv_process_traceset_middle(traceSetContext, ltt_time_infinite, G_MAXULONG, NULL); lttv_process_traceset_seek_time(traceSetContext, ltt_time_zero); + + // Find the best refrence node and remove the useless sunchronization + if (syncState->reductionModule->preProcessReduction != NULL) + syncState->reductionModule->preProcessReduction(syncState); // Obtain, reduce, adjust and set correction factors allFactors= syncState->processingModule->finalizeProcessing(syncState); diff --git a/lttv/lttv/sync/sync_chain_unittest.c b/lttv/lttv/sync/sync_chain_unittest.c index 40302a0..e76fa78 100644 --- a/lttv/lttv/sync/sync_chain_unittest.c +++ b/lttv/lttv/sync/sync_chain_unittest.c @@ -42,6 +42,7 @@ #include "event_analysis_linreg.h" #include "event_analysis_eval.h" #include "factor_reduction_accuracy.h" +#include "factor_reduction_time.h" #include "sync_chain.h" @@ -134,6 +135,7 @@ int main(const int argc, char* const argv[]) registerAnalysisEval(); registerReductionAccuracy(); + registerReductionTime(); // Initialize data structures syncState= malloc(sizeof(SyncState)); -- 1.6.0.4