#include <math.h>
#include <iostream>
#include <assert.h>
#include <time.h>
#include <sys/resource.h>
#include "dependency_graph.h"
#include "../../base/algo/repetition_vector.h"
#include "../../base/algo/components.h"

Include dependency graph for dependency_graph.cc:

Classes
struct	_State
struct	_HashSlot
Defines
#define	TDTIME_MAX INT_MAX
#define	INVALID_HASH_KEY NULL
#define	NO_SLOT_IN_HASH -1
#define	GLB_CLK sdfState.glb_clk
#define	ACT_CLK(a, t) sdfState.act_clk[a][t]
#define	CH(c) sdfState.ch[c]
#define	FIRE_ACT(a, t) ACT_CLK(a,t)++;
#define	FIRE_ACT_END(a) ACT_CLK(a,0)--;
#define	CH_TOKENS(c, n) (CH(c) >= n)
#define	CONSUME(c, n) CH(c) = CH(c) - n;
#define	PRODUCE(c, n) CH(c) = CH(c) + n;
#define	ACT_END_FIRE(a) (ACT_CLK(a,0) != 0)
#define	ADVANCE_CLK GLB_CLK = GLB_CLK + 1;
#define	NEXT_ITER GLB_CLK = 0;
#define	LOWER_CLK(a)
#define	CH_TOKENS_PREV(c, n) (prevStateP.ch[c] >= n)
Typedefs
typedef unsigned short	TCnt
typedef unsigned long	TBufSize
typedef double	TDtime
typedef struct _State	State
typedef int	StackPos
typedef unsigned int	HashKey
typedef struct _HashSlot	HashSlot
Functions
static SDFactor *	findOutputActor (TimedSDFgraph *g, RepetitionVector repVec)
static SDFtime	getMaxExecTime (TimedSDFgraph *g)
static void	clearState (State &s)
static bool	equalStates (const State &s1, const State &s2)
static void	copyState (State &to, const State &from)
static void	createState (State &s)
static void	destroyState (State &s)
static void	resizeStack ()
static void	createStack ()
static void	destroyStack ()
static void	clearStack ()
static void	popStack ()
static void	pushStack (const State &s)
static State &	topStack ()
static void	createHashTable ()
static void	destroyHashTable ()
static void	clearHashTable ()
static HashKey	getHash (const State &s)
static void	insertKeyHashTable (const HashKey key, const StackPos value)
static StackPos	findValueInHashTable (const HashKey key, const State &s)
static void	createDependencies ()
static void	initDependencies ()
static void	createDependencyNode (int a)
static void	addDependencyEdgeForActor (int a)
static void	addDependencyEdgeForChTokens (int a, int c, int s)
static TDtime	outputIntervalCycle (const StackPos cyclePos)
static TDtime	storeState (State &sdfState)
static void	analyzePeriodicPhase ()
static TDtime	execSDFgraph ()
double	stateSpaceAbstractDepGraph (TimedSDFgraph gr, bool nodes, bool **edges, unsigned int stackSz, unsigned int hashSz)
Variables
static TimedSDFgraph *	g
static SDFactor *	outputActor
static SDFtime	SDF_MAX_TIME
static TCnt	outputActorRepCnt
static State *	stack
static StackPos	stackPtr
static StackPos	maxStackPtr
static StackPos	STACK_SIZE
static HashSlot **	hashTable
static HashKey	HASH_TABLE_SIZE
static bool **	curReachableNodes
static bool **	prevReachableNodes
static bool ***	curReachableNodesCh
static bool ***	prevReachableNodesCh
static State	sdfState
static State	prevState
static State	prevStateP

Define Documentation

#define ACT_CLK	(	a,
		t
	)		sdfState.act_clk[a][t]

#define ACT_END_FIRE ( a ) (ACT_CLK(a,0) != 0)

Referenced by analyzePeriodicPhase(), and execSDFgraph().

#define ADVANCE_CLK GLB_CLK = GLB_CLK + 1;

#define CH ( c ) sdfState.ch[c]

Referenced by execSDFgraph().

#define CH_TOKENS	(	c,
		n
	)		(CH(c) >= n)

Referenced by analyzePeriodicPhase(), and execSDFgraph().

#define CH_TOKENS_PREV	(	c,
		n
	)		(prevStateP.ch[c] >= n)

Referenced by analyzePeriodicPhase().

#define CONSUME	(	c,
		n
	)		CH(c) = CH(c) - n;

Referenced by analyzePeriodicPhase(), and execSDFgraph().

#define FIRE_ACT	(	a,
		t
	)		ACT_CLK(a,t)++;

Referenced by analyzePeriodicPhase(), and execSDFgraph().

#define FIRE_ACT_END ( a ) ACT_CLK(a,0)--;

Referenced by analyzePeriodicPhase(), and execSDFgraph().

#define GLB_CLK sdfState.glb_clk

#define INVALID_HASH_KEY NULL

Referenced by createHashTable().

#define LOWER_CLK ( a )

Value:

for (TCnt t = 0; t < SDF_MAX_TIME; t++) \
                                ACT_CLK(a,t) = ACT_CLK(a,t+1); \
                            ACT_CLK(a,SDF_MAX_TIME) = 0;

Referenced by analyzePeriodicPhase(), and execSDFgraph().

#define NEXT_ITER GLB_CLK = 0;

#define NO_SLOT_IN_HASH -1

Referenced by storeState().

#define PRODUCE	(	c,
		n
	)		CH(c) = CH(c) + n;

Referenced by analyzePeriodicPhase(), and execSDFgraph().

#define TDTIME_MAX INT_MAX

Referenced by stateSpaceAbstractDepGraph().

Typedef Documentation

typedef unsigned int HashKey

HashKey

typedef struct _HashSlot HashSlot

HashSlot

typedef int StackPos

StackPos Index into stack.

typedef struct _State State

typedef unsigned long TBufSize

typedef unsigned short TCnt

typedef double TDtime

Function Documentation

static void addDependencyEdgeForActor ( int a ) [inline, static]

addDependencyEdgeForActor () Add a dependency edge to the abstract depndency graph which expresses a dependency of actor a to the previous firing of actor a.

References c, curReachableNodes, curReachableNodesCh, SDFgraph::nrActors(), SDFgraph::nrChannels(), prevReachableNodes, and prevReachableNodesCh.

Referenced by analyzePeriodicPhase().

Here is the call graph for this function:

static void addDependencyEdgeForChTokens	(	int	a,
		int	c,
		int	s
	)			`[inline, static]`

addDependencyEdgeForChTokens () Add a dependency edge to the abstract dependency graph which expresses a dependency of actor s to tokens produced on channel c by the previous firing of actor a.

References curReachableNodes, curReachableNodesCh, SDFgraph::nrActors(), SDFgraph::nrChannels(), prevReachableNodes, and prevReachableNodesCh.

Referenced by analyzePeriodicPhase().

Here is the call graph for this function:

static void analyzePeriodicPhase ( ) [static]

analyzePeriodicPhase () Analyze the periodic phase of the schedule to find the abstract dependency graph.

References a, ACT_END_FIRE, SDFgraph::actorsBegin(), SDFgraph::actorsEnd(), addDependencyEdgeForActor(), addDependencyEdgeForChTokens(), c, CH_TOKENS, CH_TOKENS_PREV, CONSUME, copyState(), createState(), curReachableNodes, curReachableNodesCh, equalStates(), FIRE_ACT, FIRE_ACT_END, SDFport::getActor(), SDFport::getChannel(), TimedSDFactor::getExecutionTime(), SDFcomponent::getId(), SDFport::getRate(), SDFport::getType(), initDependencies(), LOWER_CLK, SDFgraph::nrActors(), SDFgraph::nrChannels(), SDFchannel::oppositePort(), outputActorRepCnt, SDFactor::portsBegin(), SDFactor::portsEnd(), prevReachableNodes, prevReachableNodesCh, and PRODUCE.

Referenced by execSDFgraph().

Here is the call graph for this function:

static void clearHashTable ( ) [static]

clearHashTable () Resets the hash table to contain no keys.

References HASH_TABLE_SIZE, and _HashSlot::next.

Referenced by stateSpaceAbstractDepGraph().

static void clearStack ( ) [static]

clearStack () Reset the stack to an empty state.

References stackPtr.

Referenced by stateSpaceAbstractDepGraph().

static void clearState ( State & s ) [static]

clearState () The function sets the state to zero.

References _State::act_clk, _State::ch, _State::glb_clk, SDFgraph::nrActors(), SDFgraph::nrChannels(), and SDF_MAX_TIME.

Referenced by execSDFgraph().

Here is the call graph for this function:

static void copyState	(	State &	to,
		const State &	from
	)			`[inline, static]`

copyState () The function copies the state.

References _State::act_clk, _State::ch, _State::glb_clk, SDFgraph::nrActors(), SDFgraph::nrChannels(), and SDF_MAX_TIME.

