sdf/analysis/mcm/mcmgraph.cc File Reference

#include "base/base.h"
#include "mcmgraph.h"
#include "../../base/hsdf/check.h"
Include dependency graph for sdf/analysis/mcm/mcmgraph.cc:

Functions

static void createInitialMCMgraph (TimedSDFgraph *g, MCMgraph *mcmGraph)
static void splitMCMedgeToSequence (MCMgraph *g, MCMedge *e)
static void addLongestDelayEdgeForNode (MCMgraph *g, MCMnode *n, MCMedge *e, int **visit)
static void addLongestDelayEdgesToMCMgraph (MCMgraph *g)
MCMgraphtransformHSDFtoMCMgraph (TimedSDFgraph *g, bool mcmFormulation)
static MCMnodes getAdjacentNodes (MCMnode *a, bool transpose)
static MCMnodegetNextNode (MCMnodes &nodes, v_int &order)
static void dfsVisit (MCMnode *u, int &time, v_int &color, v_int &d, v_int &f, MCMnode **pi, bool transpose)
void dfsMCMgraph (MCMgraph *g, v_int &d, v_int &f, MCMnode **pi, bool transpose)
static void addNodeToComponent (MCMnode *n, MCMgraph *comp)
static bool treeVisitChildren (MCMgraph *g, MCMnode **pi, MCMnode *u, MCMgraph *comp)
static void findComponentsInMCMgraph (MCMgraph *g, MCMnode **pi, MCMgraphs &components)
void stronglyConnectedMCMgraph (MCMgraph *g, MCMgraphs &components)
void relabelMCMgraph (MCMgraph *g)

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().

Here is the call graph for this function:

static void addNodeToComponent ( MCMnode n,
MCMgraph comp 
) [static]

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().

Here is the call graph for this function:

void dfsMCMgraph ( MCMgraph g,
v_int d,
v_int f,
MCMnode **  pi,
bool  transpose 
)

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().

Here is the call graph for this function:

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().

Here is the call graph for this function:

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().

Here is the call graph for this function:

static MCMnodes getAdjacentNodes ( MCMnode a,
bool  transpose 
) [static]

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().

static MCMnode* getNextNode ( MCMnodes nodes,
v_int order 
) [static]

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().

static void splitMCMedgeToSequence ( MCMgraph g,
MCMedge e 
) [static]

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().

void stronglyConnectedMCMgraph ( MCMgraph g,
MCMgraphs components 
)

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().

Here is the call graph for this function:

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().

Here is the call graph for this function:

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().

Here is the call graph for this function: