sdf/analysis/mcm/mcmgraph.cc File Reference
#include "base/base.h"
#include "mcmgraph.h"
#include "../../base/hsdf/check.h"
Function Documentation
static void addLongestDelayEdgeForNode | ( | MCMgraph * | g, | |
MCMnode * | n, | |||
MCMedge * | e, | |||
int ** | visit | |||
) | [static] |
addLongestDelayEdgeForNode () The function add an additional edge between the node n and any node reachable over e which only uses edges with no initial delays (except for the initial edge e). The weight of the new edge is the longest path from the node n to the destination node. The function uses an adapted version of Dijkstra's shirtest path algorithm.
References _MCMedge::d, _MCMedge::dst, MCMgraph::edges, _MCMedge::id, _MCMnode::id, _MCMnode::in, MCMgraph::nodes, _MCMnode::out, pi, _MCMedge::src, v, _MCMedge::visible, and _MCMedge::w.
Referenced by addLongestDelayEdgesToMCMgraph().
static void addLongestDelayEdgesToMCMgraph | ( | MCMgraph * | g | ) | [static] |
addLongestDelayEdgesToMCMgraph () The function adds additional edges to the graph which express the longest path between two nodes crossing one edge with a delay. Edges with no delay are removed and edges with more then one delay element are converted into a sequence of edges with one delay element.
References addLongestDelayEdgeForNode(), _MCMedge::d, MCMgraph::edges, MCMgraph::nodes, splitMCMedgeToSequence(), _MCMedge::src, and _MCMedge::visible.
Referenced by transformHSDFtoMCMgraph().
addNodeToComponent () The function adds a new copy of a node to the component and it also creates copies for all edges between this node and all nodes already in the component.
References _MCMedge::d, _MCMedge::dst, MCMgraph::edges, _MCMedge::id, _MCMnode::id, _MCMnode::in, MCMgraph::nodes, _MCMnode::out, _MCMedge::src, _MCMedge::visible, _MCMnode::visible, and _MCMedge::w.
Referenced by findComponentsInMCMgraph(), and treeVisitChildren().
static void createInitialMCMgraph | ( | TimedSDFgraph * | g, | |
MCMgraph * | mcmGraph | |||
) | [static] |
createInitialMCMgraph () The function converts an HSDF graph to a weighted directed graph by replacing each actor in the HSDF with a node in the graph and each channel with an edge. Each edge is assigned a weight equal to the execution time of the destination actor of the corresponding channel. The initial tokens are preserved during the conversion from channels to edges.
References a, SDFgraph::actorsBegin(), SDFgraph::actorsEnd(), ASSERT, c, SDFgraph::channelsBegin(), SDFgraph::channelsEnd(), _MCMedge::d, _MCMedge::dst, MCMgraph::edges, SDFchannel::getDstActor(), SDFcomponent::getId(), SDFchannel::getInitialTokens(), SDFchannel::getSrcActor(), _MCMedge::id, _MCMnode::id, _MCMnode::in, MCMgraph::nodes, _MCMnode::out, _MCMedge::src, _MCMedge::visible, _MCMnode::visible, and _MCMedge::w.
Referenced by transformHSDFtoMCMgraph().
dfsMCMgraph () The function performs a depth first search on the graph. The discover time (d), finish time (f) and predecessor tree (pi) are passed back. The graph is transposed if the argument 't' is 'true'. Vertices are considered in decreasing order of f[u].
The function derives an 'order' vector from the vector 'f'. Actors are considered in decreasing order according to this vector. When an actor is visited, its order is set to -1. At the end, all actors must have order -1 (i.e. all actors are visited).
References a, color, dfsVisit(), getNextNode(), MCMgraph::nodes, and MCMgraph::nrNodes().
Referenced by stronglyConnectedMCMgraph().
static void dfsVisit | ( | MCMnode * | u, | |
int & | time, | |||
v_int & | color, | |||
v_int & | d, | |||
v_int & | f, | |||
MCMnode ** | pi, | |||
bool | transpose | |||
) | [static] |
dfsVisit () The visitor function of the DFS algorithm.
References getAdjacentNodes(), _MCMnode::id, and v.
Referenced by dfsMCMgraph().
static void findComponentsInMCMgraph | ( | MCMgraph * | g, | |
MCMnode ** | pi, | |||
MCMgraphs & | components | |||
) | [static] |
findComponentsInMCMgraph () The function determines the strongly connected components in the graph. To do this, it performs depth-first walk on the forest given by 'pi'.
References addNodeToComponent(), _MCMedge::dst, MCMgraph::edges, _MCMnode::id, _MCMnode::in, MCMgraph::nodes, MCMgraph::nrEdges(), _MCMedge::src, treeVisitChildren(), _MCMedge::visible, and _MCMnode::visible.
Referenced by stronglyConnectedMCMgraph().
getAdjacentNodes () The function returns a list with nodes directly reachable from node a (in case transpose if false). If transpose is 'true', the graph is transposed and the function returns a list with nodes which are directly reachable from a in the transposed graph.
References _MCMedge::dst, _MCMnode::in, _MCMnode::out, _MCMedge::src, and _MCMedge::visible.
Referenced by dfsVisit().
getNextNode () The function returns the node from the list of nodes with the highest order. Its order is set to -1. If all nodes have order -1, a NULL pointer is returned.
References a, and _MCMnode::id.
Referenced by dfsMCMgraph().
void relabelMCMgraph | ( | MCMgraph * | g | ) |
relabelMCMgraph () The function removes all hidden nodes and edges from the graph. All visible edges are assigned a new id starting in the range [0,nrNodes()).
References MCMgraph::edges, _MCMedge::id, _MCMnode::id, _MCMnode::in, MCMgraph::nodes, _MCMnode::out, _MCMedge::visible, and _MCMnode::visible.
Referenced by mcmDasdanGupta(), mcmKarp(), and mcmYoungTarjanOrlin().
splitMCMedgeToSequence () The function converts an MCM edge with more then one delay into a sequence of edges with one delay (uses recursive call to itself).
References _MCMedge::d, _MCMedge::dst, MCMgraph::edges, _MCMedge::id, _MCMnode::id, _MCMnode::in, MCMgraph::nodes, _MCMnode::out, _MCMedge::src, _MCMedge::visible, _MCMnode::visible, and _MCMedge::w.
Referenced by addLongestDelayEdgesToMCMgraph().
Extract the strongly connected components from the graph. These components are returned as a set of MCM graphs. All nodes which belong to at least one of the strongly connected components are set to visible in the graph g, all other nodes are made invisible. Also edges between two nodes in (possibly different) strongly connected components are made visible and all others invisible. The graph g consists in the end of only nodes which are part of a strongly connnected component and all the edges between these nodes. Some MCM algorithms work also on this graph (which reduces the execution time needed in some of the conversion algorithms).
References ASSERT, dfsMCMgraph(), _MCMedge::dst, MCMgraph::edges, findComponentsInMCMgraph(), _MCMnode::id, MCMgraph::nrNodes(), pi, _MCMedge::src, _MCMedge::visible, and _MCMedge::w.
Referenced by mcmDasdanGupta(), mcmHoward(), mcmKarp(), and mcmYoungTarjanOrlin().
MCMgraph* transformHSDFtoMCMgraph | ( | TimedSDFgraph * | g, | |
bool | mcmFormulation | |||
) |
transformHSDFtoMCMgraph () The function converts an HSDF graph to a weighted directed graph used in the MCM algorithm of Karp (and its variants). By default, the a longest path calculation is performed to make the graph suitable as input for an MCM algorithm. Setting the flag 'mcmFormulation' to false result in an MCM graph which is suitable for an MCR (cycle ratio) formulation. This avoids running the longest path algo.
References addLongestDelayEdgesToMCMgraph(), createInitialMCMgraph(), _MCMedge::d, _MCMedge::dst, MCMgraph::edges, _MCMnode::id, isHSDFgraph(), _MCMedge::src, _MCMedge::visible, and _MCMedge::w.
Referenced by mcmDasdanGupta(), mcmHoward(), mcmKarp(), and mcmYoungTarjanOrlin().
static bool treeVisitChildren | ( | MCMgraph * | g, | |
MCMnode ** | pi, | |||
MCMnode * | u, | |||
MCMgraph * | comp | |||
) | [static] |
treeVisitChildren () The function visits all children of the actor 'u'. The parent-child relation is given via the vector 'pi'.
References addNodeToComponent(), ASSERT, _MCMnode::id, MCMgraph::nodes, v, and _MCMnode::visible.
Referenced by findComponentsInMCMgraph().