#include <bounded_buffer.h>

Collaboration diagram for SDFstateSpaceBindingAwareBufferAnalysis:

Classes
class	TransitionSystem
Public Member Functions
	SDFstateSpaceBindingAwareBufferAnalysis ()
	~SDFstateSpaceBindingAwareBufferAnalysis ()
StorageDistributionSet *	analyze (BindingAwareSDFG bg, bool bufferChannels, bool useBoundsOnBufferChannels, const double thrBound)
Private Member Functions
void	initBoundsSearchSpace (TimedSDFgraph g, bool bufferChannels)
void	initMinimalChannelSzStep (TimedSDFgraph *g)
void	initMinimalChannelSz (TimedSDFgraph g, bool bufferChannels)
void	initLbDistributionSz (TimedSDFgraph *g)
void	initMaxThroughput (TimedSDFgraph *g)
StorageDistribution *	newStorageDistribution ()
void	deleteStorageDistribution (StorageDistribution *d)
void	execStorageDistribution (StorageDistribution d, bool bufferChannels)
void	minimizeStorageDistributionsSet (StorageDistributionSet *ds)
bool	addStorageDistributionToChecklist (StorageDistribution *d)
void	exploreStorageDistribution (StorageDistributionSet ds, StorageDistribution d, bool *bufferChannels, bool useBoundsOnBufferChannels)
void	exploreStorageDistributionSet (StorageDistributionSet ds, bool bufferChannels, bool useBoundsOnBufferChannels)
void	findMinimalStorageDistributions (const double thrBound, bool *bufferChannels, bool useBoundsOnBufferChannels)
Private Attributes
BindingAwareSDFG *	bindingAwareSDFG
TransitionSystem *	transitionSystem
StorageDistributionSet *	minStorageDistributions
TBufSize *	minSz
TBufSize *	minSzStep
TBufSize	lbDistributionSz
TDtime	maxThroughput

Detailed Description

Throughput / storage-space trade-off exploration Analyze the trade-offs between storage distributions and throughput (using auto-concurrency) under the given binding constraints of the application to the architecture graph. The vector 'bufferChannels' indicates for each channel wether initial tokens can be added to it. This is only true for channels modeling buffer space. When the 'useBoundsOnBufferChannels' flag is true, the number of initial tokens (i.e. storage space) is not enlarged above the current number of initial tokens on the edge (i.e. current storage space). This storage space allocation is then a constraint on the maximum amount of storage space that can be allocated to the channel. The exploration ends as soon as the throughput reaches the throughput bound (thrBound) or all minimal storage distributions are found (default).

Constructor & Destructor Documentation

SDFstateSpaceBindingAwareBufferAnalysis::SDFstateSpaceBindingAwareBufferAnalysis ( ) [inline]

SDFstateSpaceBindingAwareBufferAnalysis::~SDFstateSpaceBindingAwareBufferAnalysis ( ) [inline]

Member Function Documentation

bool SDFstateSpaceBindingAwareBufferAnalysis::addStorageDistributionToChecklist ( StorageDistribution * d ) [private]

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, bindingAwareSDFG, c, _StorageDistributionSet::distributions, minStorageDistributions, _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:

StorageDistributionSet * SDFstateSpaceBindingAwareBufferAnalysis::analyze	(	BindingAwareSDFG *	bg,
		bool *	bufferChannels,
		bool	useBoundsOnBufferChannels,
		const double	thrBound
	)

Throughput / storage-space trade-off exploration Analyze the trade-offs between storage distributions and throughput (using auto-concurrency) under the given binding constraints of the application to the architecture graph. The vector 'bufferChannels' indicates for each channel wether initial tokens can be added to it. This is only true for channels modeling buffer space. When the 'useBoundsOnBufferChannels' flag is true, the number of initial tokens (i.e. storage space) is not enlarged above the current number of initial tokens on the edge (i.e. current storage space). This storage space allocation is then a constraint on the maximum amount of storage space that can be allocated to the channel. The exploration ends as soon as the throughput reaches the throughput bound (thrBound) or all minimal storage distributions are found (default).

References bindingAwareSDFG, findMinimalStorageDistributions(), initBoundsSearchSpace(), minStorageDistributions, minSz, minSzStep, and transitionSystem.

Referenced by LoadBalanceBinding::minimizeStorageSpace().

Here is the call graph for this function:

void SDFstateSpaceBindingAwareBufferAnalysis::deleteStorageDistribution ( StorageDistribution * d ) [private]

deleteStorageDistribution () Deallocate memory for a storage distribution.

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

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

void SDFstateSpaceBindingAwareBufferAnalysis::execStorageDistribution	(	StorageDistribution *	d,
		bool *	bufferChannels
	)			`[private]`

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

References bindingAwareSDFG, c, _StorageDistribution::dep, SDFstateSpaceBindingAwareBufferAnalysis::TransitionSystem::execSDFgraph(), SDFgraph::nrChannels(), _StorageDistribution::sp, _StorageDistribution::thr, and transitionSystem.

Referenced by exploreStorageDistribution().

Here is the call graph for this function:

void SDFstateSpaceBindingAwareBufferAnalysis::exploreStorageDistribution	(	StorageDistributionSet *	ds,
		StorageDistribution *	d,
		bool *	bufferChannels,
		bool	useBoundsOnBufferChannels
	)			`[private]`

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(), bindingAwareSDFG, c, deleteStorageDistribution(), _StorageDistribution::dep, execStorageDistribution(), SDFgraph::getChannel(), SDFchannel::getDstActor(), SDFcomponent::getId(), SDFchannel::getInitialTokens(), 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:

void SDFstateSpaceBindingAwareBufferAnalysis::exploreStorageDistributionSet	(	StorageDistributionSet *	ds,
		bool *	bufferChannels,
		bool	useBoundsOnBufferChannels
	)			`[private]`

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:

void SDFstateSpaceBindingAwareBufferAnalysis::findMinimalStorageDistributions	(	const double	thrBound,
		bool *	bufferChannels,
		bool	useBoundsOnBufferChannels
	)			`[private]`

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

References addStorageDistributionToChecklist(), bindingAwareSDFG, c, deleteStorageDistribution(), _StorageDistributionSet::distributions, exploreStorageDistributionSet(), lbDistributionSz, maxThroughput, minStorageDistributions, minSz, newStorageDistribution(), _StorageDistributionSet::next, _StorageDistribution::next, SDFgraph::nrChannels(), _StorageDistributionSet::prev, _StorageDistribution::prev, _StorageDistribution::sp, _StorageDistributionSet::sz, _StorageDistribution::sz, _StorageDistributionSet::thr, and _StorageDistribution::thr.

Referenced by analyze().

Here is the call graph for this function:

void SDFstateSpaceBindingAwareBufferAnalysis::initBoundsSearchSpace	(	TimedSDFgraph *	g,
		bool *	bufferChannels
	)			`[private]`

initBoundsSearchSpace () Compute bounds on the trade-off space that must be explored.

References initLbDistributionSz(), initMaxThroughput(), initMinimalChannelSz(), and initMinimalChannelSzStep().

Referenced by analyze().

Here is the call graph for this function:

void SDFstateSpaceBindingAwareBufferAnalysis::initLbDistributionSz ( TimedSDFgraph * g ) [private]

initLbDistributionSz () Compute lower bound on the buffer size needed for positive throughput

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

Referenced by initBoundsSearchSpace().

Here is the call graph for this function:

void SDFstateSpaceBindingAwareBufferAnalysis::initMaxThroughput ( TimedSDFgraph * g ) [private]

initMaxThroughput () Compute the maximal throughput that can be achieved by the graph.

References maxThroughput.

Referenced by initBoundsSearchSpace().

void SDFstateSpaceBindingAwareBufferAnalysis::initMinimalChannelSz	(	TimedSDFgraph *	g,
		bool *	bufferChannels
	)			`[private]`

initMinimalChannelSz () Compute lower bound on the buffer size needed for positive throughput

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

Here is the call graph for this function:

void SDFstateSpaceBindingAwareBufferAnalysis::initMinimalChannelSzStep ( TimedSDFgraph * g ) [private]

initMinimalChannelSzStep () Compute lower bound on the step size of channels

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

Referenced by initBoundsSearchSpace().

Here is the call graph for this function:

void SDFstateSpaceBindingAwareBufferAnalysis::minimizeStorageDistributionsSet ( StorageDistributionSet * ds ) [private]

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: