#include "storage_distribution.h"
#include "../../base/algo/repetition_vector.h"
#include "../../resource_allocation/binding_aware_sdfg/binding_aware_sdfg.h"

Include dependency graph for analysis/buffersizing/buffer_capacity_constrained.cc:

Classes
class	CapacityConstrainedBufferState
Defines
#define	CH(c) currentState.ch[c]
#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	CH_TOKENS_PREV(c, n) (previousState.ch[c] >= n)
Typedefs
typedef list < CapacityConstrainedBufferState >	CapacityConstrainedBufferStates
typedef CapacityConstrainedBufferStates::iterator	CapacityConstrainedBufferStatesIter
Functions
static void	computeMinimalChannelSzStep (TimedSDFgraph *g)
static void	computeMinimalChannelSz (TimedSDFgraph *g)
static void	computeLbDistributionSz (TimedSDFgraph *g)
static void	findOutputActor (TimedSDFgraph *g)
static void	findMaxThroughput (TimedSDFgraph *g, double maxThr)
static void	initGlobals (TimedSDFgraph *g, double maxThr)
static void	clearState (CapacityConstrainedBufferState &s)
bool	equalStates (const CapacityConstrainedBufferState &s1, const CapacityConstrainedBufferState &s2)
void	copyState (CapacityConstrainedBufferState &to, const CapacityConstrainedBufferState &from)
static bool	storeState (CapacityConstrainedBufferState &s, CapacityConstrainedBufferStatesIter &pos)
static void	clearStoredStates ()
static void	dfsVisitDependencies (uint a, int color, int pi, bool *abstractDepGraph, bool dep)
static void	findStorageDependencies (bool *abstractDepGraph, bool dep)
static TDtime	computeThroughput (const CapacityConstrainedBufferStatesIter cycleIter)
static bool	actorReadyToFire (SDFactor *a)
static void	startActorFiring (TimedSDFactor *a)
static bool	actorReadyToEnd (SDFactor *a)
static void	endActorFiring (SDFactor *a)
static SDFtime	clockStep ()
static void	findCausalDependencies (SDFactor a, bool *abstractDepGraph)
static void	analyzePeriodicPhase (bool *dep)
static void	analyzeDeadlock (bool *dep)
static TDtime	execSDFgraph (const TBufSize sp, bool dep)
static StorageDistribution *	newStorageDistribution ()
static void	deleteStorageDistribution (StorageDistribution *d)
static void	execStorageDistribution (StorageDistribution *d)
static void	minimizeStorageDistributionsSet (StorageDistributionSet *ds)
static bool	addStorageDistributionToChecklist (StorageDistribution *d)
static void	exploreStorageDistribution (StorageDistributionSet ds, StorageDistribution d)
static void	exploreStorageDistributionSet (StorageDistributionSet *ds)
static void	findMinimalStorageDistributions ()
StorageDistributionSet *	stateSpaceBufferAnalysisCapacityConstrainedModel (TimedSDFgraph *gr, double maxThr)
Variables
static TimedSDFgraph *	g
static TBufSize *	minSz
static TBufSize *	minSzStep
static TBufSize	lbDistributionSz
static TDtime	maxThroughput
static SDFactor *	outputActor
static TCnt	outputActorRepCnt
static CapacityConstrainedBufferStates	storedStates
static CapacityConstrainedBufferState	currentState (0, 0)
static CapacityConstrainedBufferState	previousState (0, 0)
static StorageDistributionSet *	minStorageDistributions = NULL

Define Documentation

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

Referenced by execSDFgraph().

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

Referenced by actorReadyToFire(), and analyzeDeadlock().

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

Referenced by findCausalDependencies().

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

Referenced by startActorFiring().

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

Referenced by endActorFiring().

Typedef Documentation

typedef list<CapacityConstrainedBufferState> CapacityConstrainedBufferStates

typedef CapacityConstrainedBufferStates::iterator CapacityConstrainedBufferStatesIter

Function Documentation

static bool actorReadyToEnd ( SDFactor * a ) [inline, static]

actorReadyToEnd () The function returns true when the actor is ready to end its firing. Else the function returns false.

References CapacityConstrainedBufferState::actClk, currentState, and SDFcomponent::getId().

Referenced by analyzePeriodicPhase(), SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execConstrainedSDFgraph(), SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execSDFgraph(), and execSDFgraph().

Here is the call graph for this function:

static bool actorReadyToFire ( SDFactor * a ) [inline, static]

actorReadyToFire () The function returns true when the actor is ready to fire in state s. Else it returns false.

References c, CH_TOKENS, SDFport::getChannel(), SDFcomponent::getId(), SDFport::getRate(), SDFport::getType(), SDFactor::portsBegin(), and SDFactor::portsEnd().

Referenced by analyzePeriodicPhase(), SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execConstrainedSDFgraph(), SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execSDFgraph(), and execSDFgraph().

Here is the call graph for this function:

static bool addStorageDistributionToChecklist ( StorageDistribution * d ) [static]

addStorageDistributionToChecklist () The function add the storage distribution 'd' to the list of storage distributions which must still be checked. This list is ordered wrt to the size of the storage distribution. A storage distribution is only added if it is not already contained in the list. When the distribution is added to the list, the function returns 'true', else the function returns 'false'.

References ASSERT, c, _StorageDistributionSet::distributions, _StorageDistribution::next, _StorageDistributionSet::next, SDFgraph::nrChannels(), _StorageDistribution::prev, _StorageDistributionSet::prev, _StorageDistribution::sp, _StorageDistribution::sz, _StorageDistributionSet::sz, and _StorageDistributionSet::thr.

Referenced by exploreStorageDistribution(), and findMinimalStorageDistributions().

Here is the call graph for this function:

static void analyzeDeadlock ( bool * dep ) [static]

analyzeDeadlock () Analyze the deadlock in the schedule.

References c, CH_TOKENS, SDFgraph::channelsBegin(), SDFgraph::channelsEnd(), findStorageDependencies(), SDFchannel::getDstActor(), SDFchannel::getDstPort(), SDFcomponent::getId(), SDFport::getRate(), SDFchannel::getSrcActor(), and SDFgraph::nrActors().

Referenced by execSDFgraph().

Here is the call graph for this function:

static void analyzePeriodicPhase ( bool * dep ) [static]

analyzePeriodicPhase () Analyze the periodic phase of the schedule to find all blocked channels. This is done using the abstract dependency graph.

References a, actorReadyToEnd(), actorReadyToFire(), SDFgraph::actorsBegin(), SDFgraph::actorsEnd(), CapacityConstrainedBufferState::ch, clockStep(), copyState(), currentState, endActorFiring(), equalStates(), findCausalDependencies(), findStorageDependencies(), SDFcomponent::getId(), CapacityConstrainedBufferState::glbClk, SDFgraph::nrActors(), SDFgraph::nrChannels(), outputActorRepCnt, previousState, and startActorFiring().

Referenced by execSDFgraph().

Here is the call graph for this function:

static void clearState ( CapacityConstrainedBufferState & s ) [static]

clearState () The function sets the state to zero.

References CapacityConstrainedBufferState::actClk, CapacityConstrainedBufferState::ch, CapacityConstrainedBufferState::glbClk, SDFgraph::nrActors(), and SDFgraph::nrChannels().

Referenced by execSDFgraph().

Here is the call graph for this function:

static void clearStoredStates ( ) [static]

clearStoredStates () The function clears the list of stored states.

Referenced by SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execConstrainedSDFgraph(), SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execSDFgraph(), execSDFgraph(), and execStorageDistribution().

static SDFtime clockStep ( ) [inline, static]

clockStep () The function progresses time till the first end of firing transition becomes enabled. The time step is returned. In case of deadlock, the time step is equal to UINT_MAX.

References a, CapacityConstrainedBufferState::actClk, currentState, CapacityConstrainedBufferState::glbClk, and SDFgraph::nrActors().

Referenced by analyzePeriodicPhase(), SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execConstrainedSDFgraph(), SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execSDFgraph(), and execSDFgraph().

Here is the call graph for this function:

static void computeLbDistributionSz ( TimedSDFgraph * g ) [static]

References c, lbDistributionSz, minSz, and SDFgraph::nrChannels().

Referenced by initGlobals().

Here is the call graph for this function:

static void computeMinimalChannelSz ( TimedSDFgraph * g ) [static]

References c, SDFgraph::channelsBegin(), SDFgraph::channelsEnd(), gcd(), SDFchannel::getDstActor(), SDFchannel::getDstPort(), SDFcomponent::getId(), SDFchannel::getInitialTokens(), SDFport::getRate(), SDFchannel::getSrcActor(), SDFchannel::getSrcPort(), minSz, and SDFgraph::nrChannels().

Referenced by initGlobals().

Here is the call graph for this function:

static void computeMinimalChannelSzStep ( TimedSDFgraph * g ) [static]

References c, SDFgraph::channelsBegin(), SDFgraph::channelsEnd(), gcd(), SDFchannel::getDstPort(), SDFcomponent::getId(), SDFport::getRate(), SDFchannel::getSrcPort(), minSzStep, and SDFgraph::nrChannels().

Referenced by initGlobals().

Here is the call graph for this function:

static TDtime computeThroughput ( const CapacityConstrainedBufferStatesIter cycleIter ) [inline, static]

computeThroughput () The function calculates the throughput of the states on the cycle. Its value is equal to the average number of firings of an actor per time unit.

References CapacityConstrainedBufferState::glbClk.

Referenced by SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execConstrainedSDFgraph(), and execSDFgraph().

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

copyState () The function copies the state.

References CapacityConstrainedBufferState::actClk, CapacityConstrainedBufferState::ch, CapacityConstrainedBufferState::glbClk, SDFgraph::nrActors(), and SDFgraph::nrChannels().

Referenced by analyzePeriodicPhase(), execSDFgraph(), and pushStack().

Here is the call graph for this function:

static void deleteStorageDistribution ( StorageDistribution * d ) [static]

deleteStorageDistribution () Deallocate memory for a storage distribution.

References _StorageDistribution::dep, and _StorageDistribution::sp.

Referenced by exploreStorageDistribution(), findMinimalStorageDistributions(), and minimizeStorageDistributionsSet().

static void dfsVisitDependencies	(	uint	a,
		int *	color,
		int *	pi,
		bool **	abstractDepGraph,
		bool *	dep
	)			`[static]`

dfsVisitDependencies () The function performs a DFS on the abstract dependency graph from a node a to find all cycles of which a is part. Channels on a cycle are when needed marked to have a storage dependency.

References c, SDFgraph::channelsBegin(), SDFgraph::channelsEnd(), SDFchannel::getDstActor(), SDFcomponent::getId(), SDFchannel::getSrcActor(), and SDFgraph::nrActors().

Referenced by findStorageDependencies().

Here is the call graph for this function:

static void endActorFiring ( SDFactor * a ) [inline, static]

endActorFiring () Produce tokens on all output channels and remove the actor firing from the list of active firings.

References CapacityConstrainedBufferState::actClk, c, currentState, SDFport::getChannel(), SDFcomponent::getId(), SDFport::getRate(), SDFport::getType(), SDFactor::portsBegin(), SDFactor::portsEnd(), and PRODUCE.

Referenced by analyzePeriodicPhase(), SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execConstrainedSDFgraph(), SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execSDFgraph(), and execSDFgraph().

Here is the call graph for this function:

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

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

References CapacityConstrainedBufferState::actClk, CapacityConstrainedBufferState::ch, CapacityConstrainedBufferState::glbClk, SDFgraph::nrActors(), and SDFgraph::nrChannels().