Here is the call graph for this function:

static void createDependencies ( ) [static]

createDependencies () The function creates an initial abstract dependency graph.

References a, curReachableNodes, curReachableNodesCh, SDFgraph::nrActors(), SDFgraph::nrChannels(), prevReachableNodes, and prevReachableNodesCh.

Referenced by stateSpaceAbstractDepGraph().

Here is the call graph for this function:

static void createDependencyNode ( int a ) [inline, static]

createDependencyNode () Create a new dependency node for the actor a and add the dependency to the list 'curDependencyNode'.

References c, curReachableNodes, curReachableNodesCh, SDFgraph::nrActors(), and SDFgraph::nrChannels().

Here is the call graph for this function:

static void createHashTable ( ) [static]

createHashTable () The function constructs a hash table.

References HASH_TABLE_SIZE, and INVALID_HASH_KEY.

Referenced by stateSpaceAbstractDepGraph().

static void createStack ( ) [static]

createStack () The function creates a stack.

References createState(), maxStackPtr, and STACK_SIZE.

Referenced by stateSpaceAbstractDepGraph().

Here is the call graph for this function:

static void createState ( State & s ) [static]

createState () The function allocates memory for a new state.

References _State::act_clk, _State::ch, SDFgraph::nrActors(), SDFgraph::nrChannels(), and SDF_MAX_TIME.

Referenced by analyzePeriodicPhase(), createStack(), execSDFgraph(), and resizeStack().

Here is the call graph for this function:

static void destroyHashTable ( ) [static]

destroyHashTable () The function destoys a hash table.

References HASH_TABLE_SIZE, and _HashSlot::next.

Referenced by stateSpaceAbstractDepGraph().

static void destroyStack ( ) [static]

destroyStack() The function destroys a stack.

References destroyState(), and STACK_SIZE.

Referenced by stateSpaceAbstractDepGraph().

Here is the call graph for this function:

static void destroyState ( State & s ) [static]

destroyState () The function deallocates all data structures of the state

References _State::act_clk, _State::ch, and SDFgraph::nrActors().

Referenced by destroyStack(), and execSDFgraph().

Here is the call graph for this function:

static bool equalStates	(	const State &	s1,
		const State &	s2
	)			`[inline, static]`

equalStates () The function compares to states and returns true if they are equal.

References _State::act_clk, _State::ch, _State::glb_clk, SDFgraph::nrActors(), SDFgraph::nrChannels(), and SDF_MAX_TIME.

Here is the call graph for this function:

static TDtime execSDFgraph ( ) [static]

execSDFgraph() Execute the SDF graph till a deadlock is found or a recurrent state. The output interval (i.e. inverse of throughput) is returned.

References a, ACT_END_FIRE, SDFgraph::actorsBegin(), SDFgraph::actorsEnd(), analyzePeriodicPhase(), CH, CH_TOKENS, SDFgraph::channelsBegin(), SDFgraph::channelsEnd(), clearState(), CONSUME, copyState(), createState(), destroyState(), equalStates(), FIRE_ACT, FIRE_ACT_END, SDFport::getChannel(), TimedSDFactor::getExecutionTime(), SDFcomponent::getId(), SDFchannel::getInitialTokens(), SDFport::getRate(), SDFport::getType(), _State::glb_clk, LOWER_CLK, outputActorRepCnt, SDFactor::portsBegin(), SDFactor::portsEnd(), PRODUCE, and storeState().

Here is the call graph for this function:

static SDFactor* findOutputActor	(	TimedSDFgraph *	g,
		RepetitionVector	repVec
	)			`[static]`

References a, SDFgraph::actorsBegin(), SDFgraph::actorsEnd(), and SDFcomponent::getId().

Referenced by stateSpaceAbstractDepGraph().

Here is the call graph for this function:

static StackPos findValueInHashTable	(	const HashKey	key,
		const State &	s
	)			`[inline, static]`

findVallueInHashTable () The function returns the StackPos at which the given (key,state) pair is located or NO_SLOT_IN_HASH if unkown.

References equalStates(), _HashSlot::next, and _HashSlot::value.

Referenced by storeState().

Here is the call graph for this function:

static HashKey getHash ( const State & s ) [inline, static]

getHash () The hash function. It is a standard multiplication hash.

References _State::act_clk, _State::ch, _State::glb_clk, HASH_TABLE_SIZE, SDFgraph::nrActors(), SDFgraph::nrChannels(), and SDF_MAX_TIME.