Referenced by analyzePeriodicPhase(), execSDFgraph(), findValueInHashTable(), and storeState().

Here is the call graph for this function:

static TDtime execSDFgraph	(	const TBufSize *	sp,
		bool *	dep
	)			`[static]`

execSDFgraph() Execute the SDF graph till a deadlock is found or a recurrent state. The throughput is returned.

References a, actorReadyToEnd(), actorReadyToFire(), SDFgraph::actorsBegin(), SDFgraph::actorsEnd(), analyzeDeadlock(), analyzePeriodicPhase(), c, CapacityConstrainedBufferState::ch, CH, SDFgraph::channelsBegin(), SDFgraph::channelsEnd(), clearState(), clearStoredStates(), clockStep(), computeThroughput(), currentState, endActorFiring(), SDFcomponent::getId(), SDFchannel::getInitialTokens(), CapacityConstrainedBufferState::glbClk, CapacityConstrainedBufferState::init(), TimedSDFchannel::modelsStorageSpace(), SDFgraph::nrActors(), SDFgraph::nrChannels(), outputActorRepCnt, previousState, startActorFiring(), and storeState().

Referenced by execStorageDistribution(), latencyAnalysisForRandomStaticOrderSingleProc(), and stateSpaceAbstractDepGraph().

Here is the call graph for this function:

static void execStorageDistribution ( StorageDistribution * d ) [static]

execStorageDistribution () Compute throughput and storage dependencies of the given storage distribution.

References c, clearStoredStates(), _StorageDistribution::dep, execSDFgraph(), SDFgraph::nrChannels(), _StorageDistribution::sp, and _StorageDistribution::thr.

Referenced by exploreStorageDistribution().

Here is the call graph for this function:

static void exploreStorageDistribution	(	StorageDistributionSet *	ds,
		StorageDistribution *	d
	)			`[static]`

exploreStorageDistribution () The function computes the throughput of the storage distribution 'd' and adds new storage distributions to the list of distributions which must be checked based on the storage dependencies found in d. The function also updates the maximal throughput of the set of storage distributions when needed.

References addStorageDistributionToChecklist(), c, deleteStorageDistribution(), _StorageDistribution::dep, execStorageDistribution(), SDFgraph::getChannel(), SDFchannel::getDstActor(), SDFcomponent::getId(), SDFchannel::getSrcActor(), minSzStep, newStorageDistribution(), _StorageDistribution::next, SDFgraph::nrChannels(), _StorageDistribution::prev, _StorageDistribution::sp, _StorageDistribution::sz, _StorageDistributionSet::thr, and _StorageDistribution::thr.

Referenced by exploreStorageDistributionSet().

Here is the call graph for this function:

static void exploreStorageDistributionSet ( StorageDistributionSet * ds ) [static]

exploreStorageDistributionSet () Explore all distributions within the set and remove all non-minimal distributions from it.

References _StorageDistributionSet::distributions, exploreStorageDistribution(), minimizeStorageDistributionsSet(), and _StorageDistribution::next.

Referenced by findMinimalStorageDistributions().

Here is the call graph for this function:

static void findCausalDependencies	(	SDFactor *	a,
		bool **	abstractDepGraph
	)			`[static]`

findCausalDependencies () The function tracks all causal dependencies in the actor firing of actor a. Any causal dependency that is found is added to the abstract dependency graph.

References c, CH_TOKENS_PREV, SDFport::getChannel(), SDFchannel::getDstActor(), SDFcomponent::getId(), SDFport::getRate(), SDFchannel::getSrcActor(), SDFport::getType(), SDFactor::portsBegin(), and SDFactor::portsEnd().

Referenced by analyzePeriodicPhase().

Here is the call graph for this function:

static void findMaxThroughput	(	TimedSDFgraph *	g,
		double	maxThr
	)			`[static]`

References maxThroughput.

Referenced by initGlobals().

static void findMinimalStorageDistributions ( ) [static]