Referenced by storeState().

Here is the call graph for this function:

static SDFtime getMaxExecTime ( TimedSDFgraph * g ) [static]

References a, SDFgraph::actorsBegin(), SDFgraph::actorsEnd(), and TimedSDFactor::getExecutionTime().

Referenced by stateSpaceAbstractDepGraph().

Here is the call graph for this function:

static void initDependencies ( ) [inline, static]

initDependencies () The function initializes the dependency stack and the last dependency node pointers.

References a, c, curReachableNodes, curReachableNodesCh, SDFgraph::nrActors(), SDFgraph::nrChannels(), prevReachableNodes, and prevReachableNodesCh.

Referenced by analyzePeriodicPhase().

Here is the call graph for this function:

static void insertKeyHashTable	(	const HashKey	key,
		const StackPos	value
	)			`[inline, static]`

insertKeyHashTable () The function inserts a (key, value) pair into the hash table.

References _HashSlot::next, and _HashSlot::value.

Referenced by storeState().

static TDtime outputIntervalCycle ( const StackPos cyclePos ) [inline, static]

outputIntervalCycle () The function calculates the output interval of the states on the cycle. Its value is equal to the average time between two firings in the cycle.

References SDFcomponent::getId(), _State::glb_clk, and stackPtr.

Referenced by storeState().

Here is the call graph for this function:

static void popStack ( ) [inline, static]

popStack () Remove last element from the stack.

References stackPtr.

static void pushStack ( const State & s ) [inline, static]

pushStack () Put an element on the stack.

References copyState(), maxStackPtr, resizeStack(), STACK_SIZE, and stackPtr.

Referenced by storeState().

Here is the call graph for this function:

static void resizeStack ( ) [static]

resizeStack () Enlarge the stack with a factor of 2.

References createState(), and STACK_SIZE.

Referenced by pushStack().

Here is the call graph for this function:

double stateSpaceAbstractDepGraph	(	TimedSDFgraph *	gr,
		bool ***	nodes,
		bool ****	edges,
		unsigned int	stackSz,
		unsigned int	hashSz
	)

stateSpaceAbstractDepGraph () Compute the throughput and abstract dependency graph of an SDFG for unconstrained buffer sizes and using auto-concurrency using a state-space traversal.

The abstract dependency graph is stored in the matrices 'nodes' (2D) and 'edges' (3D). The value stored at 'nodes[a][b]' indicates whether there is at least one edge which goes directlt from node a to node b. The value stored at 'edges[a][b][c]' indicates wether the channel c in the SDFG has a depedency edge in the abstract dependency graph from node a to node b.

References clearHashTable(), clearStack(), FSMSADF::computeRepetitionVector(), createDependencies(), createHashTable(), createStack(), curReachableNodes, curReachableNodesCh, destroyHashTable(), destroyStack(), execSDFgraph(), findOutputActor(), SDFcomponent::getId(), getMaxExecTime(), HASH_TABLE_SIZE, isStronglyConnectedGraph(), outputActorRepCnt, SDF_MAX_TIME, STACK_SIZE, and TDTIME_MAX.

Referenced by SDFstateSpacePriorityListScheduler::TransitionSystem::initActorPriorities().

Here is the call graph for this function:

static TDtime storeState ( State & sdfState ) [inline, static]

storeState () The function stores the given state at the stack and insert an entry into the hash table. Cycle detection is performed, as well as a check to verify wether a cycle is valid or not.

Return values: -1 - added state to stack >= 0 - output interval of detected cycle

References findValueInHashTable(), getHash(), insertKeyHashTable(), NO_SLOT_IN_HASH, outputIntervalCycle(), pushStack(), and stackPtr.

Referenced by execSDFgraph().

Here is the call graph for this function:

static State& topStack ( ) [inline, static]

topStack () The function returns the last element of the stack.

References stackPtr.

Variable Documentation

bool** curReachableNodes [static]

curReachableNodes The array indicates wether an actor b in the current period has a chain of dependencies to an actor a in the previous period. If there is such a dependency the value of curReachableNodes[b][a] == 1, else it is 0.

The 'curReachableNodesCh' array maintains the information which back channels are seen on at least one of the paths from b to a.

The 'prev' version of both arrays are used during the dependency construction process.

Referenced by addDependencyEdgeForActor(), addDependencyEdgeForChTokens(), analyzePeriodicPhase(), createDependencies(), createDependencyNode(), initDependencies(), and stateSpaceAbstractDepGraph().