findMinimalStorageDistributions () Explore the throughput/storage-size trade-off space till either all minimal storage distributions are found or the throughput bound is reached.

Referenced by stateSpaceBufferAnalysisCapacityConstrainedModel().

Here is the call graph for this function:

static void findOutputActor ( TimedSDFgraph * g ) [static]

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

Referenced by initGlobals().

Here is the call graph for this function:

static void findStorageDependencies	(	bool **	abstractDepGraph,
		bool *	dep
	)			`[static]`

findStorageDependencies () The function find all cycles in the abstract dependency graph. Any channel modeling storage space which is part of a cycle is marked to have a storage dependency.

References c, color, dfsVisitDependencies(), SDFgraph::getChannel(), SDFgraph::nrActors(), SDFgraph::nrChannels(), and pi.

Referenced by analyzeDeadlock(), and analyzePeriodicPhase().

Here is the call graph for this function:

static void initGlobals	(	TimedSDFgraph *	g,
		double	maxThr
	)			`[static]`

References computeLbDistributionSz(), computeMinimalChannelSz(), computeMinimalChannelSzStep(), findMaxThroughput(), and findOutputActor().

Referenced by stateSpaceBufferAnalysisCapacityConstrainedModel().

Here is the call graph for this function:

static void minimizeStorageDistributionsSet ( StorageDistributionSet * ds ) [static]

minimizeMinStorageDistributions () The function removes all storage distributions within the supplied set of storage distributions which are non-minimal. All storage distributions within the set should have the same size.

References deleteStorageDistribution(), _StorageDistributionSet::distributions, _StorageDistribution::next, _StorageDistribution::prev, _StorageDistributionSet::prev, _StorageDistribution::thr, and _StorageDistributionSet::thr.

Referenced by exploreStorageDistributionSet().

Here is the call graph for this function:

static StorageDistribution* newStorageDistribution ( ) [static]

newStorageDistribution () Allocate memory for a new storage distribution.

References _StorageDistribution::dep, SDFgraph::nrChannels(), and _StorageDistribution::sp.

Referenced by exploreStorageDistribution(), and findMinimalStorageDistributions().

Here is the call graph for this function:

static void startActorFiring ( TimedSDFactor * a ) [inline, static]

startActorFiring () Start the actor firing. Remove tokens from all input channels and add the actor firing to the list of active actor firings and advance sequence position.

References CapacityConstrainedBufferState::actClk, c, CONSUME, currentState, SDFport::getChannel(), TimedSDFactor::getExecutionTime(), SDFcomponent::getId(), SDFport::getRate(), SDFport::getType(), SDFactor::portsBegin(), and SDFactor::portsEnd().

Referenced by analyzePeriodicPhase(), SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execConstrainedSDFgraph(), SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execSDFgraph(), and execSDFgraph().

Here is the call graph for this function:

StorageDistributionSet* stateSpaceBufferAnalysisCapacityConstrainedModel	(	TimedSDFgraph *	gr,
		double	maxThr
	)

stateSpaceBufferAnalysisCapacityConstrainedModel () Analyze the trade-offs between storage distributions and throughput (using auto-concurrency). Storage space allocations are determined for all channels modelling storage space in the capacity constrained model.

References findMinimalStorageDistributions(), and initGlobals().

Referenced by analyzeSDFG().

Here is the call graph for this function:

static bool storeState	(	CapacityConstrainedBufferState &	s,
		CapacityConstrainedBufferStatesIter &	pos
	)			`[static]`

storeState () The function stores the state s on whenever s is not already in the list of storedStates. When s is stored, the function returns true. When the state s is already in the list, the state s is not stored. The function returns false. The function always sets the pos variable to the position where the state s is in the list.

References equalStates().

Referenced by SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execConstrainedSDFgraph(), SDFstateSpaceSelfTimedMinimalLatencyAnalysis::TransitionSystem::execSDFgraph(), and execSDFgraph().

Here is the call graph for this function: